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.
22 Instruction *createReplacementInstr(ConstantExpr *CE, Instruction *Instr) {
23   IRBuilder<NoFolder> Builder(Instr);
24   unsigned OpCode = CE->getOpcode();
25   switch (OpCode) {
26   case Instruction::GetElementPtr: {
27     SmallVector<Value *, 4> CEOpVec(CE->operands());
28     ArrayRef<Value *> CEOps(CEOpVec);
29     return dyn_cast<Instruction>(
30         Builder.CreateInBoundsGEP(cast<GEPOperator>(CE)->getSourceElementType(),
31                                   CEOps[0], CEOps.slice(1)));
32   }
33   case Instruction::Add:
34   case Instruction::Sub:
35   case Instruction::Mul:
36   case Instruction::UDiv:
37   case Instruction::SDiv:
38   case Instruction::FDiv:
39   case Instruction::URem:
40   case Instruction::SRem:
41   case Instruction::FRem:
42   case Instruction::Shl:
43   case Instruction::LShr:
44   case Instruction::AShr:
45   case Instruction::And:
46   case Instruction::Or:
47   case Instruction::Xor:
48     return dyn_cast<Instruction>(
49         Builder.CreateBinOp((Instruction::BinaryOps)OpCode, CE->getOperand(0),
50                             CE->getOperand(1), CE->getName()));
51   case Instruction::Trunc:
52   case Instruction::ZExt:
53   case Instruction::SExt:
54   case Instruction::FPToUI:
55   case Instruction::FPToSI:
56   case Instruction::UIToFP:
57   case Instruction::SIToFP:
58   case Instruction::FPTrunc:
59   case Instruction::FPExt:
60   case Instruction::PtrToInt:
61   case Instruction::IntToPtr:
62   case Instruction::BitCast:
63   case Instruction::AddrSpaceCast:
64     return dyn_cast<Instruction>(
65         Builder.CreateCast((Instruction::CastOps)OpCode, CE->getOperand(0),
66                            CE->getType(), CE->getName()));
67   default:
68     llvm_unreachable("Unhandled constant expression!\n");
69   }
70 }
71 
72 void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE,
73                                         SmallPtrSetImpl<Instruction *> *Insts) {
74   // Collect all reachable paths to CE from constant exprssion operands of I.
75   std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
76   collectConstantExprPaths(I, CE, CEPaths);
77 
78   // Convert all constant expressions to instructions which are collected at
79   // CEPaths.
80   convertConstantExprsToInstructions(I, CEPaths, Insts);
81 }
82 
83 void convertConstantExprsToInstructions(
84     Instruction *I,
85     std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
86     SmallPtrSetImpl<Instruction *> *Insts) {
87   for (Use &U : I->operands()) {
88     // The operand U is either not a constant expression operand or the
89     // constant expression paths do not belong to U, ignore U.
90     if (!CEPaths.count(&U))
91       continue;
92 
93     // If the instruction I is a PHI instruction, then fix the instruction
94     // insertion point to the entry of the incoming basic block for operand U.
95     auto *BI = I;
96     if (auto *Phi = dyn_cast<PHINode>(I)) {
97       BasicBlock *BB = Phi->getIncomingBlock(U);
98       BI = &(*(BB->getFirstInsertionPt()));
99     }
100 
101     // Go through the paths associated with operand U, and convert all the
102     // constant expressions along all paths to corresponding instructions.
103     auto *II = I;
104     auto &Paths = CEPaths[&U];
105     SmallPtrSet<ConstantExpr *, 8> Visited;
106     for (auto &Path : Paths) {
107       for (auto *CE : Path) {
108         if (!Visited.insert(CE).second)
109           continue;
110         auto *NI = CE->getAsInstruction();
111         NI->insertBefore(BI);
112         II->replaceUsesOfWith(CE, NI);
113         CE->removeDeadConstantUsers();
114         BI = II = NI;
115         if (Insts)
116           Insts->insert(NI);
117       }
118     }
119   }
120 }
121 
122 void collectConstantExprPaths(
123     Instruction *I, ConstantExpr *CE,
124     std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
125   for (Use &U : I->operands()) {
126     // If the operand U is not a constant expression operand, then ignore it.
127     auto *CE2 = dyn_cast<ConstantExpr>(U.get());
128     if (!CE2)
129       continue;
130 
131     // Holds all reachable paths from CE2 to CE.
132     std::vector<std::vector<ConstantExpr *>> Paths;
133 
134     // Collect all reachable paths from CE2 to CE.
135     std::vector<ConstantExpr *> Path{CE2};
136     std::vector<std::vector<ConstantExpr *>> Stack{Path};
137     while (!Stack.empty()) {
138       std::vector<ConstantExpr *> TPath = Stack.back();
139       Stack.pop_back();
140       auto *CE3 = TPath.back();
141 
142       if (CE3 == CE) {
143         Paths.push_back(TPath);
144         continue;
145       }
146 
147       for (auto &UU : CE3->operands()) {
148         if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
149           std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
150           NPath.push_back(CE4);
151           Stack.push_back(NPath);
152         }
153       }
154     }
155 
156     // Associate all the collected paths with U, and save it.
157     if (!Paths.empty())
158       CEPaths[&U] = Paths;
159   }
160 }
161 
162 } // namespace llvm
163