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