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