LLVM  13.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.
24  unsigned OpCode = CE->getOpcode();
25  switch (OpCode) {
26  case Instruction::GetElementPtr: {
27  SmallVector<Value *, 4> CEOpVec(CE->operands());
28  ArrayRef<Value *> CEOps(CEOpVec);
29  return dyn_cast<Instruction>(
30  Builder.CreateInBoundsGEP(cast<GEPOperator>(CE)->getSourceElementType(),
31  CEOps[0], CEOps.slice(1)));
32  }
33  case Instruction::Add:
34  case Instruction::Sub:
35  case Instruction::Mul:
36  case Instruction::UDiv:
37  case Instruction::SDiv:
38  case Instruction::FDiv:
39  case Instruction::URem:
40  case Instruction::SRem:
41  case Instruction::FRem:
42  case Instruction::Shl:
43  case Instruction::LShr:
44  case Instruction::AShr:
45  case Instruction::And:
46  case Instruction::Or:
47  case Instruction::Xor:
48  return dyn_cast<Instruction>(
49  Builder.CreateBinOp((Instruction::BinaryOps)OpCode, CE->getOperand(0),
50  CE->getOperand(1), CE->getName()));
51  case Instruction::Trunc:
52  case Instruction::ZExt:
53  case Instruction::SExt:
54  case Instruction::FPToUI:
55  case Instruction::FPToSI:
56  case Instruction::UIToFP:
57  case Instruction::SIToFP:
58  case Instruction::FPTrunc:
59  case Instruction::FPExt:
60  case Instruction::PtrToInt:
61  case Instruction::IntToPtr:
62  case Instruction::BitCast:
63  case Instruction::AddrSpaceCast:
64  return dyn_cast<Instruction>(
65  Builder.CreateCast((Instruction::CastOps)OpCode, CE->getOperand(0),
66  CE->getType(), CE->getName()));
67  default:
68  llvm_unreachable("Unhandled constant expression!\n");
69  }
70 }
71 
74  // Collect all reachable paths to CE from constant exprssion operands of I.
75  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
76  collectConstantExprPaths(I, CE, CEPaths);
77 
78  // Convert all constant expressions to instructions which are collected at
79  // CEPaths.
80  convertConstantExprsToInstructions(I, CEPaths, Insts);
81 }
82 
84  Instruction *I,
85  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
87  for (Use &U : I->operands()) {
88  // The operand U is either not a constant expression operand or the
89  // constant expression paths do not belong to U, ignore U.
90  if (!CEPaths.count(&U))
91  continue;
92 
93  // If the instruction I is a PHI instruction, then fix the instruction
94  // insertion point to the entry of the incoming basic block for operand U.
95  auto *BI = I;
96  if (auto *Phi = dyn_cast<PHINode>(I)) {
97  BasicBlock *BB = Phi->getIncomingBlock(U);
98  BI = &(*(BB->getFirstInsertionPt()));
99  }
100 
101  // Go through the paths associated with operand U, and convert all the
102  // constant expressions along all paths to corresponding instructions.
103  auto *II = I;
104  auto &Paths = CEPaths[&U];
106  for (auto &Path : Paths) {
107  for (auto *CE : Path) {
108  if (!Visited.insert(CE).second)
109  continue;
110  auto *NI = CE->getAsInstruction();
111  NI->insertBefore(BI);
112  II->replaceUsesOfWith(CE, NI);
113  CE->removeDeadConstantUsers();
114  BI = II = NI;
115  if (Insts)
116  Insts->insert(NI);
117  }
118  }
119  }
120 }
121 
123  Instruction *I, ConstantExpr *CE,
124  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
125  for (Use &U : I->operands()) {
126  // If the operand U is not a constant expression operand, then ignore it.
127  auto *CE2 = dyn_cast<ConstantExpr>(U.get());
128  if (!CE2)
129  continue;
130 
131  // Holds all reachable paths from CE2 to CE.
132  std::vector<std::vector<ConstantExpr *>> Paths;
133 
134  // Collect all reachable paths from CE2 to CE.
135  std::vector<ConstantExpr *> Path{CE2};
136  std::vector<std::vector<ConstantExpr *>> Stack{Path};
137  while (!Stack.empty()) {
138  std::vector<ConstantExpr *> TPath = Stack.back();
139  Stack.pop_back();
140  auto *CE3 = TPath.back();
141 
142  if (CE3 == CE) {
143  Paths.push_back(TPath);
144  continue;
145  }
146 
147  for (auto &UU : CE3->operands()) {
148  if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
149  std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
150  NPath.push_back(CE4);
151  Stack.push_back(NPath);
152  }
153  }
154  }
155 
156  // Associate all the collected paths with U, and save it.
157  if (!Paths.empty())
158  CEPaths[&U] = Paths;
159  }
160 }
161 
162 } // namespace llvm
llvm
Definition: AllocatorList.h:23
NoFolder.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::IRBuilder
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2604
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:72
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:787
llvm::Instruction
Definition: Instruction.h:45
llvm::ArrayRef::slice
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
Definition: ArrayRef.h:195
I
#define I(x, y, z)
Definition: MD5.cpp:59
IRBuilder.h
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:931
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:122
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:773
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