diff options
author | Roman Divacky <rdivacky@FreeBSD.org> | 2010-04-02 08:54:30 +0000 |
---|---|---|
committer | Roman Divacky <rdivacky@FreeBSD.org> | 2010-04-02 08:54:30 +0000 |
commit | 104bd8179fb5f6551c65c94ebcd0a4918b060189 (patch) | |
tree | cf5763d092b81cecc168fa28032247ee495d06e2 /lib/Transforms | |
parent | 2f12f10af369d468b14617276446166383d692ed (diff) |
Notes
Diffstat (limited to 'lib/Transforms')
21 files changed, 648 insertions, 453 deletions
diff --git a/lib/Transforms/IPO/ArgumentPromotion.cpp b/lib/Transforms/IPO/ArgumentPromotion.cpp index 7cb13671bca57..40a87e880d7bf 100644 --- a/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -623,6 +623,7 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F, SmallVector<Value*, 16> Args; while (!F->use_empty()) { CallSite CS = CallSite::get(F->use_back()); + assert(CS.getCalledFunction() == F); Instruction *Call = CS.getInstruction(); const AttrListPtr &CallPAL = CS.getAttributes(); @@ -660,7 +661,7 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F, // Non-dead argument: insert GEPs and loads as appropriate. ScalarizeTable &ArgIndices = ScalarizedElements[I]; // Store the Value* version of the indices in here, but declare it now - // for reuse + // for reuse. std::vector<Value*> Ops; for (ScalarizeTable::iterator SI = ArgIndices.begin(), E = ArgIndices.end(); SI != E; ++SI) { @@ -677,16 +678,20 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F, Type::getInt32Ty(F->getContext()) : Type::getInt64Ty(F->getContext())); Ops.push_back(ConstantInt::get(IdxTy, *II)); - // Keep track of the type we're currently indexing + // Keep track of the type we're currently indexing. ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(*II); } - // And create a GEP to extract those indices + // And create a GEP to extract those indices. V = GetElementPtrInst::Create(V, Ops.begin(), Ops.end(), V->getName()+".idx", Call); Ops.clear(); AA.copyValue(OrigLoad->getOperand(0), V); } - Args.push_back(new LoadInst(V, V->getName()+".val", Call)); + // Since we're replacing a load make sure we take the alignment + // of the previous load. + LoadInst *newLoad = new LoadInst(V, V->getName()+".val", Call); + newLoad->setAlignment(OrigLoad->getAlignment()); + Args.push_back(newLoad); AA.copyValue(OrigLoad, Args.back()); } } @@ -694,7 +699,7 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F, if (ExtraArgHack) Args.push_back(Constant::getNullValue(Type::getInt32Ty(F->getContext()))); - // Push any varargs arguments on the list + // Push any varargs arguments on the list. for (; AI != CS.arg_end(); ++AI, ++ArgIndex) { Args.push_back(*AI); if (Attributes Attrs = CallPAL.getParamAttributes(ArgIndex)) diff --git a/lib/Transforms/IPO/DeadArgumentElimination.cpp b/lib/Transforms/IPO/DeadArgumentElimination.cpp index f386ed78b5f54..227602d19f568 100644 --- a/lib/Transforms/IPO/DeadArgumentElimination.cpp +++ b/lib/Transforms/IPO/DeadArgumentElimination.cpp @@ -50,7 +50,7 @@ namespace { /// argument. Used so that arguments and return values can be used /// interchangably. struct RetOrArg { - RetOrArg(const Function* F, unsigned Idx, bool IsArg) : F(F), Idx(Idx), + RetOrArg(const Function *F, unsigned Idx, bool IsArg) : F(F), Idx(Idx), IsArg(IsArg) {} const Function *F; unsigned Idx; @@ -72,7 +72,7 @@ namespace { } std::string getDescription() const { - return std::string((IsArg ? "Argument #" : "Return value #")) + return std::string((IsArg ? "Argument #" : "Return value #")) + utostr(Idx) + " of function " + F->getNameStr(); } }; @@ -129,11 +129,11 @@ namespace { private: Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); - Liveness SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, + Liveness SurveyUse(Value::const_use_iterator U, UseVector &MaybeLiveUses, unsigned RetValNum = 0); - Liveness SurveyUses(Value *V, UseVector &MaybeLiveUses); + Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); - void SurveyFunction(Function &F); + void SurveyFunction(const Function &F); void MarkValue(const RetOrArg &RA, Liveness L, const UseVector &MaybeLiveUses); void MarkLive(const RetOrArg &RA); @@ -196,7 +196,7 @@ 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); @@ -225,7 +225,7 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { SmallVector<AttributeWithIndex, 8> AttributesVec; for (unsigned i = 0; PAL.getSlot(i).Index <= NumArgs; ++i) AttributesVec.push_back(PAL.getSlot(i)); - if (Attributes FnAttrs = PAL.getFnAttributes()) + if (Attributes FnAttrs = PAL.getFnAttributes()) AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs)); PAL = AttrListPtr::get(AttributesVec.begin(), AttributesVec.end()); } @@ -280,7 +280,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::getVoidTy(F->getContext())) + if (F->getReturnType()->isVoidTy()) return 0; else if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) return STy->getNumElements(); @@ -305,15 +305,15 @@ DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) { /// SurveyUse - This looks at a single use of an argument or return value /// and determines if it should be alive or not. Adds this use to MaybeLiveUses -/// if it causes the used value to become MaybeAlive. +/// if it causes the used value to become MaybeLive. /// /// RetValNum is the return value number to use when this use is used in a /// return instruction. This is used in the recursion, you should always leave /// it at 0. -DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, - unsigned RetValNum) { - Value *V = *U; - if (ReturnInst *RI = dyn_cast<ReturnInst>(V)) { +DAE::Liveness DAE::SurveyUse(Value::const_use_iterator U, + UseVector &MaybeLiveUses, unsigned RetValNum) { + const User *V = *U; + if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { // The value is returned from a function. It's only live when the // function's return value is live. We use RetValNum here, for the case // that U is really a use of an insertvalue instruction that uses the @@ -322,7 +322,7 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, // We might be live, depending on the liveness of Use. return MarkIfNotLive(Use, MaybeLiveUses); } - if (InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { + if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { if (U.getOperandNo() != InsertValueInst::getAggregateOperandIndex() && IV->hasIndices()) // The use we are examining is inserted into an aggregate. Our liveness @@ -334,7 +334,7 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, // we don't change RetValNum, but do survey all our uses. Liveness Result = MaybeLive; - for (Value::use_iterator I = IV->use_begin(), + for (Value::const_use_iterator I = IV->use_begin(), E = V->use_end(); I != E; ++I) { Result = SurveyUse(I, MaybeLiveUses, RetValNum); if (Result == Live) @@ -342,24 +342,24 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, } return Result; } - CallSite CS = CallSite::get(V); - if (CS.getInstruction()) { - Function *F = CS.getCalledFunction(); + + if (ImmutableCallSite CS = V) { + const Function *F = CS.getCalledFunction(); if (F) { // Used in a direct call. - + // Find the argument number. We know for sure that this use is an // argument, since if it was the function argument this would be an // indirect call and the we know can't be looking at a value of the // label type (for the invoke instruction). - unsigned ArgNo = CS.getArgumentNo(U.getOperandNo()); + unsigned ArgNo = CS.getArgumentNo(U); if (ArgNo >= F->getFunctionType()->getNumParams()) // The value is passed in through a vararg! Must be live. return Live; - assert(CS.getArgument(ArgNo) - == CS.getInstruction()->getOperand(U.getOperandNo()) + assert(CS.getArgument(ArgNo) + == CS->getOperand(U.getOperandNo()) && "Argument is not where we expected it"); // Value passed to a normal call. It's only live when the corresponding @@ -378,11 +378,11 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If /// the result is Live, MaybeLiveUses might be modified but its content should /// be ignored (since it might not be complete). -DAE::Liveness DAE::SurveyUses(Value *V, UseVector &MaybeLiveUses) { +DAE::Liveness DAE::SurveyUses(const Value *V, UseVector &MaybeLiveUses) { // Assume it's dead (which will only hold if there are no uses at all..). Liveness Result = MaybeLive; // Check each use. - for (Value::use_iterator I = V->use_begin(), + for (Value::const_use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) { Result = SurveyUse(I, MaybeLiveUses); if (Result == Live) @@ -399,7 +399,7 @@ DAE::Liveness DAE::SurveyUses(Value *V, UseVector &MaybeLiveUses) { // We consider arguments of non-internal functions to be intrinsically alive as // well as arguments to functions which have their "address taken". // -void DAE::SurveyFunction(Function &F) { +void DAE::SurveyFunction(const Function &F) { unsigned RetCount = NumRetVals(&F); // Assume all return values are dead typedef SmallVector<Liveness, 5> RetVals; @@ -411,8 +411,8 @@ void DAE::SurveyFunction(Function &F) { // MaybeLive. Initialized to a list of RetCount empty lists. RetUses MaybeLiveRetUses(RetCount); - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) + for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() != F.getFunctionType()->getReturnType()) { // We don't support old style multiple return values. @@ -431,17 +431,18 @@ void DAE::SurveyFunction(Function &F) { unsigned NumLiveRetVals = 0; const Type *STy = dyn_cast<StructType>(F.getReturnType()); // Loop all uses of the function. - for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { + for (Value::const_use_iterator I = F.use_begin(), E = F.use_end(); + I != E; ++I) { // If the function is PASSED IN as an argument, its address has been // taken. - CallSite CS = CallSite::get(*I); - if (!CS.getInstruction() || !CS.isCallee(I)) { + ImmutableCallSite CS(*I); + if (!CS || !CS.isCallee(I)) { MarkLive(F); return; } // If this use is anything other than a call site, the function is alive. - Instruction *TheCall = CS.getInstruction(); + const Instruction *TheCall = CS.getInstruction(); if (!TheCall) { // Not a direct call site? MarkLive(F); return; @@ -454,9 +455,9 @@ void DAE::SurveyFunction(Function &F) { if (NumLiveRetVals != RetCount) { if (STy) { // Check all uses of the return value. - for (Value::use_iterator I = TheCall->use_begin(), + for (Value::const_use_iterator I = TheCall->use_begin(), E = TheCall->use_end(); I != E; ++I) { - ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I); + const ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I); if (Ext && Ext->hasIndices()) { // This use uses a part of our return value, survey the uses of // that part and store the results for this index only. @@ -493,7 +494,7 @@ void DAE::SurveyFunction(Function &F) { // Now, check all of our arguments. unsigned i = 0; UseVector MaybeLiveArgUses; - for (Function::arg_iterator AI = F.arg_begin(), + for (Function::const_arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI, ++i) { // See what the effect of this use is (recording any uses that cause // MaybeLive in MaybeLiveArgUses). @@ -599,12 +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::getVoidTy(F->getContext())) { - NRetTy = Type::getVoidTy(F->getContext()); + if (RetTy->isVoidTy()) { + NRetTy = RetTy; } else { const StructType *STy = dyn_cast<StructType>(RetTy); if (STy) @@ -653,10 +654,10 @@ 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::getVoidTy(F->getContext())) + if (NRetTy->isVoidTy()) RAttrs &= ~Attribute::typeIncompatible(NRetTy); else - assert((RAttrs & Attribute::typeIncompatible(NRetTy)) == 0 + assert((RAttrs & Attribute::typeIncompatible(NRetTy)) == 0 && "Return attributes no longer compatible?"); if (RAttrs) @@ -686,11 +687,12 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { } } - if (FnAttrs != Attribute::None) + if (FnAttrs != Attribute::None) AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs)); // Reconstruct the AttributesList based on the vector we constructed. - AttrListPtr NewPAL = AttrListPtr::get(AttributesVec.begin(), AttributesVec.end()); + AttrListPtr NewPAL = AttrListPtr::get(AttributesVec.begin(), + AttributesVec.end()); // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which // have zero fixed arguments. @@ -705,8 +707,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { } // 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) @@ -791,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::getVoidTy(F->getContext())) { + } else if (New->getType()->isVoidTy()) { // Our return value has uses, but they will get removed later on. // Replace by null for now. Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); @@ -805,7 +806,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { while (isa<PHINode>(IP)) ++IP; InsertPt = IP; } - + // We used to return a struct. Instead of doing smart stuff with all the // uses of this struct, we will just rebuild it using // extract/insertvalue chaining and let instcombine clean that up. @@ -929,11 +930,11 @@ bool DAE::runOnModule(Module &M) { DEBUG(dbgs() << "DAE - Determining liveness\n"); for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) SurveyFunction(*I); - + // Now, remove all dead arguments and return values from each function in - // turn + // turn. for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { - // Increment now, because the function will probably get removed (ie + // Increment now, because the function will probably get removed (ie. // replaced by a new one). Function *F = I++; Changed |= RemoveDeadStuffFromFunction(F); diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp index d8e97a26ada83..ddff5ef8b36c8 100644 --- a/lib/Transforms/IPO/GlobalOpt.cpp +++ b/lib/Transforms/IPO/GlobalOpt.cpp @@ -119,7 +119,7 @@ struct GlobalStatus { /// null/false. When the first accessing function is noticed, it is recorded. /// When a second different accessing function is noticed, /// HasMultipleAccessingFunctions is set to true. - Function *AccessingFunction; + const Function *AccessingFunction; bool HasMultipleAccessingFunctions; /// HasNonInstructionUser - Set to true if this global has a user that is not @@ -140,11 +140,11 @@ struct GlobalStatus { // by constants itself. Note that constants cannot be cyclic, so this test is // pretty easy to implement recursively. // -static bool SafeToDestroyConstant(Constant *C) { +static bool SafeToDestroyConstant(const Constant *C) { if (isa<GlobalValue>(C)) return false; - for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI) - if (Constant *CU = dyn_cast<Constant>(*UI)) { + for (Value::const_use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI) + if (const Constant *CU = dyn_cast<Constant>(*UI)) { if (!SafeToDestroyConstant(CU)) return false; } else return false; @@ -156,26 +156,26 @@ static bool SafeToDestroyConstant(Constant *C) { /// structure. If the global has its address taken, return true to indicate we /// can't do anything with it. /// -static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, - SmallPtrSet<PHINode*, 16> &PHIUsers) { - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) - if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { +static bool AnalyzeGlobal(const Value *V, GlobalStatus &GS, + SmallPtrSet<const PHINode*, 16> &PHIUsers) { + for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) + if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { GS.HasNonInstructionUser = true; if (AnalyzeGlobal(CE, GS, PHIUsers)) return true; - } else if (Instruction *I = dyn_cast<Instruction>(*UI)) { + } else if (const Instruction *I = dyn_cast<Instruction>(*UI)) { if (!GS.HasMultipleAccessingFunctions) { - Function *F = I->getParent()->getParent(); + const Function *F = I->getParent()->getParent(); if (GS.AccessingFunction == 0) GS.AccessingFunction = F; else if (GS.AccessingFunction != F) GS.HasMultipleAccessingFunctions = true; } - if (LoadInst *LI = dyn_cast<LoadInst>(I)) { + if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { GS.isLoaded = true; if (LI->isVolatile()) return true; // Don't hack on volatile loads. - } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { + } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) { // Don't allow a store OF the address, only stores TO the address. if (SI->getOperand(0) == V) return true; @@ -185,14 +185,13 @@ static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, // value, not an aggregate), keep more specific information about // stores. if (GS.StoredType != GlobalStatus::isStored) { - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){ + if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){ Value *StoredVal = SI->getOperand(0); if (StoredVal == GV->getInitializer()) { if (GS.StoredType < GlobalStatus::isInitializerStored) GS.StoredType = GlobalStatus::isInitializerStored; } else if (isa<LoadInst>(StoredVal) && cast<LoadInst>(StoredVal)->getOperand(0) == GV) { - // G = G if (GS.StoredType < GlobalStatus::isInitializerStored) GS.StoredType = GlobalStatus::isInitializerStored; } else if (GS.StoredType < GlobalStatus::isStoredOnce) { @@ -212,7 +211,7 @@ static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, if (AnalyzeGlobal(I, GS, PHIUsers)) return true; } else if (isa<SelectInst>(I)) { if (AnalyzeGlobal(I, GS, PHIUsers)) return true; - } else if (PHINode *PN = dyn_cast<PHINode>(I)) { + } else if (const PHINode *PN = dyn_cast<PHINode>(I)) { // PHI nodes we can check just like select or GEP instructions, but we // have to be careful about infinite recursion. if (PHIUsers.insert(PN)) // Not already visited. @@ -230,7 +229,7 @@ static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, } else { return true; // Any other non-load instruction might take address! } - } else if (Constant *C = dyn_cast<Constant>(*UI)) { + } else if (const Constant *C = dyn_cast<Constant>(*UI)) { GS.HasNonInstructionUser = true; // We might have a dead and dangling constant hanging off of here. if (!SafeToDestroyConstant(C)) @@ -1029,23 +1028,23 @@ static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc, /// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi /// of a load) are simple enough to perform heap SRA on. This permits GEP's /// that index through the array and struct field, icmps of null, and PHIs. -static bool LoadUsesSimpleEnoughForHeapSRA(Value *V, - SmallPtrSet<PHINode*, 32> &LoadUsingPHIs, - SmallPtrSet<PHINode*, 32> &LoadUsingPHIsPerLoad) { +static bool LoadUsesSimpleEnoughForHeapSRA(const Value *V, + SmallPtrSet<const PHINode*, 32> &LoadUsingPHIs, + SmallPtrSet<const PHINode*, 32> &LoadUsingPHIsPerLoad) { // We permit two users of the load: setcc comparing against the null // pointer, and a getelementptr of a specific form. - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ - Instruction *User = cast<Instruction>(*UI); + for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ + const Instruction *User = cast<Instruction>(*UI); // Comparison against null is ok. - if (ICmpInst *ICI = dyn_cast<ICmpInst>(User)) { + if (const ICmpInst *ICI = dyn_cast<ICmpInst>(User)) { if (!isa<ConstantPointerNull>(ICI->getOperand(1))) return false; continue; } // getelementptr is also ok, but only a simple form. - if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { + if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { // Must index into the array and into the struct. if (GEPI->getNumOperands() < 3) return false; @@ -1054,7 +1053,7 @@ static bool LoadUsesSimpleEnoughForHeapSRA(Value *V, continue; } - if (PHINode *PN = dyn_cast<PHINode>(User)) { + if (const PHINode *PN = dyn_cast<PHINode>(User)) { if (!LoadUsingPHIsPerLoad.insert(PN)) // This means some phi nodes are dependent on each other. // Avoid infinite looping! @@ -1081,13 +1080,13 @@ 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, +static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV, Instruction *StoredVal) { - SmallPtrSet<PHINode*, 32> LoadUsingPHIs; - SmallPtrSet<PHINode*, 32> LoadUsingPHIsPerLoad; - for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E; + SmallPtrSet<const PHINode*, 32> LoadUsingPHIs; + SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad; + for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E; ++UI) - if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { + if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) { if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs, LoadUsingPHIsPerLoad)) return false; @@ -1099,16 +1098,16 @@ static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV, // that all inputs the to the PHI nodes are in the same equivalence sets. // Check to verify that all operands of the PHIs are either PHIS that can be // transformed, loads from GV, or MI itself. - for (SmallPtrSet<PHINode*, 32>::iterator I = LoadUsingPHIs.begin(), + for (SmallPtrSet<const PHINode*, 32>::const_iterator I = LoadUsingPHIs.begin(), E = LoadUsingPHIs.end(); I != E; ++I) { - PHINode *PN = *I; + const PHINode *PN = *I; for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) { Value *InVal = PN->getIncomingValue(op); // PHI of the stored value itself is ok. if (InVal == StoredVal) continue; - if (PHINode *InPN = dyn_cast<PHINode>(InVal)) { + if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) { // One of the PHIs in our set is (optimistically) ok. if (LoadUsingPHIs.count(InPN)) continue; @@ -1116,7 +1115,7 @@ static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV, } // Load from GV is ok. - if (LoadInst *LI = dyn_cast<LoadInst>(InVal)) + if (const LoadInst *LI = dyn_cast<LoadInst>(InVal)) if (LI->getOperand(0) == GV) continue; @@ -1664,7 +1663,7 @@ static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { /// it if possible. If we make a change, return true. bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, Module::global_iterator &GVI) { - SmallPtrSet<PHINode*, 16> PHIUsers; + SmallPtrSet<const PHINode*, 16> PHIUsers; GlobalStatus GS; GV->removeDeadConstantUsers(); @@ -1715,12 +1714,13 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, GS.AccessingFunction->hasExternalLinkage() && GV->getType()->getAddressSpace() == 0) { DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV); - Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin(); + Instruction& FirstI = const_cast<Instruction&>(*GS.AccessingFunction + ->getEntryBlock().begin()); const Type* ElemTy = GV->getType()->getElementType(); // FIXME: Pass Global's alignment when globals have alignment - AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI); + AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), &FirstI); if (!isa<UndefValue>(GV->getInitializer())) - new StoreInst(GV->getInitializer(), Alloca, FirstI); + new StoreInst(GV->getInitializer(), Alloca, &FirstI); GV->replaceAllUsesWith(Alloca); GV->eraseFromParent(); diff --git a/lib/Transforms/IPO/PruneEH.cpp b/lib/Transforms/IPO/PruneEH.cpp index 3ae771c55f021..161246bc2598a 100644 --- a/lib/Transforms/IPO/PruneEH.cpp +++ b/lib/Transforms/IPO/PruneEH.cpp @@ -168,7 +168,7 @@ bool PruneEH::SimplifyFunction(Function *F) { for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) if (II->doesNotThrow()) { - SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); + SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); // Insert a call instruction before the invoke. CallInst *Call = CallInst::Create(II->getCalledValue(), Args.begin(), Args.end(), "", II); diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp index 65f2e15d2780b..76c815da86288 100644 --- a/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -766,7 +766,7 @@ protected: return SizeCI->getZExtValue() >= GetStringLength(CI->getOperand(SizeArgOp)); if (ConstantInt *Arg = dyn_cast<ConstantInt>(CI->getOperand(SizeArgOp))) - return SizeCI->getZExtValue() <= Arg->getZExtValue(); + return SizeCI->getZExtValue() >= Arg->getZExtValue(); } return false; } diff --git a/lib/Transforms/Scalar/ABCD.cpp b/lib/Transforms/Scalar/ABCD.cpp index ea8e5c3e53f2d..6135992a2f88c 100644 --- a/lib/Transforms/Scalar/ABCD.cpp +++ b/lib/Transforms/Scalar/ABCD.cpp @@ -27,6 +27,7 @@ #define DEBUG_TYPE "abcd" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/OwningPtr.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Constants.h" @@ -77,10 +78,10 @@ class ABCD : public FunctionPass { class Bound { public: Bound(APInt v, bool upper) : value(v), upper_bound(upper) {} - Bound(const Bound *b, int cnst) - : value(b->value - cnst), upper_bound(b->upper_bound) {} - Bound(const Bound *b, const APInt &cnst) - : value(b->value - cnst), upper_bound(b->upper_bound) {} + Bound(const Bound &b, int cnst) + : value(b.value - cnst), upper_bound(b.upper_bound) {} + Bound(const Bound &b, const APInt &cnst) + : value(b.value - cnst), upper_bound(b.upper_bound) {} /// Test if Bound is an upper bound bool isUpperBound() const { return upper_bound; } @@ -89,15 +90,15 @@ class ABCD : public FunctionPass { int32_t getBitWidth() const { return value.getBitWidth(); } /// Creates a Bound incrementing the one received - static Bound *createIncrement(const Bound *b) { - return new Bound(b->isUpperBound() ? b->value+1 : b->value-1, - b->upper_bound); + static Bound createIncrement(const Bound &b) { + return Bound(b.isUpperBound() ? b.value+1 : b.value-1, + b.upper_bound); } /// Creates a Bound decrementing the one received - static Bound *createDecrement(const Bound *b) { - return new Bound(b->isUpperBound() ? b->value-1 : b->value+1, - b->upper_bound); + static Bound createDecrement(const Bound &b) { + return Bound(b.isUpperBound() ? b.value-1 : b.value+1, + b.upper_bound); } /// Test if two bounds are equal @@ -109,36 +110,31 @@ class ABCD : public FunctionPass { } /// Test if val is less than or equal to Bound b - static bool leq(APInt val, const Bound *b) { - if (!b) return false; - return b->isUpperBound() ? val.sle(b->value) : val.sge(b->value); + static bool leq(APInt val, const Bound &b) { + return b.isUpperBound() ? val.sle(b.value) : val.sge(b.value); } /// Test if Bound a is less then or equal to Bound - static bool leq(const Bound *a, const Bound *b) { - if (!a || !b) return false; - - assert(a->isUpperBound() == b->isUpperBound()); - return a->isUpperBound() ? a->value.sle(b->value) : - a->value.sge(b->value); + static bool leq(const Bound &a, const Bound &b) { + assert(a.isUpperBound() == b.isUpperBound()); + return a.isUpperBound() ? a.value.sle(b.value) : + a.value.sge(b.value); } /// Test if Bound a is less then Bound b - static bool lt(const Bound *a, const Bound *b) { - if (!a || !b) return false; - - assert(a->isUpperBound() == b->isUpperBound()); - return a->isUpperBound() ? a->value.slt(b->value) : - a->value.sgt(b->value); + static bool lt(const Bound &a, const Bound &b) { + assert(a.isUpperBound() == b.isUpperBound()); + return a.isUpperBound() ? a.value.slt(b.value) : + a.value.sgt(b.value); } /// Test if Bound b is greater then or equal val - static bool geq(const Bound *b, APInt val) { + static bool geq(const Bound &b, APInt val) { return leq(val, b); } /// Test if Bound a is greater then or equal Bound b - static bool geq(const Bound *a, const Bound *b) { + static bool geq(const Bound &a, const Bound &b) { return leq(b, a); } @@ -152,29 +148,36 @@ class ABCD : public FunctionPass { /// minimum true and minimum reduced results are stored class MemoizedResultChart { public: - MemoizedResultChart() - : max_false(NULL), min_true(NULL), min_reduced(NULL) {} + MemoizedResultChart() {} + MemoizedResultChart(const MemoizedResultChart &other) { + if (other.max_false) + max_false.reset(new Bound(*other.max_false)); + if (other.min_true) + min_true.reset(new Bound(*other.min_true)); + if (other.min_reduced) + min_reduced.reset(new Bound(*other.min_reduced)); + } /// Returns the max false - Bound *getFalse() const { return max_false; } + const Bound *getFalse() const { return max_false.get(); } /// Returns the min true - Bound *getTrue() const { return min_true; } + const Bound *getTrue() const { return min_true.get(); } /// Returns the min reduced - Bound *getReduced() const { return min_reduced; } + const Bound *getReduced() const { return min_reduced.get(); } /// Return the stored result for this bound - ProveResult getResult(const Bound *bound) const; + ProveResult getResult(const Bound &bound) const; /// Stores a false found - void addFalse(Bound *bound); + void addFalse(const Bound &bound); /// Stores a true found - void addTrue(Bound *bound); + void addTrue(const Bound &bound); /// Stores a Reduced found - void addReduced(Bound *bound); + void addReduced(const Bound &bound); /// Clears redundant reduced /// If a min_true is smaller than a min_reduced then the min_reduced @@ -183,13 +186,13 @@ class ABCD : public FunctionPass { void clearRedundantReduced(); void clear() { - delete max_false; - delete min_true; - delete min_reduced; + max_false.reset(); + min_true.reset(); + min_reduced.reset(); } private: - Bound *max_false, *min_true, *min_reduced; + OwningPtr<Bound> max_false, min_true, min_reduced; }; /// This class stores the result found for a node of the graph, @@ -198,27 +201,27 @@ class ABCD : public FunctionPass { public: /// Test if there is true result stored from b to a /// that is less then the bound - bool hasTrue(Value *b, const Bound *bound) const { - Bound *trueBound = map.lookup(b).getTrue(); - return trueBound && Bound::leq(trueBound, bound); + bool hasTrue(Value *b, const Bound &bound) const { + const Bound *trueBound = map.lookup(b).getTrue(); + return trueBound && Bound::leq(*trueBound, bound); } /// Test if there is false result stored from b to a /// that is less then the bound - bool hasFalse(Value *b, const Bound *bound) const { - Bound *falseBound = map.lookup(b).getFalse(); - return falseBound && Bound::leq(falseBound, bound); + bool hasFalse(Value *b, const Bound &bound) const { + const Bound *falseBound = map.lookup(b).getFalse(); + return falseBound && Bound::leq(*falseBound, bound); } /// Test if there is reduced result stored from b to a /// that is less then the bound - bool hasReduced(Value *b, const Bound *bound) const { - Bound *reducedBound = map.lookup(b).getReduced(); - return reducedBound && Bound::leq(reducedBound, bound); + bool hasReduced(Value *b, const Bound &bound) const { + const Bound *reducedBound = map.lookup(b).getReduced(); + return reducedBound && Bound::leq(*reducedBound, bound); } /// Returns the stored bound for b - ProveResult getBoundResult(Value *b, Bound *bound) { + ProveResult getBoundResult(Value *b, const Bound &bound) { return map[b].getResult(bound); } @@ -233,7 +236,7 @@ class ABCD : public FunctionPass { } /// Stores the bound found - void updateBound(Value *b, Bound *bound, const ProveResult res); + void updateBound(Value *b, const Bound &bound, const ProveResult res); private: // Maps a nod in the graph with its results found. @@ -274,7 +277,7 @@ class ABCD : public FunctionPass { bool hasEdge(Value *V, bool upper) const; /// Returns all edges pointed by vertex V - SmallPtrSet<Edge *, 16> getEdges(Value *V) const { + SmallVector<Edge, 16> getEdges(Value *V) const { return graph.lookup(V); } @@ -292,13 +295,7 @@ class ABCD : public FunctionPass { } private: - DenseMap<Value *, SmallPtrSet<Edge *, 16> > graph; - - /// Adds a Node to the graph. - DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator addNode(Value *V) { - SmallPtrSet<Edge *, 16> p; - return graph.insert(std::make_pair(V, p)).first; - } + DenseMap<Value *, SmallVector<Edge, 16> > graph; /// Prints the header of the dot file void printHeader(raw_ostream &OS, Function &F) const; @@ -315,7 +312,7 @@ class ABCD : public FunctionPass { void printVertex(raw_ostream &OS, Value *source) const; /// Prints the edge to the dot file - void printEdge(raw_ostream &OS, Value *source, Edge *edge) const; + void printEdge(raw_ostream &OS, Value *source, const Edge &edge) const; void printName(raw_ostream &OS, Value *info) const; }; @@ -428,15 +425,15 @@ class ABCD : public FunctionPass { bool demandProve(Value *a, Value *b, int c, bool upper_bound); /// Prove that distance between b and a is <= bound - ProveResult prove(Value *a, Value *b, Bound *bound, unsigned level); + ProveResult prove(Value *a, Value *b, const Bound &bound, unsigned level); /// Updates the distance value for a and b - void updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level, + void updateMemDistance(Value *a, Value *b, const Bound &bound, unsigned level, meet_function meet); InequalityGraph inequality_graph; MemoizedResult mem_result; - DenseMap<Value*, Bound*> active; + DenseMap<Value*, const Bound*> active; SmallPtrSet<Value*, 16> created; SmallVector<PHINode *, 16> phis_to_remove; }; @@ -857,7 +854,7 @@ PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) { /// This implementation works on any kind of inequality branch. bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) { int32_t width = cast<IntegerType>(a->getType())->getBitWidth(); - Bound *bound = new Bound(APInt(width, c), upper_bound); + Bound bound(APInt(width, c), upper_bound); mem_result.clear(); active.clear(); @@ -867,7 +864,7 @@ bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) { } /// Prove that distance between b and a is <= bound -ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound, +ABCD::ProveResult ABCD::prove(Value *a, Value *b, const Bound &bound, unsigned level) { // if (C[b-a<=e] == True for some e <= bound // Same or stronger difference was already proven @@ -885,22 +882,22 @@ ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound, return Reduced; // traversal reached the source vertex - if (a == b && Bound::geq(bound, APInt(bound->getBitWidth(), 0, true))) + if (a == b && Bound::geq(bound, APInt(bound.getBitWidth(), 0, true))) return True; // if b has no predecessor then fail - if (!inequality_graph.hasEdge(b, bound->isUpperBound())) + if (!inequality_graph.hasEdge(b, bound.isUpperBound())) return False; // a cycle was encountered if (active.count(b)) { - if (Bound::leq(active.lookup(b), bound)) + if (Bound::leq(*active.lookup(b), bound)) return Reduced; // a "harmless" cycle return False; // an amplifying cycle } - active[b] = bound; + active[b] = &bound; PHINode *PN = dyn_cast<PHINode>(b); // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming @@ -917,23 +914,23 @@ ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound, } /// Updates the distance value for a and b -void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level, - meet_function meet) { +void ABCD::updateMemDistance(Value *a, Value *b, const Bound &bound, + unsigned level, meet_function meet) { ABCD::ProveResult res = (meet == max) ? False : True; - SmallPtrSet<Edge *, 16> Edges = inequality_graph.getEdges(b); - SmallPtrSet<Edge *, 16>::iterator begin = Edges.begin(), end = Edges.end(); + SmallVector<Edge, 16> Edges = inequality_graph.getEdges(b); + SmallVector<Edge, 16>::iterator begin = Edges.begin(), end = Edges.end(); for (; begin != end ; ++begin) { if (((res >= Reduced) && (meet == max)) || ((res == False) && (meet == min))) { break; } - Edge *in = *begin; - if (in->isUpperBound() == bound->isUpperBound()) { - Value *succ = in->getVertex(); - res = meet(res, prove(a, succ, new Bound(bound, in->getValue()), - level+1)); + const Edge &in = *begin; + if (in.isUpperBound() == bound.isUpperBound()) { + Value *succ = in.getVertex(); + res = meet(res, prove(a, succ, Bound(bound, in.getValue()), + level+1)); } } @@ -941,53 +938,53 @@ void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level, } /// Return the stored result for this bound -ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound *bound)const{ - if (max_false && Bound::leq(bound, max_false)) +ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound &bound)const{ + if (max_false && Bound::leq(bound, *max_false)) return False; - if (min_true && Bound::leq(min_true, bound)) + if (min_true && Bound::leq(*min_true, bound)) return True; - if (min_reduced && Bound::leq(min_reduced, bound)) + if (min_reduced && Bound::leq(*min_reduced, bound)) return Reduced; return False; } /// Stores a false found -void ABCD::MemoizedResultChart::addFalse(Bound *bound) { - if (!max_false || Bound::leq(max_false, bound)) - max_false = bound; - - if (Bound::eq(max_false, min_reduced)) - min_reduced = Bound::createIncrement(min_reduced); - if (Bound::eq(max_false, min_true)) - min_true = Bound::createIncrement(min_true); - if (Bound::eq(min_reduced, min_true)) - min_reduced = NULL; +void ABCD::MemoizedResultChart::addFalse(const Bound &bound) { + if (!max_false || Bound::leq(*max_false, bound)) + max_false.reset(new Bound(bound)); + + if (Bound::eq(max_false.get(), min_reduced.get())) + min_reduced.reset(new Bound(Bound::createIncrement(*min_reduced))); + if (Bound::eq(max_false.get(), min_true.get())) + min_true.reset(new Bound(Bound::createIncrement(*min_true))); + if (Bound::eq(min_reduced.get(), min_true.get())) + min_reduced.reset(); clearRedundantReduced(); } /// Stores a true found -void ABCD::MemoizedResultChart::addTrue(Bound *bound) { - if (!min_true || Bound::leq(bound, min_true)) - min_true = bound; - - if (Bound::eq(min_true, min_reduced)) - min_reduced = Bound::createDecrement(min_reduced); - if (Bound::eq(min_true, max_false)) - max_false = Bound::createDecrement(max_false); - if (Bound::eq(max_false, min_reduced)) - min_reduced = NULL; +void ABCD::MemoizedResultChart::addTrue(const Bound &bound) { + if (!min_true || Bound::leq(bound, *min_true)) + min_true.reset(new Bound(bound)); + + if (Bound::eq(min_true.get(), min_reduced.get())) + min_reduced.reset(new Bound(Bound::createDecrement(*min_reduced))); + if (Bound::eq(min_true.get(), max_false.get())) + max_false.reset(new Bound(Bound::createDecrement(*max_false))); + if (Bound::eq(max_false.get(), min_reduced.get())) + min_reduced.reset(); clearRedundantReduced(); } /// Stores a Reduced found -void ABCD::MemoizedResultChart::addReduced(Bound *bound) { - if (!min_reduced || Bound::leq(bound, min_reduced)) - min_reduced = bound; - - if (Bound::eq(min_reduced, min_true)) - min_true = Bound::createIncrement(min_true); - if (Bound::eq(min_reduced, max_false)) - max_false = Bound::createDecrement(max_false); +void ABCD::MemoizedResultChart::addReduced(const Bound &bound) { + if (!min_reduced || Bound::leq(bound, *min_reduced)) + min_reduced.reset(new Bound(bound)); + + if (Bound::eq(min_reduced.get(), min_true.get())) + min_true.reset(new Bound(Bound::createIncrement(*min_true))); + if (Bound::eq(min_reduced.get(), max_false.get())) + max_false.reset(new Bound(Bound::createDecrement(*max_false))); } /// Clears redundant reduced @@ -995,14 +992,14 @@ void ABCD::MemoizedResultChart::addReduced(Bound *bound) { /// is unnecessary and then removed. It also works for min_reduced /// begin smaller than max_false. void ABCD::MemoizedResultChart::clearRedundantReduced() { - if (min_true && min_reduced && Bound::lt(min_true, min_reduced)) - min_reduced = NULL; - if (max_false && min_reduced && Bound::lt(min_reduced, max_false)) - min_reduced = NULL; + if (min_true && min_reduced && Bound::lt(*min_true, *min_reduced)) + min_reduced.reset(); + if (max_false && min_reduced && Bound::lt(*min_reduced, *max_false)) + min_reduced.reset(); } /// Stores the bound found -void ABCD::MemoizedResult::updateBound(Value *b, Bound *bound, +void ABCD::MemoizedResult::updateBound(Value *b, const Bound &bound, const ProveResult res) { if (res == False) { map[b].addFalse(bound); @@ -1020,19 +1017,17 @@ void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from, assert(cast<IntegerType>(V_from->getType())->getBitWidth() == value.getBitWidth()); - DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator from; - from = addNode(V_from); - from->second.insert(new Edge(V_to, value, upper)); + graph[V_from].push_back(Edge(V_to, value, upper)); } /// Test if there is any edge from V in the upper direction bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const { - SmallPtrSet<Edge *, 16> it = graph.lookup(V); + SmallVector<Edge, 16> it = graph.lookup(V); - SmallPtrSet<Edge *, 16>::iterator begin = it.begin(); - SmallPtrSet<Edge *, 16>::iterator end = it.end(); + SmallVector<Edge, 16>::iterator begin = it.begin(); + SmallVector<Edge, 16>::iterator end = it.end(); for (; begin != end; ++begin) { - if ((*begin)->isUpperBound() == upper) { + if (begin->isUpperBound() == upper) { return true; } } @@ -1049,18 +1044,18 @@ void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const { /// Prints the body of the dot file void ABCD::InequalityGraph::printBody(raw_ostream &OS) const { - DenseMap<Value *, SmallPtrSet<Edge *, 16> >::const_iterator begin = + DenseMap<Value *, SmallVector<Edge, 16> >::const_iterator begin = graph.begin(), end = graph.end(); for (; begin != end ; ++begin) { - SmallPtrSet<Edge *, 16>::iterator begin_par = + SmallVector<Edge, 16>::const_iterator begin_par = begin->second.begin(), end_par = begin->second.end(); Value *source = begin->first; printVertex(OS, source); for (; begin_par != end_par ; ++begin_par) { - Edge *edge = *begin_par; + const Edge &edge = *begin_par; printEdge(OS, source, edge); } } @@ -1079,10 +1074,10 @@ void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const { /// Prints the edge to the dot file void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source, - Edge *edge) const { - Value *dest = edge->getVertex(); - APInt value = edge->getValue(); - bool upper = edge->isUpperBound(); + const Edge &edge) const { + Value *dest = edge.getVertex(); + APInt value = edge.getValue(); + bool upper = edge.isUpperBound(); OS << "\""; printName(OS, source); diff --git a/lib/Transforms/Scalar/CodeGenPrepare.cpp b/lib/Transforms/Scalar/CodeGenPrepare.cpp index 50c96304db095..93e9bfbe35ac7 100644 --- a/lib/Transforms/Scalar/CodeGenPrepare.cpp +++ b/lib/Transforms/Scalar/CodeGenPrepare.cpp @@ -174,7 +174,7 @@ bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, // don't mess around with them. BasicBlock::const_iterator BBI = BB->begin(); while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { - for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end(); + for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; ++UI) { const Instruction *User = cast<Instruction>(*UI); if (User->getParent() != DestBB || !isa<PHINode>(User)) @@ -714,8 +714,12 @@ bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, MemoryInst->replaceUsesOfWith(Addr, SunkAddr); - if (Addr->use_empty()) + if (Addr->use_empty()) { RecursivelyDeleteTriviallyDeadInstructions(Addr); + // This address is now available for reassignment, so erase the table entry; + // we don't want to match some completely different instruction. + SunkAddrs[Addr] = 0; + } return true; } diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index fcb802a72ae08..642d59da044f7 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -1004,18 +1004,18 @@ static int AnalyzeLoadFromClobberingWrite(const Type *LoadTy, Value *LoadPtr, // If the load and store are to the exact same address, they should have been // a must alias. AA must have gotten confused. - // FIXME: Study to see if/when this happens. - if (LoadOffset == StoreOffset) { + // FIXME: Study to see if/when this happens. One case is forwarding a memset + // to a load from the base of the memset. #if 0 + if (LoadOffset == StoreOffset) { dbgs() << "STORE/LOAD DEP WITH COMMON POINTER MISSED:\n" << "Base = " << *StoreBase << "\n" << "Store Ptr = " << *WritePtr << "\n" << "Store Offs = " << StoreOffset << "\n" << "Load Ptr = " << *LoadPtr << "\n"; abort(); -#endif - return -1; } +#endif // If the load and store don't overlap at all, the store doesn't provide // anything to the load. In this case, they really don't alias at all, AA @@ -1031,11 +1031,11 @@ static int AnalyzeLoadFromClobberingWrite(const Type *LoadTy, Value *LoadPtr, bool isAAFailure = false; - if (StoreOffset < LoadOffset) { + if (StoreOffset < LoadOffset) isAAFailure = StoreOffset+int64_t(StoreSize) <= LoadOffset; - } else { + else isAAFailure = LoadOffset+int64_t(LoadSize) <= StoreOffset; - } + if (isAAFailure) { #if 0 dbgs() << "STORE LOAD DEP WITH COMMON BASE:\n" diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index eb04d9401fbb6..988a4cb3f2a2d 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -553,22 +553,26 @@ void IndVarSimplify::SinkUnusedInvariants(Loop *L) { // New instructions were inserted at the end of the preheader. if (isa<PHINode>(I)) break; + // Don't move instructions which might have side effects, since the side - // effects need to complete before instructions inside the loop. Also - // don't move instructions which might read memory, since the loop may - // modify memory. Note that it's okay if the instruction might have - // undefined behavior: LoopSimplify guarantees that the preheader - // dominates the exit block. + // effects need to complete before instructions inside the loop. Also don't + // move instructions which might read memory, since the loop may modify + // memory. Note that it's okay if the instruction might have undefined + // behavior: LoopSimplify guarantees that the preheader dominates the exit + // block. if (I->mayHaveSideEffects() || I->mayReadFromMemory()) continue; + // Skip debug info intrinsics. if (isa<DbgInfoIntrinsic>(I)) continue; + // Don't sink static AllocaInsts out of the entry block, which would // turn them into dynamic allocas! if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) if (AI->isStaticAlloca()) continue; + // Determine if there is a use in or before the loop (direct or // otherwise). bool UsedInLoop = false; @@ -585,19 +589,29 @@ void IndVarSimplify::SinkUnusedInvariants(Loop *L) { break; } } + // If there is, the def must remain in the preheader. if (UsedInLoop) continue; + // Otherwise, sink it to the exit block. Instruction *ToMove = I; bool Done = false; - if (I != Preheader->begin()) - --I; - else + + if (I != Preheader->begin()) { + // Skip debug info intrinsics. + do { + --I; + } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); + + if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) + Done = true; + } else { Done = true; + } + ToMove->moveBefore(InsertPt); - if (Done) - break; + if (Done) break; InsertPt = ToMove; } } diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index f920dcab25dfa..625a75d6cca98 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -1899,7 +1899,7 @@ LSRInstance::CollectLoopInvariantFixupsAndFormulae() { const Value *V = U->getValue(); if (const Instruction *Inst = dyn_cast<Instruction>(V)) if (L->contains(Inst)) continue; - for (Value::use_const_iterator UI = V->use_begin(), UE = V->use_end(); + for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; ++UI) { const Instruction *UserInst = dyn_cast<Instruction>(*UI); // Ignore non-instructions. @@ -2827,6 +2827,7 @@ Value *LSRInstance::Expand(const LSRFixup &LF, IP = Tentative; } while (isa<PHINode>(IP)) ++IP; + while (isa<DbgInfoIntrinsic>(IP)) ++IP; // Inform the Rewriter if we have a post-increment use, so that it can // perform an advantageous expansion. @@ -2864,8 +2865,10 @@ Value *LSRInstance::Expand(const LSRFixup &LF, // so that it is dominated by its operand. If the original insert point // was already dominated by the increment, keep it, because there may // be loop-variant operands that need to be respected also. - if (L->contains(LF.UserInst) && !DT.dominates(IVIncInsertPos, IP)) + if (L->contains(LF.UserInst) && !DT.dominates(IVIncInsertPos, IP)) { IP = IVIncInsertPos; + while (isa<DbgInfoIntrinsic>(IP)) ++IP; + } break; } Start = AR->getStart(); diff --git a/lib/Transforms/Scalar/Reg2Mem.cpp b/lib/Transforms/Scalar/Reg2Mem.cpp index 99e12522ce0c7..7a6eec3d46b45 100644 --- a/lib/Transforms/Scalar/Reg2Mem.cpp +++ b/lib/Transforms/Scalar/Reg2Mem.cpp @@ -45,7 +45,7 @@ namespace { bool valueEscapes(const Instruction *Inst) const { const BasicBlock *BB = Inst->getParent(); - for (Value::use_const_iterator UI = Inst->use_begin(),E = Inst->use_end(); + for (Value::const_use_iterator UI = Inst->use_begin(),E = Inst->use_end(); UI != E; ++UI) if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI)) diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 7e37938868d68..546b7b6cc2920 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -1705,28 +1705,31 @@ ModulePass *llvm::createIPSCCPPass() { } -static bool AddressIsTaken(GlobalValue *GV) { +static bool AddressIsTaken(const GlobalValue *GV) { // Delete any dead constantexpr klingons. GV->removeDeadConstantUsers(); - for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); - UI != E; ++UI) - if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { + for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); + UI != E; ++UI) { + const User *U = *UI; + if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { if (SI->getOperand(0) == GV || SI->isVolatile()) return true; // Storing addr of GV. - } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) { + } else if (isa<InvokeInst>(U) || isa<CallInst>(U)) { // Make sure we are calling the function, not passing the address. - if (UI.getOperandNo() != 0) + ImmutableCallSite CS(cast<Instruction>(U)); + if (!CS.isCallee(UI)) return true; - } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { + } else if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { if (LI->isVolatile()) return true; - } else if (isa<BlockAddress>(*UI)) { + } else if (isa<BlockAddress>(U)) { // blockaddress doesn't take the address of the function, it takes addr // of label. } else { return true; } + } return false; } diff --git a/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/lib/Transforms/Scalar/SimplifyCFGPass.cpp index 738c5e8d13d1d..b621e8d8aa6f6 100644 --- a/lib/Transforms/Scalar/SimplifyCFGPass.cpp +++ b/lib/Transforms/Scalar/SimplifyCFGPass.cpp @@ -79,7 +79,7 @@ static void ChangeToUnreachable(Instruction *I) { /// ChangeToCall - Convert the specified invoke into a normal call. static void ChangeToCall(InvokeInst *II) { BasicBlock *BB = II->getParent(); - SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); + SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args.begin(), Args.end(), "", II); NewCall->takeName(II); diff --git a/lib/Transforms/Scalar/SimplifyLibCalls.cpp b/lib/Transforms/Scalar/SimplifyLibCalls.cpp index 22f3628cf7c06..5941ea6571b76 100644 --- a/lib/Transforms/Scalar/SimplifyLibCalls.cpp +++ b/lib/Transforms/Scalar/SimplifyLibCalls.cpp @@ -350,10 +350,16 @@ struct StrNCmpOpt : public LibCallOptimization { // 'strcpy' Optimizations struct StrCpyOpt : public LibCallOptimization { + bool OptChkCall; // True if it's optimizing a __strcpy_chk libcall. + + StrCpyOpt(bool c) : OptChkCall(c) {} + virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { // Verify the "strcpy" function prototype. + unsigned NumParams = OptChkCall ? 3 : 2; const FunctionType *FT = Callee->getFunctionType(); - if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) || + if (FT->getNumParams() != NumParams || + FT->getReturnType() != FT->getParamType(0) || FT->getParamType(0) != FT->getParamType(1) || FT->getParamType(0) != Type::getInt8PtrTy(*Context)) return 0; @@ -371,8 +377,13 @@ struct StrCpyOpt : public LibCallOptimization { // We have enough information to now generate the memcpy call to do the // concatenation for us. Make a memcpy to copy the nul byte with align = 1. - EmitMemCpy(Dst, Src, - ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B, TD); + if (OptChkCall) + EmitMemCpyChk(Dst, Src, + ConstantInt::get(TD->getIntPtrType(*Context), Len), + CI->getOperand(3), B, TD); + else + EmitMemCpy(Dst, Src, + ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B, TD); return Dst; } }; @@ -1162,7 +1173,8 @@ namespace { StringMap<LibCallOptimization*> Optimizations; // String and Memory LibCall Optimizations StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp; - StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrNCpyOpt StrNCpy; StrLenOpt StrLen; + StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrCpyOpt StrCpyChk; + StrNCpyOpt StrNCpy; StrLenOpt StrLen; StrToOpt StrTo; StrStrOpt StrStr; MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet; // Math Library Optimizations @@ -1177,8 +1189,7 @@ namespace { bool Modified; // This is only used by doInitialization. public: static char ID; // Pass identification - SimplifyLibCalls() : FunctionPass(&ID) {} - + SimplifyLibCalls() : FunctionPass(&ID), StrCpy(false), StrCpyChk(true) {} void InitOptimizations(); bool runOnFunction(Function &F); @@ -1228,6 +1239,9 @@ void SimplifyLibCalls::InitOptimizations() { Optimizations["memmove"] = &MemMove; Optimizations["memset"] = &MemSet; + // _chk variants of String and Memory LibCall Optimizations. + Optimizations["__strcpy_chk"] = &StrCpyChk; + // Math Library Optimizations Optimizations["powf"] = &Pow; Optimizations["pow"] = &Pow; diff --git a/lib/Transforms/Utils/AddrModeMatcher.cpp b/lib/Transforms/Utils/AddrModeMatcher.cpp index be6b3834f2739..c70bab5492ef6 100644 --- a/lib/Transforms/Utils/AddrModeMatcher.cpp +++ b/lib/Transforms/Utils/AddrModeMatcher.cpp @@ -440,8 +440,9 @@ static bool FindAllMemoryUses(Instruction *I, } if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { - if (UI.getOperandNo() == 0) return true; // Storing addr, not into addr. - MemoryUses.push_back(std::make_pair(SI, UI.getOperandNo())); + unsigned opNo = UI.getOperandNo(); + if (opNo == 0) return true; // Storing addr, not into addr. + MemoryUses.push_back(std::make_pair(SI, opNo)); continue; } diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index 36573906224d5..8c25ad139b94e 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -94,7 +94,7 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, if (TI->getNumSuccessors() == 1) return false; const BasicBlock *Dest = TI->getSuccessor(SuccNum); - pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); + const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest); // If there is more than one predecessor, this is a critical edge... assert(I != E && "No preds, but we have an edge to the block?"); diff --git a/lib/Transforms/Utils/BuildLibCalls.cpp b/lib/Transforms/Utils/BuildLibCalls.cpp index b44f019760448..0afccf42f6374 100644 --- a/lib/Transforms/Utils/BuildLibCalls.cpp +++ b/lib/Transforms/Utils/BuildLibCalls.cpp @@ -108,7 +108,7 @@ Value *llvm::EmitStrNCpy(Value *Dst, Value *Src, Value *Len, /// EmitMemCpy - Emit a call to the memcpy function to the builder. This always -/// expects that the size has type 'intptr_t' and Dst/Src are pointers. +/// expects that Len has type 'intptr_t' and Dst/Src are pointers. Value *llvm::EmitMemCpy(Value *Dst, Value *Src, Value *Len, unsigned Align, IRBuilder<> &B, const TargetData *TD) { Module *M = B.GetInsertBlock()->getParent()->getParent(); @@ -120,10 +120,34 @@ Value *llvm::EmitMemCpy(Value *Dst, Value *Src, Value *Len, ConstantInt::get(B.getInt32Ty(), Align)); } +/// EmitMemCpyChk - Emit a call to the __memcpy_chk function to the builder. +/// This expects that the Len and ObjSize have type 'intptr_t' and Dst/Src +/// are pointers. +Value *llvm::EmitMemCpyChk(Value *Dst, Value *Src, Value *Len, Value *ObjSize, + IRBuilder<> &B, const TargetData *TD) { + Module *M = B.GetInsertBlock()->getParent()->getParent(); + AttributeWithIndex AWI; + AWI = AttributeWithIndex::get(~0u, Attribute::NoUnwind); + LLVMContext &Context = B.GetInsertBlock()->getContext(); + Value *MemCpy = M->getOrInsertFunction("__memcpy_chk", + AttrListPtr::get(&AWI, 1), + B.getInt8PtrTy(), + B.getInt8PtrTy(), + B.getInt8PtrTy(), + TD->getIntPtrType(Context), + TD->getIntPtrType(Context), NULL); + Dst = CastToCStr(Dst, B); + Src = CastToCStr(Src, B); + CallInst *CI = B.CreateCall4(MemCpy, Dst, Src, Len, ObjSize); + if (const Function *F = dyn_cast<Function>(MemCpy->stripPointerCasts())) + CI->setCallingConv(F->getCallingConv()); + return CI; +} + /// EmitMemMove - Emit a call to the memmove function to the builder. This /// always expects that the size has type 'intptr_t' and Dst/Src are pointers. Value *llvm::EmitMemMove(Value *Dst, Value *Src, Value *Len, - unsigned Align, IRBuilder<> &B, const TargetData *TD) { + unsigned Align, IRBuilder<> &B, const TargetData *TD) { Module *M = B.GetInsertBlock()->getParent()->getParent(); LLVMContext &Context = B.GetInsertBlock()->getContext(); const Type *Ty = TD->getIntPtrType(Context); diff --git a/lib/Transforms/Utils/LowerInvoke.cpp b/lib/Transforms/Utils/LowerInvoke.cpp index 766c4d99a8f91..bbbcc1adae744 100644 --- a/lib/Transforms/Utils/LowerInvoke.cpp +++ b/lib/Transforms/Utils/LowerInvoke.cpp @@ -226,7 +226,7 @@ bool LowerInvoke::insertCheapEHSupport(Function &F) { bool Changed = false; for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { - std::vector<Value*> CallArgs(II->op_begin()+3, II->op_end()); + std::vector<Value*> CallArgs(II->op_begin(), II->op_end() - 3); // Insert a normal call instruction... CallInst *NewCall = CallInst::Create(II->getCalledValue(), CallArgs.begin(), CallArgs.end(), "",II); @@ -298,7 +298,7 @@ void LowerInvoke::rewriteExpensiveInvoke(InvokeInst *II, unsigned InvokeNo, CatchSwitch->addCase(InvokeNoC, II->getUnwindDest()); // Insert a normal call instruction. - std::vector<Value*> CallArgs(II->op_begin()+3, II->op_end()); + std::vector<Value*> CallArgs(II->op_begin(), II->op_end() - 3); CallInst *NewCall = CallInst::Create(II->getCalledValue(), CallArgs.begin(), CallArgs.end(), "", II); diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index 4f5a70b3b2582..f181f3a0a46fd 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -68,7 +68,7 @@ bool llvm::isAllocaPromotable(const AllocaInst *AI) { // assignments to subsections of the memory unit. // Only allow direct and non-volatile loads and stores... - for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); + for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end(); UI != UE; ++UI) // Loop over all of the uses of the alloca if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) { if (LI->isVolatile()) diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp index a31235a1f5cb3..292332e4f8a60 100644 --- a/lib/Transforms/Utils/SSAUpdater.cpp +++ b/lib/Transforms/Utils/SSAUpdater.cpp @@ -14,31 +14,82 @@ #include "llvm/Transforms/Utils/SSAUpdater.h" #include "llvm/Instructions.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/Support/AlignOf.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; -typedef DenseMap<BasicBlock*, TrackingVH<Value> > AvailableValsTy; -typedef std::vector<std::pair<BasicBlock*, TrackingVH<Value> > > - IncomingPredInfoTy; +/// BBInfo - Per-basic block information used internally by SSAUpdater. +/// The predecessors of each block are cached here since pred_iterator is +/// slow and we need to iterate over the blocks at least a few times. +class SSAUpdater::BBInfo { +public: + Value *AvailableVal; // Value to use in this block. + BasicBlock *DefBB; // Block that defines the available value. + unsigned NumPreds; // Number of predecessor blocks. + BasicBlock **Preds; // Array[NumPreds] of predecessor blocks. + unsigned Counter; // Marker to identify blocks already visited. + PHINode *PHITag; // Marker for existing PHIs that match. + + BBInfo(BasicBlock *BB, Value *V, BumpPtrAllocator *Allocator); +}; +typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy; + +SSAUpdater::BBInfo::BBInfo(BasicBlock *BB, Value *V, + BumpPtrAllocator *Allocator) + : AvailableVal(V), DefBB(0), NumPreds(0), Preds(0), Counter(0), PHITag(0) { + // If this block has a known value, don't bother finding its predecessors. + if (V) { + DefBB = BB; + return; + } + + // We can get our predecessor info by walking the pred_iterator list, but it + // is relatively slow. If we already have PHI nodes in this block, walk one + // of them to get the predecessor list instead. + if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { + NumPreds = SomePhi->getNumIncomingValues(); + Preds = static_cast<BasicBlock**> + (Allocator->Allocate(NumPreds * sizeof(BasicBlock*), + AlignOf<BasicBlock*>::Alignment)); + for (unsigned pi = 0; pi != NumPreds; ++pi) + Preds[pi] = SomePhi->getIncomingBlock(pi); + return; + } + + // Stash the predecessors in a temporary vector until we know how much space + // to allocate for them. + SmallVector<BasicBlock*, 10> TmpPreds; + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + TmpPreds.push_back(*PI); + ++NumPreds; + } + Preds = static_cast<BasicBlock**> + (Allocator->Allocate(NumPreds * sizeof(BasicBlock*), + AlignOf<BasicBlock*>::Alignment)); + memcpy(Preds, TmpPreds.data(), NumPreds * sizeof(BasicBlock*)); +} +typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; static AvailableValsTy &getAvailableVals(void *AV) { return *static_cast<AvailableValsTy*>(AV); } -static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) { - return *static_cast<IncomingPredInfoTy*>(IPI); +static BBMapTy *getBBMap(void *BM) { + return static_cast<BBMapTy*>(BM); } +static BumpPtrAllocator *getAllocator(void *BPA) { + return static_cast<BumpPtrAllocator*>(BPA); +} SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) - : AV(0), PrototypeValue(0), IPI(0), InsertedPHIs(NewPHI) {} + : AV(0), PrototypeValue(0), BM(0), BPA(0), InsertedPHIs(NewPHI) {} SSAUpdater::~SSAUpdater() { delete &getAvailableVals(AV); - delete &getIncomingPredInfo(IPI); } /// Initialize - Reset this object to get ready for a new set of SSA @@ -48,11 +99,6 @@ void SSAUpdater::Initialize(Value *ProtoValue) { AV = new AvailableValsTy(); else getAvailableVals(AV).clear(); - - if (IPI == 0) - IPI = new IncomingPredInfoTy(); - else - getIncomingPredInfo(IPI).clear(); PrototypeValue = ProtoValue; } @@ -73,7 +119,7 @@ void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { /// IsEquivalentPHI - Check if PHI has the same incoming value as specified /// in ValueMapping for each predecessor block. -static bool IsEquivalentPHI(PHINode *PHI, +static bool IsEquivalentPHI(PHINode *PHI, DenseMap<BasicBlock*, Value*> &ValueMapping) { unsigned PHINumValues = PHI->getNumIncomingValues(); if (PHINumValues != ValueMapping.size()) @@ -89,38 +135,12 @@ static bool IsEquivalentPHI(PHINode *PHI, return true; } -/// GetExistingPHI - Check if BB already contains a phi node that is equivalent -/// to the specified mapping from predecessor blocks to incoming values. -static Value *GetExistingPHI(BasicBlock *BB, - DenseMap<BasicBlock*, Value*> &ValueMapping) { - PHINode *SomePHI; - for (BasicBlock::iterator It = BB->begin(); - (SomePHI = dyn_cast<PHINode>(It)); ++It) { - if (IsEquivalentPHI(SomePHI, ValueMapping)) - return SomePHI; - } - return 0; -} - -/// GetExistingPHI - Check if BB already contains an equivalent phi node. -/// The InputIt type must be an iterator over std::pair<BasicBlock*, Value*> -/// objects that specify the mapping from predecessor blocks to incoming values. -template<typename InputIt> -static Value *GetExistingPHI(BasicBlock *BB, const InputIt &I, - const InputIt &E) { - // Avoid create the mapping if BB has no phi nodes at all. - if (!isa<PHINode>(BB->begin())) - return 0; - DenseMap<BasicBlock*, Value*> ValueMapping(I, E); - return GetExistingPHI(BB, ValueMapping); -} - /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is /// live at the end of the specified block. Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { - assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); + assert(BM == 0 && BPA == 0 && "Unexpected Internal State"); Value *Res = GetValueAtEndOfBlockInternal(BB); - assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); + assert(BM == 0 && BPA == 0 && "Unexpected Internal State"); return Res; } @@ -146,7 +166,7 @@ Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { // If there is no definition of the renamed variable in this block, just use // GetValueAtEndOfBlock to do our work. - if (!getAvailableVals(AV).count(BB)) + if (!HasValueForBlock(BB)) return GetValueAtEndOfBlock(BB); // Otherwise, we have the hard case. Get the live-in values for each @@ -193,10 +213,18 @@ Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { if (SingularValue != 0) return SingularValue; - // Otherwise, we do need a PHI. - if (Value *ExistingPHI = GetExistingPHI(BB, PredValues.begin(), - PredValues.end())) - return ExistingPHI; + // Otherwise, we do need a PHI: check to see if we already have one available + // in this block that produces the right value. + if (isa<PHINode>(BB->begin())) { + DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(), + PredValues.end()); + PHINode *SomePHI; + for (BasicBlock::iterator It = BB->begin(); + (SomePHI = dyn_cast<PHINode>(It)); ++It) { + if (IsEquivalentPHI(SomePHI, ValueMapping)) + return SomePHI; + } + } // Ok, we have no way out, insert a new one now. PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(), @@ -226,7 +254,7 @@ Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { /// which use their value in the corresponding predecessor. void SSAUpdater::RewriteUse(Use &U) { Instruction *User = cast<Instruction>(U.getUser()); - + Value *V; if (PHINode *UserPN = dyn_cast<PHINode>(User)) V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); @@ -236,161 +264,264 @@ void SSAUpdater::RewriteUse(Use &U) { U.set(V); } - /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry /// for the specified BB and if so, return it. If not, construct SSA form by -/// walking predecessors inserting PHI nodes as needed until we get to a block -/// where the value is available. -/// +/// first calculating the required placement of PHIs and then inserting new +/// PHIs where needed. Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { AvailableValsTy &AvailableVals = getAvailableVals(AV); + if (Value *V = AvailableVals[BB]) + return V; + + // Pool allocation used internally by GetValueAtEndOfBlock. + BumpPtrAllocator AllocatorObj; + BBMapTy BBMapObj; + BPA = &AllocatorObj; + BM = &BBMapObj; + + BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj); + BBMapObj[BB] = Info; + + bool Changed; + unsigned Counter = 1; + do { + Changed = false; + FindPHIPlacement(BB, Info, Changed, Counter); + ++Counter; + } while (Changed); + + FindAvailableVal(BB, Info, Counter); + + BPA = 0; + BM = 0; + return Info->AvailableVal; +} - // Query AvailableVals by doing an insertion of null. - std::pair<AvailableValsTy::iterator, bool> InsertRes = - AvailableVals.insert(std::make_pair(BB, TrackingVH<Value>())); - - // Handle the case when the insertion fails because we have already seen BB. - if (!InsertRes.second) { - // If the insertion failed, there are two cases. The first case is that the - // value is already available for the specified block. If we get this, just - // return the value. - if (InsertRes.first->second != 0) - return InsertRes.first->second; - - // Otherwise, if the value we find is null, then this is the value is not - // known but it is being computed elsewhere in our recursion. This means - // that we have a cycle. Handle this by inserting a PHI node and returning - // it. When we get back to the first instance of the recursion we will fill - // in the PHI node. - return InsertRes.first->second = - PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(), - &BB->front()); +/// FindPHIPlacement - Recursively visit the predecessors of a block to find +/// the reaching definition for each predecessor and then determine whether +/// a PHI is needed in this block. +void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed, + unsigned Counter) { + AvailableValsTy &AvailableVals = getAvailableVals(AV); + BBMapTy *BBMap = getBBMap(BM); + BumpPtrAllocator *Allocator = getAllocator(BPA); + bool BBNeedsPHI = false; + BasicBlock *SamePredDefBB = 0; + + // If there are no predecessors, then we must have found an unreachable + // block. Treat it as a definition with 'undef'. + if (Info->NumPreds == 0) { + Info->AvailableVal = UndefValue::get(PrototypeValue->getType()); + Info->DefBB = BB; + return; } - // Okay, the value isn't in the map and we just inserted a null in the entry - // to indicate that we're processing the block. Since we have no idea what - // value is in this block, we have to recurse through our predecessors. - // - // While we're walking our predecessors, we keep track of them in a vector, - // then insert a PHI node in the end if we actually need one. We could use a - // smallvector here, but that would take a lot of stack space for every level - // of the recursion, just use IncomingPredInfo as an explicit stack. - IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI); - unsigned FirstPredInfoEntry = IncomingPredInfo.size(); - - // As we're walking the predecessors, keep track of whether they are all - // producing the same value. If so, this value will capture it, if not, it - // will get reset to null. We distinguish the no-predecessor case explicitly - // below. - TrackingVH<Value> ExistingValue; - - // We can get our predecessor info by walking the pred_iterator list, but it - // is relatively slow. If we already have PHI nodes in this block, walk one - // of them to get the predecessor list instead. - if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { - for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { - BasicBlock *PredBB = SomePhi->getIncomingBlock(i); - Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); - IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); - - // Set ExistingValue to singular value from all predecessors so far. - if (i == 0) - ExistingValue = PredVal; - else if (PredVal != ExistingValue) - ExistingValue = 0; + Info->Counter = Counter; + for (unsigned pi = 0; pi != Info->NumPreds; ++pi) { + BasicBlock *Pred = Info->Preds[pi]; + BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred); + if (!BBMapBucket.second) { + Value *PredVal = AvailableVals.lookup(Pred); + BBMapBucket.second = new (*Allocator) BBInfo(Pred, PredVal, Allocator); } - } else { - bool isFirstPred = true; - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { - BasicBlock *PredBB = *PI; - Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); - IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); - - // Set ExistingValue to singular value from all predecessors so far. - if (isFirstPred) { - ExistingValue = PredVal; - isFirstPred = false; - } else if (PredVal != ExistingValue) - ExistingValue = 0; + BBInfo *PredInfo = BBMapBucket.second; + BasicBlock *DefBB = 0; + if (!PredInfo->AvailableVal) { + if (PredInfo->Counter != Counter) + FindPHIPlacement(Pred, PredInfo, Changed, Counter); + + // Ignore back edges where the value is not yet known. + if (!PredInfo->DefBB) + continue; } + DefBB = PredInfo->DefBB; + + if (!SamePredDefBB) + SamePredDefBB = DefBB; + else if (DefBB != SamePredDefBB) + BBNeedsPHI = true; } - // If there are no predecessors, then we must have found an unreachable block - // just return 'undef'. Since there are no predecessors, InsertRes must not - // be invalidated. - if (IncomingPredInfo.size() == FirstPredInfoEntry) - return InsertRes.first->second = UndefValue::get(PrototypeValue->getType()); - - /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If - /// this block is involved in a loop, a no-entry PHI node will have been - /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted - /// above. - TrackingVH<Value> &InsertedVal = AvailableVals[BB]; - - // If the predecessor values are not all the same, then check to see if there - // is an existing PHI that can be used. - if (!ExistingValue) - ExistingValue = GetExistingPHI(BB, - IncomingPredInfo.begin()+FirstPredInfoEntry, - IncomingPredInfo.end()); - - // If there is an existing value we can use, then we don't need to insert a - // PHI. This is the simple and common case. - if (ExistingValue) { - // If a PHI node got inserted, replace it with the existing value and delete - // it. - if (InsertedVal) { - PHINode *OldVal = cast<PHINode>(InsertedVal); - // Be careful about dead loops. These RAUW's also update InsertedVal. - if (InsertedVal != ExistingValue) - OldVal->replaceAllUsesWith(ExistingValue); - else - OldVal->replaceAllUsesWith(UndefValue::get(InsertedVal->getType())); - OldVal->eraseFromParent(); - } else { - InsertedVal = ExistingValue; - } + BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB); + if (Info->DefBB != NewDefBB) { + Changed = true; + Info->DefBB = NewDefBB; + } +} - // Either path through the 'if' should have set InsertedVal -> ExistingVal. - assert((InsertedVal == ExistingValue || isa<UndefValue>(InsertedVal)) && - "RAUW didn't change InsertedVal to be ExistingValue"); +/// FindAvailableVal - If this block requires a PHI, first check if an existing +/// PHI matches the PHI placement and reaching definitions computed earlier, +/// and if not, create a new PHI. Visit all the block's predecessors to +/// calculate the available value for each one and fill in the incoming values +/// for a new PHI. +void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info, + unsigned Counter) { + if (Info->AvailableVal || Info->Counter == Counter) + return; - // Drop the entries we added in IncomingPredInfo to restore the stack. - IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, - IncomingPredInfo.end()); - return ExistingValue; + AvailableValsTy &AvailableVals = getAvailableVals(AV); + BBMapTy *BBMap = getBBMap(BM); + + // Check if there needs to be a PHI in BB. + PHINode *NewPHI = 0; + if (Info->DefBB == BB) { + // Look for an existing PHI. + FindExistingPHI(BB); + if (!Info->AvailableVal) { + NewPHI = PHINode::Create(PrototypeValue->getType(), + PrototypeValue->getName(), &BB->front()); + NewPHI->reserveOperandSpace(Info->NumPreds); + Info->AvailableVal = NewPHI; + AvailableVals[BB] = NewPHI; + } } - // Otherwise, we do need a PHI: insert one now if we don't already have one. - if (InsertedVal == 0) - InsertedVal = PHINode::Create(PrototypeValue->getType(), - PrototypeValue->getName(), &BB->front()); + // Iterate through the block's predecessors. + Info->Counter = Counter; + for (unsigned pi = 0; pi != Info->NumPreds; ++pi) { + BasicBlock *Pred = Info->Preds[pi]; + BBInfo *PredInfo = (*BBMap)[Pred]; + FindAvailableVal(Pred, PredInfo, Counter); + if (NewPHI) { + // Skip to the nearest preceding definition. + if (PredInfo->DefBB != Pred) + PredInfo = (*BBMap)[PredInfo->DefBB]; + NewPHI->addIncoming(PredInfo->AvailableVal, Pred); + } else if (!Info->AvailableVal) + Info->AvailableVal = PredInfo->AvailableVal; + } - PHINode *InsertedPHI = cast<PHINode>(InsertedVal); - InsertedPHI->reserveOperandSpace(IncomingPredInfo.size()-FirstPredInfoEntry); + if (NewPHI) { + DEBUG(dbgs() << " Inserted PHI: " << *NewPHI << "\n"); - // Fill in all the predecessors of the PHI. - for (IncomingPredInfoTy::iterator I = - IncomingPredInfo.begin()+FirstPredInfoEntry, - E = IncomingPredInfo.end(); I != E; ++I) - InsertedPHI->addIncoming(I->second, I->first); + // If the client wants to know about all new instructions, tell it. + if (InsertedPHIs) InsertedPHIs->push_back(NewPHI); + } +} - // Drop the entries we added in IncomingPredInfo to restore the stack. - IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, - IncomingPredInfo.end()); +/// FindExistingPHI - Look through the PHI nodes in a block to see if any of +/// them match what is needed. +void SSAUpdater::FindExistingPHI(BasicBlock *BB) { + PHINode *SomePHI; + for (BasicBlock::iterator It = BB->begin(); + (SomePHI = dyn_cast<PHINode>(It)); ++It) { + if (CheckIfPHIMatches(SomePHI)) { + RecordMatchingPHI(SomePHI); + break; + } + ClearPHITags(SomePHI); + } +} - // See if the PHI node can be merged to a single value. This can happen in - // loop cases when we get a PHI of itself and one other value. - if (Value *ConstVal = InsertedPHI->hasConstantValue()) { - InsertedPHI->replaceAllUsesWith(ConstVal); - InsertedPHI->eraseFromParent(); - InsertedVal = ConstVal; - } else { - DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); +/// CheckIfPHIMatches - Check if a PHI node matches the placement and values +/// in the BBMap. +bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) { + BBMapTy *BBMap = getBBMap(BM); + SmallVector<PHINode*, 20> WorkList; + WorkList.push_back(PHI); + + // Mark that the block containing this PHI has been visited. + (*BBMap)[PHI->getParent()]->PHITag = PHI; + + while (!WorkList.empty()) { + PHI = WorkList.pop_back_val(); + + // Iterate through the PHI's incoming values. + for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { + Value *IncomingVal = PHI->getIncomingValue(i); + BasicBlock *Pred = PHI->getIncomingBlock(i); + BBInfo *PredInfo = (*BBMap)[Pred]; + // Skip to the nearest preceding definition. + if (PredInfo->DefBB != Pred) { + Pred = PredInfo->DefBB; + PredInfo = (*BBMap)[Pred]; + } + + // Check if it matches the expected value. + if (PredInfo->AvailableVal) { + if (IncomingVal == PredInfo->AvailableVal) + continue; + return false; + } + + // Check if the value is a PHI in the correct block. + PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal); + if (!IncomingPHIVal || IncomingPHIVal->getParent() != Pred) + return false; + + // If this block has already been visited, check if this PHI matches. + if (PredInfo->PHITag) { + if (IncomingPHIVal == PredInfo->PHITag) + continue; + return false; + } + PredInfo->PHITag = IncomingPHIVal; + + WorkList.push_back(IncomingPHIVal); + } + } + return true; +} - // If the client wants to know about all new instructions, tell it. - if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); +/// RecordMatchingPHI - For a PHI node that matches, record it and its input +/// PHIs in both the BBMap and the AvailableVals mapping. +void SSAUpdater::RecordMatchingPHI(PHINode *PHI) { + BBMapTy *BBMap = getBBMap(BM); + AvailableValsTy &AvailableVals = getAvailableVals(AV); + SmallVector<PHINode*, 20> WorkList; + WorkList.push_back(PHI); + + // Record this PHI. + BasicBlock *BB = PHI->getParent(); + AvailableVals[BB] = PHI; + (*BBMap)[BB]->AvailableVal = PHI; + + while (!WorkList.empty()) { + PHI = WorkList.pop_back_val(); + + // Iterate through the PHI's incoming values. + for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { + PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i)); + if (!IncomingPHIVal) continue; + BB = IncomingPHIVal->getParent(); + BBInfo *Info = (*BBMap)[BB]; + if (!Info || Info->AvailableVal) + continue; + + // Record the PHI and add it to the worklist. + AvailableVals[BB] = IncomingPHIVal; + Info->AvailableVal = IncomingPHIVal; + WorkList.push_back(IncomingPHIVal); + } } +} - return InsertedVal; +/// ClearPHITags - When one of the existing PHI nodes fails to match, clear +/// the PHITag values that were stored in the BBMap when checking to see if +/// it matched. +void SSAUpdater::ClearPHITags(PHINode *PHI) { + BBMapTy *BBMap = getBBMap(BM); + SmallVector<PHINode*, 20> WorkList; + WorkList.push_back(PHI); + + // Clear the tag for this PHI. + (*BBMap)[PHI->getParent()]->PHITag = 0; + + while (!WorkList.empty()) { + PHI = WorkList.pop_back_val(); + + // Iterate through the PHI's incoming values. + for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { + PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i)); + if (!IncomingPHIVal) continue; + BasicBlock *BB = IncomingPHIVal->getParent(); + BBInfo *Info = (*BBMap)[BB]; + if (!Info || Info->AvailableVal || !Info->PHITag) + continue; + + // Clear the tag and add the PHI to the worklist. + Info->PHITag = 0; + WorkList.push_back(IncomingPHIVal); + } + } } diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 2ce5bdcd61d43..9f2209dfcfc06 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -224,7 +224,7 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { if (!AggressiveInsts) return false; // Okay, it looks like the instruction IS in the "condition". Check to - // see if its a cheap instruction to unconditionally compute, and if it + // see if it's a cheap instruction to unconditionally compute, and if it // only uses stuff defined outside of the condition. If so, hoist it out. if (!I->isSafeToSpeculativelyExecute()) return false; @@ -1768,7 +1768,7 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { Pred->getInstList().remove(II); // Take out of symbol table // Insert the call now. - SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end()); + SmallVector<Value*,8> Args(II->op_begin(), II->op_end()-3); CallInst *CI = CallInst::Create(II->getCalledValue(), Args.begin(), Args.end(), II->getName(), BI); @@ -1970,13 +1970,13 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { II->removeFromParent(); // Take out of symbol table // Insert the call now... - SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); + SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3); CallInst *CI = CallInst::Create(II->getCalledValue(), Args.begin(), Args.end(), II->getName(), BI); CI->setCallingConv(II->getCallingConv()); CI->setAttributes(II->getAttributes()); - // If the invoke produced a value, the Call does now instead. + // If the invoke produced a value, the call does now instead. II->replaceAllUsesWith(CI); delete II; Changed = true; |