llvm/lib/Transforms/Utils/MoveAutoInit.cpp

   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 }