//===- LiveValues.cpp - Liveness information for LLVM IR Values. ----------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the implementation for the LLVM IR Value liveness
// analysis pass.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LiveValues.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
using namespace llvm;

namespace llvm {
  FunctionPass *createLiveValuesPass() { return new LiveValues(); }
}

char LiveValues::ID = 0;
INITIALIZE_PASS_BEGIN(LiveValues, "live-values",
                "Value Liveness Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_END(LiveValues, "live-values",
                "Value Liveness Analysis", false, true)

LiveValues::LiveValues() : FunctionPass(ID) {
  initializeLiveValuesPass(*PassRegistry::getPassRegistry());
}

void LiveValues::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<DominatorTree>();
  AU.addRequired<LoopInfo>();
  AU.setPreservesAll();
}

bool LiveValues::runOnFunction(Function &F) {
  DT = &getAnalysis<DominatorTree>();
  LI = &getAnalysis<LoopInfo>();

  // This pass' values are computed lazily, so there's nothing to do here.

  return false;
}

void LiveValues::releaseMemory() {
  Memos.clear();
}

/// isUsedInBlock - Test if the given value is used in the given block.
///
bool LiveValues::isUsedInBlock(const Value *V, const BasicBlock *BB) {
  Memo &M = getMemo(V);
  return M.Used.count(BB);
}

/// isLiveThroughBlock - Test if the given value is known to be
/// live-through the given block, meaning that the block is properly
/// dominated by the value's definition, and there exists a block
/// reachable from it that contains a use. This uses a conservative
/// approximation that errs on the side of returning false.
///
bool LiveValues::isLiveThroughBlock(const Value *V,
                                    const BasicBlock *BB) {
  Memo &M = getMemo(V);
  return M.LiveThrough.count(BB);
}

/// isKilledInBlock - Test if the given value is known to be killed in
/// the given block, meaning that the block contains a use of the value,
/// and no blocks reachable from the block contain a use. This uses a
/// conservative approximation that errs on the side of returning false.
///
bool LiveValues::isKilledInBlock(const Value *V, const BasicBlock *BB) {
  Memo &M = getMemo(V);
  return M.Killed.count(BB);
}

/// getMemo - Retrieve an existing Memo for the given value if one
/// is available, otherwise compute a new one.
///
LiveValues::Memo &LiveValues::getMemo(const Value *V) {
  DenseMap<const Value *, Memo>::iterator I = Memos.find(V);
  if (I != Memos.end())
    return I->second;
  return compute(V);
}

/// getImmediateDominator - A handy utility for the specific DominatorTree
/// query that we need here.
///
static const BasicBlock *getImmediateDominator(const BasicBlock *BB,
                                               const DominatorTree *DT) {
  DomTreeNode *Node = DT->getNode(const_cast<BasicBlock *>(BB))->getIDom();
  return Node ? Node->getBlock() : 0;
}

/// compute - Compute a new Memo for the given value.
///
LiveValues::Memo &LiveValues::compute(const Value *V) {
  Memo &M = Memos[V];

  // Determine the block containing the definition.
  const BasicBlock *DefBB;
  // Instructions define values with meaningful live ranges.
  if (const Instruction *I = dyn_cast<Instruction>(V))
    DefBB = I->getParent();
  // Arguments can be analyzed as values defined in the entry block.
  else if (const Argument *A = dyn_cast<Argument>(V))
    DefBB = &A->getParent()->getEntryBlock();
  // Constants and other things aren't meaningful here, so just
  // return having computed an empty Memo so that we don't come
  // here again. The assumption here is that client code won't
  // be asking about such values very often.
  else
    return M;

  // Determine if the value is defined inside a loop. This is used
  // to track whether the value is ever used outside the loop, so
  // it'll be set to null if the value is either not defined in a
  // loop or used outside the loop in which it is defined.
  const Loop *L = LI->getLoopFor(DefBB);

  // Track whether the value is used anywhere outside of the block
  // in which it is defined.
  bool LiveOutOfDefBB = false;

  // Examine each use of the value.
  for (Value::const_use_iterator I = V->use_begin(), E = V->use_end();
       I != E; ++I) {
    const User *U = *I;
    const BasicBlock *UseBB = cast<Instruction>(U)->getParent();

    // Note the block in which this use occurs.
    M.Used.insert(UseBB);

    // If the use block doesn't have successors, the value can be
    // considered killed.
    if (succ_begin(UseBB) == succ_end(UseBB))
      M.Killed.insert(UseBB);

    // Observe whether the value is used outside of the loop in which
    // it is defined. Switch to an enclosing loop if necessary.
    for (; L; L = L->getParentLoop())
      if (L->contains(UseBB))
        break;

    // Search for live-through blocks.
    const BasicBlock *BB;
    if (const PHINode *PHI = dyn_cast<PHINode>(U)) {
      // For PHI nodes, start the search at the incoming block paired with the
      // incoming value, which must be dominated by the definition.
      unsigned Num = PHI->getIncomingValueNumForOperand(I.getOperandNo());
      BB = PHI->getIncomingBlock(Num);

      // A PHI-node use means the value is live-out of it's defining block
      // even if that block also contains the only use.
      LiveOutOfDefBB = true;
    } else {
      // Otherwise just start the search at the use.
      BB = UseBB;

      // Note if the use is outside the defining block.
      LiveOutOfDefBB |= UseBB != DefBB;
    }

    // Climb the immediate dominator tree from the use to the definition
    // and mark all intermediate blocks as live-through.
    for (; BB != DefBB; BB = getImmediateDominator(BB, DT)) {
      if (BB != UseBB && !M.LiveThrough.insert(BB))
        break;
    }
  }

  // If the value is defined inside a loop and is not live outside
  // the loop, then each exit block of the loop in which the value
  // is used is a kill block.
  if (L) {
    SmallVector<BasicBlock *, 4> ExitingBlocks;
    L->getExitingBlocks(ExitingBlocks);
    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
      const BasicBlock *ExitingBlock = ExitingBlocks[i];
      if (M.Used.count(ExitingBlock))
        M.Killed.insert(ExitingBlock);
    }
  }

  // If the value was never used outside the block in which it was
  // defined, it's killed in that block.
  if (!LiveOutOfDefBB)
    M.Killed.insert(DefBB);

  return M;
}