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/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.
createReplacementInstr(ConstantExpr * CE,Instruction * Instr)22 Instruction *createReplacementInstr(ConstantExpr *CE, Instruction *Instr) {
23 auto *CEInstr = CE->getAsInstruction();
24 CEInstr->insertBefore(Instr);
25 return CEInstr;
26 }
27
convertConstantExprsToInstructions(Instruction * I,ConstantExpr * CE,SmallPtrSetImpl<Instruction * > * Insts)28 void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE,
29 SmallPtrSetImpl<Instruction *> *Insts) {
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
convertConstantExprsToInstructions(Instruction * I,std::map<Use *,std::vector<std::vector<ConstantExpr * >>> & CEPaths,SmallPtrSetImpl<Instruction * > * Insts)39 void convertConstantExprsToInstructions(
40 Instruction *I,
41 std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
42 SmallPtrSetImpl<Instruction *> *Insts) {
43 SmallPtrSet<ConstantExpr *, 8> Visited;
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
collectConstantExprPaths(Instruction * I,ConstantExpr * CE,std::map<Use *,std::vector<std::vector<ConstantExpr * >>> & CEPaths)78 void collectConstantExprPaths(
79 Instruction *I, ConstantExpr *CE,
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
119