contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopDeletion.cpp

   1 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
   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 implements the Dead Loop Deletion Pass. This pass is responsible
  10 // for eliminating loops with non-infinite computable trip counts that have no
  11 // side effects or volatile instructions, and do not contribute to the
  12 // computation of the function's return value.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/Scalar/LoopDeletion.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/Analysis/GlobalsModRef.h"
  20 #include "llvm/Analysis/LoopPass.h"
  21 #include "llvm/IR/Dominators.h"
  22 #include "llvm/IR/PatternMatch.h"
  23 #include "llvm/InitializePasses.h"
  24 #include "llvm/Transforms/Scalar.h"
  25 #include "llvm/Transforms/Scalar/LoopPassManager.h"
  26 #include "llvm/Transforms/Utils/LoopUtils.h"
  27 using namespace llvm;
  28
  29 #define DEBUG_TYPE "loop-delete"
  30
  31 STATISTIC(NumDeleted, "Number of loops deleted");
  32
  33 enum class LoopDeletionResult {
  34   Unmodified,
  35   Modified,
  36   Deleted,
  37 };
  38
  39 /// Determines if a loop is dead.
  40 ///
  41 /// This assumes that we've already checked for unique exit and exiting blocks,
  42 /// and that the code is in LCSSA form.
  43 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
  44                        SmallVectorImpl<BasicBlock *> &ExitingBlocks,
  45                        BasicBlock *ExitBlock, bool &Changed,
  46                        BasicBlock *Preheader) {
  47   // Make sure that all PHI entries coming from the loop are loop invariant.
  48   // Because the code is in LCSSA form, any values used outside of the loop
  49   // must pass through a PHI in the exit block, meaning that this check is
  50   // sufficient to guarantee that no loop-variant values are used outside
  51   // of the loop.
  52   bool AllEntriesInvariant = true;
  53   bool AllOutgoingValuesSame = true;
  54   for (PHINode &P : ExitBlock->phis()) {
  55     Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
  56
  57     // Make sure all exiting blocks produce the same incoming value for the exit
  58     // block.  If there are different incoming values for different exiting
  59     // blocks, then it is impossible to statically determine which value should
  60     // be used.
  61     AllOutgoingValuesSame =
  62         all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
  63           return incoming == P.getIncomingValueForBlock(BB);
  64         });
  65
  66     if (!AllOutgoingValuesSame)
  67       break;
  68
  69     if (Instruction *I = dyn_cast<Instruction>(incoming))
  70       if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
  71         AllEntriesInvariant = false;
  72         break;
  73       }
  74   }
  75
  76   if (Changed)
  77     SE.forgetLoopDispositions(L);
  78
  79   if (!AllEntriesInvariant || !AllOutgoingValuesSame)
  80     return false;
  81
  82   // Make sure that no instructions in the block have potential side-effects.
  83   // This includes instructions that could write to memory, and loads that are
  84   // marked volatile.
  85   for (auto &I : L->blocks())
  86     if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); }))
  87       return false;
  88   return true;
  89 }
  90
  91 /// This function returns true if there is no viable path from the
  92 /// entry block to the header of \p L. Right now, it only does
  93 /// a local search to save compile time.
  94 static bool isLoopNeverExecuted(Loop *L) {
  95   using namespace PatternMatch;
  96
  97   auto *Preheader = L->getLoopPreheader();
  98   // TODO: We can relax this constraint, since we just need a loop
  99   // predecessor.
 100   assert(Preheader && "Needs preheader!");
 101
 102   if (Preheader == &Preheader->getParent()->getEntryBlock())
 103     return false;
 104   // All predecessors of the preheader should have a constant conditional
 105   // branch, with the loop's preheader as not-taken.
 106   for (auto *Pred: predecessors(Preheader)) {
 107     BasicBlock *Taken, *NotTaken;
 108     ConstantInt *Cond;
 109     if (!match(Pred->getTerminator(),
 110                m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
 111       return false;
 112     if (!Cond->getZExtValue())
 113       std::swap(Taken, NotTaken);
 114     if (Taken == Preheader)
 115       return false;
 116   }
 117   assert(!pred_empty(Preheader) &&
 118          "Preheader should have predecessors at this point!");
 119   // All the predecessors have the loop preheader as not-taken target.
 120   return true;
 121 }
 122
 123 /// Remove a loop if it is dead.
 124 ///
 125 /// A loop is considered dead if it does not impact the observable behavior of
 126 /// the program other than finite running time. This never removes a loop that
 127 /// might be infinite (unless it is never executed), as doing so could change
 128 /// the halting/non-halting nature of a program.
 129 ///
 130 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
 131 /// order to make various safety checks work.
 132 ///
 133 /// \returns true if any changes were made. This may mutate the loop even if it
 134 /// is unable to delete it due to hoisting trivially loop invariant
 135 /// instructions out of the loop.
 136 static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
 137                                            ScalarEvolution &SE, LoopInfo &LI) {
 138   assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
 139
 140   // We can only remove the loop if there is a preheader that we can branch from
 141   // after removing it. Also, if LoopSimplify form is not available, stay out
 142   // of trouble.
 143   BasicBlock *Preheader = L->getLoopPreheader();
 144   if (!Preheader || !L->hasDedicatedExits()) {
 145     LLVM_DEBUG(
 146         dbgs()
 147         << "Deletion requires Loop with preheader and dedicated exits.\n");
 148     return LoopDeletionResult::Unmodified;
 149   }
 150   // We can't remove loops that contain subloops.  If the subloops were dead,
 151   // they would already have been removed in earlier executions of this pass.
 152   if (L->begin() != L->end()) {
 153     LLVM_DEBUG(dbgs() << "Loop contains subloops.\n");
 154     return LoopDeletionResult::Unmodified;
 155   }
 156
 157
 158   BasicBlock *ExitBlock = L->getUniqueExitBlock();
 159
 160   if (ExitBlock && isLoopNeverExecuted(L)) {
 161     LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
 162     // Set incoming value to undef for phi nodes in the exit block.
 163     for (PHINode &P : ExitBlock->phis()) {
 164       std::fill(P.incoming_values().begin(), P.incoming_values().end(),
 165                 UndefValue::get(P.getType()));
 166     }
 167     deleteDeadLoop(L, &DT, &SE, &LI);
 168     ++NumDeleted;
 169     return LoopDeletionResult::Deleted;
 170   }
 171
 172   // The remaining checks below are for a loop being dead because all statements
 173   // in the loop are invariant.
 174   SmallVector<BasicBlock *, 4> ExitingBlocks;
 175   L->getExitingBlocks(ExitingBlocks);
 176
 177   // We require that the loop only have a single exit block.  Otherwise, we'd
 178   // be in the situation of needing to be able to solve statically which exit
 179   // block will be branched to, or trying to preserve the branching logic in
 180   // a loop invariant manner.
 181   if (!ExitBlock) {
 182     LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n");
 183     return LoopDeletionResult::Unmodified;
 184   }
 185   // Finally, we have to check that the loop really is dead.
 186   bool Changed = false;
 187   if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
 188     LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
 189     return Changed ? LoopDeletionResult::Modified
 190                    : LoopDeletionResult::Unmodified;
 191   }
 192
 193   // Don't remove loops for which we can't solve the trip count.
 194   // They could be infinite, in which case we'd be changing program behavior.
 195   const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
 196   if (isa<SCEVCouldNotCompute>(S)) {
 197     LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
 198     return Changed ? LoopDeletionResult::Modified
 199                    : LoopDeletionResult::Unmodified;
 200   }
 201
 202   LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
 203   deleteDeadLoop(L, &DT, &SE, &LI);
 204   ++NumDeleted;
 205
 206   return LoopDeletionResult::Deleted;
 207 }
 208
 209 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
 210                                         LoopStandardAnalysisResults &AR,
 211                                         LPMUpdater &Updater) {
 212
 213   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
 214   LLVM_DEBUG(L.dump());
 215   std::string LoopName = L.getName();
 216   auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI);
 217   if (Result == LoopDeletionResult::Unmodified)
 218     return PreservedAnalyses::all();
 219
 220   if (Result == LoopDeletionResult::Deleted)
 221     Updater.markLoopAsDeleted(L, LoopName);
 222
 223   return getLoopPassPreservedAnalyses();
 224 }
 225
 226 namespace {
 227 class LoopDeletionLegacyPass : public LoopPass {
 228 public:
 229   static char ID; // Pass ID, replacement for typeid
 230   LoopDeletionLegacyPass() : LoopPass(ID) {
 231     initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
 232   }
 233
 234   // Possibly eliminate loop L if it is dead.
 235   bool runOnLoop(Loop *L, LPPassManager &) override;
 236
 237   void getAnalysisUsage(AnalysisUsage &AU) const override {
 238     getLoopAnalysisUsage(AU);
 239   }
 240 };
 241 }
 242
 243 char LoopDeletionLegacyPass::ID = 0;
 244 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
 245                       "Delete dead loops", false, false)
 246 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 247 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
 248                     "Delete dead loops", false, false)
 249
 250 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
 251
 252 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
 253   if (skipLoop(L))
 254     return false;
 255   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 256   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 257   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 258
 259   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
 260   LLVM_DEBUG(L->dump());
 261
 262   LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI);
 263
 264   if (Result == LoopDeletionResult::Deleted)
 265     LPM.markLoopAsDeleted(*L);
 266
 267   return Result != LoopDeletionResult::Unmodified;
 268 }