/// This returns true if the block was not considered live before.
bool MarkBlockExecutable(BasicBlock *BB) {
if (!BBExecutable.insert(BB)) return false;
- DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n");
+ DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
BBWorkList.push_back(BB); // Add the block to the work list!
return true;
}
}
void markOverdefined(Value *V) {
- assert(!isa<StructType>(V->getType()) && "Should use other method");
+ assert(!V->getType()->isStructTy() && "Should use other method");
markOverdefined(ValueState[V], V);
}
//
void markConstant(LatticeVal &IV, Value *V, Constant *C) {
if (!IV.markConstant(C)) return;
- DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n');
+ DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
InstWorkList.push_back(V);
}
void markConstant(Value *V, Constant *C) {
- assert(!isa<StructType>(V->getType()) && "Should use other method");
+ assert(!V->getType()->isStructTy() && "Should use other method");
markConstant(ValueState[V], V, C);
}
void markForcedConstant(Value *V, Constant *C) {
- assert(!isa<StructType>(V->getType()) && "Should use other method");
+ assert(!V->getType()->isStructTy() && "Should use other method");
ValueState[V].markForcedConstant(C);
- DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n');
+ DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
InstWorkList.push_back(V);
}
void markOverdefined(LatticeVal &IV, Value *V) {
if (!IV.markOverdefined()) return;
- DEBUG(errs() << "markOverdefined: ";
+ DEBUG(dbgs() << "markOverdefined: ";
if (Function *F = dyn_cast<Function>(V))
- errs() << "Function '" << F->getName() << "'\n";
+ dbgs() << "Function '" << F->getName() << "'\n";
else
- errs() << *V << '\n');
+ dbgs() << *V << '\n');
// Only instructions go on the work list
OverdefinedInstWorkList.push_back(V);
}
}
void mergeInValue(Value *V, LatticeVal MergeWithV) {
- assert(!isa<StructType>(V->getType()) && "Should use other method");
+ assert(!V->getType()->isStructTy() && "Should use other method");
mergeInValue(ValueState[V], V, MergeWithV);
}
/// value. This function handles the case when the value hasn't been seen yet
/// by properly seeding constants etc.
LatticeVal &getValueState(Value *V) {
- assert(!isa<StructType>(V->getType()) && "Should use getStructValueState");
+ assert(!V->getType()->isStructTy() && "Should use getStructValueState");
std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I =
ValueState.insert(std::make_pair(V, LatticeVal()));
/// value/field pair. This function handles the case when the value hasn't
/// been seen yet by properly seeding constants etc.
LatticeVal &getStructValueState(Value *V, unsigned i) {
- assert(isa<StructType>(V->getType()) && "Should use getValueState");
+ assert(V->getType()->isStructTy() && "Should use getValueState");
assert(i < cast<StructType>(V->getType())->getNumElements() &&
"Invalid element #");
// If the destination is already executable, we just made an *edge*
// feasible that wasn't before. Revisit the PHI nodes in the block
// because they have potentially new operands.
- DEBUG(errs() << "Marking Edge Executable: " << Source->getName()
+ DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
<< " -> " << Dest->getName() << "\n");
PHINode *PN;
void visitInstruction(Instruction &I) {
// If a new instruction is added to LLVM that we don't handle.
- errs() << "SCCP: Don't know how to handle: " << I;
+ dbgs() << "SCCP: Don't know how to handle: " << I;
markAnythingOverdefined(&I); // Just in case
}
};
}
#ifndef NDEBUG
- errs() << "Unknown terminator instruction: " << TI << '\n';
+ dbgs() << "Unknown terminator instruction: " << TI << '\n';
#endif
llvm_unreachable("SCCP: Don't know how to handle this terminator!");
}
return true;
#ifndef NDEBUG
- errs() << "Unknown terminator instruction: " << *TI << '\n';
+ dbgs() << "Unknown terminator instruction: " << *TI << '\n';
#endif
llvm_unreachable(0);
}
void SCCPSolver::visitPHINode(PHINode &PN) {
// If this PN returns a struct, just mark the result overdefined.
// TODO: We could do a lot better than this if code actually uses this.
- if (isa<StructType>(PN.getType()))
+ if (PN.getType()->isStructTy())
return markAnythingOverdefined(&PN);
if (getValueState(&PN).isOverdefined()) {
Value *ResultOp = I.getOperand(0);
// If we are tracking the return value of this function, merge it in.
- if (!TrackedRetVals.empty() && !isa<StructType>(ResultOp->getType())) {
+ if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
DenseMap<Function*, LatticeVal>::iterator TFRVI =
TrackedRetVals.find(F);
if (TFRVI != TrackedRetVals.end()) {
void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
// If this returns a struct, mark all elements over defined, we don't track
// structs in structs.
- if (isa<StructType>(EVI.getType()))
+ if (EVI.getType()->isStructTy())
return markAnythingOverdefined(&EVI);
// If this is extracting from more than one level of struct, we don't know.
return markOverdefined(&EVI);
Value *AggVal = EVI.getAggregateOperand();
- unsigned i = *EVI.idx_begin();
- LatticeVal EltVal = getStructValueState(AggVal, i);
- mergeInValue(getValueState(&EVI), &EVI, EltVal);
+ if (AggVal->getType()->isStructTy()) {
+ unsigned i = *EVI.idx_begin();
+ LatticeVal EltVal = getStructValueState(AggVal, i);
+ mergeInValue(getValueState(&EVI), &EVI, EltVal);
+ } else {
+ // Otherwise, must be extracting from an array.
+ return markOverdefined(&EVI);
+ }
}
void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
}
Value *Val = IVI.getInsertedValueOperand();
- if (isa<StructType>(Val->getType()))
+ if (Val->getType()->isStructTy())
// We don't track structs in structs.
markOverdefined(getStructValueState(&IVI, i), &IVI);
else {
void SCCPSolver::visitSelectInst(SelectInst &I) {
// If this select returns a struct, just mark the result overdefined.
// TODO: We could do a lot better than this if code actually uses this.
- if (isa<StructType>(I.getType()))
+ if (I.getType()->isStructTy())
return markAnythingOverdefined(&I);
LatticeVal CondValue = getValueState(I.getCondition());
void SCCPSolver::visitStoreInst(StoreInst &SI) {
// If this store is of a struct, ignore it.
- if (isa<StructType>(SI.getOperand(0)->getType()))
+ if (SI.getOperand(0)->getType()->isStructTy())
return;
if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
// global, we can replace the load with the loaded constant value!
void SCCPSolver::visitLoadInst(LoadInst &I) {
// If this load is of a struct, just mark the result overdefined.
- if (isa<StructType>(I.getType()))
+ if (I.getType()->isStructTy())
return markAnythingOverdefined(&I);
LatticeVal PtrVal = getValueState(I.getOperand(0));
// Otherwise, if we have a single return value case, and if the function is
// a declaration, maybe we can constant fold it.
- if (F && F->isDeclaration() && !isa<StructType>(I->getType()) &&
+ if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
canConstantFoldCallTo(F)) {
SmallVector<Constant*, 8> Operands;
while (!OverdefinedInstWorkList.empty()) {
Value *I = OverdefinedInstWorkList.pop_back_val();
- DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n');
+ DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
// "I" got into the work list because it either made the transition from
// bottom to constant
while (!InstWorkList.empty()) {
Value *I = InstWorkList.pop_back_val();
- DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n');
+ DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
// "I" got into the work list because it made the transition from undef to
// constant.
// since all of its users will have already been marked as overdefined.
// Update all of the users of this instruction's value.
//
- if (isa<StructType>(I->getType()) || !getValueState(I).isOverdefined())
+ if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
UI != E; ++UI)
if (Instruction *I = dyn_cast<Instruction>(*UI))
BasicBlock *BB = BBWorkList.back();
BBWorkList.pop_back();
- DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n');
+ DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
// Notify all instructions in this basic block that they are newly
// executable.
if (!LV.isUndefined()) continue;
// No instructions using structs need disambiguation.
- if (isa<StructType>(I->getOperand(0)->getType()))
+ if (I->getOperand(0)->getType()->isStructTy())
continue;
// Get the lattice values of the first two operands for use below.
LatticeVal Op1LV;
if (I->getNumOperands() == 2) {
// No instructions using structs need disambiguation.
- if (isa<StructType>(I->getOperand(1)->getType()))
+ if (I->getOperand(1)->getType()->isStructTy())
continue;
// If this is a two-operand instruction, and if both operands are
}
static void DeleteInstructionInBlock(BasicBlock *BB) {
- DEBUG(errs() << " BasicBlock Dead:" << *BB);
+ DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
++NumDeadBlocks;
// Delete the instructions backwards, as it has a reduced likelihood of
// and return true if the function was modified.
//
bool SCCP::runOnFunction(Function &F) {
- DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n");
+ DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
SCCPSolver Solver(getAnalysisIfAvailable<TargetData>());
// Mark the first block of the function as being executable.
bool ResolvedUndefs = true;
while (ResolvedUndefs) {
Solver.Solve();
- DEBUG(errs() << "RESOLVING UNDEFs\n");
+ DEBUG(dbgs() << "RESOLVING UNDEFs\n");
ResolvedUndefs = Solver.ResolvedUndefsIn(F);
}
continue;
// TODO: Reconstruct structs from their elements.
- if (isa<StructType>(Inst->getType()))
+ if (Inst->getType()->isStructTy())
continue;
LatticeVal IV = Solver.getLatticeValueFor(Inst);
Constant *Const = IV.isConstant()
? IV.getConstant() : UndefValue::get(Inst->getType());
- DEBUG(errs() << " Constant: " << *Const << " = " << *Inst);
+ DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst);
// Replaces all of the uses of a variable with uses of the constant.
Inst->replaceAllUsesWith(Const);
}
-static bool AddressIsTaken(GlobalValue *GV) {
+static bool AddressIsTaken(const GlobalValue *GV) {
// Delete any dead constantexpr klingons.
GV->removeDeadConstantUsers();
- for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
- UI != E; ++UI)
- if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
+ for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end();
+ UI != E; ++UI) {
+ const User *U = *UI;
+ if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
if (SI->getOperand(0) == GV || SI->isVolatile())
return true; // Storing addr of GV.
- } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
+ } else if (isa<InvokeInst>(U) || isa<CallInst>(U)) {
// Make sure we are calling the function, not passing the address.
- if (UI.getOperandNo() != 0)
+ ImmutableCallSite CS(cast<Instruction>(U));
+ if (!CS.isCallee(UI))
return true;
- } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
+ } else if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
if (LI->isVolatile())
return true;
- } else if (isa<BlockAddress>(*UI)) {
+ } else if (isa<BlockAddress>(U)) {
// blockaddress doesn't take the address of the function, it takes addr
// of label.
} else {
return true;
}
+ }
return false;
}
while (ResolvedUndefs) {
Solver.Solve();
- DEBUG(errs() << "RESOLVING UNDEFS\n");
+ DEBUG(dbgs() << "RESOLVING UNDEFS\n");
ResolvedUndefs = false;
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
ResolvedUndefs |= Solver.ResolvedUndefsIn(*F);
if (Solver.isBlockExecutable(F->begin())) {
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
AI != E; ++AI) {
- if (AI->use_empty() || isa<StructType>(AI->getType())) continue;
+ if (AI->use_empty() || AI->getType()->isStructTy()) continue;
// TODO: Could use getStructLatticeValueFor to find out if the entire
// result is a constant and replace it entirely if so.
Constant *CST = IV.isConstant() ?
IV.getConstant() : UndefValue::get(AI->getType());
- DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n");
+ DEBUG(dbgs() << "*** Arg " << *AI << " = " << *CST <<"\n");
// Replaces all of the uses of a variable with uses of the
// constant.
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
Instruction *Inst = BI++;
- if (Inst->getType()->isVoidTy() || isa<StructType>(Inst->getType()))
+ if (Inst->getType()->isVoidTy() || Inst->getType()->isStructTy())
continue;
// TODO: Could use getStructLatticeValueFor to find out if the entire
Constant *Const = IV.isConstant()
? IV.getConstant() : UndefValue::get(Inst->getType());
- DEBUG(errs() << " Constant: " << *Const << " = " << *Inst);
+ DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst);
// Replaces all of the uses of a variable with uses of the
// constant.
for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
// If there are any PHI nodes in this successor, drop entries for BB now.
BasicBlock *DeadBB = BlocksToErase[i];
- while (!DeadBB->use_empty()) {
- Instruction *I = cast<Instruction>(DeadBB->use_back());
+ for (Value::use_iterator UI = DeadBB->use_begin(), UE = DeadBB->use_end();
+ UI != UE; ) {
+ // Grab the user and then increment the iterator early, as the user
+ // will be deleted. Step past all adjacent uses from the same user.
+ Instruction *I = dyn_cast<Instruction>(*UI);
+ do { ++UI; } while (UI != UE && *UI == I);
+
+ // Ignore blockaddress users; BasicBlock's dtor will handle them.
+ if (!I) continue;
+
bool Folded = ConstantFoldTerminator(I->getParent());
if (!Folded) {
// The constant folder may not have been able to fold the terminator
// 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.
+ //
+ // Do this in two stages: first identify the functions we should process, then
+ // actually zap their returns. This is important because we can only do this
+ // if the address of the function isn't taken. In cases where a return is the
+ // last use of a function, the order of processing functions would affect
+ // whether other functions are optimizable.
+ SmallVector<ReturnInst*, 8> ReturnsToZap;
+
// TODO: Process multiple value ret instructions also.
const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(),
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
if (!isa<UndefValue>(RI->getOperand(0)))
- RI->setOperand(0, UndefValue::get(F->getReturnType()));
+ ReturnsToZap.push_back(RI);
+ }
+
+ // Zap all returns which we've identified as zap to change.
+ for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
+ Function *F = ReturnsToZap[i]->getParent()->getParent();
+ ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
}
// If we infered constant or undef values for globals variables, we can delete
GlobalVariable *GV = I->first;
assert(!I->second.isOverdefined() &&
"Overdefined values should have been taken out of the map!");
- DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n");
+ DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n");
while (!GV->use_empty()) {
StoreInst *SI = cast<StoreInst>(GV->use_back());
SI->eraseFromParent();