// * Assumes values are constant unless proven otherwise
// * Assumes BasicBlocks are dead unless proven otherwise
// * Proves values to be constant, and replaces them with constants
-// . Proves conditional branches constant, and unconditionalizes them
+// * Proves conditional branches constant, and unconditionalizes them
// * Folds multiple identical constants in the constant pool together
//
// Notice that:
//
//===----------------------------------------------------------------------===//
-#include "llvm/Transforms/Scalar/ConstantProp.h"
+#include "llvm/Transforms/Scalar.h"
#include "llvm/ConstantHandling.h"
#include "llvm/Function.h"
+#include "llvm/BasicBlock.h"
#include "llvm/iPHINode.h"
#include "llvm/iMemory.h"
#include "llvm/iTerminators.h"
#include "llvm/Pass.h"
#include "llvm/Support/InstVisitor.h"
#include "Support/STLExtras.h"
+#include "Support/StatisticReporter.h"
#include <algorithm>
#include <set>
#include <iostream>
using std::cerr;
+static Statistic<> NumInstRemoved("sccp\t\t- Number of instructions removed");
+
#if 0 // Enable this to get SCCP debug output
#define DEBUG_SCCP(X) X
#else
std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable
std::map<Value*, InstVal> ValueState; // The state each value is in...
- std::set<Instruction*> InstWorkList;// The instruction work list
+ std::vector<Instruction*> InstWorkList;// The instruction work list
std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
public:
bool runOnFunction(Function *F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- // FIXME: SCCP does not preserve the CFG because it folds terminators!
- //AU.preservesCFG();
+ AU.preservesCFG();
}
DEBUG_SCCP(cerr << "markConstant: " << V << " = " << I);
if (ValueState[I].markConstant(V)) {
- InstWorkList.insert(I);
+ InstWorkList.push_back(I);
return true;
}
return false;
if (ValueState[V].markOverdefined()) {
if (Instruction *I = dyn_cast<Instruction>(V)) {
DEBUG_SCCP(cerr << "markOverdefined: " << V);
- InstWorkList.insert(I); // Only instructions go on the work list
+ InstWorkList.push_back(I); // Only instructions go on the work list
}
return true;
}
// Terminators
void visitReturnInst(ReturnInst *I) { /*does not have an effect*/ }
- void visitBranchInst(BranchInst *I);
- void visitInvokeInst(InvokeInst *I);
- void visitSwitchInst(SwitchInst *I);
+ void visitTerminatorInst(TerminatorInst *TI);
void visitUnaryOperator(Instruction *I);
void visitCastInst(CastInst *I) { visitUnaryOperator(I); }
markOverdefined(I); // Just in case
}
+ // getFeasibleSuccessors - Return a vector of booleans to indicate which
+ // successors are reachable from a given terminator instruction.
+ //
+ void getFeasibleSuccessors(TerminatorInst *I, std::vector<bool> &Succs);
+
// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
// block to the 'To' basic block is currently feasible...
//
while (!BBWorkList.empty() || !InstWorkList.empty()) {
// Process the instruction work list...
while (!InstWorkList.empty()) {
- Instruction *I = *InstWorkList.begin();
- InstWorkList.erase(InstWorkList.begin());
+ Instruction *I = InstWorkList.back();
+ InstWorkList.pop_back();
DEBUG_SCCP(cerr << "\nPopped off I-WL: " << I);
}
}
-#ifdef DEBUG_SCCP
+#if 0
for (Function::iterator BBI = F->begin(), BBEnd = F->end();
BBI != BBEnd; ++BBI)
if (!BBExecutable.count(*BBI))
// Hey, we just changed something!
MadeChanges = true;
-
- // Do NOT advance the iterator, skipping the next instruction...
- continue;
-
- } else if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Inst)) {
- MadeChanges |= ConstantFoldTerminator(BB, BI, TI);
+ ++NumInstRemoved;
+ } else {
+ ++BI;
}
-
- ++BI;
}
}
return MadeChanges;
}
+
+// getFeasibleSuccessors - Return a vector of booleans to indicate which
+// successors are reachable from a given terminator instruction.
+//
+void SCCP::getFeasibleSuccessors(TerminatorInst *TI, std::vector<bool> &Succs) {
+ assert(Succs.size() == TI->getNumSuccessors() && "Succs vector wrong size!");
+ if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+ if (BI->isUnconditional()) {
+ Succs[0] = true;
+ } else {
+ InstVal &BCValue = getValueState(BI->getCondition());
+ if (BCValue.isOverdefined()) {
+ // Overdefined condition variables mean the branch could go either way.
+ Succs[0] = Succs[1] = true;
+ } else if (BCValue.isConstant()) {
+ // Constant condition variables mean the branch can only go a single way
+ Succs[BCValue.getConstant() == ConstantBool::False] = true;
+ }
+ }
+ } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
+ // Invoke instructions successors are always executable.
+ Succs[0] = Succs[1] = true;
+ } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+ InstVal &SCValue = getValueState(SI->getCondition());
+ if (SCValue.isOverdefined()) { // Overdefined condition?
+ // All destinations are executable!
+ Succs.assign(TI->getNumSuccessors(), true);
+ } else if (SCValue.isConstant()) {
+ Constant *CPV = SCValue.getConstant();
+ // Make sure to skip the "default value" which isn't a value
+ for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
+ if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
+ Succs[i] = true;
+ return;
+ }
+ }
+
+ // Constant value not equal to any of the branches... must execute
+ // default branch then...
+ Succs[0] = true;
+ }
+ } else {
+ cerr << "SCCP: Don't know how to handle: " << TI;
+ Succs.assign(TI->getNumSuccessors(), true);
+ }
+}
+
+
// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
// block to the 'To' basic block is currently feasible...
//
// Make sure the source basic block is executable!!
if (!BBExecutable.count(From)) return false;
- // This should check the terminator in From!
- return true;
+ // Check to make sure this edge itself is actually feasible now...
+ TerminatorInst *FT = From->getTerminator();
+ std::vector<bool> SuccFeasible(FT->getNumSuccessors());
+ getFeasibleSuccessors(FT, SuccFeasible);
+
+ // Check all edges from From to To. If any are feasible, return true.
+ for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
+ if (FT->getSuccessor(i) == To && SuccFeasible[i])
+ return true;
+
+ // Otherwise, none of the edges are actually feasible at this time...
+ return false;
}
// visit Implementations - Something changed in this instruction... Either an
}
}
-void SCCP::visitBranchInst(BranchInst *BI) {
- if (BI->isUnconditional())
- return; // Unconditional branches are already handled!
-
- InstVal &BCValue = getValueState(BI->getCondition());
- if (BCValue.isOverdefined()) {
- // Overdefined condition variables mean the branch could go either way.
- markExecutable(BI->getSuccessor(0));
- markExecutable(BI->getSuccessor(1));
- } else if (BCValue.isConstant()) {
- // Constant condition variables mean the branch can only go a single way.
- if (BCValue.getConstant() == ConstantBool::True)
- markExecutable(BI->getSuccessor(0));
- else
- markExecutable(BI->getSuccessor(1));
- }
-}
+void SCCP::visitTerminatorInst(TerminatorInst *TI) {
+ std::vector<bool> SuccFeasible(TI->getNumSuccessors());
+ getFeasibleSuccessors(TI, SuccFeasible);
-void SCCP::visitInvokeInst(InvokeInst *II) {
- markExecutable(II->getNormalDest());
- markExecutable(II->getExceptionalDest());
-}
-
-void SCCP::visitSwitchInst(SwitchInst *SI) {
- InstVal &SCValue = getValueState(SI->getCondition());
- if (SCValue.isOverdefined()) { // Overdefined condition? All dests are exe
- for(unsigned i = 0, E = SI->getNumSuccessors(); i != E; ++i)
- markExecutable(SI->getSuccessor(i));
- } else if (SCValue.isConstant()) {
- Constant *CPV = SCValue.getConstant();
- // Make sure to skip the "default value" which isn't a value
- for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
- if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
- markExecutable(SI->getSuccessor(i));
- return;
- }
- }
-
- // Constant value not equal to any of the branches... must execute
- // default branch then...
- markExecutable(SI->getDefaultDest());
- }
+ // Mark all feasible successors executable...
+ for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
+ if (SuccFeasible[i])
+ markExecutable(TI->getSuccessor(i));
}
void SCCP::visitUnaryOperator(Instruction *I) {
if (V1State.isOverdefined() || V2State.isOverdefined()) {
markOverdefined(I);
} else if (V1State.isConstant() && V2State.isConstant()) {
- Constant *Result = ConstantFoldBinaryInstruction(I->getOpcode(),
- V1State.getConstant(),
- V2State.getConstant());
+ Constant *Result = 0;
+ if (isa<BinaryOperator>(I))
+ Result = ConstantFoldBinaryInstruction(I->getOpcode(),
+ V1State.getConstant(),
+ V2State.getConstant());
+ else if (isa<ShiftInst>(I))
+ Result = ConstantFoldShiftInstruction(I->getOpcode(),
+ V1State.getConstant(),
+ V2State.getConstant());
if (Result)
markConstant(I, Result); // This instruction constant folds!
else
projects / oota-llvm.git / blobdiff