JumpThreading.cpp

//===- JumpThreading.cpp - Thread control through conditional blocks ------===//
//
//                     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 Jump Threading pass.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "jump-threading"
#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Target/TargetData.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;

STATISTIC(NumThreads, "Number of jumps threaded");
STATISTIC(NumFolds,   "Number of terminators folded");
STATISTIC(NumDupes,   "Number of branch blocks duplicated to eliminate phi");

static cl::opt<unsigned>
Threshold("jump-threading-threshold",
          cl::desc("Max block size to duplicate for jump threading"),
          cl::init(6), cl::Hidden);

namespace {
  // These are at global scope so static functions can use them too.
  typedef SmallVectorImpl<std::pair<Constant*, BasicBlock*> > PredValueInfo;
  typedef SmallVector<std::pair<Constant*, BasicBlock*>, 8> PredValueInfoTy;

  // This is used to keep track of what kind of constant we're currently hoping
  // to find.
  enum ConstantPreference {
    WantInteger,
    WantBlockAddress
  };

  /// This pass performs 'jump threading', which looks at blocks that have
  /// multiple predecessors and multiple successors.  If one or more of the
  /// predecessors of the block can be proven to always jump to one of the
  /// successors, we forward the edge from the predecessor to the successor by
  /// duplicating the contents of this block.
  ///
  /// An example of when this can occur is code like this:
  ///
  ///   if () { ...
  ///     X = 4;
  ///   }
  ///   if (X < 3) {
  ///
  /// In this case, the unconditional branch at the end of the first if can be
  /// revectored to the false side of the second if.
  ///
  class JumpThreading : public FunctionPass {
    TargetData *TD;
    LazyValueInfo *LVI;
#ifdef NDEBUG
    SmallPtrSet<BasicBlock*, 16> LoopHeaders;
#else
    SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders;
#endif
    DenseSet<std::pair<Value*, BasicBlock*> > RecursionSet;

    // RAII helper for updating the recursion stack.
    struct RecursionSetRemover {
      DenseSet<std::pair<Value*, BasicBlock*> > &TheSet;
      std::pair<Value*, BasicBlock*> ThePair;

      RecursionSetRemover(DenseSet<std::pair<Value*, BasicBlock*> > &S,
                          std::pair<Value*, BasicBlock*> P)
        : TheSet(S), ThePair(P) { }

      ~RecursionSetRemover() {
        TheSet.erase(ThePair);
      }
    };
  public:
    static char ID; // Pass identification
    JumpThreading() : FunctionPass(ID) {
      initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
    }

    bool runOnFunction(Function &F);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<LazyValueInfo>();
      AU.addPreserved<LazyValueInfo>();
    }

    void FindLoopHeaders(Function &F);
    bool ProcessBlock(BasicBlock *BB);
    bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock*> &PredBBs,
                    BasicBlock *SuccBB);
    bool DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB,
                                  const SmallVectorImpl<BasicBlock *> &PredBBs);

    bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
                                         PredValueInfo &Result,
                                         ConstantPreference Preference);
    bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
                                ConstantPreference Preference);

    bool ProcessBranchOnPHI(PHINode *PN);
    bool ProcessBranchOnXOR(BinaryOperator *BO);

    bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
  };
}

char JumpThreading::ID = 0;
INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
                "Jump Threading", false, false)
INITIALIZE_PASS_DEPENDENCY(LazyValueInfo)
INITIALIZE_PASS_END(JumpThreading, "jump-threading",
                "Jump Threading", false, false)

// Public interface to the Jump Threading pass
FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }

/// runOnFunction - Top level algorithm.
///
bool JumpThreading::runOnFunction(Function &F) {
  DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
  TD = getAnalysisIfAvailable<TargetData>();
  LVI = &getAnalysis<LazyValueInfo>();

  FindLoopHeaders(F);

  bool Changed, EverChanged = false;
  do {
    Changed = false;
    for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
      BasicBlock *BB = I;
      // Thread all of the branches we can over this block.
      while (ProcessBlock(BB))
        Changed = true;

      ++I;

      // If the block is trivially dead, zap it.  This eliminates the successor
      // edges which simplifies the CFG.
      if (pred_begin(BB) == pred_end(BB) &&
          BB != &BB->getParent()->getEntryBlock()) {
        DEBUG(dbgs() << "  JT: Deleting dead block '" << BB->getName()
              << "' with terminator: " << *BB->getTerminator() << '\n');
        LoopHeaders.erase(BB);
        LVI->eraseBlock(BB);
        DeleteDeadBlock(BB);
        Changed = true;
        continue;
      }

      BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());

      // Can't thread an unconditional jump, but if the block is "almost
      // empty", we can replace uses of it with uses of the successor and make
      // this dead.
      if (BI && BI->isUnconditional() &&
          BB != &BB->getParent()->getEntryBlock() &&
          // If the terminator is the only non-phi instruction, try to nuke it.
          BB->getFirstNonPHIOrDbg()->isTerminator()) {
        // Since TryToSimplifyUncondBranchFromEmptyBlock may delete the
        // block, we have to make sure it isn't in the LoopHeaders set.  We
        // reinsert afterward if needed.
        bool ErasedFromLoopHeaders = LoopHeaders.erase(BB);
        BasicBlock *Succ = BI->getSuccessor(0);

        // FIXME: It is always conservatively correct to drop the info
        // for a block even if it doesn't get erased.  This isn't totally
        // awesome, but it allows us to use AssertingVH to prevent nasty
        // dangling pointer issues within LazyValueInfo.
        LVI->eraseBlock(BB);
        if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) {
          Changed = true;
          // If we deleted BB and BB was the header of a loop, then the
          // successor is now the header of the loop.
          BB = Succ;
        }