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
14 #include "llvm/IR/ReplaceConstant.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/IR/Constants.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/ValueMap.h"
19
20 namespace llvm {
21
convertConstantExprsToInstructions(Instruction * I,ConstantExpr * CE,SmallPtrSetImpl<Instruction * > * Insts)22 void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE,
23 SmallPtrSetImpl<Instruction *> *Insts) {
24 // Collect all reachable paths to CE from constant exprssion operands of I.
25 std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
26 collectConstantExprPaths(I, CE, CEPaths);
27
28 // Convert all constant expressions to instructions which are collected at
29 // CEPaths.
30 convertConstantExprsToInstructions(I, CEPaths, Insts);
31 }
32
convertConstantExprsToInstructions(Instruction * I,std::map<Use *,std::vector<std::vector<ConstantExpr * >>> & CEPaths,SmallPtrSetImpl<Instruction * > * Insts)33 void convertConstantExprsToInstructions(
34 Instruction *I,
35 std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
36 SmallPtrSetImpl<Instruction *> *Insts) {
37 ValueMap<ConstantExpr *, Instruction *> Visited;
38
39 for (Use &U : I->operands()) {
40 // The operand U is either not a constant expression operand or the
41 // constant expression paths do not belong to U, ignore U.
42 if (!CEPaths.count(&U))
43 continue;
44
45 // If the instruction I is a PHI instruction, then fix the instruction
46 // insertion point to the entry of the incoming basic block for operand U.
47 auto *BI = I;
48 if (auto *Phi = dyn_cast<PHINode>(I)) {
49 BasicBlock *BB = Phi->getIncomingBlock(U);
50 BI = &(*(BB->getFirstInsertionPt()));
51 }
52
53 // Go through all the paths associated with operand U, and convert all the
54 // constant expressions along all the paths to corresponding instructions.
55 auto *II = I;
56 auto &Paths = CEPaths[&U];
57 for (auto &Path : Paths) {
58 for (auto *CE : Path) {
59 // Instruction which is equivalent to CE.
60 Instruction *NI = nullptr;
61
62 if (!Visited.count(CE)) {
63 // CE is encountered first time, convert it into a corresponding
64 // instruction NI, and appropriately insert NI before the parent
65 // instruction.
66 NI = CE->getAsInstruction(BI);
67
68 // Mark CE as visited by mapping CE to NI.
69 Visited[CE] = NI;
70
71 // If required collect NI.
72 if (Insts)
73 Insts->insert(NI);
74 } else {
75 // We had already encountered CE, the correponding instruction already
76 // exist, use it to replace CE.
77 NI = Visited[CE];
78 }
79
80 assert(NI && "Expected an instruction corresponding to constant "
81 "expression.");
82
83 // Replace all uses of constant expression CE by the corresponding
84 // instruction NI within the current parent instruction.
85 II->replaceUsesOfWith(CE, NI);
86 BI = II = NI;
87 }
88 }
89 }
90
91 // Remove all converted constant expressions which are dead by now.
92 for (auto Item : Visited)
93 Item.first->removeDeadConstantUsers();
94 }
95
collectConstantExprPaths(Instruction * I,ConstantExpr * CE,std::map<Use *,std::vector<std::vector<ConstantExpr * >>> & CEPaths)96 void collectConstantExprPaths(
97 Instruction *I, ConstantExpr *CE,
98 std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
99 for (Use &U : I->operands()) {
100 // If the operand U is not a constant expression operand, then ignore it.
101 auto *CE2 = dyn_cast<ConstantExpr>(U.get());
102 if (!CE2)
103 continue;
104
105 // Holds all reachable paths from CE2 to CE.
106 std::vector<std::vector<ConstantExpr *>> Paths;
107
108 // Collect all reachable paths from CE2 to CE.
109 std::vector<ConstantExpr *> Path{CE2};
110 std::vector<std::vector<ConstantExpr *>> Stack{Path};
111 while (!Stack.empty()) {
112 std::vector<ConstantExpr *> TPath = Stack.back();
113 Stack.pop_back();
114 auto *CE3 = TPath.back();
115
116 if (CE3 == CE) {
117 Paths.push_back(TPath);
118 continue;
119 }
120
121 for (auto &UU : CE3->operands()) {
122 if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
123 std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
124 NPath.push_back(CE4);
125 Stack.push_back(NPath);
126 }
127 }
128 }
129
130 // Associate all the collected paths with U, and save it.
131 if (!Paths.empty())
132 CEPaths[&U] = Paths;
133 }
134 }
135
136 } // namespace llvm
137