LLVM 17.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/ADT/SetVector.h"
17#include "llvm/IR/Constants.h"
19#include "llvm/IR/ValueMap.h"
20
21namespace llvm {
22
25 // Collect all reachable paths to CE from constant exprssion operands of I.
26 std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
27 collectConstantExprPaths(I, CE, CEPaths);
28
29 // Convert all constant expressions to instructions which are collected at
30 // CEPaths.
32}
33
36 std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
39
40 for (Use &U : I->operands()) {
41 // The operand U is either not a constant expression operand or the
42 // constant expression paths do not belong to U, ignore U.
43 if (!CEPaths.count(&U))
44 continue;
45
46 // If the instruction I is a PHI instruction, then fix the instruction
47 // insertion point to the entry of the incoming basic block for operand U.
48 auto *BI = I;
49 if (auto *Phi = dyn_cast<PHINode>(I)) {
50 BasicBlock *BB = Phi->getIncomingBlock(U);
51 BI = &(*(BB->getFirstInsertionPt()));
52 }
53
54 // Go through all the paths associated with operand U, and convert all the
55 // constant expressions along all the paths to corresponding instructions.
56 auto *II = I;
57 auto &Paths = CEPaths[&U];
58 for (auto &Path : Paths) {
59 for (auto *CE : Path) {
60 // Instruction which is equivalent to CE.
61 Instruction *NI = nullptr;
62
63 if (!Visited.count(CE)) {
64 // CE is encountered first time, convert it into a corresponding
65 // instruction NI, and appropriately insert NI before the parent
66 // instruction.
67 NI = CE->getAsInstruction(BI);
68
69 // Mark CE as visited by mapping CE to NI.
70 Visited[CE] = NI;
71
72 // If required collect NI.
73 if (Insts)
74 Insts->insert(NI);
75 } else {
76 // We had already encountered CE, the correponding instruction already
77 // exist, use it to replace CE.
78 NI = Visited[CE];
79 }
80
81 assert(NI && "Expected an instruction corresponding to constant "
82 "expression.");
83
84 // Replace all uses of constant expression CE by the corresponding
85 // instruction NI within the current parent instruction.
86 II->replaceUsesOfWith(CE, NI);
87 BI = II = NI;
88 }
89 }
90 }
91
92 // Remove all converted constant expressions which are dead by now.
93 for (auto Item : Visited)
94 Item.first->removeDeadConstantUsers();
95}
96
99 std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
100 for (Use &U : I->operands()) {
101 // If the operand U is not a constant expression operand, then ignore it.
102 auto *CE2 = dyn_cast<ConstantExpr>(U.get());
103 if (!CE2)
104 continue;
105
106 // Holds all reachable paths from CE2 to CE.
107 std::vector<std::vector<ConstantExpr *>> Paths;
108
109 // Collect all reachable paths from CE2 to CE.
110 std::vector<ConstantExpr *> Path{CE2};
111 std::vector<std::vector<ConstantExpr *>> Stack{Path};
112 while (!Stack.empty()) {
113 std::vector<ConstantExpr *> TPath = Stack.back();
114 Stack.pop_back();
115 auto *CE3 = TPath.back();
116
117 if (CE3 == CE) {
118 Paths.push_back(TPath);
119 continue;
120 }
121
122 for (auto &UU : CE3->operands()) {
123 if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
124 std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
125 NPath.push_back(CE4);
126 Stack.push_back(NPath);
127 }
128 }
129 }
130
131 // Associate all the collected paths with U, and save it.
132 if (!Paths.empty())
133 CEPaths[&U] = Paths;
134 }
135}
136
137static bool isExpandableUser(User *U) {
138 return isa<ConstantExpr>(U) || isa<ConstantAggregate>(U);
139}
140
142 if (auto *CE = dyn_cast<ConstantExpr>(C)) {
143 return CE->getAsInstruction(InsertPt);
144 } else if (isa<ConstantStruct>(C) || isa<ConstantArray>(C)) {
145 Value *V = PoisonValue::get(C->getType());
146 for (auto [Idx, Op] : enumerate(C->operands()))
147 V = InsertValueInst::Create(V, Op, Idx, "", InsertPt);
148 return cast<Instruction>(V);
149 } else if (isa<ConstantVector>(C)) {
150 Type *IdxTy = Type::getInt32Ty(C->getContext());
151 Value *V = PoisonValue::get(C->getType());
152 for (auto [Idx, Op] : enumerate(C->operands()))
153 V = InsertElementInst::Create(V, Op, ConstantInt::get(IdxTy, Idx), "",
154 InsertPt);
155 return cast<Instruction>(V);
156 } else {
157 llvm_unreachable("Not an expandable user");
158 }
159}
160
162 // Find all expandable direct users of Consts.
164 for (Constant *C : Consts)
165 for (User *U : C->users())
166 if (isExpandableUser(U))
167 Stack.push_back(cast<Constant>(U));
168
169 // Include transitive users.
170 SetVector<Constant *> ExpandableUsers;
171 while (!Stack.empty()) {
172 Constant *C = Stack.pop_back_val();
173 if (!ExpandableUsers.insert(C))
174 continue;
175
176 for (auto *Nested : C->users())
177 if (isExpandableUser(Nested))
178 Stack.push_back(cast<Constant>(Nested));
179 }
180
181 // Find all instructions that use any of the expandable users
183 for (Constant *C : ExpandableUsers)
184 for (User *U : C->users())
185 if (auto *I = dyn_cast<Instruction>(U))
186 InstructionWorklist.insert(I);
187
188 // Replace those expandable operands with instructions
189 bool Changed = false;
190 while (!InstructionWorklist.empty()) {
191 Instruction *I = InstructionWorklist.pop_back_val();
192 for (Use &U : I->operands()) {
193 auto *BI = I;
194 if (auto *Phi = dyn_cast<PHINode>(I)) {
195 BasicBlock *BB = Phi->getIncomingBlock(U);
197 assert(It != BB->end() && "Unexpected empty basic block");
198 BI = &*It;
199 }
200
201 if (auto *C = dyn_cast<Constant>(U.get())) {
202 if (ExpandableUsers.contains(C)) {
203 Changed = true;
204 Instruction *NI = expandUser(BI, C);
205 InstructionWorklist.insert(NI);
206 U.set(NI);
207 }
208 }
209 }
210 }
211
212 for (Constant *C : Consts)
213 C->removeDeadConstantUsers();
214
215 return Changed;
216}
217
218} // namespace llvm
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
@ Paths
Definition: TextStubV5.cpp:120
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:325
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:254
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1002
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
This is an important base class in LLVM.
Definition: Constant.h:41
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1750
A vector that has set insertion semantics.
Definition: SetVector.h:51
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:213
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
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:365
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt32Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
See the file comment.
Definition: ValueMap.h:84
size_type count(const KeyT &Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: ValueMap.h:151
LLVM Value Representation.
Definition: Value.h:74
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool convertUsersOfConstantsToInstructions(ArrayRef< Constant * > Consts)
Replace constant expressions users of the given constants with instructions.
static Instruction * expandUser(Instruction *InsertPt, Constant *C)
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2430
static bool isExpandableUser(User *U)
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 ...
void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE, SmallPtrSetImpl< Instruction * > *Insts=nullptr)
The given instruction I contains given constant expression CE as one of its operands,...