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