1 //===-- MoveAutoInit.cpp - move auto-init inst closer to their use site----===// 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 pass moves instruction maked as auto-init closer to the basic block that 10 // use it, eventually removing it from some control path of the function. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Utils/MoveAutoInit.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/Analysis/MemorySSA.h" 18 #include "llvm/Analysis/MemorySSAUpdater.h" 19 #include "llvm/Analysis/ValueTracking.h" 20 #include "llvm/IR/DebugInfo.h" 21 #include "llvm/IR/Dominators.h" 22 #include "llvm/IR/IRBuilder.h" 23 #include "llvm/IR/Instructions.h" 24 #include "llvm/IR/IntrinsicInst.h" 25 #include "llvm/Support/CommandLine.h" 26 #include "llvm/Transforms/Utils.h" 27 #include "llvm/Transforms/Utils/LoopUtils.h" 28 29 using namespace llvm; 30 31 #define DEBUG_TYPE "move-auto-init" 32 33 STATISTIC(NumMoved, "Number of instructions moved"); 34 35 static cl::opt<unsigned> MoveAutoInitThreshold( 36 "move-auto-init-threshold", cl::Hidden, cl::init(128), 37 cl::desc("Maximum instructions to analyze per moved initialization")); 38 39 static bool hasAutoInitMetadata(const Instruction &I) { 40 return I.hasMetadata(LLVMContext::MD_annotation) && 41 any_of(I.getMetadata(LLVMContext::MD_annotation)->operands(), 42 [](const MDOperand &Op) { return Op.equalsStr("auto-init"); }); 43 } 44 45 static std::optional<MemoryLocation> writeToAlloca(const Instruction &I) { 46 MemoryLocation ML; 47 if (auto *MI = dyn_cast<MemIntrinsic>(&I)) 48 ML = MemoryLocation::getForDest(MI); 49 else if (auto *SI = dyn_cast<StoreInst>(&I)) 50 ML = MemoryLocation::get(SI); 51 else 52 return std::nullopt; 53 54 if (isa<AllocaInst>(getUnderlyingObject(ML.Ptr))) 55 return ML; 56 else 57 return {}; 58 } 59 60 /// Finds a BasicBlock in the CFG where instruction `I` can be moved to while 61 /// not changing the Memory SSA ordering and being guarded by at least one 62 /// condition. 63 static BasicBlock *usersDominator(const MemoryLocation &ML, Instruction *I, 64 DominatorTree &DT, MemorySSA &MSSA) { 65 BasicBlock *CurrentDominator = nullptr; 66 MemoryUseOrDef &IMA = *MSSA.getMemoryAccess(I); 67 BatchAAResults AA(MSSA.getAA()); 68 69 SmallPtrSet<MemoryAccess *, 8> Visited; 70 71 auto AsMemoryAccess = [](User *U) { return cast<MemoryAccess>(U); }; 72 SmallVector<MemoryAccess *> WorkList(map_range(IMA.users(), AsMemoryAccess)); 73 74 while (!WorkList.empty()) { 75 MemoryAccess *MA = WorkList.pop_back_val(); 76 if (!Visited.insert(MA).second) 77 continue; 78 79 if (Visited.size() > MoveAutoInitThreshold) 80 return nullptr; 81 82 bool FoundClobberingUser = false; 83 if (auto *M = dyn_cast<MemoryUseOrDef>(MA)) { 84 Instruction *MI = M->getMemoryInst(); 85 86 // If this memory instruction may not clobber `I`, we can skip it. 87 // LifetimeEnd is a valid user, but we do not want it in the user 88 // dominator. 89 if (AA.getModRefInfo(MI, ML) != ModRefInfo::NoModRef && 90 !MI->isLifetimeStartOrEnd() && MI != I) { 91 FoundClobberingUser = true; 92 CurrentDominator = CurrentDominator 93 ? DT.findNearestCommonDominator(CurrentDominator, 94 MI->getParent()) 95 : MI->getParent(); 96 } 97 } 98 if (!FoundClobberingUser) { 99 auto UsersAsMemoryAccesses = map_range(MA->users(), AsMemoryAccess); 100 append_range(WorkList, UsersAsMemoryAccesses); 101 } 102 } 103 return CurrentDominator; 104 } 105 106 static bool runMoveAutoInit(Function &F, DominatorTree &DT, MemorySSA &MSSA) { 107 BasicBlock &EntryBB = F.getEntryBlock(); 108 SmallVector<std::pair<Instruction *, BasicBlock *>> JobList; 109 110 // 111 // Compute movable instructions. 112 // 113 for (Instruction &I : EntryBB) { 114 if (!hasAutoInitMetadata(I)) 115 continue; 116 117 std::optional<MemoryLocation> ML = writeToAlloca(I); 118 if (!ML) 119 continue; 120 121 if (I.isVolatile()) 122 continue; 123 124 BasicBlock *UsersDominator = usersDominator(ML.value(), &I, DT, MSSA); 125 if (!UsersDominator) 126 continue; 127 128 if (UsersDominator == &EntryBB) 129 continue; 130 131 // Traverse the CFG to detect cycles `UsersDominator` would be part of. 132 SmallPtrSet<BasicBlock *, 8> TransitiveSuccessors; 133 SmallVector<BasicBlock *> WorkList(successors(UsersDominator)); 134 bool HasCycle = false; 135 while (!WorkList.empty()) { 136 BasicBlock *CurrBB = WorkList.pop_back_val(); 137 if (CurrBB == UsersDominator) 138 // No early exit because we want to compute the full set of transitive 139 // successors. 140 HasCycle = true; 141 for (BasicBlock *Successor : successors(CurrBB)) { 142 if (!TransitiveSuccessors.insert(Successor).second) 143 continue; 144 WorkList.push_back(Successor); 145 } 146 } 147 148 // Don't insert if that could create multiple execution of I, 149 // but we can insert it in the non back-edge predecessors, if it exists. 150 if (HasCycle) { 151 BasicBlock *UsersDominatorHead = UsersDominator; 152 while (BasicBlock *UniquePredecessor = 153 UsersDominatorHead->getUniquePredecessor()) 154 UsersDominatorHead = UniquePredecessor; 155 156 if (UsersDominatorHead == &EntryBB) 157 continue; 158 159 BasicBlock *DominatingPredecessor = nullptr; 160 for (BasicBlock *Pred : predecessors(UsersDominatorHead)) { 161 // If one of the predecessor of the dominator also transitively is a 162 // successor, moving to the dominator would do the inverse of loop 163 // hoisting, and we don't want that. 164 if (TransitiveSuccessors.count(Pred)) 165 continue; 166 167 if (!DT.isReachableFromEntry(Pred)) 168 continue; 169 170 DominatingPredecessor = 171 DominatingPredecessor 172 ? DT.findNearestCommonDominator(DominatingPredecessor, Pred) 173 : Pred; 174 } 175 176 if (!DominatingPredecessor || DominatingPredecessor == &EntryBB) 177 continue; 178 179 UsersDominator = DominatingPredecessor; 180 } 181 182 // CatchSwitchInst blocks can only have one instruction, so they are not 183 // good candidates for insertion. 184 while (isa<CatchSwitchInst>(UsersDominator->getFirstNonPHI())) { 185 for (BasicBlock *Pred : predecessors(UsersDominator)) 186 if (DT.isReachableFromEntry(Pred)) 187 UsersDominator = DT.findNearestCommonDominator(UsersDominator, Pred); 188 } 189 190 // We finally found a place where I can be moved while not introducing extra 191 // execution, and guarded by at least one condition. 192 if (UsersDominator != &EntryBB) 193 JobList.emplace_back(&I, UsersDominator); 194 } 195 196 // 197 // Perform the actual substitution. 198 // 199 if (JobList.empty()) 200 return false; 201 202 MemorySSAUpdater MSSAU(&MSSA); 203 204 // Reverse insertion to respect relative order between instructions: 205 // if two instructions are moved from the same BB to the same BB, we insert 206 // the second one in the front, then the first on top of it. 207 for (auto &Job : reverse(JobList)) { 208 Job.first->moveBefore(*Job.second, Job.second->getFirstInsertionPt()); 209 MSSAU.moveToPlace(MSSA.getMemoryAccess(Job.first), Job.first->getParent(), 210 MemorySSA::InsertionPlace::Beginning); 211 } 212 213 if (VerifyMemorySSA) 214 MSSA.verifyMemorySSA(); 215 216 NumMoved += JobList.size(); 217 218 return true; 219 } 220 221 PreservedAnalyses MoveAutoInitPass::run(Function &F, 222 FunctionAnalysisManager &AM) { 223 224 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 225 auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA(); 226 if (!runMoveAutoInit(F, DT, MSSA)) 227 return PreservedAnalyses::all(); 228 229 PreservedAnalyses PA; 230 PA.preserve<DominatorTreeAnalysis>(); 231 PA.preserve<MemorySSAAnalysis>(); 232 PA.preserveSet<CFGAnalyses>(); 233 return PA; 234 } 235