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 
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 
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 
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