diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis')
24 files changed, 1020 insertions, 438 deletions
diff --git a/contrib/llvm/lib/Analysis/AliasAnalysis.cpp b/contrib/llvm/lib/Analysis/AliasAnalysis.cpp index 371dcaf..503fbbd 100644 --- a/contrib/llvm/lib/Analysis/AliasAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/AliasAnalysis.cpp @@ -233,10 +233,12 @@ bool llvm::isNoAliasCall(const Value *V) { /// NoAlias returns /// bool llvm::isIdentifiedObject(const Value *V) { - if (isa<AllocaInst>(V) || isNoAliasCall(V)) + if (isa<AllocaInst>(V)) return true; if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) return true; + if (isNoAliasCall(V)) + return true; if (const Argument *A = dyn_cast<Argument>(V)) return A->hasNoAliasAttr() || A->hasByValAttr(); return false; diff --git a/contrib/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp b/contrib/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp index bfa3ff1..37ee9fc 100644 --- a/contrib/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp +++ b/contrib/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp @@ -25,7 +25,6 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Assembly/Writer.h" -#include "llvm/Target/TargetData.h" #include "llvm/Support/Debug.h" #include "llvm/Support/InstIterator.h" #include "llvm/Support/CommandLine.h" diff --git a/contrib/llvm/lib/Analysis/AliasDebugger.cpp b/contrib/llvm/lib/Analysis/AliasDebugger.cpp index 88c2875..bc2d9c55 100644 --- a/contrib/llvm/lib/Analysis/AliasDebugger.cpp +++ b/contrib/llvm/lib/Analysis/AliasDebugger.cpp @@ -45,8 +45,12 @@ namespace { InitializeAliasAnalysis(this); // set up super class for(Module::global_iterator I = M.global_begin(), - E = M.global_end(); I != E; ++I) + E = M.global_end(); I != E; ++I) { Vals.insert(&*I); + for (User::const_op_iterator OI = I->op_begin(), + OE = I->op_end(); OI != OE; ++OI) + Vals.insert(*OI); + } for(Module::iterator I = M.begin(), E = M.end(); I != E; ++I){ @@ -58,8 +62,12 @@ namespace { for (Function::const_iterator FI = I->begin(), FE = I->end(); FI != FE; ++FI) for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end(); - BI != BE; ++BI) + BI != BE; ++BI) { Vals.insert(&*BI); + for (User::const_op_iterator OI = BI->op_begin(), + OE = BI->op_end(); OI != OE; ++OI) + Vals.insert(*OI); + } } } diff --git a/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp index cfe7a1c..4f53a6d 100644 --- a/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -78,6 +78,20 @@ static bool isNonEscapingLocalObject(const Value *V) { return false; } +/// isEscapeSource - Return true if the pointer is one which would have +/// been considered an escape by isNonEscapingLocalObject. +static bool isEscapeSource(const Value *V) { + if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) + return true; + + // The load case works because isNonEscapingLocalObject considers all + // stores to be escapes (it passes true for the StoreCaptures argument + // to PointerMayBeCaptured). + if (isa<LoadInst>(V)) + return true; + + return false; +} /// isObjectSmallerThan - Return true if we can prove that the object specified /// by V is smaller than Size. @@ -94,7 +108,7 @@ static bool isObjectSmallerThan(const Value *V, unsigned Size, } else if (const CallInst* CI = extractMallocCall(V)) { if (!isArrayMalloc(V, &TD)) // The size is the argument to the malloc call. - if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getOperand(1))) + if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getArgOperand(0))) return (C->getZExtValue() < Size); return false; } else if (const Argument *A = dyn_cast<Argument>(V)) { @@ -177,9 +191,29 @@ static RegisterAnalysisGroup<AliasAnalysis> V(U); ImmutablePass *llvm::createNoAAPass() { return new NoAA(); } //===----------------------------------------------------------------------===// -// BasicAA Pass +// BasicAliasAnalysis Pass //===----------------------------------------------------------------------===// +#ifndef NDEBUG +static const Function *getParent(const Value *V) { + if (const Instruction *inst = dyn_cast<Instruction>(V)) + return inst->getParent()->getParent(); + + if (const Argument *arg = dyn_cast<Argument>(V)) + return arg->getParent(); + + return NULL; +} + +static bool notDifferentParent(const Value *O1, const Value *O2) { + + const Function *F1 = getParent(O1); + const Function *F2 = getParent(O2); + + return !F1 || !F2 || F1 == F2; +} +#endif + namespace { /// BasicAliasAnalysis - This is the default alias analysis implementation. /// Because it doesn't chain to a previous alias analysis (like -no-aa), it @@ -187,11 +221,14 @@ namespace { struct BasicAliasAnalysis : public NoAA { static char ID; // Class identification, replacement for typeinfo BasicAliasAnalysis() : NoAA(&ID) {} + AliasResult alias(const Value *V1, unsigned V1Size, const Value *V2, unsigned V2Size) { - assert(VisitedPHIs.empty() && "VisitedPHIs must be cleared after use!"); + assert(Visited.empty() && "Visited must be cleared after use!"); + assert(notDifferentParent(V1, V2) && + "BasicAliasAnalysis doesn't support interprocedural queries."); AliasResult Alias = aliasCheck(V1, V1Size, V2, V2Size); - VisitedPHIs.clear(); + Visited.clear(); return Alias; } @@ -213,8 +250,8 @@ namespace { } private: - // VisitedPHIs - Track PHI nodes visited by a aliasCheck() call. - SmallPtrSet<const Value*, 16> VisitedPHIs; + // Visited - Track instructions visited by a aliasPHI, aliasSelect(), and aliasGEP(). + SmallPtrSet<const Value*, 16> Visited; // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP // instruction against another. @@ -268,6 +305,9 @@ bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { /// simple "address taken" analysis on local objects. AliasAnalysis::ModRefResult BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { + assert(notDifferentParent(CS.getInstruction(), P) && + "AliasAnalysis query involving multiple functions!"); + const Value *Object = P->getUnderlyingObject(); // If this is a tail call and P points to a stack location, we know that @@ -318,10 +358,10 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { case Intrinsic::memcpy: case Intrinsic::memmove: { unsigned Len = ~0U; - if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3))) + if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) Len = LenCI->getZExtValue(); - Value *Dest = II->getOperand(1); - Value *Src = II->getOperand(2); + Value *Dest = II->getArgOperand(0); + Value *Src = II->getArgOperand(1); if (isNoAlias(Dest, Len, P, Size)) { if (isNoAlias(Src, Len, P, Size)) return NoModRef; @@ -332,9 +372,9 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { case Intrinsic::memset: // Since memset is 'accesses arguments' only, the AliasAnalysis base class // will handle it for the variable length case. - if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3))) { + if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { unsigned Len = LenCI->getZExtValue(); - Value *Dest = II->getOperand(1); + Value *Dest = II->getArgOperand(0); if (isNoAlias(Dest, Len, P, Size)) return NoModRef; } @@ -352,7 +392,7 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { case Intrinsic::atomic_load_umax: case Intrinsic::atomic_load_umin: if (TD) { - Value *Op1 = II->getOperand(1); + Value *Op1 = II->getArgOperand(0); unsigned Op1Size = TD->getTypeStoreSize(Op1->getType()); if (isNoAlias(Op1, Op1Size, P, Size)) return NoModRef; @@ -361,14 +401,14 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { case Intrinsic::lifetime_start: case Intrinsic::lifetime_end: case Intrinsic::invariant_start: { - unsigned PtrSize = cast<ConstantInt>(II->getOperand(1))->getZExtValue(); - if (isNoAlias(II->getOperand(2), PtrSize, P, Size)) + unsigned PtrSize = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); + if (isNoAlias(II->getArgOperand(1), PtrSize, P, Size)) return NoModRef; break; } case Intrinsic::invariant_end: { - unsigned PtrSize = cast<ConstantInt>(II->getOperand(2))->getZExtValue(); - if (isNoAlias(II->getOperand(3), PtrSize, P, Size)) + unsigned PtrSize = cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); + if (isNoAlias(II->getArgOperand(2), PtrSize, P, Size)) return NoModRef; break; } @@ -440,6 +480,13 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, unsigned V1Size, const Value *V2, unsigned V2Size, const Value *UnderlyingV1, const Value *UnderlyingV2) { + // If this GEP has been visited before, we're on a use-def cycle. + // Such cycles are only valid when PHI nodes are involved or in unreachable + // code. The visitPHI function catches cycles containing PHIs, but there + // could still be a cycle without PHIs in unreachable code. + if (!Visited.insert(GEP1)) + return MayAlias; + int64_t GEP1BaseOffset; SmallVector<std::pair<const Value*, int64_t>, 4> GEP1VariableIndices; @@ -550,6 +597,13 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, unsigned V1Size, AliasAnalysis::AliasResult BasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize, const Value *V2, unsigned V2Size) { + // If this select has been visited before, we're on a use-def cycle. + // Such cycles are only valid when PHI nodes are involved or in unreachable + // code. The visitPHI function catches cycles containing PHIs, but there + // could still be a cycle without PHIs in unreachable code. + if (!Visited.insert(SI)) + return MayAlias; + // If the values are Selects with the same condition, we can do a more precise // check: just check for aliases between the values on corresponding arms. if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) @@ -570,11 +624,17 @@ BasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize, // If both arms of the Select node NoAlias or MustAlias V2, then returns // NoAlias / MustAlias. Otherwise, returns MayAlias. AliasResult Alias = - aliasCheck(SI->getTrueValue(), SISize, V2, V2Size); + aliasCheck(V2, V2Size, SI->getTrueValue(), SISize); if (Alias == MayAlias) return MayAlias; + + // If V2 is visited, the recursive case will have been caught in the + // above aliasCheck call, so these subsequent calls to aliasCheck + // don't need to assume that V2 is being visited recursively. + Visited.erase(V2); + AliasResult ThisAlias = - aliasCheck(SI->getFalseValue(), SISize, V2, V2Size); + aliasCheck(V2, V2Size, SI->getFalseValue(), SISize); if (ThisAlias != Alias) return MayAlias; return Alias; @@ -586,7 +646,7 @@ AliasAnalysis::AliasResult BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, const Value *V2, unsigned V2Size) { // The PHI node has already been visited, avoid recursion any further. - if (!VisitedPHIs.insert(PN)) + if (!Visited.insert(PN)) return MayAlias; // If the values are PHIs in the same block, we can do a more precise @@ -636,10 +696,10 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { Value *V = V1Srcs[i]; - // If V2 is a PHI, the recursive case will have been caught in the + // If V2 is visited, the recursive case will have been caught in the // above aliasCheck call, so these subsequent calls to aliasCheck // don't need to assume that V2 is being visited recursively. - VisitedPHIs.erase(V2); + Visited.erase(V2); AliasResult ThisAlias = aliasCheck(V2, V2Size, V, PNSize); if (ThisAlias != Alias || ThisAlias == MayAlias) @@ -693,17 +753,32 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size, (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) return NoAlias; - // Arguments can't alias with local allocations or noalias calls. - if ((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || - (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1)))) + // Arguments can't alias with local allocations or noalias calls + // in the same function. + if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || + (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1))))) return NoAlias; // Most objects can't alias null. - if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) || - (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2))) + if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || + (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) return NoAlias; - } + // If one pointer is the result of a call/invoke or load and the other is a + // non-escaping local object within the same function, then we know the + // object couldn't escape to a point where the call could return it. + // + // Note that if the pointers are in different functions, there are a + // variety of complications. A call with a nocapture argument may still + // temporary store the nocapture argument's value in a temporary memory + // location if that memory location doesn't escape. Or it may pass a + // nocapture value to other functions as long as they don't capture it. + if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) + return NoAlias; + if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) + return NoAlias; + } + // If the size of one access is larger than the entire object on the other // side, then we know such behavior is undefined and can assume no alias. if (TD) @@ -711,22 +786,6 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size, (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, *TD))) return NoAlias; - // If one pointer is the result of a call/invoke or load and the other is a - // non-escaping local object, then we know the object couldn't escape to a - // point where the call could return it. The load case works because - // isNonEscapingLocalObject considers all stores to be escapes (it - // passes true for the StoreCaptures argument to PointerMayBeCaptured). - if (O1 != O2) { - if ((isa<CallInst>(O1) || isa<InvokeInst>(O1) || isa<LoadInst>(O1) || - isa<Argument>(O1)) && - isNonEscapingLocalObject(O2)) - return NoAlias; - if ((isa<CallInst>(O2) || isa<InvokeInst>(O2) || isa<LoadInst>(O2) || - isa<Argument>(O2)) && - isNonEscapingLocalObject(O1)) - return NoAlias; - } - // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the // GEP can't simplify, we don't even look at the PHI cases. if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { diff --git a/contrib/llvm/lib/Analysis/CMakeLists.txt b/contrib/llvm/lib/Analysis/CMakeLists.txt index 5a37ce0..d9b670d 100644 --- a/contrib/llvm/lib/Analysis/CMakeLists.txt +++ b/contrib/llvm/lib/Analysis/CMakeLists.txt @@ -23,6 +23,7 @@ add_llvm_library(LLVMAnalysis LibCallSemantics.cpp Lint.cpp LiveValues.cpp + Loads.cpp LoopDependenceAnalysis.cpp LoopInfo.cpp LoopPass.cpp diff --git a/contrib/llvm/lib/Analysis/ConstantFolding.cpp b/contrib/llvm/lib/Analysis/ConstantFolding.cpp index 37cda02..13d8f4d 100644 --- a/contrib/llvm/lib/Analysis/ConstantFolding.cpp +++ b/contrib/llvm/lib/Analysis/ConstantFolding.cpp @@ -208,7 +208,7 @@ static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV, i != e; ++i, ++GTI) { ConstantInt *CI = dyn_cast<ConstantInt>(*i); if (!CI) return false; // Index isn't a simple constant? - if (CI->getZExtValue() == 0) continue; // Not adding anything. + if (CI->isZero()) continue; // Not adding anything. if (const StructType *ST = dyn_cast<StructType>(*GTI)) { // N = N + Offset @@ -436,8 +436,10 @@ Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, unsigned StrLen = Str.length(); const Type *Ty = cast<PointerType>(CE->getType())->getElementType(); unsigned NumBits = Ty->getPrimitiveSizeInBits(); - // Replace LI with immediate integer store. - if ((NumBits >> 3) == StrLen + 1) { + // Replace load with immediate integer if the result is an integer or fp + // value. + if ((NumBits >> 3) == StrLen + 1 && (NumBits & 7) == 0 && + (isa<IntegerType>(Ty) || Ty->isFloatingPointTy())) { APInt StrVal(NumBits, 0); APInt SingleChar(NumBits, 0); if (TD->isLittleEndian()) { @@ -454,7 +456,11 @@ Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, SingleChar = 0; StrVal = (StrVal << 8) | SingleChar; } - return ConstantInt::get(CE->getContext(), StrVal); + + Constant *Res = ConstantInt::get(CE->getContext(), StrVal); + if (Ty->isFloatingPointTy()) + Res = ConstantExpr::getBitCast(Res, Ty); + return Res; } } @@ -772,9 +778,9 @@ Constant *llvm::ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy, case Instruction::ICmp: case Instruction::FCmp: assert(0 && "Invalid for compares"); case Instruction::Call: - if (Function *F = dyn_cast<Function>(Ops[0])) + if (Function *F = dyn_cast<Function>(Ops[CallInst::ArgOffset ? 0:NumOps-1])) if (canConstantFoldCallTo(F)) - return ConstantFoldCall(F, Ops+1, NumOps-1); + return ConstantFoldCall(F, Ops+CallInst::ArgOffset, NumOps-1); return 0; case Instruction::PtrToInt: // If the input is a inttoptr, eliminate the pair. This requires knowing diff --git a/contrib/llvm/lib/Analysis/DebugInfo.cpp b/contrib/llvm/lib/Analysis/DebugInfo.cpp index a7b6d2b..c8d0d22 100644 --- a/contrib/llvm/lib/Analysis/DebugInfo.cpp +++ b/contrib/llvm/lib/Analysis/DebugInfo.cpp @@ -73,6 +73,15 @@ GlobalVariable *DIDescriptor::getGlobalVariableField(unsigned Elt) const { return 0; } +Function *DIDescriptor::getFunctionField(unsigned Elt) const { + if (DbgNode == 0) + return 0; + + if (Elt < DbgNode->getNumOperands()) + return dyn_cast_or_null<Function>(DbgNode->getOperand(Elt)); + return 0; +} + unsigned DIVariable::getNumAddrElements() const { return DbgNode->getNumOperands()-6; } @@ -397,6 +406,8 @@ bool DIVariable::isInlinedFnArgument(const Function *CurFn) { /// information for the function F. bool DISubprogram::describes(const Function *F) { assert(F && "Invalid function"); + if (F == getFunction()) + return true; StringRef Name = getLinkageName(); if (Name.empty()) Name = getName(); @@ -938,7 +949,8 @@ DISubprogram DIFactory::CreateSubprogram(DIDescriptor Context, unsigned VK, unsigned VIndex, DIType ContainingType, bool isArtificial, - bool isOptimized) { + bool isOptimized, + Function *Fn) { Value *Elts[] = { GetTagConstant(dwarf::DW_TAG_subprogram), @@ -956,9 +968,15 @@ DISubprogram DIFactory::CreateSubprogram(DIDescriptor Context, ConstantInt::get(Type::getInt32Ty(VMContext), VIndex), ContainingType, ConstantInt::get(Type::getInt1Ty(VMContext), isArtificial), - ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized) + ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), + Fn }; - return DISubprogram(MDNode::get(VMContext, &Elts[0], 16)); + MDNode *Node = MDNode::get(VMContext, &Elts[0], 17); + + // Create a named metadata so that we do not lose this mdnode. + NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.sp"); + NMD->addOperand(Node); + return DISubprogram(Node); } /// CreateSubprogramDefinition - Create new subprogram descriptor for the @@ -984,9 +1002,15 @@ DISubprogram DIFactory::CreateSubprogramDefinition(DISubprogram &SPDeclaration) DeclNode->getOperand(12), // VIndex DeclNode->getOperand(13), // Containting Type DeclNode->getOperand(14), // isArtificial - DeclNode->getOperand(15) // isOptimized + DeclNode->getOperand(15), // isOptimized + SPDeclaration.getFunction() }; - return DISubprogram(MDNode::get(VMContext, &Elts[0], 16)); + MDNode *Node =MDNode::get(VMContext, &Elts[0], 16); + + // Create a named metadata so that we do not lose this mdnode. + NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.sp"); + NMD->addOperand(Node); + return DISubprogram(Node); } /// CreateGlobalVariable - Create a new descriptor for the specified global. @@ -1042,8 +1066,18 @@ DIVariable DIFactory::CreateVariable(unsigned Tag, DIDescriptor Context, // The optimizer may remove local variable. If there is an interest // to preserve variable info in such situation then stash it in a // named mdnode. - NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.lv"); - NMD->addOperand(Node); + DISubprogram Fn(getDISubprogram(Context)); + StringRef FName = "fn"; + if (Fn.getFunction()) + FName = Fn.getFunction()->getName(); + char One = '\1'; + if (FName.startswith(StringRef(&One, 1))) + FName = FName.substr(1); + NamedMDNode *FnLocals = M.getNamedMetadata(Twine("llvm.dbg.lv.", FName)); + if (!FnLocals) + FnLocals = NamedMDNode::Create(VMContext, Twine("llvm.dbg.lv.", FName), + NULL, 0, &M); + FnLocals->addOperand(Node); } return DIVariable(Node); } @@ -1110,18 +1144,6 @@ DILocation DIFactory::CreateLocation(unsigned LineNo, unsigned ColumnNo, return DILocation(MDNode::get(VMContext, &Elts[0], 4)); } -/// CreateLocation - Creates a debug info location. -DILocation DIFactory::CreateLocation(unsigned LineNo, unsigned ColumnNo, - DIScope S, MDNode *OrigLoc) { - Value *Elts[] = { - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - ConstantInt::get(Type::getInt32Ty(VMContext), ColumnNo), - S, - OrigLoc - }; - return DILocation(MDNode::get(VMContext, &Elts[0], 4)); -} - //===----------------------------------------------------------------------===// // DIFactory: Routines for inserting code into a function //===----------------------------------------------------------------------===// @@ -1218,17 +1240,19 @@ void DebugInfoFinder::processModule(Module &M) { processLocation(DILocation(IA)); } - NamedMDNode *NMD = M.getNamedMetadata("llvm.dbg.gv"); - if (!NMD) - return; - - for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) { - DIGlobalVariable DIG(cast<MDNode>(NMD->getOperand(i))); - if (addGlobalVariable(DIG)) { - addCompileUnit(DIG.getCompileUnit()); - processType(DIG.getType()); + if (NamedMDNode *NMD = M.getNamedMetadata("llvm.dbg.gv")) { + for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) { + DIGlobalVariable DIG(cast<MDNode>(NMD->getOperand(i))); + if (addGlobalVariable(DIG)) { + addCompileUnit(DIG.getCompileUnit()); + processType(DIG.getType()); + } } } + + if (NamedMDNode *NMD = M.getNamedMetadata("llvm.dbg.sp")) + for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) + processSubprogram(DISubprogram(NMD->getOperand(i))); } /// processLocation - Process DILocation. diff --git a/contrib/llvm/lib/Analysis/DomPrinter.cpp b/contrib/llvm/lib/Analysis/DomPrinter.cpp index a1676e5..d95c376 100644 --- a/contrib/llvm/lib/Analysis/DomPrinter.cpp +++ b/contrib/llvm/lib/Analysis/DomPrinter.cpp @@ -43,10 +43,10 @@ struct DOTGraphTraits<DomTreeNode*> : public DefaultDOTGraphTraits { if (isSimple()) return DOTGraphTraits<const Function*> - ::getSimpleNodeLabel(BB, BB->getParent()); + ::getSimpleNodeLabel(BB, BB->getParent()); else return DOTGraphTraits<const Function*> - ::getCompleteNodeLabel(BB, BB->getParent()); + ::getCompleteNodeLabel(BB, BB->getParent()); } }; diff --git a/contrib/llvm/lib/Analysis/IPA/CallGraph.cpp b/contrib/llvm/lib/Analysis/IPA/CallGraph.cpp index 2bde56d7..65c7c6e 100644 --- a/contrib/llvm/lib/Analysis/IPA/CallGraph.cpp +++ b/contrib/llvm/lib/Analysis/IPA/CallGraph.cpp @@ -126,13 +126,15 @@ private: } // Loop over all of the users of the function, looking for non-call uses. - for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) - if ((!isa<CallInst>(I) && !isa<InvokeInst>(I)) - || !CallSite(cast<Instruction>(I)).isCallee(I)) { + for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ + User *U = *I; + if ((!isa<CallInst>(U) && !isa<InvokeInst>(U)) + || !CallSite(cast<Instruction>(U)).isCallee(I)) { // Not a call, or being used as a parameter rather than as the callee. ExternalCallingNode->addCalledFunction(CallSite(), Node); break; } + } // If this function is not defined in this translation unit, it could call // anything. diff --git a/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp b/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp index b14afa3..f13deea 100644 --- a/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp +++ b/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp @@ -233,33 +233,34 @@ bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V, GlobalValue *OkayStoreDest) { if (!V->getType()->isPointerTy()) return true; - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) - if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { + for (Value::use_iterator UI = V->use_begin(), E=V->use_end(); UI != E; ++UI) { + User *U = *UI; + if (LoadInst *LI = dyn_cast<LoadInst>(U)) { Readers.push_back(LI->getParent()->getParent()); - } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { + } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { if (V == SI->getOperand(1)) { Writers.push_back(SI->getParent()->getParent()); } else if (SI->getOperand(1) != OkayStoreDest) { return true; // Storing the pointer } - } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { + } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { if (AnalyzeUsesOfPointer(GEP, Readers, Writers)) return true; - } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) { + } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { if (AnalyzeUsesOfPointer(BCI, Readers, Writers, OkayStoreDest)) return true; - } else if (isFreeCall(*UI)) { - Writers.push_back(cast<Instruction>(*UI)->getParent()->getParent()); - } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { + } else if (isFreeCall(U)) { + Writers.push_back(cast<Instruction>(U)->getParent()->getParent()); + } else if (CallInst *CI = dyn_cast<CallInst>(U)) { // Make sure that this is just the function being called, not that it is // passing into the function. - for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) - if (CI->getOperand(i) == V) return true; - } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { + for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) + if (CI->getArgOperand(i) == V) return true; + } else if (InvokeInst *II = dyn_cast<InvokeInst>(U)) { // Make sure that this is just the function being called, not that it is // passing into the function. - for (unsigned i = 0, e = II->getNumOperands() - 3; i != e; ++i) - if (II->getOperand(i) == V) return true; - } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { + for (unsigned i = 0, e = II->getNumArgOperands(); i != e; ++i) + if (II->getArgOperand(i) == V) return true; + } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { if (CE->getOpcode() == Instruction::GetElementPtr || CE->getOpcode() == Instruction::BitCast) { if (AnalyzeUsesOfPointer(CE, Readers, Writers)) @@ -267,12 +268,14 @@ bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V, } else { return true; } - } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) { + } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(U)) { if (!isa<ConstantPointerNull>(ICI->getOperand(1))) return true; // Allow comparison against null. } else { return true; } + } + return false; } @@ -291,7 +294,8 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { // Walk the user list of the global. If we find anything other than a direct // load or store, bail out. for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){ - if (LoadInst *LI = dyn_cast<LoadInst>(*I)) { + User *U = *I; + if (LoadInst *LI = dyn_cast<LoadInst>(U)) { // The pointer loaded from the global can only be used in simple ways: // we allow addressing of it and loading storing to it. We do *not* allow // storing the loaded pointer somewhere else or passing to a function. @@ -299,7 +303,7 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { if (AnalyzeUsesOfPointer(LI, ReadersWriters, ReadersWriters)) return false; // Loaded pointer escapes. // TODO: Could try some IP mod/ref of the loaded pointer. - } else if (StoreInst *SI = dyn_cast<StoreInst>(*I)) { + } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { // Storing the global itself. if (SI->getOperand(0) == GV) return false; diff --git a/contrib/llvm/lib/Analysis/InlineCost.cpp b/contrib/llvm/lib/Analysis/InlineCost.cpp index 98dbb69..b1df517 100644 --- a/contrib/llvm/lib/Analysis/InlineCost.cpp +++ b/contrib/llvm/lib/Analysis/InlineCost.cpp @@ -162,14 +162,14 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB) { if (Function *F = CS.getCalledFunction()) { if (F->isDeclaration() && (F->getName() == "setjmp" || F->getName() == "_setjmp")) - NeverInline = true; + callsSetJmp = true; // If this call is to function itself, then the function is recursive. // Inlining it into other functions is a bad idea, because this is // basically just a form of loop peeling, and our metrics aren't useful // for that case. if (F == BB->getParent()) - NeverInline = true; + isRecursive = true; } if (!isa<IntrinsicInst>(II) && !callIsSmall(CS.getCalledFunction())) { @@ -220,7 +220,7 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB) { // jump would jump from the inlined copy of the function into the original // function which is extremely undefined behavior. if (isa<IndirectBrInst>(BB->getTerminator())) - NeverInline = true; + containsIndirectBr = true; // Remember NumInsts for this BB. NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB; @@ -247,7 +247,7 @@ void InlineCostAnalyzer::FunctionInfo::analyzeFunction(Function *F) { // Don't bother calculating argument weights if we are never going to inline // the function anyway. - if (Metrics.NeverInline) + if (NeverInline()) return; // Check out all of the arguments to the function, figuring out how much @@ -258,6 +258,14 @@ void InlineCostAnalyzer::FunctionInfo::analyzeFunction(Function *F) { CountCodeReductionForAlloca(I))); } +/// NeverInline - returns true if the function should never be inlined into +/// any caller +bool InlineCostAnalyzer::FunctionInfo::NeverInline() +{ + return (Metrics.callsSetJmp || Metrics.isRecursive || + Metrics.containsIndirectBr); + +} // getInlineCost - The heuristic used to determine if we should inline the // function call or not. // @@ -315,7 +323,7 @@ InlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, CalleeFI->analyzeFunction(Callee); // If we should never inline this, return a huge cost. - if (CalleeFI->Metrics.NeverInline) + if (CalleeFI->NeverInline()) return InlineCost::getNever(); // FIXME: It would be nice to kill off CalleeFI->NeverInline. Then we @@ -443,10 +451,15 @@ InlineCostAnalyzer::growCachedCostInfo(Function *Caller, Function *Callee) { } // Since CalleeMetrics were already calculated, we know that the CallerMetrics - // reference isn't invalidated: both were in the DenseMap. - CallerMetrics.NeverInline |= CalleeMetrics.NeverInline; + // reference isn't invalidated: both were in the DenseMap. CallerMetrics.usesDynamicAlloca |= CalleeMetrics.usesDynamicAlloca; + // FIXME: If any of these three are true for the callee, the callee was + // not inlined into the caller, so I think they're redundant here. + CallerMetrics.callsSetJmp |= CalleeMetrics.callsSetJmp; + CallerMetrics.isRecursive |= CalleeMetrics.isRecursive; + CallerMetrics.containsIndirectBr |= CalleeMetrics.containsIndirectBr; + CallerMetrics.NumInsts += CalleeMetrics.NumInsts; CallerMetrics.NumBlocks += CalleeMetrics.NumBlocks; CallerMetrics.NumCalls += CalleeMetrics.NumCalls; diff --git a/contrib/llvm/lib/Analysis/InstructionSimplify.cpp b/contrib/llvm/lib/Analysis/InstructionSimplify.cpp index dbefc2d..24cd343 100644 --- a/contrib/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/contrib/llvm/lib/Analysis/InstructionSimplify.cpp @@ -440,27 +440,47 @@ void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, const TargetData *TD) { assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); - // FromHandle - This keeps a weakvh on the from value so that we can know if - // it gets deleted out from under us in a recursive simplification. + // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that + // we can know if it gets deleted out from under us or replaced in a + // recursive simplification. WeakVH FromHandle(From); + WeakVH ToHandle(To); while (!From->use_empty()) { // Update the instruction to use the new value. - Use &U = From->use_begin().getUse(); - Instruction *User = cast<Instruction>(U.getUser()); - U = To; + Use &TheUse = From->use_begin().getUse(); + Instruction *User = cast<Instruction>(TheUse.getUser()); + TheUse = To; + + // Check to see if the instruction can be folded due to the operand + // replacement. For example changing (or X, Y) into (or X, -1) can replace + // the 'or' with -1. + Value *SimplifiedVal; + { + // Sanity check to make sure 'User' doesn't dangle across + // SimplifyInstruction. + AssertingVH<> UserHandle(User); - // See if we can simplify it. - if (Value *V = SimplifyInstruction(User, TD)) { - // Recursively simplify this. - ReplaceAndSimplifyAllUses(User, V, TD); - - // If the recursive simplification ended up revisiting and deleting 'From' - // then we're done. - if (FromHandle == 0) - return; + SimplifiedVal = SimplifyInstruction(User, TD); + if (SimplifiedVal == 0) continue; } + + // Recursively simplify this user to the new value. + ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD); + From = dyn_cast_or_null<Instruction>((Value*)FromHandle); + To = ToHandle; + + assert(ToHandle && "To value deleted by recursive simplification?"); + + // If the recursive simplification ended up revisiting and deleting + // 'From' then we're done. + if (From == 0) + return; } + + // If 'From' has value handles referring to it, do a real RAUW to update them. + From->replaceAllUsesWith(To); + From->eraseFromParent(); } diff --git a/contrib/llvm/lib/Analysis/Lint.cpp b/contrib/llvm/lib/Analysis/Lint.cpp index a031cbc..9f1b30d 100644 --- a/contrib/llvm/lib/Analysis/Lint.cpp +++ b/contrib/llvm/lib/Analysis/Lint.cpp @@ -19,7 +19,8 @@ // // Another limitation is that it assumes all code will be executed. A store // through a null pointer in a basic block which is never reached is harmless, -// but this pass will warn about it anyway. +// but this pass will warn about it anyway. This is the main reason why most +// of these checks live here instead of in the Verifier pass. // // Optimization passes may make conditions that this pass checks for more or // less obvious. If an optimization pass appears to be introducing a warning, @@ -35,7 +36,11 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/Lint.h" +#include "llvm/Analysis/Loads.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Assembly/Writer.h" #include "llvm/Target/TargetData.h" @@ -64,7 +69,8 @@ namespace { void visitFunction(Function &F); void visitCallSite(CallSite CS); - void visitMemoryReference(Instruction &I, Value *Ptr, unsigned Align, + void visitMemoryReference(Instruction &I, Value *Ptr, + unsigned Size, unsigned Align, const Type *Ty, unsigned Flags); void visitCallInst(CallInst &I); @@ -88,9 +94,14 @@ namespace { void visitInsertElementInst(InsertElementInst &I); void visitUnreachableInst(UnreachableInst &I); + Value *findValue(Value *V, bool OffsetOk) const; + Value *findValueImpl(Value *V, bool OffsetOk, + SmallPtrSet<Value *, 4> &Visited) const; + public: Module *Mod; AliasAnalysis *AA; + DominatorTree *DT; TargetData *TD; std::string Messages; @@ -104,6 +115,7 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired<AliasAnalysis>(); + AU.addRequired<DominatorTree>(); } virtual void print(raw_ostream &O, const Module *M) const {} @@ -176,6 +188,7 @@ X("lint", "Statically lint-checks LLVM IR", false, true); bool Lint::runOnFunction(Function &F) { Mod = F.getParent(); AA = &getAnalysis<AliasAnalysis>(); + DT = &getAnalysis<DominatorTree>(); TD = getAnalysisIfAvailable<TargetData>(); visit(F); dbgs() << MessagesStr.str(); @@ -188,15 +201,17 @@ void Lint::visitFunction(Function &F) { // fairly common mistake to neglect to name a function. Assert1(F.hasName() || F.hasLocalLinkage(), "Unusual: Unnamed function with non-local linkage", &F); + + // TODO: Check for irreducible control flow. } void Lint::visitCallSite(CallSite CS) { Instruction &I = *CS.getInstruction(); Value *Callee = CS.getCalledValue(); - visitMemoryReference(I, Callee, 0, 0, MemRef::Callee); + visitMemoryReference(I, Callee, ~0u, 0, 0, MemRef::Callee); - if (Function *F = dyn_cast<Function>(Callee->stripPointerCasts())) { + if (Function *F = dyn_cast<Function>(findValue(Callee, /*OffsetOk=*/false))) { Assert1(CS.getCallingConv() == F->getCallingConv(), "Undefined behavior: Caller and callee calling convention differ", &I); @@ -209,23 +224,53 @@ void Lint::visitCallSite(CallSite CS) { FT->getNumParams() == NumActualArgs, "Undefined behavior: Call argument count mismatches callee " "argument count", &I); - - // TODO: Check argument types (in case the callee was casted) - - // TODO: Check ABI-significant attributes. - // TODO: Check noalias attribute. - - // TODO: Check sret attribute. + Assert1(FT->getReturnType() == I.getType(), + "Undefined behavior: Call return type mismatches " + "callee return type", &I); + + // Check argument types (in case the callee was casted) and attributes. + // TODO: Verify that caller and callee attributes are compatible. + Function::arg_iterator PI = F->arg_begin(), PE = F->arg_end(); + CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); + for (; AI != AE; ++AI) { + Value *Actual = *AI; + if (PI != PE) { + Argument *Formal = PI++; + Assert1(Formal->getType() == Actual->getType(), + "Undefined behavior: Call argument type mismatches " + "callee parameter type", &I); + + // Check that noalias arguments don't alias other arguments. The + // AliasAnalysis API isn't expressive enough for what we really want + // to do. Known partial overlap is not distinguished from the case + // where nothing is known. + if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy()) + for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI) { + Assert1(AI == BI || + AA->alias(*AI, ~0u, *BI, ~0u) != AliasAnalysis::MustAlias, + "Unusual: noalias argument aliases another argument", &I); + } + + // Check that an sret argument points to valid memory. + if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { + const Type *Ty = + cast<PointerType>(Formal->getType())->getElementType(); + visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty), + TD ? TD->getABITypeAlignment(Ty) : 0, + Ty, MemRef::Read | MemRef::Write); + } + } + } } if (CS.isCall() && cast<CallInst>(CS.getInstruction())->isTailCall()) for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) { - Value *Obj = (*AI)->getUnderlyingObject(); - Assert1(!isa<AllocaInst>(Obj) && !isa<VAArgInst>(Obj), + Value *Obj = findValue(*AI, /*OffsetOk=*/true); + Assert1(!isa<AllocaInst>(Obj), "Undefined behavior: Call with \"tail\" keyword references " - "alloca or va_arg", &I); + "alloca", &I); } @@ -237,9 +282,10 @@ void Lint::visitCallSite(CallSite CS) { case Intrinsic::memcpy: { MemCpyInst *MCI = cast<MemCpyInst>(&I); - visitMemoryReference(I, MCI->getSource(), MCI->getAlignment(), 0, + // TODO: If the size is known, use it. + visitMemoryReference(I, MCI->getDest(), ~0u, MCI->getAlignment(), 0, MemRef::Write); - visitMemoryReference(I, MCI->getDest(), MCI->getAlignment(), 0, + visitMemoryReference(I, MCI->getSource(), ~0u, MCI->getAlignment(), 0, MemRef::Read); // Check that the memcpy arguments don't overlap. The AliasAnalysis API @@ -247,7 +293,8 @@ void Lint::visitCallSite(CallSite CS) { // overlap is not distinguished from the case where nothing is known. unsigned Size = 0; if (const ConstantInt *Len = - dyn_cast<ConstantInt>(MCI->getLength()->stripPointerCasts())) + dyn_cast<ConstantInt>(findValue(MCI->getLength(), + /*OffsetOk=*/false))) if (Len->getValue().isIntN(32)) Size = Len->getValue().getZExtValue(); Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != @@ -257,15 +304,17 @@ void Lint::visitCallSite(CallSite CS) { } case Intrinsic::memmove: { MemMoveInst *MMI = cast<MemMoveInst>(&I); - visitMemoryReference(I, MMI->getSource(), MMI->getAlignment(), 0, + // TODO: If the size is known, use it. + visitMemoryReference(I, MMI->getDest(), ~0u, MMI->getAlignment(), 0, MemRef::Write); - visitMemoryReference(I, MMI->getDest(), MMI->getAlignment(), 0, + visitMemoryReference(I, MMI->getSource(), ~0u, MMI->getAlignment(), 0, MemRef::Read); break; } case Intrinsic::memset: { MemSetInst *MSI = cast<MemSetInst>(&I); - visitMemoryReference(I, MSI->getDest(), MSI->getAlignment(), 0, + // TODO: If the size is known, use it. + visitMemoryReference(I, MSI->getDest(), ~0u, MSI->getAlignment(), 0, MemRef::Write); break; } @@ -275,15 +324,15 @@ void Lint::visitCallSite(CallSite CS) { "Undefined behavior: va_start called in a non-varargs function", &I); - visitMemoryReference(I, CS.getArgument(0), 0, 0, + visitMemoryReference(I, CS.getArgument(0), ~0u, 0, 0, MemRef::Read | MemRef::Write); break; case Intrinsic::vacopy: - visitMemoryReference(I, CS.getArgument(0), 0, 0, MemRef::Write); - visitMemoryReference(I, CS.getArgument(1), 0, 0, MemRef::Read); + visitMemoryReference(I, CS.getArgument(0), ~0u, 0, 0, MemRef::Write); + visitMemoryReference(I, CS.getArgument(1), ~0u, 0, 0, MemRef::Read); break; case Intrinsic::vaend: - visitMemoryReference(I, CS.getArgument(0), 0, 0, + visitMemoryReference(I, CS.getArgument(0), ~0u, 0, 0, MemRef::Read | MemRef::Write); break; @@ -291,7 +340,7 @@ void Lint::visitCallSite(CallSite CS) { // Stackrestore doesn't read or write memory, but it sets the // stack pointer, which the compiler may read from or write to // at any time, so check it for both readability and writeability. - visitMemoryReference(I, CS.getArgument(0), 0, 0, + visitMemoryReference(I, CS.getArgument(0), ~0u, 0, 0, MemRef::Read | MemRef::Write); break; } @@ -310,17 +359,35 @@ void Lint::visitReturnInst(ReturnInst &I) { Assert1(!F->doesNotReturn(), "Unusual: Return statement in function with noreturn attribute", &I); + + if (Value *V = I.getReturnValue()) { + Value *Obj = findValue(V, /*OffsetOk=*/true); + Assert1(!isa<AllocaInst>(Obj), + "Unusual: Returning alloca value", &I); + } } -// TODO: Add a length argument and check that the reference is in bounds +// TODO: Check that the reference is in bounds. +// TODO: Check readnone/readonly function attributes. void Lint::visitMemoryReference(Instruction &I, - Value *Ptr, unsigned Align, const Type *Ty, - unsigned Flags) { - Value *UnderlyingObject = Ptr->getUnderlyingObject(); + Value *Ptr, unsigned Size, unsigned Align, + const Type *Ty, unsigned Flags) { + // If no memory is being referenced, it doesn't matter if the pointer + // is valid. + if (Size == 0) + return; + + Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true); Assert1(!isa<ConstantPointerNull>(UnderlyingObject), "Undefined behavior: Null pointer dereference", &I); Assert1(!isa<UndefValue>(UnderlyingObject), "Undefined behavior: Undef pointer dereference", &I); + Assert1(!isa<ConstantInt>(UnderlyingObject) || + !cast<ConstantInt>(UnderlyingObject)->isAllOnesValue(), + "Unusual: All-ones pointer dereference", &I); + Assert1(!isa<ConstantInt>(UnderlyingObject) || + !cast<ConstantInt>(UnderlyingObject)->isOne(), + "Unusual: Address one pointer dereference", &I); if (Flags & MemRef::Write) { if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(UnderlyingObject)) @@ -361,13 +428,16 @@ void Lint::visitMemoryReference(Instruction &I, } void Lint::visitLoadInst(LoadInst &I) { - visitMemoryReference(I, I.getPointerOperand(), I.getAlignment(), I.getType(), - MemRef::Read); + visitMemoryReference(I, I.getPointerOperand(), + AA->getTypeStoreSize(I.getType()), I.getAlignment(), + I.getType(), MemRef::Read); } void Lint::visitStoreInst(StoreInst &I) { - visitMemoryReference(I, I.getPointerOperand(), I.getAlignment(), - I.getOperand(0)->getType(), MemRef::Write); + visitMemoryReference(I, I.getPointerOperand(), + AA->getTypeStoreSize(I.getOperand(0)->getType()), + I.getAlignment(), + I.getOperand(0)->getType(), MemRef::Write); } void Lint::visitXor(BinaryOperator &I) { @@ -384,21 +454,21 @@ void Lint::visitSub(BinaryOperator &I) { void Lint::visitLShr(BinaryOperator &I) { if (ConstantInt *CI = - dyn_cast<ConstantInt>(I.getOperand(1)->stripPointerCasts())) + dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), "Undefined result: Shift count out of range", &I); } void Lint::visitAShr(BinaryOperator &I) { if (ConstantInt *CI = - dyn_cast<ConstantInt>(I.getOperand(1)->stripPointerCasts())) + dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), "Undefined result: Shift count out of range", &I); } void Lint::visitShl(BinaryOperator &I) { if (ConstantInt *CI = - dyn_cast<ConstantInt>(I.getOperand(1)->stripPointerCasts())) + dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), "Undefined result: Shift count out of range", &I); } @@ -439,27 +509,31 @@ void Lint::visitAllocaInst(AllocaInst &I) { // This isn't undefined behavior, it's just an obvious pessimization. Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), "Pessimization: Static alloca outside of entry block", &I); + + // TODO: Check for an unusual size (MSB set?) } void Lint::visitVAArgInst(VAArgInst &I) { - visitMemoryReference(I, I.getOperand(0), 0, 0, + visitMemoryReference(I, I.getOperand(0), ~0u, 0, 0, MemRef::Read | MemRef::Write); } void Lint::visitIndirectBrInst(IndirectBrInst &I) { - visitMemoryReference(I, I.getAddress(), 0, 0, MemRef::Branchee); + visitMemoryReference(I, I.getAddress(), ~0u, 0, 0, MemRef::Branchee); } void Lint::visitExtractElementInst(ExtractElementInst &I) { if (ConstantInt *CI = - dyn_cast<ConstantInt>(I.getIndexOperand()->stripPointerCasts())) + dyn_cast<ConstantInt>(findValue(I.getIndexOperand(), + /*OffsetOk=*/false))) Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), "Undefined result: extractelement index out of range", &I); } void Lint::visitInsertElementInst(InsertElementInst &I) { if (ConstantInt *CI = - dyn_cast<ConstantInt>(I.getOperand(2)->stripPointerCasts())) + dyn_cast<ConstantInt>(findValue(I.getOperand(2), + /*OffsetOk=*/false))) Assert1(CI->getValue().ult(I.getType()->getNumElements()), "Undefined result: insertelement index out of range", &I); } @@ -472,6 +546,91 @@ void Lint::visitUnreachableInst(UnreachableInst &I) { "side effects", &I); } +/// findValue - Look through bitcasts and simple memory reference patterns +/// to identify an equivalent, but more informative, value. If OffsetOk +/// is true, look through getelementptrs with non-zero offsets too. +/// +/// Most analysis passes don't require this logic, because instcombine +/// will simplify most of these kinds of things away. But it's a goal of +/// this Lint pass to be useful even on non-optimized IR. +Value *Lint::findValue(Value *V, bool OffsetOk) const { + SmallPtrSet<Value *, 4> Visited; + return findValueImpl(V, OffsetOk, Visited); +} + +/// findValueImpl - Implementation helper for findValue. +Value *Lint::findValueImpl(Value *V, bool OffsetOk, + SmallPtrSet<Value *, 4> &Visited) const { + // Detect self-referential values. + if (!Visited.insert(V)) + return UndefValue::get(V->getType()); + + // TODO: Look through sext or zext cast, when the result is known to + // be interpreted as signed or unsigned, respectively. + // TODO: Look through eliminable cast pairs. + // TODO: Look through calls with unique return values. + // TODO: Look through vector insert/extract/shuffle. + V = OffsetOk ? V->getUnderlyingObject() : V->stripPointerCasts(); + if (LoadInst *L = dyn_cast<LoadInst>(V)) { + BasicBlock::iterator BBI = L; + BasicBlock *BB = L->getParent(); + SmallPtrSet<BasicBlock *, 4> VisitedBlocks; + for (;;) { + if (!VisitedBlocks.insert(BB)) break; + if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(), + BB, BBI, 6, AA)) + return findValueImpl(U, OffsetOk, Visited); + if (BBI != BB->begin()) break; + BB = BB->getUniquePredecessor(); + if (!BB) break; + BBI = BB->end(); + } + } else if (PHINode *PN = dyn_cast<PHINode>(V)) { + if (Value *W = PN->hasConstantValue(DT)) + return findValueImpl(W, OffsetOk, Visited); + } else if (CastInst *CI = dyn_cast<CastInst>(V)) { + if (CI->isNoopCast(TD ? TD->getIntPtrType(V->getContext()) : + Type::getInt64Ty(V->getContext()))) + return findValueImpl(CI->getOperand(0), OffsetOk, Visited); + } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) { + if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), + Ex->idx_begin(), + Ex->idx_end())) + if (W != V) + return findValueImpl(W, OffsetOk, Visited); + } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { + // Same as above, but for ConstantExpr instead of Instruction. + if (Instruction::isCast(CE->getOpcode())) { + if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), + CE->getOperand(0)->getType(), + CE->getType(), + TD ? TD->getIntPtrType(V->getContext()) : + Type::getInt64Ty(V->getContext()))) + return findValueImpl(CE->getOperand(0), OffsetOk, Visited); + } else if (CE->getOpcode() == Instruction::ExtractValue) { + const SmallVector<unsigned, 4> &Indices = CE->getIndices(); + if (Value *W = FindInsertedValue(CE->getOperand(0), + Indices.begin(), + Indices.end())) + if (W != V) + return findValueImpl(W, OffsetOk, Visited); + } + } + + // As a last resort, try SimplifyInstruction or constant folding. + if (Instruction *Inst = dyn_cast<Instruction>(V)) { + if (Value *W = SimplifyInstruction(Inst, TD)) + if (W != Inst) + return findValueImpl(W, OffsetOk, Visited); + } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { + if (Value *W = ConstantFoldConstantExpression(CE, TD)) + if (W != V) + return findValueImpl(W, OffsetOk, Visited); + } + + return V; +} + //===----------------------------------------------------------------------===// // Implement the public interfaces to this file... //===----------------------------------------------------------------------===// diff --git a/contrib/llvm/lib/Analysis/Loads.cpp b/contrib/llvm/lib/Analysis/Loads.cpp new file mode 100644 index 0000000..2ba1d86 --- /dev/null +++ b/contrib/llvm/lib/Analysis/Loads.cpp @@ -0,0 +1,235 @@ +//===- Loads.cpp - Local load analysis ------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines simple local analyses for load instructions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Target/TargetData.h" +#include "llvm/GlobalAlias.h" +#include "llvm/GlobalVariable.h" +#include "llvm/IntrinsicInst.h" +using namespace llvm; + +/// AreEquivalentAddressValues - Test if A and B will obviously have the same +/// value. This includes recognizing that %t0 and %t1 will have the same +/// value in code like this: +/// %t0 = getelementptr \@a, 0, 3 +/// store i32 0, i32* %t0 +/// %t1 = getelementptr \@a, 0, 3 +/// %t2 = load i32* %t1 +/// +static bool AreEquivalentAddressValues(const Value *A, const Value *B) { + // Test if the values are trivially equivalent. + if (A == B) return true; + + // Test if the values come from identical arithmetic instructions. + // Use isIdenticalToWhenDefined instead of isIdenticalTo because + // this function is only used when one address use dominates the + // other, which means that they'll always either have the same + // value or one of them will have an undefined value. + if (isa<BinaryOperator>(A) || isa<CastInst>(A) || + isa<PHINode>(A) || isa<GetElementPtrInst>(A)) + if (const Instruction *BI = dyn_cast<Instruction>(B)) + if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI)) + return true; + + // Otherwise they may not be equivalent. + return false; +} + +/// getUnderlyingObjectWithOffset - Strip off up to MaxLookup GEPs and +/// bitcasts to get back to the underlying object being addressed, keeping +/// track of the offset in bytes from the GEPs relative to the result. +/// This is closely related to Value::getUnderlyingObject but is located +/// here to avoid making VMCore depend on TargetData. +static Value *getUnderlyingObjectWithOffset(Value *V, const TargetData *TD, + uint64_t &ByteOffset, + unsigned MaxLookup = 6) { + if (!V->getType()->isPointerTy()) + return V; + for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) { + if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { + if (!GEP->hasAllConstantIndices()) + return V; + SmallVector<Value*, 8> Indices(GEP->op_begin() + 1, GEP->op_end()); + ByteOffset += TD->getIndexedOffset(GEP->getPointerOperandType(), + &Indices[0], Indices.size()); + V = GEP->getPointerOperand(); + } else if (Operator::getOpcode(V) == Instruction::BitCast) { + V = cast<Operator>(V)->getOperand(0); + } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { + if (GA->mayBeOverridden()) + return V; + V = GA->getAliasee(); + } else { + return V; + } + assert(V->getType()->isPointerTy() && "Unexpected operand type!"); + } + return V; +} + +/// isSafeToLoadUnconditionally - Return true if we know that executing a load +/// from this value cannot trap. If it is not obviously safe to load from the +/// specified pointer, we do a quick local scan of the basic block containing +/// ScanFrom, to determine if the address is already accessed. +bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom, + unsigned Align, const TargetData *TD) { + uint64_t ByteOffset = 0; + Value *Base = V; + if (TD) + Base = getUnderlyingObjectWithOffset(V, TD, ByteOffset); + + const Type *BaseType = 0; + unsigned BaseAlign = 0; + if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { + // An alloca is safe to load from as load as it is suitably aligned. + BaseType = AI->getAllocatedType(); + BaseAlign = AI->getAlignment(); + } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(Base)) { + // Global variables are safe to load from but their size cannot be + // guaranteed if they are overridden. + if (!isa<GlobalAlias>(GV) && !GV->mayBeOverridden()) { + BaseType = GV->getType()->getElementType(); + BaseAlign = GV->getAlignment(); + } + } + + if (BaseType && BaseType->isSized()) { + if (TD && BaseAlign == 0) + BaseAlign = TD->getPrefTypeAlignment(BaseType); + + if (Align <= BaseAlign) { + if (!TD) + return true; // Loading directly from an alloca or global is OK. + + // Check if the load is within the bounds of the underlying object. + const PointerType *AddrTy = cast<PointerType>(V->getType()); + uint64_t LoadSize = TD->getTypeStoreSize(AddrTy->getElementType()); + if (ByteOffset + LoadSize <= TD->getTypeAllocSize(BaseType) && + (Align == 0 || (ByteOffset % Align) == 0)) + return true; + } + } + + // Otherwise, be a little bit aggressive by scanning the local block where we + // want to check to see if the pointer is already being loaded or stored + // from/to. If so, the previous load or store would have already trapped, + // so there is no harm doing an extra load (also, CSE will later eliminate + // the load entirely). + BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin(); + + while (BBI != E) { + --BBI; + + // If we see a free or a call which may write to memory (i.e. which might do + // a free) the pointer could be marked invalid. + if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && + !isa<DbgInfoIntrinsic>(BBI)) + return false; + + if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { + if (AreEquivalentAddressValues(LI->getOperand(0), V)) return true; + } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { + if (AreEquivalentAddressValues(SI->getOperand(1), V)) return true; + } + } + return false; +} + +/// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at the +/// instruction before ScanFrom) checking to see if we have the value at the +/// memory address *Ptr locally available within a small number of instructions. +/// If the value is available, return it. +/// +/// If not, return the iterator for the last validated instruction that the +/// value would be live through. If we scanned the entire block and didn't find +/// something that invalidates *Ptr or provides it, ScanFrom would be left at +/// begin() and this returns null. ScanFrom could also be left +/// +/// MaxInstsToScan specifies the maximum instructions to scan in the block. If +/// it is set to 0, it will scan the whole block. You can also optionally +/// specify an alias analysis implementation, which makes this more precise. +Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, + BasicBlock::iterator &ScanFrom, + unsigned MaxInstsToScan, + AliasAnalysis *AA) { + if (MaxInstsToScan == 0) MaxInstsToScan = ~0U; + + // If we're using alias analysis to disambiguate get the size of *Ptr. + unsigned AccessSize = 0; + if (AA) { + const Type *AccessTy = cast<PointerType>(Ptr->getType())->getElementType(); + AccessSize = AA->getTypeStoreSize(AccessTy); + } + + while (ScanFrom != ScanBB->begin()) { + // We must ignore debug info directives when counting (otherwise they + // would affect codegen). + Instruction *Inst = --ScanFrom; + if (isa<DbgInfoIntrinsic>(Inst)) + continue; + + // Restore ScanFrom to expected value in case next test succeeds + ScanFrom++; + + // Don't scan huge blocks. + if (MaxInstsToScan-- == 0) return 0; + + --ScanFrom; + // If this is a load of Ptr, the loaded value is available. + if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) + if (AreEquivalentAddressValues(LI->getOperand(0), Ptr)) + return LI; + + if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { + // If this is a store through Ptr, the value is available! + if (AreEquivalentAddressValues(SI->getOperand(1), Ptr)) + return SI->getOperand(0); + + // If Ptr is an alloca and this is a store to a different alloca, ignore + // the store. This is a trivial form of alias analysis that is important + // for reg2mem'd code. + if ((isa<AllocaInst>(Ptr) || isa<GlobalVariable>(Ptr)) && + (isa<AllocaInst>(SI->getOperand(1)) || + isa<GlobalVariable>(SI->getOperand(1)))) + continue; + + // If we have alias analysis and it says the store won't modify the loaded + // value, ignore the store. + if (AA && + (AA->getModRefInfo(SI, Ptr, AccessSize) & AliasAnalysis::Mod) == 0) + continue; + + // Otherwise the store that may or may not alias the pointer, bail out. + ++ScanFrom; + return 0; + } + + // If this is some other instruction that may clobber Ptr, bail out. + if (Inst->mayWriteToMemory()) { + // If alias analysis claims that it really won't modify the load, + // ignore it. + if (AA && + (AA->getModRefInfo(Inst, Ptr, AccessSize) & AliasAnalysis::Mod) == 0) + continue; + + // May modify the pointer, bail out. + ++ScanFrom; + return 0; + } + } + + // Got to the start of the block, we didn't find it, but are done for this + // block. + return 0; +} diff --git a/contrib/llvm/lib/Analysis/LoopInfo.cpp b/contrib/llvm/lib/Analysis/LoopInfo.cpp index 735e31f..818d0a9 100644 --- a/contrib/llvm/lib/Analysis/LoopInfo.cpp +++ b/contrib/llvm/lib/Analysis/LoopInfo.cpp @@ -266,15 +266,16 @@ unsigned Loop::getSmallConstantTripMultiple() const { bool Loop::isLCSSAForm(DominatorTree &DT) const { // Sort the blocks vector so that we can use binary search to do quick // lookups. - SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); + SmallPtrSet<BasicBlock*, 16> LoopBBs(block_begin(), block_end()); for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { BasicBlock *BB = *BI; for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) { - BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); - if (PHINode *P = dyn_cast<PHINode>(*UI)) + User *U = *UI; + BasicBlock *UserBB = cast<Instruction>(U)->getParent(); + if (PHINode *P = dyn_cast<PHINode>(U)) UserBB = P->getIncomingBlock(UI); // Check the current block, as a fast-path, before checking whether diff --git a/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp b/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp index 89f9743..1ab18ca 100644 --- a/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp +++ b/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp @@ -101,9 +101,9 @@ static Value *computeArraySize(const CallInst *CI, const TargetData *TD, if (const StructType *ST = dyn_cast<StructType>(T)) ElementSize = TD->getStructLayout(ST)->getSizeInBytes(); - // If malloc calls' arg can be determined to be a multiple of ElementSize, + // If malloc call's arg can be determined to be a multiple of ElementSize, // return the multiple. Otherwise, return NULL. - Value *MallocArg = CI->getOperand(1); + Value *MallocArg = CI->getArgOperand(0); Value *Multiple = NULL; if (ComputeMultiple(MallocArg, ElementSize, Multiple, LookThroughSExt)) @@ -120,7 +120,7 @@ const CallInst *llvm::isArrayMalloc(const Value *I, const TargetData *TD) { Value *ArraySize = computeArraySize(CI, TD); if (ArraySize && - ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1)) + ArraySize != ConstantInt::get(CI->getArgOperand(0)->getType(), 1)) return CI; // CI is a non-array malloc or we can't figure out that it is an array malloc. @@ -183,25 +183,25 @@ Value *llvm::getMallocArraySize(CallInst *CI, const TargetData *TD, // free Call Utility Functions. // -/// isFreeCall - Returns true if the value is a call to the builtin free() -bool llvm::isFreeCall(const Value *I) { +/// isFreeCall - Returns non-null if the value is a call to the builtin free() +const CallInst *llvm::isFreeCall(const Value *I) { const CallInst *CI = dyn_cast<CallInst>(I); if (!CI) - return false; + return 0; Function *Callee = CI->getCalledFunction(); if (Callee == 0 || !Callee->isDeclaration() || Callee->getName() != "free") - return false; + return 0; // Check free prototype. // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin // attribute will exist. const FunctionType *FTy = Callee->getFunctionType(); if (!FTy->getReturnType()->isVoidTy()) - return false; + return 0; if (FTy->getNumParams() != 1) - return false; + return 0; if (FTy->param_begin()->get() != Type::getInt8PtrTy(Callee->getContext())) - return false; + return 0; - return true; + return CI; } diff --git a/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp index 2aa2f17..1f54d74 100644 --- a/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -116,8 +116,8 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) { Pointer = V->getOperand(0); PointerSize = AA->getTypeStoreSize(V->getType()); - } else if (isFreeCall(Inst)) { - Pointer = Inst->getOperand(1); + } else if (const CallInst *CI = isFreeCall(Inst)) { + Pointer = CI->getArgOperand(0); // calls to free() erase the entire structure PointerSize = ~0ULL; } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { @@ -197,9 +197,9 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, // pointer, not on query pointers that are indexed off of them. It'd // be nice to handle that at some point. AliasAnalysis::AliasResult R = - AA->alias(II->getOperand(3), ~0U, MemPtr, ~0U); + AA->alias(II->getArgOperand(2), ~0U, MemPtr, ~0U); if (R == AliasAnalysis::MustAlias) { - InvariantTag = II->getOperand(1); + InvariantTag = II->getArgOperand(0); continue; } @@ -210,7 +210,7 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, // pointer, not on query pointers that are indexed off of them. It'd // be nice to handle that at some point. AliasAnalysis::AliasResult R = - AA->alias(II->getOperand(2), ~0U, MemPtr, ~0U); + AA->alias(II->getArgOperand(1), ~0U, MemPtr, ~0U); if (R == AliasAnalysis::MustAlias) return MemDepResult::getDef(II); } @@ -365,25 +365,26 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { MemPtr = LI->getPointerOperand(); MemSize = AA->getTypeStoreSize(LI->getType()); } - } else if (isFreeCall(QueryInst)) { - MemPtr = QueryInst->getOperand(1); + } else if (const CallInst *CI = isFreeCall(QueryInst)) { + MemPtr = CI->getArgOperand(0); // calls to free() erase the entire structure, not just a field. MemSize = ~0UL; } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) { int IntrinsicID = 0; // Intrinsic IDs start at 1. - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst)) + IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst); + if (II) IntrinsicID = II->getIntrinsicID(); switch (IntrinsicID) { case Intrinsic::lifetime_start: case Intrinsic::lifetime_end: case Intrinsic::invariant_start: - MemPtr = QueryInst->getOperand(2); - MemSize = cast<ConstantInt>(QueryInst->getOperand(1))->getZExtValue(); + MemPtr = II->getArgOperand(1); + MemSize = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); break; case Intrinsic::invariant_end: - MemPtr = QueryInst->getOperand(3); - MemSize = cast<ConstantInt>(QueryInst->getOperand(2))->getZExtValue(); + MemPtr = II->getArgOperand(2); + MemSize = cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); break; default: CallSite QueryCS = CallSite::get(QueryInst); @@ -456,7 +457,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // Okay, we have a cache entry. If we know it is not dirty, just return it // with no computation. if (!CacheP.second) { - NumCacheNonLocal++; + ++NumCacheNonLocal; return Cache; } @@ -478,7 +479,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { BasicBlock *QueryBB = QueryCS.getInstruction()->getParent(); for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI) DirtyBlocks.push_back(*PI); - NumUncacheNonLocal++; + ++NumUncacheNonLocal; } // isReadonlyCall - If this is a read-only call, we can be more aggressive. diff --git a/contrib/llvm/lib/Analysis/PostDominators.cpp b/contrib/llvm/lib/Analysis/PostDominators.cpp index f0f3a05..7354afa 100644 --- a/contrib/llvm/lib/Analysis/PostDominators.cpp +++ b/contrib/llvm/lib/Analysis/PostDominators.cpp @@ -67,10 +67,11 @@ PostDominanceFrontier::calculate(const PostDominatorTree &DT, if (BB) for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI) { + BasicBlock *P = *SI; // Does Node immediately dominate this predecessor? - DomTreeNode *SINode = DT[*SI]; + DomTreeNode *SINode = DT[P]; if (SINode && SINode->getIDom() != Node) - S.insert(*SI); + S.insert(P); } // At this point, S is DFlocal. Now we union in DFup's of our children... diff --git a/contrib/llvm/lib/Analysis/ProfileInfo.cpp b/contrib/llvm/lib/Analysis/ProfileInfo.cpp index 662576e..8d2712f 100644 --- a/contrib/llvm/lib/Analysis/ProfileInfo.cpp +++ b/contrib/llvm/lib/Analysis/ProfileInfo.cpp @@ -71,22 +71,24 @@ ProfileInfoT<Function,BasicBlock>::getExecutionCount(const BasicBlock *BB) { // Are there zero predecessors of this block? if (PI == PE) { - Edge e = getEdge(0,BB); + Edge e = getEdge(0, BB); Count = getEdgeWeight(e); } else { // Otherwise, if there are predecessors, the execution count of this block is // the sum of the edge frequencies from the incoming edges. std::set<const BasicBlock*> ProcessedPreds; Count = 0; - for (; PI != PE; ++PI) - if (ProcessedPreds.insert(*PI).second) { - double w = getEdgeWeight(getEdge(*PI, BB)); + for (; PI != PE; ++PI) { + const BasicBlock *P = *PI; + if (ProcessedPreds.insert(P).second) { + double w = getEdgeWeight(getEdge(P, BB)); if (w == MissingValue) { Count = MissingValue; break; } Count += w; } + } } // If the predecessors did not suffice to get block weight, try successors. @@ -577,8 +579,6 @@ static void readEdge(ProfileInfo *PI, ProfileInfo::Edge e, double &calcw, std::s template<> bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *BB) { - bool hasNoSuccessors = false; - double inWeight = 0; std::set<Edge> inMissing; std::set<const BasicBlock*> ProcessedPreds; @@ -596,10 +596,8 @@ bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *B std::set<Edge> outMissing; std::set<const BasicBlock*> ProcessedSuccs; succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB); - if (sbbi == sbbe) { + if (sbbi == sbbe) readEdge(this,getEdge(BB,0),outWeight,outMissing); - hasNoSuccessors = true; - } for ( ; sbbi != sbbe; ++sbbi ) { if (ProcessedSuccs.insert(*sbbi).second) { readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing); diff --git a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp index 6870268..413b3b4 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp @@ -822,7 +822,8 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) return getConstant( - cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty))); + cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), + getEffectiveSCEVType(Ty)))); // trunc(trunc(x)) --> trunc(x) if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) @@ -844,9 +845,9 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, return getAddRecExpr(Operands, AddRec->getLoop()); } - // The cast wasn't folded; create an explicit cast node. - // Recompute the insert position, as it may have been invalidated. - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + // The cast wasn't folded; create an explicit cast node. We can reuse + // the existing insert position since if we get here, we won't have + // made any changes which would invalidate it. SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); @@ -862,12 +863,10 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Ty = getEffectiveSCEVType(Ty); // Fold if the operand is constant. - if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { - const Type *IntTy = getEffectiveSCEVType(Ty); - Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy); - if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); - return getConstant(cast<ConstantInt>(C)); - } + if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) + return getConstant( + cast<ConstantInt>(ConstantExpr::getZExt(SC->getValue(), + getEffectiveSCEVType(Ty)))); // zext(zext(x)) --> zext(x) if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) @@ -997,12 +996,10 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, Ty = getEffectiveSCEVType(Ty); // Fold if the operand is constant. - if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { - const Type *IntTy = getEffectiveSCEVType(Ty); - Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy); - if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); - return getConstant(cast<ConstantInt>(C)); - } + if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) + return getConstant( + cast<ConstantInt>(ConstantExpr::getSExt(SC->getValue(), + getEffectiveSCEVType(Ty)))); // sext(sext(x)) --> sext(x) if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) @@ -1208,8 +1205,19 @@ CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M, ScalarEvolution &SE) { bool Interesting = false; - // Iterate over the add operands. - for (unsigned i = 0, e = NumOperands; i != e; ++i) { + // Iterate over the add operands. They are sorted, with constants first. + unsigned i = 0; + while (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) { + ++i; + // Pull a buried constant out to the outside. + if (Scale != 1 || AccumulatedConstant != 0 || C->getValue()->isZero()) + Interesting = true; + AccumulatedConstant += Scale * C->getValue()->getValue(); + } + + // Next comes everything else. We're especially interested in multiplies + // here, but they're in the middle, so just visit the rest with one loop. + for (; i != NumOperands; ++i) { const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[i]); if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) { APInt NewScale = @@ -1237,11 +1245,6 @@ CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M, Interesting = true; } } - } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) { - // Pull a buried constant out to the outside. - if (Scale != 1 || AccumulatedConstant != 0 || C->getValue()->isZero()) - Interesting = true; - AccumulatedConstant += Scale * C->getValue()->getValue(); } else { // An ordinary operand. Update the map. std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair = @@ -1275,9 +1278,9 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, assert(!Ops.empty() && "Cannot get empty add!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG + const Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); for (unsigned i = 1, e = Ops.size(); i != e; ++i) - assert(getEffectiveSCEVType(Ops[i]->getType()) == - getEffectiveSCEVType(Ops[0]->getType()) && + assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy && "SCEVAddExpr operand types don't match!"); #endif @@ -1400,8 +1403,8 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) { // If we have an add, expand the add operands onto the end of the operands // list. - Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(Add->op_begin(), Add->op_end()); DeletedAdd = true; } @@ -1549,9 +1552,11 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, AddRec->op_end()); AddRecOps[0] = getAddExpr(LIOps); - // It's tempting to propagate NUW/NSW flags here, but nuw/nsw addition - // is not associative so this isn't necessarily safe. - const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop); + // Build the new addrec. Propagate the NUW and NSW flags if both the + // outer add and the inner addrec are guaranteed to have no overflow. + const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, + HasNUW && AddRec->hasNoUnsignedWrap(), + HasNSW && AddRec->hasNoSignedWrap()); // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -1578,7 +1583,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, AddRec->op_end()); for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) { if (i >= NewOps.size()) { - NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i, + NewOps.append(OtherAddRec->op_begin()+i, OtherAddRec->op_end()); break; } @@ -1711,8 +1716,8 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) { // If we have an mul, expand the mul operands onto the end of the operands // list. - Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(Mul->op_begin(), Mul->op_end()); DeletedMul = true; } @@ -1747,23 +1752,15 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step} SmallVector<const SCEV *, 4> NewOps; NewOps.reserve(AddRec->getNumOperands()); - if (LIOps.size() == 1) { - const SCEV *Scale = LIOps[0]; - for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) - NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i))); - } else { - for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { - SmallVector<const SCEV *, 4> MulOps(LIOps.begin(), LIOps.end()); - MulOps.push_back(AddRec->getOperand(i)); - NewOps.push_back(getMulExpr(MulOps)); - } - } + const SCEV *Scale = getMulExpr(LIOps); + for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) + NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i))); - // It's tempting to propagate the NSW flag here, but nsw multiplication - // is not associative so this isn't necessarily safe. + // Build the new addrec. Propagate the NUW and NSW flags if both the + // outer mul and the inner addrec are guaranteed to have no overflow. const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), HasNUW && AddRec->hasNoUnsignedWrap(), - /*HasNSW=*/false); + HasNSW && AddRec->hasNoSignedWrap()); // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -1942,8 +1939,7 @@ const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, Operands.push_back(Start); if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step)) if (StepChrec->getLoop() == L) { - Operands.insert(Operands.end(), StepChrec->op_begin(), - StepChrec->op_end()); + Operands.append(StepChrec->op_begin(), StepChrec->op_end()); return getAddRecExpr(Operands, L); } @@ -2106,8 +2102,8 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { if (Idx < Ops.size()) { bool DeletedSMax = false; while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) { - Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(SMax->op_begin(), SMax->op_end()); DeletedSMax = true; } @@ -2211,8 +2207,8 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { if (Idx < Ops.size()) { bool DeletedUMax = false; while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) { - Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(UMax->op_begin(), UMax->op_end()); DeletedUMax = true; } @@ -2278,7 +2274,8 @@ const SCEV *ScalarEvolution::getSizeOfExpr(const Type *AllocTy) { Constant *C = ConstantExpr::getSizeOf(AllocTy); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } @@ -2286,7 +2283,8 @@ const SCEV *ScalarEvolution::getSizeOfExpr(const Type *AllocTy) { const SCEV *ScalarEvolution::getAlignOfExpr(const Type *AllocTy) { Constant *C = ConstantExpr::getAlignOf(AllocTy); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } @@ -2302,7 +2300,8 @@ const SCEV *ScalarEvolution::getOffsetOfExpr(const StructType *STy, Constant *C = ConstantExpr::getOffsetOf(STy, FieldNo); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } @@ -2311,7 +2310,8 @@ const SCEV *ScalarEvolution::getOffsetOfExpr(const Type *CTy, Constant *FieldNo) { Constant *C = ConstantExpr::getOffsetOf(CTy, FieldNo); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(CTy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } @@ -2398,13 +2398,6 @@ const SCEV *ScalarEvolution::getSCEV(Value *V) { return S; } -/// getIntegerSCEV - Given a SCEVable type, create a constant for the -/// specified signed integer value and return a SCEV for the constant. -const SCEV *ScalarEvolution::getIntegerSCEV(int64_t Val, const Type *Ty) { - const IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty)); - return getConstant(ConstantInt::get(ITy, Val)); -} - /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V /// const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V) { @@ -2772,7 +2765,11 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { /// const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { - bool InBounds = GEP->isInBounds(); + // Don't blindly transfer the inbounds flag from the GEP instruction to the + // Add expression, because the Instruction may be guarded by control flow + // and the no-overflow bits may not be valid for the expression in any + // context. + const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType()); Value *Base = GEP->getOperand(0); // Don't attempt to analyze GEPs over unsized objects. @@ -2788,23 +2785,30 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { if (const StructType *STy = dyn_cast<StructType>(*GTI++)) { // For a struct, add the member offset. unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); - TotalOffset = getAddExpr(TotalOffset, - getOffsetOfExpr(STy, FieldNo), - /*HasNUW=*/false, /*HasNSW=*/InBounds); + const SCEV *FieldOffset = getOffsetOfExpr(STy, FieldNo); + + // Add the field offset to the running total offset. + TotalOffset = getAddExpr(TotalOffset, FieldOffset); } else { // For an array, add the element offset, explicitly scaled. - const SCEV *LocalOffset = getSCEV(Index); + const SCEV *ElementSize = getSizeOfExpr(*GTI); + const SCEV *IndexS = getSCEV(Index); // Getelementptr indices are signed. - LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy); - // Lower "inbounds" GEPs to NSW arithmetic. - LocalOffset = getMulExpr(LocalOffset, getSizeOfExpr(*GTI), - /*HasNUW=*/false, /*HasNSW=*/InBounds); - TotalOffset = getAddExpr(TotalOffset, LocalOffset, - /*HasNUW=*/false, /*HasNSW=*/InBounds); + IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy); + + // Multiply the index by the element size to compute the element offset. + const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize); + + // Add the element offset to the running total offset. + TotalOffset = getAddExpr(TotalOffset, LocalOffset); } } - return getAddExpr(getSCEV(Base), TotalOffset, - /*HasNUW=*/false, /*HasNSW=*/InBounds); + + // Get the SCEV for the GEP base. + const SCEV *BaseS = getSCEV(Base); + + // Add the total offset from all the GEP indices to the base. + return getAddExpr(BaseS, TotalOffset); } /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is @@ -2963,7 +2967,8 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart())) if (!C->getValue()->isZero()) ConservativeResult = - ConstantRange(C->getValue()->getValue(), APInt(BitWidth, 0)); + ConservativeResult.intersectWith( + ConstantRange(C->getValue()->getValue(), APInt(BitWidth, 0))); // TODO: non-affine addrec if (AddRec->isAffine()) { @@ -3196,15 +3201,9 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { Operator *U = cast<Operator>(V); switch (Opcode) { case Instruction::Add: - // Don't transfer the NSW and NUW bits from the Add instruction to the - // Add expression, because the Instruction may be guarded by control - // flow and the no-overflow bits may not be valid for the expression in - // any context. return getAddExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); case Instruction::Mul: - // Don't transfer the NSW and NUW bits from the Mul instruction to the - // Mul expression, as with Add. return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); case Instruction::UDiv: @@ -3658,6 +3657,26 @@ void ScalarEvolution::forgetValue(Value *V) { ConstantEvolutionLoopExitValue.erase(PN); } + // If there's a SCEVUnknown tying this value into the SCEV + // space, remove it from the folding set map. The SCEVUnknown + // object and any other SCEV objects which reference it + // (transitively) remain allocated, effectively leaked until + // the underlying BumpPtrAllocator is freed. + // + // This permits SCEV pointers to be used as keys in maps + // such as the ValuesAtScopes map. + FoldingSetNodeID ID; + ID.AddInteger(scUnknown); + ID.AddPointer(I); + void *IP; + if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) { + UniqueSCEVs.RemoveNode(S); + + // This isn't necessary, but we might as well remove the + // value from the ValuesAtScopes map too. + ValuesAtScopes.erase(S); + } + PushDefUseChildren(I, Worklist); } } @@ -4139,8 +4158,7 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { // constant or derived from a PHI node themselves. PHINode *PHI = 0; for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op) - if (!(isa<Constant>(I->getOperand(Op)) || - isa<GlobalValue>(I->getOperand(Op)))) { + if (!isa<Constant>(I->getOperand(Op))) { PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L); if (P == 0) return 0; // Not evolving from PHI if (PHI == 0) @@ -4161,11 +4179,9 @@ static Constant *EvaluateExpression(Value *V, Constant *PHIVal, const TargetData *TD) { if (isa<PHINode>(V)) return PHIVal; if (Constant *C = dyn_cast<Constant>(V)) return C; - if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV; Instruction *I = cast<Instruction>(V); - std::vector<Constant*> Operands; - Operands.resize(I->getNumOperands()); + std::vector<Constant*> Operands(I->getNumOperands()); for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal, TD); @@ -4207,8 +4223,8 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, return RetVal = 0; // Must be a constant. Value *BEValue = PN->getIncomingValue(SecondIsBackedge); - PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); - if (PN2 != PN) + if (getConstantEvolvingPHI(BEValue, L) != PN && + !isa<Constant>(BEValue)) return RetVal = 0; // Not derived from same PHI. // Execute the loop symbolically to determine the exit value. @@ -4243,8 +4259,11 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, PHINode *PN = getConstantEvolvingPHI(Cond, L); if (PN == 0) return getCouldNotCompute(); - // Since the loop is canonicalized, the PHI node must have two entries. One - // entry must be a constant (coming in from outside of the loop), and the + // If the loop is canonicalized, the PHI will have exactly two entries. + // That's the only form we support here. + if (PN->getNumIncomingValues() != 2) return getCouldNotCompute(); + + // One entry must be a constant (coming in from outside of the loop), and the // second must be derived from the same PHI. bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); Constant *StartCST = @@ -4252,8 +4271,9 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, if (StartCST == 0) return getCouldNotCompute(); // Must be a constant. Value *BEValue = PN->getIncomingValue(SecondIsBackedge); - PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); - if (PN2 != PN) return getCouldNotCompute(); // Not derived from same PHI. + if (getConstantEvolvingPHI(BEValue, L) != PN && + !isa<Constant>(BEValue)) + return getCouldNotCompute(); // Not derived from same PHI. // Okay, we find a PHI node that defines the trip count of this loop. Execute // the loop symbolically to determine when the condition gets a value of @@ -4341,54 +4361,51 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // the arguments into constants, and if so, try to constant propagate the // result. This is particularly useful for computing loop exit values. if (CanConstantFold(I)) { - std::vector<Constant*> Operands; - Operands.reserve(I->getNumOperands()); + SmallVector<Constant *, 4> Operands; + bool MadeImprovement = false; for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Value *Op = I->getOperand(i); if (Constant *C = dyn_cast<Constant>(Op)) { Operands.push_back(C); - } else { - // If any of the operands is non-constant and if they are - // non-integer and non-pointer, don't even try to analyze them - // with scev techniques. - if (!isSCEVable(Op->getType())) - return V; - - const SCEV *OpV = getSCEVAtScope(Op, L); - if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) { - Constant *C = SC->getValue(); - if (C->getType() != Op->getType()) - C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, - Op->getType(), - false), - C, Op->getType()); - Operands.push_back(C); - } else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) { - if (Constant *C = dyn_cast<Constant>(SU->getValue())) { - if (C->getType() != Op->getType()) - C = - ConstantExpr::getCast(CastInst::getCastOpcode(C, false, - Op->getType(), - false), - C, Op->getType()); - Operands.push_back(C); - } else - return V; - } else { - return V; - } + continue; } + + // If any of the operands is non-constant and if they are + // non-integer and non-pointer, don't even try to analyze them + // with scev techniques. + if (!isSCEVable(Op->getType())) + return V; + + const SCEV *OrigV = getSCEV(Op); + const SCEV *OpV = getSCEVAtScope(OrigV, L); + MadeImprovement |= OrigV != OpV; + + Constant *C = 0; + if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) + C = SC->getValue(); + if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) + C = dyn_cast<Constant>(SU->getValue()); + if (!C) return V; + if (C->getType() != Op->getType()) + C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, + Op->getType(), + false), + C, Op->getType()); + Operands.push_back(C); } - Constant *C = 0; - if (const CmpInst *CI = dyn_cast<CmpInst>(I)) - C = ConstantFoldCompareInstOperands(CI->getPredicate(), - Operands[0], Operands[1], TD); - else - C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), - &Operands[0], Operands.size(), TD); - if (C) + // Check to see if getSCEVAtScope actually made an improvement. + if (MadeImprovement) { + Constant *C = 0; + if (const CmpInst *CI = dyn_cast<CmpInst>(I)) + C = ConstantFoldCompareInstOperands(CI->getPredicate(), + Operands[0], Operands[1], TD); + else + C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), + &Operands[0], Operands.size(), TD); + if (!C) return V; return getSCEV(C); + } } } @@ -4438,7 +4455,29 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // If this is a loop recurrence for a loop that does not contain L, then we // are dealing with the final value computed by the loop. if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) { - if (!L || !AddRec->getLoop()->contains(L)) { + // First, attempt to evaluate each operand. + // Avoid performing the look-up in the common case where the specified + // expression has no loop-variant portions. + for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { + const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L); + if (OpAtScope == AddRec->getOperand(i)) + continue; + + // Okay, at least one of these operands is loop variant but might be + // foldable. Build a new instance of the folded commutative expression. + SmallVector<const SCEV *, 8> NewOps(AddRec->op_begin(), + AddRec->op_begin()+i); + NewOps.push_back(OpAtScope); + for (++i; i != e; ++i) + NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L)); + + AddRec = cast<SCEVAddRecExpr>(getAddRecExpr(NewOps, AddRec->getLoop())); + break; + } + + // If the scope is outside the addrec's loop, evaluate it by using the + // loop exit value of the addrec. + if (!AddRec->getLoop()->contains(L)) { // To evaluate this recurrence, we need to know how many times the AddRec // loop iterates. Compute this now. const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); @@ -4447,6 +4486,7 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // Then, evaluate the AddRec. return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); } + return AddRec; } @@ -4696,23 +4736,6 @@ ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) { return getCouldNotCompute(); } -/// getLoopPredecessor - If the given loop's header has exactly one unique -/// predecessor outside the loop, return it. Otherwise return null. -/// This is less strict that the loop "preheader" concept, which requires -/// the predecessor to have only one single successor. -/// -BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) { - BasicBlock *Header = L->getHeader(); - BasicBlock *Pred = 0; - for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); - PI != E; ++PI) - if (!L->contains(*PI)) { - if (Pred && Pred != *PI) return 0; // Multiple predecessors. - Pred = *PI; - } - return Pred; -} - /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one /// successor from which BB is reachable, or null if no such block is @@ -4730,7 +4753,7 @@ ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { // If the header has a unique predecessor outside the loop, it must be // a block that has exactly one successor that can reach the loop. if (Loop *L = LI->getLoopFor(BB)) - return std::make_pair(getLoopPredecessor(L), L->getHeader()); + return std::make_pair(L->getLoopPredecessor(), L->getHeader()); return std::pair<BasicBlock *, BasicBlock *>(); } @@ -5181,7 +5204,7 @@ ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L, // as there are predecessors that can be found that have unique successors // leading to the original header. for (std::pair<BasicBlock *, BasicBlock *> - Pair(getLoopPredecessor(L), L->getHeader()); + Pair(L->getLoopPredecessor(), L->getHeader()); Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) { diff --git a/contrib/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp b/contrib/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp index 17b254f..58711b8 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp @@ -12,7 +12,7 @@ // // This differs from traditional loop dependence analysis in that it tests // for dependencies within a single iteration of a loop, rather than -// dependences between different iterations. +// dependencies between different iterations. // // ScalarEvolution has a more complete understanding of pointer arithmetic // than BasicAliasAnalysis' collection of ad-hoc analyses. @@ -106,6 +106,12 @@ ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { AliasAnalysis::AliasResult ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, const Value *B, unsigned BSize) { + // If either of the memory references is empty, it doesn't matter what the + // pointer values are. This allows the code below to ignore this special + // case. + if (ASize == 0 || BSize == 0) + return NoAlias; + // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! const SCEV *AS = SE->getSCEV(const_cast<Value *>(A)); const SCEV *BS = SE->getSCEV(const_cast<Value *>(B)); @@ -118,14 +124,32 @@ ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, if (SE->getEffectiveSCEVType(AS->getType()) == SE->getEffectiveSCEVType(BS->getType())) { unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); - APInt AI(BitWidth, ASize); + APInt ASizeInt(BitWidth, ASize); + APInt BSizeInt(BitWidth, BSize); + + // Compute the difference between the two pointers. const SCEV *BA = SE->getMinusSCEV(BS, AS); - if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) { - APInt BI(BitWidth, BSize); - const SCEV *AB = SE->getMinusSCEV(AS, BS); - if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin())) - return NoAlias; - } + + // Test whether the difference is known to be great enough that memory of + // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt + // are non-zero, which is special-cased above. + if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) && + (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax())) + return NoAlias; + + // Folding the subtraction while preserving range information can be tricky + // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS + // and try again to see if things fold better that way. + + // Compute the difference between the two pointers. + const SCEV *AB = SE->getMinusSCEV(AS, BS); + + // Test whether the difference is known to be great enough that memory of + // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt + // are non-zero, which is special-cased above. + if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) && + (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax())) + return NoAlias; } // If ScalarEvolution can find an underlying object, form a new query. diff --git a/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp index 0012b84..d4a4b26 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp @@ -21,6 +21,43 @@ #include "llvm/ADT/STLExtras.h" using namespace llvm; +/// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP, +/// reusing an existing cast if a suitable one exists, moving an existing +/// cast if a suitable one exists but isn't in the right place, or +/// creating a new one. +Value *SCEVExpander::ReuseOrCreateCast(Value *V, const Type *Ty, + Instruction::CastOps Op, + BasicBlock::iterator IP) { + // Check to see if there is already a cast! + for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); + UI != E; ++UI) { + User *U = *UI; + if (U->getType() == Ty) + if (CastInst *CI = dyn_cast<CastInst>(U)) + if (CI->getOpcode() == Op) { + // If the cast isn't where we want it, fix it. + if (BasicBlock::iterator(CI) != IP) { + // Create a new cast, and leave the old cast in place in case + // it is being used as an insert point. Clear its operand + // so that it doesn't hold anything live. + Instruction *NewCI = CastInst::Create(Op, V, Ty, "", IP); + NewCI->takeName(CI); + CI->replaceAllUsesWith(NewCI); + CI->setOperand(0, UndefValue::get(V->getType())); + rememberInstruction(NewCI); + return NewCI; + } + rememberInstruction(CI); + return CI; + } + } + + // Create a new cast. + Instruction *I = CastInst::Create(Op, V, Ty, V->getName(), IP); + rememberInstruction(I); + return I; +} + /// InsertNoopCastOfTo - Insert a cast of V to the specified type, /// which must be possible with a noop cast, doing what we can to share /// the casts. @@ -54,71 +91,29 @@ Value *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { return CE->getOperand(0); } + // Fold a cast of a constant. if (Constant *C = dyn_cast<Constant>(V)) return ConstantExpr::getCast(Op, C, Ty); + // Cast the argument at the beginning of the entry block, after + // any bitcasts of other arguments. if (Argument *A = dyn_cast<Argument>(V)) { - // Check to see if there is already a cast! - for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); - UI != E; ++UI) - if ((*UI)->getType() == Ty) - if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) - if (CI->getOpcode() == Op) { - // If the cast isn't the first instruction of the function, move it. - if (BasicBlock::iterator(CI) != - A->getParent()->getEntryBlock().begin()) { - // Recreate the cast at the beginning of the entry block. - // The old cast is left in place in case it is being used - // as an insert point. - Instruction *NewCI = - CastInst::Create(Op, V, Ty, "", - A->getParent()->getEntryBlock().begin()); - NewCI->takeName(CI); - CI->replaceAllUsesWith(NewCI); - return NewCI; - } - return CI; - } - - Instruction *I = CastInst::Create(Op, V, Ty, V->getName(), - A->getParent()->getEntryBlock().begin()); - rememberInstruction(I); - return I; + BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin(); + while ((isa<BitCastInst>(IP) && + isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) && + cast<BitCastInst>(IP)->getOperand(0) != A) || + isa<DbgInfoIntrinsic>(IP)) + ++IP; + return ReuseOrCreateCast(A, Ty, Op, IP); } + // Cast the instruction immediately after the instruction. Instruction *I = cast<Instruction>(V); - - // Check to see if there is already a cast. If there is, use it. - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - if ((*UI)->getType() == Ty) - if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) - if (CI->getOpcode() == Op) { - BasicBlock::iterator It = I; ++It; - if (isa<InvokeInst>(I)) - It = cast<InvokeInst>(I)->getNormalDest()->begin(); - while (isa<PHINode>(It)) ++It; - if (It != BasicBlock::iterator(CI)) { - // Recreate the cast after the user. - // The old cast is left in place in case it is being used - // as an insert point. - Instruction *NewCI = CastInst::Create(Op, V, Ty, "", It); - NewCI->takeName(CI); - CI->replaceAllUsesWith(NewCI); - rememberInstruction(NewCI); - return NewCI; - } - rememberInstruction(CI); - return CI; - } - } BasicBlock::iterator IP = I; ++IP; if (InvokeInst *II = dyn_cast<InvokeInst>(I)) IP = II->getNormalDest()->begin(); - while (isa<PHINode>(IP)) ++IP; - Instruction *CI = CastInst::Create(Op, V, Ty, V->getName(), IP); - rememberInstruction(CI); - return CI; + while (isa<PHINode>(IP) || isa<DbgInfoIntrinsic>(IP)) ++IP; + return ReuseOrCreateCast(I, Ty, Op, IP); } /// InsertBinop - Insert the specified binary operator, doing a small amount @@ -295,11 +290,11 @@ static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops, // the sum into a single value, so just use that. Ops.clear(); if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum)) - Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); + Ops.append(Add->op_begin(), Add->op_end()); else if (!Sum->isZero()) Ops.push_back(Sum); // Then append the addrecs. - Ops.insert(Ops.end(), AddRecs.begin(), AddRecs.end()); + Ops.append(AddRecs.begin(), AddRecs.end()); } /// SplitAddRecs - Flatten a list of add operands, moving addrec start values @@ -322,7 +317,7 @@ static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, A->getLoop())); if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) { Ops[i] = Zero; - Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); + Ops.append(Add->op_begin(), Add->op_end()); e += Add->getNumOperands(); } else { Ops[i] = Start; @@ -330,7 +325,7 @@ static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, } if (!AddRecs.empty()) { // Add the addrecs onto the end of the list. - Ops.insert(Ops.end(), AddRecs.begin(), AddRecs.end()); + Ops.append(AddRecs.begin(), AddRecs.end()); // Resort the operand list, moving any constants to the front. SimplifyAddOperands(Ops, Ty, SE); } @@ -1070,7 +1065,8 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); BasicBlock::iterator NewInsertPt = llvm::next(BasicBlock::iterator(cast<Instruction>(V))); - while (isa<PHINode>(NewInsertPt)) ++NewInsertPt; + while (isa<PHINode>(NewInsertPt) || isa<DbgInfoIntrinsic>(NewInsertPt)) + ++NewInsertPt; V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, NewInsertPt); restoreInsertPoint(SaveInsertBB, SaveInsertPt); @@ -1107,8 +1103,7 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { } // {0,+,1} --> Insert a canonical induction variable into the loop! - if (S->isAffine() && - S->getOperand(1) == SE.getConstant(Ty, 1)) { + if (S->isAffine() && S->getOperand(1)->isOne()) { // If there's a canonical IV, just use it. if (CanonicalIV) { assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && @@ -1125,17 +1120,19 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { Constant *One = ConstantInt::get(Ty, 1); for (pred_iterator HPI = pred_begin(Header), HPE = pred_end(Header); - HPI != HPE; ++HPI) - if (L->contains(*HPI)) { + HPI != HPE; ++HPI) { + BasicBlock *HP = *HPI; + if (L->contains(HP)) { // Insert a unit add instruction right before the terminator // corresponding to the back-edge. Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", - (*HPI)->getTerminator()); + HP->getTerminator()); rememberInstruction(Add); - PN->addIncoming(Add, *HPI); + PN->addIncoming(Add, HP); } else { - PN->addIncoming(Constant::getNullValue(Ty), *HPI); + PN->addIncoming(Constant::getNullValue(Ty), HP); } + } } // {0,+,F} --> {0,+,1} * F @@ -1312,7 +1309,9 @@ Value *SCEVExpander::expand(const SCEV *S) { } void SCEVExpander::rememberInstruction(Value *I) { - if (PostIncLoops.empty()) + if (!PostIncLoops.empty()) + InsertedPostIncValues.insert(I); + else InsertedValues.insert(I); // If we just claimed an existing instruction and that instruction had diff --git a/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp b/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp index 75c381d..563fd2f 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp @@ -105,22 +105,25 @@ const SCEV *llvm::TransformForPostIncUse(TransformKind Kind, case NormalizeAutodetect: if (Instruction *OI = dyn_cast<Instruction>(OperandValToReplace)) if (IVUseShouldUsePostIncValue(User, OI, L, &DT)) { - Result = SE.getMinusSCEV(Result, AR->getStepRecurrence(SE)); + const SCEV *TransformedStep = + TransformForPostIncUse(Kind, AR->getStepRecurrence(SE), + User, OperandValToReplace, Loops, SE, DT); + Result = SE.getMinusSCEV(Result, TransformedStep); Loops.insert(L); } break; case Normalize: - if (Loops.count(L)) - Result = SE.getMinusSCEV(Result, AR->getStepRecurrence(SE)); - break; - case Denormalize: if (Loops.count(L)) { const SCEV *TransformedStep = TransformForPostIncUse(Kind, AR->getStepRecurrence(SE), User, OperandValToReplace, Loops, SE, DT); - Result = SE.getAddExpr(Result, TransformedStep); + Result = SE.getMinusSCEV(Result, TransformedStep); } break; + case Denormalize: + if (Loops.count(L)) + Result = SE.getAddExpr(Result, AR->getStepRecurrence(SE)); + break; } return Result; } diff --git a/contrib/llvm/lib/Analysis/ValueTracking.cpp b/contrib/llvm/lib/Analysis/ValueTracking.cpp index 7e8ec2e..b4c9884 100644 --- a/contrib/llvm/lib/Analysis/ValueTracking.cpp +++ b/contrib/llvm/lib/Analysis/ValueTracking.cpp @@ -953,7 +953,7 @@ bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) // sqrt(-0.0) = -0.0, no other negative results are possible. if (II->getIntrinsicID() == Intrinsic::sqrt) - return CannotBeNegativeZero(II->getOperand(1), Depth+1); + return CannotBeNegativeZero(II->getArgOperand(0), Depth+1); if (const CallInst *CI = dyn_cast<CallInst>(I)) if (const Function *F = CI->getCalledFunction()) { @@ -966,7 +966,7 @@ bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { if (F->getName() == "fabsl") return true; if (F->getName() == "sqrt" || F->getName() == "sqrtf" || F->getName() == "sqrtl") - return CannotBeNegativeZero(CI->getOperand(1), Depth+1); + return CannotBeNegativeZero(CI->getArgOperand(0), Depth+1); } } |
