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

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