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 auto *CEInstr = CE->getAsInstruction(); 24 CEInstr->insertBefore(Instr); 25 return CEInstr; 26 } 27 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 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 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