llvm.org GIT mirror llvm / 045a03d lib / Transforms / Scalar / LoopDeletion.cpp
045a03d

Tree @045a03d (Download .tar.gz)

LoopDeletion.cpp @045a03d

0396cd3
0ff7708
 
 
 
 
 
 
 
a8a118b
 
 
 
0ff7708
 
 
 
d04a8d4
 
3c17729
d04a8d4
0db198d
56e1394
eca46e6
0ff7708
 
7962dbd
 
0ff7708
 
 
3e8b663
0ff7708
 
081c34b
 
 
a94d6e8
0ff7708
50776d0
a94d6e8
7b62be2
eca46e6
0ff7708
89c4dc6
 
045a03d
 
 
 
0ff7708
cd52a7a
a94d6e8
844731a
2ab36d3
 
eca46e6
2ab36d3
ce665bd
0ff7708
89c4dc6
0396cd3
0ff7708
 
89c4dc6
9862f31
 
045a03d
a0ec3f9
 
bdc017e
89c4dc6
a94d6e8
0ff7708
9862f31
 
 
 
0ff7708
045a03d
 
89c4dc6
 
c4f3d51
 
 
 
 
89c4dc6
045a03d
 
 
 
c4f3d51
a94d6e8
045a03d
 
 
89c4dc6
045a03d
 
 
 
c4f3d51
fe60104
0ff7708
a94d6e8
045a03d
 
 
 
 
 
0ff7708
9862f31
 
 
0ff7708
 
 
 
7af1c78
0ff7708
 
 
a94d6e8
0ff7708
 
 
5f8b344
a94d6e8
5f8b344
 
9862f31
 
50776d0
1e455c5
2684ddd
 
745f68c
 
 
a94d6e8
0ff7708
89c4dc6
0ff7708
 
a94d6e8
32cc5f4
 
 
 
0ff7708
 
 
 
a94d6e8
0db198d
 
a94d6e8
0db198d
 
a94d6e8
0db198d
 
 
 
 
9862f31
a94d6e8
045a03d
 
0ff7708
bdc017e
045a03d
bdc017e
a94d6e8
0db198d
 
934af9c
0db198d
bdc017e
a94d6e8
9862f31
a94d6e8
89c4dc6
a94d6e8
e54cfdb
 
 
85ebb0f
 
 
 
4c7279a
85ebb0f
e54cfdb
89c4dc6
9862f31
 
e54cfdb
 
89c4dc6
0ff7708
89c4dc6
69254f6
 
 
c4f3d51
 
fe60104
0ff7708
a94d6e8
9862f31
 
85bbd57
0ff7708
 
e54cfdb
 
85bbd57
6227d5c
d0a90b9
0ff7708
d0a90b9
a94d6e8
9862f31
0ff7708
d0a90b9
0db198d
 
0ff7708
 
a94d6e8
e54cfdb
 
9862f31
 
0ff7708
cd5e6dd
0ff7708
e2abdd3
e54cfdb
 
de5df29
0ff7708
 
273fd11
 
a94d6e8
50776d0
fbbc16f
bdc017e
a94d6e8
fe60104
a94d6e8
bdc017e
0ff7708
//===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the Dead Loop Deletion Pass. This pass is responsible
// for eliminating loops with non-infinite computable trip counts that have no
// side effects or volatile instructions, and do not contribute to the
// computation of the function's return value.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
using namespace llvm;

#define DEBUG_TYPE "loop-delete"

STATISTIC(NumDeleted, "Number of loops deleted");

namespace {
  class LoopDeletion : public LoopPass {
  public:
    static char ID; // Pass ID, replacement for typeid
    LoopDeletion() : LoopPass(ID) {
      initializeLoopDeletionPass(*PassRegistry::getPassRegistry());
    }

    // Possibly eliminate loop L if it is dead.
    bool runOnLoop(Loop *L, LPPassManager &) override;

    void getAnalysisUsage(AnalysisUsage &AU) const override {
      getLoopAnalysisUsage(AU);
    }

  private:
    bool isLoopDead(Loop *L, ScalarEvolution &SE,
                    SmallVectorImpl<BasicBlock *> &exitingBlocks,
                    SmallVectorImpl<BasicBlock *> &exitBlocks, bool &Changed,
                    BasicBlock *Preheader);
  };
}

char LoopDeletion::ID = 0;
INITIALIZE_PASS_BEGIN(LoopDeletion, "loop-deletion",
                "Delete dead loops", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)
INITIALIZE_PASS_END(LoopDeletion, "loop-deletion",
                "Delete dead loops", false, false)

Pass *llvm::createLoopDeletionPass() {
  return new LoopDeletion();
}

/// isLoopDead - Determined if a loop is dead.  This assumes that we've already
/// checked for unique exit and exiting blocks, and that the code is in LCSSA
/// form.
bool LoopDeletion::isLoopDead(Loop *L, ScalarEvolution &SE,
                              SmallVectorImpl<BasicBlock *> &exitingBlocks,
                              SmallVectorImpl<BasicBlock *> &exitBlocks,
                              bool &Changed, BasicBlock *Preheader) {
  BasicBlock *exitBlock = exitBlocks[0];

  // Make sure that all PHI entries coming from the loop are loop invariant.
  // Because the code is in LCSSA form, any values used outside of the loop
  // must pass through a PHI in the exit block, meaning that this check is
  // sufficient to guarantee that no loop-variant values are used outside
  // of the loop.
  BasicBlock::iterator BI = exitBlock->begin();
  bool AllEntriesInvariant = true;
  bool AllOutgoingValuesSame = true;
  while (PHINode *P = dyn_cast<PHINode>(BI)) {
    Value *incoming = P->getIncomingValueForBlock(exitingBlocks[0]);

    // Make sure all exiting blocks produce the same incoming value for the exit
    // block.  If there are different incoming values for different exiting
    // blocks, then it is impossible to statically determine which value should
    // be used.
    for (unsigned i = 1, e = exitingBlocks.size(); i < e; ++i) {
      if (incoming != P->getIncomingValueForBlock(exitingBlocks[i])) {
        AllOutgoingValuesSame = false;
        break;
      }
    }

    if (!AllOutgoingValuesSame)
      break;

    if (Instruction *I = dyn_cast<Instruction>(incoming))
      if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
        AllEntriesInvariant = false;
        break;
      }

    ++BI;
  }

  if (Changed)
    SE.forgetLoopDispositions(L);

  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
    return false;

  // Make sure that no instructions in the block have potential side-effects.
  // This includes instructions that could write to memory, and loads that are
  // marked volatile.  This could be made more aggressive by using aliasing
  // information to identify readonly and readnone calls.
  for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
       LI != LE; ++LI) {
    for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
         BI != BE; ++BI) {
      if (BI->mayHaveSideEffects())
        return false;
    }
  }

  return true;
}

/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the
/// observable behavior of the program other than finite running time.  Note
/// we do ensure that this never remove a loop that might be infinite, as doing
/// so could change the halting/non-halting nature of a program.
/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA
/// in order to make various safety checks work.
bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &) {
  if (skipLoop(L))
    return false;

  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");

  // We can only remove the loop if there is a preheader that we can
  // branch from after removing it.
  BasicBlock *preheader = L->getLoopPreheader();
  if (!preheader)
    return false;

  // If LoopSimplify form is not available, stay out of trouble.
  if (!L->hasDedicatedExits())
    return false;

  // We can't remove loops that contain subloops.  If the subloops were dead,
  // they would already have been removed in earlier executions of this pass.
  if (L->begin() != L->end())
    return false;

  SmallVector<BasicBlock*, 4> exitingBlocks;
  L->getExitingBlocks(exitingBlocks);

  SmallVector<BasicBlock*, 4> exitBlocks;
  L->getUniqueExitBlocks(exitBlocks);

  // We require that the loop only have a single exit block.  Otherwise, we'd
  // be in the situation of needing to be able to solve statically which exit
  // block will be branched to, or trying to preserve the branching logic in
  // a loop invariant manner.
  if (exitBlocks.size() != 1)
    return false;

  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();

  // Finally, we have to check that the loop really is dead.
  bool Changed = false;
  if (!isLoopDead(L, SE, exitingBlocks, exitBlocks, Changed, preheader))
    return Changed;

  // Don't remove loops for which we can't solve the trip count.
  // They could be infinite, in which case we'd be changing program behavior.
  const SCEV *S = SE.getMaxBackedgeTakenCount(L);
  if (isa<SCEVCouldNotCompute>(S))
    return Changed;

  // Now that we know the removal is safe, remove the loop by changing the
  // branch from the preheader to go to the single exit block.
  BasicBlock *exitBlock = exitBlocks[0];

  // Because we're deleting a large chunk of code at once, the sequence in which
  // we remove things is very important to avoid invalidation issues.  Don't
  // mess with this unless you have good reason and know what you're doing.

  // Tell ScalarEvolution that the loop is deleted. Do this before
  // deleting the loop so that ScalarEvolution can look at the loop
  // to determine what it needs to clean up.
  SE.forgetLoop(L);

  // Connect the preheader directly to the exit block.
  TerminatorInst *TI = preheader->getTerminator();
  TI->replaceUsesOfWith(L->getHeader(), exitBlock);

  // Rewrite phis in the exit block to get their inputs from
  // the preheader instead of the exiting block.
  BasicBlock *exitingBlock = exitingBlocks[0];
  BasicBlock::iterator BI = exitBlock->begin();
  while (PHINode *P = dyn_cast<PHINode>(BI)) {
    int j = P->getBasicBlockIndex(exitingBlock);
    assert(j >= 0 && "Can't find exiting block in exit block's phi node!");
    P->setIncomingBlock(j, preheader);
    for (unsigned i = 1; i < exitingBlocks.size(); ++i)
      P->removeIncomingValue(exitingBlocks[i]);
    ++BI;
  }

  // Update the dominator tree and remove the instructions and blocks that will
  // be deleted from the reference counting scheme.
  SmallVector<DomTreeNode*, 8> ChildNodes;
  for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
       LI != LE; ++LI) {
    // Move all of the block's children to be children of the preheader, which
    // allows us to remove the domtree entry for the block.
    ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end());
    for (SmallVectorImpl<DomTreeNode *>::iterator DI = ChildNodes.begin(),
         DE = ChildNodes.end(); DI != DE; ++DI) {
      DT.changeImmediateDominator(*DI, DT[preheader]);
    }

    ChildNodes.clear();
    DT.eraseNode(*LI);

    // Remove the block from the reference counting scheme, so that we can
    // delete it freely later.
    (*LI)->dropAllReferences();
  }

  // Erase the instructions and the blocks without having to worry
  // about ordering because we already dropped the references.
  // NOTE: This iteration is safe because erasing the block does not remove its
  // entry from the loop's block list.  We do that in the next section.
  for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
       LI != LE; ++LI)
    (*LI)->eraseFromParent();

  // Finally, the blocks from loopinfo.  This has to happen late because
  // otherwise our loop iterators won't work.
  LoopInfo &loopInfo = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  SmallPtrSet<BasicBlock*, 8> blocks;
  blocks.insert(L->block_begin(), L->block_end());
  for (BasicBlock *BB : blocks)
    loopInfo.removeBlock(BB);

  // The last step is to update LoopInfo now that we've eliminated this loop.
  loopInfo.markAsRemoved(L);
  Changed = true;

  ++NumDeleted;

  return Changed;
}