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