#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
+#include <map>
using namespace llvm;
STATISTIC(NumInstRemoved, "Number of instructions removed");
/// overdefined, it's entry is simply removed from this map.
DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals;
- /// TrackedFunctionRetVals - If we are tracking arguments into and the return
+ /// TrackedRetVals - If we are tracking arguments into and the return
/// value out of a function, it will have an entry in this map, indicating
/// what the known return value for the function is.
- DenseMap<Function*, LatticeVal> TrackedFunctionRetVals;
+ DenseMap<Function*, LatticeVal> TrackedRetVals;
+
+ /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
+ /// that return multiple values.
+ std::map<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals;
// The reason for two worklists is that overdefined is the lowest state
// on the lattice, and moving things to overdefined as fast as possible
/// MarkBlockExecutable - This method can be used by clients to mark all of
/// the blocks that are known to be intrinsically live in the processed unit.
void MarkBlockExecutable(BasicBlock *BB) {
- DOUT << "Marking Block Executable: " << BB->getName() << "\n";
+ DOUT << "Marking Block Executable: " << BB->getNameStart() << "\n";
BBExecutable.insert(BB); // Basic block is executable!
BBWorkList.push_back(BB); // Add the block to the work list!
}
void AddTrackedFunction(Function *F) {
assert(F->hasInternalLinkage() && "Can only track internal functions!");
// Add an entry, F -> undef.
- TrackedFunctionRetVals[F];
+ if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) {
+ for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
+ TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i),
+ LatticeVal()));
+ } else
+ TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
}
/// Solve - Solve for constants and executable blocks.
return ValueState;
}
- /// getTrackedFunctionRetVals - Get the inferred return value map.
+ /// getTrackedRetVals - Get the inferred return value map.
///
- const DenseMap<Function*, LatticeVal> &getTrackedFunctionRetVals() {
- return TrackedFunctionRetVals;
+ const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
+ return TrackedRetVals;
}
/// getTrackedGlobals - Get and return the set of inferred initializers for
// markOverdefined - Make a value be marked as "overdefined". If the
// value is not already overdefined, add it to the overdefined instruction
// work list so that the users of the instruction are updated later.
-
inline void markOverdefined(LatticeVal &IV, Value *V) {
if (IV.markOverdefined()) {
DEBUG(DOUT << "markOverdefined: ";
return; // This edge is already known to be executable!
if (BBExecutable.count(Dest)) {
- DOUT << "Marking Edge Executable: " << Source->getName()
- << " -> " << Dest->getName() << "\n";
+ DOUT << "Marking Edge Executable: " << Source->getNameStart()
+ << " -> " << Dest->getNameStart() << "\n";
// The destination is already executable, but we just made an edge
// feasible that wasn't before. Revisit the PHI nodes in the block
void visitTerminatorInst(TerminatorInst &TI);
void visitCastInst(CastInst &I);
+ void visitGetResultInst(GetResultInst &GRI);
void visitSelectInst(SelectInst &I);
void visitBinaryOperator(Instruction &I);
void visitCmpInst(CmpInst &I);
(SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
// 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 if (SCValue.isConstant())
+ Succs[SI->findCaseValue(cast<ConstantInt>(SCValue.getConstant()))] = true;
} else {
assert(0 && "SCCP: Don't know how to handle this terminator!");
}
void SCCPSolver::visitReturnInst(ReturnInst &I) {
if (I.getNumOperands() == 0) return; // Ret void
- // If we are tracking the return value of this function, merge it in.
Function *F = I.getParent()->getParent();
- if (F->hasInternalLinkage() && !TrackedFunctionRetVals.empty()) {
+ // If we are tracking the return value of this function, merge it in.
+ if (!F->hasInternalLinkage())
+ return;
+
+ if (!TrackedRetVals.empty() && I.getNumOperands() == 1) {
DenseMap<Function*, LatticeVal>::iterator TFRVI =
- TrackedFunctionRetVals.find(F);
- if (TFRVI != TrackedFunctionRetVals.end() &&
+ TrackedRetVals.find(F);
+ if (TFRVI != TrackedRetVals.end() &&
!TFRVI->second.isOverdefined()) {
LatticeVal &IV = getValueState(I.getOperand(0));
mergeInValue(TFRVI->second, F, IV);
+ return;
+ }
+ }
+
+ // Handle functions that return multiple values.
+ if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) {
+ for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
+ std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ It = TrackedMultipleRetVals.find(std::make_pair(F, i));
+ if (It == TrackedMultipleRetVals.end()) break;
+ mergeInValue(It->second, F, getValueState(I.getOperand(i)));
}
}
}
-
void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
SmallVector<bool, 16> SuccFeasible;
getFeasibleSuccessors(TI, SuccFeasible);
VState.getConstant(), I.getType()));
}
+void SCCPSolver::visitGetResultInst(GetResultInst &GRI) {
+ Value *Aggr = GRI.getOperand(0);
+
+ // If the operand to the getresult is an undef, the result is undef.
+ if (isa<UndefValue>(Aggr))
+ return;
+
+ Function *F;
+ if (CallInst *CI = dyn_cast<CallInst>(Aggr))
+ F = CI->getCalledFunction();
+ else
+ F = cast<InvokeInst>(Aggr)->getCalledFunction();
+
+ // TODO: If IPSCCP resolves the callee of this function, we could propagate a
+ // result back!
+ if (F == 0 || TrackedMultipleRetVals.empty()) {
+ markOverdefined(&GRI);
+ return;
+ }
+
+ // See if we are tracking the result of the callee.
+ std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ It = TrackedMultipleRetVals.find(std::make_pair(F, GRI.getIndex()));
+
+ // If not tracking this function (for example, it is a declaration) just move
+ // to overdefined.
+ if (It == TrackedMultipleRetVals.end()) {
+ markOverdefined(&GRI);
+ return;
+ }
+
+ // Otherwise, the value will be merged in here as a result of CallSite
+ // handling.
+}
+
void SCCPSolver::visitSelectInst(SelectInst &I) {
LatticeVal &CondValue = getValueState(I.getCondition());
if (CondValue.isUndefined())
void SCCPSolver::visitCallSite(CallSite CS) {
Function *F = CS.getCalledFunction();
-
- // If we are tracking this function, we must make sure to bind arguments as
- // appropriate.
- DenseMap<Function*, LatticeVal>::iterator TFRVI =TrackedFunctionRetVals.end();
- if (F && F->hasInternalLinkage())
- TFRVI = TrackedFunctionRetVals.find(F);
-
- if (TFRVI != TrackedFunctionRetVals.end()) {
- // If this is the first call to the function hit, mark its entry block
- // executable.
- if (!BBExecutable.count(F->begin()))
- MarkBlockExecutable(F->begin());
-
- CallSite::arg_iterator CAI = CS.arg_begin();
- for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
- AI != E; ++AI, ++CAI) {
- LatticeVal &IV = ValueState[AI];
- if (!IV.isOverdefined())
- mergeInValue(IV, AI, getValueState(*CAI));
- }
- }
Instruction *I = CS.getInstruction();
+
+ // The common case is that we aren't tracking the callee, either because we
+ // are not doing interprocedural analysis or the callee is indirect, or is
+ // external. Handle these cases first.
+ if (F == 0 || !F->hasInternalLinkage()) {
+CallOverdefined:
+ // Void return and not tracking callee, just bail.
+ if (I->getType() == Type::VoidTy) return;
+
+ // Otherwise, if we have a single return value case, and if the function is
+ // a declaration, maybe we can constant fold it.
+ if (!isa<StructType>(I->getType()) && F && F->isDeclaration() &&
+ canConstantFoldCallTo(F)) {
+
+ SmallVector<Constant*, 8> Operands;
+ for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
+ AI != E; ++AI) {
+ LatticeVal &State = getValueState(*AI);
+ if (State.isUndefined())
+ return; // Operands are not resolved yet.
+ else if (State.isOverdefined()) {
+ markOverdefined(I);
+ return;
+ }
+ assert(State.isConstant() && "Unknown state!");
+ Operands.push_back(State.getConstant());
+ }
+
+ // If we can constant fold this, mark the result of the call as a
+ // constant.
+ if (Constant *C = ConstantFoldCall(F, &Operands[0], Operands.size())) {
+ markConstant(I, C);
+ return;
+ }
+ }
- if (!CS.doesNotThrow() && I->getParent()->getUnwindDest())
- markEdgeExecutable(I->getParent(), I->getParent()->getUnwindDest());
-
- if (I->getType() == Type::VoidTy) return;
-
- LatticeVal &IV = ValueState[I];
- if (IV.isOverdefined()) return;
-
- // Propagate the return value of the function to the value of the instruction.
- if (TFRVI != TrackedFunctionRetVals.end()) {
- mergeInValue(IV, I, TFRVI->second);
- return;
- }
-
- if (F == 0 || !F->isDeclaration() || !canConstantFoldCallTo(F)) {
- markOverdefined(IV, I);
+ // Otherwise, we don't know anything about this call, mark it overdefined.
+ markOverdefined(I);
return;
}
- SmallVector<Constant*, 8> Operands;
- Operands.reserve(I->getNumOperands()-1);
-
- for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
- AI != E; ++AI) {
- LatticeVal &State = getValueState(*AI);
- if (State.isUndefined())
- return; // Operands are not resolved yet...
- else if (State.isOverdefined()) {
- markOverdefined(IV, I);
- return;
+ // If this is a single/zero retval case, see if we're tracking the function.
+ const StructType *RetSTy = dyn_cast<StructType>(I->getType());
+ if (RetSTy == 0) {
+ // Check to see if we're tracking this callee, if not, handle it in the
+ // common path above.
+ DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
+ if (TFRVI == TrackedRetVals.end())
+ goto CallOverdefined;
+
+ // If so, propagate the return value of the callee into this call result.
+ mergeInValue(I, TFRVI->second);
+ } else {
+ // Check to see if we're tracking this callee, if not, handle it in the
+ // common path above.
+ std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0));
+ if (TMRVI == TrackedMultipleRetVals.end())
+ goto CallOverdefined;
+
+ // If we are tracking this callee, propagate the return values of the call
+ // into this call site. We do this by walking all the getresult uses.
+ for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
+ UI != E; ++UI) {
+ GetResultInst *GRI = cast<GetResultInst>(*UI);
+ mergeInValue(GRI,
+ TrackedMultipleRetVals[std::make_pair(F, GRI->getIndex())]);
}
- assert(State.isConstant() && "Unknown state!");
- Operands.push_back(State.getConstant());
}
-
- if (Constant *C = ConstantFoldCall(F, &Operands[0], Operands.size()))
- markConstant(IV, I, C);
- else
- markOverdefined(IV, I);
+
+ // Finally, if this is the first call to the function hit, mark its entry
+ // block executable.
+ if (!BBExecutable.count(F->begin()))
+ MarkBlockExecutable(F->begin());
+
+ // Propagate information from this call site into the callee.
+ CallSite::arg_iterator CAI = CS.arg_begin();
+ for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
+ AI != E; ++AI, ++CAI) {
+ LatticeVal &IV = ValueState[AI];
+ if (!IV.isOverdefined())
+ mergeInValue(IV, AI, getValueState(*CAI));
+ }
}
AU.setPreservesCFG();
}
};
-
- char SCCP::ID = 0;
- RegisterPass<SCCP> X("sccp", "Sparse Conditional Constant Propagation");
} // end anonymous namespace
+char SCCP::ID = 0;
+static RegisterPass<SCCP>
+X("sccp", "Sparse Conditional Constant Propagation");
// createSCCPPass - This is the public interface to this file...
FunctionPass *llvm::createSCCPPass() {
// and return true if the function was modified.
//
bool SCCP::runOnFunction(Function &F) {
- DOUT << "SCCP on function '" << F.getName() << "'\n";
+ DOUT << "SCCP on function '" << F.getNameStart() << "'\n";
SCCPSolver Solver;
// Mark the first block of the function as being executable.
//
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
- if (Inst->getType() != Type::VoidTy) {
- LatticeVal &IV = Values[Inst];
- if ((IV.isConstant() || IV.isUndefined()) &&
- !isa<TerminatorInst>(Inst)) {
- Constant *Const = IV.isConstant()
- ? IV.getConstant() : UndefValue::get(Inst->getType());
- DOUT << " Constant: " << *Const << " = " << *Inst;
-
- // Replaces all of the uses of a variable with uses of the constant.
- Inst->replaceAllUsesWith(Const);
-
- // Delete the instruction.
- BB->getInstList().erase(Inst);
+ if (Inst->getType() == Type::VoidTy ||
+ isa<StructType>(Inst->getType()) ||
+ isa<TerminatorInst>(Inst))
+ continue;
+
+ LatticeVal &IV = Values[Inst];
+ if (!IV.isConstant() && !IV.isUndefined())
+ continue;
+
+ Constant *Const = IV.isConstant()
+ ? IV.getConstant() : UndefValue::get(Inst->getType());
+ DOUT << " Constant: " << *Const << " = " << *Inst;
- // Hey, we just changed something!
- MadeChanges = true;
- ++NumInstRemoved;
- }
- }
+ // Replaces all of the uses of a variable with uses of the constant.
+ Inst->replaceAllUsesWith(Const);
+
+ // Delete the instruction.
+ Inst->eraseFromParent();
+
+ // Hey, we just changed something!
+ MadeChanges = true;
+ ++NumInstRemoved;
}
}
IPSCCP() : ModulePass((intptr_t)&ID) {}
bool runOnModule(Module &M);
};
-
- char IPSCCP::ID = 0;
- RegisterPass<IPSCCP>
- Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
} // end anonymous namespace
+char IPSCCP::ID = 0;
+static RegisterPass<IPSCCP>
+Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
+
// createIPSCCPPass - This is the public interface to this file...
ModulePass *llvm::createIPSCCPPass() {
return new IPSCCP();
} else {
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
- if (Inst->getType() != Type::VoidTy) {
- LatticeVal &IV = Values[Inst];
- if (IV.isConstant() ||
- (IV.isUndefined() && !isa<TerminatorInst>(Inst))) {
- Constant *Const = IV.isConstant()
- ? IV.getConstant() : UndefValue::get(Inst->getType());
- DOUT << " Constant: " << *Const << " = " << *Inst;
-
- // Replaces all of the uses of a variable with uses of the
- // constant.
- Inst->replaceAllUsesWith(Const);
-
- // Delete the instruction.
- if (!isa<TerminatorInst>(Inst) && !isa<CallInst>(Inst))
- BB->getInstList().erase(Inst);
-
- // Hey, we just changed something!
- MadeChanges = true;
- ++IPNumInstRemoved;
- }
- }
+ if (Inst->getType() == Type::VoidTy ||
+ isa<StructType>(Inst->getType()) ||
+ isa<TerminatorInst>(Inst))
+ continue;
+
+ LatticeVal &IV = Values[Inst];
+ if (!IV.isConstant() && !IV.isUndefined())
+ continue;
+
+ Constant *Const = IV.isConstant()
+ ? IV.getConstant() : UndefValue::get(Inst->getType());
+ DOUT << " Constant: " << *Const << " = " << *Inst;
+
+ // Replaces all of the uses of a variable with uses of the
+ // constant.
+ Inst->replaceAllUsesWith(Const);
+
+ // Delete the instruction.
+ if (!isa<CallInst>(Inst))
+ Inst->eraseFromParent();
+
+ // Hey, we just changed something!
+ MadeChanges = true;
+ ++IPNumInstRemoved;
}
}
// If there are any PHI nodes in this successor, drop entries for BB now.
BasicBlock *DeadBB = BlocksToErase[i];
while (!DeadBB->use_empty()) {
- if (BasicBlock *PredBB = dyn_cast<BasicBlock>(DeadBB->use_back())) {
- PredBB->setUnwindDest(NULL);
- continue;
- }
-
Instruction *I = cast<Instruction>(DeadBB->use_back());
bool Folded = ConstantFoldTerminator(I->getParent());
if (!Folded) {
// Make this an uncond branch to the first successor.
TerminatorInst *TI = I->getParent()->getTerminator();
- new BranchInst(TI->getSuccessor(0), TI);
+ BranchInst::Create(TI->getSuccessor(0), TI);
// Remove entries in successor phi nodes to remove edges.
for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i)
// all call uses with the inferred value. This means we don't need to bother
// actually returning anything from the function. Replace all return
// instructions with return undef.
- const DenseMap<Function*, LatticeVal> &RV =Solver.getTrackedFunctionRetVals();
+ // TODO: Process multiple value ret instructions also.
+ const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(),
E = RV.end(); I != E; ++I)
if (!I->second.isOverdefined() &&
GlobalVariable *GV = I->first;
assert(!I->second.isOverdefined() &&
"Overdefined values should have been taken out of the map!");
- DOUT << "Found that GV '" << GV->getName()<< "' is constant!\n";
+ DOUT << "Found that GV '" << GV->getNameStart() << "' is constant!\n";
while (!GV->use_empty()) {
StoreInst *SI = cast<StoreInst>(GV->use_back());
SI->eraseFromParent();