#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/MallocHelper.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
-#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/InstVisitor.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
/// LatticeVal class - This class represents the different lattice values that
/// an LLVM value may occupy. It is a simple class with value semantics.
///
-class VISIBILITY_HIDDEN LatticeVal {
+class LatticeVal {
enum {
/// undefined - This LLVM Value has no known value yet.
undefined,
}
};
-/// LatticeValIndex - LatticeVal and associated Index. This is used
-/// to track individual operand Lattice values for multi value ret instructions.
-class VISIBILITY_HIDDEN LatticeValIndexed {
- public:
- LatticeValIndexed(unsigned I = 0) { Index = I; }
- LatticeVal &getLatticeVal() { return LV; }
- unsigned getIndex() const { return Index; }
-
- void setLatticeVal(LatticeVal &L) { LV = L; }
- void setIndex(unsigned I) { Index = I; }
-
- private:
- LatticeVal LV;
- unsigned Index;
-};
//===----------------------------------------------------------------------===//
//
/// SCCPSolver - This class is a general purpose solver for Sparse Conditional
/// Constant Propagation.
///
class SCCPSolver : public InstVisitor<SCCPSolver> {
- SmallSet<BasicBlock*, 16> BBExecutable;// The basic blocks that are executable
+ LLVMContext *Context;
+ DenseSet<BasicBlock*> BBExecutable;// The basic blocks that are executable
std::map<Value*, LatticeVal> ValueState; // The state each value is in.
/// GlobalValue - If we are tracking any values for the contents of a global
/// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
/// that return multiple values.
- std::multimap<Function*, LatticeValIndexed> TrackedMultipleRetVals;
+ DenseMap<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
// By having a separate worklist, we accomplish this because everything
// possibly overdefined will become overdefined at the soonest possible
// point.
- std::vector<Value*> OverdefinedInstWorkList;
- std::vector<Value*> InstWorkList;
+ SmallVector<Value*, 64> OverdefinedInstWorkList;
+ SmallVector<Value*, 64> InstWorkList;
- std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
+ SmallVector<BasicBlock*, 64> BBWorkList; // The BasicBlock work list
/// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
/// overdefined, despite the fact that the PHI node is overdefined.
/// KnownFeasibleEdges - Entries in this set are edges which have already had
/// PHI nodes retriggered.
- typedef std::pair<BasicBlock*,BasicBlock*> Edge;
- std::set<Edge> KnownFeasibleEdges;
+ typedef std::pair<BasicBlock*, BasicBlock*> Edge;
+ DenseSet<Edge> KnownFeasibleEdges;
public:
+ void setContext(LLVMContext *C) { Context = C; }
/// 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";
+ DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n");
BBExecutable.insert(BB); // Basic block is executable!
BBWorkList.push_back(BB); // Add the block to the work list!
}
/// and out of the specified function (which cannot have its address taken),
/// this method must be called.
void AddTrackedFunction(Function *F) {
- assert(F->hasInternalLinkage() && "Can only track internal functions!");
+ assert(F->hasLocalLinkage() && "Can only track internal functions!");
// Add an entry, F -> undef.
if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) {
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
- TrackedMultipleRetVals.insert(std::pair<Function *, LatticeValIndexed>
- (F, LatticeValIndexed(i)));
- }
- else
- TrackedRetVals[F];
+ 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.
/// should be rerun.
bool ResolvedUndefsIn(Function &F);
- /// getExecutableBlocks - Once we have solved for constants, return the set of
- /// blocks that is known to be executable.
- SmallSet<BasicBlock*, 16> &getExecutableBlocks() {
- return BBExecutable;
+ bool isBlockExecutable(BasicBlock *BB) const {
+ return BBExecutable.count(BB);
}
/// getValueMapping - Once we have solved for constants, return the mapping of
//
inline void markConstant(LatticeVal &IV, Value *V, Constant *C) {
if (IV.markConstant(C)) {
- DOUT << "markConstant: " << *C << ": " << *V;
+ DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n');
InstWorkList.push_back(V);
}
}
inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) {
IV.markForcedConstant(C);
- DOUT << "markForcedConstant: " << *C << ": " << *V;
+ DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n');
InstWorkList.push_back(V);
}
// 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: ";
+ DEBUG(errs() << "markOverdefined: ";
if (Function *F = dyn_cast<Function>(V))
- DOUT << "Function '" << F->getName() << "'\n";
+ errs() << "Function '" << F->getName() << "'\n";
else
- DOUT << *V);
+ errs() << *V << '\n');
// Only instructions go on the work list
OverdefinedInstWorkList.push_back(V);
}
return; // This edge is already known to be executable!
if (BBExecutable.count(Dest)) {
- DOUT << "Marking Edge Executable: " << Source->getName()
- << " -> " << Dest->getName() << "\n";
+ DEBUG(errs() << "Marking Edge Executable: " << Source->getName()
+ << " -> " << Dest->getName() << "\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);
void visitExtractElementInst(ExtractElementInst &I);
void visitInsertElementInst(InsertElementInst &I);
void visitShuffleVectorInst(ShuffleVectorInst &I);
+ void visitExtractValueInst(ExtractValueInst &EVI);
+ void visitInsertValueInst(InsertValueInst &IVI);
// Instructions that cannot be folded away...
void visitStoreInst (Instruction &I);
void visitLoadInst (LoadInst &I);
void visitGetElementPtrInst(GetElementPtrInst &I);
- void visitCallInst (CallInst &I) { visitCallSite(CallSite::get(&I)); }
+ void visitCallInst (CallInst &I) {
+ if (isMalloc(&I))
+ markOverdefined(&I);
+ else
+ visitCallSite(CallSite::get(&I));
+ }
void visitInvokeInst (InvokeInst &II) {
visitCallSite(CallSite::get(&II));
visitTerminatorInst(II);
void visitInstruction(Instruction &I) {
// If a new instruction is added to LLVM that we don't handle...
- cerr << "SCCP: Don't know how to handle: " << I;
+ errs() << "SCCP: Don't know how to handle: " << I;
markOverdefined(&I); // Just in case
}
};
Succs[0] = Succs[1] = true;
} else if (BCValue.isConstant()) {
// Constant condition variables mean the branch can only go a single way
- Succs[BCValue.getConstant() == ConstantInt::getFalse()] = true;
+ Succs[BCValue.getConstant() == ConstantInt::getFalse(*Context)] = true;
}
}
} else if (isa<InvokeInst>(&TI)) {
(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!");
+ llvm_unreachable("SCCP: Don't know how to handle this terminator!");
}
}
// Constant condition variables mean the branch can only go a single way
return BI->getSuccessor(BCValue.getConstant() ==
- ConstantInt::getFalse()) == To;
+ ConstantInt::getFalse(*Context)) == To;
}
return false;
}
}
return false;
} else {
- cerr << "Unknown terminator instruction: " << *TI;
- abort();
+#ifndef NDEBUG
+ errs() << "Unknown terminator instruction: " << *TI << '\n';
+#endif
+ llvm_unreachable(0);
}
}
if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
if (IV.isOverdefined()) { // PHI node becomes overdefined!
- markOverdefined(PNIV, &PN);
+ markOverdefined(&PN);
return;
}
// Yes there is. This means the PHI node is not constant.
// You must be overdefined poor PHI.
//
- markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined
+ markOverdefined(&PN); // The PHI node now becomes overdefined
return; // I'm done analyzing you
}
}
// this is the case, the PHI remains undefined.
//
if (OperandVal)
- markConstant(PNIV, &PN, OperandVal); // Acquire operand value
+ markConstant(&PN, OperandVal); // Acquire operand value
}
void SCCPSolver::visitReturnInst(ReturnInst &I) {
Function *F = I.getParent()->getParent();
// If we are tracking the return value of this function, merge it in.
- if (!F->hasInternalLinkage())
+ if (!F->hasLocalLinkage())
return;
- if (!TrackedRetVals.empty()) {
+ if (!TrackedRetVals.empty() && I.getNumOperands() == 1) {
DenseMap<Function*, LatticeVal>::iterator TFRVI =
TrackedRetVals.find(F);
if (TFRVI != TrackedRetVals.end() &&
}
}
- // Handle function that returns multiple values.
- std::multimap<Function*, LatticeValIndexed>::iterator It, E;
- tie(It, E) = TrackedMultipleRetVals.equal_range(F);
- if (It != E) {
- for (; It != E; ++It) {
- LatticeValIndexed &LV = It->second;
- unsigned Idx = LV.getIndex();
- Value *V = I.getOperand(Idx);
- mergeInValue(LV.getLatticeVal(), V, getValueState(V));
+ // Handle functions that return multiple values.
+ if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) {
+ for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
+ DenseMap<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)));
+ }
+ } else if (!TrackedMultipleRetVals.empty() &&
+ I.getNumOperands() == 1 &&
+ isa<StructType>(I.getOperand(0)->getType())) {
+ for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes();
+ i != e; ++i) {
+ DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ It = TrackedMultipleRetVals.find(std::make_pair(F, i));
+ if (It == TrackedMultipleRetVals.end()) break;
+ if (Value *Val = FindInsertedValue(I.getOperand(0), i, I.getContext()))
+ mergeInValue(It->second, F, getValueState(Val));
}
}
}
VState.getConstant(), I.getType()));
}
-void SCCPSolver::visitGetResultInst(GetResultInst &GRI) {
- unsigned Idx = GRI.getIndex();
- Value *Aggr = GRI.getOperand(0);
- Function *F = NULL;
+void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
+ Value *Aggr = EVI.getAggregateOperand();
+
+ // If the operand to the extractvalue is an undef, the result is undef.
+ if (isa<UndefValue>(Aggr))
+ return;
+
+ // Currently only handle single-index extractvalues.
+ if (EVI.getNumIndices() != 1) {
+ markOverdefined(&EVI);
+ return;
+ }
+
+ Function *F = 0;
if (CallInst *CI = dyn_cast<CallInst>(Aggr))
F = CI->getCalledFunction();
else if (InvokeInst *II = dyn_cast<InvokeInst>(Aggr))
F = II->getCalledFunction();
- if (!F)
+ // TODO: If IPSCCP resolves the callee of this function, we could propagate a
+ // result back!
+ if (F == 0 || TrackedMultipleRetVals.empty()) {
+ markOverdefined(&EVI);
+ return;
+ }
+
+ // See if we are tracking the result of the callee. If not tracking this
+ // function (for example, it is a declaration) just move to overdefined.
+ if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) {
+ markOverdefined(&EVI);
return;
+ }
+
+ // Otherwise, the value will be merged in here as a result of CallSite
+ // handling.
+}
+
+void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
+ Value *Aggr = IVI.getAggregateOperand();
+ Value *Val = IVI.getInsertedValueOperand();
- std::multimap<Function*, LatticeValIndexed>::iterator It, E;
- tie(It, E) = TrackedMultipleRetVals.equal_range(F);
- if (It == E)
+ // If the operands to the insertvalue are undef, the result is undef.
+ if (isa<UndefValue>(Aggr) && isa<UndefValue>(Val))
return;
- for (; It != E; ++It) {
- LatticeValIndexed &LIV = It->second;
- if (LIV.getIndex() == Idx) {
- mergeInValue(&GRI, LIV.getLatticeVal());
+ // Currently only handle single-index insertvalues.
+ if (IVI.getNumIndices() != 1) {
+ markOverdefined(&IVI);
+ return;
+ }
+
+ // Currently only handle insertvalue instructions that are in a single-use
+ // chain that builds up a return value.
+ for (const InsertValueInst *TmpIVI = &IVI; ; ) {
+ if (!TmpIVI->hasOneUse()) {
+ markOverdefined(&IVI);
+ return;
+ }
+ const Value *V = *TmpIVI->use_begin();
+ if (isa<ReturnInst>(V))
+ break;
+ TmpIVI = dyn_cast<InsertValueInst>(V);
+ if (!TmpIVI) {
+ markOverdefined(&IVI);
+ return;
}
}
+
+ // See if we are tracking the result of the callee.
+ Function *F = IVI.getParent()->getParent();
+ DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin()));
+
+ // Merge in the inserted member value.
+ if (It != TrackedMultipleRetVals.end())
+ mergeInValue(It->second, F, getValueState(Val));
+
+ // Mark the aggregate result of the IVI overdefined; any tracking that we do
+ // will be done on the individual member values.
+ markOverdefined(&IVI);
}
void SCCPSolver::visitSelectInst(SelectInst &I) {
if (I.getOpcode() == Instruction::And)
markConstant(IV, &I, Constant::getNullValue(I.getType()));
else if (const VectorType *PT = dyn_cast<VectorType>(I.getType()))
- markConstant(IV, &I, ConstantVector::getAllOnesValue(PT));
+ markConstant(IV, &I, Constant::getAllOnesValue(PT));
else
- markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType()));
+ markConstant(IV, &I,
+ Constant::getAllOnesValue(I.getType()));
return;
} else {
if (I.getOpcode() == Instruction::And) {
Result.markOverdefined();
break; // Cannot fold this operation over the PHI nodes!
} else if (In1.isConstant() && In2.isConstant()) {
- Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
+ Constant *V =
+ ConstantExpr::get(I.getOpcode(), In1.getConstant(),
In2.getConstant());
if (Result.isUndefined())
Result.markConstant(V);
markOverdefined(IV, &I);
} else if (V1State.isConstant() && V2State.isConstant()) {
- markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
+ markConstant(IV, &I,
+ ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
V2State.getConstant()));
}
}
if (PtrVal.isConstant() && !I.isVolatile()) {
Value *Ptr = PtrVal.getConstant();
// TODO: Consider a target hook for valid address spaces for this xform.
- if (isa<ConstantPointerNull>(Ptr) &&
- cast<PointerType>(Ptr->getType())->getAddressSpace() == 0) {
+ if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0) {
// load null -> null
markConstant(IV, &I, Constant::getNullValue(I.getType()));
return;
// Transform load (constant global) into the value loaded.
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
if (GV->isConstant()) {
- if (!GV->isDeclaration()) {
+ if (GV->hasDefinitiveInitializer()) {
markConstant(IV, &I, GV->getInitializer());
return;
}
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
if (CE->getOpcode() == Instruction::GetElementPtr)
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
- if (GV->isConstant() && !GV->isDeclaration())
+ if (GV->isConstant() && GV->hasDefinitiveInitializer())
if (Constant *V =
- ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) {
+ ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE,
+ *Context)) {
markConstant(IV, &I, V);
return;
}
void SCCPSolver::visitCallSite(CallSite CS) {
Function *F = CS.getCalledFunction();
-
- DenseMap<Function*, LatticeVal>::iterator TFRVI =TrackedRetVals.end();
- // If we are tracking this function, we must make sure to bind arguments as
- // appropriate.
- bool FirstCall = false;
- if (F && F->hasInternalLinkage()) {
- TFRVI = TrackedRetVals.find(F);
- if (TFRVI != TrackedRetVals.end())
- FirstCall = true;
- else {
- std::multimap<Function*, LatticeValIndexed>::iterator It, E;
- tie(It, E) = TrackedMultipleRetVals.equal_range(F);
- if (It != E)
- FirstCall = true;
- }
- }
-
- if (FirstCall) {
- // If this is the first call to the function hit, mark its entry block
- // executable.
- if (!BBExecutable.count(F->begin()))
- MarkBlockExecutable(F->begin());
+ 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->hasLocalLinkage()) {
+CallOverdefined:
+ // Void return and not tracking callee, just bail.
+ if (I->getType() == Type::getVoidTy(I->getContext())) return;
- 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));
+ // 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.data(), Operands.size())) {
+ markConstant(I, C);
+ return;
+ }
}
- }
- Instruction *I = CS.getInstruction();
-
- 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 single return value of the function to the value of the
- // instruction.
- if (TFRVI != TrackedRetVals.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.
+ DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
+ if (TFRVI != TrackedRetVals.end()) {
+ // If so, propagate the return value of the callee into this call result.
+ mergeInValue(I, TFRVI->second);
+ } else if (isa<StructType>(I->getType())) {
+ // Check to see if we're tracking this callee, if not, handle it in the
+ // common path above.
+ DenseMap<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 uses. Single-index
+ // ExtractValueInst uses can be tracked; anything more complicated is
+ // currently handled conservatively.
+ for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
+ UI != E; ++UI) {
+ if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(*UI)) {
+ if (EVI->getNumIndices() == 1) {
+ mergeInValue(EVI,
+ TrackedMultipleRetVals[std::make_pair(F, *EVI->idx_begin())]);
+ continue;
+ }
+ }
+ // The aggregate value is used in a way not handled here. Assume nothing.
+ markOverdefined(*UI);
}
- assert(State.isConstant() && "Unknown state!");
- Operands.push_back(State.getConstant());
+ } else {
+ // Otherwise we're not tracking this callee, so handle it in the
+ // common path above.
+ goto CallOverdefined;
+ }
+
+ // 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));
}
-
- if (Constant *C = ConstantFoldCall(F, &Operands[0], Operands.size()))
- markConstant(IV, I, C);
- else
- markOverdefined(IV, I);
}
Value *I = OverdefinedInstWorkList.back();
OverdefinedInstWorkList.pop_back();
- DOUT << "\nPopped off OI-WL: " << *I;
+ DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n');
// "I" got into the work list because it either made the transition from
// bottom to constant
Value *I = InstWorkList.back();
InstWorkList.pop_back();
- DOUT << "\nPopped off I-WL: " << *I;
+ DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n');
// "I" got into the work list because it either made the transition from
// bottom to constant
BasicBlock *BB = BBWorkList.back();
BBWorkList.pop_back();
- DOUT << "\nPopped off BBWL: " << *BB;
+ DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n');
// Notify all instructions in this basic block that they are newly
// executable.
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
// Look for instructions which produce undef values.
- if (I->getType() == Type::VoidTy) continue;
+ if (I->getType() == Type::getVoidTy(F.getContext())) continue;
LatticeVal &LV = getValueState(I);
if (!LV.isUndefined()) continue;
case Instruction::Or:
// undef | X -> -1. X could be -1.
if (const VectorType *PTy = dyn_cast<VectorType>(ITy))
- markForcedConstant(LV, I, ConstantVector::getAllOnesValue(PTy));
+ markForcedConstant(LV, I,
+ Constant::getAllOnesValue(PTy));
else
- markForcedConstant(LV, I, ConstantInt::getAllOnesValue(ITy));
+ markForcedConstant(LV, I, Constant::getAllOnesValue(ITy));
return true;
case Instruction::SDiv:
else
markOverdefined(LV, I);
return true;
+ case Instruction::Call:
+ // If a call has an undef result, it is because it is constant foldable
+ // but one of the inputs was undef. Just force the result to
+ // overdefined.
+ markOverdefined(LV, I);
+ return true;
}
}
if (!getValueState(BI->getCondition()).isUndefined())
continue;
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+ if (SI->getNumSuccessors()<2) // no cases
+ continue;
if (!getValueState(SI->getCondition()).isUndefined())
continue;
} else {
// as undef, then further analysis could think the undef went another way
// leading to an inconsistent set of conclusions.
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
- BI->setCondition(ConstantInt::getFalse());
+ BI->setCondition(ConstantInt::getFalse(*Context));
} else {
SwitchInst *SI = cast<SwitchInst>(TI);
SI->setCondition(SI->getCaseValue(1));
/// SCCP Class - This class uses the SCCPSolver to implement a per-function
/// Sparse Conditional Constant Propagator.
///
- struct VISIBILITY_HIDDEN SCCP : public FunctionPass {
+ struct SCCP : public FunctionPass {
static char ID; // Pass identification, replacement for typeid
- SCCP() : FunctionPass((intptr_t)&ID) {}
+ SCCP() : FunctionPass(&ID) {}
// runOnFunction - Run the Sparse Conditional Constant Propagation
// algorithm, and return true if the function was modified.
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";
+ DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n");
SCCPSolver Solver;
+ Solver.setContext(&F.getContext());
// Mark the first block of the function as being executable.
Solver.MarkBlockExecutable(F.begin());
bool ResolvedUndefs = true;
while (ResolvedUndefs) {
Solver.Solve();
- DOUT << "RESOLVING UNDEFs\n";
+ DEBUG(errs() << "RESOLVING UNDEFs\n");
ResolvedUndefs = Solver.ResolvedUndefsIn(F);
}
// delete their contents now. Note that we cannot actually delete the blocks,
// as we cannot modify the CFG of the function.
//
- SmallSet<BasicBlock*, 16> &ExecutableBBs = Solver.getExecutableBlocks();
- SmallVector<Instruction*, 32> Insts;
+ SmallVector<Instruction*, 512> Insts;
std::map<Value*, LatticeVal> &Values = Solver.getValueMapping();
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
- if (!ExecutableBBs.count(BB)) {
- DOUT << " BasicBlock Dead:" << *BB;
+ if (!Solver.isBlockExecutable(BB)) {
+ DEBUG(errs() << " BasicBlock Dead:" << *BB);
++NumDeadBlocks;
// Delete the instructions backwards, as it has a reduced likelihood of
//
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::getVoidTy(F.getContext()) ||
+ isa<TerminatorInst>(Inst))
+ continue;
+
+ LatticeVal &IV = Values[Inst];
+ if (!IV.isConstant() && !IV.isUndefined())
+ continue;
+
+ Constant *Const = IV.isConstant()
+ ? IV.getConstant() : UndefValue::get(Inst->getType());
+ DEBUG(errs() << " 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 Class - This class implements interprocedural Sparse Conditional
/// Constant Propagation.
///
- struct VISIBILITY_HIDDEN IPSCCP : public ModulePass {
+ struct IPSCCP : public ModulePass {
static char ID;
- IPSCCP() : ModulePass((intptr_t)&ID) {}
+ IPSCCP() : ModulePass(&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 if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
// Make sure we are calling the function, not passing the address.
CallSite CS = CallSite::get(cast<Instruction>(*UI));
- for (CallSite::arg_iterator AI = CS.arg_begin(),
- E = CS.arg_end(); AI != E; ++AI)
- if (*AI == GV)
- return true;
+ if (CS.hasArgument(GV))
+ return true;
} else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
if (LI->isVolatile())
return true;
}
bool IPSCCP::runOnModule(Module &M) {
+ LLVMContext *Context = &M.getContext();
+
SCCPSolver Solver;
+ Solver.setContext(Context);
// Loop over all functions, marking arguments to those with their addresses
// taken or that are external as overdefined.
//
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
- if (!F->hasInternalLinkage() || AddressIsTaken(F)) {
+ if (!F->hasLocalLinkage() || AddressIsTaken(F)) {
if (!F->isDeclaration())
Solver.MarkBlockExecutable(F->begin());
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
// their addresses taken, we can propagate constants through them.
for (Module::global_iterator G = M.global_begin(), E = M.global_end();
G != E; ++G)
- if (!G->isConstant() && G->hasInternalLinkage() && !AddressIsTaken(G))
+ if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G))
Solver.TrackValueOfGlobalVariable(G);
// Solve for constants.
while (ResolvedUndefs) {
Solver.Solve();
- DOUT << "RESOLVING UNDEFS\n";
+ DEBUG(errs() << "RESOLVING UNDEFS\n");
ResolvedUndefs = false;
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
ResolvedUndefs |= Solver.ResolvedUndefsIn(*F);
// Iterate over all of the instructions in the module, replacing them with
// constants if we have found them to be of constant values.
//
- SmallSet<BasicBlock*, 16> &ExecutableBBs = Solver.getExecutableBlocks();
- SmallVector<Instruction*, 32> Insts;
- SmallVector<BasicBlock*, 32> BlocksToErase;
+ SmallVector<Instruction*, 512> Insts;
+ SmallVector<BasicBlock*, 512> BlocksToErase;
std::map<Value*, LatticeVal> &Values = Solver.getValueMapping();
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
if (IV.isConstant() || IV.isUndefined()) {
Constant *CST = IV.isConstant() ?
IV.getConstant() : UndefValue::get(AI->getType());
- DOUT << "*** Arg " << *AI << " = " << *CST <<"\n";
+ DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n");
// Replaces all of the uses of a variable with uses of the
// constant.
}
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
- if (!ExecutableBBs.count(BB)) {
- DOUT << " BasicBlock Dead:" << *BB;
+ if (!Solver.isBlockExecutable(BB)) {
+ DEBUG(errs() << " BasicBlock Dead:" << *BB);
++IPNumDeadBlocks;
// Delete the instructions backwards, as it has a reduced likelihood of
if (&*BB != &F->front())
BlocksToErase.push_back(BB);
else
- new UnreachableInst(BB);
+ new UnreachableInst(M.getContext(), BB);
} 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::getVoidTy(M.getContext()))
+ continue;
+
+ LatticeVal &IV = Values[Inst];
+ if (!IV.isConstant() && !IV.isUndefined())
+ continue;
+
+ Constant *Const = IV.isConstant()
+ ? IV.getConstant() : UndefValue::get(Inst->getType());
+ DEBUG(errs() << " 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) && !isa<TerminatorInst>(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) {
// The constant folder may not have been able to fold the terminator
// if this is a branch or switch on undef. Fold it manually as a
// branch to the first successor.
+#ifndef NDEBUG
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) &&
"Branch should be foldable!");
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold");
} else {
- assert(0 && "Didn't fold away reference to block!");
+ llvm_unreachable("Didn't fold away reference to block!");
}
+#endif
// Make this an uncond branch to the first successor.
TerminatorInst *TI = I->getParent()->getTerminator();
for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(),
E = RV.end(); I != E; ++I)
if (!I->second.isOverdefined() &&
- I->first->getReturnType() != Type::VoidTy) {
+ I->first->getReturnType() != Type::getVoidTy(M.getContext())) {
Function *F = I->first;
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
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";
+ DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n");
while (!GV->use_empty()) {
StoreInst *SI = cast<StoreInst>(GV->use_back());
SI->eraseFromParent();