contrib/llvm-project/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

   1 //===----------------- LoopRotationUtils.cpp -----------------------------===//
   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 provides utilities to convert a loop into a loop with bottom test.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Transforms/Utils/LoopRotationUtils.h"
  14 #include "llvm/ADT/Statistic.h"
  15 #include "llvm/Analysis/AliasAnalysis.h"
  16 #include "llvm/Analysis/AssumptionCache.h"
  17 #include "llvm/Analysis/BasicAliasAnalysis.h"
  18 #include "llvm/Analysis/CodeMetrics.h"
  19 #include "llvm/Analysis/DomTreeUpdater.h"
  20 #include "llvm/Analysis/GlobalsModRef.h"
  21 #include "llvm/Analysis/InstructionSimplify.h"
  22 #include "llvm/Analysis/LoopPass.h"
  23 #include "llvm/Analysis/MemorySSA.h"
  24 #include "llvm/Analysis/MemorySSAUpdater.h"
  25 #include "llvm/Analysis/ScalarEvolution.h"
  26 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  27 #include "llvm/Analysis/TargetTransformInfo.h"
  28 #include "llvm/Analysis/ValueTracking.h"
  29 #include "llvm/IR/CFG.h"
  30 #include "llvm/IR/DebugInfoMetadata.h"
  31 #include "llvm/IR/Dominators.h"
  32 #include "llvm/IR/Function.h"
  33 #include "llvm/IR/IntrinsicInst.h"
  34 #include "llvm/IR/Module.h"
  35 #include "llvm/Support/CommandLine.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  39 #include "llvm/Transforms/Utils/Local.h"
  40 #include "llvm/Transforms/Utils/LoopUtils.h"
  41 #include "llvm/Transforms/Utils/SSAUpdater.h"
  42 #include "llvm/Transforms/Utils/ValueMapper.h"
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "loop-rotate"
  46
  47 STATISTIC(NumRotated, "Number of loops rotated");
  48
  49 static cl::opt<bool>
  50     MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden,
  51                 cl::desc("Allow loop rotation multiple times in order to reach "
  52                          "a better latch exit"));
  53
  54 namespace {
  55 /// A simple loop rotation transformation.
  56 class LoopRotate {
  57   const unsigned MaxHeaderSize;
  58   LoopInfo *LI;
  59   const TargetTransformInfo *TTI;
  60   AssumptionCache *AC;
  61   DominatorTree *DT;
  62   ScalarEvolution *SE;
  63   MemorySSAUpdater *MSSAU;
  64   const SimplifyQuery &SQ;
  65   bool RotationOnly;
  66   bool IsUtilMode;
  67
  68 public:
  69   LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
  70              const TargetTransformInfo *TTI, AssumptionCache *AC,
  71              DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
  72              const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode)
  73       : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
  74         MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
  75         IsUtilMode(IsUtilMode) {}
  76   bool processLoop(Loop *L);
  77
  78 private:
  79   bool rotateLoop(Loop *L, bool SimplifiedLatch);
  80   bool simplifyLoopLatch(Loop *L);
  81 };
  82 } // end anonymous namespace
  83
  84 /// Insert (K, V) pair into the ValueToValueMap, and verify the key did not
  85 /// previously exist in the map, and the value was inserted.
  86 static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V) {
  87   bool Inserted = VM.insert({K, V}).second;
  88   assert(Inserted);
  89   (void)Inserted;
  90 }
  91 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
  92 /// old header into the preheader.  If there were uses of the values produced by
  93 /// these instruction that were outside of the loop, we have to insert PHI nodes
  94 /// to merge the two values.  Do this now.
  95 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
  96                                             BasicBlock *OrigPreheader,
  97                                             ValueToValueMapTy &ValueMap,
  98                                 SmallVectorImpl<PHINode*> *InsertedPHIs) {
  99   // Remove PHI node entries that are no longer live.
 100   BasicBlock::iterator I, E = OrigHeader->end();
 101   for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
 102     PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
 103
 104   // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
 105   // as necessary.
 106   SSAUpdater SSA(InsertedPHIs);
 107   for (I = OrigHeader->begin(); I != E; ++I) {
 108     Value *OrigHeaderVal = &*I;
 109
 110     // If there are no uses of the value (e.g. because it returns void), there
 111     // is nothing to rewrite.
 112     if (OrigHeaderVal->use_empty())
 113       continue;
 114
 115     Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);
 116
 117     // The value now exits in two versions: the initial value in the preheader
 118     // and the loop "next" value in the original header.
 119     SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
 120     SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
 121     SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
 122
 123     // Visit each use of the OrigHeader instruction.
 124     for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
 125                              UE = OrigHeaderVal->use_end();
 126          UI != UE;) {
 127       // Grab the use before incrementing the iterator.
 128       Use &U = *UI;
 129
 130       // Increment the iterator before removing the use from the list.
 131       ++UI;
 132
 133       // SSAUpdater can't handle a non-PHI use in the same block as an
 134       // earlier def. We can easily handle those cases manually.
 135       Instruction *UserInst = cast<Instruction>(U.getUser());
 136       if (!isa<PHINode>(UserInst)) {
 137         BasicBlock *UserBB = UserInst->getParent();
 138
 139         // The original users in the OrigHeader are already using the
 140         // original definitions.
 141         if (UserBB == OrigHeader)
 142           continue;
 143
 144         // Users in the OrigPreHeader need to use the value to which the
 145         // original definitions are mapped.
 146         if (UserBB == OrigPreheader) {
 147           U = OrigPreHeaderVal;
 148           continue;
 149         }
 150       }
 151
 152       // Anything else can be handled by SSAUpdater.
 153       SSA.RewriteUse(U);
 154     }
 155
 156     // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
 157     // intrinsics.
 158     SmallVector<DbgValueInst *, 1> DbgValues;
 159     llvm::findDbgValues(DbgValues, OrigHeaderVal);
 160     for (auto &DbgValue : DbgValues) {
 161       // The original users in the OrigHeader are already using the original
 162       // definitions.
 163       BasicBlock *UserBB = DbgValue->getParent();
 164       if (UserBB == OrigHeader)
 165         continue;
 166
 167       // Users in the OrigPreHeader need to use the value to which the
 168       // original definitions are mapped and anything else can be handled by
 169       // the SSAUpdater. To avoid adding PHINodes, check if the value is
 170       // available in UserBB, if not substitute undef.
 171       Value *NewVal;
 172       if (UserBB == OrigPreheader)
 173         NewVal = OrigPreHeaderVal;
 174       else if (SSA.HasValueForBlock(UserBB))
 175         NewVal = SSA.GetValueInMiddleOfBlock(UserBB);
 176       else
 177         NewVal = UndefValue::get(OrigHeaderVal->getType());
 178       DbgValue->setOperand(0,
 179                            MetadataAsValue::get(OrigHeaderVal->getContext(),
 180                                                 ValueAsMetadata::get(NewVal)));
 181     }
 182   }
 183 }
 184
 185 // Assuming both header and latch are exiting, look for a phi which is only
 186 // used outside the loop (via a LCSSA phi) in the exit from the header.
 187 // This means that rotating the loop can remove the phi.
 188 static bool profitableToRotateLoopExitingLatch(Loop *L) {
 189   BasicBlock *Header = L->getHeader();
 190   BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator());
 191   assert(BI && BI->isConditional() && "need header with conditional exit");
 192   BasicBlock *HeaderExit = BI->getSuccessor(0);
 193   if (L->contains(HeaderExit))
 194     HeaderExit = BI->getSuccessor(1);
 195
 196   for (auto &Phi : Header->phis()) {
 197     // Look for uses of this phi in the loop/via exits other than the header.
 198     if (llvm::any_of(Phi.users(), [HeaderExit](const User *U) {
 199           return cast<Instruction>(U)->getParent() != HeaderExit;
 200         }))
 201       continue;
 202     return true;
 203   }
 204   return false;
 205 }
 206
 207 // Check that latch exit is deoptimizing (which means - very unlikely to happen)
 208 // and there is another exit from the loop which is non-deoptimizing.
 209 // If we rotate latch to that exit our loop has a better chance of being fully
 210 // canonical.
 211 //
 212 // It can give false positives in some rare cases.
 213 static bool canRotateDeoptimizingLatchExit(Loop *L) {
 214   BasicBlock *Latch = L->getLoopLatch();
 215   assert(Latch && "need latch");
 216   BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
 217   // Need normal exiting latch.
 218   if (!BI || !BI->isConditional())
 219     return false;
 220
 221   BasicBlock *Exit = BI->getSuccessor(1);
 222   if (L->contains(Exit))
 223     Exit = BI->getSuccessor(0);
 224
 225   // Latch exit is non-deoptimizing, no need to rotate.
 226   if (!Exit->getPostdominatingDeoptimizeCall())
 227     return false;
 228
 229   SmallVector<BasicBlock *, 4> Exits;
 230   L->getUniqueExitBlocks(Exits);
 231   if (!Exits.empty()) {
 232     // There is at least one non-deoptimizing exit.
 233     //
 234     // Note, that BasicBlock::getPostdominatingDeoptimizeCall is not exact,
 235     // as it can conservatively return false for deoptimizing exits with
 236     // complex enough control flow down to deoptimize call.
 237     //
 238     // That means here we can report success for a case where
 239     // all exits are deoptimizing but one of them has complex enough
 240     // control flow (e.g. with loops).
 241     //
 242     // That should be a very rare case and false positives for this function
 243     // have compile-time effect only.
 244     return any_of(Exits, [](const BasicBlock *BB) {
 245       return !BB->getPostdominatingDeoptimizeCall();
 246     });
 247   }
 248   return false;
 249 }
 250
 251 /// Rotate loop LP. Return true if the loop is rotated.
 252 ///
 253 /// \param SimplifiedLatch is true if the latch was just folded into the final
 254 /// loop exit. In this case we may want to rotate even though the new latch is
 255 /// now an exiting branch. This rotation would have happened had the latch not
 256 /// been simplified. However, if SimplifiedLatch is false, then we avoid
 257 /// rotating loops in which the latch exits to avoid excessive or endless
 258 /// rotation. LoopRotate should be repeatable and converge to a canonical
 259 /// form. This property is satisfied because simplifying the loop latch can only
 260 /// happen once across multiple invocations of the LoopRotate pass.
 261 ///
 262 /// If -loop-rotate-multi is enabled we can do multiple rotations in one go
 263 /// so to reach a suitable (non-deoptimizing) exit.
 264 bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
 265   // If the loop has only one block then there is not much to rotate.
 266   if (L->getBlocks().size() == 1)
 267     return false;
 268
 269   bool Rotated = false;
 270   do {
 271     BasicBlock *OrigHeader = L->getHeader();
 272     BasicBlock *OrigLatch = L->getLoopLatch();
 273
 274     BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
 275     if (!BI || BI->isUnconditional())
 276       return Rotated;
 277
 278     // If the loop header is not one of the loop exiting blocks then
 279     // either this loop is already rotated or it is not
 280     // suitable for loop rotation transformations.
 281     if (!L->isLoopExiting(OrigHeader))
 282       return Rotated;
 283
 284     // If the loop latch already contains a branch that leaves the loop then the
 285     // loop is already rotated.
 286     if (!OrigLatch)
 287       return Rotated;
 288
 289     // Rotate if either the loop latch does *not* exit the loop, or if the loop
 290     // latch was just simplified. Or if we think it will be profitable.
 291     if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&
 292         !profitableToRotateLoopExitingLatch(L) &&
 293         !canRotateDeoptimizingLatchExit(L))
 294       return Rotated;
 295
 296     // Check size of original header and reject loop if it is very big or we can't
 297     // duplicate blocks inside it.
 298     {
 299       SmallPtrSet<const Value *, 32> EphValues;
 300       CodeMetrics::collectEphemeralValues(L, AC, EphValues);
 301
 302       CodeMetrics Metrics;
 303       Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues);
 304       if (Metrics.notDuplicatable) {
 305         LLVM_DEBUG(
 306                    dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"
 307                    << " instructions: ";
 308                    L->dump());
 309         return Rotated;
 310       }
 311       if (Metrics.convergent) {
 312         LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
 313                    "instructions: ";
 314                    L->dump());
 315         return Rotated;
 316       }
 317       if (Metrics.NumInsts > MaxHeaderSize) {
 318         LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "
 319                           << Metrics.NumInsts
 320                           << " instructions, which is more than the threshold ("
 321                           << MaxHeaderSize << " instructions): ";
 322                    L->dump());
 323         return Rotated;
 324       }
 325     }
 326
 327     // Now, this loop is suitable for rotation.
 328     BasicBlock *OrigPreheader = L->getLoopPreheader();
 329
 330     // If the loop could not be converted to canonical form, it must have an
 331     // indirectbr in it, just give up.
 332     if (!OrigPreheader || !L->hasDedicatedExits())
 333       return Rotated;
 334
 335     // Anything ScalarEvolution may know about this loop or the PHI nodes
 336     // in its header will soon be invalidated. We should also invalidate
 337     // all outer loops because insertion and deletion of blocks that happens
 338     // during the rotation may violate invariants related to backedge taken
 339     // infos in them.
 340     if (SE)
 341       SE->forgetTopmostLoop(L);
 342
 343     LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
 344     if (MSSAU && VerifyMemorySSA)
 345       MSSAU->getMemorySSA()->verifyMemorySSA();
 346
 347     // Find new Loop header. NewHeader is a Header's one and only successor
 348     // that is inside loop.  Header's other successor is outside the
 349     // loop.  Otherwise loop is not suitable for rotation.
 350     BasicBlock *Exit = BI->getSuccessor(0);
 351     BasicBlock *NewHeader = BI->getSuccessor(1);
 352     if (L->contains(Exit))
 353       std::swap(Exit, NewHeader);
 354     assert(NewHeader && "Unable to determine new loop header");
 355     assert(L->contains(NewHeader) && !L->contains(Exit) &&
 356            "Unable to determine loop header and exit blocks");
 357
 358     // This code assumes that the new header has exactly one predecessor.
 359     // Remove any single-entry PHI nodes in it.
 360     assert(NewHeader->getSinglePredecessor() &&
 361            "New header doesn't have one pred!");
 362     FoldSingleEntryPHINodes(NewHeader);
 363
 364     // Begin by walking OrigHeader and populating ValueMap with an entry for
 365     // each Instruction.
 366     BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
 367     ValueToValueMapTy ValueMap, ValueMapMSSA;
 368
 369     // For PHI nodes, the value available in OldPreHeader is just the
 370     // incoming value from OldPreHeader.
 371     for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)
 372       InsertNewValueIntoMap(ValueMap, PN,
 373                             PN->getIncomingValueForBlock(OrigPreheader));
 374
 375     // For the rest of the instructions, either hoist to the OrigPreheader if
 376     // possible or create a clone in the OldPreHeader if not.
 377     Instruction *LoopEntryBranch = OrigPreheader->getTerminator();
 378
 379     // Record all debug intrinsics preceding LoopEntryBranch to avoid duplication.
 380     using DbgIntrinsicHash =
 381       std::pair<std::pair<Value *, DILocalVariable *>, DIExpression *>;
 382     auto makeHash = [](DbgVariableIntrinsic *D) -> DbgIntrinsicHash {
 383       return {{D->getVariableLocation(), D->getVariable()}, D->getExpression()};
 384     };
 385     SmallDenseSet<DbgIntrinsicHash, 8> DbgIntrinsics;
 386     for (auto I = std::next(OrigPreheader->rbegin()), E = OrigPreheader->rend();
 387          I != E; ++I) {
 388       if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&*I))
 389         DbgIntrinsics.insert(makeHash(DII));
 390       else
 391         break;
 392     }
 393
 394     while (I != E) {
 395       Instruction *Inst = &*I++;
 396
 397       // If the instruction's operands are invariant and it doesn't read or write
 398       // memory, then it is safe to hoist.  Doing this doesn't change the order of
 399       // execution in the preheader, but does prevent the instruction from
 400       // executing in each iteration of the loop.  This means it is safe to hoist
 401       // something that might trap, but isn't safe to hoist something that reads
 402       // memory (without proving that the loop doesn't write).
 403       if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&
 404           !Inst->mayWriteToMemory() && !Inst->isTerminator() &&
 405           !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) {
 406         Inst->moveBefore(LoopEntryBranch);
 407         continue;
 408       }
 409
 410       // Otherwise, create a duplicate of the instruction.
 411       Instruction *C = Inst->clone();
 412
 413       // Eagerly remap the operands of the instruction.
 414       RemapInstruction(C, ValueMap,
 415                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
 416
 417       // Avoid inserting the same intrinsic twice.
 418       if (auto *DII = dyn_cast<DbgVariableIntrinsic>(C))
 419         if (DbgIntrinsics.count(makeHash(DII))) {
 420           C->deleteValue();
 421           continue;
 422         }
 423
 424       // With the operands remapped, see if the instruction constant folds or is
 425       // otherwise simplifyable.  This commonly occurs because the entry from PHI
 426       // nodes allows icmps and other instructions to fold.
 427       Value *V = SimplifyInstruction(C, SQ);
 428       if (V && LI->replacementPreservesLCSSAForm(C, V)) {
 429         // If so, then delete the temporary instruction and stick the folded value
 430         // in the map.
 431         InsertNewValueIntoMap(ValueMap, Inst, V);
 432         if (!C->mayHaveSideEffects()) {
 433           C->deleteValue();
 434           C = nullptr;
 435         }
 436       } else {
 437         InsertNewValueIntoMap(ValueMap, Inst, C);
 438       }
 439       if (C) {
 440         // Otherwise, stick the new instruction into the new block!
 441         C->setName(Inst->getName());
 442         C->insertBefore(LoopEntryBranch);
 443
 444         if (auto *II = dyn_cast<IntrinsicInst>(C))
 445           if (II->getIntrinsicID() == Intrinsic::assume)
 446             AC->registerAssumption(II);
 447         // MemorySSA cares whether the cloned instruction was inserted or not, and
 448         // not whether it can be remapped to a simplified value.
 449         if (MSSAU)
 450           InsertNewValueIntoMap(ValueMapMSSA, Inst, C);
 451       }
 452     }
 453
 454     // Along with all the other instructions, we just cloned OrigHeader's
 455     // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
 456     // successors by duplicating their incoming values for OrigHeader.
 457     for (BasicBlock *SuccBB : successors(OrigHeader))
 458       for (BasicBlock::iterator BI = SuccBB->begin();
 459            PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
 460         PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
 461
 462     // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
 463     // OrigPreHeader's old terminator (the original branch into the loop), and
 464     // remove the corresponding incoming values from the PHI nodes in OrigHeader.
 465     LoopEntryBranch->eraseFromParent();
 466
 467     // Update MemorySSA before the rewrite call below changes the 1:1
 468     // instruction:cloned_instruction_or_value mapping.
 469     if (MSSAU) {
 470       InsertNewValueIntoMap(ValueMapMSSA, OrigHeader, OrigPreheader);
 471       MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader,
 472                                           ValueMapMSSA);
 473     }
 474
 475     SmallVector<PHINode*, 2> InsertedPHIs;
 476     // If there were any uses of instructions in the duplicated block outside the
 477     // loop, update them, inserting PHI nodes as required
 478     RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap,
 479                                     &InsertedPHIs);
 480
 481     // Attach dbg.value intrinsics to the new phis if that phi uses a value that
 482     // previously had debug metadata attached. This keeps the debug info
 483     // up-to-date in the loop body.
 484     if (!InsertedPHIs.empty())
 485       insertDebugValuesForPHIs(OrigHeader, InsertedPHIs);
 486
 487     // NewHeader is now the header of the loop.
 488     L->moveToHeader(NewHeader);
 489     assert(L->getHeader() == NewHeader && "Latch block is our new header");
 490
 491     // Inform DT about changes to the CFG.
 492     if (DT) {
 493       // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
 494       // the DT about the removed edge to the OrigHeader (that got removed).
 495       SmallVector<DominatorTree::UpdateType, 3> Updates;
 496       Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
 497       Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
 498       Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
 499       DT->applyUpdates(Updates);
 500
 501       if (MSSAU) {
 502         MSSAU->applyUpdates(Updates, *DT);
 503         if (VerifyMemorySSA)
 504           MSSAU->getMemorySSA()->verifyMemorySSA();
 505       }
 506     }
 507
 508     // At this point, we've finished our major CFG changes.  As part of cloning
 509     // the loop into the preheader we've simplified instructions and the
 510     // duplicated conditional branch may now be branching on a constant.  If it is
 511     // branching on a constant and if that constant means that we enter the loop,
 512     // then we fold away the cond branch to an uncond branch.  This simplifies the
 513     // loop in cases important for nested loops, and it also means we don't have
 514     // to split as many edges.
 515     BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
 516     assert(PHBI->isConditional() && "Should be clone of BI condbr!");
 517     if (!isa<ConstantInt>(PHBI->getCondition()) ||
 518         PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
 519         NewHeader) {
 520       // The conditional branch can't be folded, handle the general case.
 521       // Split edges as necessary to preserve LoopSimplify form.
 522
 523       // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
 524       // thus is not a preheader anymore.
 525       // Split the edge to form a real preheader.
 526       BasicBlock *NewPH = SplitCriticalEdge(
 527                                             OrigPreheader, NewHeader,
 528                                             CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
 529       NewPH->setName(NewHeader->getName() + ".lr.ph");
 530
 531       // Preserve canonical loop form, which means that 'Exit' should have only
 532       // one predecessor. Note that Exit could be an exit block for multiple
 533       // nested loops, causing both of the edges to now be critical and need to
 534       // be split.
 535       SmallVector<BasicBlock *, 4> ExitPreds(pred_begin(Exit), pred_end(Exit));
 536       bool SplitLatchEdge = false;
 537       for (BasicBlock *ExitPred : ExitPreds) {
 538         // We only need to split loop exit edges.
 539         Loop *PredLoop = LI->getLoopFor(ExitPred);
 540         if (!PredLoop || PredLoop->contains(Exit) ||
 541             ExitPred->getTerminator()->isIndirectTerminator())
 542           continue;
 543         SplitLatchEdge |= L->getLoopLatch() == ExitPred;
 544         BasicBlock *ExitSplit = SplitCriticalEdge(
 545                                                   ExitPred, Exit,
 546                                                   CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
 547         ExitSplit->moveBefore(Exit);
 548       }
 549       assert(SplitLatchEdge &&
 550              "Despite splitting all preds, failed to split latch exit?");
 551     } else {
 552       // We can fold the conditional branch in the preheader, this makes things
 553       // simpler. The first step is to remove the extra edge to the Exit block.
 554       Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
 555       BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
 556       NewBI->setDebugLoc(PHBI->getDebugLoc());
 557       PHBI->eraseFromParent();
 558
 559       // With our CFG finalized, update DomTree if it is available.
 560       if (DT) DT->deleteEdge(OrigPreheader, Exit);
 561
 562       // Update MSSA too, if available.
 563       if (MSSAU)
 564         MSSAU->removeEdge(OrigPreheader, Exit);
 565     }
 566
 567     assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
 568     assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
 569
 570     if (MSSAU && VerifyMemorySSA)
 571       MSSAU->getMemorySSA()->verifyMemorySSA();
 572
 573     // Now that the CFG and DomTree are in a consistent state again, try to merge
 574     // the OrigHeader block into OrigLatch.  This will succeed if they are
 575     // connected by an unconditional branch.  This is just a cleanup so the
 576     // emitted code isn't too gross in this common case.
 577     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 578     MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);
 579
 580     if (MSSAU && VerifyMemorySSA)
 581       MSSAU->getMemorySSA()->verifyMemorySSA();
 582
 583     LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
 584
 585     ++NumRotated;
 586
 587     Rotated = true;
 588     SimplifiedLatch = false;
 589
 590     // Check that new latch is a deoptimizing exit and then repeat rotation if possible.
 591     // Deoptimizing latch exit is not a generally typical case, so we just loop over.
 592     // TODO: if it becomes a performance bottleneck extend rotation algorithm
 593     // to handle multiple rotations in one go.
 594   } while (MultiRotate && canRotateDeoptimizingLatchExit(L));
 595
 596
 597   return true;
 598 }
 599
 600 /// Determine whether the instructions in this range may be safely and cheaply
 601 /// speculated. This is not an important enough situation to develop complex
 602 /// heuristics. We handle a single arithmetic instruction along with any type
 603 /// conversions.
 604 static bool shouldSpeculateInstrs(BasicBlock::iterator Begin,
 605                                   BasicBlock::iterator End, Loop *L) {
 606   bool seenIncrement = false;
 607   bool MultiExitLoop = false;
 608
 609   if (!L->getExitingBlock())
 610     MultiExitLoop = true;
 611
 612   for (BasicBlock::iterator I = Begin; I != End; ++I) {
 613
 614     if (!isSafeToSpeculativelyExecute(&*I))
 615       return false;
 616
 617     if (isa<DbgInfoIntrinsic>(I))
 618       continue;
 619
 620     switch (I->getOpcode()) {
 621     default:
 622       return false;
 623     case Instruction::GetElementPtr:
 624       // GEPs are cheap if all indices are constant.
 625       if (!cast<GEPOperator>(I)->hasAllConstantIndices())
 626         return false;
 627       // fall-thru to increment case
 628       LLVM_FALLTHROUGH;
 629     case Instruction::Add:
 630     case Instruction::Sub:
 631     case Instruction::And:
 632     case Instruction::Or:
 633     case Instruction::Xor:
 634     case Instruction::Shl:
 635     case Instruction::LShr:
 636     case Instruction::AShr: {
 637       Value *IVOpnd =
 638           !isa<Constant>(I->getOperand(0))
 639               ? I->getOperand(0)
 640               : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr;
 641       if (!IVOpnd)
 642         return false;
 643
 644       // If increment operand is used outside of the loop, this speculation
 645       // could cause extra live range interference.
 646       if (MultiExitLoop) {
 647         for (User *UseI : IVOpnd->users()) {
 648           auto *UserInst = cast<Instruction>(UseI);
 649           if (!L->contains(UserInst))
 650             return false;
 651         }
 652       }
 653
 654       if (seenIncrement)
 655         return false;
 656       seenIncrement = true;
 657       break;
 658     }
 659     case Instruction::Trunc:
 660     case Instruction::ZExt:
 661     case Instruction::SExt:
 662       // ignore type conversions
 663       break;
 664     }
 665   }
 666   return true;
 667 }
 668
 669 /// Fold the loop tail into the loop exit by speculating the loop tail
 670 /// instructions. Typically, this is a single post-increment. In the case of a
 671 /// simple 2-block loop, hoisting the increment can be much better than
 672 /// duplicating the entire loop header. In the case of loops with early exits,
 673 /// rotation will not work anyway, but simplifyLoopLatch will put the loop in
 674 /// canonical form so downstream passes can handle it.
 675 ///
 676 /// I don't believe this invalidates SCEV.
 677 bool LoopRotate::simplifyLoopLatch(Loop *L) {
 678   BasicBlock *Latch = L->getLoopLatch();
 679   if (!Latch || Latch->hasAddressTaken())
 680     return false;
 681
 682   BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
 683   if (!Jmp || !Jmp->isUnconditional())
 684     return false;
 685
 686   BasicBlock *LastExit = Latch->getSinglePredecessor();
 687   if (!LastExit || !L->isLoopExiting(LastExit))
 688     return false;
 689
 690   BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
 691   if (!BI)
 692     return false;
 693
 694   if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
 695     return false;
 696
 697   LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
 698                     << LastExit->getName() << "\n");
 699
 700   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 701   MergeBlockIntoPredecessor(Latch, &DTU, LI, MSSAU, nullptr,
 702                             /*PredecessorWithTwoSuccessors=*/true);
 703
 704   if (MSSAU && VerifyMemorySSA)
 705     MSSAU->getMemorySSA()->verifyMemorySSA();
 706
 707   return true;
 708 }
 709
 710 /// Rotate \c L, and return true if any modification was made.
 711 bool LoopRotate::processLoop(Loop *L) {
 712   // Save the loop metadata.
 713   MDNode *LoopMD = L->getLoopID();
 714
 715   bool SimplifiedLatch = false;
 716
 717   // Simplify the loop latch before attempting to rotate the header
 718   // upward. Rotation may not be needed if the loop tail can be folded into the
 719   // loop exit.
 720   if (!RotationOnly)
 721     SimplifiedLatch = simplifyLoopLatch(L);
 722
 723   bool MadeChange = rotateLoop(L, SimplifiedLatch);
 724   assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
 725          "Loop latch should be exiting after loop-rotate.");
 726
 727   // Restore the loop metadata.
 728   // NB! We presume LoopRotation DOESN'T ADD its own metadata.
 729   if ((MadeChange || SimplifiedLatch) && LoopMD)
 730     L->setLoopID(LoopMD);
 731
 732   return MadeChange || SimplifiedLatch;
 733 }
 734
 735
 736 /// The utility to convert a loop into a loop with bottom test.
 737 bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
 738                         AssumptionCache *AC, DominatorTree *DT,
 739                         ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
 740                         const SimplifyQuery &SQ, bool RotationOnly = true,
 741                         unsigned Threshold = unsigned(-1),
 742                         bool IsUtilMode = true) {
 743   if (MSSAU && VerifyMemorySSA)
 744     MSSAU->getMemorySSA()->verifyMemorySSA();
 745   LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
 746                 IsUtilMode);
 747   if (MSSAU && VerifyMemorySSA)
 748     MSSAU->getMemorySSA()->verifyMemorySSA();
 749
 750   return LR.processLoop(L);
 751 }