X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSCCP.cpp;h=dcb657cc1f187a1de033d2b9ab5b231caaf913c3;hp=977827841d9e81524b8c9f2227b2901d0ddbfb0c;hb=d13db2c59cc94162d6cf0a04187d408bfef6d4a7;hpb=6a2392131e2e5b8c4123d69cc959831b4fe719ca diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 977827841d9..dcb657cc1f1 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -218,7 +218,7 @@ public: /// 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; } @@ -295,7 +295,7 @@ public: } void markOverdefined(Value *V) { - assert(!isa(V->getType()) && "Should use other method"); + assert(!V->getType()->isStructTy() && "Should use other method"); markOverdefined(ValueState[V], V); } @@ -316,20 +316,27 @@ private: // void markConstant(LatticeVal &IV, Value *V, Constant *C) { if (!IV.markConstant(C)) return; - DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n'); - InstWorkList.push_back(V); + DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); + if (IV.isOverdefined()) + OverdefinedInstWorkList.push_back(V); + else + InstWorkList.push_back(V); } void markConstant(Value *V, Constant *C) { - assert(!isa(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(V->getType()) && "Should use other method"); - ValueState[V].markForcedConstant(C); - DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n'); - InstWorkList.push_back(V); + assert(!V->getType()->isStructTy() && "Should use other method"); + LatticeVal &IV = ValueState[V]; + IV.markForcedConstant(C); + DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); + if (IV.isOverdefined()) + OverdefinedInstWorkList.push_back(V); + else + InstWorkList.push_back(V); } @@ -339,11 +346,11 @@ private: void markOverdefined(LatticeVal &IV, Value *V) { if (!IV.markOverdefined()) return; - DEBUG(errs() << "markOverdefined: "; + DEBUG(dbgs() << "markOverdefined: "; if (Function *F = dyn_cast(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); } @@ -360,7 +367,7 @@ private: } void mergeInValue(Value *V, LatticeVal MergeWithV) { - assert(!isa(V->getType()) && "Should use other method"); + assert(!V->getType()->isStructTy() && "Should use other method"); mergeInValue(ValueState[V], V, MergeWithV); } @@ -369,7 +376,7 @@ private: /// 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(V->getType()) && "Should use getStructValueState"); + assert(!V->getType()->isStructTy() && "Should use getStructValueState"); std::pair::iterator, bool> I = ValueState.insert(std::make_pair(V, LatticeVal())); @@ -392,7 +399,7 @@ private: /// 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(V->getType()) && "Should use getValueState"); + assert(V->getType()->isStructTy() && "Should use getValueState"); assert(i < cast(V->getType())->getNumElements() && "Invalid element #"); @@ -431,7 +438,7 @@ private: // 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; @@ -516,7 +523,7 @@ private: 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 } }; @@ -580,7 +587,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, } #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!"); } @@ -640,7 +647,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { return true; #ifndef NDEBUG - errs() << "Unknown terminator instruction: " << *TI << '\n'; + dbgs() << "Unknown terminator instruction: " << *TI << '\n'; #endif llvm_unreachable(0); } @@ -666,7 +673,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 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(PN.getType())) + if (PN.getType()->isStructTy()) return markAnythingOverdefined(&PN); if (getValueState(&PN).isOverdefined()) { @@ -742,7 +749,7 @@ void SCCPSolver::visitReturnInst(ReturnInst &I) { Value *ResultOp = I.getOperand(0); // If we are tracking the return value of this function, merge it in. - if (!TrackedRetVals.empty() && !isa(ResultOp->getType())) { + if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) { DenseMap::iterator TFRVI = TrackedRetVals.find(F); if (TFRVI != TrackedRetVals.end()) { @@ -787,7 +794,7 @@ void SCCPSolver::visitCastInst(CastInst &I) { void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { // If this returns a struct, mark all elements over defined, we don't track // structs in structs. - if (isa(EVI.getType())) + if (EVI.getType()->isStructTy()) return markAnythingOverdefined(&EVI); // If this is extracting from more than one level of struct, we don't know. @@ -795,7 +802,7 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { return markOverdefined(&EVI); Value *AggVal = EVI.getAggregateOperand(); - if (isa(AggVal->getType())) { + if (AggVal->getType()->isStructTy()) { unsigned i = *EVI.idx_begin(); LatticeVal EltVal = getStructValueState(AggVal, i); mergeInValue(getValueState(&EVI), &EVI, EltVal); @@ -828,7 +835,7 @@ void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { } Value *Val = IVI.getInsertedValueOperand(); - if (isa(Val->getType())) + if (Val->getType()->isStructTy()) // We don't track structs in structs. markOverdefined(getStructValueState(&IVI, i), &IVI); else { @@ -841,7 +848,7 @@ void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { 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(I.getType())) + if (I.getType()->isStructTy()) return markAnythingOverdefined(&I); LatticeVal CondValue = getValueState(I.getCondition()); @@ -1166,7 +1173,7 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { void SCCPSolver::visitStoreInst(StoreInst &SI) { // If this store is of a struct, ignore it. - if (isa(SI.getOperand(0)->getType())) + if (SI.getOperand(0)->getType()->isStructTy()) return; if (TrackedGlobals.empty() || !isa(SI.getOperand(1))) @@ -1187,7 +1194,7 @@ void SCCPSolver::visitStoreInst(StoreInst &SI) { // 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(I.getType())) + if (I.getType()->isStructTy()) return markAnythingOverdefined(&I); LatticeVal PtrVal = getValueState(I.getOperand(0)); @@ -1241,7 +1248,7 @@ CallOverdefined: // 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(I->getType()) && + if (F && F->isDeclaration() && !I->getType()->isStructTy() && canConstantFoldCallTo(F)) { SmallVector Operands; @@ -1324,7 +1331,7 @@ void SCCPSolver::Solve() { 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 @@ -1343,7 +1350,7 @@ void SCCPSolver::Solve() { 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. @@ -1352,7 +1359,7 @@ void SCCPSolver::Solve() { // since all of its users will have already been marked as overdefined. // Update all of the users of this instruction's value. // - if (isa(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(*UI)) @@ -1364,7 +1371,7 @@ void SCCPSolver::Solve() { 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. @@ -1418,7 +1425,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { if (!LV.isUndefined()) continue; // No instructions using structs need disambiguation. - if (isa(I->getOperand(0)->getType())) + if (I->getOperand(0)->getType()->isStructTy()) continue; // Get the lattice values of the first two operands for use below. @@ -1426,7 +1433,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { LatticeVal Op1LV; if (I->getNumOperands() == 2) { // No instructions using structs need disambiguation. - if (isa(I->getOperand(1)->getType())) + if (I->getOperand(1)->getType()->isStructTy()) continue; // If this is a two-operand instruction, and if both operands are @@ -1445,6 +1452,8 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // After a zero extend, we know the top part is zero. SExt doesn't have // to be handled here, because we don't know whether the top part is 1's // or 0's. + case Instruction::SIToFP: // some FP values are not possible, just use 0. + case Instruction::UIToFP: // some FP values are not possible, just use 0. markForcedConstant(I, Constant::getNullValue(ITy)); return true; case Instruction::Mul: @@ -1521,45 +1530,48 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { } } + // Check to see if we have a branch or switch on an undefined value. If so + // we force the branch to go one way or the other to make the successor + // values live. It doesn't really matter which way we force it. TerminatorInst *TI = BB->getTerminator(); if (BranchInst *BI = dyn_cast(TI)) { if (!BI->isConditional()) continue; if (!getValueState(BI->getCondition()).isUndefined()) continue; - } else if (SwitchInst *SI = dyn_cast(TI)) { + + // If the input to SCCP is actually branch on undef, fix the undef to + // false. + if (isa(BI->getCondition())) { + BI->setCondition(ConstantInt::getFalse(BI->getContext())); + markEdgeExecutable(BB, TI->getSuccessor(1)); + return true; + } + + // Otherwise, it is a branch on a symbolic value which is currently + // considered to be undef. Handle this by forcing the input value to the + // branch to false. + markForcedConstant(BI->getCondition(), + ConstantInt::getFalse(TI->getContext())); + return true; + } + + if (SwitchInst *SI = dyn_cast(TI)) { if (SI->getNumSuccessors() < 2) // no cases continue; if (!getValueState(SI->getCondition()).isUndefined()) continue; - } else { - continue; - } - - // If the edge to the second successor isn't thought to be feasible yet, - // mark it so now. We pick the second one so that this goes to some - // enumerated value in a switch instead of going to the default destination. - if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(1)))) - continue; - - // Otherwise, it isn't already thought to be feasible. Mark it as such now - // and return. This will make other blocks reachable, which will allow new - // values to be discovered and existing ones to be moved in the lattice. - markEdgeExecutable(BB, TI->getSuccessor(1)); - - // This must be a conditional branch of switch on undef. At this point, - // force the old terminator to branch to the first successor. This is - // required because we are now influencing the dataflow of the function with - // the assumption that this edge is taken. If we leave the branch condition - // as undef, then further analysis could think the undef went another way - // leading to an inconsistent set of conclusions. - if (BranchInst *BI = dyn_cast(TI)) { - BI->setCondition(ConstantInt::getFalse(BI->getContext())); - } else { - SwitchInst *SI = cast(TI); - SI->setCondition(SI->getCaseValue(1)); + + // If the input to SCCP is actually switch on undef, fix the undef to + // the first constant. + if (isa(SI->getCondition())) { + SI->setCondition(SI->getCaseValue(1)); + markEdgeExecutable(BB, TI->getSuccessor(1)); + return true; + } + + markForcedConstant(SI->getCondition(), SI->getCaseValue(1)); + return true; } - - return true; } return false; @@ -1588,8 +1600,8 @@ namespace { } // end anonymous namespace char SCCP::ID = 0; -static RegisterPass -X("sccp", "Sparse Conditional Constant Propagation"); +INITIALIZE_PASS(SCCP, "sccp", + "Sparse Conditional Constant Propagation", false, false); // createSCCPPass - This is the public interface to this file. FunctionPass *llvm::createSCCPPass() { @@ -1597,7 +1609,7 @@ FunctionPass *llvm::createSCCPPass() { } 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 @@ -1616,7 +1628,7 @@ static void DeleteInstructionInBlock(BasicBlock *BB) { // 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()); // Mark the first block of the function as being executable. @@ -1630,7 +1642,7 @@ bool SCCP::runOnFunction(Function &F) { bool ResolvedUndefs = true; while (ResolvedUndefs) { Solver.Solve(); - DEBUG(errs() << "RESOLVING UNDEFs\n"); + DEBUG(dbgs() << "RESOLVING UNDEFs\n"); ResolvedUndefs = Solver.ResolvedUndefsIn(F); } @@ -1656,7 +1668,7 @@ bool SCCP::runOnFunction(Function &F) { continue; // TODO: Reconstruct structs from their elements. - if (isa(Inst->getType())) + if (Inst->getType()->isStructTy()) continue; LatticeVal IV = Solver.getLatticeValueFor(Inst); @@ -1665,7 +1677,7 @@ bool SCCP::runOnFunction(Function &F) { 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); @@ -1696,8 +1708,9 @@ namespace { } // end anonymous namespace char IPSCCP::ID = 0; -static RegisterPass -Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); +INITIALIZE_PASS(IPSCCP, "ipsccp", + "Interprocedural Sparse Conditional Constant Propagation", + false, false); // createIPSCCPPass - This is the public interface to this file. ModulePass *llvm::createIPSCCPPass() { @@ -1705,28 +1718,31 @@ ModulePass *llvm::createIPSCCPPass() { } -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(*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(U)) { if (SI->getOperand(0) == GV || SI->isVolatile()) return true; // Storing addr of GV. - } else if (isa(*UI) || isa(*UI)) { + } else if (isa(U) || isa(U)) { // Make sure we are calling the function, not passing the address. - if (UI.getOperandNo() != 0) + ImmutableCallSite CS(cast(U)); + if (!CS.isCallee(UI)) return true; - } else if (LoadInst *LI = dyn_cast(*UI)) { + } else if (const LoadInst *LI = dyn_cast(U)) { if (LI->isVolatile()) return true; - } else if (isa(*UI)) { + } else if (isa(U)) { // blockaddress doesn't take the address of the function, it takes addr // of label. } else { return true; } + } return false; } @@ -1775,7 +1791,7 @@ bool IPSCCP::runOnModule(Module &M) { 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); @@ -1792,7 +1808,7 @@ bool IPSCCP::runOnModule(Module &M) { 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(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. @@ -1802,7 +1818,7 @@ bool IPSCCP::runOnModule(Module &M) { 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. @@ -1835,7 +1851,7 @@ bool IPSCCP::runOnModule(Module &M) { for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { Instruction *Inst = BI++; - if (Inst->getType()->isVoidTy() || isa(Inst->getType())) + if (Inst->getType()->isVoidTy() || Inst->getType()->isStructTy()) continue; // TODO: Could use getStructLatticeValueFor to find out if the entire @@ -1847,7 +1863,7 @@ bool IPSCCP::runOnModule(Module &M) { 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. @@ -1871,8 +1887,12 @@ bool IPSCCP::runOnModule(Module &M) { BasicBlock *DeadBB = BlocksToErase[i]; 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(*UI); + do { ++UI; } while (UI != UE && *UI == I); + // Ignore blockaddress users; BasicBlock's dtor will handle them. - Instruction *I = dyn_cast(*UI++); if (!I) continue; bool Folded = ConstantFoldTerminator(I->getParent()); @@ -1914,6 +1934,14 @@ bool IPSCCP::runOnModule(Module &M) { // 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 ReturnsToZap; + // TODO: Process multiple value ret instructions also. const DenseMap &RV = Solver.getTrackedRetVals(); for (DenseMap::const_iterator I = RV.begin(), @@ -1929,7 +1957,13 @@ bool IPSCCP::runOnModule(Module &M) { for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) if (ReturnInst *RI = dyn_cast(BB->getTerminator())) if (!isa(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 @@ -1940,7 +1974,7 @@ bool IPSCCP::runOnModule(Module &M) { 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(GV->use_back()); SI->eraseFromParent();