llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

   1 //===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
   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 family of functions perform movements on basic blocks, and instructions
  10 // contained within a function.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
  15 #include "llvm/ADT/Statistic.h"
  16 #include "llvm/Analysis/DependenceAnalysis.h"
  17 #include "llvm/Analysis/PostDominators.h"
  18 #include "llvm/Analysis/ValueTracking.h"
  19 #include "llvm/IR/Dominators.h"
  20
  21 using namespace llvm;
  22
  23 #define DEBUG_TYPE "codemover-utils"
  24
  25 STATISTIC(HasDependences,
  26           "Cannot move across instructions that has memory dependences");
  27 STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
  28 STATISTIC(NotControlFlowEquivalent,
  29           "Instructions are not control flow equivalent");
  30 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
  31 STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
  32
  33 namespace {
  34 /// Represent a control condition. A control condition is a condition of a
  35 /// terminator to decide which successors to execute. The pointer field
  36 /// represents the address of the condition of the terminator. The integer field
  37 /// is a bool, it is true when the basic block is executed when V is true. For
  38 /// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
  39 /// integer field equals to true, while %cond is a control condition of bb1 with
  40 /// the integer field equals to false.
  41 using ControlCondition = PointerIntPair<Value *, 1, bool>;
  42 #ifndef NDEBUG
  43 raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
  44   OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
  45      << "]";
  46   return OS;
  47 }
  48 #endif
  49
  50 /// Represent a set of control conditions required to execute ToBB from FromBB.
  51 class ControlConditions {
  52   using ConditionVectorTy = SmallVector<ControlCondition, 6>;
  53
  54   /// A SmallVector of control conditions.
  55   ConditionVectorTy Conditions;
  56
  57 public:
  58   /// Return a ControlConditions which stores all conditions required to execute
  59   /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the
  60   /// number of conditions to collect. Return std::nullopt if not all conditions
  61   /// are collected successfully, or we hit the limit.
  62   static const std::optional<ControlConditions>
  63   collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
  64                            const DominatorTree &DT,
  65                            const PostDominatorTree &PDT,
  66                            unsigned MaxLookup = 6);
  67
  68   /// Return true if there exists no control conditions required to execute ToBB
  69   /// from FromBB.
  70   bool isUnconditional() const { return Conditions.empty(); }
  71
  72   /// Return a constant reference of Conditions.
  73   const ConditionVectorTy &getControlConditions() const { return Conditions; }
  74
  75   /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition
  76   /// equals to \p True. Return true if inserted successfully.
  77   bool addControlCondition(ControlCondition C);
  78
  79   /// Return true if for all control conditions in Conditions, there exists an
  80   /// equivalent control condition in \p Other.Conditions.
  81   bool isEquivalent(const ControlConditions &Other) const;
  82
  83   /// Return true if \p C1 and \p C2 are equivalent.
  84   static bool isEquivalent(const ControlCondition &C1,
  85                            const ControlCondition &C2);
  86
  87 private:
  88   ControlConditions() = default;
  89
  90   static bool isEquivalent(const Value &V1, const Value &V2);
  91   static bool isInverse(const Value &V1, const Value &V2);
  92 };
  93 } // namespace
  94
  95 static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,
  96                                const Instruction *InstB) {
  97   // Use ordered basic block in case the 2 instructions are in the same
  98   // block.
  99   if (InstA->getParent() == InstB->getParent())
 100     return InstA->comesBefore(InstB);
 101
 102   DomTreeNode *DA = DT->getNode(InstA->getParent());
 103   DomTreeNode *DB = DT->getNode(InstB->getParent());
 104   return DA->getLevel() < DB->getLevel();
 105 }
 106
 107 const std::optional<ControlConditions>
 108 ControlConditions::collectControlConditions(const BasicBlock &BB,
 109                                             const BasicBlock &Dominator,
 110                                             const DominatorTree &DT,
 111                                             const PostDominatorTree &PDT,
 112                                             unsigned MaxLookup) {
 113   assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
 114
 115   ControlConditions Conditions;
 116   unsigned NumConditions = 0;
 117
 118   // BB is executed unconditional from itself.
 119   if (&Dominator == &BB)
 120     return Conditions;
 121
 122   const BasicBlock *CurBlock = &BB;
 123   // Walk up the dominator tree from the associated DT node for BB to the
 124   // associated DT node for Dominator.
 125   do {
 126     assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
 127     BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
 128     assert(DT.dominates(&Dominator, IDom) &&
 129            "Expecting Dominator to dominate IDom");
 130
 131     // Limitation: can only handle branch instruction currently.
 132     const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
 133     if (!BI)
 134       return std::nullopt;
 135
 136     bool Inserted = false;
 137     if (PDT.dominates(CurBlock, IDom)) {
 138       LLVM_DEBUG(dbgs() << CurBlock->getName()
 139                         << " is executed unconditionally from "
 140                         << IDom->getName() << "\n");
 141     } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
 142       LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
 143                         << *BI->getCondition() << "\" is true from "
 144                         << IDom->getName() << "\n");
 145       Inserted = Conditions.addControlCondition(
 146           ControlCondition(BI->getCondition(), true));
 147     } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
 148       LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
 149                         << *BI->getCondition() << "\" is false from "
 150                         << IDom->getName() << "\n");
 151       Inserted = Conditions.addControlCondition(
 152           ControlCondition(BI->getCondition(), false));
 153     } else
 154       return std::nullopt;
 155
 156     if (Inserted)
 157       ++NumConditions;
 158
 159     if (MaxLookup != 0 && NumConditions > MaxLookup)
 160       return std::nullopt;
 161
 162     CurBlock = IDom;
 163   } while (CurBlock != &Dominator);
 164
 165   return Conditions;
 166 }
 167
 168 bool ControlConditions::addControlCondition(ControlCondition C) {
 169   bool Inserted = false;
 170   if (none_of(Conditions, [&](ControlCondition &Exists) {
 171         return ControlConditions::isEquivalent(C, Exists);
 172       })) {
 173     Conditions.push_back(C);
 174     Inserted = true;
 175   }
 176
 177   LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
 178   return Inserted;
 179 }
 180
 181 bool ControlConditions::isEquivalent(const ControlConditions &Other) const {
 182   if (Conditions.empty() && Other.Conditions.empty())
 183     return true;
 184
 185   if (Conditions.size() != Other.Conditions.size())
 186     return false;
 187
 188   return all_of(Conditions, [&](const ControlCondition &C) {
 189     return any_of(Other.Conditions, [&](const ControlCondition &OtherC) {
 190       return ControlConditions::isEquivalent(C, OtherC);
 191     });
 192   });
 193 }
 194
 195 bool ControlConditions::isEquivalent(const ControlCondition &C1,
 196                                      const ControlCondition &C2) {
 197   if (C1.getInt() == C2.getInt()) {
 198     if (isEquivalent(*C1.getPointer(), *C2.getPointer()))
 199       return true;
 200   } else if (isInverse(*C1.getPointer(), *C2.getPointer()))
 201     return true;
 202
 203   return false;
 204 }
 205
 206 // FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
 207 // Values.
 208 // Currently, isEquivalent rely on other passes to ensure equivalent conditions
 209 // have the same value, e.g. GVN.
 210 bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {
 211   return &V1 == &V2;
 212 }
 213
 214 bool ControlConditions::isInverse(const Value &V1, const Value &V2) {
 215   if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))
 216     if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
 217       if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&
 218           Cmp1->getOperand(0) == Cmp2->getOperand(0) &&
 219           Cmp1->getOperand(1) == Cmp2->getOperand(1))
 220         return true;
 221
 222       if (Cmp1->getPredicate() ==
 223               CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
 224           Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
 225           Cmp1->getOperand(1) == Cmp2->getOperand(0))
 226         return true;
 227     }
 228   return false;
 229 }
 230
 231 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
 232                                    const DominatorTree &DT,
 233                                    const PostDominatorTree &PDT) {
 234   return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
 235 }
 236
 237 bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
 238                                    const DominatorTree &DT,
 239                                    const PostDominatorTree &PDT) {
 240   if (&BB0 == &BB1)
 241     return true;
 242
 243   if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
 244       (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
 245     return true;
 246
 247   // If the set of conditions required to execute BB0 and BB1 from their common
 248   // dominator are the same, then BB0 and BB1 are control flow equivalent.
 249   const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
 250   LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
 251                     << " and " << BB1.getName() << " is "
 252                     << CommonDominator->getName() << "\n");
 253
 254   const std::optional<ControlConditions> BB0Conditions =
 255       ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
 256                                                   PDT);
 257   if (BB0Conditions == std::nullopt)
 258     return false;
 259
 260   const std::optional<ControlConditions> BB1Conditions =
 261       ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
 262                                                   PDT);
 263   if (BB1Conditions == std::nullopt)
 264     return false;
 265
 266   return BB0Conditions->isEquivalent(*BB1Conditions);
 267 }
 268
 269 static bool reportInvalidCandidate(const Instruction &I,
 270                                    llvm::Statistic &Stat) {
 271   ++Stat;
 272   LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
 273                     << Stat.getDesc());
 274   return false;
 275 }
 276
 277 /// Collect all instructions in between \p StartInst and \p EndInst, and store
 278 /// them in \p InBetweenInsts.
 279 static void
 280 collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
 281                              SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
 282   assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
 283
 284   /// Get the next instructions of \p I, and push them to \p WorkList.
 285   auto getNextInsts = [](Instruction &I,
 286                          SmallPtrSetImpl<Instruction *> &WorkList) {
 287     if (Instruction *NextInst = I.getNextNode())
 288       WorkList.insert(NextInst);
 289     else {
 290       assert(I.isTerminator() && "Expecting a terminator instruction");
 291       for (BasicBlock *Succ : successors(&I))
 292         WorkList.insert(&Succ->front());
 293     }
 294   };
 295
 296   SmallPtrSet<Instruction *, 10> WorkList;
 297   getNextInsts(StartInst, WorkList);
 298   while (!WorkList.empty()) {
 299     Instruction *CurInst = *WorkList.begin();
 300     WorkList.erase(CurInst);
 301
 302     if (CurInst == &EndInst)
 303       continue;
 304
 305     if (!InBetweenInsts.insert(CurInst).second)
 306       continue;
 307
 308     getNextInsts(*CurInst, WorkList);
 309   }
 310 }
 311
 312 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
 313                               DominatorTree &DT, const PostDominatorTree *PDT,
 314                               DependenceInfo *DI, bool CheckForEntireBlock) {
 315   // Skip tests when we don't have PDT or DI
 316   if (!PDT || !DI)
 317     return false;
 318
 319   // Cannot move itself before itself.
 320   if (&I == &InsertPoint)
 321     return false;
 322
 323   // Not moved.
 324   if (I.getNextNode() == &InsertPoint)
 325     return true;
 326
 327   if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
 328     return reportInvalidCandidate(I, NotMovedPHINode);
 329
 330   if (I.isTerminator())
 331     return reportInvalidCandidate(I, NotMovedTerminator);
 332
 333   // TODO remove this limitation.
 334   if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT))
 335     return reportInvalidCandidate(I, NotControlFlowEquivalent);
 336
 337   if (isReachedBefore(&I, &InsertPoint, &DT, PDT))
 338     for (const Use &U : I.uses())
 339       if (auto *UserInst = dyn_cast<Instruction>(U.getUser())) {
 340         // If InsertPoint is in a BB that comes after I, then we cannot move if
 341         // I is used in the terminator of the current BB.
 342         if (I.getParent() == InsertPoint.getParent() &&
 343             UserInst == I.getParent()->getTerminator())
 344           return false;
 345         if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U)) {
 346           // If UserInst is an instruction that appears later in the same BB as
 347           // I, then it is okay to move since I will still be available when
 348           // UserInst is executed.
 349           if (CheckForEntireBlock && I.getParent() == UserInst->getParent() &&
 350               DT.dominates(&I, UserInst))
 351             continue;
 352           return false;
 353         }
 354       }
 355   if (isReachedBefore(&InsertPoint, &I, &DT, PDT))
 356     for (const Value *Op : I.operands())
 357       if (auto *OpInst = dyn_cast<Instruction>(Op)) {
 358         if (&InsertPoint == OpInst)
 359           return false;
 360         // If OpInst is an instruction that appears earlier in the same BB as
 361         // I, then it is okay to move since OpInst will still be available.
 362         if (CheckForEntireBlock && I.getParent() == OpInst->getParent() &&
 363             DT.dominates(OpInst, &I))
 364           continue;
 365         if (!DT.dominates(OpInst, &InsertPoint))
 366           return false;
 367       }
 368
 369   DT.updateDFSNumbers();
 370   const bool MoveForward = domTreeLevelBefore(&DT, &I, &InsertPoint);
 371   Instruction &StartInst = (MoveForward ? I : InsertPoint);
 372   Instruction &EndInst = (MoveForward ? InsertPoint : I);
 373   SmallPtrSet<Instruction *, 10> InstsToCheck;
 374   collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
 375   if (!MoveForward)
 376     InstsToCheck.insert(&InsertPoint);
 377
 378   // Check if there exists instructions which may throw, may synchonize, or may
 379   // never return, from I to InsertPoint.
 380   if (!isSafeToSpeculativelyExecute(&I))
 381     if (llvm::any_of(InstsToCheck, [](Instruction *I) {
 382           if (I->mayThrow())
 383             return true;
 384
 385           const CallBase *CB = dyn_cast<CallBase>(I);
 386           if (!CB)
 387             return false;
 388           if (!CB->hasFnAttr(Attribute::WillReturn))
 389             return true;
 390           if (!CB->hasFnAttr(Attribute::NoSync))
 391             return true;
 392
 393           return false;
 394         })) {
 395       return reportInvalidCandidate(I, MayThrowException);
 396     }
 397
 398   // Check if I has any output/flow/anti dependences with instructions from \p
 399   // StartInst to \p EndInst.
 400   if (llvm::any_of(InstsToCheck, [&DI, &I](Instruction *CurInst) {
 401         auto DepResult = DI->depends(&I, CurInst, true);
 402         if (DepResult && (DepResult->isOutput() || DepResult->isFlow() ||
 403                           DepResult->isAnti()))
 404           return true;
 405         return false;
 406       }))
 407     return reportInvalidCandidate(I, HasDependences);
 408
 409   return true;
 410 }
 411
 412 bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
 413                               DominatorTree &DT, const PostDominatorTree *PDT,
 414                               DependenceInfo *DI) {
 415   return llvm::all_of(BB, [&](Instruction &I) {
 416     if (BB.getTerminator() == &I)
 417       return true;
 418
 419     return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
 420                               /*CheckForEntireBlock=*/true);
 421   });
 422 }
 423
 424 void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
 425                                           DominatorTree &DT,
 426                                           const PostDominatorTree &PDT,
 427                                           DependenceInfo &DI) {
 428   for (Instruction &I :
 429        llvm::make_early_inc_range(llvm::drop_begin(llvm::reverse(FromBB)))) {
 430     Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
 431
 432     if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
 433       I.moveBeforePreserving(MovePos);
 434   }
 435 }
 436
 437 void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
 438                                     DominatorTree &DT,
 439                                     const PostDominatorTree &PDT,
 440                                     DependenceInfo &DI) {
 441   Instruction *MovePos = ToBB.getTerminator();
 442   while (FromBB.size() > 1) {
 443     Instruction &I = FromBB.front();
 444     if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
 445       I.moveBeforePreserving(MovePos);
 446   }
 447 }
 448
 449 bool llvm::nonStrictlyPostDominate(const BasicBlock *ThisBlock,
 450                                    const BasicBlock *OtherBlock,
 451                                    const DominatorTree *DT,
 452                                    const PostDominatorTree *PDT) {
 453   assert(isControlFlowEquivalent(*ThisBlock, *OtherBlock, *DT, *PDT) &&
 454          "ThisBlock and OtherBlock must be CFG equivalent!");
 455   const BasicBlock *CommonDominator =
 456       DT->findNearestCommonDominator(ThisBlock, OtherBlock);
 457   if (CommonDominator == nullptr)
 458     return false;
 459
 460   /// Recursively check the predecessors of \p ThisBlock up to
 461   /// their common dominator, and see if any of them post-dominates
 462   /// \p OtherBlock.
 463   SmallVector<const BasicBlock *, 8> WorkList;
 464   SmallPtrSet<const BasicBlock *, 8> Visited;
 465   WorkList.push_back(ThisBlock);
 466   while (!WorkList.empty()) {
 467     const BasicBlock *CurBlock = WorkList.back();
 468     WorkList.pop_back();
 469     Visited.insert(CurBlock);
 470     if (PDT->dominates(CurBlock, OtherBlock))
 471       return true;
 472
 473     for (const auto *Pred : predecessors(CurBlock)) {
 474       if (Pred == CommonDominator || Visited.count(Pred))
 475         continue;
 476       WorkList.push_back(Pred);
 477     }
 478   }
 479   return false;
 480 }
 481
 482 bool llvm::isReachedBefore(const Instruction *I0, const Instruction *I1,
 483                            const DominatorTree *DT,
 484                            const PostDominatorTree *PDT) {
 485   const BasicBlock *BB0 = I0->getParent();
 486   const BasicBlock *BB1 = I1->getParent();
 487   if (BB0 == BB1)
 488     return DT->dominates(I0, I1);
 489
 490   return nonStrictlyPostDominate(BB1, BB0, DT, PDT);
 491 }