X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSCCP.cpp;h=f0b5d7702e37f13d7ba60f435fbdd3d16321e68f;hb=ca74940fee04662a61cee290a1b04ef2f2b52c09;hp=2de64c15ab153a5b2552effaf6d6c2179f3ef424;hpb=7d696d80409aad20bb5da0fc4eccab941dd371d4;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 2de64c15ab1..f0b5d7702e3 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -30,13 +30,14 @@ #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" @@ -59,7 +60,7 @@ namespace { /// 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, @@ -185,7 +186,7 @@ public: /// 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->getNameStart() << "\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! } @@ -261,14 +262,14 @@ private: // 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); } @@ -281,11 +282,11 @@ private: // 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(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); } @@ -338,8 +339,8 @@ private: return; // This edge is already known to be executable! if (BBExecutable.count(Dest)) { - DOUT << "Marking Edge Executable: " << Source->getNameStart() - << " -> " << Dest->getNameStart() << "\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 @@ -400,7 +401,12 @@ private: 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); @@ -415,7 +421,7 @@ private: 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 } }; @@ -441,7 +447,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, Succs[0] = Succs[1] = true; } else if (BCValue.isConstant()) { // Constant condition variables mean the branch can only go a single way - Succs[BCValue.getConstant() == Context->getConstantIntFalse()] = true; + Succs[BCValue.getConstant() == ConstantInt::getFalse(*Context)] = true; } } } else if (isa(&TI)) { @@ -456,7 +462,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, } else if (SCValue.isConstant()) Succs[SI->findCaseValue(cast(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!"); } } @@ -486,7 +492,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { // Constant condition variables mean the branch can only go a single way return BI->getSuccessor(BCValue.getConstant() == - Context->getConstantIntFalse()) == To; + ConstantInt::getFalse(*Context)) == To; } return false; } @@ -515,9 +521,9 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { return false; } else { #ifndef NDEBUG - cerr << "Unknown terminator instruction: " << *TI; + errs() << "Unknown terminator instruction: " << *TI << '\n'; #endif - llvm_unreachable(); + llvm_unreachable(0); } } @@ -645,7 +651,7 @@ void SCCPSolver::visitReturnInst(ReturnInst &I) { DenseMap, LatticeVal>::iterator It = TrackedMultipleRetVals.find(std::make_pair(F, i)); if (It == TrackedMultipleRetVals.end()) break; - if (Value *Val = FindInsertedValue(I.getOperand(0), i, Context)) + if (Value *Val = FindInsertedValue(I.getOperand(0), i, I.getContext())) mergeInValue(It->second, F, getValueState(Val)); } } @@ -669,7 +675,7 @@ void SCCPSolver::visitCastInst(CastInst &I) { if (VState.isOverdefined()) // Inherit overdefinedness of operand markOverdefined(&I); else if (VState.isConstant()) // Propagate constant value - markConstant(&I, Context->getConstantExprCast(I.getOpcode(), + markConstant(&I, ConstantExpr::getCast(I.getOpcode(), VState.getConstant(), I.getType())); } @@ -812,12 +818,12 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { if (NonOverdefVal->isUndefined()) { // Could annihilate value. if (I.getOpcode() == Instruction::And) - markConstant(IV, &I, Context->getNullValue(I.getType())); + markConstant(IV, &I, Constant::getNullValue(I.getType())); else if (const VectorType *PT = dyn_cast(I.getType())) - markConstant(IV, &I, Context->getConstantVectorAllOnesValue(PT)); + markConstant(IV, &I, Constant::getAllOnesValue(PT)); else markConstant(IV, &I, - Context->getConstantIntAllOnesValue(I.getType())); + Constant::getAllOnesValue(I.getType())); return; } else { if (I.getOpcode() == Instruction::And) { @@ -862,7 +868,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { break; // Cannot fold this operation over the PHI nodes! } else if (In1.isConstant() && In2.isConstant()) { Constant *V = - Context->getConstantExpr(I.getOpcode(), In1.getConstant(), + ConstantExpr::get(I.getOpcode(), In1.getConstant(), In2.getConstant()); if (Result.isUndefined()) Result.markConstant(V); @@ -911,7 +917,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { markOverdefined(IV, &I); } else if (V1State.isConstant() && V2State.isConstant()) { markConstant(IV, &I, - Context->getConstantExpr(I.getOpcode(), V1State.getConstant(), + ConstantExpr::get(I.getOpcode(), V1State.getConstant(), V2State.getConstant())); } } @@ -948,7 +954,7 @@ void SCCPSolver::visitCmpInst(CmpInst &I) { Result.markOverdefined(); break; // Cannot fold this operation over the PHI nodes! } else if (In1.isConstant() && In2.isConstant()) { - Constant *V = Context->getConstantExprCompare(I.getPredicate(), + Constant *V = ConstantExpr::getCompare(I.getPredicate(), In1.getConstant(), In2.getConstant()); if (Result.isUndefined()) @@ -997,7 +1003,7 @@ void SCCPSolver::visitCmpInst(CmpInst &I) { markOverdefined(IV, &I); } else if (V1State.isConstant() && V2State.isConstant()) { - markConstant(IV, &I, Context->getConstantExprCompare(I.getPredicate(), + markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), V1State.getConstant(), V2State.getConstant())); } @@ -1099,7 +1105,7 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { Constant *Ptr = Operands[0]; Operands.erase(Operands.begin()); // Erase the pointer from idx list... - markConstant(IV, &I, Context->getConstantExprGetElementPtr(Ptr, &Operands[0], + markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0], Operands.size())); } @@ -1130,10 +1136,9 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (PtrVal.isConstant() && !I.isVolatile()) { Value *Ptr = PtrVal.getConstant(); // TODO: Consider a target hook for valid address spaces for this xform. - if (isa(Ptr) && - cast(Ptr->getType())->getAddressSpace() == 0) { + if (isa(Ptr) && I.getPointerAddressSpace() == 0) { // load null -> null - markConstant(IV, &I, Context->getNullValue(I.getType())); + markConstant(IV, &I, Constant::getNullValue(I.getType())); return; } @@ -1162,7 +1167,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (GV->isConstant() && GV->hasDefinitiveInitializer()) if (Constant *V = ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE, - Context)) { + *Context)) { markConstant(IV, &I, V); return; } @@ -1183,7 +1188,7 @@ void SCCPSolver::visitCallSite(CallSite CS) { if (F == 0 || !F->hasLocalLinkage()) { CallOverdefined: // Void return and not tracking callee, just bail. - if (I->getType() == Type::VoidTy) return; + if (I->getType() == Type::getVoidTy(I->getContext())) return; // Otherwise, if we have a single return value case, and if the function is // a declaration, maybe we can constant fold it. @@ -1277,7 +1282,7 @@ void SCCPSolver::Solve() { 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 @@ -1295,7 +1300,7 @@ void SCCPSolver::Solve() { 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 @@ -1315,7 +1320,7 @@ void SCCPSolver::Solve() { 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. @@ -1349,7 +1354,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { 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; @@ -1375,22 +1380,22 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // to be handled here, because we don't know whether the top part is 1's // or 0's. assert(Op0LV.isUndefined()); - markForcedConstant(LV, I, Context->getNullValue(ITy)); + markForcedConstant(LV, I, Constant::getNullValue(ITy)); return true; case Instruction::Mul: case Instruction::And: // undef * X -> 0. X could be zero. // undef & X -> 0. X could be zero. - markForcedConstant(LV, I, Context->getNullValue(ITy)); + markForcedConstant(LV, I, Constant::getNullValue(ITy)); return true; case Instruction::Or: // undef | X -> -1. X could be -1. if (const VectorType *PTy = dyn_cast(ITy)) markForcedConstant(LV, I, - Context->getConstantVectorAllOnesValue(PTy)); + Constant::getAllOnesValue(PTy)); else - markForcedConstant(LV, I, Context->getConstantIntAllOnesValue(ITy)); + markForcedConstant(LV, I, Constant::getAllOnesValue(ITy)); return true; case Instruction::SDiv: @@ -1403,7 +1408,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // undef / X -> 0. X could be maxint. // undef % X -> 0. X could be 1. - markForcedConstant(LV, I, Context->getNullValue(ITy)); + markForcedConstant(LV, I, Constant::getNullValue(ITy)); return true; case Instruction::AShr: @@ -1424,7 +1429,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // X >> undef -> 0. X could be 0. // X << undef -> 0. X could be 0. - markForcedConstant(LV, I, Context->getNullValue(ITy)); + markForcedConstant(LV, I, Constant::getNullValue(ITy)); return true; case Instruction::Select: // undef ? X : Y -> X or Y. There could be commonality between X/Y. @@ -1487,7 +1492,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // 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(Context->getConstantIntFalse()); + BI->setCondition(ConstantInt::getFalse(*Context)); } else { SwitchInst *SI = cast(TI); SI->setCondition(SI->getCaseValue(1)); @@ -1506,7 +1511,7 @@ namespace { /// 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(&ID) {} @@ -1535,9 +1540,9 @@ FunctionPass *llvm::createSCCPPass() { // and return true if the function was modified. // bool SCCP::runOnFunction(Function &F) { - DOUT << "SCCP on function '" << F.getNameStart() << "'\n"; + DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n"); SCCPSolver Solver; - Solver.setContext(Context); + Solver.setContext(&F.getContext()); // Mark the first block of the function as being executable. Solver.MarkBlockExecutable(F.begin()); @@ -1550,7 +1555,7 @@ bool SCCP::runOnFunction(Function &F) { bool ResolvedUndefs = true; while (ResolvedUndefs) { Solver.Solve(); - DOUT << "RESOLVING UNDEFs\n"; + DEBUG(errs() << "RESOLVING UNDEFs\n"); ResolvedUndefs = Solver.ResolvedUndefsIn(F); } @@ -1565,7 +1570,7 @@ bool SCCP::runOnFunction(Function &F) { for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) if (!Solver.isBlockExecutable(BB)) { - DOUT << " BasicBlock Dead:" << *BB; + DEBUG(errs() << " BasicBlock Dead:" << *BB); ++NumDeadBlocks; // Delete the instructions backwards, as it has a reduced likelihood of @@ -1577,7 +1582,7 @@ bool SCCP::runOnFunction(Function &F) { Instruction *I = Insts.back(); Insts.pop_back(); if (!I->use_empty()) - I->replaceAllUsesWith(Context->getUndef(I->getType())); + I->replaceAllUsesWith(UndefValue::get(I->getType())); BB->getInstList().erase(I); MadeChanges = true; ++NumInstRemoved; @@ -1588,7 +1593,7 @@ bool SCCP::runOnFunction(Function &F) { // for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { Instruction *Inst = BI++; - if (Inst->getType() == Type::VoidTy || + if (Inst->getType() == Type::getVoidTy(F.getContext()) || isa(Inst)) continue; @@ -1597,8 +1602,8 @@ bool SCCP::runOnFunction(Function &F) { continue; Constant *Const = IV.isConstant() - ? IV.getConstant() : Context->getUndef(Inst->getType()); - DOUT << " Constant: " << *Const << " = " << *Inst; + ? 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); @@ -1621,7 +1626,7 @@ namespace { /// 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(&ID) {} bool runOnModule(Module &M); @@ -1662,7 +1667,10 @@ static bool AddressIsTaken(GlobalValue *GV) { } 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. @@ -1691,7 +1699,7 @@ bool IPSCCP::runOnModule(Module &M) { 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); @@ -1713,8 +1721,8 @@ bool IPSCCP::runOnModule(Module &M) { LatticeVal &IV = Values[AI]; if (IV.isConstant() || IV.isUndefined()) { Constant *CST = IV.isConstant() ? - IV.getConstant() : Context->getUndef(AI->getType()); - DOUT << "*** Arg " << *AI << " = " << *CST <<"\n"; + IV.getConstant() : UndefValue::get(AI->getType()); + DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n"); // Replaces all of the uses of a variable with uses of the // constant. @@ -1725,7 +1733,7 @@ bool IPSCCP::runOnModule(Module &M) { for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) if (!Solver.isBlockExecutable(BB)) { - DOUT << " BasicBlock Dead:" << *BB; + DEBUG(errs() << " BasicBlock Dead:" << *BB); ++IPNumDeadBlocks; // Delete the instructions backwards, as it has a reduced likelihood of @@ -1738,7 +1746,7 @@ bool IPSCCP::runOnModule(Module &M) { Instruction *I = Insts.back(); Insts.pop_back(); if (!I->use_empty()) - I->replaceAllUsesWith(Context->getUndef(I->getType())); + I->replaceAllUsesWith(UndefValue::get(I->getType())); BB->getInstList().erase(I); MadeChanges = true; ++IPNumInstRemoved; @@ -1750,18 +1758,18 @@ bool IPSCCP::runOnModule(Module &M) { TI->getSuccessor(i)->removePredecessor(BB); } if (!TI->use_empty()) - TI->replaceAllUsesWith(Context->getUndef(TI->getType())); + TI->replaceAllUsesWith(UndefValue::get(TI->getType())); BB->getInstList().erase(TI); 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) + if (Inst->getType() == Type::getVoidTy(M.getContext())) continue; LatticeVal &IV = Values[Inst]; @@ -1769,8 +1777,8 @@ bool IPSCCP::runOnModule(Module &M) { continue; Constant *Const = IV.isConstant() - ? IV.getConstant() : Context->getUndef(Inst->getType()); - DOUT << " Constant: " << *Const << " = " << *Inst; + ? IV.getConstant() : UndefValue::get(Inst->getType()); + DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); // Replaces all of the uses of a variable with uses of the // constant. @@ -1806,7 +1814,7 @@ bool IPSCCP::runOnModule(Module &M) { } else if (SwitchInst *SI = dyn_cast(I)) { assert(isa(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 @@ -1838,12 +1846,12 @@ bool IPSCCP::runOnModule(Module &M) { for (DenseMap::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(BB->getTerminator())) if (!isa(RI->getOperand(0))) - RI->setOperand(0, Context->getUndef(F->getReturnType())); + RI->setOperand(0, UndefValue::get(F->getReturnType())); } // If we infered constant or undef values for globals variables, we can delete @@ -1854,7 +1862,7 @@ bool IPSCCP::runOnModule(Module &M) { GlobalVariable *GV = I->first; assert(!I->second.isOverdefined() && "Overdefined values should have been taken out of the map!"); - DOUT << "Found that GV '" << GV->getNameStart() << "' is constant!\n"; + DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n"); while (!GV->use_empty()) { StoreInst *SI = cast(GV->use_back()); SI->eraseFromParent();