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