LLVM  14.0.0git
ReplaceConstant.cpp
Go to the documentation of this file.
1 //===- ReplaceConstant.cpp - Replace LLVM constant expression--------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements a utility function for replacing LLVM constant
10 // expressions by instructions.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/IR/IRBuilder.h"
16 #include "llvm/IR/Instructions.h"
17 #include "llvm/IR/NoFolder.h"
18 
19 namespace llvm {
20 // Replace a constant expression by instructions with equivalent operations at
21 // a specified location.
23  auto *CEInstr = CE->getAsInstruction();
24  CEInstr->insertBefore(Instr);
25  return CEInstr;
26 }
27 
30  // Collect all reachable paths to CE from constant exprssion operands of I.
31  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
32  collectConstantExprPaths(I, CE, CEPaths);
33 
34  // Convert all constant expressions to instructions which are collected at
35  // CEPaths.
36  convertConstantExprsToInstructions(I, CEPaths, Insts);
37 }
38 
40  Instruction *I,
41  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
44  for (Use &U : I->operands()) {
45  // The operand U is either not a constant expression operand or the
46  // constant expression paths do not belong to U, ignore U.
47  if (!CEPaths.count(&U))
48  continue;
49 
50  // If the instruction I is a PHI instruction, then fix the instruction
51  // insertion point to the entry of the incoming basic block for operand U.
52  auto *BI = I;
53  if (auto *Phi = dyn_cast<PHINode>(I)) {
54  BasicBlock *BB = Phi->getIncomingBlock(U);
55  BI = &(*(BB->getFirstInsertionPt()));
56  }
57 
58  // Go through the paths associated with operand U, and convert all the
59  // constant expressions along all paths to corresponding instructions.
60  auto *II = I;
61  auto &Paths = CEPaths[&U];
62  for (auto &Path : Paths) {
63  for (auto *CE : Path) {
64  if (!Visited.insert(CE).second)
65  continue;
66  auto *NI = CE->getAsInstruction();
67  NI->insertBefore(BI);
68  II->replaceUsesOfWith(CE, NI);
69  CE->removeDeadConstantUsers();
70  BI = II = NI;
71  if (Insts)
72  Insts->insert(NI);
73  }
74  }
75  }
76 }
77 
80  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
81  for (Use &U : I->operands()) {
82  // If the operand U is not a constant expression operand, then ignore it.
83  auto *CE2 = dyn_cast<ConstantExpr>(U.get());
84  if (!CE2)
85  continue;
86 
87  // Holds all reachable paths from CE2 to CE.
88  std::vector<std::vector<ConstantExpr *>> Paths;
89 
90  // Collect all reachable paths from CE2 to CE.
91  std::vector<ConstantExpr *> Path{CE2};
92  std::vector<std::vector<ConstantExpr *>> Stack{Path};
93  while (!Stack.empty()) {
94  std::vector<ConstantExpr *> TPath = Stack.back();
95  Stack.pop_back();
96  auto *CE3 = TPath.back();
97 
98  if (CE3 == CE) {
99  Paths.push_back(TPath);
100  continue;
101  }
102 
103  for (auto &UU : CE3->operands()) {
104  if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
105  std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
106  NPath.push_back(CE4);
107  Stack.push_back(NPath);
108  }
109  }
110  }
111 
112  // Associate all the collected paths with U, and save it.
113  if (!Paths.empty())
114  CEPaths[&U] = Paths;
115  }
116 }
117 
118 } // namespace llvm
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
NoFolder.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::convertConstantExprsToInstructions
void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE, SmallPtrSetImpl< Instruction * > *Insts=nullptr)
The given instruction I contains given constant expression CE as one of its operands,...
Definition: ReplaceConstant.cpp:28
llvm::Instruction
Definition: Instruction.h:45
I
#define I(x, y, z)
Definition: MD5.cpp:59
IRBuilder.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:936
llvm::collectConstantExprPaths
void collectConstantExprPaths(Instruction *I, ConstantExpr *CE, std::map< Use *, std::vector< std::vector< ConstantExpr * >>> &CEPaths)
Given an instruction I which uses given constant expression CE as operand, either directly or nested ...
Definition: ReplaceConstant.cpp:78
Instructions.h
ReplaceConstant.h
llvm::SmallPtrSetImpl< Instruction * >
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::createReplacementInstr
Instruction * createReplacementInstr(ConstantExpr *CE, Instruction *Instr)
Create a replacement instruction for constant expression CE and insert it before Instr.
Definition: ReplaceConstant.cpp:22
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364