diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis')
33 files changed, 1068 insertions, 1385 deletions
diff --git a/contrib/llvm/lib/Analysis/AliasAnalysis.cpp b/contrib/llvm/lib/Analysis/AliasAnalysis.cpp index be02ddb..c189a00 100644 --- a/contrib/llvm/lib/Analysis/AliasAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/AliasAnalysis.cpp @@ -86,14 +86,20 @@ AliasAnalysis::getModRefInfo(ImmutableCallSite CS, if (onlyAccessesArgPointees(MRB)) { bool doesAlias = false; - if (doesAccessArgPointees(MRB)) + if (doesAccessArgPointees(MRB)) { + MDNode *CSTag = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa); for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); - AI != AE; ++AI) - if (!isNoAlias(Location(*AI), Loc)) { + AI != AE; ++AI) { + const Value *Arg = *AI; + if (!Arg->getType()->isPointerTy()) + continue; + Location CSLoc(Arg, UnknownSize, CSTag); + if (!isNoAlias(CSLoc, Loc)) { doesAlias = true; break; } - + } + } if (!doesAlias) return NoModRef; } @@ -138,13 +144,19 @@ AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { // CS2's arguments. if (onlyAccessesArgPointees(CS2B)) { AliasAnalysis::ModRefResult R = NoModRef; - if (doesAccessArgPointees(CS2B)) + if (doesAccessArgPointees(CS2B)) { + MDNode *CS2Tag = CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa); for (ImmutableCallSite::arg_iterator I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { - R = ModRefResult((R | getModRefInfo(CS1, *I, UnknownSize)) & Mask); + const Value *Arg = *I; + if (!Arg->getType()->isPointerTy()) + continue; + Location CS2Loc(Arg, UnknownSize, CS2Tag); + R = ModRefResult((R | getModRefInfo(CS1, CS2Loc)) & Mask); if (R == Mask) break; } + } return R; } @@ -152,13 +164,20 @@ AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { // any of the memory referenced by CS1's arguments. If not, return NoModRef. if (onlyAccessesArgPointees(CS1B)) { AliasAnalysis::ModRefResult R = NoModRef; - if (doesAccessArgPointees(CS1B)) + if (doesAccessArgPointees(CS1B)) { + MDNode *CS1Tag = CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa); for (ImmutableCallSite::arg_iterator - I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) - if (getModRefInfo(CS2, *I, UnknownSize) != NoModRef) { + I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { + const Value *Arg = *I; + if (!Arg->getType()->isPointerTy()) + continue; + Location CS1Loc(Arg, UnknownSize, CS1Tag); + if (getModRefInfo(CS2, CS1Loc) != NoModRef) { R = Mask; break; } + } + } if (R == NoModRef) return R; } diff --git a/contrib/llvm/lib/Analysis/AliasSetTracker.cpp b/contrib/llvm/lib/Analysis/AliasSetTracker.cpp index 3a46976d..2ed6949 100644 --- a/contrib/llvm/lib/Analysis/AliasSetTracker.cpp +++ b/contrib/llvm/lib/Analysis/AliasSetTracker.cpp @@ -602,6 +602,10 @@ void AliasSetTracker::ASTCallbackVH::deleted() { // this now dangles! } +void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) { + AST->copyValue(getValPtr(), V); +} + AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast) : CallbackVH(V), AST(ast) {} diff --git a/contrib/llvm/lib/Analysis/Analysis.cpp b/contrib/llvm/lib/Analysis/Analysis.cpp index 1af1c35..6ebe100 100644 --- a/contrib/llvm/lib/Analysis/Analysis.cpp +++ b/contrib/llvm/lib/Analysis/Analysis.cpp @@ -43,14 +43,12 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeLazyValueInfoPass(Registry); initializeLibCallAliasAnalysisPass(Registry); initializeLintPass(Registry); - initializeLiveValuesPass(Registry); initializeLoopDependenceAnalysisPass(Registry); initializeLoopInfoPass(Registry); initializeMemDepPrinterPass(Registry); initializeMemoryDependenceAnalysisPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); initializePostDominatorTreePass(Registry); - initializePostDominanceFrontierPass(Registry); initializeProfileEstimatorPassPass(Registry); initializeNoProfileInfoPass(Registry); initializeNoPathProfileInfoPass(Registry); diff --git a/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp index f7bcd9e..f1bb8a3 100644 --- a/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -350,7 +350,7 @@ DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, Scale *= IndexScale.getSExtValue(); - // If we already had an occurrance of this index variable, merge this + // If we already had an occurrence of this index variable, merge this // scale into it. For example, we want to handle: // A[x][x] -> x*16 + x*4 -> x*20 // This also ensures that 'x' only appears in the index list once. @@ -779,6 +779,26 @@ BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, return NoModRef; break; } + case Intrinsic::arm_neon_vld1: { + // LLVM's vld1 and vst1 intrinsics currently only support a single + // vector register. + uint64_t Size = + TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize; + if (isNoAlias(Location(II->getArgOperand(0), Size, + II->getMetadata(LLVMContext::MD_tbaa)), + Loc)) + return NoModRef; + break; + } + case Intrinsic::arm_neon_vst1: { + uint64_t Size = + TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize; + if (isNoAlias(Location(II->getArgOperand(0), Size, + II->getMetadata(LLVMContext::MD_tbaa)), + Loc)) + return NoModRef; + break; + } } // The AliasAnalysis base class has some smarts, lets use them. @@ -883,7 +903,7 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) return MustAlias; - // If there is a difference betwen the pointers, but the difference is + // If there is a difference between the pointers, but the difference is // less than the size of the associated memory object, then we know // that the objects are partially overlapping. if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { diff --git a/contrib/llvm/lib/Analysis/CaptureTracking.cpp b/contrib/llvm/lib/Analysis/CaptureTracking.cpp index 42a54d9..b2c27d1 100644 --- a/contrib/llvm/lib/Analysis/CaptureTracking.cpp +++ b/contrib/llvm/lib/Analysis/CaptureTracking.cpp @@ -17,6 +17,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Value.h" #include "llvm/Analysis/AliasAnalysis.h" diff --git a/contrib/llvm/lib/Analysis/ConstantFolding.cpp b/contrib/llvm/lib/Analysis/ConstantFolding.cpp index cd8d52c..5de2b04 100644 --- a/contrib/llvm/lib/Analysis/ConstantFolding.cpp +++ b/contrib/llvm/lib/Analysis/ConstantFolding.cpp @@ -23,6 +23,7 @@ #include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" #include "llvm/Intrinsics.h" +#include "llvm/Operator.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Target/TargetData.h" #include "llvm/ADT/SmallVector.h" @@ -1048,11 +1049,12 @@ llvm::canConstantFoldCallTo(const Function *F) { case Intrinsic::ctpop: case Intrinsic::ctlz: case Intrinsic::cttz: - case Intrinsic::uadd_with_overflow: - case Intrinsic::usub_with_overflow: case Intrinsic::sadd_with_overflow: + case Intrinsic::uadd_with_overflow: case Intrinsic::ssub_with_overflow: + case Intrinsic::usub_with_overflow: case Intrinsic::smul_with_overflow: + case Intrinsic::umul_with_overflow: case Intrinsic::convert_from_fp16: case Intrinsic::convert_to_fp16: case Intrinsic::x86_sse_cvtss2si: @@ -1362,7 +1364,8 @@ llvm::ConstantFoldCall(Function *F, case Intrinsic::uadd_with_overflow: case Intrinsic::ssub_with_overflow: case Intrinsic::usub_with_overflow: - case Intrinsic::smul_with_overflow: { + case Intrinsic::smul_with_overflow: + case Intrinsic::umul_with_overflow: { APInt Res; bool Overflow; switch (F->getIntrinsicID()) { @@ -1382,6 +1385,9 @@ llvm::ConstantFoldCall(Function *F, case Intrinsic::smul_with_overflow: Res = Op1->getValue().smul_ov(Op2->getValue(), Overflow); break; + case Intrinsic::umul_with_overflow: + Res = Op1->getValue().umul_ov(Op2->getValue(), Overflow); + break; } Constant *Ops[] = { ConstantInt::get(F->getContext(), Res), diff --git a/contrib/llvm/lib/Analysis/DIBuilder.cpp b/contrib/llvm/lib/Analysis/DIBuilder.cpp index 590a9c1..dc98c9e 100644 --- a/contrib/llvm/lib/Analysis/DIBuilder.cpp +++ b/contrib/llvm/lib/Analysis/DIBuilder.cpp @@ -50,7 +50,7 @@ void DIBuilder::createCompileUnit(unsigned Lang, StringRef Filename, MDString::get(VMContext, Flags), ConstantInt::get(Type::getInt32Ty(VMContext), RunTimeVer) }; - TheCU = DICompileUnit(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + TheCU = DICompileUnit(MDNode::get(VMContext, Elts)); } /// createFile - Create a file descriptor to hold debugging information @@ -63,7 +63,7 @@ DIFile DIBuilder::createFile(StringRef Filename, StringRef Directory) { MDString::get(VMContext, Directory), TheCU }; - return DIFile(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIFile(MDNode::get(VMContext, Elts)); } /// createEnumerator - Create a single enumerator value. @@ -73,7 +73,7 @@ DIEnumerator DIBuilder::createEnumerator(StringRef Name, uint64_t Val) { MDString::get(VMContext, Name), ConstantInt::get(Type::getInt64Ty(VMContext), Val) }; - return DIEnumerator(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIEnumerator(MDNode::get(VMContext, Elts)); } /// createBasicType - Create debugging information entry for a basic @@ -95,7 +95,7 @@ DIType DIBuilder::createBasicType(StringRef Name, uint64_t SizeInBits, ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags; ConstantInt::get(Type::getInt32Ty(VMContext), Encoding) }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createQaulifiedType - Create debugging information entry for a qualified @@ -114,7 +114,7 @@ DIType DIBuilder::createQualifiedType(unsigned Tag, DIType FromTy) { ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags FromTy }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createPointerType - Create debugging information entry for a pointer. @@ -133,7 +133,7 @@ DIType DIBuilder::createPointerType(DIType PointeeTy, uint64_t SizeInBits, ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags PointeeTy }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createReferenceType - Create debugging information entry for a reference. @@ -151,7 +151,7 @@ DIType DIBuilder::createReferenceType(DIType RTy) { ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags RTy }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createTypedef - Create debugging information entry for a typedef. @@ -171,7 +171,7 @@ DIType DIBuilder::createTypedef(DIType Ty, StringRef Name, DIFile File, ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags Ty }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createFriend - Create debugging information entry for a 'friend'. @@ -191,7 +191,7 @@ DIType DIBuilder::createFriend(DIType Ty, DIType FriendTy) { ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags FriendTy }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createInheritance - Create debugging information entry to establish @@ -211,7 +211,7 @@ DIType DIBuilder::createInheritance(DIType Ty, DIType BaseTy, ConstantInt::get(Type::getInt32Ty(VMContext), Flags), BaseTy }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createMemberType - Create debugging information entry for a member. @@ -233,7 +233,36 @@ DIType DIBuilder::createMemberType(StringRef Name, ConstantInt::get(Type::getInt32Ty(VMContext), Flags), Ty }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); +} + +/// createObjCIVar - Create debugging information entry for Objective-C +/// instance variable. +DIType DIBuilder::createObjCIVar(StringRef Name, + DIFile File, unsigned LineNumber, + uint64_t SizeInBits, uint64_t AlignInBits, + uint64_t OffsetInBits, unsigned Flags, + DIType Ty, StringRef PropertyName, + StringRef GetterName, StringRef SetterName, + unsigned PropertyAttributes) { + // TAG_member is encoded in DIDerivedType format. + Value *Elts[] = { + GetTagConstant(VMContext, dwarf::DW_TAG_member), + File, // Or TheCU ? Ty ? + MDString::get(VMContext, Name), + File, + ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), + ConstantInt::get(Type::getInt64Ty(VMContext), SizeInBits), + ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), + ConstantInt::get(Type::getInt64Ty(VMContext), OffsetInBits), + ConstantInt::get(Type::getInt32Ty(VMContext), Flags), + Ty, + MDString::get(VMContext, PropertyName), + MDString::get(VMContext, GetterName), + MDString::get(VMContext, SetterName), + ConstantInt::get(Type::getInt32Ty(VMContext), PropertyAttributes) + }; + return DIType(MDNode::get(VMContext, Elts)); } /// createClassType - Create debugging information entry for a class. @@ -260,7 +289,7 @@ DIType DIBuilder::createClassType(DIDescriptor Context, StringRef Name, VTableHoder, TemplateParams }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createTemplateTypeParameter - Create debugging information for template @@ -278,8 +307,7 @@ DIBuilder::createTemplateTypeParameter(DIDescriptor Context, StringRef Name, ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), ConstantInt::get(Type::getInt32Ty(VMContext), ColumnNo) }; - return DITemplateTypeParameter(MDNode::get(VMContext, &Elts[0], - array_lengthof(Elts))); + return DITemplateTypeParameter(MDNode::get(VMContext, Elts)); } /// createTemplateValueParameter - Create debugging information for template @@ -299,8 +327,7 @@ DIBuilder::createTemplateValueParameter(DIDescriptor Context, StringRef Name, ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), ConstantInt::get(Type::getInt32Ty(VMContext), ColumnNo) }; - return DITemplateValueParameter(MDNode::get(VMContext, &Elts[0], - array_lengthof(Elts))); + return DITemplateValueParameter(MDNode::get(VMContext, Elts)); } /// createStructType - Create debugging information entry for a struct. @@ -325,7 +352,7 @@ DIType DIBuilder::createStructType(DIDescriptor Context, StringRef Name, ConstantInt::get(Type::getInt32Ty(VMContext), RunTimeLang), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createUnionType - Create debugging information entry for an union. @@ -350,7 +377,7 @@ DIType DIBuilder::createUnionType(DIDescriptor Scope, StringRef Name, ConstantInt::get(Type::getInt32Ty(VMContext), RunTimeLang), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createSubroutineType - Create subroutine type. @@ -371,7 +398,7 @@ DIType DIBuilder::createSubroutineType(DIFile File, DIArray ParameterTypes) { ConstantInt::get(Type::getInt32Ty(VMContext), 0), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createEnumerationType - Create debugging information entry for an @@ -396,7 +423,7 @@ DIType DIBuilder::createEnumerationType(DIDescriptor Scope, StringRef Name, ConstantInt::get(Type::getInt32Ty(VMContext), 0), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], array_lengthof(Elts)); + MDNode *Node = MDNode::get(VMContext, Elts); NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.enum"); NMD->addOperand(Node); return DIType(Node); @@ -421,7 +448,7 @@ DIType DIBuilder::createArrayType(uint64_t Size, uint64_t AlignInBits, ConstantInt::get(Type::getInt32Ty(VMContext), 0), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createVectorType - Create debugging information entry for a vector. @@ -443,7 +470,7 @@ DIType DIBuilder::createVectorType(uint64_t Size, uint64_t AlignInBits, ConstantInt::get(Type::getInt32Ty(VMContext), 0), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), }; - return DIType(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DIType(MDNode::get(VMContext, Elts)); } /// createArtificialType - Create a new DIType with "artificial" flag set. @@ -467,7 +494,7 @@ DIType DIBuilder::createArtificialType(DIType Ty) { // Flags are stored at this slot. Elts[8] = ConstantInt::get(Type::getInt32Ty(VMContext), CurFlags); - return DIType(MDNode::get(VMContext, Elts.data(), Elts.size())); + return DIType(MDNode::get(VMContext, Elts)); } /// retainType - Retain DIType in a module even if it is not referenced @@ -483,7 +510,7 @@ DIDescriptor DIBuilder::createUnspecifiedParameter() { Value *Elts[] = { GetTagConstant(VMContext, dwarf::DW_TAG_unspecified_parameters) }; - return DIDescriptor(MDNode::get(VMContext, &Elts[0], 1)); + return DIDescriptor(MDNode::get(VMContext, Elts)); } /// createTemporaryType - Create a temporary forward-declared type. @@ -491,7 +518,7 @@ DIType DIBuilder::createTemporaryType() { // Give the temporary MDNode a tag. It doesn't matter what tag we // use here as long as DIType accepts it. Value *Elts[] = { GetTagConstant(VMContext, DW_TAG_base_type) }; - MDNode *Node = MDNode::getTemporary(VMContext, Elts, array_lengthof(Elts)); + MDNode *Node = MDNode::getTemporary(VMContext, Elts); return DIType(Node); } @@ -505,17 +532,17 @@ DIType DIBuilder::createTemporaryType(DIFile F) { NULL, F }; - MDNode *Node = MDNode::getTemporary(VMContext, Elts, array_lengthof(Elts)); + MDNode *Node = MDNode::getTemporary(VMContext, Elts); return DIType(Node); } /// getOrCreateArray - Get a DIArray, create one if required. -DIArray DIBuilder::getOrCreateArray(Value *const *Elements, unsigned NumElements) { - if (NumElements == 0) { +DIArray DIBuilder::getOrCreateArray(ArrayRef<Value *> Elements) { + if (Elements.empty()) { Value *Null = llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)); - return DIArray(MDNode::get(VMContext, &Null, 1)); + return DIArray(MDNode::get(VMContext, Null)); } - return DIArray(MDNode::get(VMContext, Elements, NumElements)); + return DIArray(MDNode::get(VMContext, Elements)); } /// getOrCreateSubrange - Create a descriptor for a value range. This @@ -527,7 +554,7 @@ DISubrange DIBuilder::getOrCreateSubrange(int64_t Lo, int64_t Hi) { ConstantInt::get(Type::getInt64Ty(VMContext), Hi) }; - return DISubrange(MDNode::get(VMContext, &Elts[0], 3)); + return DISubrange(MDNode::get(VMContext, Elts)); } /// createGlobalVariable - Create a new descriptor for the specified global. @@ -548,7 +575,7 @@ createGlobalVariable(StringRef Name, DIFile F, unsigned LineNumber, ConstantInt::get(Type::getInt32Ty(VMContext), 1), /* isDefinition*/ Val }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], array_lengthof(Elts)); + MDNode *Node = MDNode::get(VMContext, Elts); // Create a named metadata so that we do not lose this mdnode. NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.gv"); NMD->addOperand(Node); @@ -575,7 +602,7 @@ createStaticVariable(DIDescriptor Context, StringRef Name, ConstantInt::get(Type::getInt32Ty(VMContext), 1), /* isDefinition*/ Val }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], array_lengthof(Elts)); + MDNode *Node = MDNode::get(VMContext, Elts); // Create a named metadata so that we do not lose this mdnode. NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.gv"); NMD->addOperand(Node); @@ -586,17 +613,18 @@ createStaticVariable(DIDescriptor Context, StringRef Name, DIVariable DIBuilder::createLocalVariable(unsigned Tag, DIDescriptor Scope, StringRef Name, DIFile File, unsigned LineNo, DIType Ty, - bool AlwaysPreserve, unsigned Flags) { + bool AlwaysPreserve, unsigned Flags, + unsigned ArgNo) { Value *Elts[] = { GetTagConstant(VMContext, Tag), Scope, MDString::get(VMContext, Name), File, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), + ConstantInt::get(Type::getInt32Ty(VMContext), (LineNo | (ArgNo << 24))), Ty, ConstantInt::get(Type::getInt32Ty(VMContext), Flags) }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], array_lengthof(Elts)); + MDNode *Node = MDNode::get(VMContext, Elts); if (AlwaysPreserve) { // The optimizer may remove local variable. If there is an interest // to preserve variable info in such situation then stash it in a @@ -619,18 +647,19 @@ DIVariable DIBuilder::createLocalVariable(unsigned Tag, DIDescriptor Scope, DIVariable DIBuilder::createComplexVariable(unsigned Tag, DIDescriptor Scope, StringRef Name, DIFile F, unsigned LineNo, - DIType Ty, Value *const *Addr, - unsigned NumAddr) { + DIType Ty, ArrayRef<Value *> Addr, + unsigned ArgNo) { SmallVector<Value *, 15> Elts; Elts.push_back(GetTagConstant(VMContext, Tag)); Elts.push_back(Scope); Elts.push_back(MDString::get(VMContext, Name)); Elts.push_back(F); - Elts.push_back(ConstantInt::get(Type::getInt32Ty(VMContext), LineNo)); + Elts.push_back(ConstantInt::get(Type::getInt32Ty(VMContext), (LineNo | (ArgNo << 24)))); Elts.push_back(Ty); - Elts.append(Addr, Addr+NumAddr); + Elts.push_back(llvm::Constant::getNullValue(Type::getInt32Ty(VMContext))); + Elts.append(Addr.begin(), Addr.end()); - return DIVariable(MDNode::get(VMContext, Elts.data(), Elts.size())); + return DIVariable(MDNode::get(VMContext, Elts)); } /// createFunction - Create a new descriptor for the specified function. @@ -641,8 +670,9 @@ DISubprogram DIBuilder::createFunction(DIDescriptor Context, DIType Ty, bool isLocalToUnit, bool isDefinition, unsigned Flags, bool isOptimized, - Function *Fn) { - + Function *Fn, + MDNode *TParams, + MDNode *Decl) { Value *Elts[] = { GetTagConstant(VMContext, dwarf::DW_TAG_subprogram), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), @@ -660,9 +690,11 @@ DISubprogram DIBuilder::createFunction(DIDescriptor Context, llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), ConstantInt::get(Type::getInt32Ty(VMContext), Flags), ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), - Fn + Fn, + TParams, + Decl }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], array_lengthof(Elts)); + MDNode *Node = MDNode::get(VMContext, Elts); // Create a named metadata so that we do not lose this mdnode. NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.sp"); @@ -682,7 +714,8 @@ DISubprogram DIBuilder::createMethod(DIDescriptor Context, MDNode *VTableHolder, unsigned Flags, bool isOptimized, - Function *Fn) { + Function *Fn, + MDNode *TParam) { Value *Elts[] = { GetTagConstant(VMContext, dwarf::DW_TAG_subprogram), llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), @@ -700,9 +733,10 @@ DISubprogram DIBuilder::createMethod(DIDescriptor Context, VTableHolder, ConstantInt::get(Type::getInt32Ty(VMContext), Flags), ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), - Fn + Fn, + TParam, }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], array_lengthof(Elts)); + MDNode *Node = MDNode::get(VMContext, Elts); // Create a named metadata so that we do not lose this mdnode. NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.sp"); @@ -721,7 +755,7 @@ DINameSpace DIBuilder::createNameSpace(DIDescriptor Scope, StringRef Name, File, ConstantInt::get(Type::getInt32Ty(VMContext), LineNo) }; - return DINameSpace(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DINameSpace(MDNode::get(VMContext, Elts)); } DILexicalBlock DIBuilder::createLexicalBlock(DIDescriptor Scope, DIFile File, @@ -736,7 +770,7 @@ DILexicalBlock DIBuilder::createLexicalBlock(DIDescriptor Scope, DIFile File, File, ConstantInt::get(Type::getInt32Ty(VMContext), unique_id++) }; - return DILexicalBlock(MDNode::get(VMContext, &Elts[0], array_lengthof(Elts))); + return DILexicalBlock(MDNode::get(VMContext, Elts)); } /// insertDeclare - Insert a new llvm.dbg.declare intrinsic call. @@ -747,7 +781,7 @@ Instruction *DIBuilder::insertDeclare(Value *Storage, DIVariable VarInfo, if (!DeclareFn) DeclareFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_declare); - Value *Args[] = { MDNode::get(Storage->getContext(), &Storage, 1), VarInfo }; + Value *Args[] = { MDNode::get(Storage->getContext(), Storage), VarInfo }; return CallInst::Create(DeclareFn, Args, Args+2, "", InsertBefore); } @@ -759,7 +793,7 @@ Instruction *DIBuilder::insertDeclare(Value *Storage, DIVariable VarInfo, if (!DeclareFn) DeclareFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_declare); - Value *Args[] = { MDNode::get(Storage->getContext(), &Storage, 1), VarInfo }; + Value *Args[] = { MDNode::get(Storage->getContext(), Storage), VarInfo }; // If this block already has a terminator then insert this intrinsic // before the terminator. @@ -778,7 +812,7 @@ Instruction *DIBuilder::insertDbgValueIntrinsic(Value *V, uint64_t Offset, if (!ValueFn) ValueFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_value); - Value *Args[] = { MDNode::get(V->getContext(), &V, 1), + Value *Args[] = { MDNode::get(V->getContext(), V), ConstantInt::get(Type::getInt64Ty(V->getContext()), Offset), VarInfo }; return CallInst::Create(ValueFn, Args, Args+3, "", InsertBefore); @@ -793,7 +827,7 @@ Instruction *DIBuilder::insertDbgValueIntrinsic(Value *V, uint64_t Offset, if (!ValueFn) ValueFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_value); - Value *Args[] = { MDNode::get(V->getContext(), &V, 1), + Value *Args[] = { MDNode::get(V->getContext(), V), ConstantInt::get(Type::getInt64Ty(V->getContext()), Offset), VarInfo }; return CallInst::Create(ValueFn, Args, Args+3, "", InsertAtEnd); diff --git a/contrib/llvm/lib/Analysis/DebugInfo.cpp b/contrib/llvm/lib/Analysis/DebugInfo.cpp index 9db1456..67f8147 100644 --- a/contrib/llvm/lib/Analysis/DebugInfo.cpp +++ b/contrib/llvm/lib/Analysis/DebugInfo.cpp @@ -725,484 +725,6 @@ void DIVariable::dump() const { print(dbgs()); dbgs() << '\n'; } -//===----------------------------------------------------------------------===// -// DIFactory: Basic Helpers -//===----------------------------------------------------------------------===// - -DIFactory::DIFactory(Module &m) - : M(m), VMContext(M.getContext()), DeclareFn(0), ValueFn(0) {} - -Constant *DIFactory::GetTagConstant(unsigned TAG) { - assert((TAG & LLVMDebugVersionMask) == 0 && - "Tag too large for debug encoding!"); - return ConstantInt::get(Type::getInt32Ty(VMContext), TAG | LLVMDebugVersion); -} - -//===----------------------------------------------------------------------===// -// DIFactory: Primary Constructors -//===----------------------------------------------------------------------===// - -/// GetOrCreateArray - Create an descriptor for an array of descriptors. -/// This implicitly uniques the arrays created. -DIArray DIFactory::GetOrCreateArray(DIDescriptor *Tys, unsigned NumTys) { - if (NumTys == 0) { - Value *Null = llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)); - return DIArray(MDNode::get(VMContext, &Null, 1)); - } - - SmallVector<Value *, 16> Elts(Tys, Tys+NumTys); - return DIArray(MDNode::get(VMContext, Elts.data(), Elts.size())); -} - -/// GetOrCreateSubrange - Create a descriptor for a value range. This -/// implicitly uniques the values returned. -DISubrange DIFactory::GetOrCreateSubrange(int64_t Lo, int64_t Hi) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_subrange_type), - ConstantInt::get(Type::getInt64Ty(VMContext), Lo), - ConstantInt::get(Type::getInt64Ty(VMContext), Hi) - }; - - return DISubrange(MDNode::get(VMContext, &Elts[0], 3)); -} - -/// CreateUnspecifiedParameter - Create unspeicified type descriptor -/// for the subroutine type. -DIDescriptor DIFactory::CreateUnspecifiedParameter() { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_unspecified_parameters) - }; - return DIDescriptor(MDNode::get(VMContext, &Elts[0], 1)); -} - -/// CreateCompileUnit - Create a new descriptor for the specified compile -/// unit. Note that this does not unique compile units within the module. -DICompileUnit DIFactory::CreateCompileUnit(unsigned LangID, - StringRef Filename, - StringRef Directory, - StringRef Producer, - bool isMain, - bool isOptimized, - StringRef Flags, - unsigned RunTimeVer) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_compile_unit), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - ConstantInt::get(Type::getInt32Ty(VMContext), LangID), - MDString::get(VMContext, Filename), - MDString::get(VMContext, Directory), - MDString::get(VMContext, Producer), - ConstantInt::get(Type::getInt1Ty(VMContext), isMain), - ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), - MDString::get(VMContext, Flags), - ConstantInt::get(Type::getInt32Ty(VMContext), RunTimeVer) - }; - - return DICompileUnit(MDNode::get(VMContext, &Elts[0], 10)); -} - -/// CreateFile - Create a new descriptor for the specified file. -DIFile DIFactory::CreateFile(StringRef Filename, - StringRef Directory, - DICompileUnit CU) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_file_type), - MDString::get(VMContext, Filename), - MDString::get(VMContext, Directory), - CU - }; - - return DIFile(MDNode::get(VMContext, &Elts[0], 4)); -} - -/// CreateEnumerator - Create a single enumerator value. -DIEnumerator DIFactory::CreateEnumerator(StringRef Name, uint64_t Val){ - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_enumerator), - MDString::get(VMContext, Name), - ConstantInt::get(Type::getInt64Ty(VMContext), Val) - }; - return DIEnumerator(MDNode::get(VMContext, &Elts[0], 3)); -} - - -/// CreateBasicType - Create a basic type like int, float, etc. -DIBasicType DIFactory::CreateBasicType(DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - uint64_t SizeInBits, - uint64_t AlignInBits, - uint64_t OffsetInBits, unsigned Flags, - unsigned Encoding) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_base_type), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - ConstantInt::get(Type::getInt64Ty(VMContext), SizeInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), OffsetInBits), - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - ConstantInt::get(Type::getInt32Ty(VMContext), Encoding) - }; - return DIBasicType(MDNode::get(VMContext, &Elts[0], 10)); -} - - -/// CreateBasicType - Create a basic type like int, float, etc. -DIBasicType DIFactory::CreateBasicTypeEx(DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - Constant *SizeInBits, - Constant *AlignInBits, - Constant *OffsetInBits, unsigned Flags, - unsigned Encoding) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_base_type), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - SizeInBits, - AlignInBits, - OffsetInBits, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - ConstantInt::get(Type::getInt32Ty(VMContext), Encoding) - }; - return DIBasicType(MDNode::get(VMContext, &Elts[0], 10)); -} - -/// CreateArtificialType - Create a new DIType with "artificial" flag set. -DIType DIFactory::CreateArtificialType(DIType Ty) { - if (Ty.isArtificial()) - return Ty; - - SmallVector<Value *, 9> Elts; - MDNode *N = Ty; - assert (N && "Unexpected input DIType!"); - for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { - if (Value *V = N->getOperand(i)) - Elts.push_back(V); - else - Elts.push_back(Constant::getNullValue(Type::getInt32Ty(VMContext))); - } - - unsigned CurFlags = Ty.getFlags(); - CurFlags = CurFlags | DIType::FlagArtificial; - - // Flags are stored at this slot. - Elts[8] = ConstantInt::get(Type::getInt32Ty(VMContext), CurFlags); - - return DIType(MDNode::get(VMContext, Elts.data(), Elts.size())); -} - -/// CreateDerivedType - Create a derived type like const qualified type, -/// pointer, typedef, etc. -DIDerivedType DIFactory::CreateDerivedType(unsigned Tag, - DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - uint64_t SizeInBits, - uint64_t AlignInBits, - uint64_t OffsetInBits, - unsigned Flags, - DIType DerivedFrom) { - Value *Elts[] = { - GetTagConstant(Tag), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - ConstantInt::get(Type::getInt64Ty(VMContext), SizeInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), OffsetInBits), - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - DerivedFrom, - }; - return DIDerivedType(MDNode::get(VMContext, &Elts[0], 10)); -} - - -/// CreateDerivedType - Create a derived type like const qualified type, -/// pointer, typedef, etc. -DIDerivedType DIFactory::CreateDerivedTypeEx(unsigned Tag, - DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - Constant *SizeInBits, - Constant *AlignInBits, - Constant *OffsetInBits, - unsigned Flags, - DIType DerivedFrom) { - Value *Elts[] = { - GetTagConstant(Tag), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - SizeInBits, - AlignInBits, - OffsetInBits, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - DerivedFrom, - }; - return DIDerivedType(MDNode::get(VMContext, &Elts[0], 10)); -} - - -/// CreateCompositeType - Create a composite type like array, struct, etc. -DICompositeType DIFactory::CreateCompositeType(unsigned Tag, - DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - uint64_t SizeInBits, - uint64_t AlignInBits, - uint64_t OffsetInBits, - unsigned Flags, - DIType DerivedFrom, - DIArray Elements, - unsigned RuntimeLang, - MDNode *ContainingType) { - - Value *Elts[] = { - GetTagConstant(Tag), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - ConstantInt::get(Type::getInt64Ty(VMContext), SizeInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), OffsetInBits), - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - DerivedFrom, - Elements, - ConstantInt::get(Type::getInt32Ty(VMContext), RuntimeLang), - ContainingType - }; - - MDNode *Node = MDNode::get(VMContext, &Elts[0], 13); - // Create a named metadata so that we do not lose this enum info. - if (Tag == dwarf::DW_TAG_enumeration_type) { - NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.enum"); - NMD->addOperand(Node); - } - return DICompositeType(Node); -} - -/// CreateTemporaryType - Create a temporary forward-declared type. -DIType DIFactory::CreateTemporaryType() { - // Give the temporary MDNode a tag. It doesn't matter what tag we - // use here as long as DIType accepts it. - Value *Elts[] = { - GetTagConstant(DW_TAG_base_type) - }; - MDNode *Node = MDNode::getTemporary(VMContext, Elts, array_lengthof(Elts)); - return DIType(Node); -} - -/// CreateTemporaryType - Create a temporary forward-declared type. -DIType DIFactory::CreateTemporaryType(DIFile F) { - // Give the temporary MDNode a tag. It doesn't matter what tag we - // use here as long as DIType accepts it. - Value *Elts[] = { - GetTagConstant(DW_TAG_base_type), - F.getCompileUnit(), - NULL, - F - }; - MDNode *Node = MDNode::getTemporary(VMContext, Elts, array_lengthof(Elts)); - return DIType(Node); -} - -/// CreateCompositeType - Create a composite type like array, struct, etc. -DICompositeType DIFactory::CreateCompositeTypeEx(unsigned Tag, - DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - Constant *SizeInBits, - Constant *AlignInBits, - Constant *OffsetInBits, - unsigned Flags, - DIType DerivedFrom, - DIArray Elements, - unsigned RuntimeLang, - MDNode *ContainingType) { - Value *Elts[] = { - GetTagConstant(Tag), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - SizeInBits, - AlignInBits, - OffsetInBits, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - DerivedFrom, - Elements, - ConstantInt::get(Type::getInt32Ty(VMContext), RuntimeLang), - ContainingType - }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], 13); - // Create a named metadata so that we do not lose this enum info. - if (Tag == dwarf::DW_TAG_enumeration_type) { - NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.enum"); - NMD->addOperand(Node); - } - return DICompositeType(Node); -} - - -/// CreateSubprogram - Create a new descriptor for the specified subprogram. -/// See comments in DISubprogram for descriptions of these fields. This -/// method does not unique the generated descriptors. -DISubprogram DIFactory::CreateSubprogram(DIDescriptor Context, - StringRef Name, - StringRef DisplayName, - StringRef LinkageName, - DIFile F, - unsigned LineNo, DIType Ty, - bool isLocalToUnit, - bool isDefinition, - unsigned VK, unsigned VIndex, - DIType ContainingType, - unsigned Flags, - bool isOptimized, - Function *Fn) { - - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_subprogram), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - Context, - MDString::get(VMContext, Name), - MDString::get(VMContext, DisplayName), - MDString::get(VMContext, LinkageName), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - Ty, - ConstantInt::get(Type::getInt1Ty(VMContext), isLocalToUnit), - ConstantInt::get(Type::getInt1Ty(VMContext), isDefinition), - ConstantInt::get(Type::getInt32Ty(VMContext), (unsigned)VK), - ConstantInt::get(Type::getInt32Ty(VMContext), VIndex), - ContainingType, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), - Fn - }; - 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 -/// given declaration. -DISubprogram DIFactory::CreateSubprogramDefinition(DISubprogram &SPDeclaration){ - if (SPDeclaration.isDefinition()) - return DISubprogram(SPDeclaration); - - MDNode *DeclNode = SPDeclaration; - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_subprogram), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - DeclNode->getOperand(2), // Context - DeclNode->getOperand(3), // Name - DeclNode->getOperand(4), // DisplayName - DeclNode->getOperand(5), // LinkageName - DeclNode->getOperand(6), // CompileUnit - DeclNode->getOperand(7), // LineNo - DeclNode->getOperand(8), // Type - DeclNode->getOperand(9), // isLocalToUnit - ConstantInt::get(Type::getInt1Ty(VMContext), true), - DeclNode->getOperand(11), // Virtuality - DeclNode->getOperand(12), // VIndex - DeclNode->getOperand(13), // Containting Type - DeclNode->getOperand(14), // Flags - DeclNode->getOperand(15), // isOptimized - SPDeclaration.getFunction() - }; - 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. -DIGlobalVariable -DIFactory::CreateGlobalVariable(DIDescriptor Context, StringRef Name, - StringRef DisplayName, - StringRef LinkageName, - DIFile F, - unsigned LineNo, DIType Ty,bool isLocalToUnit, - bool isDefinition, llvm::GlobalVariable *Val) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_variable), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - Context, - MDString::get(VMContext, Name), - MDString::get(VMContext, DisplayName), - MDString::get(VMContext, LinkageName), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - Ty, - ConstantInt::get(Type::getInt1Ty(VMContext), isLocalToUnit), - ConstantInt::get(Type::getInt1Ty(VMContext), isDefinition), - Val - }; - - Value *const *Vs = &Elts[0]; - MDNode *Node = MDNode::get(VMContext,Vs, 12); - - // Create a named metadata so that we do not lose this mdnode. - NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.gv"); - NMD->addOperand(Node); - - return DIGlobalVariable(Node); -} - -/// CreateGlobalVariable - Create a new descriptor for the specified constant. -DIGlobalVariable -DIFactory::CreateGlobalVariable(DIDescriptor Context, StringRef Name, - StringRef DisplayName, - StringRef LinkageName, - DIFile F, - unsigned LineNo, DIType Ty,bool isLocalToUnit, - bool isDefinition, llvm::Constant *Val) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_variable), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - Context, - MDString::get(VMContext, Name), - MDString::get(VMContext, DisplayName), - MDString::get(VMContext, LinkageName), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - Ty, - ConstantInt::get(Type::getInt1Ty(VMContext), isLocalToUnit), - ConstantInt::get(Type::getInt1Ty(VMContext), isDefinition), - Val - }; - - Value *const *Vs = &Elts[0]; - MDNode *Node = MDNode::get(VMContext,Vs, 12); - - // Create a named metadata so that we do not lose this mdnode. - NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.gv"); - NMD->addOperand(Node); - - return DIGlobalVariable(Node); -} - /// fixupObjcLikeName - Replace contains special characters used /// in a typical Objective-C names with '.' in a given string. static void fixupObjcLikeName(std::string &Str) { @@ -1214,19 +736,6 @@ static void fixupObjcLikeName(std::string &Str) { } } -/// getOrInsertFnSpecificMDNode - Return a NameMDNode that is suitable -/// to hold function specific information. -NamedMDNode *llvm::getOrInsertFnSpecificMDNode(Module &M, StringRef FuncName) { - SmallString<32> Out; - if (FuncName.find('[') == StringRef::npos) - return M.getOrInsertNamedMetadata(Twine("llvm.dbg.lv.", FuncName) - .toStringRef(Out)); - std::string Name = FuncName; - fixupObjcLikeName(Name); - return M.getOrInsertNamedMetadata(Twine("llvm.dbg.lv.", Name) - .toStringRef(Out)); -} - /// getFnSpecificMDNode - Return a NameMDNode, if available, that is /// suitable to hold function specific information. NamedMDNode *llvm::getFnSpecificMDNode(const Module &M, StringRef FuncName) { @@ -1237,178 +746,18 @@ NamedMDNode *llvm::getFnSpecificMDNode(const Module &M, StringRef FuncName) { return M.getNamedMetadata(Twine("llvm.dbg.lv.", Name)); } -/// CreateVariable - Create a new descriptor for the specified variable. -DIVariable DIFactory::CreateVariable(unsigned Tag, DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNo, - DIType Ty, bool AlwaysPreserve, - unsigned Flags) { - Value *Elts[] = { - GetTagConstant(Tag), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - Ty, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags) - }; - MDNode *Node = MDNode::get(VMContext, &Elts[0], 7); - if (AlwaysPreserve) { - // 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. - 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 = getOrInsertFnSpecificMDNode(M, FName); - FnLocals->addOperand(Node); - } - return DIVariable(Node); -} - - -/// CreateComplexVariable - Create a new descriptor for the specified variable -/// which has a complex address expression for its address. -DIVariable DIFactory::CreateComplexVariable(unsigned Tag, DIDescriptor Context, - StringRef Name, DIFile F, - unsigned LineNo, - DIType Ty, Value *const *Addr, - unsigned NumAddr) { - SmallVector<Value *, 15> Elts; - Elts.push_back(GetTagConstant(Tag)); - Elts.push_back(Context); - Elts.push_back(MDString::get(VMContext, Name)); - Elts.push_back(F); - Elts.push_back(ConstantInt::get(Type::getInt32Ty(VMContext), LineNo)); - Elts.push_back(Ty); - Elts.append(Addr, Addr+NumAddr); - - return DIVariable(MDNode::get(VMContext, Elts.data(), Elts.size())); -} - - -/// CreateBlock - This creates a descriptor for a lexical block with the -/// specified parent VMContext. -DILexicalBlock DIFactory::CreateLexicalBlock(DIDescriptor Context, - DIFile F, unsigned LineNo, - unsigned Col) { - // Defeat MDNode uniqing for lexical blocks. - static unsigned int unique_id = 0; - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_lexical_block), - Context, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - ConstantInt::get(Type::getInt32Ty(VMContext), Col), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), unique_id++) - }; - return DILexicalBlock(MDNode::get(VMContext, &Elts[0], 6)); -} - -/// CreateNameSpace - This creates new descriptor for a namespace -/// with the specified parent context. -DINameSpace DIFactory::CreateNameSpace(DIDescriptor Context, StringRef Name, - DIFile F, - unsigned LineNo) { - Value *Elts[] = { - GetTagConstant(dwarf::DW_TAG_namespace), - Context, - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo) - }; - return DINameSpace(MDNode::get(VMContext, &Elts[0], 5)); -} - -/// CreateLocation - Creates a debug info location. -DILocation DIFactory::CreateLocation(unsigned LineNo, unsigned ColumnNo, - DIScope S, DILocation 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 -//===----------------------------------------------------------------------===// - -/// InsertDeclare - Insert a new llvm.dbg.declare intrinsic call. -Instruction *DIFactory::InsertDeclare(Value *Storage, DIVariable D, - Instruction *InsertBefore) { - assert(Storage && "no storage passed to dbg.declare"); - assert(D.Verify() && "empty DIVariable passed to dbg.declare"); - if (!DeclareFn) - DeclareFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_declare); - - Value *Args[] = { MDNode::get(Storage->getContext(), &Storage, 1), - D }; - return CallInst::Create(DeclareFn, Args, Args+2, "", InsertBefore); -} - -/// InsertDeclare - Insert a new llvm.dbg.declare intrinsic call. -Instruction *DIFactory::InsertDeclare(Value *Storage, DIVariable D, - BasicBlock *InsertAtEnd) { - assert(Storage && "no storage passed to dbg.declare"); - assert(D.Verify() && "invalid DIVariable passed to dbg.declare"); - if (!DeclareFn) - DeclareFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_declare); - - Value *Args[] = { MDNode::get(Storage->getContext(), &Storage, 1), - D }; - - // If this block already has a terminator then insert this intrinsic - // before the terminator. - if (TerminatorInst *T = InsertAtEnd->getTerminator()) - return CallInst::Create(DeclareFn, Args, Args+2, "", T); - else - return CallInst::Create(DeclareFn, Args, Args+2, "", InsertAtEnd);} - -/// InsertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call. -Instruction *DIFactory::InsertDbgValueIntrinsic(Value *V, uint64_t Offset, - DIVariable D, - Instruction *InsertBefore) { - assert(V && "no value passed to dbg.value"); - assert(D.Verify() && "invalid DIVariable passed to dbg.value"); - if (!ValueFn) - ValueFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_value); - - Value *Args[] = { MDNode::get(V->getContext(), &V, 1), - ConstantInt::get(Type::getInt64Ty(V->getContext()), Offset), - D }; - return CallInst::Create(ValueFn, Args, Args+3, "", InsertBefore); -} - -/// InsertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call. -Instruction *DIFactory::InsertDbgValueIntrinsic(Value *V, uint64_t Offset, - DIVariable D, - BasicBlock *InsertAtEnd) { - assert(V && "no value passed to dbg.value"); - assert(D.Verify() && "invalid DIVariable passed to dbg.value"); - if (!ValueFn) - ValueFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_value); - - Value *Args[] = { MDNode::get(V->getContext(), &V, 1), - ConstantInt::get(Type::getInt64Ty(V->getContext()), Offset), - D }; - return CallInst::Create(ValueFn, Args, Args+3, "", InsertAtEnd); -} - -// RecordType - Record DIType in a module such that it is not lost even if -// it is not referenced through debug info anchors. -void DIFactory::RecordType(DIType T) { - NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.ty"); - NMD->addOperand(T); +/// getOrInsertFnSpecificMDNode - Return a NameMDNode that is suitable +/// to hold function specific information. +NamedMDNode *llvm::getOrInsertFnSpecificMDNode(Module &M, StringRef FuncName) { + SmallString<32> Out; + if (FuncName.find('[') == StringRef::npos) + return M.getOrInsertNamedMetadata(Twine("llvm.dbg.lv.", FuncName) + .toStringRef(Out)); + + std::string Name = FuncName; + fixupObjcLikeName(Name); + return M.getOrInsertNamedMetadata(Twine("llvm.dbg.lv.", Name) + .toStringRef(Out)); } diff --git a/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp b/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp index 116aaf4..b226d66 100644 --- a/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp +++ b/contrib/llvm/lib/Analysis/IPA/GlobalsModRef.cpp @@ -602,7 +602,7 @@ void GlobalsModRef::addEscapingUse(Use &U) { // For the purposes of this analysis, it is conservatively correct to treat // a newly escaping value equivalently to a deleted one. We could perhaps // be more precise by processing the new use and attempting to update our - // saved analysis results to accomodate it. + // saved analysis results to accommodate it. deleteValue(U); AliasAnalysis::addEscapingUse(U); diff --git a/contrib/llvm/lib/Analysis/IVUsers.cpp b/contrib/llvm/lib/Analysis/IVUsers.cpp index c838218..2cda791 100644 --- a/contrib/llvm/lib/Analysis/IVUsers.cpp +++ b/contrib/llvm/lib/Analysis/IVUsers.cpp @@ -21,6 +21,7 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Target/TargetData.h" #include "llvm/Assembly/Writer.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Support/Debug.h" @@ -83,7 +84,10 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) { return false; // Void and FP expressions cannot be reduced. // LSR is not APInt clean, do not touch integers bigger than 64-bits. - if (SE->getTypeSizeInBits(I->getType()) > 64) + // Also avoid creating IVs of non-native types. For example, we don't want a + // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. + uint64_t Width = SE->getTypeSizeInBits(I->getType()); + if (Width > 64 || (TD && !TD->isLegalInteger(Width))) return false; if (!Processed.insert(I)) @@ -167,6 +171,7 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { LI = &getAnalysis<LoopInfo>(); DT = &getAnalysis<DominatorTree>(); SE = &getAnalysis<ScalarEvolution>(); + TD = getAnalysisIfAvailable<TargetData>(); // Find all uses of induction variables in this loop, and categorize // them by stride. Start by finding all of the PHI nodes in the header for diff --git a/contrib/llvm/lib/Analysis/InlineCost.cpp b/contrib/llvm/lib/Analysis/InlineCost.cpp index 47f91cf..a820ecf 100644 --- a/contrib/llvm/lib/Analysis/InlineCost.cpp +++ b/contrib/llvm/lib/Analysis/InlineCost.cpp @@ -501,7 +501,7 @@ InlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, return InlineCost::getAlways(); if (CalleeFI->Metrics.usesDynamicAlloca) { - // Get infomation about the caller. + // Get information about the caller. FunctionInfo &CallerFI = CachedFunctionInfo[Caller]; // If we haven't calculated this information yet, do so now. @@ -549,7 +549,7 @@ InlineCost InlineCostAnalyzer::getSpecializationCost(Function *Callee, int Cost = 0; - // Look at the orginal size of the callee. Each instruction counts as 5. + // Look at the original size of the callee. Each instruction counts as 5. Cost += CalleeFI->Metrics.NumInsts * InlineConstants::InstrCost; // Offset that with the amount of code that can be constant-folded diff --git a/contrib/llvm/lib/Analysis/InstructionSimplify.cpp b/contrib/llvm/lib/Analysis/InstructionSimplify.cpp index 982dacb..9d6d339 100644 --- a/contrib/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/contrib/llvm/lib/Analysis/InstructionSimplify.cpp @@ -18,11 +18,13 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "instsimplify" +#include "llvm/Operator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Support/ConstantRange.h" #include "llvm/Support/PatternMatch.h" #include "llvm/Support/ValueHandle.h" #include "llvm/Target/TargetData.h" @@ -899,6 +901,111 @@ Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD, return ::SimplifyFDivInst(Op0, Op1, TD, DT, RecursionLimit); } +/// SimplifyRem - Given operands for an SRem or URem, see if we can +/// fold the result. If not, this returns null. +static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, + const TargetData *TD, const DominatorTree *DT, + unsigned MaxRecurse) { + if (Constant *C0 = dyn_cast<Constant>(Op0)) { + if (Constant *C1 = dyn_cast<Constant>(Op1)) { + Constant *Ops[] = { C0, C1 }; + return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); + } + } + + bool isSigned = Opcode == Instruction::SRem; + + // X % undef -> undef + if (match(Op1, m_Undef())) + return Op1; + + // undef % X -> 0 + if (match(Op0, m_Undef())) + return Constant::getNullValue(Op0->getType()); + + // 0 % X -> 0, we don't need to preserve faults! + if (match(Op0, m_Zero())) + return Op0; + + // X % 0 -> undef, we don't need to preserve faults! + if (match(Op1, m_Zero())) + return UndefValue::get(Op0->getType()); + + // X % 1 -> 0 + if (match(Op1, m_One())) + return Constant::getNullValue(Op0->getType()); + + if (Op0->getType()->isIntegerTy(1)) + // It can't be remainder by zero, hence it must be remainder by one. + return Constant::getNullValue(Op0->getType()); + + // X % X -> 0 + if (Op0 == Op1) + return Constant::getNullValue(Op0->getType()); + + // If the operation is with the result of a select instruction, check whether + // operating on either branch of the select always yields the same value. + if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) + if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse)) + return V; + + // If the operation is with the result of a phi instruction, check whether + // operating on all incoming values of the phi always yields the same value. + if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) + if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse)) + return V; + + return 0; +} + +/// SimplifySRemInst - Given operands for an SRem, see if we can +/// fold the result. If not, this returns null. +static Value *SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT, unsigned MaxRecurse) { + if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, TD, DT, MaxRecurse)) + return V; + + return 0; +} + +Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT) { + return ::SimplifySRemInst(Op0, Op1, TD, DT, RecursionLimit); +} + +/// SimplifyURemInst - Given operands for a URem, see if we can +/// fold the result. If not, this returns null. +static Value *SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT, unsigned MaxRecurse) { + if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, TD, DT, MaxRecurse)) + return V; + + return 0; +} + +Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT) { + return ::SimplifyURemInst(Op0, Op1, TD, DT, RecursionLimit); +} + +static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *, + const DominatorTree *, unsigned) { + // undef % X -> undef (the undef could be a snan). + if (match(Op0, m_Undef())) + return Op0; + + // X % undef -> undef + if (match(Op1, m_Undef())) + return Op1; + + return 0; +} + +Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT) { + return ::SimplifyFRemInst(Op0, Op1, TD, DT, RecursionLimit); +} + /// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can /// fold the result. If not, this returns null. static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, @@ -1343,7 +1450,7 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, // the compare, and if only one of them is then we moved it to RHS already. if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || isa<ConstantPointerNull>(RHS))) - // We already know that LHS != LHS. + // We already know that LHS != RHS. return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); // If we are comparing with zero then try hard since this is a common case. @@ -1399,40 +1506,66 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, // See if we are doing a comparison with a constant integer. if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { - switch (Pred) { - default: break; - case ICmpInst::ICMP_UGT: - if (CI->isMaxValue(false)) // A >u MAX -> FALSE - return ConstantInt::getFalse(CI->getContext()); - break; - case ICmpInst::ICMP_UGE: - if (CI->isMinValue(false)) // A >=u MIN -> TRUE - return ConstantInt::getTrue(CI->getContext()); - break; - case ICmpInst::ICMP_ULT: - if (CI->isMinValue(false)) // A <u MIN -> FALSE - return ConstantInt::getFalse(CI->getContext()); - break; - case ICmpInst::ICMP_ULE: - if (CI->isMaxValue(false)) // A <=u MAX -> TRUE - return ConstantInt::getTrue(CI->getContext()); - break; - case ICmpInst::ICMP_SGT: - if (CI->isMaxValue(true)) // A >s MAX -> FALSE - return ConstantInt::getFalse(CI->getContext()); - break; - case ICmpInst::ICMP_SGE: - if (CI->isMinValue(true)) // A >=s MIN -> TRUE - return ConstantInt::getTrue(CI->getContext()); - break; - case ICmpInst::ICMP_SLT: - if (CI->isMinValue(true)) // A <s MIN -> FALSE - return ConstantInt::getFalse(CI->getContext()); - break; - case ICmpInst::ICMP_SLE: - if (CI->isMaxValue(true)) // A <=s MAX -> TRUE - return ConstantInt::getTrue(CI->getContext()); - break; + // Rule out tautological comparisons (eg., ult 0 or uge 0). + ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue()); + if (RHS_CR.isEmptySet()) + return ConstantInt::getFalse(CI->getContext()); + if (RHS_CR.isFullSet()) + return ConstantInt::getTrue(CI->getContext()); + + // Many binary operators with constant RHS have easy to compute constant + // range. Use them to check whether the comparison is a tautology. + uint32_t Width = CI->getBitWidth(); + APInt Lower = APInt(Width, 0); + APInt Upper = APInt(Width, 0); + ConstantInt *CI2; + if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) { + // 'urem x, CI2' produces [0, CI2). + Upper = CI2->getValue(); + } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) { + // 'srem x, CI2' produces (-|CI2|, |CI2|). + Upper = CI2->getValue().abs(); + Lower = (-Upper) + 1; + } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) { + // 'udiv x, CI2' produces [0, UINT_MAX / CI2]. + APInt NegOne = APInt::getAllOnesValue(Width); + if (!CI2->isZero()) + Upper = NegOne.udiv(CI2->getValue()) + 1; + } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) { + // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2]. + APInt IntMin = APInt::getSignedMinValue(Width); + APInt IntMax = APInt::getSignedMaxValue(Width); + APInt Val = CI2->getValue().abs(); + if (!Val.isMinValue()) { + Lower = IntMin.sdiv(Val); + Upper = IntMax.sdiv(Val) + 1; + } + } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) { + // 'lshr x, CI2' produces [0, UINT_MAX >> CI2]. + APInt NegOne = APInt::getAllOnesValue(Width); + if (CI2->getValue().ult(Width)) + Upper = NegOne.lshr(CI2->getValue()) + 1; + } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { + // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. + APInt IntMin = APInt::getSignedMinValue(Width); + APInt IntMax = APInt::getSignedMaxValue(Width); + if (CI2->getValue().ult(Width)) { + Lower = IntMin.ashr(CI2->getValue()); + Upper = IntMax.ashr(CI2->getValue()) + 1; + } + } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { + // 'or x, CI2' produces [CI2, UINT_MAX]. + Lower = CI2->getValue(); + } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { + // 'and x, CI2' produces [0, CI2]. + Upper = CI2->getValue() + 1; + } + if (Lower != Upper) { + ConstantRange LHS_CR = ConstantRange(Lower, Upper); + if (RHS_CR.contains(LHS_CR)) + return ConstantInt::getTrue(RHS->getContext()); + if (RHS_CR.inverse().contains(LHS_CR)) + return ConstantInt::getFalse(RHS->getContext()); } } @@ -1644,6 +1777,93 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } } + if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { + bool KnownNonNegative, KnownNegative; + switch (Pred) { + default: + break; + case ICmpInst::ICMP_SGT: + case ICmpInst::ICMP_SGE: + ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD); + if (!KnownNonNegative) + break; + // fall-through + case ICmpInst::ICMP_EQ: + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_UGE: + return ConstantInt::getFalse(RHS->getContext()); + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_SLE: + ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD); + if (!KnownNonNegative) + break; + // fall-through + case ICmpInst::ICMP_NE: + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_ULE: + return ConstantInt::getTrue(RHS->getContext()); + } + } + if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { + bool KnownNonNegative, KnownNegative; + switch (Pred) { + default: + break; + case ICmpInst::ICMP_SGT: + case ICmpInst::ICMP_SGE: + ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD); + if (!KnownNonNegative) + break; + // fall-through + case ICmpInst::ICMP_NE: + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_UGE: + return ConstantInt::getTrue(RHS->getContext()); + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_SLE: + ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD); + if (!KnownNonNegative) + break; + // fall-through + case ICmpInst::ICMP_EQ: + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_ULE: + return ConstantInt::getFalse(RHS->getContext()); + } + } + + if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && + LBO->getOperand(1) == RBO->getOperand(1)) { + switch (LBO->getOpcode()) { + default: break; + case Instruction::UDiv: + case Instruction::LShr: + if (ICmpInst::isSigned(Pred)) + break; + // fall-through + case Instruction::SDiv: + case Instruction::AShr: + if (!LBO->isExact() && !RBO->isExact()) + break; + if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), + RBO->getOperand(0), TD, DT, MaxRecurse-1)) + return V; + break; + case Instruction::Shl: { + bool NUW = LBO->hasNoUnsignedWrap() && LBO->hasNoUnsignedWrap(); + bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); + if (!NUW && !NSW) + break; + if (!NSW && ICmpInst::isSigned(Pred)) + break; + if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), + RBO->getOperand(0), TD, DT, MaxRecurse-1)) + return V; + break; + } + } + } + // If the comparison is with the result of a select instruction, check whether // comparing with either branch of the select always yields the same value. if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) @@ -1879,6 +2099,9 @@ static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, DT, MaxRecurse); case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, DT, MaxRecurse); case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, TD, DT, MaxRecurse); + case Instruction::SRem: return SimplifySRemInst(LHS, RHS, TD, DT, MaxRecurse); + case Instruction::URem: return SimplifyURemInst(LHS, RHS, TD, DT, MaxRecurse); + case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, TD, DT, MaxRecurse); case Instruction::Shl: return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, TD, DT, MaxRecurse); @@ -1973,6 +2196,15 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, case Instruction::FDiv: Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, DT); break; + case Instruction::SRem: + Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), TD, DT); + break; + case Instruction::URem: + Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), TD, DT); + break; + case Instruction::FRem: + Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), TD, DT); + break; case Instruction::Shl: Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), cast<BinaryOperator>(I)->hasNoSignedWrap(), diff --git a/contrib/llvm/lib/Analysis/LazyValueInfo.cpp b/contrib/llvm/lib/Analysis/LazyValueInfo.cpp index 9e7da6c..d5f0b5c 100644 --- a/contrib/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/contrib/llvm/lib/Analysis/LazyValueInfo.cpp @@ -29,7 +29,6 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" #include <map> -#include <set> #include <stack> using namespace llvm; @@ -268,6 +267,8 @@ public: } // end anonymous namespace. namespace llvm { +raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) + LLVM_ATTRIBUTE_USED; raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { if (Val.isUndefined()) return OS << "undefined"; diff --git a/contrib/llvm/lib/Analysis/Lint.cpp b/contrib/llvm/lib/Analysis/Lint.cpp index fc7edc0..f130f30 100644 --- a/contrib/llvm/lib/Analysis/Lint.cpp +++ b/contrib/llvm/lib/Analysis/Lint.cpp @@ -606,7 +606,7 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, Type::getInt64Ty(V->getContext()))) return findValueImpl(CE->getOperand(0), OffsetOk, Visited); } else if (CE->getOpcode() == Instruction::ExtractValue) { - const SmallVector<unsigned, 4> &Indices = CE->getIndices(); + ArrayRef<unsigned> Indices = CE->getIndices(); if (Value *W = FindInsertedValue(CE->getOperand(0), Indices.begin(), Indices.end())) diff --git a/contrib/llvm/lib/Analysis/LiveValues.cpp b/contrib/llvm/lib/Analysis/LiveValues.cpp deleted file mode 100644 index a0e6034..0000000 --- a/contrib/llvm/lib/Analysis/LiveValues.cpp +++ /dev/null @@ -1,200 +0,0 @@ -//===- LiveValues.cpp - Liveness information for LLVM IR Values. ----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the implementation for the LLVM IR Value liveness -// analysis pass. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/LiveValues.h" -#include "llvm/Instructions.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/LoopInfo.h" -using namespace llvm; - -namespace llvm { - FunctionPass *createLiveValuesPass() { return new LiveValues(); } -} - -char LiveValues::ID = 0; -INITIALIZE_PASS_BEGIN(LiveValues, "live-values", - "Value Liveness Analysis", false, true) -INITIALIZE_PASS_DEPENDENCY(DominatorTree) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) -INITIALIZE_PASS_END(LiveValues, "live-values", - "Value Liveness Analysis", false, true) - -LiveValues::LiveValues() : FunctionPass(ID) { - initializeLiveValuesPass(*PassRegistry::getPassRegistry()); -} - -void LiveValues::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<DominatorTree>(); - AU.addRequired<LoopInfo>(); - AU.setPreservesAll(); -} - -bool LiveValues::runOnFunction(Function &F) { - DT = &getAnalysis<DominatorTree>(); - LI = &getAnalysis<LoopInfo>(); - - // This pass' values are computed lazily, so there's nothing to do here. - - return false; -} - -void LiveValues::releaseMemory() { - Memos.clear(); -} - -/// isUsedInBlock - Test if the given value is used in the given block. -/// -bool LiveValues::isUsedInBlock(const Value *V, const BasicBlock *BB) { - Memo &M = getMemo(V); - return M.Used.count(BB); -} - -/// isLiveThroughBlock - Test if the given value is known to be -/// live-through the given block, meaning that the block is properly -/// dominated by the value's definition, and there exists a block -/// reachable from it that contains a use. This uses a conservative -/// approximation that errs on the side of returning false. -/// -bool LiveValues::isLiveThroughBlock(const Value *V, - const BasicBlock *BB) { - Memo &M = getMemo(V); - return M.LiveThrough.count(BB); -} - -/// isKilledInBlock - Test if the given value is known to be killed in -/// the given block, meaning that the block contains a use of the value, -/// and no blocks reachable from the block contain a use. This uses a -/// conservative approximation that errs on the side of returning false. -/// -bool LiveValues::isKilledInBlock(const Value *V, const BasicBlock *BB) { - Memo &M = getMemo(V); - return M.Killed.count(BB); -} - -/// getMemo - Retrieve an existing Memo for the given value if one -/// is available, otherwise compute a new one. -/// -LiveValues::Memo &LiveValues::getMemo(const Value *V) { - DenseMap<const Value *, Memo>::iterator I = Memos.find(V); - if (I != Memos.end()) - return I->second; - return compute(V); -} - -/// getImmediateDominator - A handy utility for the specific DominatorTree -/// query that we need here. -/// -static const BasicBlock *getImmediateDominator(const BasicBlock *BB, - const DominatorTree *DT) { - DomTreeNode *Node = DT->getNode(const_cast<BasicBlock *>(BB))->getIDom(); - return Node ? Node->getBlock() : 0; -} - -/// compute - Compute a new Memo for the given value. -/// -LiveValues::Memo &LiveValues::compute(const Value *V) { - Memo &M = Memos[V]; - - // Determine the block containing the definition. - const BasicBlock *DefBB; - // Instructions define values with meaningful live ranges. - if (const Instruction *I = dyn_cast<Instruction>(V)) - DefBB = I->getParent(); - // Arguments can be analyzed as values defined in the entry block. - else if (const Argument *A = dyn_cast<Argument>(V)) - DefBB = &A->getParent()->getEntryBlock(); - // Constants and other things aren't meaningful here, so just - // return having computed an empty Memo so that we don't come - // here again. The assumption here is that client code won't - // be asking about such values very often. - else - return M; - - // Determine if the value is defined inside a loop. This is used - // to track whether the value is ever used outside the loop, so - // it'll be set to null if the value is either not defined in a - // loop or used outside the loop in which it is defined. - const Loop *L = LI->getLoopFor(DefBB); - - // Track whether the value is used anywhere outside of the block - // in which it is defined. - bool LiveOutOfDefBB = false; - - // Examine each use of the value. - for (Value::const_use_iterator I = V->use_begin(), E = V->use_end(); - I != E; ++I) { - const User *U = *I; - const BasicBlock *UseBB = cast<Instruction>(U)->getParent(); - - // Note the block in which this use occurs. - M.Used.insert(UseBB); - - // If the use block doesn't have successors, the value can be - // considered killed. - if (succ_begin(UseBB) == succ_end(UseBB)) - M.Killed.insert(UseBB); - - // Observe whether the value is used outside of the loop in which - // it is defined. Switch to an enclosing loop if necessary. - for (; L; L = L->getParentLoop()) - if (L->contains(UseBB)) - break; - - // Search for live-through blocks. - const BasicBlock *BB; - if (const PHINode *PHI = dyn_cast<PHINode>(U)) { - // For PHI nodes, start the search at the incoming block paired with the - // incoming value, which must be dominated by the definition. - unsigned Num = PHI->getIncomingValueNumForOperand(I.getOperandNo()); - BB = PHI->getIncomingBlock(Num); - - // A PHI-node use means the value is live-out of it's defining block - // even if that block also contains the only use. - LiveOutOfDefBB = true; - } else { - // Otherwise just start the search at the use. - BB = UseBB; - - // Note if the use is outside the defining block. - LiveOutOfDefBB |= UseBB != DefBB; - } - - // Climb the immediate dominator tree from the use to the definition - // and mark all intermediate blocks as live-through. - for (; BB != DefBB; BB = getImmediateDominator(BB, DT)) { - if (BB != UseBB && !M.LiveThrough.insert(BB)) - break; - } - } - - // If the value is defined inside a loop and is not live outside - // the loop, then each exit block of the loop in which the value - // is used is a kill block. - if (L) { - SmallVector<BasicBlock *, 4> ExitingBlocks; - L->getExitingBlocks(ExitingBlocks); - for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { - const BasicBlock *ExitingBlock = ExitingBlocks[i]; - if (M.Used.count(ExitingBlock)) - M.Killed.insert(ExitingBlock); - } - } - - // If the value was never used outside the block in which it was - // defined, it's killed in that block. - if (!LiveOutOfDefBB) - M.Killed.insert(DefBB); - - return M; -} diff --git a/contrib/llvm/lib/Analysis/Loads.cpp b/contrib/llvm/lib/Analysis/Loads.cpp index 2ea27fb..ab34fd6 100644 --- a/contrib/llvm/lib/Analysis/Loads.cpp +++ b/contrib/llvm/lib/Analysis/Loads.cpp @@ -17,6 +17,7 @@ #include "llvm/GlobalAlias.h" #include "llvm/GlobalVariable.h" #include "llvm/IntrinsicInst.h" +#include "llvm/Operator.h" using namespace llvm; /// AreEquivalentAddressValues - Test if A and B will obviously have the same diff --git a/contrib/llvm/lib/Analysis/LoopPass.cpp b/contrib/llvm/lib/Analysis/LoopPass.cpp index 8e1a7bf..10e3f29 100644 --- a/contrib/llvm/lib/Analysis/LoopPass.cpp +++ b/contrib/llvm/lib/Analysis/LoopPass.cpp @@ -14,8 +14,10 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopPass.h" +#include "llvm/DebugInfoProbe.h" #include "llvm/Assembly/PrintModulePass.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ManagedStatic.h" #include "llvm/Support/Timer.h" using namespace llvm; @@ -52,6 +54,20 @@ char PrintLoopPass::ID = 0; } //===----------------------------------------------------------------------===// +// DebugInfoProbe + +static DebugInfoProbeInfo *TheDebugProbe; +static void createDebugInfoProbe() { + if (TheDebugProbe) return; + + // Constructed the first time this is called. This guarantees that the + // object will be constructed, if -enable-debug-info-probe is set, + // before static globals, thus it will be destroyed before them. + static ManagedStatic<DebugInfoProbeInfo> DIP; + TheDebugProbe = &*DIP; +} + +//===----------------------------------------------------------------------===// // LPPassManager // @@ -223,6 +239,7 @@ void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { bool LPPassManager::runOnFunction(Function &F) { LI = &getAnalysis<LoopInfo>(); bool Changed = false; + createDebugInfoProbe(); // Collect inherited analysis from Module level pass manager. populateInheritedAnalysis(TPM->activeStack); @@ -254,19 +271,21 @@ bool LPPassManager::runOnFunction(Function &F) { // Run all passes on the current Loop. for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { LoopPass *P = getContainedPass(Index); - dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, CurrentLoop->getHeader()->getName()); dumpRequiredSet(P); initializeAnalysisImpl(P); - + if (TheDebugProbe) + TheDebugProbe->initialize(P, F); { PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader()); TimeRegion PassTimer(getPassTimer(P)); Changed |= P->runOnLoop(CurrentLoop, *this); } + if (TheDebugProbe) + TheDebugProbe->finalize(P, F); if (Changed) dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, diff --git a/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp b/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp index 1ab18ca..769c68c 100644 --- a/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp +++ b/contrib/llvm/lib/Analysis/MemoryBuiltins.cpp @@ -35,7 +35,13 @@ static bool isMallocCall(const CallInst *CI) { return false; Function *Callee = CI->getCalledFunction(); - if (Callee == 0 || !Callee->isDeclaration() || Callee->getName() != "malloc") + if (Callee == 0 || !Callee->isDeclaration()) + return false; + if (Callee->getName() != "malloc" && + Callee->getName() != "_Znwj" && // operator new(unsigned int) + Callee->getName() != "_Znwm" && // operator new(unsigned long) + Callee->getName() != "_Znaj" && // operator new[](unsigned int) + Callee->getName() != "_Znam") // operator new[](unsigned long) return false; // Check malloc prototype. @@ -189,7 +195,12 @@ const CallInst *llvm::isFreeCall(const Value *I) { if (!CI) return 0; Function *Callee = CI->getCalledFunction(); - if (Callee == 0 || !Callee->isDeclaration() || Callee->getName() != "free") + if (Callee == 0 || !Callee->isDeclaration()) + return 0; + + if (Callee->getName() != "free" && + Callee->getName() != "_ZdlPv" && // operator delete(void*) + Callee->getName() != "_ZdaPv") // operator delete[](void*) return 0; // Check free prototype. diff --git a/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp index 35043bd..ce7fab6 100644 --- a/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -16,6 +16,7 @@ #define DEBUG_TYPE "memdep" #include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/Function.h" @@ -221,6 +222,96 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, return MemDepResult::getClobber(ScanIt); } +/// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that +/// would fully overlap MemLoc if done as a wider legal integer load. +/// +/// MemLocBase, MemLocOffset are lazily computed here the first time the +/// base/offs of memloc is needed. +static bool +isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, + const Value *&MemLocBase, + int64_t &MemLocOffs, + const LoadInst *LI, + const TargetData *TD) { + // If we have no target data, we can't do this. + if (TD == 0) return false; + + // If we haven't already computed the base/offset of MemLoc, do so now. + if (MemLocBase == 0) + MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, *TD); + + unsigned Size = MemoryDependenceAnalysis:: + getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size, + LI, *TD); + return Size != 0; +} + +/// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that +/// looks at a memory location for a load (specified by MemLocBase, Offs, +/// and Size) and compares it against a load. If the specified load could +/// be safely widened to a larger integer load that is 1) still efficient, +/// 2) safe for the target, and 3) would provide the specified memory +/// location value, then this function returns the size in bytes of the +/// load width to use. If not, this returns zero. +unsigned MemoryDependenceAnalysis:: +getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, + unsigned MemLocSize, const LoadInst *LI, + const TargetData &TD) { + // We can only extend non-volatile integer loads. + if (!isa<IntegerType>(LI->getType()) || LI->isVolatile()) return 0; + + // Get the base of this load. + int64_t LIOffs = 0; + const Value *LIBase = + GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, TD); + + // If the two pointers are not based on the same pointer, we can't tell that + // they are related. + if (LIBase != MemLocBase) return 0; + + // Okay, the two values are based on the same pointer, but returned as + // no-alias. This happens when we have things like two byte loads at "P+1" + // and "P+3". Check to see if increasing the size of the "LI" load up to its + // alignment (or the largest native integer type) will allow us to load all + // the bits required by MemLoc. + + // If MemLoc is before LI, then no widening of LI will help us out. + if (MemLocOffs < LIOffs) return 0; + + // Get the alignment of the load in bytes. We assume that it is safe to load + // any legal integer up to this size without a problem. For example, if we're + // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can + // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it + // to i16. + unsigned LoadAlign = LI->getAlignment(); + + int64_t MemLocEnd = MemLocOffs+MemLocSize; + + // If no amount of rounding up will let MemLoc fit into LI, then bail out. + if (LIOffs+LoadAlign < MemLocEnd) return 0; + + // This is the size of the load to try. Start with the next larger power of + // two. + unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U; + NewLoadByteSize = NextPowerOf2(NewLoadByteSize); + + while (1) { + // If this load size is bigger than our known alignment or would not fit + // into a native integer register, then we fail. + if (NewLoadByteSize > LoadAlign || + !TD.fitsInLegalInteger(NewLoadByteSize*8)) + return 0; + + // If a load of this width would include all of MemLoc, then we succeed. + if (LIOffs+NewLoadByteSize >= MemLocEnd) + return NewLoadByteSize; + + NewLoadByteSize <<= 1; + } + + return 0; +} + /// getPointerDependencyFrom - Return the instruction on which a memory /// location depends. If isLoad is true, this routine ignores may-aliases with /// read-only operations. If isLoad is false, this routine ignores may-aliases @@ -229,58 +320,31 @@ MemDepResult MemoryDependenceAnalysis:: getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB) { - Value *InvariantTag = 0; - + const Value *MemLocBase = 0; + int64_t MemLocOffset = 0; + // Walk backwards through the basic block, looking for dependencies. while (ScanIt != BB->begin()) { Instruction *Inst = --ScanIt; - // If we're in an invariant region, no dependencies can be found before - // we pass an invariant-begin marker. - if (InvariantTag == Inst) { - InvariantTag = 0; - continue; - } - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { // Debug intrinsics don't (and can't) cause dependences. if (isa<DbgInfoIntrinsic>(II)) continue; - // If we pass an invariant-end marker, then we've just entered an - // invariant region and can start ignoring dependencies. - if (II->getIntrinsicID() == Intrinsic::invariant_end) { - // FIXME: This only considers queries directly on the invariant-tagged - // 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(AliasAnalysis::Location(II->getArgOperand(2)), MemLoc); - if (R == AliasAnalysis::MustAlias) - InvariantTag = II->getArgOperand(0); - - continue; - } - // If we reach a lifetime begin or end marker, then the query ends here // because the value is undefined. if (II->getIntrinsicID() == Intrinsic::lifetime_start) { // FIXME: This only considers queries directly on the invariant-tagged // 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(AliasAnalysis::Location(II->getArgOperand(1)), MemLoc); - if (R == AliasAnalysis::MustAlias) + // be nice to handle that at some point (the right approach is to use + // GetPointerBaseWithConstantOffset). + if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)), + MemLoc)) return MemDepResult::getDef(II); continue; } } - // If we're querying on a load and we're in an invariant region, we're done - // at this point. Nothing a load depends on can live in an invariant region. - // - // FIXME: this will prevent us from returning load/load must-aliases, so GVN - // won't remove redundant loads. - if (isLoad && InvariantTag) continue; - // Values depend on loads if the pointers are must aliased. This means that // a load depends on another must aliased load from the same value. if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { @@ -288,27 +352,51 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // If we found a pointer, check if it could be the same as our pointer. AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); - if (R == AliasAnalysis::NoAlias) - continue; - // May-alias loads don't depend on each other without a dependence. - if (isLoad && R != AliasAnalysis::MustAlias) + if (isLoad) { + if (R == AliasAnalysis::NoAlias) { + // If this is an over-aligned integer load (for example, + // "load i8* %P, align 4") see if it would obviously overlap with the + // queried location if widened to a larger load (e.g. if the queried + // location is 1 byte at P+1). If so, return it as a load/load + // clobber result, allowing the client to decide to widen the load if + // it wants to. + if (const IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) + if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() && + isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase, + MemLocOffset, LI, TD)) + return MemDepResult::getClobber(Inst); + + continue; + } + + // Must aliased loads are defs of each other. + if (R == AliasAnalysis::MustAlias) + return MemDepResult::getDef(Inst); + + // If we have a partial alias, then return this as a clobber for the + // client to handle. + if (R == AliasAnalysis::PartialAlias) + return MemDepResult::getClobber(Inst); + + // Random may-alias loads don't depend on each other without a + // dependence. + continue; + } + + // Stores don't depend on other no-aliased accesses. + if (R == AliasAnalysis::NoAlias) continue; // Stores don't alias loads from read-only memory. - if (!isLoad && AA->pointsToConstantMemory(LoadLoc)) + if (AA->pointsToConstantMemory(LoadLoc)) continue; - // Stores depend on may and must aliased loads, loads depend on must-alias - // loads. + // Stores depend on may/must aliased loads. return MemDepResult::getDef(Inst); } if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { - // There can't be stores to the value we care about inside an - // invariant region. - if (InvariantTag) continue; - // If alias analysis can tell that this store is guaranteed to not modify // the query pointer, ignore it. Use getModRefInfo to handle cases where // the query pointer points to constant memory etc. @@ -341,8 +429,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, (isa<CallInst>(Inst) && extractMallocCall(Inst))) { const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD); - if (AccessPtr == Inst || - AA->alias(Inst, 1, AccessPtr, 1) == AliasAnalysis::MustAlias) + if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr)) return MemDepResult::getDef(Inst); continue; } @@ -353,9 +440,6 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // If the call has no effect on the queried pointer, just ignore it. continue; case AliasAnalysis::Mod: - // If we're in an invariant region, we can ignore calls that ONLY - // modify the pointer. - if (InvariantTag) continue; return MemDepResult::getClobber(Inst); case AliasAnalysis::Ref: // If the call is known to never store to the pointer, and if this is a diff --git a/contrib/llvm/lib/Analysis/PHITransAddr.cpp b/contrib/llvm/lib/Analysis/PHITransAddr.cpp index 93da5a4..70dcd0d 100644 --- a/contrib/llvm/lib/Analysis/PHITransAddr.cpp +++ b/contrib/llvm/lib/Analysis/PHITransAddr.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/PHITransAddr.h" +#include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" diff --git a/contrib/llvm/lib/Analysis/PathNumbering.cpp b/contrib/llvm/lib/Analysis/PathNumbering.cpp index 5d3f6bb..7c584da 100644 --- a/contrib/llvm/lib/Analysis/PathNumbering.cpp +++ b/contrib/llvm/lib/Analysis/PathNumbering.cpp @@ -38,13 +38,10 @@ #include "llvm/Support/TypeBuilder.h" #include "llvm/Support/raw_ostream.h" -#include <map> #include <queue> -#include <set> #include <stack> #include <string> #include <utility> -#include <vector> #include <sstream> using namespace llvm; @@ -286,7 +283,7 @@ void BallLarusDag::calculatePathNumbers() { BallLarusEdge* exitEdge = addEdge(node, getExit(), 0); exitEdge->setType(BallLarusEdge::SPLITEDGE_PHONY); - // Counters to handle the possibilty of a multi-graph + // Counters to handle the possibility of a multi-graph BasicBlock* oldTarget = 0; unsigned duplicateNumber = 0; diff --git a/contrib/llvm/lib/Analysis/PathProfileVerifier.cpp b/contrib/llvm/lib/Analysis/PathProfileVerifier.cpp index c549773..0ae734e 100644 --- a/contrib/llvm/lib/Analysis/PathProfileVerifier.cpp +++ b/contrib/llvm/lib/Analysis/PathProfileVerifier.cpp @@ -124,7 +124,7 @@ bool PathProfileVerifier::runOnModule (Module &M) { ProfilePathEdgeVector* pev = currentPath->getPathEdges(); DEBUG(dbgs () << "path #" << currentPath->getNumber() << ": " << currentPath->getCount() << "\n"); - // setup the entry edge (normally path profiling doens't care about this) + // setup the entry edge (normally path profiling doesn't care about this) if (currentPath->getFirstBlockInPath() == &F->getEntryBlock()) edgeArray[arrayMap[0][currentPath->getFirstBlockInPath()][0]] += currentPath->getCount(); diff --git a/contrib/llvm/lib/Analysis/PostDominators.cpp b/contrib/llvm/lib/Analysis/PostDominators.cpp index 3f0deab..6ed2729 100644 --- a/contrib/llvm/lib/Analysis/PostDominators.cpp +++ b/contrib/llvm/lib/Analysis/PostDominators.cpp @@ -28,7 +28,6 @@ using namespace llvm; //===----------------------------------------------------------------------===// char PostDominatorTree::ID = 0; -char PostDominanceFrontier::ID = 0; INITIALIZE_PASS(PostDominatorTree, "postdomtree", "Post-Dominator Tree Construction", true, true) @@ -50,53 +49,3 @@ FunctionPass* llvm::createPostDomTree() { return new PostDominatorTree(); } -//===----------------------------------------------------------------------===// -// PostDominanceFrontier Implementation -//===----------------------------------------------------------------------===// - -INITIALIZE_PASS_BEGIN(PostDominanceFrontier, "postdomfrontier", - "Post-Dominance Frontier Construction", true, true) -INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) -INITIALIZE_PASS_END(PostDominanceFrontier, "postdomfrontier", - "Post-Dominance Frontier Construction", true, true) - -const DominanceFrontier::DomSetType & -PostDominanceFrontier::calculate(const PostDominatorTree &DT, - const DomTreeNode *Node) { - // Loop over CFG successors to calculate DFlocal[Node] - BasicBlock *BB = Node->getBlock(); - DomSetType &S = Frontiers[BB]; // The new set to fill in... - if (getRoots().empty()) return S; - - 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[P]; - if (SINode && SINode->getIDom() != Node) - S.insert(P); - } - - // At this point, S is DFlocal. Now we union in DFup's of our children... - // Loop through and visit the nodes that Node immediately dominates (Node's - // children in the IDomTree) - // - for (DomTreeNode::const_iterator - NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { - DomTreeNode *IDominee = *NI; - const DomSetType &ChildDF = calculate(DT, IDominee); - - DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); - for (; CDFI != CDFE; ++CDFI) { - if (!DT.properlyDominates(Node, DT[*CDFI])) - S.insert(*CDFI); - } - } - - return S; -} - -FunctionPass* llvm::createPostDomFrontier() { - return new PostDominanceFrontier(); -} diff --git a/contrib/llvm/lib/Analysis/ProfileEstimatorPass.cpp b/contrib/llvm/lib/Analysis/ProfileEstimatorPass.cpp index 667ee1c..b594e2b 100644 --- a/contrib/llvm/lib/Analysis/ProfileEstimatorPass.cpp +++ b/contrib/llvm/lib/Analysis/ProfileEstimatorPass.cpp @@ -140,7 +140,7 @@ void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { // loop, thus the edge is a backedge, continue and do not check if the // value is valid. if (BBisHeader && BBLoop->contains(*bbi)) { - printEdgeError(edge, "but is backedge, continueing"); + printEdgeError(edge, "but is backedge, continuing"); continue; } // If the edges value is missing (and this is no loop header, and this is diff --git a/contrib/llvm/lib/Analysis/ProfileInfo.cpp b/contrib/llvm/lib/Analysis/ProfileInfo.cpp index 36f211e..173de2c 100644 --- a/contrib/llvm/lib/Analysis/ProfileInfo.cpp +++ b/contrib/llvm/lib/Analysis/ProfileInfo.cpp @@ -309,9 +309,9 @@ void ProfileInfoT<Function,BasicBlock>:: removeEdge(oldedge); } -/// Replaces all occurences of RmBB in the ProfilingInfo with DestBB. +/// Replaces all occurrences of RmBB in the ProfilingInfo with DestBB. /// This checks all edges of the function the blocks reside in and replaces the -/// occurences of RmBB with DestBB. +/// occurrences of RmBB with DestBB. template<> void ProfileInfoT<Function,BasicBlock>:: replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB) { @@ -812,7 +812,7 @@ void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) { } if (iw < 0) continue; - // Check the recieving end of the path if it can handle the flow. + // Check the receiving end of the path if it can handle the flow. double ow = getExecutionCount(Dest); Processed.clear(); for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); diff --git a/contrib/llvm/lib/Analysis/ProfileInfoLoader.cpp b/contrib/llvm/lib/Analysis/ProfileInfoLoader.cpp index 25481b2..eaa38da 100644 --- a/contrib/llvm/lib/Analysis/ProfileInfoLoader.cpp +++ b/contrib/llvm/lib/Analysis/ProfileInfoLoader.cpp @@ -19,7 +19,6 @@ #include "llvm/Support/raw_ostream.h" #include <cstdio> #include <cstdlib> -#include <map> using namespace llvm; // ByteSwap - Byteswap 'Var' if 'Really' is true. diff --git a/contrib/llvm/lib/Analysis/RegionInfo.cpp b/contrib/llvm/lib/Analysis/RegionInfo.cpp index e2f6a8b..52753cb 100644 --- a/contrib/llvm/lib/Analysis/RegionInfo.cpp +++ b/contrib/llvm/lib/Analysis/RegionInfo.cpp @@ -41,16 +41,15 @@ VerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo), STATISTIC(numRegions, "The # of regions"); STATISTIC(numSimpleRegions, "The # of simple regions"); -//===----------------------------------------------------------------------===// -/// PrintStyle - Print region in difference ways. -enum PrintStyle { PrintNone, PrintBB, PrintRN }; - -static cl::opt<enum PrintStyle> printStyle("print-region-style", cl::Hidden, +static cl::opt<enum Region::PrintStyle> printStyle("print-region-style", + cl::Hidden, cl::desc("style of printing regions"), cl::values( - clEnumValN(PrintNone, "none", "print no details"), - clEnumValN(PrintBB, "bb", "print regions in detail with block_iterator"), - clEnumValN(PrintRN, "rn", "print regions in detail with element_iterator"), + clEnumValN(Region::PrintNone, "none", "print no details"), + clEnumValN(Region::PrintBB, "bb", + "print regions in detail with block_iterator"), + clEnumValN(Region::PrintRN, "rn", + "print regions in detail with element_iterator"), clEnumValEnd)); //===----------------------------------------------------------------------===// /// Region Implementation @@ -413,7 +412,8 @@ Region *Region::getExpandedRegion() const { return new Region(getEntry(), R->getExit(), RI, DT); } -void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const { +void Region::print(raw_ostream &OS, bool print_tree, unsigned level, + enum PrintStyle Style) const { if (print_tree) OS.indent(level*2) << "[" << level << "] " << getNameStr(); else @@ -422,14 +422,14 @@ void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const { OS << "\n"; - if (printStyle != PrintNone) { + if (Style != PrintNone) { OS.indent(level*2) << "{\n"; OS.indent(level*2 + 2); - if (printStyle == PrintBB) { + if (Style == PrintBB) { for (const_block_iterator I = block_begin(), E = block_end(); I!=E; ++I) OS << **I << ", "; // TODO: remove the last "," - } else if (printStyle == PrintRN) { + } else if (Style == PrintRN) { for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I) OS << **I << ", "; // TODO: remove the last ", } @@ -439,14 +439,14 @@ void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const { if (print_tree) for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) - (*RI)->print(OS, print_tree, level+1); + (*RI)->print(OS, print_tree, level+1, Style); - if (printStyle != PrintNone) + if (Style != PrintNone) OS.indent(level*2) << "} \n"; } void Region::dump() const { - print(dbgs(), true, getDepth()); + print(dbgs(), true, getDepth(), printStyle.getValue()); } void Region::clearNodeCache() { @@ -714,7 +714,7 @@ void RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const { void RegionInfo::print(raw_ostream &OS, const Module *) const { OS << "Region tree:\n"; - TopLevelRegion->print(OS, true, 0); + TopLevelRegion->print(OS, true, 0, printStyle.getValue()); OS << "End region tree\n"; } diff --git a/contrib/llvm/lib/Analysis/RegionPrinter.cpp b/contrib/llvm/lib/Analysis/RegionPrinter.cpp index 0cf0f90..a1730b0 100644 --- a/contrib/llvm/lib/Analysis/RegionPrinter.cpp +++ b/contrib/llvm/lib/Analysis/RegionPrinter.cpp @@ -70,6 +70,32 @@ struct DOTGraphTraits<RegionInfo*> : public DOTGraphTraits<RegionNode*> { G->getTopLevelRegion()); } + std::string getEdgeAttributes(RegionNode *srcNode, + GraphTraits<RegionInfo*>::ChildIteratorType CI, RegionInfo *RI) { + + RegionNode *destNode = *CI; + + if (srcNode->isSubRegion() || destNode->isSubRegion()) + return ""; + + // In case of a backedge, do not use it to define the layout of the nodes. + BasicBlock *srcBB = srcNode->getNodeAs<BasicBlock>(); + BasicBlock *destBB = destNode->getNodeAs<BasicBlock>(); + + Region *R = RI->getRegionFor(destBB); + + while (R && R->getParent()) + if (R->getParent()->getEntry() == destBB) + R = R->getParent(); + else + break; + + if (R->getEntry() == destBB && R->contains(srcBB)) + return "constraint=false"; + + return ""; + } + // Print the cluster of the subregions. This groups the single basic blocks // and adds a different background color for each group. static void printRegionCluster(const Region *R, GraphWriter<RegionInfo*> &GW, diff --git a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp index 62244cc..bab4619 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp @@ -157,10 +157,13 @@ void SCEV::print(raw_ostream &OS) const { for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i) OS << ",+," << *AR->getOperand(i); OS << "}<"; - if (AR->hasNoUnsignedWrap()) + if (AR->getNoWrapFlags(FlagNUW)) OS << "nuw><"; - if (AR->hasNoSignedWrap()) + if (AR->getNoWrapFlags(FlagNSW)) OS << "nsw><"; + if (AR->getNoWrapFlags(FlagNW) && + !AR->getNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW))) + OS << "nw><"; WriteAsOperand(OS, AR->getLoop()->getHeader(), /*PrintType=*/false); OS << ">"; return; @@ -203,7 +206,7 @@ void SCEV::print(raw_ostream &OS) const { OS << "alignof(" << *AllocTy << ")"; return; } - + const Type *CTy; Constant *FieldNo; if (U->isOffsetOf(CTy, FieldNo)) { @@ -212,7 +215,7 @@ void SCEV::print(raw_ostream &OS) const { OS << ")"; return; } - + // Otherwise just print it normally. WriteAsOperand(OS, U->getValue(), false); return; @@ -830,7 +833,7 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Operands.push_back(S); } if (!hasTrunc) - return getAddExpr(Operands, false, false); + return getAddExpr(Operands); UniqueSCEVs.FindNodeOrInsertPos(ID, IP); // Mutates IP, returns NULL. } @@ -845,7 +848,7 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Operands.push_back(S); } if (!hasTrunc) - return getMulExpr(Operands, false, false); + return getMulExpr(Operands); UniqueSCEVs.FindNodeOrInsertPos(ID, IP); // Mutates IP, returns NULL. } @@ -854,7 +857,7 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, SmallVector<const SCEV *, 4> Operands; for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty)); - return getAddRecExpr(Operands, AddRec->getLoop()); + return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap); } // As a special case, fold trunc(undef) to undef. We don't want to @@ -926,10 +929,10 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, // If we have special knowledge that this addrec won't overflow, // we don't need to do any further analysis. - if (AR->hasNoUnsignedWrap()) + if (AR->getNoWrapFlags(SCEV::FlagNUW)) return getAddRecExpr(getZeroExtendExpr(Start, Ty), getZeroExtendExpr(Step, Ty), - L); + L, AR->getNoWrapFlags()); // Check whether the backedge-taken count is SCEVCouldNotCompute. // Note that this serves two purposes: It filters out loops that are @@ -959,12 +962,14 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, getAddExpr(getZeroExtendExpr(Start, WideTy), getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), getZeroExtendExpr(Step, WideTy))); - if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) + if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) { + // Cache knowledge of AR NUW, which is propagated to this AddRec. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW); // Return the expression with the addrec on the outside. return getAddRecExpr(getZeroExtendExpr(Start, Ty), getZeroExtendExpr(Step, Ty), - L); - + L, AR->getNoWrapFlags()); + } // Similar to above, only this time treat the step value as signed. // This covers loops that count down. const SCEV *SMul = getMulExpr(CastedMaxBECount, Step); @@ -973,11 +978,15 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, getAddExpr(getZeroExtendExpr(Start, WideTy), getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), getSignExtendExpr(Step, WideTy))); - if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) + if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) { + // Cache knowledge of AR NW, which is propagated to this AddRec. + // Negative step causes unsigned wrap, but it still can't self-wrap. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW); // Return the expression with the addrec on the outside. return getAddRecExpr(getZeroExtendExpr(Start, Ty), getSignExtendExpr(Step, Ty), - L); + L, AR->getNoWrapFlags()); + } } // If the backedge is guarded by a comparison with the pre-inc value @@ -990,22 +999,29 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) || (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, - AR->getPostIncExpr(*this), N))) + AR->getPostIncExpr(*this), N))) { + // Cache knowledge of AR NUW, which is propagated to this AddRec. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW); // Return the expression with the addrec on the outside. return getAddRecExpr(getZeroExtendExpr(Start, Ty), getZeroExtendExpr(Step, Ty), - L); + L, AR->getNoWrapFlags()); + } } else if (isKnownNegative(Step)) { const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) - getSignedRange(Step).getSignedMin()); if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) || (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, - AR->getPostIncExpr(*this), N))) + AR->getPostIncExpr(*this), N))) { + // Cache knowledge of AR NW, which is propagated to this AddRec. + // Negative step causes unsigned wrap, but it still can't self-wrap. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW); // Return the expression with the addrec on the outside. return getAddRecExpr(getZeroExtendExpr(Start, Ty), getSignExtendExpr(Step, Ty), - L); + L, AR->getNoWrapFlags()); + } } } } @@ -1080,10 +1096,10 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, // If we have special knowledge that this addrec won't overflow, // we don't need to do any further analysis. - if (AR->hasNoSignedWrap()) + if (AR->getNoWrapFlags(SCEV::FlagNSW)) return getAddRecExpr(getSignExtendExpr(Start, Ty), getSignExtendExpr(Step, Ty), - L); + L, SCEV::FlagNSW); // Check whether the backedge-taken count is SCEVCouldNotCompute. // Note that this serves two purposes: It filters out loops that are @@ -1113,12 +1129,14 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, getAddExpr(getSignExtendExpr(Start, WideTy), getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), getSignExtendExpr(Step, WideTy))); - if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) + if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) { + // Cache knowledge of AR NSW, which is propagated to this AddRec. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW); // Return the expression with the addrec on the outside. return getAddRecExpr(getSignExtendExpr(Start, Ty), getSignExtendExpr(Step, Ty), - L); - + L, AR->getNoWrapFlags()); + } // Similar to above, only this time treat the step value as unsigned. // This covers loops that count up with an unsigned step. const SCEV *UMul = getMulExpr(CastedMaxBECount, Step); @@ -1127,11 +1145,14 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, getAddExpr(getSignExtendExpr(Start, WideTy), getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), getZeroExtendExpr(Step, WideTy))); - if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) + if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) { + // Cache knowledge of AR NSW, which is propagated to this AddRec. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW); // Return the expression with the addrec on the outside. return getAddRecExpr(getSignExtendExpr(Start, Ty), getZeroExtendExpr(Step, Ty), - L); + L, AR->getNoWrapFlags()); + } } // If the backedge is guarded by a comparison with the pre-inc value @@ -1144,22 +1165,28 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, AR, N) || (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, - AR->getPostIncExpr(*this), N))) + AR->getPostIncExpr(*this), N))) { + // Cache knowledge of AR NSW, which is propagated to this AddRec. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW); // Return the expression with the addrec on the outside. return getAddRecExpr(getSignExtendExpr(Start, Ty), getSignExtendExpr(Step, Ty), - L); + L, AR->getNoWrapFlags()); + } } else if (isKnownNegative(Step)) { const SCEV *N = getConstant(APInt::getSignedMaxValue(BitWidth) - getSignedRange(Step).getSignedMin()); if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, AR, N) || (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, - AR->getPostIncExpr(*this), N))) + AR->getPostIncExpr(*this), N))) { + // Cache knowledge of AR NSW, which is propagated to this AddRec. + const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW); // Return the expression with the addrec on the outside. return getAddRecExpr(getSignExtendExpr(Start, Ty), getSignExtendExpr(Step, Ty), - L); + L, AR->getNoWrapFlags()); + } } } } @@ -1213,7 +1240,7 @@ const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end(); I != E; ++I) Ops.push_back(getAnyExtendExpr(*I, Ty)); - return getAddRecExpr(Ops, AR->getLoop()); + return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW); } // As a special case, fold anyext(undef) to undef. We don't want to @@ -1334,7 +1361,9 @@ namespace { /// getAddExpr - Get a canonical add expression, or something simpler if /// possible. const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, - bool HasNUW, bool HasNSW) { + SCEV::NoWrapFlags Flags) { + assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) && + "only nuw or nsw allowed"); assert(!Ops.empty() && "Cannot get empty add!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG @@ -1344,8 +1373,11 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, "SCEVAddExpr operand types don't match!"); #endif - // If HasNSW is true and all the operands are non-negative, infer HasNUW. - if (!HasNUW && HasNSW) { + // If FlagNSW is true and all the operands are non-negative, infer FlagNUW. + // And vice-versa. + int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW; + SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask); + if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) { bool All = true; for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(), E = Ops.end(); I != E; ++I) @@ -1353,7 +1385,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, All = false; break; } - if (All) HasNUW = true; + if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask); } // Sort by complexity, this groups all similar expression types together. @@ -1404,7 +1436,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, FoundMatch = true; } if (FoundMatch) - return getAddExpr(Ops, HasNUW, HasNSW); + return getAddExpr(Ops, Flags); // Check for truncates. If all the operands are truncated from the same // type, see if factoring out the truncate would permit the result to be @@ -1454,7 +1486,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, } if (Ok) { // Evaluate the expression in the larger type. - const SCEV *Fold = getAddExpr(LargeOps, HasNUW, HasNSW); + const SCEV *Fold = getAddExpr(LargeOps, Flags); // If it folds to something simple, use it. Otherwise, don't. if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold)) return getTruncateExpr(Fold, DstType); @@ -1625,9 +1657,9 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, // 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()); + // Always propagate NW. + Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW)); + const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags); // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -1668,7 +1700,8 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, } Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; } - Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop); + // Step size has changed, so we cannot guarantee no self-wraparound. + Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap); return getAddExpr(Ops); } @@ -1692,15 +1725,16 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, O, Ops.size()); UniqueSCEVs.InsertNode(S, IP); } - if (HasNUW) S->setHasNoUnsignedWrap(true); - if (HasNSW) S->setHasNoSignedWrap(true); + S->setNoWrapFlags(Flags); return S; } /// getMulExpr - Get a canonical multiply expression, or something simpler if /// possible. const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, - bool HasNUW, bool HasNSW) { + SCEV::NoWrapFlags Flags) { + assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) && + "only nuw or nsw allowed"); assert(!Ops.empty() && "Cannot get empty mul!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG @@ -1710,8 +1744,11 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, "SCEVMulExpr operand types don't match!"); #endif - // If HasNSW is true and all the operands are non-negative, infer HasNUW. - if (!HasNUW && HasNSW) { + // If FlagNSW is true and all the operands are non-negative, infer FlagNUW. + // And vice-versa. + int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW; + SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask); + if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) { bool All = true; for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(), E = Ops.end(); I != E; ++I) @@ -1719,7 +1756,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, All = false; break; } - if (All) HasNUW = true; + if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask); } // Sort by complexity, this groups all similar expression types together. @@ -1759,12 +1796,12 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, } else if (Ops[0]->isAllOnesValue()) { // If we have a mul by -1 of an add, try distributing the -1 among the // add operands. - if (Ops.size() == 2) + if (Ops.size() == 2) { if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) { SmallVector<const SCEV *, 4> NewOps; bool AnyFolded = false; - for (SCEVAddRecExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); - I != E; ++I) { + for (SCEVAddRecExpr::op_iterator I = Add->op_begin(), + E = Add->op_end(); I != E; ++I) { const SCEV *Mul = getMulExpr(Ops[0], *I); if (!isa<SCEVMulExpr>(Mul)) AnyFolded = true; NewOps.push_back(Mul); @@ -1772,6 +1809,18 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, if (AnyFolded) return getAddExpr(NewOps); } + else if (const SCEVAddRecExpr * + AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) { + // Negation preserves a recurrence's no self-wrap property. + SmallVector<const SCEV *, 4> Operands; + for (SCEVAddRecExpr::op_iterator I = AddRec->op_begin(), + E = AddRec->op_end(); I != E; ++I) { + Operands.push_back(getMulExpr(Ops[0], *I)); + } + return getAddRecExpr(Operands, AddRec->getLoop(), + AddRec->getNoWrapFlags(SCEV::FlagNW)); + } + } } if (Ops.size() == 1) @@ -1831,9 +1880,11 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, // 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, AddRecLoop, - HasNUW && AddRec->hasNoUnsignedWrap(), - HasNSW && AddRec->hasNoSignedWrap()); + // + // No self-wrap cannot be guaranteed after changing the step size, but + // will be inferred if either NUW or NSW is true. + Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW)); + const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags); // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -1869,7 +1920,8 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, getMulExpr(G, B), getMulExpr(B, D)); const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep, - F->getLoop()); + F->getLoop(), + SCEV::FlagAnyWrap); if (Ops.size() == 2) return NewAddRec; Ops[Idx] = AddRec = cast<SCEVAddRecExpr>(NewAddRec); Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; @@ -1897,8 +1949,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, O, Ops.size()); UniqueSCEVs.InsertNode(S, IP); } - if (HasNUW) S->setHasNoUnsignedWrap(true); - if (HasNSW) S->setHasNoSignedWrap(true); + S->setNoWrapFlags(Flags); return S; } @@ -1938,11 +1989,12 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, getZeroExtendExpr(AR, ExtTy) == getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), getZeroExtendExpr(Step, ExtTy), - AR->getLoop())) { + AR->getLoop(), SCEV::FlagAnyWrap)) { SmallVector<const SCEV *, 4> Operands; for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i) Operands.push_back(getUDivExpr(AR->getOperand(i), RHS)); - return getAddRecExpr(Operands, AR->getLoop()); + return getAddRecExpr(Operands, AR->getLoop(), + SCEV::FlagNW); } // (A*B)/C --> A*(B/C) if safe and B/C can be folded. if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) { @@ -1963,7 +2015,7 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, } } // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded. - if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) { + if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(LHS)) { SmallVector<const SCEV *, 4> Operands; for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy)); @@ -2006,27 +2058,26 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, /// getAddRecExpr - Get an add recurrence expression for the specified loop. /// Simplify the expression as much as possible. -const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, - const SCEV *Step, const Loop *L, - bool HasNUW, bool HasNSW) { +const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step, + const Loop *L, + SCEV::NoWrapFlags Flags) { SmallVector<const SCEV *, 4> Operands; Operands.push_back(Start); if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step)) if (StepChrec->getLoop() == L) { Operands.append(StepChrec->op_begin(), StepChrec->op_end()); - return getAddRecExpr(Operands, L); + return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW)); } Operands.push_back(Step); - return getAddRecExpr(Operands, L, HasNUW, HasNSW); + return getAddRecExpr(Operands, L, Flags); } /// getAddRecExpr - Get an add recurrence expression for the specified loop. /// Simplify the expression as much as possible. const SCEV * ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, - const Loop *L, - bool HasNUW, bool HasNSW) { + const Loop *L, SCEV::NoWrapFlags Flags) { if (Operands.size() == 1) return Operands[0]; #ifndef NDEBUG const Type *ETy = getEffectiveSCEVType(Operands[0]->getType()); @@ -2040,7 +2091,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, if (Operands.back()->isZero()) { Operands.pop_back(); - return getAddRecExpr(Operands, L, HasNUW, HasNSW); // {X,+,0} --> X + return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X } // It's tempting to want to call getMaxBackedgeTakenCount count here and @@ -2049,8 +2100,11 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, // meaningful BE count at this point (and if we don't, we'd be stuck // with a SCEVCouldNotCompute as the cached BE count). - // If HasNSW is true and all the operands are non-negative, infer HasNUW. - if (!HasNUW && HasNSW) { + // If FlagNSW is true and all the operands are non-negative, infer FlagNUW. + // And vice-versa. + int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW; + SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask); + if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) { bool All = true; for (SmallVectorImpl<const SCEV *>::const_iterator I = Operands.begin(), E = Operands.end(); I != E; ++I) @@ -2058,7 +2112,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, All = false; break; } - if (All) HasNUW = true; + if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask); } // Canonicalize nested AddRecs in by nesting them in order of loop depth. @@ -2081,16 +2135,29 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, break; } if (AllInvariant) { - NestedOperands[0] = getAddRecExpr(Operands, L); + // Create a recurrence for the outer loop with the same step size. + // + // The outer recurrence keeps its NW flag but only keeps NUW/NSW if the + // inner recurrence has the same property. + SCEV::NoWrapFlags OuterFlags = + maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags()); + + NestedOperands[0] = getAddRecExpr(Operands, L, OuterFlags); AllInvariant = true; for (unsigned i = 0, e = NestedOperands.size(); i != e; ++i) if (!isLoopInvariant(NestedOperands[i], NestedLoop)) { AllInvariant = false; break; } - if (AllInvariant) + if (AllInvariant) { // Ok, both add recurrences are valid after the transformation. - return getAddRecExpr(NestedOperands, NestedLoop, HasNUW, HasNSW); + // + // The inner recurrence keeps its NW flag but only keeps NUW/NSW if + // the outer recurrence has the same property. + SCEV::NoWrapFlags InnerFlags = + maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags); + return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags); + } } // Reset Operands to its original state. Operands[0] = NestedAR; @@ -2114,8 +2181,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, O, Operands.size(), L); UniqueSCEVs.InsertNode(S, IP); } - if (HasNUW) S->setHasNoUnsignedWrap(true); - if (HasNSW) S->setHasNoSignedWrap(true); + S->setNoWrapFlags(Flags); return S; } @@ -2510,17 +2576,17 @@ const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { return getMinusSCEV(AllOnes, V); } -/// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1, -/// and thus the HasNUW and HasNSW bits apply to the resultant add, not -/// whether the sub would have overflowed. +/// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1. const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, - bool HasNUW, bool HasNSW) { + SCEV::NoWrapFlags Flags) { + assert(!maskFlags(Flags, SCEV::FlagNUW) && "subtraction does not have NUW"); + // Fast path: X - X --> 0. if (LHS == RHS) return getConstant(LHS->getType(), 0); // X - Y --> X + -Y - return getAddExpr(LHS, getNegativeSCEV(RHS), HasNUW, HasNSW); + return getAddExpr(LHS, getNegativeSCEV(RHS), Flags); } /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the @@ -2652,6 +2718,36 @@ const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, return getUMinExpr(PromotedLHS, PromotedRHS); } +/// getPointerBase - Transitively follow the chain of pointer-type operands +/// until reaching a SCEV that does not have a single pointer operand. This +/// returns a SCEVUnknown pointer for well-formed pointer-type expressions, +/// but corner cases do exist. +const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) { + // A pointer operand may evaluate to a nonpointer expression, such as null. + if (!V->getType()->isPointerTy()) + return V; + + if (const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(V)) { + return getPointerBase(Cast->getOperand()); + } + else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) { + const SCEV *PtrOp = 0; + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); + I != E; ++I) { + if ((*I)->getType()->isPointerTy()) { + // Cannot find the base of an expression with multiple pointer operands. + if (PtrOp) + return V; + PtrOp = *I; + } + } + if (!PtrOp) + return V; + return getPointerBase(PtrOp); + } + return V; +} + /// PushDefUseChildren - Push users of the given Instruction /// onto the given Worklist. static void @@ -2773,44 +2869,34 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { if (isLoopInvariant(Accum, L) || (isa<SCEVAddRecExpr>(Accum) && cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) { - bool HasNUW = false; - bool HasNSW = false; + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; // If the increment doesn't overflow, then neither the addrec nor // the post-increment will overflow. if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) { if (OBO->hasNoUnsignedWrap()) - HasNUW = true; + Flags = setFlags(Flags, SCEV::FlagNUW); if (OBO->hasNoSignedWrap()) - HasNSW = true; - } else if (const GEPOperator *GEP = - dyn_cast<GEPOperator>(BEValueV)) { - // If the increment is a GEP, then we know it won't perform a - // signed overflow, because the address space cannot be - // wrapped around. - // - // NOTE: This isn't strictly true, because you could have an - // object straddling the 2G address boundary in a 32-bit address - // space (for example). We really want to model this as a "has - // no signed/unsigned wrap" where the base pointer is treated as - // unsigned and the increment is known to not have signed - // wrapping. - // - // This is a highly theoretical concern though, and this is good - // enough for all cases we know of at this point. :) - // - HasNSW |= GEP->isInBounds(); + Flags = setFlags(Flags, SCEV::FlagNSW); + } else if (const GEPOperator *GEP = + dyn_cast<GEPOperator>(BEValueV)) { + // If the increment is an inbounds GEP, then we know the address + // space cannot be wrapped around. We cannot make any guarantee + // about signed or unsigned overflow because pointers are + // unsigned but we may have a negative index from the base + // pointer. + if (GEP->isInBounds()) + Flags = setFlags(Flags, SCEV::FlagNW); } const SCEV *StartVal = getSCEV(StartValueV); - const SCEV *PHISCEV = - getAddRecExpr(StartVal, Accum, L, HasNUW, HasNSW); + const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); // Since the no-wrap flags are on the increment, they apply to the // post-incremented value as well. if (isLoopInvariant(Accum, L)) (void)getAddRecExpr(getAddExpr(StartVal, Accum), - Accum, L, HasNUW, HasNSW); + Accum, L, Flags); // Okay, for the entire analysis of this edge we assumed the PHI // to be symbolic. We now need to go back and purge all of the @@ -2834,8 +2920,11 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // initial step of the addrec evolution. if (StartVal == getMinusSCEV(AddRec->getOperand(0), AddRec->getOperand(1))) { + // FIXME: For constant StartVal, we should be able to infer + // no-wrap flags. const SCEV *PHISCEV = - getAddRecExpr(StartVal, AddRec->getOperand(1), L); + getAddRecExpr(StartVal, AddRec->getOperand(1), L, + SCEV::FlagAnyWrap); // Okay, for the entire analysis of this edge we assumed the PHI // to be symbolic. We now need to go back and purge all of the @@ -2899,8 +2988,9 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy); // Multiply the index by the element size to compute the element offset. - const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize, /*NUW*/ false, - /*NSW*/ isInBounds); + const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize, + isInBounds ? SCEV::FlagNSW : + SCEV::FlagAnyWrap); // Add the element offset to the running total offset. TotalOffset = getAddExpr(TotalOffset, LocalOffset); @@ -2911,8 +3001,8 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { const SCEV *BaseS = getSCEV(Base); // Add the total offset from all the GEP indices to the base. - return getAddExpr(BaseS, TotalOffset, /*NUW*/ false, - /*NSW*/ isInBounds); + return getAddExpr(BaseS, TotalOffset, + isInBounds ? SCEV::FlagNSW : SCEV::FlagAnyWrap); } /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is @@ -3074,7 +3164,7 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { // If there's no unsigned wrap, the value will never be less than its // initial value. - if (AddRec->hasNoUnsignedWrap()) + if (AddRec->getNoWrapFlags(SCEV::FlagNUW)) if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart())) if (!C->getValue()->isZero()) ConservativeResult = @@ -3216,7 +3306,7 @@ ScalarEvolution::getSignedRange(const SCEV *S) { if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { // If there's no signed wrap, and all the operands have the same sign or // zero, the value won't ever change sign. - if (AddRec->hasNoSignedWrap()) { + if (AddRec->getNoWrapFlags(SCEV::FlagNSW)) { bool AllNonNeg = true; bool AllNonPos = true; for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { @@ -3349,7 +3439,7 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { SmallVector<const SCEV *, 4> MulOps; MulOps.push_back(getSCEV(U->getOperand(1))); for (Value *Op = U->getOperand(0); - Op->getValueID() == Instruction::Mul + Value::InstructionVal; + Op->getValueID() == Instruction::Mul + Value::InstructionVal; Op = U->getOperand(0)) { U = cast<Operator>(Op); MulOps.push_back(getSCEV(U->getOperand(1))); @@ -3411,10 +3501,8 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // transfer the no-wrap flags, since an or won't introduce a wrap. if (const SCEVAddRecExpr *NewAR = dyn_cast<SCEVAddRecExpr>(S)) { const SCEVAddRecExpr *OldAR = cast<SCEVAddRecExpr>(LHS); - if (OldAR->hasNoUnsignedWrap()) - const_cast<SCEVAddRecExpr *>(NewAR)->setHasNoUnsignedWrap(true); - if (OldAR->hasNoSignedWrap()) - const_cast<SCEVAddRecExpr *>(NewAR)->setHasNoSignedWrap(true); + const_cast<SCEVAddRecExpr *>(NewAR)->setNoWrapFlags( + OldAR->getNoWrapFlags()); } return S; } @@ -3700,19 +3788,20 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { if (!Pair.second) return Pair.first->second; - BackedgeTakenInfo BECount = ComputeBackedgeTakenCount(L); - if (BECount.Exact != getCouldNotCompute()) { - assert(isLoopInvariant(BECount.Exact, L) && - isLoopInvariant(BECount.Max, L) && + BackedgeTakenInfo Result = getCouldNotCompute(); + BackedgeTakenInfo Computed = ComputeBackedgeTakenCount(L); + if (Computed.Exact != getCouldNotCompute()) { + assert(isLoopInvariant(Computed.Exact, L) && + isLoopInvariant(Computed.Max, L) && "Computed backedge-taken count isn't loop invariant for loop!"); ++NumTripCountsComputed; // Update the value in the map. - Pair.first->second = BECount; + Result = Computed; } else { - if (BECount.Max != getCouldNotCompute()) + if (Computed.Max != getCouldNotCompute()) // Update the value in the map. - Pair.first->second = BECount; + Result = Computed; if (isa<PHINode>(L->getHeader()->begin())) // Only count loops that have phi nodes as not being computable. ++NumTripCountsNotComputed; @@ -3723,7 +3812,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // conservative estimates made without the benefit of trip count // information. This is similar to the code in forgetLoop, except that // it handles SCEVUnknown PHI nodes specially. - if (BECount.hasAnyInfo()) { + if (Computed.hasAnyInfo()) { SmallVector<Instruction *, 16> Worklist; PushLoopPHIs(L, Worklist); @@ -3754,7 +3843,13 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { PushDefUseChildren(I, Worklist); } } - return Pair.first->second; + + // Re-lookup the insert position, since the call to + // ComputeBackedgeTakenCount above could result in a + // recusive call to getBackedgeTakenInfo (on a different + // loop), which would invalidate the iterator computed + // earlier. + return BackedgeTakenCounts.find(L)->second = Result; } /// forgetLoop - This method should be called by the client when it has @@ -4022,105 +4117,6 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L, return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB)); } -static const SCEVAddRecExpr * -isSimpleUnwrappingAddRec(const SCEV *S, const Loop *L) { - const SCEVAddRecExpr *SA = dyn_cast<SCEVAddRecExpr>(S); - - // The SCEV must be an addrec of this loop. - if (!SA || SA->getLoop() != L || !SA->isAffine()) - return 0; - - // The SCEV must be known to not wrap in some way to be interesting. - if (!SA->hasNoUnsignedWrap() && !SA->hasNoSignedWrap()) - return 0; - - // The stride must be a constant so that we know if it is striding up or down. - if (!isa<SCEVConstant>(SA->getOperand(1))) - return 0; - return SA; -} - -/// getMinusSCEVForExitTest - When considering an exit test for a loop with a -/// "x != y" exit test, we turn this into a computation that evaluates x-y != 0, -/// and this function returns the expression to use for x-y. We know and take -/// advantage of the fact that this subtraction is only being used in a -/// comparison by zero context. -/// -static const SCEV *getMinusSCEVForExitTest(const SCEV *LHS, const SCEV *RHS, - const Loop *L, ScalarEvolution &SE) { - // If either LHS or RHS is an AddRec SCEV (of this loop) that is known to not - // wrap (either NSW or NUW), then we know that the value will either become - // the other one (and thus the loop terminates), that the loop will terminate - // through some other exit condition first, or that the loop has undefined - // behavior. This information is useful when the addrec has a stride that is - // != 1 or -1, because it means we can't "miss" the exit value. - // - // In any of these three cases, it is safe to turn the exit condition into a - // "counting down" AddRec (to zero) by subtracting the two inputs as normal, - // but since we know that the "end cannot be missed" we can force the - // resulting AddRec to be a NUW addrec. Since it is counting down, this means - // that the AddRec *cannot* pass zero. - - // See if LHS and RHS are addrec's we can handle. - const SCEVAddRecExpr *LHSA = isSimpleUnwrappingAddRec(LHS, L); - const SCEVAddRecExpr *RHSA = isSimpleUnwrappingAddRec(RHS, L); - - // If neither addrec is interesting, just return a minus. - if (RHSA == 0 && LHSA == 0) - return SE.getMinusSCEV(LHS, RHS); - - // If only one of LHS and RHS are an AddRec of this loop, make sure it is LHS. - if (RHSA && LHSA == 0) { - // Safe because a-b === b-a for comparisons against zero. - std::swap(LHS, RHS); - std::swap(LHSA, RHSA); - } - - // Handle the case when only one is advancing in a non-overflowing way. - if (RHSA == 0) { - // If RHS is loop varying, then we can't predict when LHS will cross it. - if (!SE.isLoopInvariant(RHS, L)) - return SE.getMinusSCEV(LHS, RHS); - - // If LHS has a positive stride, then we compute RHS-LHS, because the loop - // is counting up until it crosses RHS (which must be larger than LHS). If - // it is negative, we compute LHS-RHS because we're counting down to RHS. - const ConstantInt *Stride = - cast<SCEVConstant>(LHSA->getOperand(1))->getValue(); - if (Stride->getValue().isNegative()) - std::swap(LHS, RHS); - - return SE.getMinusSCEV(RHS, LHS, true /*HasNUW*/); - } - - // If both LHS and RHS are interesting, we have something like: - // a+i*4 != b+i*8. - const ConstantInt *LHSStride = - cast<SCEVConstant>(LHSA->getOperand(1))->getValue(); - const ConstantInt *RHSStride = - cast<SCEVConstant>(RHSA->getOperand(1))->getValue(); - - // If the strides are equal, then this is just a (complex) loop invariant - // comparison of a and b. - if (LHSStride == RHSStride) - return SE.getMinusSCEV(LHSA->getStart(), RHSA->getStart()); - - // If the signs of the strides differ, then the negative stride is counting - // down to the positive stride. - if (LHSStride->getValue().isNegative() != RHSStride->getValue().isNegative()){ - if (RHSStride->getValue().isNegative()) - std::swap(LHS, RHS); - } else { - // If LHS's stride is smaller than RHS's stride, then "b" must be less than - // "a" and "b" is RHS is counting up (catching up) to LHS. This is true - // whether the strides are positive or negative. - if (RHSStride->getValue().slt(LHSStride->getValue())) - std::swap(LHS, RHS); - } - - return SE.getMinusSCEV(LHS, RHS, true /*HasNUW*/); -} - /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the /// backedge of the specified loop will execute if its exit condition /// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB. @@ -4180,8 +4176,7 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, switch (Cond) { case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) - BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEVForExitTest(LHS, RHS, L, - *this), L); + BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEV(LHS, RHS), L); if (BTI.hasAnyInfo()) return BTI; break; } @@ -4706,7 +4701,15 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { for (++i; i != e; ++i) NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L)); - AddRec = cast<SCEVAddRecExpr>(getAddRecExpr(NewOps, AddRec->getLoop())); + const SCEV *FoldedRec = + getAddRecExpr(NewOps, AddRec->getLoop(), + AddRec->getNoWrapFlags(SCEV::FlagNW)); + AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec); + // The addrec may be folded to a nonrecurrence, for example, if the + // induction variable is multiplied by zero after constant folding. Go + // ahead and return the folded value. + if (!AddRec) + return FoldedRec; break; } @@ -4871,6 +4874,11 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { /// HowFarToZero - Return the number of times a backedge comparing the specified /// value to zero will execute. If not computable, return CouldNotCompute. +/// +/// This is only used for loops with a "x != y" exit test. The exit condition is +/// now expressed as a single expression, V = x-y. So the exit test is +/// effectively V != 0. We know and take advantage of the fact that this +/// expression only being used in a comparison by zero context. ScalarEvolution::BackedgeTakenInfo ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { // If the value is a constant @@ -4903,7 +4911,7 @@ ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { R2->getValue()))) { if (CB->getZExtValue() == false) std::swap(R1, R2); // R1 is the minimum root now. - + // We can only use this value if the chrec ends up with an exact zero // value at this index. When solving for "X*X != 5", for example, we // should not accept a root of 2. @@ -4934,26 +4942,43 @@ ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop()); - // If the AddRec is NUW, then (in an unsigned sense) it cannot be counting up - // to wrap to 0, it must be counting down to equal 0. Also, while counting - // down, it cannot "miss" 0 (which would cause it to wrap), regardless of what - // the stride is. As such, NUW addrec's will always become zero in - // "start / -stride" steps, and we know that the division is exact. - if (AddRec->hasNoUnsignedWrap()) - // FIXME: We really want an "isexact" bit for udiv. - return getUDivExpr(Start, getNegativeSCEV(Step)); - // For now we handle only constant steps. + // + // TODO: Handle a nonconstant Step given AddRec<NUW>. If the + // AddRec is NUW, then (in an unsigned sense) it cannot be counting up to wrap + // to 0, it must be counting down to equal 0. Consequently, N = Start / -Step. + // We have not yet seen any such cases. const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step); if (StepC == 0) return getCouldNotCompute(); - // First, handle unitary steps. - if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so: - return getNegativeSCEV(Start); // N = -Start (as unsigned) - - if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so: - return Start; // N = Start (as unsigned) + // For positive steps (counting up until unsigned overflow): + // N = -Start/Step (as unsigned) + // For negative steps (counting down to zero): + // N = Start/-Step + // First compute the unsigned distance from zero in the direction of Step. + bool CountDown = StepC->getValue()->getValue().isNegative(); + const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start); + + // Handle unitary steps, which cannot wraparound. + // 1*N = -Start; -1*N = Start (mod 2^BW), so: + // N = Distance (as unsigned) + if (StepC->getValue()->equalsInt(1) || StepC->getValue()->isAllOnesValue()) + return Distance; + + // If the recurrence is known not to wraparound, unsigned divide computes the + // back edge count. We know that the value will either become zero (and thus + // the loop terminates), that the loop will terminate through some other exit + // condition first, or that the loop has undefined behavior. This means + // we can't "miss" the exit value, even with nonunit stride. + // + // FIXME: Prove that loops always exhibits *acceptable* undefined + // behavior. Loops must exhibit defined behavior until a wrapped value is + // actually used. So the trip count computed by udiv could be smaller than the + // number of well-defined iterations. + if (AddRec->getNoWrapFlags(SCEV::FlagNW)) + // FIXME: We really want an "isexact" bit for udiv. + return getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step); // Then, try to solve the above equation provided that Start is constant. if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) @@ -5220,12 +5245,12 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, case ICmpInst::ICMP_SLE: if (!getSignedRange(RHS).getSignedMax().isMaxSignedValue()) { RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, - /*HasNUW=*/false, /*HasNSW=*/true); + SCEV::FlagNSW); Pred = ICmpInst::ICMP_SLT; Changed = true; } else if (!getSignedRange(LHS).getSignedMin().isMinSignedValue()) { LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS, - /*HasNUW=*/false, /*HasNSW=*/true); + SCEV::FlagNSW); Pred = ICmpInst::ICMP_SLT; Changed = true; } @@ -5233,12 +5258,12 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, case ICmpInst::ICMP_SGE: if (!getSignedRange(RHS).getSignedMin().isMinSignedValue()) { RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS, - /*HasNUW=*/false, /*HasNSW=*/true); + SCEV::FlagNSW); Pred = ICmpInst::ICMP_SGT; Changed = true; } else if (!getSignedRange(LHS).getSignedMax().isMaxSignedValue()) { LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, - /*HasNUW=*/false, /*HasNSW=*/true); + SCEV::FlagNSW); Pred = ICmpInst::ICMP_SGT; Changed = true; } @@ -5246,12 +5271,12 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, case ICmpInst::ICMP_ULE: if (!getUnsignedRange(RHS).getUnsignedMax().isMaxValue()) { RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, - /*HasNUW=*/true, /*HasNSW=*/false); + SCEV::FlagNUW); Pred = ICmpInst::ICMP_ULT; Changed = true; } else if (!getUnsignedRange(LHS).getUnsignedMin().isMinValue()) { LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS, - /*HasNUW=*/true, /*HasNSW=*/false); + SCEV::FlagNUW); Pred = ICmpInst::ICMP_ULT; Changed = true; } @@ -5259,12 +5284,12 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, case ICmpInst::ICMP_UGE: if (!getUnsignedRange(RHS).getUnsignedMin().isMinValue()) { RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS, - /*HasNUW=*/true, /*HasNSW=*/false); + SCEV::FlagNUW); Pred = ICmpInst::ICMP_UGT; Changed = true; } else if (!getUnsignedRange(LHS).getUnsignedMax().isMaxValue()) { LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, - /*HasNUW=*/true, /*HasNSW=*/false); + SCEV::FlagNUW); Pred = ICmpInst::ICMP_UGT; Changed = true; } @@ -5646,6 +5671,13 @@ const SCEV *ScalarEvolution::getBECount(const SCEV *Start, "This code doesn't handle negative strides yet!"); const Type *Ty = Start->getType(); + + // When Start == End, we have an exact BECount == 0. Short-circuit this case + // here because SCEV may not be able to determine that the unsigned division + // after rounding is zero. + if (Start == End) + return getConstant(Ty, 0); + const SCEV *NegOne = getConstant(Ty, (uint64_t)-1); const SCEV *Diff = getMinusSCEV(End, Start); const SCEV *RoundUp = getAddExpr(Step, NegOne); @@ -5683,8 +5715,8 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, return getCouldNotCompute(); // Check to see if we have a flag which makes analysis easy. - bool NoWrap = isSigned ? AddRec->hasNoSignedWrap() : - AddRec->hasNoUnsignedWrap(); + bool NoWrap = isSigned ? AddRec->getNoWrapFlags(SCEV::FlagNSW) : + AddRec->getNoWrapFlags(SCEV::FlagNUW); if (AddRec->isAffine()) { unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); @@ -5768,7 +5800,16 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, // The maximum backedge count is similar, except using the minimum start // value and the maximum end value. - const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step, NoWrap); + // If we already have an exact constant BECount, use it instead. + const SCEV *MaxBECount = isa<SCEVConstant>(BECount) ? BECount + : getBECount(MinStart, MaxEnd, Step, NoWrap); + + // If the stride is nonconstant, and NoWrap == true, then + // getBECount(MinStart, MaxEnd) may not compute. This would result in an + // exact BECount and invalid MaxBECount, which should be avoided to catch + // more optimization opportunities. + if (isa<SCEVCouldNotCompute>(MaxBECount)) + MaxBECount = BECount; return BackedgeTakenInfo(BECount, MaxBECount); } @@ -5791,7 +5832,8 @@ const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, if (!SC->getValue()->isZero()) { SmallVector<const SCEV *, 4> Operands(op_begin(), op_end()); Operands[0] = SE.getConstant(SC->getType(), 0); - const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop()); + const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(), + getNoWrapFlags(FlagNW)); if (const SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted)) return ShiftedAddRec->getNumIterationsInRange( @@ -5852,7 +5894,9 @@ const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, // Range.getUpper() is crossed. SmallVector<const SCEV *, 4> NewOps(op_begin(), op_end()); NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper())); - const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop()); + const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop(), + // getNoWrapFlags(FlagNW) + FlagAnyWrap); // Next, solve the constructed addrec std::pair<const SCEV *,const SCEV *> Roots = diff --git a/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp index b7c110f..8e5a400 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolutionExpander.cpp @@ -262,7 +262,8 @@ static bool FactorOutConstant(const SCEV *&S, const SCEV *Start = A->getStart(); if (!FactorOutConstant(Start, Remainder, Factor, SE, TD)) return false; - S = SE.getAddRecExpr(Start, Step, A->getLoop()); + // FIXME: can use A->getNoWrapFlags(FlagNW) + S = SE.getAddRecExpr(Start, Step, A->getLoop(), SCEV::FlagAnyWrap); return true; } @@ -314,7 +315,9 @@ static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, const SCEV *Zero = SE.getConstant(Ty, 0); AddRecs.push_back(SE.getAddRecExpr(Zero, A->getStepRecurrence(SE), - A->getLoop())); + A->getLoop(), + // FIXME: A->getNoWrapFlags(FlagNW) + SCEV::FlagAnyWrap)); if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) { Ops[i] = Zero; Ops.append(Add->op_begin(), Add->op_end()); @@ -823,7 +826,9 @@ static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, Rest = SE.getAddExpr(Rest, SE.getAddRecExpr(SE.getConstant(A->getType(), 0), A->getStepRecurrence(SE), - A->getLoop())); + A->getLoop(), + // FIXME: A->getNoWrapFlags(FlagNW) + SCEV::FlagAnyWrap)); } if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { Base = A->getOperand(A->getNumOperands()-1); @@ -858,7 +863,8 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, // loop already visited by LSR for example, but it wouldn't have // to be. do { - if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV)) { + if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) || + (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV))) { IncV = 0; break; } @@ -926,14 +932,14 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, Value *StepV = expandCodeFor(Step, IntTy, L->getHeader()->begin()); // Create the PHI. - Builder.SetInsertPoint(L->getHeader(), L->getHeader()->begin()); - PHINode *PN = Builder.CreatePHI(ExpandTy, "lsr.iv"); + BasicBlock *Header = L->getHeader(); + Builder.SetInsertPoint(Header, Header->begin()); + pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); + PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE), "lsr.iv"); rememberInstruction(PN); // Create the step instructions and populate the PHI. - BasicBlock *Header = L->getHeader(); - for (pred_iterator HPI = pred_begin(Header), HPE = pred_end(Header); - HPI != HPE; ++HPI) { + for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { BasicBlock *Pred = *HPI; // Add a start value. @@ -1004,10 +1010,11 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { if (!SE.properlyDominates(Start, L->getHeader())) { PostLoopOffset = Start; Start = SE.getConstant(Normalized->getType(), 0); - Normalized = - cast<SCEVAddRecExpr>(SE.getAddRecExpr(Start, - Normalized->getStepRecurrence(SE), - Normalized->getLoop())); + Normalized = cast<SCEVAddRecExpr>( + SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE), + Normalized->getLoop(), + // FIXME: Normalized->getNoWrapFlags(FlagNW) + SCEV::FlagAnyWrap)); } // Strip off any non-loop-dominating component from the addrec step. @@ -1018,7 +1025,10 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { Step = SE.getConstant(Normalized->getType(), 1); Normalized = cast<SCEVAddRecExpr>(SE.getAddRecExpr(Start, Step, - Normalized->getLoop())); + Normalized->getLoop(), + // FIXME: Normalized + // ->getNoWrapFlags(FlagNW) + SCEV::FlagAnyWrap)); } // Expand the core addrec. If we need post-loop scaling, force it to @@ -1081,7 +1091,9 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { SmallVector<const SCEV *, 4> NewOps(S->getNumOperands()); for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i) NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType()); - Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop())); + Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(), + // FIXME: S->getNoWrapFlags(FlagNW) + SCEV::FlagAnyWrap)); BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); BasicBlock::iterator NewInsertPt = @@ -1098,7 +1110,8 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { if (!S->getStart()->isZero()) { SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end()); NewOps[0] = SE.getConstant(Ty, 0); - const SCEV *Rest = SE.getAddRecExpr(NewOps, L); + // FIXME: can use S->getNoWrapFlags() + const SCEV *Rest = SE.getAddRecExpr(NewOps, L, SCEV::FlagAnyWrap); // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the // comments on expandAddToGEP for details. @@ -1128,12 +1141,13 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { // Create and insert the PHI node for the induction variable in the // specified loop. BasicBlock *Header = L->getHeader(); - CanonicalIV = PHINode::Create(Ty, "indvar", Header->begin()); + pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); + CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar", + Header->begin()); rememberInstruction(CanonicalIV); Constant *One = ConstantInt::get(Ty, 1); - for (pred_iterator HPI = pred_begin(Header), HPE = pred_end(Header); - HPI != HPE; ++HPI) { + for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { BasicBlock *HP = *HPI; if (L->contains(HP)) { // Insert a unit add instruction right before the terminator @@ -1333,7 +1347,7 @@ void SCEVExpander::rememberInstruction(Value *I) { InsertedValues.insert(I); // If we just claimed an existing instruction and that instruction had - // been the insert point, adjust the insert point forward so that + // been the insert point, adjust the insert point forward so that // subsequently inserted code will be dominated. if (Builder.GetInsertPoint() == I) { BasicBlock::iterator It = cast<Instruction>(I); @@ -1361,8 +1375,9 @@ SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, assert(Ty->isIntegerTy() && "Can only insert integer induction variables!"); // Build a SCEV for {0,+,1}<L>. + // Conservatively use FlagAnyWrap for now. const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0), - SE.getConstant(Ty, 1), L); + SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap); // Emit code for it. BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); diff --git a/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp b/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp index ac36cef..60e630a 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp @@ -97,7 +97,8 @@ const SCEV *llvm::TransformForPostIncUse(TransformKind Kind, const SCEV *N = TransformForPostIncUse(Kind, O, LUser, 0, Loops, SE, DT); Operands.push_back(N); } - const SCEV *Result = SE.getAddRecExpr(Operands, L); + // Conservatively use AnyWrap until/unless we need FlagNW. + const SCEV *Result = SE.getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); switch (Kind) { default: llvm_unreachable("Unexpected transform name!"); case NormalizeAutodetect: diff --git a/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp b/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp index 40e18ab..0faf1398 100644 --- a/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -31,7 +31,7 @@ // // The second field identifies the type's parent node in the tree, or // is null or omitted for a root node. A type is considered to alias -// all of its decendents and all of its ancestors in the tree. Also, +// all of its descendants and all of its ancestors in the tree. Also, // a type is considered to alias all types in other trees, so that // bitcode produced from multiple front-ends is handled conservatively. // @@ -59,6 +59,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Passes.h" +#include "llvm/Constants.h" #include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Metadata.h" diff --git a/contrib/llvm/lib/Analysis/ValueTracking.cpp b/contrib/llvm/lib/Analysis/ValueTracking.cpp index 1060bc5..8f18dd2 100644 --- a/contrib/llvm/lib/Analysis/ValueTracking.cpp +++ b/contrib/llvm/lib/Analysis/ValueTracking.cpp @@ -429,6 +429,29 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, KnownZero |= LHSKnownZero & Mask; KnownOne |= LHSKnownOne & Mask; } + + // Are we still trying to solve for the sign bit? + if (Mask.isNegative() && !KnownZero.isNegative() && !KnownOne.isNegative()){ + OverflowingBinaryOperator *OBO = cast<OverflowingBinaryOperator>(I); + if (OBO->hasNoSignedWrap()) { + if (I->getOpcode() == Instruction::Add) { + // Adding two positive numbers can't wrap into negative + if (LHSKnownZero.isNegative() && KnownZero2.isNegative()) + KnownZero |= APInt::getSignBit(BitWidth); + // and adding two negative numbers can't wrap into positive. + else if (LHSKnownOne.isNegative() && KnownOne2.isNegative()) + KnownOne |= APInt::getSignBit(BitWidth); + } else { + // Subtracting a negative number from a positive one can't wrap + if (LHSKnownZero.isNegative() && KnownOne2.isNegative()) + KnownZero |= APInt::getSignBit(BitWidth); + // neither can subtracting a positive number from a negative one. + else if (LHSKnownOne.isNegative() && KnownZero2.isNegative()) + KnownOne |= APInt::getSignBit(BitWidth); + } + } + } + return; } case Instruction::SRem: @@ -460,6 +483,19 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); } } + + // The sign bit is the LHS's sign bit, except when the result of the + // remainder is zero. + if (Mask.isNegative() && KnownZero.isNonNegative()) { + APInt Mask2 = APInt::getSignBit(BitWidth); + APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); + ComputeMaskedBits(I->getOperand(0), Mask2, LHSKnownZero, LHSKnownOne, TD, + Depth+1); + // If it's known zero, our sign bit is also zero. + if (LHSKnownZero.isNegative()) + KnownZero |= LHSKnownZero; + } + break; case Instruction::URem: { if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { @@ -597,6 +633,10 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, // Otherwise take the unions of the known bit sets of the operands, // taking conservative care to avoid excessive recursion. if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { + // Skip if every incoming value references to ourself. + if (P->hasConstantValue() == P) + break; + KnownZero = APInt::getAllOnesValue(BitWidth); KnownOne = APInt::getAllOnesValue(BitWidth); for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { @@ -684,6 +724,16 @@ bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, unsigned Depth) { return isPowerOfTwo(SI->getTrueValue(), TD, Depth) && isPowerOfTwo(SI->getFalseValue(), TD, Depth); + // An exact divide or right shift can only shift off zero bits, so the result + // is a power of two only if the first operand is a power of two and not + // copying a sign bit (sdiv int_min, 2). + if (match(V, m_LShr(m_Value(), m_Value())) || + match(V, m_UDiv(m_Value(), m_Value()))) { + PossiblyExactOperator *PEO = cast<PossiblyExactOperator>(V); + if (PEO->isExact()) + return isPowerOfTwo(PEO->getOperand(0), TD, Depth); + } + return false; } @@ -720,6 +770,11 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined // if the lowest bit is shifted off the end. if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) { + // shl nuw can't remove any non-zero bits. + BinaryOperator *BO = cast<BinaryOperator>(V); + if (BO->hasNoUnsignedWrap()) + return isKnownNonZero(X, TD, Depth); + APInt KnownZero(BitWidth, 0); APInt KnownOne(BitWidth, 0); ComputeMaskedBits(X, APInt(BitWidth, 1), KnownZero, KnownOne, TD, Depth); @@ -729,11 +784,22 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { // shr X, Y != 0 if X is negative. Note that the value of the shift is not // defined if the sign bit is shifted off the end. else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) { + // shr exact can only shift out zero bits. + BinaryOperator *BO = cast<BinaryOperator>(V); + if (BO->isExact()) + return isKnownNonZero(X, TD, Depth); + bool XKnownNonNegative, XKnownNegative; ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); if (XKnownNegative) return true; } + // div exact can only produce a zero if the dividend is zero. + else if (match(V, m_IDiv(m_Value(X), m_Value()))) { + BinaryOperator *BO = cast<BinaryOperator>(V); + if (BO->isExact()) + return isKnownNonZero(X, TD, Depth); + } // X + Y. else if (match(V, m_Add(m_Value(X), m_Value(Y)))) { bool XKnownNonNegative, XKnownNegative; @@ -1262,7 +1328,7 @@ static Value *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, break; } } - // If we succesfully found a value for each of our subaggregates + // If we successfully found a value for each of our subaggregates if (To) return To; } @@ -1691,7 +1757,7 @@ llvm::GetUnderlyingObject(Value *V, const TargetData *TD, unsigned MaxLookup) { } else { // See if InstructionSimplify knows any relevant tricks. if (Instruction *I = dyn_cast<Instruction>(V)) - // TODO: Aquire a DominatorTree and use it. + // TODO: Acquire a DominatorTree and use it. if (Value *Simplified = SimplifyInstruction(I, TD, 0)) { V = Simplified; continue; |
