#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Compiler.h"
/// 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!
}
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);
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);
(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!");
}
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) {
+ std::map<std::pair<Function*, unsigned>, LatticeVal>::iterator
+ It = TrackedMultipleRetVals.find(std::make_pair(F, i));
+ if (It == TrackedMultipleRetVals.end()) break;
+ Value *Val = FindInsertedValue(I.getOperand(0), i);
+ mergeInValue(It->second, F, getValueState(Val));
+ }
}
}
VState.getConstant(), I.getType()));
}
-void SCCPSolver::visitGetResultInst(GetResultInst &GRI) {
- Value *Aggr = GRI.getOperand(0);
+void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
+ Value *Aggr = EVI.getAggregateOperand();
- // If the operand to the getresult is an undef, the result is undef.
+ // 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;
+ Function *F = 0;
if (CallInst *CI = dyn_cast<CallInst>(Aggr))
F = CI->getCalledFunction();
- else
- F = cast<InvokeInst>(Aggr)->getCalledFunction();
+ else if (InvokeInst *II = dyn_cast<InvokeInst>(Aggr))
+ F = II->getCalledFunction();
// TODO: If IPSCCP resolves the callee of this function, we could propagate a
// result back!
if (F == 0 || TrackedMultipleRetVals.empty()) {
- markOverdefined(&GRI);
+ markOverdefined(&EVI);
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()));
+ It = TrackedMultipleRetVals.find(std::make_pair(F, *EVI.idx_begin()));
// If not tracking this function (for example, it is a declaration) just move
// to overdefined.
if (It == TrackedMultipleRetVals.end()) {
- markOverdefined(&GRI);
+ markOverdefined(&EVI);
return;
}
// handling.
}
+void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
+ Value *Aggr = IVI.getAggregateOperand();
+ Value *Val = IVI.getInsertedValueOperand();
+
+ // If the operands to the insertvalue are undef, the result is undef.
+ if (isa<UndefValue>(Aggr) && isa<UndefValue>(Val))
+ return;
+
+ // 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();
+ std::map<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) {
LatticeVal &CondValue = getValueState(I.getCondition());
if (CondValue.isUndefined())
}
// 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;
-
+ 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 {
+ } else if (isa<StructType>(I->getType())) {
// 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
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.
+ // 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) {
- GetResultInst *GRI = cast<GetResultInst>(*UI);
- mergeInValue(GRI,
- TrackedMultipleRetVals[std::make_pair(F, GRI->getIndex())]);
+ 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);
}
+ } 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
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 {
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 ||
- isa<StructType>(Inst->getType()) ||
isa<TerminatorInst>(Inst))
continue;
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();
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
if (Inst->getType() == Type::VoidTy ||
- isa<StructType>(Inst->getType()) ||
isa<TerminatorInst>(Inst))
continue;
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();