diff options
Diffstat (limited to 'lib/Transforms/IPO')
22 files changed, 1382 insertions, 754 deletions
diff --git a/lib/Transforms/IPO/ArgumentPromotion.cpp b/lib/Transforms/IPO/ArgumentPromotion.cpp index a612634..5b91f3d 100644 --- a/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -36,16 +36,18 @@ #include "llvm/Module.h" #include "llvm/CallGraphSCCPass.h" #include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Target/TargetData.h" #include "llvm/Support/CallSite.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" -#include "llvm/Support/Compiler.h" #include <set> using namespace llvm; @@ -60,11 +62,10 @@ namespace { struct VISIBILITY_HIDDEN ArgPromotion : public CallGraphSCCPass { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired<AliasAnalysis>(); - AU.addRequired<TargetData>(); CallGraphSCCPass::getAnalysisUsage(AU); } - virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC); + virtual bool runOnSCC(std::vector<CallGraphNode *> &SCC); static char ID; // Pass identification, replacement for typeid explicit ArgPromotion(unsigned maxElements = 3) : CallGraphSCCPass(&ID), maxElements(maxElements) {} @@ -73,11 +74,11 @@ namespace { typedef std::vector<uint64_t> IndicesVector; private: - bool PromoteArguments(CallGraphNode *CGN); + CallGraphNode *PromoteArguments(CallGraphNode *CGN); bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const; - Function *DoPromotion(Function *F, - SmallPtrSet<Argument*, 8> &ArgsToPromote, - SmallPtrSet<Argument*, 8> &ByValArgsToTransform); + CallGraphNode *DoPromotion(Function *F, + SmallPtrSet<Argument*, 8> &ArgsToPromote, + SmallPtrSet<Argument*, 8> &ByValArgsToTransform); /// The maximum number of elements to expand, or 0 for unlimited. unsigned maxElements; }; @@ -91,14 +92,17 @@ Pass *llvm::createArgumentPromotionPass(unsigned maxElements) { return new ArgPromotion(maxElements); } -bool ArgPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) { +bool ArgPromotion::runOnSCC(std::vector<CallGraphNode *> &SCC) { bool Changed = false, LocalChange; do { // Iterate until we stop promoting from this SCC. LocalChange = false; // Attempt to promote arguments from all functions in this SCC. for (unsigned i = 0, e = SCC.size(); i != e; ++i) - LocalChange |= PromoteArguments(SCC[i]); + if (CallGraphNode *CGN = PromoteArguments(SCC[i])) { + LocalChange = true; + SCC[i] = CGN; + } Changed |= LocalChange; // Remember that we changed something. } while (LocalChange); @@ -110,11 +114,11 @@ bool ArgPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) { /// example, all callers are direct). If safe to promote some arguments, it /// calls the DoPromotion method. /// -bool ArgPromotion::PromoteArguments(CallGraphNode *CGN) { +CallGraphNode *ArgPromotion::PromoteArguments(CallGraphNode *CGN) { Function *F = CGN->getFunction(); // Make sure that it is local to this module. - if (!F || !F->hasLocalLinkage()) return false; + if (!F || !F->hasLocalLinkage()) return 0; // First check: see if there are any pointer arguments! If not, quick exit. SmallVector<std::pair<Argument*, unsigned>, 16> PointerArgs; @@ -123,12 +127,12 @@ bool ArgPromotion::PromoteArguments(CallGraphNode *CGN) { I != E; ++I, ++ArgNo) if (isa<PointerType>(I->getType())) PointerArgs.push_back(std::pair<Argument*, unsigned>(I, ArgNo)); - if (PointerArgs.empty()) return false; + if (PointerArgs.empty()) return 0; // Second check: make sure that all callers are direct callers. We can't // transform functions that have indirect callers. if (F->hasAddressTaken()) - return false; + return 0; // Check to see which arguments are promotable. If an argument is promotable, // add it to ArgsToPromote. @@ -144,9 +148,9 @@ bool ArgPromotion::PromoteArguments(CallGraphNode *CGN) { const Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType(); if (const StructType *STy = dyn_cast<StructType>(AgTy)) { if (maxElements > 0 && STy->getNumElements() > maxElements) { - DOUT << "argpromotion disable promoting argument '" - << PtrArg->getName() << "' because it would require adding more " - << "than " << maxElements << " arguments to the function.\n"; + DEBUG(errs() << "argpromotion disable promoting argument '" + << PtrArg->getName() << "' because it would require adding more" + << " than " << maxElements << " arguments to the function.\n"); } else { // If all the elements are single-value types, we can promote it. bool AllSimple = true; @@ -173,13 +177,10 @@ bool ArgPromotion::PromoteArguments(CallGraphNode *CGN) { } // No promotable pointer arguments. - if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) return false; - - Function *NewF = DoPromotion(F, ArgsToPromote, ByValArgsToTransform); + if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) + return 0; - // Update the call graph to know that the function has been transformed. - getAnalysis<CallGraph>().changeFunction(F, NewF); - return true; + return DoPromotion(F, ArgsToPromote, ByValArgsToTransform); } /// IsAlwaysValidPointer - Return true if the specified pointer is always legal @@ -409,9 +410,9 @@ bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const { // to do. if (ToPromote.find(Operands) == ToPromote.end()) { if (maxElements > 0 && ToPromote.size() == maxElements) { - DOUT << "argpromotion not promoting argument '" - << Arg->getName() << "' because it would require adding more " - << "than " << maxElements << " arguments to the function.\n"; + DEBUG(errs() << "argpromotion not promoting argument '" + << Arg->getName() << "' because it would require adding more " + << "than " << maxElements << " arguments to the function.\n"); // We limit aggregate promotion to only promoting up to a fixed number // of elements of the aggregate. return false; @@ -432,7 +433,8 @@ bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const { SmallPtrSet<BasicBlock*, 16> TranspBlocks; AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); - TargetData &TD = getAnalysis<TargetData>(); + TargetData *TD = getAnalysisIfAvailable<TargetData>(); + if (!TD) return false; // Without TargetData, assume the worst. for (unsigned i = 0, e = Loads.size(); i != e; ++i) { // Check to see if the load is invalidated from the start of the block to @@ -442,7 +444,7 @@ bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const { const PointerType *LoadTy = cast<PointerType>(Load->getPointerOperand()->getType()); - unsigned LoadSize = (unsigned)TD.getTypeStoreSize(LoadTy->getElementType()); + unsigned LoadSize =(unsigned)TD->getTypeStoreSize(LoadTy->getElementType()); if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize)) return false; // Pointer is invalidated! @@ -467,8 +469,8 @@ bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const { /// DoPromotion - This method actually performs the promotion of the specified /// arguments, and returns the new function. At this point, we know that it's /// safe to do so. -Function *ArgPromotion::DoPromotion(Function *F, - SmallPtrSet<Argument*, 8> &ArgsToPromote, +CallGraphNode *ArgPromotion::DoPromotion(Function *F, + SmallPtrSet<Argument*, 8> &ArgsToPromote, SmallPtrSet<Argument*, 8> &ByValArgsToTransform) { // Start by computing a new prototype for the function, which is the same as @@ -581,19 +583,24 @@ Function *ArgPromotion::DoPromotion(Function *F, bool ExtraArgHack = false; if (Params.empty() && FTy->isVarArg()) { ExtraArgHack = true; - Params.push_back(Type::Int32Ty); + Params.push_back(Type::getInt32Ty(F->getContext())); } // Construct the new function type using the new arguments. FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); - // Create the new function body and insert it into the module... + // Create the new function body and insert it into the module. Function *NF = Function::Create(NFTy, F->getLinkage(), F->getName()); NF->copyAttributesFrom(F); + + DEBUG(errs() << "ARG PROMOTION: Promoting to:" << *NF << "\n" + << "From: " << *F); + // Recompute the parameter attributes list based on the new arguments for // the function. - NF->setAttributes(AttrListPtr::get(AttributesVec.begin(), AttributesVec.end())); + NF->setAttributes(AttrListPtr::get(AttributesVec.begin(), + AttributesVec.end())); AttributesVec.clear(); F->getParent()->getFunctionList().insert(F, NF); @@ -606,6 +613,10 @@ Function *ArgPromotion::DoPromotion(Function *F, // Get the callgraph information that we need to update to reflect our // changes. CallGraph &CG = getAnalysis<CallGraph>(); + + // Get a new callgraph node for NF. + CallGraphNode *NF_CGN = CG.getOrInsertFunction(NF); + // Loop over all of the callers of the function, transforming the call sites // to pass in the loaded pointers. @@ -636,9 +647,10 @@ Function *ArgPromotion::DoPromotion(Function *F, // Emit a GEP and load for each element of the struct. const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); const StructType *STy = cast<StructType>(AgTy); - Value *Idxs[2] = { ConstantInt::get(Type::Int32Ty, 0), 0 }; + Value *Idxs[2] = { + ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), 0 }; for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { - Idxs[1] = ConstantInt::get(Type::Int32Ty, i); + Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); Value *Idx = GetElementPtrInst::Create(*AI, Idxs, Idxs+2, (*AI)->getName()+"."+utostr(i), Call); @@ -662,7 +674,9 @@ Function *ArgPromotion::DoPromotion(Function *F, IE = SI->end(); II != IE; ++II) { // Use i32 to index structs, and i64 for others (pointers/arrays). // This satisfies GEP constraints. - const Type *IdxTy = (isa<StructType>(ElTy) ? Type::Int32Ty : Type::Int64Ty); + const Type *IdxTy = (isa<StructType>(ElTy) ? + Type::getInt32Ty(F->getContext()) : + Type::getInt64Ty(F->getContext())); Ops.push_back(ConstantInt::get(IdxTy, *II)); // Keep track of the type we're currently indexing ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(*II); @@ -679,7 +693,7 @@ Function *ArgPromotion::DoPromotion(Function *F, } if (ExtraArgHack) - Args.push_back(Constant::getNullValue(Type::Int32Ty)); + Args.push_back(Constant::getNullValue(Type::getInt32Ty(F->getContext()))); // Push any varargs arguments on the list for (; AI != CS.arg_end(); ++AI, ++ArgIndex) { @@ -715,7 +729,8 @@ Function *ArgPromotion::DoPromotion(Function *F, AA.replaceWithNewValue(Call, New); // Update the callgraph to know that the callsite has been transformed. - CG[Call->getParent()->getParent()]->replaceCallSite(Call, New); + CallGraphNode *CalleeNode = CG[Call->getParent()->getParent()]; + CalleeNode->replaceCallEdge(Call, New, NF_CGN); if (!Call->use_empty()) { Call->replaceAllUsesWith(New); @@ -756,14 +771,16 @@ Function *ArgPromotion::DoPromotion(Function *F, const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); Value *TheAlloca = new AllocaInst(AgTy, 0, "", InsertPt); const StructType *STy = cast<StructType>(AgTy); - Value *Idxs[2] = { ConstantInt::get(Type::Int32Ty, 0), 0 }; + Value *Idxs[2] = { + ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), 0 }; for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { - Idxs[1] = ConstantInt::get(Type::Int32Ty, i); - std::string Name = TheAlloca->getName()+"."+utostr(i); - Value *Idx = GetElementPtrInst::Create(TheAlloca, Idxs, Idxs+2, - Name, InsertPt); - I2->setName(I->getName()+"."+utostr(i)); + Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); + Value *Idx = + GetElementPtrInst::Create(TheAlloca, Idxs, Idxs+2, + TheAlloca->getName()+"."+Twine(i), + InsertPt); + I2->setName(I->getName()+"."+Twine(i)); new StoreInst(I2++, Idx, InsertPt); } @@ -792,8 +809,8 @@ Function *ArgPromotion::DoPromotion(Function *F, LI->replaceAllUsesWith(I2); AA.replaceWithNewValue(LI, I2); LI->eraseFromParent(); - DOUT << "*** Promoted load of argument '" << I->getName() - << "' in function '" << F->getName() << "'\n"; + DEBUG(errs() << "*** Promoted load of argument '" << I->getName() + << "' in function '" << F->getName() << "'\n"); } else { GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->use_back()); IndicesVector Operands; @@ -819,8 +836,8 @@ Function *ArgPromotion::DoPromotion(Function *F, NewName += ".val"; TheArg->setName(NewName); - DOUT << "*** Promoted agg argument '" << TheArg->getName() - << "' of function '" << NF->getName() << "'\n"; + DEBUG(errs() << "*** Promoted agg argument '" << TheArg->getName() + << "' of function '" << NF->getName() << "'\n"); // All of the uses must be load instructions. Replace them all with // the argument specified by ArgNo. @@ -842,13 +859,18 @@ Function *ArgPromotion::DoPromotion(Function *F, // Notify the alias analysis implementation that we inserted a new argument. if (ExtraArgHack) - AA.copyValue(Constant::getNullValue(Type::Int32Ty), NF->arg_begin()); + AA.copyValue(Constant::getNullValue(Type::getInt32Ty(F->getContext())), + NF->arg_begin()); // Tell the alias analysis that the old function is about to disappear. AA.replaceWithNewValue(F, NF); + + NF_CGN->stealCalledFunctionsFrom(CG[F]); + // Now that the old function is dead, delete it. - F->eraseFromParent(); - return NF; + delete CG.removeFunctionFromModule(F); + + return NF_CGN; } diff --git a/lib/Transforms/IPO/CMakeLists.txt b/lib/Transforms/IPO/CMakeLists.txt index 1438b48..ec0f1e1 100644 --- a/lib/Transforms/IPO/CMakeLists.txt +++ b/lib/Transforms/IPO/CMakeLists.txt @@ -1,18 +1,19 @@ add_llvm_library(LLVMipo - FunctionAttrs.cpp ArgumentPromotion.cpp ConstantMerge.cpp DeadArgumentElimination.cpp DeadTypeElimination.cpp ExtractGV.cpp + FunctionAttrs.cpp GlobalDCE.cpp GlobalOpt.cpp + IPConstantPropagation.cpp + IPO.cpp IndMemRemoval.cpp InlineAlways.cpp - Inliner.cpp InlineSimple.cpp + Inliner.cpp Internalize.cpp - IPConstantPropagation.cpp LoopExtractor.cpp LowerSetJmp.cpp MergeFunctions.cpp diff --git a/lib/Transforms/IPO/ConstantMerge.cpp b/lib/Transforms/IPO/ConstantMerge.cpp index 237e6db..c1a1045 100644 --- a/lib/Transforms/IPO/ConstantMerge.cpp +++ b/lib/Transforms/IPO/ConstantMerge.cpp @@ -78,7 +78,7 @@ bool ConstantMerge::runOnModule(Module &M) { } // Only process constants with initializers. - if (GV->isConstant() && GV->hasInitializer()) { + if (GV->isConstant() && GV->hasDefinitiveInitializer()) { Constant *Init = GV->getInitializer(); // Check to see if the initializer is already known. diff --git a/lib/Transforms/IPO/DeadArgumentElimination.cpp b/lib/Transforms/IPO/DeadArgumentElimination.cpp index e480dad..79a32f0 100644 --- a/lib/Transforms/IPO/DeadArgumentElimination.cpp +++ b/lib/Transforms/IPO/DeadArgumentElimination.cpp @@ -24,10 +24,12 @@ #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" @@ -72,7 +74,7 @@ namespace { std::string getDescription() const { return std::string((IsArg ? "Argument #" : "Return value #")) - + utostr(Idx) + " of function " + F->getName(); + + utostr(Idx) + " of function " + F->getNameStr(); } }; @@ -195,8 +197,10 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { // Start by computing a new prototype for the function, which is the same as // the old function, but doesn't have isVarArg set. const FunctionType *FTy = Fn.getFunctionType(); + std::vector<const Type*> Params(FTy->param_begin(), FTy->param_end()); - FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false); + FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), + Params, false); unsigned NumArgs = Params.size(); // Create the new function body and insert it into the module... @@ -277,7 +281,7 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { /// for void functions and 1 for functions not returning a struct. It returns /// the number of struct elements for functions returning a struct. static unsigned NumRetVals(const Function *F) { - if (F->getReturnType() == Type::VoidTy) + if (F->getReturnType() == Type::getVoidTy(F->getContext())) return 0; else if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) return STy->getNumElements(); @@ -422,7 +426,7 @@ void DAE::SurveyFunction(Function &F) { return; } - DOUT << "DAE - Inspecting callers for fn: " << F.getName() << "\n"; + DEBUG(errs() << "DAE - Inspecting callers for fn: " << F.getName() << "\n"); // Keep track of the number of live retvals, so we can skip checks once all // of them turn out to be live. unsigned NumLiveRetVals = 0; @@ -485,7 +489,7 @@ void DAE::SurveyFunction(Function &F) { for (unsigned i = 0; i != RetCount; ++i) MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]); - DOUT << "DAE - Inspecting args for fn: " << F.getName() << "\n"; + DEBUG(errs() << "DAE - Inspecting args for fn: " << F.getName() << "\n"); // Now, check all of our arguments. unsigned i = 0; @@ -527,7 +531,7 @@ void DAE::MarkValue(const RetOrArg &RA, Liveness L, /// mark any values that are used as this function's parameters or by its return /// values (according to Uses) live as well. void DAE::MarkLive(const Function &F) { - DOUT << "DAE - Intrinsically live fn: " << F.getName() << "\n"; + DEBUG(errs() << "DAE - Intrinsically live fn: " << F.getName() << "\n"); // Mark the function as live. LiveFunctions.insert(&F); // Mark all arguments as live. @@ -548,7 +552,7 @@ void DAE::MarkLive(const RetOrArg &RA) { if (!LiveValues.insert(RA).second) return; // We were already marked Live. - DOUT << "DAE - Marking " << RA.getDescription() << " live\n"; + DEBUG(errs() << "DAE - Marking " << RA.getDescription() << " live\n"); PropagateLiveness(RA); } @@ -596,11 +600,12 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { const Type *RetTy = FTy->getReturnType(); const Type *NRetTy = NULL; unsigned RetCount = NumRetVals(F); + // -1 means unused, other numbers are the new index SmallVector<int, 5> NewRetIdxs(RetCount, -1); std::vector<const Type*> RetTypes; - if (RetTy == Type::VoidTy) { - NRetTy = Type::VoidTy; + if (RetTy == Type::getVoidTy(F->getContext())) { + NRetTy = Type::getVoidTy(F->getContext()); } else { const StructType *STy = dyn_cast<StructType>(RetTy); if (STy) @@ -612,8 +617,8 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { NewRetIdxs[i] = RetTypes.size() - 1; } else { ++NumRetValsEliminated; - DOUT << "DAE - Removing return value " << i << " from " - << F->getNameStart() << "\n"; + DEBUG(errs() << "DAE - Removing return value " << i << " from " + << F->getName() << "\n"); } } else @@ -622,8 +627,8 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { RetTypes.push_back(RetTy); NewRetIdxs[0] = 0; } else { - DOUT << "DAE - Removing return value from " << F->getNameStart() - << "\n"; + DEBUG(errs() << "DAE - Removing return value from " << F->getName() + << "\n"); ++NumRetValsEliminated; } if (RetTypes.size() > 1) @@ -633,14 +638,14 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // something and {} into void. // Make the new struct packed if we used to return a packed struct // already. - NRetTy = StructType::get(RetTypes, STy->isPacked()); + NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); else if (RetTypes.size() == 1) // One return type? Just a simple value then, but only if we didn't use to // return a struct with that simple value before. NRetTy = RetTypes.front(); else if (RetTypes.size() == 0) // No return types? Make it void, but only if we didn't use to return {}. - NRetTy = Type::VoidTy; + NRetTy = Type::getVoidTy(F->getContext()); } assert(NRetTy && "No new return type found?"); @@ -649,7 +654,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // values. Otherwise, ensure that we don't have any conflicting attributes // here. Currently, this should not be possible, but special handling might be // required when new return value attributes are added. - if (NRetTy == Type::VoidTy) + if (NRetTy == Type::getVoidTy(F->getContext())) RAttrs &= ~Attribute::typeIncompatible(NRetTy); else assert((RAttrs & Attribute::typeIncompatible(NRetTy)) == 0 @@ -677,8 +682,8 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { AttributesVec.push_back(AttributeWithIndex::get(Params.size(), Attrs)); } else { ++NumArgumentsEliminated; - DOUT << "DAE - Removing argument " << i << " (" << I->getNameStart() - << ") from " << F->getNameStart() << "\n"; + DEBUG(errs() << "DAE - Removing argument " << i << " (" << I->getName() + << ") from " << F->getName() << "\n"); } } @@ -697,11 +702,12 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { bool ExtraArgHack = false; if (Params.empty() && FTy->isVarArg() && FTy->getNumParams() != 0) { ExtraArgHack = true; - Params.push_back(Type::Int32Ty); + Params.push_back(Type::getInt32Ty(F->getContext())); } // Create the new function type based on the recomputed parameters. - FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); + FunctionType *NFTy = FunctionType::get(NRetTy, Params, + FTy->isVarArg()); // No change? if (NFTy == FTy) @@ -750,7 +756,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { } if (ExtraArgHack) - Args.push_back(UndefValue::get(Type::Int32Ty)); + Args.push_back(UndefValue::get(Type::getInt32Ty(F->getContext()))); // Push any varargs arguments on the list. Don't forget their attributes. for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { @@ -786,7 +792,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // Return type not changed? Just replace users then. Call->replaceAllUsesWith(New); New->takeName(Call); - } else if (New->getType() == Type::VoidTy) { + } else if (New->getType() == Type::getVoidTy(F->getContext())) { // Our return value has uses, but they will get removed later on. // Replace by null for now. Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); @@ -806,7 +812,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // extract/insertvalue chaining and let instcombine clean that up. // // Start out building up our return value from undef - Value *RetVal = llvm::UndefValue::get(RetTy); + Value *RetVal = UndefValue::get(RetTy); for (unsigned i = 0; i != RetCount; ++i) if (NewRetIdxs[i] != -1) { Value *V; @@ -862,7 +868,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { Value *RetVal; - if (NFTy->getReturnType() == Type::VoidTy) { + if (NFTy->getReturnType() == Type::getVoidTy(F->getContext())) { RetVal = 0; } else { assert (isa<StructType>(RetTy)); @@ -873,7 +879,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // clean that up. Value *OldRet = RI->getOperand(0); // Start out building up our return value from undef - RetVal = llvm::UndefValue::get(NRetTy); + RetVal = UndefValue::get(NRetTy); for (unsigned i = 0; i != RetCount; ++i) if (NewRetIdxs[i] != -1) { ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i, @@ -893,7 +899,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { } // Replace the return instruction with one returning the new return // value (possibly 0 if we became void). - ReturnInst::Create(RetVal, RI); + ReturnInst::Create(F->getContext(), RetVal, RI); BB->getInstList().erase(RI); } @@ -910,7 +916,7 @@ bool DAE::runOnModule(Module &M) { // removed. We can do this if they never call va_start. This loop cannot be // fused with the next loop, because deleting a function invalidates // information computed while surveying other functions. - DOUT << "DAE - Deleting dead varargs\n"; + DEBUG(errs() << "DAE - Deleting dead varargs\n"); for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { Function &F = *I++; if (F.getFunctionType()->isVarArg()) @@ -921,7 +927,7 @@ bool DAE::runOnModule(Module &M) { // We assume all arguments are dead unless proven otherwise (allowing us to // determine that dead arguments passed into recursive functions are dead). // - DOUT << "DAE - Determining liveness\n"; + DEBUG(errs() << "DAE - Determining liveness\n"); for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) SurveyFunction(*I); diff --git a/lib/Transforms/IPO/ExtractGV.cpp b/lib/Transforms/IPO/ExtractGV.cpp index 0c529d2..191100c 100644 --- a/lib/Transforms/IPO/ExtractGV.cpp +++ b/lib/Transforms/IPO/ExtractGV.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Constants.h" @@ -43,6 +44,7 @@ namespace { return false; // Nothing to extract } + if (deleteStuff) return deleteGV(); M.setModuleInlineAsm(""); @@ -99,7 +101,8 @@ namespace { // by putting them in the used array { std::vector<Constant *> AUGs; - const Type *SBP= PointerType::getUnqual(Type::Int8Ty); + const Type *SBP= + Type::getInt8PtrTy(M.getContext()); for (std::vector<GlobalValue*>::iterator GI = Named.begin(), GE = Named.end(); GI != GE; ++GI) { (*GI)->setLinkage(GlobalValue::ExternalLinkage); @@ -107,9 +110,9 @@ namespace { } ArrayType *AT = ArrayType::get(SBP, AUGs.size()); Constant *Init = ConstantArray::get(AT, AUGs); - GlobalValue *gv = new GlobalVariable(AT, false, + GlobalValue *gv = new GlobalVariable(M, AT, false, GlobalValue::AppendingLinkage, - Init, "llvm.used", &M); + Init, "llvm.used"); gv->setSection("llvm.metadata"); } diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp index e831524..7edaa7f 100644 --- a/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/lib/Transforms/IPO/FunctionAttrs.cpp @@ -26,6 +26,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/MallocHelper.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/UniqueVector.h" @@ -44,7 +45,7 @@ namespace { FunctionAttrs() : CallGraphSCCPass(&ID) {} // runOnSCC - Analyze the SCC, performing the transformation if possible. - bool runOnSCC(const std::vector<CallGraphNode *> &SCC); + bool runOnSCC(std::vector<CallGraphNode *> &SCC); // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. bool AddReadAttrs(const std::vector<CallGraphNode *> &SCC); @@ -54,7 +55,7 @@ namespace { // IsFunctionMallocLike - Does this function allocate new memory? bool IsFunctionMallocLike(Function *F, - SmallPtrSet<CallGraphNode*, 8> &) const; + SmallPtrSet<Function*, 8> &) const; // AddNoAliasAttrs - Deduce noalias attributes for the SCC. bool AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC); @@ -93,13 +94,12 @@ bool FunctionAttrs::PointsToLocalMemory(Value *V) { /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) { - SmallPtrSet<CallGraphNode*, 8> SCCNodes; - CallGraph &CG = getAnalysis<CallGraph>(); + SmallPtrSet<Function*, 8> SCCNodes; // Fill SCCNodes with the elements of the SCC. Used for quickly // looking up whether a given CallGraphNode is in this SCC. for (unsigned i = 0, e = SCC.size(); i != e; ++i) - SCCNodes.insert(SCC[i]); + SCCNodes.insert(SCC[i]->getFunction()); // Check if any of the functions in the SCC read or write memory. If they // write memory then they can't be marked readnone or readonly. @@ -133,9 +133,9 @@ bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) { // Some instructions can be ignored even if they read or write memory. // Detect these now, skipping to the next instruction if one is found. CallSite CS = CallSite::get(I); - if (CS.getInstruction()) { + if (CS.getInstruction() && CS.getCalledFunction()) { // Ignore calls to functions in the same SCC. - if (SCCNodes.count(CG[CS.getCalledFunction()])) + if (SCCNodes.count(CS.getCalledFunction())) continue; } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { // Ignore loads from local memory. @@ -154,7 +154,7 @@ bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) { return false; if (isa<MallocInst>(I)) - // MallocInst claims not to write memory! PR3754. + // malloc claims not to write memory! PR3754. return false; // If this instruction may read memory, remember that. @@ -226,9 +226,7 @@ bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) { /// IsFunctionMallocLike - A function is malloc-like if it returns either null /// or a pointer that doesn't alias any other pointer visible to the caller. bool FunctionAttrs::IsFunctionMallocLike(Function *F, - SmallPtrSet<CallGraphNode*, 8> &SCCNodes) const { - CallGraph &CG = getAnalysis<CallGraph>(); - + SmallPtrSet<Function*, 8> &SCCNodes) const { UniqueVector<Value *> FlowsToReturn; for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) @@ -250,32 +248,36 @@ bool FunctionAttrs::IsFunctionMallocLike(Function *F, if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) switch (RVI->getOpcode()) { // Extend the analysis by looking upwards. - case Instruction::GetElementPtr: case Instruction::BitCast: + case Instruction::GetElementPtr: FlowsToReturn.insert(RVI->getOperand(0)); continue; case Instruction::Select: { SelectInst *SI = cast<SelectInst>(RVI); FlowsToReturn.insert(SI->getTrueValue()); FlowsToReturn.insert(SI->getFalseValue()); - } continue; + continue; + } case Instruction::PHI: { PHINode *PN = cast<PHINode>(RVI); for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) FlowsToReturn.insert(PN->getIncomingValue(i)); - } continue; + continue; + } // Check whether the pointer came from an allocation. case Instruction::Alloca: case Instruction::Malloc: break; case Instruction::Call: + if (isMalloc(RVI)) + break; case Instruction::Invoke: { CallSite CS(RVI); if (CS.paramHasAttr(0, Attribute::NoAlias)) break; if (CS.getCalledFunction() && - SCCNodes.count(CG[CS.getCalledFunction()])) + SCCNodes.count(CS.getCalledFunction())) break; } // fall-through default: @@ -291,12 +293,12 @@ bool FunctionAttrs::IsFunctionMallocLike(Function *F, /// AddNoAliasAttrs - Deduce noalias attributes for the SCC. bool FunctionAttrs::AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC) { - SmallPtrSet<CallGraphNode*, 8> SCCNodes; + SmallPtrSet<Function*, 8> SCCNodes; // Fill SCCNodes with the elements of the SCC. Used for quickly // looking up whether a given CallGraphNode is in this SCC. for (unsigned i = 0, e = SCC.size(); i != e; ++i) - SCCNodes.insert(SCC[i]); + SCCNodes.insert(SCC[i]->getFunction()); // Check each function in turn, determining which functions return noalias // pointers. @@ -339,7 +341,7 @@ bool FunctionAttrs::AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC) { return MadeChange; } -bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) { +bool FunctionAttrs::runOnSCC(std::vector<CallGraphNode *> &SCC) { bool Changed = AddReadAttrs(SCC); Changed |= AddNoCaptureAttrs(SCC); Changed |= AddNoAliasAttrs(SCC); diff --git a/lib/Transforms/IPO/GlobalDCE.cpp b/lib/Transforms/IPO/GlobalDCE.cpp index 9c652b9..09f9e7c 100644 --- a/lib/Transforms/IPO/GlobalDCE.cpp +++ b/lib/Transforms/IPO/GlobalDCE.cpp @@ -58,6 +58,7 @@ ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); } bool GlobalDCE::runOnModule(Module &M) { bool Changed = false; + // Loop over the module, adding globals which are obviously necessary. for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { Changed |= RemoveUnusedGlobalValue(*I); @@ -147,6 +148,9 @@ bool GlobalDCE::runOnModule(Module &M) { // Make sure that all memory is released AliveGlobals.clear(); + + // Remove dead metadata. + Changed |= M.getContext().RemoveDeadMetadata(); return Changed; } diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp index 7fe097c..a44386e 100644 --- a/lib/Transforms/IPO/GlobalOpt.cpp +++ b/lib/Transforms/IPO/GlobalOpt.cpp @@ -20,20 +20,23 @@ #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/MallocHelper.h" #include "llvm/Target/TargetData.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/STLExtras.h" #include <algorithm> using namespace llvm; @@ -56,7 +59,6 @@ STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated"); namespace { struct VISIBILITY_HIDDEN GlobalOpt : public ModulePass { virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<TargetData>(); } static char ID; // Pass identification, replacement for typeid GlobalOpt() : ModulePass(&ID) {} @@ -244,7 +246,8 @@ static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, return false; } -static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) { +static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx, + LLVMContext &Context) { ConstantInt *CI = dyn_cast<ConstantInt>(Idx); if (!CI) return 0; unsigned IdxV = CI->getZExtValue(); @@ -280,7 +283,8 @@ static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) { /// users of the global, cleaning up the obvious ones. This is largely just a /// quick scan over the use list to clean up the easy and obvious cruft. This /// returns true if it made a change. -static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) { +static bool CleanupConstantGlobalUsers(Value *V, Constant *Init, + LLVMContext &Context) { bool Changed = false; for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) { User *U = *UI++; @@ -301,11 +305,11 @@ static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) { Constant *SubInit = 0; if (Init) SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); - Changed |= CleanupConstantGlobalUsers(CE, SubInit); + Changed |= CleanupConstantGlobalUsers(CE, SubInit, Context); } else if (CE->getOpcode() == Instruction::BitCast && isa<PointerType>(CE->getType())) { // Pointer cast, delete any stores and memsets to the global. - Changed |= CleanupConstantGlobalUsers(CE, 0); + Changed |= CleanupConstantGlobalUsers(CE, 0, Context); } if (CE->use_empty()) { @@ -319,11 +323,11 @@ static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) { Constant *SubInit = 0; if (!isa<ConstantExpr>(GEP->getOperand(0))) { ConstantExpr *CE = - dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP)); + dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, Context)); if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr) SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); } - Changed |= CleanupConstantGlobalUsers(GEP, SubInit); + Changed |= CleanupConstantGlobalUsers(GEP, SubInit, Context); if (GEP->use_empty()) { GEP->eraseFromParent(); @@ -341,7 +345,7 @@ static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) { if (SafeToDestroyConstant(C)) { C->destroyConstant(); // This could have invalidated UI, start over from scratch. - CleanupConstantGlobalUsers(V, Init); + CleanupConstantGlobalUsers(V, Init, Context); return true; } } @@ -423,13 +427,18 @@ static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) { // Scalar replacing *just* the outer index of the array is probably not // going to be a win anyway, so just give up. for (++GEPI; // Skip array index. - GEPI != E && (isa<ArrayType>(*GEPI) || isa<VectorType>(*GEPI)); + GEPI != E; ++GEPI) { uint64_t NumElements; if (const ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI)) NumElements = SubArrayTy->getNumElements(); - else - NumElements = cast<VectorType>(*GEPI)->getNumElements(); + else if (const VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI)) + NumElements = SubVectorTy->getNumElements(); + else { + assert(isa<StructType>(*GEPI) && + "Indexed GEP type is not array, vector, or struct!"); + continue; + } ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand()); if (!IdxVal || IdxVal->getZExtValue() >= NumElements) @@ -461,7 +470,8 @@ static bool GlobalUsersSafeToSRA(GlobalValue *GV) { /// behavior of the program in a more fine-grained way. We have determined that /// this transformation is safe already. We return the first global variable we /// insert so that the caller can reprocess it. -static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD) { +static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD, + LLVMContext &Context) { // Make sure this global only has simple uses that we can SRA. if (!GlobalUsersSafeToSRA(GV)) return 0; @@ -483,14 +493,15 @@ static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD) { const StructLayout &Layout = *TD.getStructLayout(STy); for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { Constant *In = getAggregateConstantElement(Init, - ConstantInt::get(Type::Int32Ty, i)); + ConstantInt::get(Type::getInt32Ty(Context), i), + Context); assert(In && "Couldn't get element of initializer?"); - GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false, + GlobalVariable *NGV = new GlobalVariable(Context, + STy->getElementType(i), false, GlobalVariable::InternalLinkage, - In, GV->getName()+"."+utostr(i), - (Module *)NULL, + In, GV->getName()+"."+Twine(i), GV->isThreadLocal(), - GV->getType()->getAddressSpace()); + GV->getType()->getAddressSpace()); Globals.insert(GV, NGV); NewGlobals.push_back(NGV); @@ -517,15 +528,16 @@ static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD) { unsigned EltAlign = TD.getABITypeAlignment(STy->getElementType()); for (unsigned i = 0, e = NumElements; i != e; ++i) { Constant *In = getAggregateConstantElement(Init, - ConstantInt::get(Type::Int32Ty, i)); + ConstantInt::get(Type::getInt32Ty(Context), i), + Context); assert(In && "Couldn't get element of initializer?"); - GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false, + GlobalVariable *NGV = new GlobalVariable(Context, + STy->getElementType(), false, GlobalVariable::InternalLinkage, - In, GV->getName()+"."+utostr(i), - (Module *)NULL, + In, GV->getName()+"."+Twine(i), GV->isThreadLocal(), - GV->getType()->getAddressSpace()); + GV->getType()->getAddressSpace()); Globals.insert(GV, NGV); NewGlobals.push_back(NGV); @@ -541,9 +553,9 @@ static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD) { if (NewGlobals.empty()) return 0; - DOUT << "PERFORMING GLOBAL SRA ON: " << *GV; + DEBUG(errs() << "PERFORMING GLOBAL SRA ON: " << *GV); - Constant *NullInt = Constant::getNullValue(Type::Int32Ty); + Constant *NullInt = Constant::getNullValue(Type::getInt32Ty(Context)); // Loop over all of the uses of the global, replacing the constantexpr geps, // with smaller constantexpr geps or direct references. @@ -577,7 +589,7 @@ static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD) { for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) Idxs.push_back(GEPI->getOperand(i)); NewPtr = GetElementPtrInst::Create(NewPtr, Idxs.begin(), Idxs.end(), - GEPI->getName()+"."+utostr(Val), GEPI); + GEPI->getName()+"."+Twine(Val),GEPI); } } GEP->replaceAllUsesWith(NewPtr); @@ -667,7 +679,8 @@ static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) { return true; } -static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { +static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV, + LLVMContext &Context) { bool Changed = false; for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { Instruction *I = cast<Instruction>(*UI++); @@ -700,7 +713,7 @@ static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { } else if (CastInst *CI = dyn_cast<CastInst>(I)) { Changed |= OptimizeAwayTrappingUsesOfValue(CI, ConstantExpr::getCast(CI->getOpcode(), - NewV, CI->getType())); + NewV, CI->getType()), Context); if (CI->use_empty()) { Changed = true; CI->eraseFromParent(); @@ -717,8 +730,8 @@ static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { break; if (Idxs.size() == GEPI->getNumOperands()-1) Changed |= OptimizeAwayTrappingUsesOfValue(GEPI, - ConstantExpr::getGetElementPtr(NewV, &Idxs[0], - Idxs.size())); + ConstantExpr::getGetElementPtr(NewV, &Idxs[0], + Idxs.size()), Context); if (GEPI->use_empty()) { Changed = true; GEPI->eraseFromParent(); @@ -734,7 +747,8 @@ static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { /// value stored into it. If there are uses of the loaded value that would trap /// if the loaded value is dynamically null, then we know that they cannot be /// reachable with a null optimize away the load. -static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) { +static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV, + LLVMContext &Context) { bool Changed = false; // Keep track of whether we are able to remove all the uses of the global @@ -745,7 +759,7 @@ static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) { for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); GUI != E;){ User *GlobalUser = *GUI++; if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) { - Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV); + Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV, Context); // If we were able to delete all uses of the loads if (LI->use_empty()) { LI->eraseFromParent(); @@ -768,15 +782,15 @@ static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) { } if (Changed) { - DOUT << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV; + DEBUG(errs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV); ++NumGlobUses; } // If we nuked all of the loads, then none of the stores are needed either, // nor is the global. if (AllNonStoreUsesGone) { - DOUT << " *** GLOBAL NOW DEAD!\n"; - CleanupConstantGlobalUsers(GV, 0); + DEBUG(errs() << " *** GLOBAL NOW DEAD!\n"); + CleanupConstantGlobalUsers(GV, 0, Context); if (GV->use_empty()) { GV->eraseFromParent(); ++NumDeleted; @@ -788,10 +802,10 @@ static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) { /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the /// instructions that are foldable. -static void ConstantPropUsersOf(Value *V) { +static void ConstantPropUsersOf(Value *V, LLVMContext &Context) { for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) if (Instruction *I = dyn_cast<Instruction>(*UI++)) - if (Constant *NewC = ConstantFoldInstruction(I)) { + if (Constant *NewC = ConstantFoldInstruction(I, Context)) { I->replaceAllUsesWith(NewC); // Advance UI to the next non-I use to avoid invalidating it! @@ -808,8 +822,9 @@ static void ConstantPropUsersOf(Value *V) { /// malloc, there is no reason to actually DO the malloc. Instead, turn the /// malloc into a global, and any loads of GV as uses of the new global. static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, - MallocInst *MI) { - DOUT << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " << *MI; + MallocInst *MI, + LLVMContext &Context) { + DEBUG(errs() << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " << *MI); ConstantInt *NElements = cast<ConstantInt>(MI->getArraySize()); if (NElements->getZExtValue() != 1) { @@ -818,10 +833,10 @@ static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, Type *NewTy = ArrayType::get(MI->getAllocatedType(), NElements->getZExtValue()); MallocInst *NewMI = - new MallocInst(NewTy, Constant::getNullValue(Type::Int32Ty), + new MallocInst(NewTy, Constant::getNullValue(Type::getInt32Ty(Context)), MI->getAlignment(), MI->getName(), MI); Value* Indices[2]; - Indices[0] = Indices[1] = Constant::getNullValue(Type::Int32Ty); + Indices[0] = Indices[1] = Constant::getNullValue(Type::getInt32Ty(Context)); Value *NewGEP = GetElementPtrInst::Create(NewMI, Indices, Indices + 2, NewMI->getName()+".el0", MI); MI->replaceAllUsesWith(NewGEP); @@ -831,17 +846,17 @@ static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, // Create the new global variable. The contents of the malloc'd memory is // undefined, so initialize with an undef value. + // FIXME: This new global should have the alignment returned by malloc. Code + // could depend on malloc returning large alignment (on the mac, 16 bytes) but + // this would only guarantee some lower alignment. Constant *Init = UndefValue::get(MI->getAllocatedType()); - GlobalVariable *NewGV = new GlobalVariable(MI->getAllocatedType(), false, + GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(), + MI->getAllocatedType(), false, GlobalValue::InternalLinkage, Init, GV->getName()+".body", - (Module *)NULL, + GV, GV->isThreadLocal()); - // FIXME: This new global should have the alignment returned by malloc. Code - // could depend on malloc returning large alignment (on the mac, 16 bytes) but - // this would only guarantee some lower alignment. - GV->getParent()->getGlobalList().insert(GV, NewGV); - + // Anything that used the malloc now uses the global directly. MI->replaceAllUsesWith(NewGV); @@ -853,9 +868,10 @@ static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, // If there is a comparison against null, we will insert a global bool to // keep track of whether the global was initialized yet or not. GlobalVariable *InitBool = - new GlobalVariable(Type::Int1Ty, false, GlobalValue::InternalLinkage, - ConstantInt::getFalse(), GV->getName()+".init", - (Module *)NULL, GV->isThreadLocal()); + new GlobalVariable(Context, Type::getInt1Ty(Context), false, + GlobalValue::InternalLinkage, + ConstantInt::getFalse(Context), GV->getName()+".init", + GV->isThreadLocal()); bool InitBoolUsed = false; // Loop over all uses of GV, processing them in turn. @@ -872,10 +888,10 @@ static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", CI); InitBoolUsed = true; switch (CI->getPredicate()) { - default: assert(0 && "Unknown ICmp Predicate!"); + default: llvm_unreachable("Unknown ICmp Predicate!"); case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_SLT: - LV = ConstantInt::getFalse(); // X < null -> always false + LV = ConstantInt::getFalse(Context); // X < null -> always false break; case ICmpInst::ICMP_ULE: case ICmpInst::ICMP_SLE: @@ -897,7 +913,7 @@ static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, } else { StoreInst *SI = cast<StoreInst>(GV->use_back()); // The global is initialized when the store to it occurs. - new StoreInst(ConstantInt::getTrue(), InitBool, SI); + new StoreInst(ConstantInt::getTrue(Context), InitBool, SI); SI->eraseFromParent(); } @@ -917,9 +933,141 @@ static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, // To further other optimizations, loop over all users of NewGV and try to // constant prop them. This will promote GEP instructions with constant // indices into GEP constant-exprs, which will allow global-opt to hack on it. - ConstantPropUsersOf(NewGV); + ConstantPropUsersOf(NewGV, Context); if (RepValue != NewGV) - ConstantPropUsersOf(RepValue); + ConstantPropUsersOf(RepValue, Context); + + return NewGV; +} + +/// OptimizeGlobalAddressOfMalloc - This function takes the specified global +/// variable, and transforms the program as if it always contained the result of +/// the specified malloc. Because it is always the result of the specified +/// malloc, there is no reason to actually DO the malloc. Instead, turn the +/// malloc into a global, and any loads of GV as uses of the new global. +static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, + CallInst *CI, + BitCastInst *BCI, + LLVMContext &Context, + TargetData* TD) { + const Type *IntPtrTy = TD->getIntPtrType(Context); + + DEBUG(errs() << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " << *CI); + + ConstantInt *NElements = cast<ConstantInt>(getMallocArraySize(CI, + Context, TD)); + if (NElements->getZExtValue() != 1) { + // If we have an array allocation, transform it to a single element + // allocation to make the code below simpler. + Type *NewTy = ArrayType::get(getMallocAllocatedType(CI), + NElements->getZExtValue()); + Value* NewM = CallInst::CreateMalloc(CI, IntPtrTy, NewTy); + Instruction* NewMI = cast<Instruction>(NewM); + Value* Indices[2]; + Indices[0] = Indices[1] = Constant::getNullValue(IntPtrTy); + Value *NewGEP = GetElementPtrInst::Create(NewMI, Indices, Indices + 2, + NewMI->getName()+".el0", CI); + BCI->replaceAllUsesWith(NewGEP); + BCI->eraseFromParent(); + CI->eraseFromParent(); + BCI = cast<BitCastInst>(NewMI); + CI = extractMallocCallFromBitCast(NewMI); + } + + // Create the new global variable. The contents of the malloc'd memory is + // undefined, so initialize with an undef value. + // FIXME: This new global should have the alignment returned by malloc. Code + // could depend on malloc returning large alignment (on the mac, 16 bytes) but + // this would only guarantee some lower alignment. + const Type *MAT = getMallocAllocatedType(CI); + Constant *Init = UndefValue::get(MAT); + GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(), + MAT, false, + GlobalValue::InternalLinkage, Init, + GV->getName()+".body", + GV, + GV->isThreadLocal()); + + // Anything that used the malloc now uses the global directly. + BCI->replaceAllUsesWith(NewGV); + + Constant *RepValue = NewGV; + if (NewGV->getType() != GV->getType()->getElementType()) + RepValue = ConstantExpr::getBitCast(RepValue, + GV->getType()->getElementType()); + + // If there is a comparison against null, we will insert a global bool to + // keep track of whether the global was initialized yet or not. + GlobalVariable *InitBool = + new GlobalVariable(Context, Type::getInt1Ty(Context), false, + GlobalValue::InternalLinkage, + ConstantInt::getFalse(Context), GV->getName()+".init", + GV->isThreadLocal()); + bool InitBoolUsed = false; + + // Loop over all uses of GV, processing them in turn. + std::vector<StoreInst*> Stores; + while (!GV->use_empty()) + if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) { + while (!LI->use_empty()) { + Use &LoadUse = LI->use_begin().getUse(); + if (!isa<ICmpInst>(LoadUse.getUser())) + LoadUse = RepValue; + else { + ICmpInst *ICI = cast<ICmpInst>(LoadUse.getUser()); + // Replace the cmp X, 0 with a use of the bool value. + Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", ICI); + InitBoolUsed = true; + switch (ICI->getPredicate()) { + default: llvm_unreachable("Unknown ICmp Predicate!"); + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_SLT: + LV = ConstantInt::getFalse(Context); // X < null -> always false + break; + case ICmpInst::ICMP_ULE: + case ICmpInst::ICMP_SLE: + case ICmpInst::ICMP_EQ: + LV = BinaryOperator::CreateNot(LV, "notinit", ICI); + break; + case ICmpInst::ICMP_NE: + case ICmpInst::ICMP_UGE: + case ICmpInst::ICMP_SGE: + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_SGT: + break; // no change. + } + ICI->replaceAllUsesWith(LV); + ICI->eraseFromParent(); + } + } + LI->eraseFromParent(); + } else { + StoreInst *SI = cast<StoreInst>(GV->use_back()); + // The global is initialized when the store to it occurs. + new StoreInst(ConstantInt::getTrue(Context), InitBool, SI); + SI->eraseFromParent(); + } + + // If the initialization boolean was used, insert it, otherwise delete it. + if (!InitBoolUsed) { + while (!InitBool->use_empty()) // Delete initializations + cast<Instruction>(InitBool->use_back())->eraseFromParent(); + delete InitBool; + } else + GV->getParent()->getGlobalList().insert(GV, InitBool); + + + // Now the GV is dead, nuke it and the malloc. + GV->eraseFromParent(); + BCI->eraseFromParent(); + CI->eraseFromParent(); + + // To further other optimizations, loop over all users of NewGV and try to + // constant prop them. This will promote GEP instructions with constant + // indices into GEP constant-exprs, which will allow global-opt to hack on it. + ConstantPropUsersOf(NewGV, Context); + if (RepValue != NewGV) + ConstantPropUsersOf(RepValue, Context); return NewGV; } @@ -1071,7 +1219,7 @@ static bool LoadUsesSimpleEnoughForHeapSRA(Value *V, /// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from /// GV are simple enough to perform HeapSRA, return true. static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV, - MallocInst *MI) { + Instruction *StoredVal) { SmallPtrSet<PHINode*, 32> LoadUsingPHIs; SmallPtrSet<PHINode*, 32> LoadUsingPHIsPerLoad; for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E; @@ -1095,7 +1243,7 @@ static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV, Value *InVal = PN->getIncomingValue(op); // PHI of the stored value itself is ok. - if (InVal == MI) continue; + if (InVal == StoredVal) continue; if (PHINode *InPN = dyn_cast<PHINode>(InVal)) { // One of the PHIs in our set is (optimistically) ok. @@ -1121,7 +1269,8 @@ static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV, static Value *GetHeapSROAValue(Value *V, unsigned FieldNo, DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, - std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { + std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite, + LLVMContext &Context) { std::vector<Value*> &FieldVals = InsertedScalarizedValues[V]; if (FieldNo >= FieldVals.size()) @@ -1139,19 +1288,20 @@ static Value *GetHeapSROAValue(Value *V, unsigned FieldNo, // a new Load of the scalarized global. Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo, InsertedScalarizedValues, - PHIsToRewrite), - LI->getName()+".f" + utostr(FieldNo), LI); + PHIsToRewrite, Context), + LI->getName()+".f"+Twine(FieldNo), LI); } else if (PHINode *PN = dyn_cast<PHINode>(V)) { // PN's type is pointer to struct. Make a new PHI of pointer to struct // field. const StructType *ST = cast<StructType>(cast<PointerType>(PN->getType())->getElementType()); - Result =PHINode::Create(PointerType::getUnqual(ST->getElementType(FieldNo)), - PN->getName()+".f"+utostr(FieldNo), PN); + Result = + PHINode::Create(PointerType::getUnqual(ST->getElementType(FieldNo)), + PN->getName()+".f"+Twine(FieldNo), PN); PHIsToRewrite.push_back(std::make_pair(PN, FieldNo)); } else { - assert(0 && "Unknown usable value"); + llvm_unreachable("Unknown usable value"); Result = 0; } @@ -1162,18 +1312,20 @@ static Value *GetHeapSROAValue(Value *V, unsigned FieldNo, /// the load, rewrite the derived value to use the HeapSRoA'd load. static void RewriteHeapSROALoadUser(Instruction *LoadUser, DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, - std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { + std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite, + LLVMContext &Context) { // If this is a comparison against null, handle it. if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) { assert(isa<ConstantPointerNull>(SCI->getOperand(1))); // If we have a setcc of the loaded pointer, we can use a setcc of any // field. Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0, - InsertedScalarizedValues, PHIsToRewrite); + InsertedScalarizedValues, PHIsToRewrite, + Context); - Value *New = new ICmpInst(SCI->getPredicate(), NPtr, - Constant::getNullValue(NPtr->getType()), - SCI->getName(), SCI); + Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr, + Constant::getNullValue(NPtr->getType()), + SCI->getName()); SCI->replaceAllUsesWith(New); SCI->eraseFromParent(); return; @@ -1187,7 +1339,8 @@ static void RewriteHeapSROALoadUser(Instruction *LoadUser, // Load the pointer for this field. unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo, - InsertedScalarizedValues, PHIsToRewrite); + InsertedScalarizedValues, PHIsToRewrite, + Context); // Create the new GEP idx vector. SmallVector<Value*, 8> GEPIdx; @@ -1219,7 +1372,8 @@ static void RewriteHeapSROALoadUser(Instruction *LoadUser, // users. for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; ) { Instruction *User = cast<Instruction>(*UI++); - RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); + RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite, + Context); } } @@ -1229,11 +1383,13 @@ static void RewriteHeapSROALoadUser(Instruction *LoadUser, /// AllGlobalLoadUsesSimpleEnoughForHeapSRA. static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, - std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { + std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite, + LLVMContext &Context) { for (Value::use_iterator UI = Load->use_begin(), E = Load->use_end(); UI != E; ) { Instruction *User = cast<Instruction>(*UI++); - RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); + RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite, + Context); } if (Load->use_empty()) { @@ -1244,8 +1400,9 @@ static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, /// PerformHeapAllocSRoA - MI is an allocation of an array of structures. Break /// it up into multiple allocations of arrays of the fields. -static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ - DOUT << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *MI; +static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI, + LLVMContext &Context){ + DEBUG(errs() << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *MI); const StructType *STy = cast<StructType>(MI->getAllocatedType()); // There is guaranteed to be at least one use of the malloc (storing @@ -1264,14 +1421,15 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ const Type *PFieldTy = PointerType::getUnqual(FieldTy); GlobalVariable *NGV = - new GlobalVariable(PFieldTy, false, GlobalValue::InternalLinkage, + new GlobalVariable(*GV->getParent(), + PFieldTy, false, GlobalValue::InternalLinkage, Constant::getNullValue(PFieldTy), - GV->getName() + ".f" + utostr(FieldNo), GV, + GV->getName() + ".f" + Twine(FieldNo), GV, GV->isThreadLocal()); FieldGlobals.push_back(NGV); MallocInst *NMI = new MallocInst(FieldTy, MI->getArraySize(), - MI->getName() + ".f" + utostr(FieldNo),MI); + MI->getName() + ".f" + Twine(FieldNo), MI); FieldMallocs.push_back(NMI); new StoreInst(NMI, NGV, MI); } @@ -1290,9 +1448,9 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ // } Value *RunningOr = 0; for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) { - Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, FieldMallocs[i], - Constant::getNullValue(FieldMallocs[i]->getType()), - "isnull", MI); + Value *Cond = new ICmpInst(MI, ICmpInst::ICMP_EQ, FieldMallocs[i], + Constant::getNullValue(FieldMallocs[i]->getType()), + "isnull"); if (!RunningOr) RunningOr = Cond; // First seteq else @@ -1305,7 +1463,7 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ // Create the block to check the first condition. Put all these blocks at the // end of the function as they are unlikely to be executed. - BasicBlock *NullPtrBlock = BasicBlock::Create("malloc_ret_null", + BasicBlock *NullPtrBlock = BasicBlock::Create(Context, "malloc_ret_null", OrigBB->getParent()); // Remove the uncond branch from OrigBB to ContBB, turning it into a cond @@ -1317,11 +1475,13 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ // pointer, because some may be null while others are not. for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock); - Value *Cmp = new ICmpInst(ICmpInst::ICMP_NE, GVVal, + Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal, Constant::getNullValue(GVVal->getType()), - "tmp", NullPtrBlock); - BasicBlock *FreeBlock = BasicBlock::Create("free_it", OrigBB->getParent()); - BasicBlock *NextBlock = BasicBlock::Create("next", OrigBB->getParent()); + "tmp"); + BasicBlock *FreeBlock = BasicBlock::Create(Context, "free_it", + OrigBB->getParent()); + BasicBlock *NextBlock = BasicBlock::Create(Context, "next", + OrigBB->getParent()); BranchInst::Create(FreeBlock, NextBlock, Cmp, NullPtrBlock); // Fill in FreeBlock. @@ -1353,7 +1513,8 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ Instruction *User = cast<Instruction>(*UI++); if (LoadInst *LI = dyn_cast<LoadInst>(User)) { - RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite); + RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite, + Context); continue; } @@ -1384,7 +1545,192 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { Value *InVal = PN->getIncomingValue(i); InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues, - PHIsToRewrite); + PHIsToRewrite, Context); + FieldPN->addIncoming(InVal, PN->getIncomingBlock(i)); + } + } + + // Drop all inter-phi links and any loads that made it this far. + for (DenseMap<Value*, std::vector<Value*> >::iterator + I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); + I != E; ++I) { + if (PHINode *PN = dyn_cast<PHINode>(I->first)) + PN->dropAllReferences(); + else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) + LI->dropAllReferences(); + } + + // Delete all the phis and loads now that inter-references are dead. + for (DenseMap<Value*, std::vector<Value*> >::iterator + I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); + I != E; ++I) { + if (PHINode *PN = dyn_cast<PHINode>(I->first)) + PN->eraseFromParent(); + else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) + LI->eraseFromParent(); + } + + // The old global is now dead, remove it. + GV->eraseFromParent(); + + ++NumHeapSRA; + return cast<GlobalVariable>(FieldGlobals[0]); +} + +/// PerformHeapAllocSRoA - CI is an allocation of an array of structures. Break +/// it up into multiple allocations of arrays of the fields. +static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, + CallInst *CI, BitCastInst* BCI, + LLVMContext &Context, + TargetData *TD){ + DEBUG(errs() << "SROA HEAP ALLOC: " << *GV << " MALLOC CALL = " << *CI + << " BITCAST = " << *BCI << '\n'); + const Type* MAT = getMallocAllocatedType(CI); + const StructType *STy = cast<StructType>(MAT); + + // There is guaranteed to be at least one use of the malloc (storing + // it into GV). If there are other uses, change them to be uses of + // the global to simplify later code. This also deletes the store + // into GV. + ReplaceUsesOfMallocWithGlobal(BCI, GV); + + // Okay, at this point, there are no users of the malloc. Insert N + // new mallocs at the same place as CI, and N globals. + std::vector<Value*> FieldGlobals; + std::vector<Value*> FieldMallocs; + + for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){ + const Type *FieldTy = STy->getElementType(FieldNo); + const PointerType *PFieldTy = PointerType::getUnqual(FieldTy); + + GlobalVariable *NGV = + new GlobalVariable(*GV->getParent(), + PFieldTy, false, GlobalValue::InternalLinkage, + Constant::getNullValue(PFieldTy), + GV->getName() + ".f" + Twine(FieldNo), GV, + GV->isThreadLocal()); + FieldGlobals.push_back(NGV); + + Value *NMI = CallInst::CreateMalloc(CI, TD->getIntPtrType(Context), FieldTy, + getMallocArraySize(CI, Context, TD), + BCI->getName() + ".f" + Twine(FieldNo)); + FieldMallocs.push_back(NMI); + new StoreInst(NMI, NGV, BCI); + } + + // The tricky aspect of this transformation is handling the case when malloc + // fails. In the original code, malloc failing would set the result pointer + // of malloc to null. In this case, some mallocs could succeed and others + // could fail. As such, we emit code that looks like this: + // F0 = malloc(field0) + // F1 = malloc(field1) + // F2 = malloc(field2) + // if (F0 == 0 || F1 == 0 || F2 == 0) { + // if (F0) { free(F0); F0 = 0; } + // if (F1) { free(F1); F1 = 0; } + // if (F2) { free(F2); F2 = 0; } + // } + Value *RunningOr = 0; + for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) { + Value *Cond = new ICmpInst(BCI, ICmpInst::ICMP_EQ, FieldMallocs[i], + Constant::getNullValue(FieldMallocs[i]->getType()), + "isnull"); + if (!RunningOr) + RunningOr = Cond; // First seteq + else + RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", BCI); + } + + // Split the basic block at the old malloc. + BasicBlock *OrigBB = BCI->getParent(); + BasicBlock *ContBB = OrigBB->splitBasicBlock(BCI, "malloc_cont"); + + // Create the block to check the first condition. Put all these blocks at the + // end of the function as they are unlikely to be executed. + BasicBlock *NullPtrBlock = BasicBlock::Create(Context, "malloc_ret_null", + OrigBB->getParent()); + + // Remove the uncond branch from OrigBB to ContBB, turning it into a cond + // branch on RunningOr. + OrigBB->getTerminator()->eraseFromParent(); + BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB); + + // Within the NullPtrBlock, we need to emit a comparison and branch for each + // pointer, because some may be null while others are not. + for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { + Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock); + Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal, + Constant::getNullValue(GVVal->getType()), + "tmp"); + BasicBlock *FreeBlock = BasicBlock::Create(Context, "free_it", + OrigBB->getParent()); + BasicBlock *NextBlock = BasicBlock::Create(Context, "next", + OrigBB->getParent()); + BranchInst::Create(FreeBlock, NextBlock, Cmp, NullPtrBlock); + + // Fill in FreeBlock. + new FreeInst(GVVal, FreeBlock); + new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i], + FreeBlock); + BranchInst::Create(NextBlock, FreeBlock); + + NullPtrBlock = NextBlock; + } + + BranchInst::Create(ContBB, NullPtrBlock); + + // CI and BCI are no longer needed, remove them. + BCI->eraseFromParent(); + CI->eraseFromParent(); + + /// InsertedScalarizedLoads - As we process loads, if we can't immediately + /// update all uses of the load, keep track of what scalarized loads are + /// inserted for a given load. + DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues; + InsertedScalarizedValues[GV] = FieldGlobals; + + std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite; + + // Okay, the malloc site is completely handled. All of the uses of GV are now + // loads, and all uses of those loads are simple. Rewrite them to use loads + // of the per-field globals instead. + for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;) { + Instruction *User = cast<Instruction>(*UI++); + + if (LoadInst *LI = dyn_cast<LoadInst>(User)) { + RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite, + Context); + continue; + } + + // Must be a store of null. + StoreInst *SI = cast<StoreInst>(User); + assert(isa<ConstantPointerNull>(SI->getOperand(0)) && + "Unexpected heap-sra user!"); + + // Insert a store of null into each global. + for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { + const PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType()); + Constant *Null = Constant::getNullValue(PT->getElementType()); + new StoreInst(Null, FieldGlobals[i], SI); + } + // Erase the original store. + SI->eraseFromParent(); + } + + // While we have PHIs that are interesting to rewrite, do it. + while (!PHIsToRewrite.empty()) { + PHINode *PN = PHIsToRewrite.back().first; + unsigned FieldNo = PHIsToRewrite.back().second; + PHIsToRewrite.pop_back(); + PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]); + assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi"); + + // Add all the incoming values. This can materialize more phis. + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + Value *InVal = PN->getIncomingValue(i); + InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues, + PHIsToRewrite, Context); FieldPN->addIncoming(InVal, PN->getIncomingBlock(i)); } } @@ -1422,7 +1768,8 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, MallocInst *MI, Module::global_iterator &GVI, - TargetData &TD) { + TargetData *TD, + LLVMContext &Context) { // If this is a malloc of an abstract type, don't touch it. if (!MI->getAllocatedType()->isSized()) return false; @@ -1456,9 +1803,10 @@ static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, // Restrict this transformation to only working on small allocations // (2048 bytes currently), as we don't want to introduce a 16M global or // something. - if (NElements->getZExtValue()* - TD.getTypeAllocSize(MI->getAllocatedType()) < 2048) { - GVI = OptimizeGlobalAddressOfMalloc(GV, MI); + if (TD && + NElements->getZExtValue()* + TD->getTypeAllocSize(MI->getAllocatedType()) < 2048) { + GVI = OptimizeGlobalAddressOfMalloc(GV, MI, Context); return true; } } @@ -1485,7 +1833,8 @@ static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, if (const ArrayType *AT = dyn_cast<ArrayType>(MI->getAllocatedType())) { MallocInst *NewMI = new MallocInst(AllocSTy, - ConstantInt::get(Type::Int32Ty, AT->getNumElements()), + ConstantInt::get(Type::getInt32Ty(Context), + AT->getNumElements()), "", MI); NewMI->takeName(MI); Value *Cast = new BitCastInst(NewMI, MI->getType(), "tmp", MI); @@ -1494,7 +1843,100 @@ static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, MI = NewMI; } - GVI = PerformHeapAllocSRoA(GV, MI); + GVI = PerformHeapAllocSRoA(GV, MI, Context); + return true; + } + } + + return false; +} + +/// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a +/// pointer global variable with a single value stored it that is a malloc or +/// cast of malloc. +static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, + CallInst *CI, + BitCastInst *BCI, + Module::global_iterator &GVI, + TargetData *TD, + LLVMContext &Context) { + // If we can't figure out the type being malloced, then we can't optimize. + const Type *AllocTy = getMallocAllocatedType(CI); + assert(AllocTy); + + // If this is a malloc of an abstract type, don't touch it. + if (!AllocTy->isSized()) + return false; + + // We can't optimize this global unless all uses of it are *known* to be + // of the malloc value, not of the null initializer value (consider a use + // that compares the global's value against zero to see if the malloc has + // been reached). To do this, we check to see if all uses of the global + // would trap if the global were null: this proves that they must all + // happen after the malloc. + if (!AllUsesOfLoadedValueWillTrapIfNull(GV)) + return false; + + // We can't optimize this if the malloc itself is used in a complex way, + // for example, being stored into multiple globals. This allows the + // malloc to be stored into the specified global, loaded setcc'd, and + // GEP'd. These are all things we could transform to using the global + // for. + { + SmallPtrSet<PHINode*, 8> PHIs; + if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs)) + return false; + } + + // If we have a global that is only initialized with a fixed size malloc, + // transform the program to use global memory instead of malloc'd memory. + // This eliminates dynamic allocation, avoids an indirection accessing the + // data, and exposes the resultant global to further GlobalOpt. + if (ConstantInt *NElements = + dyn_cast<ConstantInt>(getMallocArraySize(CI, Context, TD))) { + // Restrict this transformation to only working on small allocations + // (2048 bytes currently), as we don't want to introduce a 16M global or + // something. + if (TD && + NElements->getZExtValue() * TD->getTypeAllocSize(AllocTy) < 2048) { + GVI = OptimizeGlobalAddressOfMalloc(GV, CI, BCI, Context, TD); + return true; + } + } + + // If the allocation is an array of structures, consider transforming this + // into multiple malloc'd arrays, one for each field. This is basically + // SRoA for malloc'd memory. + + // If this is an allocation of a fixed size array of structs, analyze as a + // variable size array. malloc [100 x struct],1 -> malloc struct, 100 + if (!isArrayMalloc(CI, Context, TD)) + if (const ArrayType *AT = dyn_cast<ArrayType>(AllocTy)) + AllocTy = AT->getElementType(); + + if (const StructType *AllocSTy = dyn_cast<StructType>(AllocTy)) { + // This the structure has an unreasonable number of fields, leave it + // alone. + if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 && + AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, BCI)) { + + // If this is a fixed size array, transform the Malloc to be an alloc of + // structs. malloc [100 x struct],1 -> malloc struct, 100 + if (const ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI))) { + Value* NumElements = ConstantInt::get(Type::getInt32Ty(Context), + AT->getNumElements()); + Value* NewMI = CallInst::CreateMalloc(CI, TD->getIntPtrType(Context), + AllocSTy, NumElements, + BCI->getName()); + Value *Cast = new BitCastInst(NewMI, getMallocType(CI), "tmp", CI); + BCI->replaceAllUsesWith(Cast); + BCI->eraseFromParent(); + CI->eraseFromParent(); + BCI = cast<BitCastInst>(NewMI); + CI = extractMallocCallFromBitCast(NewMI); + } + + GVI = PerformHeapAllocSRoA(GV, CI, BCI, Context, TD); return true; } } @@ -1506,7 +1948,7 @@ static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, // that only one value (besides its initializer) is ever stored to the global. static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, Module::global_iterator &GVI, - TargetData &TD) { + TargetData *TD, LLVMContext &Context) { // Ignore no-op GEPs and bitcasts. StoredOnceVal = StoredOnceVal->stripPointerCasts(); @@ -1518,14 +1960,25 @@ static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, GV->getInitializer()->isNullValue()) { if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) - SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); + SOVC = + ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); // Optimize away any trapping uses of the loaded value. - if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC)) + if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, Context)) return true; } else if (MallocInst *MI = dyn_cast<MallocInst>(StoredOnceVal)) { - if (TryToOptimizeStoreOfMallocToGlobal(GV, MI, GVI, TD)) + if (TryToOptimizeStoreOfMallocToGlobal(GV, MI, GVI, TD, Context)) return true; + } else if (CallInst *CI = extractMallocCall(StoredOnceVal)) { + if (getMallocAllocatedType(CI)) { + BitCastInst* BCI = NULL; + for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); + UI != E; ) + BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++)); + if (BCI && + TryToOptimizeStoreOfMallocToGlobal(GV, CI, BCI, GVI, TD, Context)) + return true; + } } } @@ -1536,7 +1989,8 @@ static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, /// two values ever stored into GV are its initializer and OtherVal. See if we /// can shrink the global into a boolean and select between the two values /// whenever it is used. This exposes the values to other scalar optimizations. -static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { +static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal, + LLVMContext &Context) { const Type *GVElType = GV->getType()->getElementType(); // If GVElType is already i1, it is already shrunk. If the type of the GV is @@ -1544,7 +1998,7 @@ static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { // between them is very expensive and unlikely to lead to later // simplification. In these cases, we typically end up with "cond ? v1 : v2" // where v1 and v2 both require constant pool loads, a big loss. - if (GVElType == Type::Int1Ty || GVElType->isFloatingPoint() || + if (GVElType == Type::getInt1Ty(Context) || GVElType->isFloatingPoint() || isa<PointerType>(GVElType) || isa<VectorType>(GVElType)) return false; @@ -1554,18 +2008,19 @@ static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { if (!isa<LoadInst>(I) && !isa<StoreInst>(I)) return false; - DOUT << " *** SHRINKING TO BOOL: " << *GV; + DEBUG(errs() << " *** SHRINKING TO BOOL: " << *GV); // Create the new global, initializing it to false. - GlobalVariable *NewGV = new GlobalVariable(Type::Int1Ty, false, - GlobalValue::InternalLinkage, ConstantInt::getFalse(), + GlobalVariable *NewGV = new GlobalVariable(Context, + Type::getInt1Ty(Context), false, + GlobalValue::InternalLinkage, ConstantInt::getFalse(Context), GV->getName()+".b", - (Module *)NULL, GV->isThreadLocal()); GV->getParent()->getGlobalList().insert(GV, NewGV); Constant *InitVal = GV->getInitializer(); - assert(InitVal->getType() != Type::Int1Ty && "No reason to shrink to bool!"); + assert(InitVal->getType() != Type::getInt1Ty(Context) && + "No reason to shrink to bool!"); // If initialized to zero and storing one into the global, we can use a cast // instead of a select to synthesize the desired value. @@ -1581,7 +2036,7 @@ static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { // Only do this if we weren't storing a loaded value. Value *StoreVal; if (StoringOther || SI->getOperand(0) == InitVal) - StoreVal = ConstantInt::get(Type::Int1Ty, StoringOther); + StoreVal = ConstantInt::get(Type::getInt1Ty(Context), StoringOther); else { // Otherwise, we are storing a previously loaded copy. To do this, // change the copy from copying the original value to just copying the @@ -1632,7 +2087,7 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, GV->removeDeadConstantUsers(); if (GV->use_empty()) { - DOUT << "GLOBAL DEAD: " << *GV; + DEBUG(errs() << "GLOBAL DEAD: " << *GV); GV->eraseFromParent(); ++NumDeleted; return true; @@ -1675,7 +2130,7 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, GS.AccessingFunction->getName() == "main" && GS.AccessingFunction->hasExternalLinkage() && GV->getType()->getAddressSpace() == 0) { - DOUT << "LOCALIZING GLOBAL: " << *GV; + DEBUG(errs() << "LOCALIZING GLOBAL: " << *GV); Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin(); const Type* ElemTy = GV->getType()->getElementType(); // FIXME: Pass Global's alignment when globals have alignment @@ -1692,11 +2147,12 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, // If the global is never loaded (but may be stored to), it is dead. // Delete it now. if (!GS.isLoaded) { - DOUT << "GLOBAL NEVER LOADED: " << *GV; + DEBUG(errs() << "GLOBAL NEVER LOADED: " << *GV); // Delete any stores we can find to the global. We may not be able to // make it completely dead though. - bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer()); + bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), + GV->getContext()); // If the global is dead now, delete it. if (GV->use_empty()) { @@ -1707,16 +2163,16 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, return Changed; } else if (GS.StoredType <= GlobalStatus::isInitializerStored) { - DOUT << "MARKING CONSTANT: " << *GV; + DEBUG(errs() << "MARKING CONSTANT: " << *GV); GV->setConstant(true); // Clean up any obviously simplifiable users now. - CleanupConstantGlobalUsers(GV, GV->getInitializer()); + CleanupConstantGlobalUsers(GV, GV->getInitializer(), GV->getContext()); // If the global is dead now, just nuke it. if (GV->use_empty()) { - DOUT << " *** Marking constant allowed us to simplify " - << "all users and delete global!\n"; + DEBUG(errs() << " *** Marking constant allowed us to simplify " + << "all users and delete global!\n"); GV->eraseFromParent(); ++NumDeleted; } @@ -1724,11 +2180,12 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, ++NumMarked; return true; } else if (!GV->getInitializer()->getType()->isSingleValueType()) { - if (GlobalVariable *FirstNewGV = SRAGlobal(GV, - getAnalysis<TargetData>())) { - GVI = FirstNewGV; // Don't skip the newly produced globals! - return true; - } + if (TargetData *TD = getAnalysisIfAvailable<TargetData>()) + if (GlobalVariable *FirstNewGV = SRAGlobal(GV, *TD, + GV->getContext())) { + GVI = FirstNewGV; // Don't skip the newly produced globals! + return true; + } } else if (GS.StoredType == GlobalStatus::isStoredOnce) { // If the initial value for the global was an undef value, and if only // one other value was stored into it, we can just change the @@ -1740,11 +2197,12 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, GV->setInitializer(SOVConstant); // Clean up any obviously simplifiable users now. - CleanupConstantGlobalUsers(GV, GV->getInitializer()); + CleanupConstantGlobalUsers(GV, GV->getInitializer(), + GV->getContext()); if (GV->use_empty()) { - DOUT << " *** Substituting initializer allowed us to " - << "simplify all users and delete global!\n"; + DEBUG(errs() << " *** Substituting initializer allowed us to " + << "simplify all users and delete global!\n"); GV->eraseFromParent(); ++NumDeleted; } else { @@ -1757,13 +2215,14 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, // Try to optimize globals based on the knowledge that only one value // (besides its initializer) is ever stored to the global. if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI, - getAnalysis<TargetData>())) + getAnalysisIfAvailable<TargetData>(), + GV->getContext())) return true; // Otherwise, if the global was not a boolean, we can shrink it to be a // boolean. if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) - if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) { + if (TryToShrinkGlobalToBoolean(GV, SOVConstant, GV->getContext())) { ++NumShrunkToBool; return true; } @@ -1866,16 +2325,16 @@ GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) { if (!ATy) return 0; const StructType *STy = dyn_cast<StructType>(ATy->getElementType()); if (!STy || STy->getNumElements() != 2 || - STy->getElementType(0) != Type::Int32Ty) return 0; + STy->getElementType(0) != Type::getInt32Ty(M.getContext())) return 0; const PointerType *PFTy = dyn_cast<PointerType>(STy->getElementType(1)); if (!PFTy) return 0; const FunctionType *FTy = dyn_cast<FunctionType>(PFTy->getElementType()); - if (!FTy || FTy->getReturnType() != Type::VoidTy || FTy->isVarArg() || - FTy->getNumParams() != 0) + if (!FTy || FTy->getReturnType() != Type::getVoidTy(M.getContext()) || + FTy->isVarArg() || FTy->getNumParams() != 0) return 0; // Verify that the initializer is simple enough for us to handle. - if (!I->hasInitializer()) return 0; + if (!I->hasDefinitiveInitializer()) return 0; ConstantArray *CA = dyn_cast<ConstantArray>(I->getInitializer()); if (!CA) return 0; for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) @@ -1916,10 +2375,11 @@ static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) { /// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the /// specified array, returning the new global to use. static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, - const std::vector<Function*> &Ctors) { + const std::vector<Function*> &Ctors, + LLVMContext &Context) { // If we made a change, reassemble the initializer list. std::vector<Constant*> CSVals; - CSVals.push_back(ConstantInt::get(Type::Int32Ty, 65535)); + CSVals.push_back(ConstantInt::get(Type::getInt32Ty(Context), 65535)); CSVals.push_back(0); // Create the new init list. @@ -1928,19 +2388,19 @@ static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, if (Ctors[i]) { CSVals[1] = Ctors[i]; } else { - const Type *FTy = FunctionType::get(Type::VoidTy, false); + const Type *FTy = FunctionType::get(Type::getVoidTy(Context), false); const PointerType *PFTy = PointerType::getUnqual(FTy); CSVals[1] = Constant::getNullValue(PFTy); - CSVals[0] = ConstantInt::get(Type::Int32Ty, 2147483647); + CSVals[0] = ConstantInt::get(Type::getInt32Ty(Context), 2147483647); } - CAList.push_back(ConstantStruct::get(CSVals)); + CAList.push_back(ConstantStruct::get(Context, CSVals, false)); } // Create the array initializer. const Type *StructTy = - cast<ArrayType>(GCL->getType()->getElementType())->getElementType(); - Constant *CA = ConstantArray::get(ArrayType::get(StructTy, CAList.size()), - CAList); + cast<ArrayType>(GCL->getType()->getElementType())->getElementType(); + Constant *CA = ConstantArray::get(ArrayType::get(StructTy, + CAList.size()), CAList); // If we didn't change the number of elements, don't create a new GV. if (CA->getType() == GCL->getInitializer()->getType()) { @@ -1949,9 +2409,9 @@ static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, } // Create the new global and insert it next to the existing list. - GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(), + GlobalVariable *NGV = new GlobalVariable(Context, CA->getType(), + GCL->isConstant(), GCL->getLinkage(), CA, "", - (Module *)NULL, GCL->isThreadLocal()); GCL->getParent()->getGlobalList().insert(GCL, NGV); NGV->takeName(GCL); @@ -1984,21 +2444,38 @@ static Constant *getVal(DenseMap<Value*, Constant*> &ComputedValues, /// enough for us to understand. In particular, if it is a cast of something, /// we punt. We basically just support direct accesses to globals and GEP's of /// globals. This should be kept up to date with CommitValueTo. -static bool isSimpleEnoughPointerToCommit(Constant *C) { - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) { - if (!GV->hasExternalLinkage() && !GV->hasLocalLinkage()) - return false; // do not allow weak/linkonce/dllimport/dllexport linkage. - return !GV->isDeclaration(); // reject external globals. - } +static bool isSimpleEnoughPointerToCommit(Constant *C, LLVMContext &Context) { + // Conservatively, avoid aggregate types. This is because we don't + // want to worry about them partially overlapping other stores. + if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType()) + return false; + + if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) + // Do not allow weak/linkonce/dllimport/dllexport linkage or + // external globals. + return GV->hasDefinitiveInitializer(); + if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) // Handle a constantexpr gep. if (CE->getOpcode() == Instruction::GetElementPtr && - isa<GlobalVariable>(CE->getOperand(0))) { + isa<GlobalVariable>(CE->getOperand(0)) && + cast<GEPOperator>(CE)->isInBounds()) { GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); - if (!GV->hasExternalLinkage() && !GV->hasLocalLinkage()) - return false; // do not allow weak/linkonce/dllimport/dllexport linkage. - return GV->hasInitializer() && - ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); + // Do not allow weak/linkonce/dllimport/dllexport linkage or + // external globals. + if (!GV->hasDefinitiveInitializer()) + return false; + + // The first index must be zero. + ConstantInt *CI = dyn_cast<ConstantInt>(*next(CE->op_begin())); + if (!CI || !CI->isZero()) return false; + + // The remaining indices must be compile-time known integers within the + // notional bounds of the corresponding static array types. + if (!CE->isGEPWithNoNotionalOverIndexing()) + return false; + + return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); } return false; } @@ -2007,7 +2484,8 @@ static bool isSimpleEnoughPointerToCommit(Constant *C) { /// initializer. This returns 'Init' modified to reflect 'Val' stored into it. /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into. static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, - ConstantExpr *Addr, unsigned OpNo) { + ConstantExpr *Addr, unsigned OpNo, + LLVMContext &Context) { // Base case of the recursion. if (OpNo == Addr->getNumOperands()) { assert(Val->getType() == Init->getType() && "Type mismatch!"); @@ -2028,7 +2506,7 @@ static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) Elts.push_back(UndefValue::get(STy->getElementType(i))); } else { - assert(0 && "This code is out of sync with " + llvm_unreachable("This code is out of sync with " " ConstantFoldLoadThroughGEPConstantExpr"); } @@ -2036,10 +2514,10 @@ static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo)); unsigned Idx = CU->getZExtValue(); assert(Idx < STy->getNumElements() && "Struct index out of range!"); - Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1); + Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1, Context); // Return the modified struct. - return ConstantStruct::get(&Elts[0], Elts.size(), STy->isPacked()); + return ConstantStruct::get(Context, &Elts[0], Elts.size(), STy->isPacked()); } else { ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo)); const ArrayType *ATy = cast<ArrayType>(Init->getType()); @@ -2056,20 +2534,21 @@ static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, Constant *Elt = UndefValue::get(ATy->getElementType()); Elts.assign(ATy->getNumElements(), Elt); } else { - assert(0 && "This code is out of sync with " + llvm_unreachable("This code is out of sync with " " ConstantFoldLoadThroughGEPConstantExpr"); } assert(CI->getZExtValue() < ATy->getNumElements()); Elts[CI->getZExtValue()] = - EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1); + EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1, Context); return ConstantArray::get(ATy, Elts); } } /// CommitValueTo - We have decided that Addr (which satisfies the predicate /// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen. -static void CommitValueTo(Constant *Val, Constant *Addr) { +static void CommitValueTo(Constant *Val, Constant *Addr, + LLVMContext &Context) { if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { assert(GV->hasInitializer()); GV->setInitializer(Val); @@ -2080,7 +2559,7 @@ static void CommitValueTo(Constant *Val, Constant *Addr) { GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); Constant *Init = GV->getInitializer(); - Init = EvaluateStoreInto(Init, Val, CE, 2); + Init = EvaluateStoreInto(Init, Val, CE, 2, Context); GV->setInitializer(Init); } @@ -2088,7 +2567,8 @@ static void CommitValueTo(Constant *Val, Constant *Addr) { /// P after the stores reflected by 'memory' have been performed. If we can't /// decide, return null. static Constant *ComputeLoadResult(Constant *P, - const DenseMap<Constant*, Constant*> &Memory) { + const DenseMap<Constant*, Constant*> &Memory, + LLVMContext &Context) { // If this memory location has been recently stored, use the stored value: it // is the most up-to-date. DenseMap<Constant*, Constant*>::const_iterator I = Memory.find(P); @@ -2096,7 +2576,7 @@ static Constant *ComputeLoadResult(Constant *P, // Access it. if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { - if (GV->hasInitializer()) + if (GV->hasDefinitiveInitializer()) return GV->getInitializer(); return 0; } @@ -2106,7 +2586,7 @@ static Constant *ComputeLoadResult(Constant *P, if (CE->getOpcode() == Instruction::GetElementPtr && isa<GlobalVariable>(CE->getOperand(0))) { GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); - if (GV->hasInitializer()) + if (GV->hasDefinitiveInitializer()) return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); } @@ -2117,7 +2597,7 @@ static Constant *ComputeLoadResult(Constant *P, /// successful, false if we can't evaluate it. ActualArgs contains the formal /// arguments for the function. static bool EvaluateFunction(Function *F, Constant *&RetVal, - const std::vector<Constant*> &ActualArgs, + const SmallVectorImpl<Constant*> &ActualArgs, std::vector<Function*> &CallStack, DenseMap<Constant*, Constant*> &MutatedMemory, std::vector<GlobalVariable*> &AllocaTmps) { @@ -2126,6 +2606,8 @@ static bool EvaluateFunction(Function *F, Constant *&RetVal, if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end()) return false; + LLVMContext &Context = F->getContext(); + CallStack.push_back(F); /// Values - As we compute SSA register values, we store their contents here. @@ -2152,7 +2634,7 @@ static bool EvaluateFunction(Function *F, Constant *&RetVal, if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { if (SI->isVolatile()) return false; // no volatile accesses. Constant *Ptr = getVal(Values, SI->getOperand(1)); - if (!isSimpleEnoughPointerToCommit(Ptr)) + if (!isSimpleEnoughPointerToCommit(Ptr, Context)) // If this is too complex for us to commit, reject it. return false; Constant *Val = getVal(Values, SI->getOperand(0)); @@ -2170,7 +2652,8 @@ static bool EvaluateFunction(Function *F, Constant *&RetVal, getVal(Values, CI->getOperand(0)), CI->getType()); } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) { - InstResult = ConstantExpr::getSelect(getVal(Values, SI->getOperand(0)), + InstResult = + ConstantExpr::getSelect(getVal(Values, SI->getOperand(0)), getVal(Values, SI->getOperand(1)), getVal(Values, SI->getOperand(2))); } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { @@ -2179,16 +2662,18 @@ static bool EvaluateFunction(Function *F, Constant *&RetVal, for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; ++i) GEPOps.push_back(getVal(Values, *i)); - InstResult = ConstantExpr::getGetElementPtr(P, &GEPOps[0], GEPOps.size()); + InstResult = cast<GEPOperator>(GEP)->isInBounds() ? + ConstantExpr::getInBoundsGetElementPtr(P, &GEPOps[0], GEPOps.size()) : + ConstantExpr::getGetElementPtr(P, &GEPOps[0], GEPOps.size()); } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { if (LI->isVolatile()) return false; // no volatile accesses. InstResult = ComputeLoadResult(getVal(Values, LI->getOperand(0)), - MutatedMemory); + MutatedMemory, Context); if (InstResult == 0) return false; // Could not evaluate load. } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { if (AI->isArrayAllocation()) return false; // Cannot handle array allocs. const Type *Ty = AI->getType()->getElementType(); - AllocaTmps.push_back(new GlobalVariable(Ty, false, + AllocaTmps.push_back(new GlobalVariable(Context, Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty), AI->getName())); @@ -2208,14 +2693,14 @@ static bool EvaluateFunction(Function *F, Constant *&RetVal, Function *Callee = dyn_cast<Function>(getVal(Values, CI->getOperand(0))); if (!Callee) return false; // Cannot resolve. - std::vector<Constant*> Formals; + SmallVector<Constant*, 8> Formals; for (User::op_iterator i = CI->op_begin() + 1, e = CI->op_end(); i != e; ++i) Formals.push_back(getVal(Values, *i)); - + if (Callee->isDeclaration()) { // If this is a function we can constant fold, do it. - if (Constant *C = ConstantFoldCall(Callee, &Formals[0], + if (Constant *C = ConstantFoldCall(Callee, Formals.data(), Formals.size())) { InstResult = C; } else { @@ -2310,16 +2795,17 @@ static bool EvaluateStaticConstructor(Function *F) { // Call the function. Constant *RetValDummy; - bool EvalSuccess = EvaluateFunction(F, RetValDummy, std::vector<Constant*>(), - CallStack, MutatedMemory, AllocaTmps); + bool EvalSuccess = EvaluateFunction(F, RetValDummy, + SmallVector<Constant*, 0>(), CallStack, + MutatedMemory, AllocaTmps); if (EvalSuccess) { // We succeeded at evaluation: commit the result. - DOUT << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" - << F->getName() << "' to " << MutatedMemory.size() - << " stores.\n"; + DEBUG(errs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" + << F->getName() << "' to " << MutatedMemory.size() + << " stores.\n"); for (DenseMap<Constant*, Constant*>::iterator I = MutatedMemory.begin(), E = MutatedMemory.end(); I != E; ++I) - CommitValueTo(I->second, I->first); + CommitValueTo(I->second, I->first, F->getContext()); } // At this point, we are done interpreting. If we created any 'alloca' @@ -2376,7 +2862,7 @@ bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) { if (!MadeChange) return false; - GCL = InstallGlobalCtors(GCL, Ctors); + GCL = InstallGlobalCtors(GCL, Ctors, GCL->getContext()); return true; } diff --git a/lib/Transforms/IPO/IPConstantPropagation.cpp b/lib/Transforms/IPO/IPConstantPropagation.cpp index e4a9dea..7b0e9c7 100644 --- a/lib/Transforms/IPO/IPConstantPropagation.cpp +++ b/lib/Transforms/IPO/IPConstantPropagation.cpp @@ -19,6 +19,7 @@ #include "llvm/Transforms/IPO.h" #include "llvm/Constants.h" #include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Analysis/ValueTracking.h" @@ -129,7 +130,8 @@ bool IPCP::PropagateConstantsIntoArguments(Function &F) { Function::arg_iterator AI = F.arg_begin(); for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) { // Do we have a constant argument? - if (ArgumentConstants[i].second || AI->use_empty()) + if (ArgumentConstants[i].second || AI->use_empty() || + (AI->hasByValAttr() && !F.onlyReadsMemory())) continue; Value *V = ArgumentConstants[i].first; @@ -151,13 +153,15 @@ bool IPCP::PropagateConstantsIntoArguments(Function &F) { // callers will be updated to use the value they pass in directly instead of // using the return value. bool IPCP::PropagateConstantReturn(Function &F) { - if (F.getReturnType() == Type::VoidTy) + if (F.getReturnType() == Type::getVoidTy(F.getContext())) return false; // No return value. // If this function could be overridden later in the link stage, we can't // propagate information about its results into callers. if (F.mayBeOverridden()) return false; + + LLVMContext &Context = F.getContext(); // Check to see if this function returns a constant. SmallVector<Value *,4> RetVals; @@ -182,7 +186,7 @@ bool IPCP::PropagateConstantReturn(Function &F) { if (!STy) V = RI->getOperand(i); else - V = FindInsertedValue(RI->getOperand(0), i); + V = FindInsertedValue(RI->getOperand(0), i, Context); if (V) { // Ignore undefs, we can change them into anything diff --git a/lib/Transforms/IPO/IndMemRemoval.cpp b/lib/Transforms/IPO/IndMemRemoval.cpp index b55dea2..e7884ec 100644 --- a/lib/Transforms/IPO/IndMemRemoval.cpp +++ b/lib/Transforms/IPO/IndMemRemoval.cpp @@ -1,4 +1,4 @@ -//===-- IndMemRemoval.cpp - Remove indirect allocations and frees ----------===// +//===-- IndMemRemoval.cpp - Remove indirect allocations and frees ---------===// // // The LLVM Compiler Infrastructure // @@ -10,8 +10,8 @@ // This pass finds places where memory allocation functions may escape into // indirect land. Some transforms are much easier (aka possible) only if free // or malloc are not called indirectly. -// Thus find places where the address of memory functions are taken and construct -// bounce functions with direct calls of those functions. +// Thus find places where the address of memory functions are taken and +// construct bounce functions with direct calls of those functions. // //===----------------------------------------------------------------------===// @@ -55,8 +55,8 @@ bool IndMemRemPass::runOnModule(Module &M) { Function* FN = Function::Create(F->getFunctionType(), GlobalValue::LinkOnceAnyLinkage, "free_llvm_bounce", &M); - BasicBlock* bb = BasicBlock::Create("entry",FN); - Instruction* R = ReturnInst::Create(bb); + BasicBlock* bb = BasicBlock::Create(M.getContext(), "entry",FN); + Instruction* R = ReturnInst::Create(M.getContext(), bb); new FreeInst(FN->arg_begin(), R); ++NumBounce; NumBounceSites += F->getNumUses(); @@ -70,11 +70,12 @@ bool IndMemRemPass::runOnModule(Module &M) { GlobalValue::LinkOnceAnyLinkage, "malloc_llvm_bounce", &M); FN->setDoesNotAlias(0); - BasicBlock* bb = BasicBlock::Create("entry",FN); + BasicBlock* bb = BasicBlock::Create(M.getContext(), "entry",FN); Instruction* c = CastInst::CreateIntegerCast( - FN->arg_begin(), Type::Int32Ty, false, "c", bb); - Instruction* a = new MallocInst(Type::Int8Ty, c, "m", bb); - ReturnInst::Create(a, bb); + FN->arg_begin(), Type::getInt32Ty(M.getContext()), false, "c", bb); + Instruction* a = new MallocInst(Type::getInt8Ty(M.getContext()), + c, "m", bb); + ReturnInst::Create(M.getContext(), a, bb); ++NumBounce; NumBounceSites += F->getNumUses(); F->replaceAllUsesWith(FN); diff --git a/lib/Transforms/IPO/InlineAlways.cpp b/lib/Transforms/IPO/InlineAlways.cpp index 5f9ea54..2344403 100644 --- a/lib/Transforms/IPO/InlineAlways.cpp +++ b/lib/Transforms/IPO/InlineAlways.cpp @@ -19,11 +19,11 @@ #include "llvm/Module.h" #include "llvm/Type.h" #include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/InlineCost.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Compiler.h" #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/IPO/InlinerPass.h" -#include "llvm/Transforms/Utils/InlineCost.h" #include "llvm/ADT/SmallPtrSet.h" using namespace llvm; diff --git a/lib/Transforms/IPO/InlineSimple.cpp b/lib/Transforms/IPO/InlineSimple.cpp index e107a00..b1c643b 100644 --- a/lib/Transforms/IPO/InlineSimple.cpp +++ b/lib/Transforms/IPO/InlineSimple.cpp @@ -18,11 +18,11 @@ #include "llvm/Module.h" #include "llvm/Type.h" #include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/InlineCost.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Compiler.h" #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/IPO/InlinerPass.h" -#include "llvm/Transforms/Utils/InlineCost.h" #include "llvm/ADT/SmallPtrSet.h" using namespace llvm; @@ -78,7 +78,7 @@ bool SimpleInliner::doInitialization(CallGraph &CG) { return false; // Don't crash on invalid code - if (!GV->hasInitializer()) + if (!GV->hasDefinitiveInitializer()) return false; const ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); diff --git a/lib/Transforms/IPO/Inliner.cpp b/lib/Transforms/IPO/Inliner.cpp index b382837..ea47366 100644 --- a/lib/Transforms/IPO/Inliner.cpp +++ b/lib/Transforms/IPO/Inliner.cpp @@ -18,21 +18,25 @@ #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/InlineCost.h" #include "llvm/Support/CallSite.h" #include "llvm/Target/TargetData.h" #include "llvm/Transforms/IPO/InlinerPass.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include <set> using namespace llvm; STATISTIC(NumInlined, "Number of functions inlined"); STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); +STATISTIC(NumMergedAllocas, "Number of allocas merged together"); static cl::opt<int> -InlineLimit("inline-threshold", cl::Hidden, cl::init(200), +InlineLimit("inline-threshold", cl::Hidden, cl::init(200), cl::ZeroOrMore, cl::desc("Control the amount of inlining to perform (default = 200)")); Inliner::Inliner(void *ID) @@ -45,19 +49,32 @@ Inliner::Inliner(void *ID, int Threshold) /// the call graph. If the derived class implements this method, it should /// always explicitly call the implementation here. void Inliner::getAnalysisUsage(AnalysisUsage &Info) const { - Info.addRequired<TargetData>(); CallGraphSCCPass::getAnalysisUsage(Info); } -// InlineCallIfPossible - If it is possible to inline the specified call site, -// do so and update the CallGraph for this operation. -bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, - const SmallPtrSet<Function*, 8> &SCCFunctions, - const TargetData &TD) { + +typedef DenseMap<const ArrayType*, std::vector<AllocaInst*> > +InlinedArrayAllocasTy; + +/// InlineCallIfPossible - If it is possible to inline the specified call site, +/// do so and update the CallGraph for this operation. +/// +/// This function also does some basic book-keeping to update the IR. The +/// InlinedArrayAllocas map keeps track of any allocas that are already +/// available from other functions inlined into the caller. If we are able to +/// inline this call site we attempt to reuse already available allocas or add +/// any new allocas to the set if not possible. +static bool InlineCallIfPossible(CallSite CS, CallGraph &CG, + const TargetData *TD, + InlinedArrayAllocasTy &InlinedArrayAllocas) { Function *Callee = CS.getCalledFunction(); Function *Caller = CS.getCaller(); - if (!InlineFunction(CS, &CG, &TD)) return false; + // Try to inline the function. Get the list of static allocas that were + // inlined. + SmallVector<AllocaInst*, 16> StaticAllocas; + if (!InlineFunction(CS, &CG, TD, &StaticAllocas)) + return false; // If the inlined function had a higher stack protection level than the // calling function, then bump up the caller's stack protection level. @@ -67,23 +84,89 @@ bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, !Caller->hasFnAttr(Attribute::StackProtectReq)) Caller->addFnAttr(Attribute::StackProtect); - // If we inlined the last possible call site to the function, delete the - // function body now. - if (Callee->use_empty() && (Callee->hasLocalLinkage() || - Callee->hasAvailableExternallyLinkage()) && - !SCCFunctions.count(Callee)) { - DOUT << " -> Deleting dead function: " << Callee->getName() << "\n"; - CallGraphNode *CalleeNode = CG[Callee]; - - // Remove any call graph edges from the callee to its callees. - CalleeNode->removeAllCalledFunctions(); - - resetCachedCostInfo(CalleeNode->getFunction()); + + // Look at all of the allocas that we inlined through this call site. If we + // have already inlined other allocas through other calls into this function, + // then we know that they have disjoint lifetimes and that we can merge them. + // + // There are many heuristics possible for merging these allocas, and the + // different options have different tradeoffs. One thing that we *really* + // don't want to hurt is SRoA: once inlining happens, often allocas are no + // longer address taken and so they can be promoted. + // + // Our "solution" for that is to only merge allocas whose outermost type is an + // array type. These are usually not promoted because someone is using a + // variable index into them. These are also often the most important ones to + // merge. + // + // A better solution would be to have real memory lifetime markers in the IR + // and not have the inliner do any merging of allocas at all. This would + // allow the backend to do proper stack slot coloring of all allocas that + // *actually make it to the backend*, which is really what we want. + // + // Because we don't have this information, we do this simple and useful hack. + // + SmallPtrSet<AllocaInst*, 16> UsedAllocas; + + // Loop over all the allocas we have so far and see if they can be merged with + // a previously inlined alloca. If not, remember that we had it. + for (unsigned AllocaNo = 0, e = StaticAllocas.size(); + AllocaNo != e; ++AllocaNo) { + AllocaInst *AI = StaticAllocas[AllocaNo]; + + // Don't bother trying to merge array allocations (they will usually be + // canonicalized to be an allocation *of* an array), or allocations whose + // type is not itself an array (because we're afraid of pessimizing SRoA). + const ArrayType *ATy = dyn_cast<ArrayType>(AI->getAllocatedType()); + if (ATy == 0 || AI->isArrayAllocation()) + continue; + + // Get the list of all available allocas for this array type. + std::vector<AllocaInst*> &AllocasForType = InlinedArrayAllocas[ATy]; + + // Loop over the allocas in AllocasForType to see if we can reuse one. Note + // that we have to be careful not to reuse the same "available" alloca for + // multiple different allocas that we just inlined, we use the 'UsedAllocas' + // set to keep track of which "available" allocas are being used by this + // function. Also, AllocasForType can be empty of course! + bool MergedAwayAlloca = false; + for (unsigned i = 0, e = AllocasForType.size(); i != e; ++i) { + AllocaInst *AvailableAlloca = AllocasForType[i]; + + // The available alloca has to be in the right function, not in some other + // function in this SCC. + if (AvailableAlloca->getParent() != AI->getParent()) + continue; + + // If the inlined function already uses this alloca then we can't reuse + // it. + if (!UsedAllocas.insert(AvailableAlloca)) + continue; + + // Otherwise, we *can* reuse it, RAUW AI into AvailableAlloca and declare + // success! + DEBUG(errs() << " ***MERGED ALLOCA: " << *AI); + + AI->replaceAllUsesWith(AvailableAlloca); + AI->eraseFromParent(); + MergedAwayAlloca = true; + ++NumMergedAllocas; + break; + } - // Removing the node for callee from the call graph and delete it. - delete CG.removeFunctionFromModule(CalleeNode); - ++NumDeleted; + // If we already nuked the alloca, we're done with it. + if (MergedAwayAlloca) + continue; + + // If we were unable to merge away the alloca either because there are no + // allocas of the right type available or because we reused them all + // already, remember that this alloca came from an inlined function and mark + // it used so we don't reuse it for other allocas from this inline + // operation. + AllocasForType.push_back(AI); + UsedAllocas.insert(AI); } + return true; } @@ -91,69 +174,145 @@ bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, /// at the given CallSite. bool Inliner::shouldInline(CallSite CS) { InlineCost IC = getInlineCost(CS); - float FudgeFactor = getInlineFudgeFactor(CS); if (IC.isAlways()) { - DOUT << " Inlining: cost=always" - << ", Call: " << *CS.getInstruction(); + DEBUG(errs() << " Inlining: cost=always" + << ", Call: " << *CS.getInstruction() << "\n"); return true; } if (IC.isNever()) { - DOUT << " NOT Inlining: cost=never" - << ", Call: " << *CS.getInstruction(); + DEBUG(errs() << " NOT Inlining: cost=never" + << ", Call: " << *CS.getInstruction() << "\n"); return false; } int Cost = IC.getValue(); int CurrentThreshold = InlineThreshold; - Function *Fn = CS.getCaller(); - if (Fn && !Fn->isDeclaration() - && Fn->hasFnAttr(Attribute::OptimizeForSize) - && InlineThreshold != 50) { + Function *Caller = CS.getCaller(); + if (Caller && !Caller->isDeclaration() && + Caller->hasFnAttr(Attribute::OptimizeForSize) && + InlineLimit.getNumOccurrences() == 0 && + InlineThreshold != 50) CurrentThreshold = 50; - } + float FudgeFactor = getInlineFudgeFactor(CS); if (Cost >= (int)(CurrentThreshold * FudgeFactor)) { - DOUT << " NOT Inlining: cost=" << Cost - << ", Call: " << *CS.getInstruction(); + DEBUG(errs() << " NOT Inlining: cost=" << Cost + << ", Call: " << *CS.getInstruction() << "\n"); return false; - } else { - DOUT << " Inlining: cost=" << Cost - << ", Call: " << *CS.getInstruction(); - return true; } + + // Try to detect the case where the current inlining candidate caller + // (call it B) is a static function and is an inlining candidate elsewhere, + // and the current candidate callee (call it C) is large enough that + // inlining it into B would make B too big to inline later. In these + // circumstances it may be best not to inline C into B, but to inline B + // into its callers. + if (Caller->hasLocalLinkage()) { + int TotalSecondaryCost = 0; + bool outerCallsFound = false; + bool allOuterCallsWillBeInlined = true; + bool someOuterCallWouldNotBeInlined = false; + for (Value::use_iterator I = Caller->use_begin(), E =Caller->use_end(); + I != E; ++I) { + CallSite CS2 = CallSite::get(*I); + + // If this isn't a call to Caller (it could be some other sort + // of reference) skip it. + if (CS2.getInstruction() == 0 || CS2.getCalledFunction() != Caller) + continue; + + InlineCost IC2 = getInlineCost(CS2); + if (IC2.isNever()) + allOuterCallsWillBeInlined = false; + if (IC2.isAlways() || IC2.isNever()) + continue; + + outerCallsFound = true; + int Cost2 = IC2.getValue(); + int CurrentThreshold2 = InlineThreshold; + Function *Caller2 = CS2.getCaller(); + if (Caller2 && !Caller2->isDeclaration() && + Caller2->hasFnAttr(Attribute::OptimizeForSize) && + InlineThreshold != 50) + CurrentThreshold2 = 50; + + float FudgeFactor2 = getInlineFudgeFactor(CS2); + + if (Cost2 >= (int)(CurrentThreshold2 * FudgeFactor2)) + allOuterCallsWillBeInlined = false; + + // See if we have this case. We subtract off the penalty + // for the call instruction, which we would be deleting. + if (Cost2 < (int)(CurrentThreshold2 * FudgeFactor2) && + Cost2 + Cost - (InlineConstants::CallPenalty + 1) >= + (int)(CurrentThreshold2 * FudgeFactor2)) { + someOuterCallWouldNotBeInlined = true; + TotalSecondaryCost += Cost2; + } + } + // If all outer calls to Caller would get inlined, the cost for the last + // one is set very low by getInlineCost, in anticipation that Caller will + // be removed entirely. We did not account for this above unless there + // is only one caller of Caller. + if (allOuterCallsWillBeInlined && Caller->use_begin() != Caller->use_end()) + TotalSecondaryCost += InlineConstants::LastCallToStaticBonus; + + if (outerCallsFound && someOuterCallWouldNotBeInlined && + TotalSecondaryCost < Cost) { + DEBUG(errs() << " NOT Inlining: " << *CS.getInstruction() << + " Cost = " << Cost << + ", outer Cost = " << TotalSecondaryCost << '\n'); + return false; + } + } + + DEBUG(errs() << " Inlining: cost=" << Cost + << ", Call: " << *CS.getInstruction() << '\n'); + return true; } -bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { +bool Inliner::runOnSCC(std::vector<CallGraphNode*> &SCC) { CallGraph &CG = getAnalysis<CallGraph>(); - TargetData &TD = getAnalysis<TargetData>(); + const TargetData *TD = getAnalysisIfAvailable<TargetData>(); SmallPtrSet<Function*, 8> SCCFunctions; - DOUT << "Inliner visiting SCC:"; + DEBUG(errs() << "Inliner visiting SCC:"); for (unsigned i = 0, e = SCC.size(); i != e; ++i) { Function *F = SCC[i]->getFunction(); if (F) SCCFunctions.insert(F); - DOUT << " " << (F ? F->getName() : "INDIRECTNODE"); + DEBUG(errs() << " " << (F ? F->getName() : "INDIRECTNODE")); } // Scan through and identify all call sites ahead of time so that we only // inline call sites in the original functions, not call sites that result // from inlining other functions. - std::vector<CallSite> CallSites; + SmallVector<CallSite, 16> CallSites; - for (unsigned i = 0, e = SCC.size(); i != e; ++i) - if (Function *F = SCC[i]->getFunction()) - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { - CallSite CS = CallSite::get(I); - if (CS.getInstruction() && !isa<DbgInfoIntrinsic>(I) && - (!CS.getCalledFunction() || - !CS.getCalledFunction()->isDeclaration())) - CallSites.push_back(CS); - } + for (unsigned i = 0, e = SCC.size(); i != e; ++i) { + Function *F = SCC[i]->getFunction(); + if (!F) continue; + + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + CallSite CS = CallSite::get(I); + // If this isn't a call, or it is a call to an intrinsic, it can + // never be inlined. + if (CS.getInstruction() == 0 || isa<IntrinsicInst>(I)) + continue; + + // If this is a direct call to an external function, we can never inline + // it. If it is an indirect call, inlining may resolve it to be a + // direct call, so we keep it. + if (CS.getCalledFunction() && CS.getCalledFunction()->isDeclaration()) + continue; + + CallSites.push_back(CS); + } + } - DOUT << ": " << CallSites.size() << " call sites.\n"; + DEBUG(errs() << ": " << CallSites.size() << " call sites.\n"); // Now that we have all of the call sites, move the ones to functions in the // current SCC to the end of the list. @@ -163,6 +322,9 @@ bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { if (SCCFunctions.count(F)) std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); + + InlinedArrayAllocasTy InlinedArrayAllocas; + // Now that we have all of the call sites, loop over them and inline them if // it looks profitable to do so. bool Changed = false; @@ -171,51 +333,68 @@ bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { LocalChange = false; // Iterate over the outer loop because inlining functions can cause indirect // calls to become direct calls. - for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) - if (Function *Callee = CallSites[CSi].getCalledFunction()) { - // Calls to external functions are never inlinable. - if (Callee->isDeclaration()) { - if (SCC.size() == 1) { - std::swap(CallSites[CSi], CallSites.back()); - CallSites.pop_back(); - } else { - // Keep the 'in SCC / not in SCC' boundary correct. - CallSites.erase(CallSites.begin()+CSi); - } - --CSi; - continue; - } - - // If the policy determines that we should inline this function, - // try to do so. - CallSite CS = CallSites[CSi]; - if (shouldInline(CS)) { - Function *Caller = CS.getCaller(); - // Attempt to inline the function... - if (InlineCallIfPossible(CS, CG, SCCFunctions, TD)) { - // Remove any cached cost info for this caller, as inlining the - // callee has increased the size of the caller (which may be the - // same as the callee). - resetCachedCostInfo(Caller); - - // Remove this call site from the list. If possible, use - // swap/pop_back for efficiency, but do not use it if doing so would - // move a call site to a function in this SCC before the - // 'FirstCallInSCC' barrier. - if (SCC.size() == 1) { - std::swap(CallSites[CSi], CallSites.back()); - CallSites.pop_back(); - } else { - CallSites.erase(CallSites.begin()+CSi); - } - --CSi; - - ++NumInlined; - Changed = true; - LocalChange = true; - } - } + for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) { + CallSite CS = CallSites[CSi]; + + Function *Callee = CS.getCalledFunction(); + // We can only inline direct calls to non-declarations. + if (Callee == 0 || Callee->isDeclaration()) continue; + + // If the policy determines that we should inline this function, + // try to do so. + if (!shouldInline(CS)) + continue; + + Function *Caller = CS.getCaller(); + // Attempt to inline the function... + if (!InlineCallIfPossible(CS, CG, TD, InlinedArrayAllocas)) + continue; + + // If we inlined the last possible call site to the function, delete the + // function body now. + if (Callee->use_empty() && Callee->hasLocalLinkage() && + // TODO: Can remove if in SCC now. + !SCCFunctions.count(Callee) && + + // The function may be apparently dead, but if there are indirect + // callgraph references to the node, we cannot delete it yet, this + // could invalidate the CGSCC iterator. + CG[Callee]->getNumReferences() == 0) { + DEBUG(errs() << " -> Deleting dead function: " + << Callee->getName() << "\n"); + CallGraphNode *CalleeNode = CG[Callee]; + + // Remove any call graph edges from the callee to its callees. + CalleeNode->removeAllCalledFunctions(); + + resetCachedCostInfo(Callee); + + // Removing the node for callee from the call graph and delete it. + delete CG.removeFunctionFromModule(CalleeNode); + ++NumDeleted; } + + // Remove any cached cost info for this caller, as inlining the + // callee has increased the size of the caller (which may be the + // same as the callee). + resetCachedCostInfo(Caller); + + // Remove this call site from the list. If possible, use + // swap/pop_back for efficiency, but do not use it if doing so would + // move a call site to a function in this SCC before the + // 'FirstCallInSCC' barrier. + if (SCC.size() == 1) { + std::swap(CallSites[CSi], CallSites.back()); + CallSites.pop_back(); + } else { + CallSites.erase(CallSites.begin()+CSi); + } + --CSi; + + ++NumInlined; + Changed = true; + LocalChange = true; + } } while (LocalChange); return Changed; @@ -227,47 +406,55 @@ bool Inliner::doFinalization(CallGraph &CG) { return removeDeadFunctions(CG); } - /// removeDeadFunctions - Remove dead functions that are not included in - /// DNR (Do Not Remove) list. +/// removeDeadFunctions - Remove dead functions that are not included in +/// DNR (Do Not Remove) list. bool Inliner::removeDeadFunctions(CallGraph &CG, - SmallPtrSet<const Function *, 16> *DNR) { - std::set<CallGraphNode*> FunctionsToRemove; + SmallPtrSet<const Function *, 16> *DNR) { + SmallPtrSet<CallGraphNode*, 16> FunctionsToRemove; // Scan for all of the functions, looking for ones that should now be removed // from the program. Insert the dead ones in the FunctionsToRemove set. for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { CallGraphNode *CGN = I->second; - if (Function *F = CGN ? CGN->getFunction() : 0) { - // If the only remaining users of the function are dead constants, remove - // them. - F->removeDeadConstantUsers(); - - if (DNR && DNR->count(F)) - continue; + if (CGN->getFunction() == 0) + continue; + + Function *F = CGN->getFunction(); + + // If the only remaining users of the function are dead constants, remove + // them. + F->removeDeadConstantUsers(); + + if (DNR && DNR->count(F)) + continue; + if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage() && + !F->hasAvailableExternallyLinkage()) + continue; + if (!F->use_empty()) + continue; + + // Remove any call graph edges from the function to its callees. + CGN->removeAllCalledFunctions(); + + // Remove any edges from the external node to the function's call graph + // node. These edges might have been made irrelegant due to + // optimization of the program. + CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); - if ((F->hasLinkOnceLinkage() || F->hasLocalLinkage()) && - F->use_empty()) { - - // Remove any call graph edges from the function to its callees. - CGN->removeAllCalledFunctions(); - - // Remove any edges from the external node to the function's call graph - // node. These edges might have been made irrelegant due to - // optimization of the program. - CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); - - // Removing the node for callee from the call graph and delete it. - FunctionsToRemove.insert(CGN); - } - } + // Removing the node for callee from the call graph and delete it. + FunctionsToRemove.insert(CGN); } // Now that we know which functions to delete, do so. We didn't want to do // this inline, because that would invalidate our CallGraph::iterator // objects. :( + // + // Note that it doesn't matter that we are iterating over a non-stable set + // here to do this, it doesn't matter which order the functions are deleted + // in. bool Changed = false; - for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(), - E = FunctionsToRemove.end(); I != E; ++I) { + for (SmallPtrSet<CallGraphNode*, 16>::iterator I = FunctionsToRemove.begin(), + E = FunctionsToRemove.end(); I != E; ++I) { resetCachedCostInfo((*I)->getFunction()); delete CG.removeFunctionFromModule(*I); ++NumDeleted; diff --git a/lib/Transforms/IPO/Internalize.cpp b/lib/Transforms/IPO/Internalize.cpp index 5093ae9..e3c3c67 100644 --- a/lib/Transforms/IPO/Internalize.cpp +++ b/lib/Transforms/IPO/Internalize.cpp @@ -21,6 +21,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/Statistic.h" #include <fstream> #include <set> @@ -86,7 +87,7 @@ void InternalizePass::LoadFile(const char *Filename) { // Load the APIFile... std::ifstream In(Filename); if (!In.good()) { - cerr << "WARNING: Internalize couldn't load file '" << Filename + errs() << "WARNING: Internalize couldn't load file '" << Filename << "'! Continuing as if it's empty.\n"; return; // Just continue as if the file were empty } @@ -101,7 +102,7 @@ void InternalizePass::LoadFile(const char *Filename) { bool InternalizePass::runOnModule(Module &M) { CallGraph *CG = getAnalysisIfAvailable<CallGraph>(); CallGraphNode *ExternalNode = CG ? CG->getExternalCallingNode() : 0; - + if (ExternalNames.empty()) { // Return if we're not in 'all but main' mode and have no external api if (!AllButMain) @@ -131,12 +132,14 @@ bool InternalizePass::runOnModule(Module &M) { if (ExternalNode) ExternalNode->removeOneAbstractEdgeTo((*CG)[I]); Changed = true; ++NumFunctions; - DOUT << "Internalizing func " << I->getName() << "\n"; + DEBUG(errs() << "Internalizing func " << I->getName() << "\n"); } // Never internalize the llvm.used symbol. It is used to implement // attribute((used)). + // FIXME: Shouldn't this just filter on llvm.metadata section?? ExternalNames.insert("llvm.used"); + ExternalNames.insert("llvm.compiler.used"); // Never internalize anchors used by the machine module info, else the info // won't find them. (see MachineModuleInfo.) @@ -158,7 +161,7 @@ bool InternalizePass::runOnModule(Module &M) { I->setLinkage(GlobalValue::InternalLinkage); Changed = true; ++NumGlobals; - DOUT << "Internalized gvar " << I->getName() << "\n"; + DEBUG(errs() << "Internalized gvar " << I->getName() << "\n"); } // Mark all aliases that are not in the api as internal as well. @@ -169,7 +172,7 @@ bool InternalizePass::runOnModule(Module &M) { I->setLinkage(GlobalValue::InternalLinkage); Changed = true; ++NumAliases; - DOUT << "Internalized alias " << I->getName() << "\n"; + DEBUG(errs() << "Internalized alias " << I->getName() << "\n"); } return Changed; diff --git a/lib/Transforms/IPO/LoopExtractor.cpp b/lib/Transforms/IPO/LoopExtractor.cpp index 0c65443..02ac3bb 100644 --- a/lib/Transforms/IPO/LoopExtractor.cpp +++ b/lib/Transforms/IPO/LoopExtractor.cpp @@ -20,7 +20,7 @@ #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Transforms/Scalar.h" @@ -33,23 +33,19 @@ using namespace llvm; STATISTIC(NumExtracted, "Number of loops extracted"); namespace { - // FIXME: This is not a function pass, but the PassManager doesn't allow - // Module passes to require FunctionPasses, so we can't get loop info if we're - // not a function pass. - struct VISIBILITY_HIDDEN LoopExtractor : public FunctionPass { + struct VISIBILITY_HIDDEN LoopExtractor : public LoopPass { static char ID; // Pass identification, replacement for typeid unsigned NumLoops; explicit LoopExtractor(unsigned numLoops = ~0) - : FunctionPass(&ID), NumLoops(numLoops) {} + : LoopPass(&ID), NumLoops(numLoops) {} - virtual bool runOnFunction(Function &F); + virtual bool runOnLoop(Loop *L, LPPassManager &LPM); virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequiredID(BreakCriticalEdgesID); AU.addRequiredID(LoopSimplifyID); AU.addRequired<DominatorTree>(); - AU.addRequired<LoopInfo>(); } }; } @@ -73,68 +69,50 @@ Y("loop-extract-single", "Extract at most one loop into a new function"); // createLoopExtractorPass - This pass extracts all natural loops from the // program into a function if it can. // -FunctionPass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } +Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } -bool LoopExtractor::runOnFunction(Function &F) { - LoopInfo &LI = getAnalysis<LoopInfo>(); - - // If this function has no loops, there is nothing to do. - if (LI.empty()) +bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) { + // Only visit top-level loops. + if (L->getParentLoop()) return false; DominatorTree &DT = getAnalysis<DominatorTree>(); - - // If there is more than one top-level loop in this function, extract all of - // the loops. bool Changed = false; - if (LI.end()-LI.begin() > 1) { - for (LoopInfo::iterator i = LI.begin(), e = LI.end(); i != e; ++i) { - if (NumLoops == 0) return Changed; - --NumLoops; - Changed |= ExtractLoop(DT, *i) != 0; - ++NumExtracted; - } - } else { - // Otherwise there is exactly one top-level loop. If this function is more - // than a minimal wrapper around the loop, extract the loop. - Loop *TLL = *LI.begin(); - bool ShouldExtractLoop = false; - - // Extract the loop if the entry block doesn't branch to the loop header. - TerminatorInst *EntryTI = F.getEntryBlock().getTerminator(); - if (!isa<BranchInst>(EntryTI) || - !cast<BranchInst>(EntryTI)->isUnconditional() || - EntryTI->getSuccessor(0) != TLL->getHeader()) - ShouldExtractLoop = true; - else { - // Check to see if any exits from the loop are more than just return - // blocks. - SmallVector<BasicBlock*, 8> ExitBlocks; - TLL->getExitBlocks(ExitBlocks); - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) { - ShouldExtractLoop = true; - break; - } - } - if (ShouldExtractLoop) { - if (NumLoops == 0) return Changed; - --NumLoops; - Changed |= ExtractLoop(DT, TLL) != 0; - ++NumExtracted; - } else { - // Okay, this function is a minimal container around the specified loop. - // If we extract the loop, we will continue to just keep extracting it - // infinitely... so don't extract it. However, if the loop contains any - // subloops, extract them. - for (Loop::iterator i = TLL->begin(), e = TLL->end(); i != e; ++i) { - if (NumLoops == 0) return Changed; - --NumLoops; - Changed |= ExtractLoop(DT, *i) != 0; - ++NumExtracted; + // If there is more than one top-level loop in this function, extract all of + // the loops. Otherwise there is exactly one top-level loop; in this case if + // this function is more than a minimal wrapper around the loop, extract + // the loop. + bool ShouldExtractLoop = false; + + // Extract the loop if the entry block doesn't branch to the loop header. + TerminatorInst *EntryTI = + L->getHeader()->getParent()->getEntryBlock().getTerminator(); + if (!isa<BranchInst>(EntryTI) || + !cast<BranchInst>(EntryTI)->isUnconditional() || + EntryTI->getSuccessor(0) != L->getHeader()) + ShouldExtractLoop = true; + else { + // Check to see if any exits from the loop are more than just return + // blocks. + SmallVector<BasicBlock*, 8> ExitBlocks; + L->getExitBlocks(ExitBlocks); + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) + if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) { + ShouldExtractLoop = true; + break; } + } + if (ShouldExtractLoop) { + if (NumLoops == 0) return Changed; + --NumLoops; + if (ExtractLoop(DT, L) != 0) { + Changed = true; + // After extraction, the loop is replaced by a function call, so + // we shouldn't try to run any more loop passes on it. + LPM.deleteLoopFromQueue(L); } + ++NumExtracted; } return Changed; @@ -143,7 +121,7 @@ bool LoopExtractor::runOnFunction(Function &F) { // createSingleLoopExtractorPass - This pass extracts one natural loop from the // program into a function if it can. This is used by bugpoint. // -FunctionPass *llvm::createSingleLoopExtractorPass() { +Pass *llvm::createSingleLoopExtractorPass() { return new SingleLoopExtractor(); } @@ -193,8 +171,8 @@ void BlockExtractorPass::LoadFile(const char *Filename) { // Load the BlockFile... std::ifstream In(Filename); if (!In.good()) { - cerr << "WARNING: BlockExtractor couldn't load file '" << Filename - << "'!\n"; + errs() << "WARNING: BlockExtractor couldn't load file '" << Filename + << "'!\n"; return; } while (In) { diff --git a/lib/Transforms/IPO/LowerSetJmp.cpp b/lib/Transforms/IPO/LowerSetJmp.cpp index dfc040b..55194b3 100644 --- a/lib/Transforms/IPO/LowerSetJmp.cpp +++ b/lib/Transforms/IPO/LowerSetJmp.cpp @@ -39,6 +39,7 @@ #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" #include "llvm/Intrinsics.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Support/CFG.h" @@ -200,7 +201,7 @@ bool LowerSetJmp::runOnModule(Module& M) { // This function is always successful, unless it isn't. bool LowerSetJmp::doInitialization(Module& M) { - const Type *SBPTy = PointerType::getUnqual(Type::Int8Ty); + const Type *SBPTy = Type::getInt8PtrTy(M.getContext()); const Type *SBPPTy = PointerType::getUnqual(SBPTy); // N.B. See llvm/runtime/GCCLibraries/libexception/SJLJ-Exception.h for @@ -208,33 +209,40 @@ bool LowerSetJmp::doInitialization(Module& M) // void __llvm_sjljeh_init_setjmpmap(void**) InitSJMap = M.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap", - Type::VoidTy, SBPPTy, (Type *)0); + Type::getVoidTy(M.getContext()), + SBPPTy, (Type *)0); // void __llvm_sjljeh_destroy_setjmpmap(void**) DestroySJMap = M.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap", - Type::VoidTy, SBPPTy, (Type *)0); + Type::getVoidTy(M.getContext()), + SBPPTy, (Type *)0); // void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned) AddSJToMap = M.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map", - Type::VoidTy, SBPPTy, SBPTy, - Type::Int32Ty, (Type *)0); + Type::getVoidTy(M.getContext()), + SBPPTy, SBPTy, + Type::getInt32Ty(M.getContext()), + (Type *)0); // void __llvm_sjljeh_throw_longjmp(int*, int) ThrowLongJmp = M.getOrInsertFunction("__llvm_sjljeh_throw_longjmp", - Type::VoidTy, SBPTy, Type::Int32Ty, + Type::getVoidTy(M.getContext()), SBPTy, + Type::getInt32Ty(M.getContext()), (Type *)0); // unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **) TryCatchLJ = M.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception", - Type::Int32Ty, SBPPTy, (Type *)0); + Type::getInt32Ty(M.getContext()), SBPPTy, (Type *)0); // bool __llvm_sjljeh_is_longjmp_exception() IsLJException = M.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception", - Type::Int1Ty, (Type *)0); + Type::getInt1Ty(M.getContext()), + (Type *)0); // int __llvm_sjljeh_get_longjmp_value() GetLJValue = M.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value", - Type::Int32Ty, (Type *)0); + Type::getInt32Ty(M.getContext()), + (Type *)0); return true; } @@ -257,7 +265,8 @@ bool LowerSetJmp::IsTransformableFunction(const std::string& Name) { // throwing the exception for us. void LowerSetJmp::TransformLongJmpCall(CallInst* Inst) { - const Type* SBPTy = PointerType::getUnqual(Type::Int8Ty); + const Type* SBPTy = + Type::getInt8PtrTy(Inst->getContext()); // Create the call to "__llvm_sjljeh_throw_longjmp". This takes the // same parameters as "longjmp", except that the buffer is cast to a @@ -278,7 +287,7 @@ void LowerSetJmp::TransformLongJmpCall(CallInst* Inst) if (SVP.first) BranchInst::Create(SVP.first->getParent(), Inst); else - new UnwindInst(Inst); + new UnwindInst(Inst->getContext(), Inst); // Remove all insts after the branch/unwind inst. Go from back to front to // avoid replaceAllUsesWith if possible. @@ -309,7 +318,8 @@ AllocaInst* LowerSetJmp::GetSetJmpMap(Function* Func) assert(Inst && "Couldn't find even ONE instruction in entry block!"); // Fill in the alloca and call to initialize the SJ map. - const Type *SBPTy = PointerType::getUnqual(Type::Int8Ty); + const Type *SBPTy = + Type::getInt8PtrTy(Func->getContext()); AllocaInst* Map = new AllocaInst(SBPTy, 0, "SJMap", Inst); CallInst::Create(InitSJMap, Map, "", Inst); return SJMap[Func] = Map; @@ -324,12 +334,13 @@ BasicBlock* LowerSetJmp::GetRethrowBB(Function* Func) // The basic block we're going to jump to if we need to rethrow the // exception. - BasicBlock* Rethrow = BasicBlock::Create("RethrowExcept", Func); + BasicBlock* Rethrow = + BasicBlock::Create(Func->getContext(), "RethrowExcept", Func); // Fill in the "Rethrow" BB with a call to rethrow the exception. This // is the last instruction in the BB since at this point the runtime // should exit this function and go to the next function. - new UnwindInst(Rethrow); + new UnwindInst(Func->getContext(), Rethrow); return RethrowBBMap[Func] = Rethrow; } @@ -340,7 +351,8 @@ LowerSetJmp::SwitchValuePair LowerSetJmp::GetSJSwitch(Function* Func, { if (SwitchValMap[Func].first) return SwitchValMap[Func]; - BasicBlock* LongJmpPre = BasicBlock::Create("LongJmpBlkPre", Func); + BasicBlock* LongJmpPre = + BasicBlock::Create(Func->getContext(), "LongJmpBlkPre", Func); // Keep track of the preliminary basic block for some of the other // transformations. @@ -352,7 +364,8 @@ LowerSetJmp::SwitchValuePair LowerSetJmp::GetSJSwitch(Function* Func, // The "decision basic block" gets the number associated with the // setjmp call returning to switch on and the value returned by // longjmp. - BasicBlock* DecisionBB = BasicBlock::Create("LJDecisionBB", Func); + BasicBlock* DecisionBB = + BasicBlock::Create(Func->getContext(), "LJDecisionBB", Func); BranchInst::Create(DecisionBB, Rethrow, Cond, LongJmpPre); @@ -375,12 +388,13 @@ void LowerSetJmp::TransformSetJmpCall(CallInst* Inst) Function* Func = ABlock->getParent(); // Add this setjmp to the setjmp map. - const Type* SBPTy = PointerType::getUnqual(Type::Int8Ty); + const Type* SBPTy = + Type::getInt8PtrTy(Inst->getContext()); CastInst* BufPtr = new BitCastInst(Inst->getOperand(1), SBPTy, "SBJmpBuf", Inst); std::vector<Value*> Args = make_vector<Value*>(GetSetJmpMap(Func), BufPtr, - ConstantInt::get(Type::Int32Ty, + ConstantInt::get(Type::getInt32Ty(Inst->getContext()), SetJmpIDMap[Func]++), 0); CallInst::Create(AddSJToMap, Args.begin(), Args.end(), "", Inst); @@ -424,14 +438,17 @@ void LowerSetJmp::TransformSetJmpCall(CallInst* Inst) // This PHI node will be in the new block created from the // splitBasicBlock call. - PHINode* PHI = PHINode::Create(Type::Int32Ty, "SetJmpReturn", Inst); + PHINode* PHI = PHINode::Create(Type::getInt32Ty(Inst->getContext()), + "SetJmpReturn", Inst); // Coming from a call to setjmp, the return is 0. - PHI->addIncoming(ConstantInt::getNullValue(Type::Int32Ty), ABlock); + PHI->addIncoming(Constant::getNullValue(Type::getInt32Ty(Inst->getContext())), + ABlock); // Add the case for this setjmp's number... SwitchValuePair SVP = GetSJSwitch(Func, GetRethrowBB(Func)); - SVP.first->addCase(ConstantInt::get(Type::Int32Ty, SetJmpIDMap[Func] - 1), + SVP.first->addCase(ConstantInt::get(Type::getInt32Ty(Inst->getContext()), + SetJmpIDMap[Func] - 1), SetJmpContBlock); // Value coming from the handling of the exception. @@ -503,7 +520,8 @@ void LowerSetJmp::visitInvokeInst(InvokeInst& II) BasicBlock* ExceptBB = II.getUnwindDest(); Function* Func = BB->getParent(); - BasicBlock* NewExceptBB = BasicBlock::Create("InvokeExcept", Func); + BasicBlock* NewExceptBB = BasicBlock::Create(II.getContext(), + "InvokeExcept", Func); // If this is a longjmp exception, then branch to the preliminary BB of // the longjmp exception handling. Otherwise, go to the old exception. diff --git a/lib/Transforms/IPO/MergeFunctions.cpp b/lib/Transforms/IPO/MergeFunctions.cpp index 5693cc0..13bbf9c 100644 --- a/lib/Transforms/IPO/MergeFunctions.cpp +++ b/lib/Transforms/IPO/MergeFunctions.cpp @@ -47,11 +47,14 @@ #include "llvm/Constants.h" #include "llvm/InlineAsm.h" #include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include <map> #include <vector> using namespace llvm; @@ -61,7 +64,7 @@ STATISTIC(NumFunctionsMerged, "Number of functions merged"); namespace { struct VISIBILITY_HIDDEN MergeFunctions : public ModulePass { static char ID; // Pass identification, replacement for typeid - MergeFunctions() : ModulePass((intptr_t)&ID) {} + MergeFunctions() : ModulePass(&ID) {} bool runOnModule(Module &M); }; @@ -127,7 +130,7 @@ static bool isEquivalentType(const Type *Ty1, const Type *Ty2) { return false; default: - assert(0 && "Unknown type!"); + llvm_unreachable("Unknown type!"); return false; case Type::PointerTyID: { @@ -185,7 +188,8 @@ static bool isEquivalentOperation(const Instruction *I1, const Instruction *I2) { if (I1->getOpcode() != I2->getOpcode() || I1->getNumOperands() != I2->getNumOperands() || - !isEquivalentType(I1->getType(), I2->getType())) + !isEquivalentType(I1->getType(), I2->getType()) || + !I1->hasSameSubclassOptionalData(I2)) return false; // We have two instructions of identical opcode and #operands. Check to see @@ -449,6 +453,7 @@ static LinkageCategory categorize(const Function *F) { switch (F->getLinkage()) { case GlobalValue::InternalLinkage: case GlobalValue::PrivateLinkage: + case GlobalValue::LinkerPrivateLinkage: return Internal; case GlobalValue::WeakAnyLinkage: @@ -468,14 +473,14 @@ static LinkageCategory categorize(const Function *F) { return ExternalStrong; } - assert(0 && "Unknown LinkageType."); + llvm_unreachable("Unknown LinkageType."); return ExternalWeak; } static void ThunkGToF(Function *F, Function *G) { Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", G->getParent()); - BasicBlock *BB = BasicBlock::Create("", NewG); + BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); std::vector<Value *> Args; unsigned i = 0; @@ -494,13 +499,13 @@ static void ThunkGToF(Function *F, Function *G) { CallInst *CI = CallInst::Create(F, Args.begin(), Args.end(), "", BB); CI->setTailCall(); CI->setCallingConv(F->getCallingConv()); - if (NewG->getReturnType() == Type::VoidTy) { - ReturnInst::Create(BB); + if (NewG->getReturnType() == Type::getVoidTy(F->getContext())) { + ReturnInst::Create(F->getContext(), BB); } else if (CI->getType() != NewG->getReturnType()) { Value *BCI = new BitCastInst(CI, NewG->getReturnType(), "", BB); - ReturnInst::Create(BCI, BB); + ReturnInst::Create(F->getContext(), BCI, BB); } else { - ReturnInst::Create(CI, BB); + ReturnInst::Create(F->getContext(), CI, BB); } NewG->copyAttributesFrom(G); @@ -574,22 +579,22 @@ static bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) { case Internal: switch (catG) { case ExternalStrong: - assert(0); + llvm_unreachable(0); // fall-through case ExternalWeak: - if (F->hasAddressTaken()) + if (F->hasAddressTaken()) ThunkGToF(F, G); else AliasGToF(F, G); - break; + break; case Internal: { bool addrTakenF = F->hasAddressTaken(); bool addrTakenG = G->hasAddressTaken(); if (!addrTakenF && addrTakenG) { std::swap(FnVec[i], FnVec[j]); std::swap(F, G); - std::swap(addrTakenF, addrTakenG); - } + std::swap(addrTakenF, addrTakenG); + } if (addrTakenF && addrTakenG) { ThunkGToF(F, G); @@ -597,7 +602,7 @@ static bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) { assert(!addrTakenG); AliasGToF(F, G); } - } break; + } break; } break; } @@ -629,19 +634,19 @@ bool MergeFunctions::runOnModule(Module &M) { bool LocalChanged; do { LocalChanged = false; - DOUT << "size: " << FnMap.size() << "\n"; + DEBUG(errs() << "size: " << FnMap.size() << "\n"); for (std::map<unsigned long, std::vector<Function *> >::iterator I = FnMap.begin(), E = FnMap.end(); I != E; ++I) { std::vector<Function *> &FnVec = I->second; - DOUT << "hash (" << I->first << "): " << FnVec.size() << "\n"; + DEBUG(errs() << "hash (" << I->first << "): " << FnVec.size() << "\n"); for (int i = 0, e = FnVec.size(); i != e; ++i) { for (int j = i + 1; j != e; ++j) { bool isEqual = equals(FnVec[i], FnVec[j]); - DOUT << " " << FnVec[i]->getName() - << (isEqual ? " == " : " != ") - << FnVec[j]->getName() << "\n"; + DEBUG(errs() << " " << FnVec[i]->getName() + << (isEqual ? " == " : " != ") + << FnVec[j]->getName() << "\n"); if (isEqual) { if (fold(FnVec, i, j)) { diff --git a/lib/Transforms/IPO/PartialInlining.cpp b/lib/Transforms/IPO/PartialInlining.cpp index 73ec9c1..8f858d3 100644 --- a/lib/Transforms/IPO/PartialInlining.cpp +++ b/lib/Transforms/IPO/PartialInlining.cpp @@ -48,7 +48,8 @@ ModulePass* llvm::createPartialInliningPass() { return new PartialInliner(); } Function* PartialInliner::unswitchFunction(Function* F) { // First, verify that this function is an unswitching candidate... BasicBlock* entryBlock = F->begin(); - if (!isa<BranchInst>(entryBlock->getTerminator())) + BranchInst *BR = dyn_cast<BranchInst>(entryBlock->getTerminator()); + if (!BR || BR->isUnconditional()) return 0; BasicBlock* returnBlock = 0; diff --git a/lib/Transforms/IPO/PruneEH.cpp b/lib/Transforms/IPO/PruneEH.cpp index 2b52f46..daf81e9 100644 --- a/lib/Transforms/IPO/PruneEH.cpp +++ b/lib/Transforms/IPO/PruneEH.cpp @@ -19,6 +19,7 @@ #include "llvm/CallGraphSCCPass.h" #include "llvm/Constants.h" #include "llvm/Function.h" +#include "llvm/LLVMContext.h" #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/Analysis/CallGraph.h" @@ -40,7 +41,7 @@ namespace { PruneEH() : CallGraphSCCPass(&ID) {} // runOnSCC - Analyze the SCC, performing the transformation if possible. - bool runOnSCC(const std::vector<CallGraphNode *> &SCC); + bool runOnSCC(std::vector<CallGraphNode *> &SCC); bool SimplifyFunction(Function *F); void DeleteBasicBlock(BasicBlock *BB); @@ -54,7 +55,7 @@ X("prune-eh", "Remove unused exception handling info"); Pass *llvm::createPruneEHPass() { return new PruneEH(); } -bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) { +bool PruneEH::runOnSCC(std::vector<CallGraphNode *> &SCC) { SmallPtrSet<CallGraphNode *, 8> SCCNodes; CallGraph &CG = getAnalysis<CallGraph>(); bool MadeChange = false; @@ -164,9 +165,6 @@ bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) { // function if we have invokes to non-unwinding functions or code after calls to // no-return functions. bool PruneEH::SimplifyFunction(Function *F) { - CallGraph &CG = getAnalysis<CallGraph>(); - CallGraphNode *CGN = CG[F]; - bool MadeChange = false; for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) @@ -180,14 +178,13 @@ bool PruneEH::SimplifyFunction(Function *F) { Call->setAttributes(II->getAttributes()); // Anything that used the value produced by the invoke instruction - // now uses the value produced by the call instruction. + // now uses the value produced by the call instruction. Note that we + // do this even for void functions and calls with no uses so that the + // callgraph edge is updated. II->replaceAllUsesWith(Call); BasicBlock *UnwindBlock = II->getUnwindDest(); UnwindBlock->removePredecessor(II->getParent()); - // Fix up the call graph. - CGN->replaceCallSite(II, Call); - // Insert a branch to the normal destination right before the // invoke. BranchInst::Create(II->getNormalDest(), II); @@ -214,7 +211,7 @@ bool PruneEH::SimplifyFunction(Function *F) { // Remove the uncond branch and add an unreachable. BB->getInstList().pop_back(); - new UnreachableInst(BB); + new UnreachableInst(BB->getContext(), BB); DeleteBasicBlock(New); // Delete the new BB. MadeChange = true; diff --git a/lib/Transforms/IPO/RaiseAllocations.cpp b/lib/Transforms/IPO/RaiseAllocations.cpp index 9900368..4c1f26d 100644 --- a/lib/Transforms/IPO/RaiseAllocations.cpp +++ b/lib/Transforms/IPO/RaiseAllocations.cpp @@ -16,6 +16,7 @@ #include "llvm/Transforms/IPO.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Instructions.h" #include "llvm/Pass.h" @@ -69,7 +70,6 @@ ModulePass *llvm::createRaiseAllocationsPass() { // function into the appropriate instruction. // void RaiseAllocations::doInitialization(Module &M) { - // Get Malloc and free prototypes if they exist! MallocFunc = M.getFunction("malloc"); if (MallocFunc) { @@ -77,22 +77,27 @@ void RaiseAllocations::doInitialization(Module &M) { // Get the expected prototype for malloc const FunctionType *Malloc1Type = - FunctionType::get(PointerType::getUnqual(Type::Int8Ty), - std::vector<const Type*>(1, Type::Int64Ty), false); + FunctionType::get(Type::getInt8PtrTy(M.getContext()), + std::vector<const Type*>(1, + Type::getInt64Ty(M.getContext())), false); // Chck to see if we got the expected malloc if (TyWeHave != Malloc1Type) { // Check to see if the prototype is wrong, giving us i8*(i32) * malloc // This handles the common declaration of: 'void *malloc(unsigned);' const FunctionType *Malloc2Type = - FunctionType::get(PointerType::getUnqual(Type::Int8Ty), - std::vector<const Type*>(1, Type::Int32Ty), false); + FunctionType::get(PointerType::getUnqual( + Type::getInt8Ty(M.getContext())), + std::vector<const Type*>(1, + Type::getInt32Ty(M.getContext())), false); if (TyWeHave != Malloc2Type) { // Check to see if the prototype is missing, giving us // i8*(...) * malloc // This handles the common declaration of: 'void *malloc();' const FunctionType *Malloc3Type = - FunctionType::get(PointerType::getUnqual(Type::Int8Ty), true); + FunctionType::get(PointerType::getUnqual( + Type::getInt8Ty(M.getContext())), + true); if (TyWeHave != Malloc3Type) // Give up MallocFunc = 0; @@ -105,19 +110,24 @@ void RaiseAllocations::doInitialization(Module &M) { const FunctionType* TyWeHave = FreeFunc->getFunctionType(); // Get the expected prototype for void free(i8*) - const FunctionType *Free1Type = FunctionType::get(Type::VoidTy, - std::vector<const Type*>(1, PointerType::getUnqual(Type::Int8Ty)), false); + const FunctionType *Free1Type = + FunctionType::get(Type::getVoidTy(M.getContext()), + std::vector<const Type*>(1, PointerType::getUnqual( + Type::getInt8Ty(M.getContext()))), + false); if (TyWeHave != Free1Type) { // Check to see if the prototype was forgotten, giving us // void (...) * free // This handles the common forward declaration of: 'void free();' - const FunctionType* Free2Type = FunctionType::get(Type::VoidTy, true); + const FunctionType* Free2Type = + FunctionType::get(Type::getVoidTy(M.getContext()), true); if (TyWeHave != Free2Type) { // One last try, check to see if we can find free as // int (...)* free. This handles the case where NOTHING was declared. - const FunctionType* Free3Type = FunctionType::get(Type::Int32Ty, true); + const FunctionType* Free3Type = + FunctionType::get(Type::getInt32Ty(M.getContext()), true); if (TyWeHave != Free3Type) { // Give up. @@ -137,7 +147,7 @@ void RaiseAllocations::doInitialization(Module &M) { bool RaiseAllocations::runOnModule(Module &M) { // Find the malloc/free prototypes... doInitialization(M); - + bool Changed = false; // First, process all of the malloc calls... @@ -159,12 +169,15 @@ bool RaiseAllocations::runOnModule(Module &M) { // If no prototype was provided for malloc, we may need to cast the // source size. - if (Source->getType() != Type::Int32Ty) + if (Source->getType() != Type::getInt32Ty(M.getContext())) Source = - CastInst::CreateIntegerCast(Source, Type::Int32Ty, false/*ZExt*/, + CastInst::CreateIntegerCast(Source, + Type::getInt32Ty(M.getContext()), + false/*ZExt*/, "MallocAmtCast", I); - MallocInst *MI = new MallocInst(Type::Int8Ty, Source, "", I); + MallocInst *MI = new MallocInst(Type::getInt8Ty(M.getContext()), + Source, "", I); MI->takeName(I); I->replaceAllUsesWith(MI); @@ -216,7 +229,7 @@ bool RaiseAllocations::runOnModule(Module &M) { Value *Source = *CS.arg_begin(); if (!isa<PointerType>(Source->getType())) Source = new IntToPtrInst(Source, - PointerType::getUnqual(Type::Int8Ty), + Type::getInt8PtrTy(M.getContext()), "FreePtrCast", I); new FreeInst(Source, I); @@ -226,7 +239,7 @@ bool RaiseAllocations::runOnModule(Module &M) { BranchInst::Create(II->getNormalDest(), I); // Delete the old call site - if (I->getType() != Type::VoidTy) + if (I->getType() != Type::getVoidTy(M.getContext())) I->replaceAllUsesWith(UndefValue::get(I->getType())); I->eraseFromParent(); Changed = true; diff --git a/lib/Transforms/IPO/StripSymbols.cpp b/lib/Transforms/IPO/StripSymbols.cpp index 046e044..77d44b2 100644 --- a/lib/Transforms/IPO/StripSymbols.cpp +++ b/lib/Transforms/IPO/StripSymbols.cpp @@ -24,18 +24,18 @@ #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Analysis/DebugInfo.h" #include "llvm/ValueSymbolTable.h" #include "llvm/TypeSymbolTable.h" #include "llvm/Transforms/Utils/Local.h" -#include "llvm/Support/Compiler.h" #include "llvm/ADT/SmallPtrSet.h" using namespace llvm; namespace { - class VISIBILITY_HIDDEN StripSymbols : public ModulePass { + class StripSymbols : public ModulePass { bool OnlyDebugInfo; public: static char ID; // Pass identification, replacement for typeid @@ -49,7 +49,7 @@ namespace { } }; - class VISIBILITY_HIDDEN StripNonDebugSymbols : public ModulePass { + class StripNonDebugSymbols : public ModulePass { public: static char ID; // Pass identification, replacement for typeid explicit StripNonDebugSymbols() @@ -62,7 +62,7 @@ namespace { } }; - class VISIBILITY_HIDDEN StripDebugDeclare : public ModulePass { + class StripDebugDeclare : public ModulePass { public: static char ID; // Pass identification, replacement for typeid explicit StripDebugDeclare() @@ -138,7 +138,7 @@ static void StripSymtab(ValueSymbolTable &ST, bool PreserveDbgInfo) { Value *V = VI->getValue(); ++VI; if (!isa<GlobalValue>(V) || cast<GlobalValue>(V)->hasLocalLinkage()) { - if (!PreserveDbgInfo || strncmp(V->getNameStart(), "llvm.dbg", 8)) + if (!PreserveDbgInfo || !V->getName().startswith("llvm.dbg")) // Set name to "", removing from symbol table! V->setName(""); } @@ -156,43 +156,37 @@ static void StripTypeSymtab(TypeSymbolTable &ST, bool PreserveDbgInfo) { } /// Find values that are marked as llvm.used. -void findUsedValues(Module &M, - SmallPtrSet<const GlobalValue*, 8>& llvmUsedValues) { - if (GlobalVariable *LLVMUsed = M.getGlobalVariable("llvm.used")) { - llvmUsedValues.insert(LLVMUsed); - // Collect values that are preserved as per explicit request. - // llvm.used is used to list these values. - if (ConstantArray *Inits = - dyn_cast<ConstantArray>(LLVMUsed->getInitializer())) { - for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) { - if (GlobalValue *GV = dyn_cast<GlobalValue>(Inits->getOperand(i))) - llvmUsedValues.insert(GV); - else if (ConstantExpr *CE = - dyn_cast<ConstantExpr>(Inits->getOperand(i))) - if (CE->getOpcode() == Instruction::BitCast) - if (GlobalValue *GV = dyn_cast<GlobalValue>(CE->getOperand(0))) - llvmUsedValues.insert(GV); - } - } - } +static void findUsedValues(GlobalVariable *LLVMUsed, + SmallPtrSet<const GlobalValue*, 8> &UsedValues) { + if (LLVMUsed == 0) return; + UsedValues.insert(LLVMUsed); + + ConstantArray *Inits = dyn_cast<ConstantArray>(LLVMUsed->getInitializer()); + if (Inits == 0) return; + + for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) + if (GlobalValue *GV = + dyn_cast<GlobalValue>(Inits->getOperand(i)->stripPointerCasts())) + UsedValues.insert(GV); } /// StripSymbolNames - Strip symbol names. -bool StripSymbolNames(Module &M, bool PreserveDbgInfo) { +static bool StripSymbolNames(Module &M, bool PreserveDbgInfo) { SmallPtrSet<const GlobalValue*, 8> llvmUsedValues; - findUsedValues(M, llvmUsedValues); + findUsedValues(M.getGlobalVariable("llvm.used"), llvmUsedValues); + findUsedValues(M.getGlobalVariable("llvm.compiler.used"), llvmUsedValues); for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) { if (I->hasLocalLinkage() && llvmUsedValues.count(I) == 0) - if (!PreserveDbgInfo || strncmp(I->getNameStart(), "llvm.dbg", 8)) + if (!PreserveDbgInfo || !I->getName().startswith("llvm.dbg")) I->setName(""); // Internal symbols can't participate in linkage } for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { if (I->hasLocalLinkage() && llvmUsedValues.count(I) == 0) - if (!PreserveDbgInfo || strncmp(I->getNameStart(), "llvm.dbg", 8)) + if (!PreserveDbgInfo || !I->getName().startswith("llvm.dbg")) I->setName(""); // Internal symbols can't participate in linkage StripSymtab(I->getValueSymbolTable(), PreserveDbgInfo); } @@ -206,169 +200,58 @@ bool StripSymbolNames(Module &M, bool PreserveDbgInfo) { // StripDebugInfo - Strip debug info in the module if it exists. // To do this, we remove llvm.dbg.func.start, llvm.dbg.stoppoint, and // llvm.dbg.region.end calls, and any globals they point to if now dead. -bool StripDebugInfo(Module &M) { - - SmallPtrSet<const GlobalValue*, 8> llvmUsedValues; - findUsedValues(M, llvmUsedValues); - - SmallVector<GlobalVariable *, 2> CUs; - SmallVector<GlobalVariable *, 4> GVs; - SmallVector<GlobalVariable *, 4> SPs; - CollectDebugInfoAnchors(M, CUs, GVs, SPs); - // These anchors use LinkOnce linkage so that the optimizer does not - // remove them accidently. Set InternalLinkage for all these debug - // info anchors. - for (SmallVector<GlobalVariable *, 2>::iterator I = CUs.begin(), - E = CUs.end(); I != E; ++I) - (*I)->setLinkage(GlobalValue::InternalLinkage); - for (SmallVector<GlobalVariable *, 4>::iterator I = GVs.begin(), - E = GVs.end(); I != E; ++I) - (*I)->setLinkage(GlobalValue::InternalLinkage); - for (SmallVector<GlobalVariable *, 4>::iterator I = SPs.begin(), - E = SPs.end(); I != E; ++I) - (*I)->setLinkage(GlobalValue::InternalLinkage); - - - // Delete all dbg variables. - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) { - GlobalVariable *GV = dyn_cast<GlobalVariable>(I); - if (!GV) continue; - if (!GV->use_empty() && llvmUsedValues.count(I) == 0) { - if (strncmp(GV->getNameStart(), "llvm.dbg", 8) == 0) { - GV->replaceAllUsesWith(UndefValue::get(GV->getType())); - } - } - } +static bool StripDebugInfo(Module &M) { + // Remove all of the calls to the debugger intrinsics, and remove them from + // the module. Function *FuncStart = M.getFunction("llvm.dbg.func.start"); Function *StopPoint = M.getFunction("llvm.dbg.stoppoint"); Function *RegionStart = M.getFunction("llvm.dbg.region.start"); Function *RegionEnd = M.getFunction("llvm.dbg.region.end"); Function *Declare = M.getFunction("llvm.dbg.declare"); - std::vector<Constant*> DeadConstants; - - // Remove all of the calls to the debugger intrinsics, and remove them from - // the module. if (FuncStart) { while (!FuncStart->use_empty()) { CallInst *CI = cast<CallInst>(FuncStart->use_back()); - Value *Arg = CI->getOperand(1); - assert(CI->use_empty() && "llvm.dbg intrinsic should have void result"); CI->eraseFromParent(); - if (Arg->use_empty()) - if (Constant *C = dyn_cast<Constant>(Arg)) - DeadConstants.push_back(C); } FuncStart->eraseFromParent(); } if (StopPoint) { while (!StopPoint->use_empty()) { CallInst *CI = cast<CallInst>(StopPoint->use_back()); - Value *Arg = CI->getOperand(3); - assert(CI->use_empty() && "llvm.dbg intrinsic should have void result"); CI->eraseFromParent(); - if (Arg->use_empty()) - if (Constant *C = dyn_cast<Constant>(Arg)) - DeadConstants.push_back(C); } StopPoint->eraseFromParent(); } if (RegionStart) { while (!RegionStart->use_empty()) { CallInst *CI = cast<CallInst>(RegionStart->use_back()); - Value *Arg = CI->getOperand(1); - assert(CI->use_empty() && "llvm.dbg intrinsic should have void result"); CI->eraseFromParent(); - if (Arg->use_empty()) - if (Constant *C = dyn_cast<Constant>(Arg)) - DeadConstants.push_back(C); } RegionStart->eraseFromParent(); } if (RegionEnd) { while (!RegionEnd->use_empty()) { CallInst *CI = cast<CallInst>(RegionEnd->use_back()); - Value *Arg = CI->getOperand(1); - assert(CI->use_empty() && "llvm.dbg intrinsic should have void result"); CI->eraseFromParent(); - if (Arg->use_empty()) - if (Constant *C = dyn_cast<Constant>(Arg)) - DeadConstants.push_back(C); } RegionEnd->eraseFromParent(); } if (Declare) { while (!Declare->use_empty()) { CallInst *CI = cast<CallInst>(Declare->use_back()); - Value *Arg1 = CI->getOperand(1); - Value *Arg2 = CI->getOperand(2); - assert(CI->use_empty() && "llvm.dbg intrinsic should have void result"); CI->eraseFromParent(); - if (Arg1->use_empty()) { - if (Constant *C = dyn_cast<Constant>(Arg1)) - DeadConstants.push_back(C); - else - RecursivelyDeleteTriviallyDeadInstructions(Arg1); - } - if (Arg2->use_empty()) - if (Constant *C = dyn_cast<Constant>(Arg2)) - DeadConstants.push_back(C); } Declare->eraseFromParent(); } - // llvm.dbg.compile_units and llvm.dbg.subprograms are marked as linkonce - // but since we are removing all debug information, make them internal now. - // FIXME: Use private linkage maybe? - if (Constant *C = M.getNamedGlobal("llvm.dbg.compile_units")) - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) - GV->setLinkage(GlobalValue::InternalLinkage); - - if (Constant *C = M.getNamedGlobal("llvm.dbg.subprograms")) - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) - GV->setLinkage(GlobalValue::InternalLinkage); - - if (Constant *C = M.getNamedGlobal("llvm.dbg.global_variables")) - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) - GV->setLinkage(GlobalValue::InternalLinkage); - - // Delete all dbg variables. - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) { - GlobalVariable *GV = dyn_cast<GlobalVariable>(I); - if (!GV) continue; - if (GV->use_empty() && llvmUsedValues.count(I) == 0 - && (!GV->hasSection() - || strcmp(GV->getSection().c_str(), "llvm.metadata") == 0)) - DeadConstants.push_back(GV); - } - - if (DeadConstants.empty()) - return false; + NamedMDNode *NMD = M.getNamedMetadata("llvm.dbg.gv"); + if (NMD) + NMD->eraseFromParent(); - // Delete any internal globals that were only used by the debugger intrinsics. - while (!DeadConstants.empty()) { - Constant *C = DeadConstants.back(); - DeadConstants.pop_back(); - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) { - if (GV->hasLocalLinkage()) - RemoveDeadConstant(GV); - } - else - RemoveDeadConstant(C); - } - - // Remove all llvm.dbg types. - TypeSymbolTable &ST = M.getTypeSymbolTable(); - for (TypeSymbolTable::iterator TI = ST.begin(), TE = ST.end(); TI != TE; ) { - if (!strncmp(TI->first.c_str(), "llvm.dbg.", 9)) - ST.remove(TI++); - else - ++TI; - } - + // Remove dead metadata. + M.getContext().RemoveDeadMetadata(); return true; } @@ -414,8 +297,7 @@ bool StripDebugDeclare::runOnModule(Module &M) { I != E; ++I) { GlobalVariable *GV = dyn_cast<GlobalVariable>(I); if (!GV) continue; - if (GV->use_empty() && GV->hasName() - && strncmp(GV->getNameStart(), "llvm.dbg.global_variable", 24) == 0) + if (GV->use_empty() && GV->getName().startswith("llvm.dbg.global_variable")) DeadConstants.push_back(GV); } diff --git a/lib/Transforms/IPO/StructRetPromotion.cpp b/lib/Transforms/IPO/StructRetPromotion.cpp index 9f54388..4442820 100644 --- a/lib/Transforms/IPO/StructRetPromotion.cpp +++ b/lib/Transforms/IPO/StructRetPromotion.cpp @@ -23,6 +23,7 @@ #include "llvm/Transforms/IPO.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/CallGraphSCCPass.h" #include "llvm/Instructions.h" @@ -34,6 +35,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; STATISTIC(NumRejectedSRETUses , "Number of sret rejected due to unexpected uses"); @@ -47,15 +49,15 @@ namespace { CallGraphSCCPass::getAnalysisUsage(AU); } - virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC); + virtual bool runOnSCC(std::vector<CallGraphNode *> &SCC); static char ID; // Pass identification, replacement for typeid SRETPromotion() : CallGraphSCCPass(&ID) {} private: - bool PromoteReturn(CallGraphNode *CGN); + CallGraphNode *PromoteReturn(CallGraphNode *CGN); bool isSafeToUpdateAllCallers(Function *F); Function *cloneFunctionBody(Function *F, const StructType *STy); - void updateCallSites(Function *F, Function *NF); + CallGraphNode *updateCallSites(Function *F, Function *NF); bool nestedStructType(const StructType *STy); }; } @@ -68,49 +70,54 @@ Pass *llvm::createStructRetPromotionPass() { return new SRETPromotion(); } -bool SRETPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) { +bool SRETPromotion::runOnSCC(std::vector<CallGraphNode *> &SCC) { bool Changed = false; for (unsigned i = 0, e = SCC.size(); i != e; ++i) - Changed |= PromoteReturn(SCC[i]); + if (CallGraphNode *NewNode = PromoteReturn(SCC[i])) { + SCC[i] = NewNode; + Changed = true; + } return Changed; } /// PromoteReturn - This method promotes function that uses StructRet paramater -/// into a function that uses mulitple return value. -bool SRETPromotion::PromoteReturn(CallGraphNode *CGN) { +/// into a function that uses multiple return values. +CallGraphNode *SRETPromotion::PromoteReturn(CallGraphNode *CGN) { Function *F = CGN->getFunction(); if (!F || F->isDeclaration() || !F->hasLocalLinkage()) - return false; + return 0; // Make sure that function returns struct. if (F->arg_size() == 0 || !F->hasStructRetAttr() || F->doesNotReturn()) - return false; + return 0; - DOUT << "SretPromotion: Looking at sret function " << F->getNameStart() << "\n"; + DEBUG(errs() << "SretPromotion: Looking at sret function " + << F->getName() << "\n"); - assert (F->getReturnType() == Type::VoidTy && "Invalid function return type"); + assert(F->getReturnType() == Type::getVoidTy(F->getContext()) && + "Invalid function return type"); Function::arg_iterator AI = F->arg_begin(); const llvm::PointerType *FArgType = dyn_cast<PointerType>(AI->getType()); - assert (FArgType && "Invalid sret parameter type"); + assert(FArgType && "Invalid sret parameter type"); const llvm::StructType *STy = dyn_cast<StructType>(FArgType->getElementType()); - assert (STy && "Invalid sret parameter element type"); + assert(STy && "Invalid sret parameter element type"); // Check if it is ok to perform this promotion. if (isSafeToUpdateAllCallers(F) == false) { - DOUT << "SretPromotion: Not all callers can be updated\n"; + DEBUG(errs() << "SretPromotion: Not all callers can be updated\n"); NumRejectedSRETUses++; - return false; + return 0; } - DOUT << "SretPromotion: sret argument will be promoted\n"; + DEBUG(errs() << "SretPromotion: sret argument will be promoted\n"); NumSRET++; // [1] Replace use of sret parameter - AllocaInst *TheAlloca = new AllocaInst (STy, NULL, "mrv", - F->getEntryBlock().begin()); + AllocaInst *TheAlloca = new AllocaInst(STy, NULL, "mrv", + F->getEntryBlock().begin()); Value *NFirstArg = F->arg_begin(); NFirstArg->replaceAllUsesWith(TheAlloca); @@ -121,7 +128,7 @@ bool SRETPromotion::PromoteReturn(CallGraphNode *CGN) { ++BI; if (isa<ReturnInst>(I)) { Value *NV = new LoadInst(TheAlloca, "mrv.ld", I); - ReturnInst *NR = ReturnInst::Create(NV, I); + ReturnInst *NR = ReturnInst::Create(F->getContext(), NV, I); I->replaceAllUsesWith(NR); I->eraseFromParent(); } @@ -131,11 +138,13 @@ bool SRETPromotion::PromoteReturn(CallGraphNode *CGN) { Function *NF = cloneFunctionBody(F, STy); // [4] Update all call sites to use new function - updateCallSites(F, NF); + CallGraphNode *NF_CFN = updateCallSites(F, NF); - F->eraseFromParent(); - getAnalysis<CallGraph>().changeFunction(F, NF); - return true; + CallGraph &CG = getAnalysis<CallGraph>(); + NF_CFN->stealCalledFunctionsFrom(CG[F]); + + delete CG.removeFunctionFromModule(F); + return NF_CFN; } // Check if it is ok to perform this promotion. @@ -243,23 +252,26 @@ Function *SRETPromotion::cloneFunctionBody(Function *F, Function::arg_iterator NI = NF->arg_begin(); ++I; while (I != E) { - I->replaceAllUsesWith(NI); - NI->takeName(I); - ++I; - ++NI; + I->replaceAllUsesWith(NI); + NI->takeName(I); + ++I; + ++NI; } return NF; } /// updateCallSites - Update all sites that call F to use NF. -void SRETPromotion::updateCallSites(Function *F, Function *NF) { +CallGraphNode *SRETPromotion::updateCallSites(Function *F, Function *NF) { CallGraph &CG = getAnalysis<CallGraph>(); SmallVector<Value*, 16> Args; // Attributes - Keep track of the parameter attributes for the arguments. SmallVector<AttributeWithIndex, 8> ArgAttrsVec; + // Get a new callgraph node for NF. + CallGraphNode *NF_CGN = CG.getOrInsertFunction(NF); + while (!F->use_empty()) { CallSite CS = CallSite::get(*F->use_begin()); Instruction *Call = CS.getInstruction(); @@ -309,8 +321,10 @@ void SRETPromotion::updateCallSites(Function *F, Function *NF) { New->takeName(Call); // Update the callgraph to know that the callsite has been transformed. - CG[Call->getParent()->getParent()]->replaceCallSite(Call, New); - + CallGraphNode *CalleeNode = CG[Call->getParent()->getParent()]; + CalleeNode->removeCallEdgeFor(Call); + CalleeNode->addCalledFunction(New, NF_CGN); + // Update all users of sret parameter to extract value using extractvalue. for (Value::use_iterator UI = FirstCArg->use_begin(), UE = FirstCArg->use_end(); UI != UE; ) { @@ -318,24 +332,25 @@ void SRETPromotion::updateCallSites(Function *F, Function *NF) { CallInst *C2 = dyn_cast<CallInst>(U2); if (C2 && (C2 == Call)) continue; - else if (GetElementPtrInst *UGEP = dyn_cast<GetElementPtrInst>(U2)) { - ConstantInt *Idx = dyn_cast<ConstantInt>(UGEP->getOperand(2)); - assert (Idx && "Unexpected getelementptr index!"); - Value *GR = ExtractValueInst::Create(New, Idx->getZExtValue(), - "evi", UGEP); - while(!UGEP->use_empty()) { - // isSafeToUpdateAllCallers has checked that all GEP uses are - // LoadInsts - LoadInst *L = cast<LoadInst>(*UGEP->use_begin()); - L->replaceAllUsesWith(GR); - L->eraseFromParent(); - } - UGEP->eraseFromParent(); + + GetElementPtrInst *UGEP = cast<GetElementPtrInst>(U2); + ConstantInt *Idx = cast<ConstantInt>(UGEP->getOperand(2)); + Value *GR = ExtractValueInst::Create(New, Idx->getZExtValue(), + "evi", UGEP); + while(!UGEP->use_empty()) { + // isSafeToUpdateAllCallers has checked that all GEP uses are + // LoadInsts + LoadInst *L = cast<LoadInst>(*UGEP->use_begin()); + L->replaceAllUsesWith(GR); + L->eraseFromParent(); } - else assert( 0 && "Unexpected sret parameter use"); + UGEP->eraseFromParent(); + continue; } Call->eraseFromParent(); } + + return NF_CGN; } /// nestedStructType - Return true if STy includes any @@ -344,7 +359,7 @@ bool SRETPromotion::nestedStructType(const StructType *STy) { unsigned Num = STy->getNumElements(); for (unsigned i = 0; i < Num; i++) { const Type *Ty = STy->getElementType(i); - if (!Ty->isSingleValueType() && Ty != Type::VoidTy) + if (!Ty->isSingleValueType() && Ty != Type::getVoidTy(STy->getContext())) return true; } return false; |
