diff options
Diffstat (limited to 'lib/Analysis')
32 files changed, 1181 insertions, 2756 deletions
diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp index 95c834b..3b6aab1 100644 --- a/lib/Analysis/AliasAnalysis.cpp +++ b/lib/Analysis/AliasAnalysis.cpp @@ -25,6 +25,9 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/Pass.h" #include "llvm/BasicBlock.h" #include "llvm/Function.h" @@ -356,6 +359,86 @@ AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { return ModRef; } +namespace { + /// Only find pointer captures which happen before the given instruction. Uses + /// the dominator tree to determine whether one instruction is before another. + struct CapturesBefore : public CaptureTracker { + CapturesBefore(const Instruction *I, DominatorTree *DT) + : BeforeHere(I), DT(DT), Captured(false) {} + + void tooManyUses() { Captured = true; } + + bool shouldExplore(Use *U) { + Instruction *I = cast<Instruction>(U->getUser()); + BasicBlock *BB = I->getParent(); + if (BeforeHere != I && + (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I))) + return false; + return true; + } + + bool captured(Use *U) { + Instruction *I = cast<Instruction>(U->getUser()); + BasicBlock *BB = I->getParent(); + if (BeforeHere != I && + (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I))) + return false; + Captured = true; + return true; + } + + const Instruction *BeforeHere; + DominatorTree *DT; + + bool Captured; + }; +} + +// FIXME: this is really just shoring-up a deficiency in alias analysis. +// BasicAA isn't willing to spend linear time determining whether an alloca +// was captured before or after this particular call, while we are. However, +// with a smarter AA in place, this test is just wasting compile time. +AliasAnalysis::ModRefResult +AliasAnalysis::callCapturesBefore(const Instruction *I, + const AliasAnalysis::Location &MemLoc, + DominatorTree *DT) { + if (!DT || !TD) return AliasAnalysis::ModRef; + + const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD); + if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || + isa<Constant>(Object)) + return AliasAnalysis::ModRef; + + ImmutableCallSite CS(I); + if (!CS.getInstruction() || CS.getInstruction() == Object) + return AliasAnalysis::ModRef; + + CapturesBefore CB(I, DT); + llvm::PointerMayBeCaptured(Object, &CB); + if (CB.Captured) + return AliasAnalysis::ModRef; + + unsigned ArgNo = 0; + for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); + CI != CE; ++CI, ++ArgNo) { + // Only look at the no-capture or byval pointer arguments. If this + // pointer were passed to arguments that were neither of these, then it + // couldn't be no-capture. + if (!(*CI)->getType()->isPointerTy() || + (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) + continue; + + // If this is a no-capture pointer argument, see if we can tell that it + // is impossible to alias the pointer we're checking. If not, we have to + // assume that the call could touch the pointer, even though it doesn't + // escape. + if (!isNoAlias(AliasAnalysis::Location(*CI), + AliasAnalysis::Location(Object))) { + return AliasAnalysis::ModRef; + } + } + return AliasAnalysis::NoModRef; +} // AliasAnalysis destructor: DO NOT move this to the header file for // AliasAnalysis or else clients of the AliasAnalysis class may not depend on diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp index f80e2fb..92e8906 100644 --- a/lib/Analysis/AliasSetTracker.cpp +++ b/lib/Analysis/AliasSetTracker.cpp @@ -501,7 +501,7 @@ void AliasSetTracker::deleteValue(Value *PtrVal) { } // First, look up the PointerRec for this pointer. - PointerMapType::iterator I = PointerMap.find(PtrVal); + PointerMapType::iterator I = PointerMap.find_as(PtrVal); if (I == PointerMap.end()) return; // Noop // If we found one, remove the pointer from the alias set it is in. @@ -527,7 +527,7 @@ void AliasSetTracker::copyValue(Value *From, Value *To) { AA.copyValue(From, To); // First, look up the PointerRec for this pointer. - PointerMapType::iterator I = PointerMap.find(From); + PointerMapType::iterator I = PointerMap.find_as(From); if (I == PointerMap.end()) return; // Noop assert(I->second->hasAliasSet() && "Dead entry?"); @@ -536,7 +536,7 @@ void AliasSetTracker::copyValue(Value *From, Value *To) { if (Entry.hasAliasSet()) return; // Already in the tracker! // Add it to the alias set it aliases... - I = PointerMap.find(From); + I = PointerMap.find_as(From); AliasSet *AS = I->second->getAliasSet(*this); AS->addPointer(*this, Entry, I->second->getSize(), I->second->getTBAAInfo(), diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 20ecfd2..1d028c2 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -86,47 +86,10 @@ static bool isEscapeSource(const Value *V) { /// UnknownSize if unknown. static uint64_t getObjectSize(const Value *V, const TargetData &TD, bool RoundToAlign = false) { - Type *AccessTy; - unsigned Align; - if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { - if (!GV->hasDefinitiveInitializer()) - return AliasAnalysis::UnknownSize; - AccessTy = GV->getType()->getElementType(); - Align = GV->getAlignment(); - } else if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { - if (!AI->isArrayAllocation()) - AccessTy = AI->getType()->getElementType(); - else - return AliasAnalysis::UnknownSize; - Align = AI->getAlignment(); - } else if (const CallInst* CI = extractMallocCall(V)) { - if (!RoundToAlign && !isArrayMalloc(V, &TD)) - // The size is the argument to the malloc call. - if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getArgOperand(0))) - return C->getZExtValue(); - return AliasAnalysis::UnknownSize; - } else if (const Argument *A = dyn_cast<Argument>(V)) { - if (A->hasByValAttr()) { - AccessTy = cast<PointerType>(A->getType())->getElementType(); - Align = A->getParamAlignment(); - } else { - return AliasAnalysis::UnknownSize; - } - } else { - return AliasAnalysis::UnknownSize; - } - - if (!AccessTy->isSized()) - return AliasAnalysis::UnknownSize; - - uint64_t Size = TD.getTypeAllocSize(AccessTy); - // If there is an explicitly specified alignment, and we need to - // take alignment into account, round up the size. (If the alignment - // is implicit, getTypeAllocSize is sufficient.) - if (RoundToAlign && Align) - Size = RoundUpToAlignment(Size, Align); - - return Size; + uint64_t Size; + if (getObjectSize(V, Size, &TD, RoundToAlign)) + return Size; + return AliasAnalysis::UnknownSize; } /// isObjectSmallerThan - Return true if we can prove that the object specified diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 2e3ec8b..96e68b4 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -12,9 +12,7 @@ add_llvm_library(LLVMAnalysis CaptureTracking.cpp CodeMetrics.cpp ConstantFolding.cpp - DIBuilder.cpp DbgInfoPrinter.cpp - DebugInfo.cpp DomPrinter.cpp DominanceFrontier.cpp IVUsers.cpp @@ -59,4 +57,6 @@ add_llvm_library(LLVMAnalysis ValueTracking.cpp ) +add_dependencies(LLVMAnalysis intrinsics_gen) + add_subdirectory(IPA) diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp index dd33eeb..974b906 100644 --- a/lib/Analysis/CaptureTracking.cpp +++ b/lib/Analysis/CaptureTracking.cpp @@ -34,7 +34,7 @@ namespace { bool captured(Use *U) { if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) - return false; + return false; Captured = true; return true; diff --git a/lib/Analysis/CodeMetrics.cpp b/lib/Analysis/CodeMetrics.cpp index 316e7bc9..acda34b 100644 --- a/lib/Analysis/CodeMetrics.cpp +++ b/lib/Analysis/CodeMetrics.cpp @@ -22,7 +22,11 @@ using namespace llvm; /// callIsSmall - If a call is likely to lower to a single target instruction, /// or is otherwise deemed small return true. /// TODO: Perhaps calls like memcpy, strcpy, etc? -bool llvm::callIsSmall(const Function *F) { +bool llvm::callIsSmall(ImmutableCallSite CS) { + if (isa<IntrinsicInst>(CS.getInstruction())) + return true; + + const Function *F = CS.getCalledFunction(); if (!F) return false; if (F->hasLocalLinkage()) return false; @@ -79,8 +83,24 @@ bool llvm::isInstructionFree(const Instruction *I, const TargetData *TD) { if (const CastInst *CI = dyn_cast<CastInst>(I)) { // Noop casts, including ptr <-> int, don't count. - if (CI->isLosslessCast() || isa<IntToPtrInst>(CI) || isa<PtrToIntInst>(CI)) + if (CI->isLosslessCast()) + return true; + + Value *Op = CI->getOperand(0); + // An inttoptr cast is free so long as the input is a legal integer type + // which doesn't contain values outside the range of a pointer. + if (isa<IntToPtrInst>(CI) && TD && + TD->isLegalInteger(Op->getType()->getScalarSizeInBits()) && + Op->getType()->getScalarSizeInBits() <= TD->getPointerSizeInBits()) return true; + + // A ptrtoint cast is free so long as the result is large enough to store + // the pointer, and a legal integer type. + if (isa<PtrToIntInst>(CI) && TD && + TD->isLegalInteger(Op->getType()->getScalarSizeInBits()) && + Op->getType()->getScalarSizeInBits() >= TD->getPointerSizeInBits()) + return true; + // trunc to a native type is free (assuming the target has compare and // shift-right of the same width). if (TD && isa<TruncInst>(CI) && @@ -126,7 +146,7 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB, isRecursive = true; } - if (!isa<IntrinsicInst>(II) && !callIsSmall(CS.getCalledFunction())) { + if (!callIsSmall(CS)) { // Each argument to a call takes on average one instruction to set up. NumInsts += CS.arg_size(); diff --git a/lib/Analysis/ConstantFolding.cpp b/lib/Analysis/ConstantFolding.cpp index 783c32e..f5e619c 100644 --- a/lib/Analysis/ConstantFolding.cpp +++ b/lib/Analysis/ConstantFolding.cpp @@ -358,17 +358,20 @@ static bool ReadDataFromGlobal(Constant *C, uint64_t ByteOffset, NumElts = AT->getNumElements(); else NumElts = cast<VectorType>(C->getType())->getNumElements(); - + for (; Index != NumElts; ++Index) { if (!ReadDataFromGlobal(C->getAggregateElement(Index), Offset, CurPtr, BytesLeft, TD)) return false; - if (EltSize >= BytesLeft) + + uint64_t BytesWritten = EltSize - Offset; + assert(BytesWritten <= EltSize && "Not indexing into this element?"); + if (BytesWritten >= BytesLeft) return true; - + Offset = 0; - BytesLeft -= EltSize; - CurPtr += EltSize; + BytesLeft -= BytesWritten; + CurPtr += BytesWritten; } return true; } @@ -600,6 +603,22 @@ static Constant *CastGEPIndices(ArrayRef<Constant *> Ops, return C; } +/// Strip the pointer casts, but preserve the address space information. +static Constant* StripPtrCastKeepAS(Constant* Ptr) { + assert(Ptr->getType()->isPointerTy() && "Not a pointer type"); + PointerType *OldPtrTy = cast<PointerType>(Ptr->getType()); + Ptr = cast<Constant>(Ptr->stripPointerCasts()); + PointerType *NewPtrTy = cast<PointerType>(Ptr->getType()); + + // Preserve the address space number of the pointer. + if (NewPtrTy->getAddressSpace() != OldPtrTy->getAddressSpace()) { + NewPtrTy = NewPtrTy->getElementType()->getPointerTo( + OldPtrTy->getAddressSpace()); + Ptr = ConstantExpr::getBitCast(Ptr, NewPtrTy); + } + return Ptr; +} + /// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP /// constant expression, do so. static Constant *SymbolicallyEvaluateGEP(ArrayRef<Constant *> Ops, @@ -636,13 +655,13 @@ static Constant *SymbolicallyEvaluateGEP(ArrayRef<Constant *> Ops, } return 0; } - + unsigned BitWidth = TD->getTypeSizeInBits(IntPtrTy); APInt Offset = APInt(BitWidth, TD->getIndexedOffset(Ptr->getType(), makeArrayRef((Value **)Ops.data() + 1, Ops.size() - 1))); - Ptr = cast<Constant>(Ptr->stripPointerCasts()); + Ptr = StripPtrCastKeepAS(Ptr); // If this is a GEP of a GEP, fold it all into a single GEP. while (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) { @@ -661,7 +680,7 @@ static Constant *SymbolicallyEvaluateGEP(ArrayRef<Constant *> Ops, Ptr = cast<Constant>(GEP->getOperand(0)); Offset += APInt(BitWidth, TD->getIndexedOffset(Ptr->getType(), NestedOps)); - Ptr = cast<Constant>(Ptr->stripPointerCasts()); + Ptr = StripPtrCastKeepAS(Ptr); } // If the base value for this address is a literal integer value, fold the @@ -780,14 +799,21 @@ Constant *llvm::ConstantFoldInstruction(Instruction *I, // all operands are constants. if (isa<UndefValue>(Incoming)) continue; - // If the incoming value is not a constant, or is a different constant to - // the one we saw previously, then give up. + // If the incoming value is not a constant, then give up. Constant *C = dyn_cast<Constant>(Incoming); - if (!C || (CommonValue && C != CommonValue)) + if (!C) + return 0; + // Fold the PHI's operands. + if (ConstantExpr *NewC = dyn_cast<ConstantExpr>(C)) + C = ConstantFoldConstantExpression(NewC, TD, TLI); + // If the incoming value is a different constant to + // the one we saw previously, then give up. + if (CommonValue && C != CommonValue) return 0; CommonValue = C; } + // If we reach here, all incoming values are the same constant or undef. return CommonValue ? CommonValue : UndefValue::get(PN->getType()); } @@ -795,12 +821,18 @@ Constant *llvm::ConstantFoldInstruction(Instruction *I, // Scan the operand list, checking to see if they are all constants, if so, // hand off to ConstantFoldInstOperands. SmallVector<Constant*, 8> Ops; - for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) - if (Constant *Op = dyn_cast<Constant>(*i)) - Ops.push_back(Op); - else + for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) { + Constant *Op = dyn_cast<Constant>(*i); + if (!Op) return 0; // All operands not constant! + // Fold the Instruction's operands. + if (ConstantExpr *NewCE = dyn_cast<ConstantExpr>(Op)) + Op = ConstantFoldConstantExpression(NewCE, TD, TLI); + + Ops.push_back(Op); + } + if (const CmpInst *CI = dyn_cast<CmpInst>(I)) return ConstantFoldCompareInstOperands(CI->getPredicate(), Ops[0], Ops[1], TD, TLI); diff --git a/lib/Analysis/DIBuilder.cpp b/lib/Analysis/DIBuilder.cpp deleted file mode 100644 index 85913b1..0000000 --- a/lib/Analysis/DIBuilder.cpp +++ /dev/null @@ -1,1015 +0,0 @@ -//===--- DIBuilder.cpp - Debug Information Builder ------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the DIBuilder. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DIBuilder.h" -#include "llvm/Analysis/DebugInfo.h" -#include "llvm/Constants.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Module.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Dwarf.h" - -using namespace llvm; -using namespace llvm::dwarf; - -static Constant *GetTagConstant(LLVMContext &VMContext, unsigned Tag) { - assert((Tag & LLVMDebugVersionMask) == 0 && - "Tag too large for debug encoding!"); - return ConstantInt::get(Type::getInt32Ty(VMContext), Tag | LLVMDebugVersion); -} - -DIBuilder::DIBuilder(Module &m) - : M(m), VMContext(M.getContext()), TheCU(0), TempEnumTypes(0), - TempRetainTypes(0), TempSubprograms(0), TempGVs(0), DeclareFn(0), - ValueFn(0) -{} - -/// finalize - Construct any deferred debug info descriptors. -void DIBuilder::finalize() { - DIArray Enums = getOrCreateArray(AllEnumTypes); - DIType(TempEnumTypes).replaceAllUsesWith(Enums); - - DIArray RetainTypes = getOrCreateArray(AllRetainTypes); - DIType(TempRetainTypes).replaceAllUsesWith(RetainTypes); - - DIArray SPs = getOrCreateArray(AllSubprograms); - DIType(TempSubprograms).replaceAllUsesWith(SPs); - for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) { - DISubprogram SP(SPs.getElement(i)); - if (NamedMDNode *NMD = getFnSpecificMDNode(M, SP)) { - SmallVector<Value *, 4> Variables; - for (unsigned ii = 0, ee = NMD->getNumOperands(); ii != ee; ++ii) - Variables.push_back(NMD->getOperand(ii)); - if (MDNode *Temp = SP.getVariablesNodes()) { - DIArray AV = getOrCreateArray(Variables); - DIType(Temp).replaceAllUsesWith(AV); - } - NMD->eraseFromParent(); - } - } - - DIArray GVs = getOrCreateArray(AllGVs); - DIType(TempGVs).replaceAllUsesWith(GVs); -} - -/// getNonCompileUnitScope - If N is compile unit return NULL otherwise return -/// N. -static MDNode *getNonCompileUnitScope(MDNode *N) { - if (DIDescriptor(N).isCompileUnit()) - return NULL; - return N; -} - -/// createCompileUnit - A CompileUnit provides an anchor for all debugging -/// information generated during this instance of compilation. -void DIBuilder::createCompileUnit(unsigned Lang, StringRef Filename, - StringRef Directory, StringRef Producer, - bool isOptimized, StringRef Flags, - unsigned RunTimeVer) { - assert(((Lang <= dwarf::DW_LANG_Python && Lang >= dwarf::DW_LANG_C89) || - (Lang <= dwarf::DW_LANG_hi_user && Lang >= dwarf::DW_LANG_lo_user)) && - "Invalid Language tag"); - assert(!Filename.empty() && - "Unable to create compile unit without filename"); - Value *TElts[] = { GetTagConstant(VMContext, DW_TAG_base_type) }; - TempEnumTypes = MDNode::getTemporary(VMContext, TElts); - Value *THElts[] = { TempEnumTypes }; - MDNode *EnumHolder = MDNode::get(VMContext, THElts); - - TempRetainTypes = MDNode::getTemporary(VMContext, TElts); - Value *TRElts[] = { TempRetainTypes }; - MDNode *RetainHolder = MDNode::get(VMContext, TRElts); - - TempSubprograms = MDNode::getTemporary(VMContext, TElts); - Value *TSElts[] = { TempSubprograms }; - MDNode *SPHolder = MDNode::get(VMContext, TSElts); - - TempGVs = MDNode::getTemporary(VMContext, TElts); - Value *TVElts[] = { TempGVs }; - MDNode *GVHolder = MDNode::get(VMContext, TVElts); - - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_compile_unit), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - ConstantInt::get(Type::getInt32Ty(VMContext), Lang), - MDString::get(VMContext, Filename), - MDString::get(VMContext, Directory), - MDString::get(VMContext, Producer), - // Deprecate isMain field. - ConstantInt::get(Type::getInt1Ty(VMContext), true), // isMain - ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), - MDString::get(VMContext, Flags), - ConstantInt::get(Type::getInt32Ty(VMContext), RunTimeVer), - EnumHolder, - RetainHolder, - SPHolder, - GVHolder - }; - TheCU = DICompileUnit(MDNode::get(VMContext, Elts)); - - // Create a named metadata so that it is easier to find cu in a module. - NamedMDNode *NMD = M.getOrInsertNamedMetadata("llvm.dbg.cu"); - NMD->addOperand(TheCU); -} - -/// createFile - Create a file descriptor to hold debugging information -/// for a file. -DIFile DIBuilder::createFile(StringRef Filename, StringRef Directory) { - assert(TheCU && "Unable to create DW_TAG_file_type without CompileUnit"); - assert(!Filename.empty() && "Unable to create file without name"); - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_file_type), - MDString::get(VMContext, Filename), - MDString::get(VMContext, Directory), - NULL // TheCU - }; - return DIFile(MDNode::get(VMContext, Elts)); -} - -/// createEnumerator - Create a single enumerator value. -DIEnumerator DIBuilder::createEnumerator(StringRef Name, uint64_t Val) { - assert(!Name.empty() && "Unable to create enumerator without name"); - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_enumerator), - MDString::get(VMContext, Name), - ConstantInt::get(Type::getInt64Ty(VMContext), Val) - }; - return DIEnumerator(MDNode::get(VMContext, Elts)); -} - -/// createNullPtrType - Create C++0x nullptr type. -DIType DIBuilder::createNullPtrType(StringRef Name) { - assert(!Name.empty() && "Unable to create type without name"); - // nullptr is encoded in DIBasicType format. Line number, filename, - // ,size, alignment, offset and flags are always empty here. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_unspecified_type), - NULL, //TheCU, - MDString::get(VMContext, Name), - NULL, // Filename - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Line - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Size - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Align - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Offset - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags; - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Encoding - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createBasicType - Create debugging information entry for a basic -/// type, e.g 'char'. -DIType DIBuilder::createBasicType(StringRef Name, uint64_t SizeInBits, - uint64_t AlignInBits, - unsigned Encoding) { - assert(!Name.empty() && "Unable to create type without name"); - // Basic types are encoded in DIBasicType format. Line number, filename, - // offset and flags are always empty here. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_base_type), - NULL, //TheCU, - MDString::get(VMContext, Name), - NULL, // Filename - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Line - ConstantInt::get(Type::getInt64Ty(VMContext), SizeInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Offset - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags; - ConstantInt::get(Type::getInt32Ty(VMContext), Encoding) - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createQualifiedType - Create debugging information entry for a qualified -/// type, e.g. 'const int'. -DIType DIBuilder::createQualifiedType(unsigned Tag, DIType FromTy) { - // Qualified types are encoded in DIDerivedType format. - Value *Elts[] = { - GetTagConstant(VMContext, Tag), - NULL, //TheCU, - MDString::get(VMContext, StringRef()), // Empty name. - NULL, // Filename - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Line - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Size - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Align - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Offset - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags - FromTy - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createPointerType - Create debugging information entry for a pointer. -DIType DIBuilder::createPointerType(DIType PointeeTy, uint64_t SizeInBits, - uint64_t AlignInBits, StringRef Name) { - // Pointer types are encoded in DIDerivedType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_pointer_type), - NULL, //TheCU, - MDString::get(VMContext, Name), - NULL, // Filename - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Line - ConstantInt::get(Type::getInt64Ty(VMContext), SizeInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Offset - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags - PointeeTy - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createReferenceType - Create debugging information entry for a reference. -DIType DIBuilder::createReferenceType(DIType RTy) { - assert(RTy.Verify() && "Unable to create reference type"); - // References are encoded in DIDerivedType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_reference_type), - NULL, // TheCU, - NULL, // Name - NULL, // Filename - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Line - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Size - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Align - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Offset - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags - RTy - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createTypedef - Create debugging information entry for a typedef. -DIType DIBuilder::createTypedef(DIType Ty, StringRef Name, DIFile File, - unsigned LineNo, DIDescriptor Context) { - // typedefs are encoded in DIDerivedType format. - assert(Ty.Verify() && "Invalid typedef type!"); - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_typedef), - getNonCompileUnitScope(Context), - MDString::get(VMContext, Name), - File, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Size - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Align - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Offset - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags - Ty - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createFriend - Create debugging information entry for a 'friend'. -DIType DIBuilder::createFriend(DIType Ty, DIType FriendTy) { - // typedefs are encoded in DIDerivedType format. - assert(Ty.Verify() && "Invalid type!"); - assert(FriendTy.Verify() && "Invalid friend type!"); - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_friend), - Ty, - NULL, // Name - Ty.getFile(), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Line - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Size - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Align - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Offset - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Flags - FriendTy - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createInheritance - Create debugging information entry to establish -/// inheritance relationship between two types. -DIType DIBuilder::createInheritance(DIType Ty, DIType BaseTy, - uint64_t BaseOffset, unsigned Flags) { - assert(Ty.Verify() && "Unable to create inheritance"); - // TAG_inheritance is encoded in DIDerivedType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_inheritance), - Ty, - NULL, // Name - Ty.getFile(), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), // Line - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Size - ConstantInt::get(Type::getInt64Ty(VMContext), 0), // Align - ConstantInt::get(Type::getInt64Ty(VMContext), BaseOffset), - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - BaseTy - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createMemberType - Create debugging information entry for a member. -DIType DIBuilder::createMemberType(DIDescriptor Scope, StringRef Name, - DIFile File, unsigned LineNumber, - uint64_t SizeInBits, uint64_t AlignInBits, - uint64_t OffsetInBits, unsigned Flags, - DIType Ty) { - // TAG_member is encoded in DIDerivedType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_member), - getNonCompileUnitScope(Scope), - 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 - }; - 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), - getNonCompileUnitScope(File), - 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)); -} - -/// 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, MDNode *PropertyNode) { - // TAG_member is encoded in DIDerivedType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_member), - getNonCompileUnitScope(File), - 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, - PropertyNode - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createObjCProperty - Create debugging information entry for Objective-C -/// property. -DIObjCProperty DIBuilder::createObjCProperty(StringRef Name, - DIFile File, unsigned LineNumber, - StringRef GetterName, - StringRef SetterName, - unsigned PropertyAttributes, - DIType Ty) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_APPLE_property), - MDString::get(VMContext, Name), - File, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - MDString::get(VMContext, GetterName), - MDString::get(VMContext, SetterName), - ConstantInt::get(Type::getInt32Ty(VMContext), PropertyAttributes), - Ty - }; - return DIObjCProperty(MDNode::get(VMContext, Elts)); -} - -/// createClassType - Create debugging information entry for a class. -DIType DIBuilder::createClassType(DIDescriptor Context, StringRef Name, - DIFile File, unsigned LineNumber, - uint64_t SizeInBits, uint64_t AlignInBits, - uint64_t OffsetInBits, unsigned Flags, - DIType DerivedFrom, DIArray Elements, - MDNode *VTableHolder, MDNode *TemplateParams) { - // TAG_class_type is encoded in DICompositeType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_class_type), - getNonCompileUnitScope(Context), - 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::getInt32Ty(VMContext), OffsetInBits), - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - DerivedFrom, - Elements, - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - VTableHolder, - TemplateParams - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createTemplateTypeParameter - Create debugging information for template -/// type parameter. -DITemplateTypeParameter -DIBuilder::createTemplateTypeParameter(DIDescriptor Context, StringRef Name, - DIType Ty, MDNode *File, unsigned LineNo, - unsigned ColumnNo) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_template_type_parameter), - getNonCompileUnitScope(Context), - MDString::get(VMContext, Name), - Ty, - File, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - ConstantInt::get(Type::getInt32Ty(VMContext), ColumnNo) - }; - return DITemplateTypeParameter(MDNode::get(VMContext, Elts)); -} - -/// createTemplateValueParameter - Create debugging information for template -/// value parameter. -DITemplateValueParameter -DIBuilder::createTemplateValueParameter(DIDescriptor Context, StringRef Name, - DIType Ty, uint64_t Val, - MDNode *File, unsigned LineNo, - unsigned ColumnNo) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_template_value_parameter), - getNonCompileUnitScope(Context), - MDString::get(VMContext, Name), - Ty, - ConstantInt::get(Type::getInt64Ty(VMContext), Val), - File, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - ConstantInt::get(Type::getInt32Ty(VMContext), ColumnNo) - }; - return DITemplateValueParameter(MDNode::get(VMContext, Elts)); -} - -/// createStructType - Create debugging information entry for a struct. -DIType DIBuilder::createStructType(DIDescriptor Context, StringRef Name, - DIFile File, unsigned LineNumber, - uint64_t SizeInBits, uint64_t AlignInBits, - unsigned Flags, DIArray Elements, - unsigned RunTimeLang) { - // TAG_structure_type is encoded in DICompositeType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_structure_type), - getNonCompileUnitScope(Context), - 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::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - NULL, - Elements, - ConstantInt::get(Type::getInt32Ty(VMContext), RunTimeLang), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createUnionType - Create debugging information entry for an union. -DIType DIBuilder::createUnionType(DIDescriptor Scope, StringRef Name, - DIFile File, - unsigned LineNumber, uint64_t SizeInBits, - uint64_t AlignInBits, unsigned Flags, - DIArray Elements, unsigned RunTimeLang) { - // TAG_union_type is encoded in DICompositeType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_union_type), - getNonCompileUnitScope(Scope), - 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), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - NULL, - Elements, - ConstantInt::get(Type::getInt32Ty(VMContext), RunTimeLang), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createSubroutineType - Create subroutine type. -DIType DIBuilder::createSubroutineType(DIFile File, DIArray ParameterTypes) { - // TAG_subroutine_type is encoded in DICompositeType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_subroutine_type), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - MDString::get(VMContext, ""), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt64Ty(VMContext), 0), - ConstantInt::get(Type::getInt64Ty(VMContext), 0), - ConstantInt::get(Type::getInt64Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - NULL, - ParameterTypes, - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createEnumerationType - Create debugging information entry for an -/// enumeration. -DIType DIBuilder::createEnumerationType(DIDescriptor Scope, StringRef Name, - DIFile File, unsigned LineNumber, - uint64_t SizeInBits, - uint64_t AlignInBits, - DIArray Elements) { - // TAG_enumeration_type is encoded in DICompositeType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_enumeration_type), - getNonCompileUnitScope(Scope), - 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::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - NULL, - Elements, - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - }; - MDNode *Node = MDNode::get(VMContext, Elts); - AllEnumTypes.push_back(Node); - return DIType(Node); -} - -/// createArrayType - Create debugging information entry for an array. -DIType DIBuilder::createArrayType(uint64_t Size, uint64_t AlignInBits, - DIType Ty, DIArray Subscripts) { - // TAG_array_type is encoded in DICompositeType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_array_type), - NULL, //TheCU, - MDString::get(VMContext, ""), - NULL, //TheCU, - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt64Ty(VMContext), Size), - ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - Ty, - Subscripts, - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createVectorType - Create debugging information entry for a vector. -DIType DIBuilder::createVectorType(uint64_t Size, uint64_t AlignInBits, - DIType Ty, DIArray Subscripts) { - // TAG_vector_type is encoded in DICompositeType format. - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_vector_type), - NULL, //TheCU, - MDString::get(VMContext, ""), - NULL, //TheCU, - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt64Ty(VMContext), Size), - ConstantInt::get(Type::getInt64Ty(VMContext), AlignInBits), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - Ty, - Subscripts, - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - }; - return DIType(MDNode::get(VMContext, Elts)); -} - -/// createArtificialType - Create a new DIType with "artificial" flag set. -DIType DIBuilder::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)); -} - -/// retainType - Retain DIType in a module even if it is not referenced -/// through debug info anchors. -void DIBuilder::retainType(DIType T) { - AllRetainTypes.push_back(T); -} - -/// createUnspecifiedParameter - Create unspeicified type descriptor -/// for the subroutine type. -DIDescriptor DIBuilder::createUnspecifiedParameter() { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_unspecified_parameters) - }; - return DIDescriptor(MDNode::get(VMContext, Elts)); -} - -/// createTemporaryType - Create a temporary forward-declared type. -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); - return DIType(Node); -} - -/// createTemporaryType - Create a temporary forward-declared type. -DIType DIBuilder::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(VMContext, DW_TAG_base_type), - TheCU, - NULL, - F - }; - MDNode *Node = MDNode::getTemporary(VMContext, Elts); - return DIType(Node); -} - -/// createForwardDecl - Create a temporary forward-declared type that -/// can be RAUW'd if the full type is seen. -DIType DIBuilder::createForwardDecl(unsigned Tag, StringRef Name, DIFile F, - unsigned Line, unsigned RuntimeLang) { - // Create a temporary MDNode. - Value *Elts[] = { - GetTagConstant(VMContext, Tag), - NULL, // TheCU - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), Line), - // To ease transition include sizes etc of 0. - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), - DIDescriptor::FlagFwdDecl), - NULL, - DIArray(), - ConstantInt::get(Type::getInt32Ty(VMContext), RuntimeLang) - }; - MDNode *Node = MDNode::getTemporary(VMContext, Elts); - return DIType(Node); -} - -/// getOrCreateArray - Get a DIArray, create one if required. -DIArray DIBuilder::getOrCreateArray(ArrayRef<Value *> Elements) { - if (Elements.empty()) { - Value *Null = llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)); - return DIArray(MDNode::get(VMContext, Null)); - } - return DIArray(MDNode::get(VMContext, Elements)); -} - -/// getOrCreateSubrange - Create a descriptor for a value range. This -/// implicitly uniques the values returned. -DISubrange DIBuilder::getOrCreateSubrange(int64_t Lo, int64_t Hi) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_subrange_type), - ConstantInt::get(Type::getInt64Ty(VMContext), Lo), - ConstantInt::get(Type::getInt64Ty(VMContext), Hi) - }; - - return DISubrange(MDNode::get(VMContext, Elts)); -} - -/// createGlobalVariable - Create a new descriptor for the specified global. -DIGlobalVariable DIBuilder:: -createGlobalVariable(StringRef Name, DIFile F, unsigned LineNumber, - DIType Ty, bool isLocalToUnit, llvm::Value *Val) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_variable), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - NULL, // TheCU, - MDString::get(VMContext, Name), - MDString::get(VMContext, Name), - MDString::get(VMContext, Name), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - Ty, - ConstantInt::get(Type::getInt32Ty(VMContext), isLocalToUnit), - ConstantInt::get(Type::getInt32Ty(VMContext), 1), /* isDefinition*/ - Val - }; - MDNode *Node = MDNode::get(VMContext, Elts); - AllGVs.push_back(Node); - return DIGlobalVariable(Node); -} - -/// createStaticVariable - Create a new descriptor for the specified static -/// variable. -DIGlobalVariable DIBuilder:: -createStaticVariable(DIDescriptor Context, StringRef Name, - StringRef LinkageName, DIFile F, unsigned LineNumber, - DIType Ty, bool isLocalToUnit, llvm::Value *Val) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_variable), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - getNonCompileUnitScope(Context), - MDString::get(VMContext, Name), - MDString::get(VMContext, Name), - MDString::get(VMContext, LinkageName), - F, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNumber), - Ty, - ConstantInt::get(Type::getInt32Ty(VMContext), isLocalToUnit), - ConstantInt::get(Type::getInt32Ty(VMContext), 1), /* isDefinition*/ - Val - }; - MDNode *Node = MDNode::get(VMContext, Elts); - AllGVs.push_back(Node); - return DIGlobalVariable(Node); -} - -/// createVariable - Create a new descriptor for the specified variable. -DIVariable DIBuilder::createLocalVariable(unsigned Tag, DIDescriptor Scope, - StringRef Name, DIFile File, - unsigned LineNo, DIType Ty, - bool AlwaysPreserve, unsigned Flags, - unsigned ArgNo) { - Value *Elts[] = { - GetTagConstant(VMContext, Tag), - getNonCompileUnitScope(Scope), - MDString::get(VMContext, Name), - File, - ConstantInt::get(Type::getInt32Ty(VMContext), (LineNo | (ArgNo << 24))), - Ty, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - Constant::getNullValue(Type::getInt32Ty(VMContext)), - }; - 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 - // named mdnode. - DISubprogram Fn(getDISubprogram(Scope)); - NamedMDNode *FnLocals = getOrInsertFnSpecificMDNode(M, Fn); - 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 DIBuilder::createComplexVariable(unsigned Tag, DIDescriptor Scope, - StringRef Name, DIFile F, - unsigned LineNo, - DIType Ty, ArrayRef<Value *> Addr, - unsigned ArgNo) { - SmallVector<Value *, 15> Elts; - Elts.push_back(GetTagConstant(VMContext, Tag)); - Elts.push_back(getNonCompileUnitScope(Scope)), - Elts.push_back(MDString::get(VMContext, Name)); - Elts.push_back(F); - Elts.push_back(ConstantInt::get(Type::getInt32Ty(VMContext), - (LineNo | (ArgNo << 24)))); - Elts.push_back(Ty); - Elts.push_back(llvm::Constant::getNullValue(Type::getInt32Ty(VMContext))); - Elts.push_back(llvm::Constant::getNullValue(Type::getInt32Ty(VMContext))); - Elts.append(Addr.begin(), Addr.end()); - - return DIVariable(MDNode::get(VMContext, Elts)); -} - -/// createFunction - Create a new descriptor for the specified function. -DISubprogram DIBuilder::createFunction(DIDescriptor Context, - StringRef Name, - StringRef LinkageName, - DIFile File, unsigned LineNo, - DIType Ty, - bool isLocalToUnit, bool isDefinition, - unsigned ScopeLine, - unsigned Flags, bool isOptimized, - Function *Fn, - MDNode *TParams, - MDNode *Decl) { - Value *TElts[] = { GetTagConstant(VMContext, DW_TAG_base_type) }; - MDNode *Temp = MDNode::getTemporary(VMContext, TElts); - Value *TVElts[] = { Temp }; - MDNode *THolder = MDNode::get(VMContext, TVElts); - - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_subprogram), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - getNonCompileUnitScope(Context), - MDString::get(VMContext, Name), - MDString::get(VMContext, Name), - MDString::get(VMContext, LinkageName), - File, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo), - Ty, - ConstantInt::get(Type::getInt1Ty(VMContext), isLocalToUnit), - ConstantInt::get(Type::getInt1Ty(VMContext), isDefinition), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - ConstantInt::get(Type::getInt32Ty(VMContext), 0), - NULL, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), - Fn, - TParams, - Decl, - THolder, - ConstantInt::get(Type::getInt32Ty(VMContext), ScopeLine) - }; - MDNode *Node = MDNode::get(VMContext, Elts); - - // Create a named metadata so that we do not lose this mdnode. - AllSubprograms.push_back(Node); - return DISubprogram(Node); -} - -/// createMethod - Create a new descriptor for the specified C++ method. -DISubprogram DIBuilder::createMethod(DIDescriptor Context, - StringRef Name, - StringRef LinkageName, - DIFile F, - unsigned LineNo, DIType Ty, - bool isLocalToUnit, - bool isDefinition, - unsigned VK, unsigned VIndex, - MDNode *VTableHolder, - unsigned Flags, - bool isOptimized, - Function *Fn, - MDNode *TParam) { - Value *TElts[] = { GetTagConstant(VMContext, DW_TAG_base_type) }; - MDNode *Temp = MDNode::getTemporary(VMContext, TElts); - Value *TVElts[] = { Temp }; - MDNode *THolder = MDNode::get(VMContext, TVElts); - - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_subprogram), - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - getNonCompileUnitScope(Context), - MDString::get(VMContext, Name), - MDString::get(VMContext, Name), - 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), - VTableHolder, - ConstantInt::get(Type::getInt32Ty(VMContext), Flags), - ConstantInt::get(Type::getInt1Ty(VMContext), isOptimized), - Fn, - TParam, - llvm::Constant::getNullValue(Type::getInt32Ty(VMContext)), - THolder, - // FIXME: Do we want to use a different scope lines? - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo) - }; - MDNode *Node = MDNode::get(VMContext, Elts); - return DISubprogram(Node); -} - -/// createNameSpace - This creates new descriptor for a namespace -/// with the specified parent scope. -DINameSpace DIBuilder::createNameSpace(DIDescriptor Scope, StringRef Name, - DIFile File, unsigned LineNo) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_namespace), - getNonCompileUnitScope(Scope), - MDString::get(VMContext, Name), - File, - ConstantInt::get(Type::getInt32Ty(VMContext), LineNo) - }; - return DINameSpace(MDNode::get(VMContext, Elts)); -} - -/// createLexicalBlockFile - This creates a new MDNode that encapsulates -/// an existing scope with a new filename. -DILexicalBlockFile DIBuilder::createLexicalBlockFile(DIDescriptor Scope, - DIFile File) { - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_lexical_block), - Scope, - File - }; - return DILexicalBlockFile(MDNode::get(VMContext, Elts)); -} - -DILexicalBlock DIBuilder::createLexicalBlock(DIDescriptor Scope, DIFile File, - unsigned Line, unsigned Col) { - // Defeat MDNode uniqing for lexical blocks by using unique id. - static unsigned int unique_id = 0; - Value *Elts[] = { - GetTagConstant(VMContext, dwarf::DW_TAG_lexical_block), - getNonCompileUnitScope(Scope), - ConstantInt::get(Type::getInt32Ty(VMContext), Line), - ConstantInt::get(Type::getInt32Ty(VMContext), Col), - File, - ConstantInt::get(Type::getInt32Ty(VMContext), unique_id++) - }; - return DILexicalBlock(MDNode::get(VMContext, Elts)); -} - -/// insertDeclare - Insert a new llvm.dbg.declare intrinsic call. -Instruction *DIBuilder::insertDeclare(Value *Storage, DIVariable VarInfo, - Instruction *InsertBefore) { - assert(Storage && "no storage passed to dbg.declare"); - assert(VarInfo.Verify() && "empty DIVariable passed to dbg.declare"); - if (!DeclareFn) - DeclareFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_declare); - - Value *Args[] = { MDNode::get(Storage->getContext(), Storage), VarInfo }; - return CallInst::Create(DeclareFn, Args, "", InsertBefore); -} - -/// insertDeclare - Insert a new llvm.dbg.declare intrinsic call. -Instruction *DIBuilder::insertDeclare(Value *Storage, DIVariable VarInfo, - BasicBlock *InsertAtEnd) { - assert(Storage && "no storage passed to dbg.declare"); - assert(VarInfo.Verify() && "invalid DIVariable passed to dbg.declare"); - if (!DeclareFn) - DeclareFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_declare); - - Value *Args[] = { MDNode::get(Storage->getContext(), Storage), VarInfo }; - - // If this block already has a terminator then insert this intrinsic - // before the terminator. - if (TerminatorInst *T = InsertAtEnd->getTerminator()) - return CallInst::Create(DeclareFn, Args, "", T); - else - return CallInst::Create(DeclareFn, Args, "", InsertAtEnd); -} - -/// insertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call. -Instruction *DIBuilder::insertDbgValueIntrinsic(Value *V, uint64_t Offset, - DIVariable VarInfo, - Instruction *InsertBefore) { - assert(V && "no value passed to dbg.value"); - assert(VarInfo.Verify() && "invalid DIVariable passed to dbg.value"); - if (!ValueFn) - ValueFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_value); - - Value *Args[] = { MDNode::get(V->getContext(), V), - ConstantInt::get(Type::getInt64Ty(V->getContext()), Offset), - VarInfo }; - return CallInst::Create(ValueFn, Args, "", InsertBefore); -} - -/// insertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call. -Instruction *DIBuilder::insertDbgValueIntrinsic(Value *V, uint64_t Offset, - DIVariable VarInfo, - BasicBlock *InsertAtEnd) { - assert(V && "no value passed to dbg.value"); - assert(VarInfo.Verify() && "invalid DIVariable passed to dbg.value"); - if (!ValueFn) - ValueFn = Intrinsic::getDeclaration(&M, Intrinsic::dbg_value); - - Value *Args[] = { MDNode::get(V->getContext(), V), - ConstantInt::get(Type::getInt64Ty(V->getContext()), Offset), - VarInfo }; - return CallInst::Create(ValueFn, Args, "", InsertAtEnd); -} diff --git a/lib/Analysis/DbgInfoPrinter.cpp b/lib/Analysis/DbgInfoPrinter.cpp index cd832ab..41cd34c 100644 --- a/lib/Analysis/DbgInfoPrinter.cpp +++ b/lib/Analysis/DbgInfoPrinter.cpp @@ -16,14 +16,14 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Pass.h" +#include "llvm/DebugInfo.h" #include "llvm/Function.h" #include "llvm/IntrinsicInst.h" #include "llvm/Metadata.h" #include "llvm/Module.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/Analysis/DebugInfo.h" +#include "llvm/Pass.h" #include "llvm/Analysis/Passes.h" +#include "llvm/Assembly/Writer.h" #include "llvm/Support/CFG.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/raw_ostream.h" diff --git a/lib/Analysis/DebugInfo.cpp b/lib/Analysis/DebugInfo.cpp deleted file mode 100644 index f61a8f3..0000000 --- a/lib/Analysis/DebugInfo.cpp +++ /dev/null @@ -1,1229 +0,0 @@ -//===--- DebugInfo.cpp - Debug Information Helper Classes -----------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the helper classes used to build and interpret debug -// information in LLVM IR form. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DebugInfo.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Intrinsics.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" -#include "llvm/Analysis/ValueTracking.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallString.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Dwarf.h" -#include "llvm/Support/raw_ostream.h" -using namespace llvm; -using namespace llvm::dwarf; - -//===----------------------------------------------------------------------===// -// DIDescriptor -//===----------------------------------------------------------------------===// - -DIDescriptor::DIDescriptor(const DIFile F) : DbgNode(F.DbgNode) { -} - -DIDescriptor::DIDescriptor(const DISubprogram F) : DbgNode(F.DbgNode) { -} - -DIDescriptor::DIDescriptor(const DILexicalBlockFile F) : DbgNode(F.DbgNode) { -} - -DIDescriptor::DIDescriptor(const DILexicalBlock F) : DbgNode(F.DbgNode) { -} - -DIDescriptor::DIDescriptor(const DIVariable F) : DbgNode(F.DbgNode) { -} - -DIDescriptor::DIDescriptor(const DIType F) : DbgNode(F.DbgNode) { -} - -StringRef -DIDescriptor::getStringField(unsigned Elt) const { - if (DbgNode == 0) - return StringRef(); - - if (Elt < DbgNode->getNumOperands()) - if (MDString *MDS = dyn_cast_or_null<MDString>(DbgNode->getOperand(Elt))) - return MDS->getString(); - - return StringRef(); -} - -uint64_t DIDescriptor::getUInt64Field(unsigned Elt) const { - if (DbgNode == 0) - return 0; - - if (Elt < DbgNode->getNumOperands()) - if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(DbgNode->getOperand(Elt))) - return CI->getZExtValue(); - - return 0; -} - -DIDescriptor DIDescriptor::getDescriptorField(unsigned Elt) const { - if (DbgNode == 0) - return DIDescriptor(); - - if (Elt < DbgNode->getNumOperands()) - return - DIDescriptor(dyn_cast_or_null<const MDNode>(DbgNode->getOperand(Elt))); - return DIDescriptor(); -} - -GlobalVariable *DIDescriptor::getGlobalVariableField(unsigned Elt) const { - if (DbgNode == 0) - return 0; - - if (Elt < DbgNode->getNumOperands()) - return dyn_cast_or_null<GlobalVariable>(DbgNode->getOperand(Elt)); - return 0; -} - -Constant *DIDescriptor::getConstantField(unsigned Elt) const { - if (DbgNode == 0) - return 0; - - if (Elt < DbgNode->getNumOperands()) - return dyn_cast_or_null<Constant>(DbgNode->getOperand(Elt)); - return 0; -} - -Function *DIDescriptor::getFunctionField(unsigned Elt) const { - if (DbgNode == 0) - return 0; - - if (Elt < DbgNode->getNumOperands()) - return dyn_cast_or_null<Function>(DbgNode->getOperand(Elt)); - return 0; -} - -unsigned DIVariable::getNumAddrElements() const { - if (getVersion() <= llvm::LLVMDebugVersion8) - return DbgNode->getNumOperands()-6; - if (getVersion() == llvm::LLVMDebugVersion9) - return DbgNode->getNumOperands()-7; - return DbgNode->getNumOperands()-8; -} - -/// getInlinedAt - If this variable is inlined then return inline location. -MDNode *DIVariable::getInlinedAt() const { - if (getVersion() <= llvm::LLVMDebugVersion9) - return NULL; - return dyn_cast_or_null<MDNode>(DbgNode->getOperand(7)); -} - -//===----------------------------------------------------------------------===// -// Predicates -//===----------------------------------------------------------------------===// - -/// isBasicType - Return true if the specified tag is legal for -/// DIBasicType. -bool DIDescriptor::isBasicType() const { - if (!DbgNode) return false; - switch (getTag()) { - case dwarf::DW_TAG_base_type: - case dwarf::DW_TAG_unspecified_type: - return true; - default: - return false; - } -} - -/// isDerivedType - Return true if the specified tag is legal for DIDerivedType. -bool DIDescriptor::isDerivedType() const { - if (!DbgNode) return false; - switch (getTag()) { - case dwarf::DW_TAG_typedef: - case dwarf::DW_TAG_pointer_type: - case dwarf::DW_TAG_reference_type: - case dwarf::DW_TAG_const_type: - case dwarf::DW_TAG_volatile_type: - case dwarf::DW_TAG_restrict_type: - case dwarf::DW_TAG_member: - case dwarf::DW_TAG_inheritance: - case dwarf::DW_TAG_friend: - return true; - default: - // CompositeTypes are currently modelled as DerivedTypes. - return isCompositeType(); - } -} - -/// isCompositeType - Return true if the specified tag is legal for -/// DICompositeType. -bool DIDescriptor::isCompositeType() const { - if (!DbgNode) return false; - switch (getTag()) { - case dwarf::DW_TAG_array_type: - case dwarf::DW_TAG_structure_type: - case dwarf::DW_TAG_union_type: - case dwarf::DW_TAG_enumeration_type: - case dwarf::DW_TAG_vector_type: - case dwarf::DW_TAG_subroutine_type: - case dwarf::DW_TAG_class_type: - return true; - default: - return false; - } -} - -/// isVariable - Return true if the specified tag is legal for DIVariable. -bool DIDescriptor::isVariable() const { - if (!DbgNode) return false; - switch (getTag()) { - case dwarf::DW_TAG_auto_variable: - case dwarf::DW_TAG_arg_variable: - case dwarf::DW_TAG_return_variable: - return true; - default: - return false; - } -} - -/// isType - Return true if the specified tag is legal for DIType. -bool DIDescriptor::isType() const { - return isBasicType() || isCompositeType() || isDerivedType(); -} - -/// isSubprogram - Return true if the specified tag is legal for -/// DISubprogram. -bool DIDescriptor::isSubprogram() const { - return DbgNode && getTag() == dwarf::DW_TAG_subprogram; -} - -/// isGlobalVariable - Return true if the specified tag is legal for -/// DIGlobalVariable. -bool DIDescriptor::isGlobalVariable() const { - return DbgNode && (getTag() == dwarf::DW_TAG_variable || - getTag() == dwarf::DW_TAG_constant); -} - -/// isGlobal - Return true if the specified tag is legal for DIGlobal. -bool DIDescriptor::isGlobal() const { - return isGlobalVariable(); -} - -/// isUnspecifiedParmeter - Return true if the specified tag is -/// DW_TAG_unspecified_parameters. -bool DIDescriptor::isUnspecifiedParameter() const { - return DbgNode && getTag() == dwarf::DW_TAG_unspecified_parameters; -} - -/// isScope - Return true if the specified tag is one of the scope -/// related tag. -bool DIDescriptor::isScope() const { - if (!DbgNode) return false; - switch (getTag()) { - case dwarf::DW_TAG_compile_unit: - case dwarf::DW_TAG_lexical_block: - case dwarf::DW_TAG_subprogram: - case dwarf::DW_TAG_namespace: - return true; - default: - break; - } - return false; -} - -/// isTemplateTypeParameter - Return true if the specified tag is -/// DW_TAG_template_type_parameter. -bool DIDescriptor::isTemplateTypeParameter() const { - return DbgNode && getTag() == dwarf::DW_TAG_template_type_parameter; -} - -/// isTemplateValueParameter - Return true if the specified tag is -/// DW_TAG_template_value_parameter. -bool DIDescriptor::isTemplateValueParameter() const { - return DbgNode && getTag() == dwarf::DW_TAG_template_value_parameter; -} - -/// isCompileUnit - Return true if the specified tag is DW_TAG_compile_unit. -bool DIDescriptor::isCompileUnit() const { - return DbgNode && getTag() == dwarf::DW_TAG_compile_unit; -} - -/// isFile - Return true if the specified tag is DW_TAG_file_type. -bool DIDescriptor::isFile() const { - return DbgNode && getTag() == dwarf::DW_TAG_file_type; -} - -/// isNameSpace - Return true if the specified tag is DW_TAG_namespace. -bool DIDescriptor::isNameSpace() const { - return DbgNode && getTag() == dwarf::DW_TAG_namespace; -} - -/// isLexicalBlockFile - Return true if the specified descriptor is a -/// lexical block with an extra file. -bool DIDescriptor::isLexicalBlockFile() const { - return DbgNode && getTag() == dwarf::DW_TAG_lexical_block && - (DbgNode->getNumOperands() == 3); -} - -/// isLexicalBlock - Return true if the specified tag is DW_TAG_lexical_block. -bool DIDescriptor::isLexicalBlock() const { - return DbgNode && getTag() == dwarf::DW_TAG_lexical_block && - (DbgNode->getNumOperands() > 3); -} - -/// isSubrange - Return true if the specified tag is DW_TAG_subrange_type. -bool DIDescriptor::isSubrange() const { - return DbgNode && getTag() == dwarf::DW_TAG_subrange_type; -} - -/// isEnumerator - Return true if the specified tag is DW_TAG_enumerator. -bool DIDescriptor::isEnumerator() const { - return DbgNode && getTag() == dwarf::DW_TAG_enumerator; -} - -/// isObjCProperty - Return true if the specified tag is DW_TAG -bool DIDescriptor::isObjCProperty() const { - return DbgNode && getTag() == dwarf::DW_TAG_APPLE_property; -} -//===----------------------------------------------------------------------===// -// Simple Descriptor Constructors and other Methods -//===----------------------------------------------------------------------===// - -DIType::DIType(const MDNode *N) : DIScope(N) { - if (!N) return; - if (!isBasicType() && !isDerivedType() && !isCompositeType()) { - DbgNode = 0; - } -} - -unsigned DIArray::getNumElements() const { - if (!DbgNode) - return 0; - return DbgNode->getNumOperands(); -} - -/// replaceAllUsesWith - Replace all uses of debug info referenced by -/// this descriptor. -void DIType::replaceAllUsesWith(DIDescriptor &D) { - if (!DbgNode) - return; - - // Since we use a TrackingVH for the node, its easy for clients to manufacture - // legitimate situations where they want to replaceAllUsesWith() on something - // which, due to uniquing, has merged with the source. We shield clients from - // this detail by allowing a value to be replaced with replaceAllUsesWith() - // itself. - if (DbgNode != D) { - MDNode *Node = const_cast<MDNode*>(DbgNode); - const MDNode *DN = D; - const Value *V = cast_or_null<Value>(DN); - Node->replaceAllUsesWith(const_cast<Value*>(V)); - MDNode::deleteTemporary(Node); - } -} - -/// replaceAllUsesWith - Replace all uses of debug info referenced by -/// this descriptor. -void DIType::replaceAllUsesWith(MDNode *D) { - if (!DbgNode) - return; - - // Since we use a TrackingVH for the node, its easy for clients to manufacture - // legitimate situations where they want to replaceAllUsesWith() on something - // which, due to uniquing, has merged with the source. We shield clients from - // this detail by allowing a value to be replaced with replaceAllUsesWith() - // itself. - if (DbgNode != D) { - MDNode *Node = const_cast<MDNode*>(DbgNode); - const MDNode *DN = D; - const Value *V = cast_or_null<Value>(DN); - Node->replaceAllUsesWith(const_cast<Value*>(V)); - MDNode::deleteTemporary(Node); - } -} - -/// isUnsignedDIType - Return true if type encoding is unsigned. -bool DIType::isUnsignedDIType() { - DIDerivedType DTy(DbgNode); - if (DTy.Verify()) - return DTy.getTypeDerivedFrom().isUnsignedDIType(); - - DIBasicType BTy(DbgNode); - if (BTy.Verify()) { - unsigned Encoding = BTy.getEncoding(); - if (Encoding == dwarf::DW_ATE_unsigned || - Encoding == dwarf::DW_ATE_unsigned_char) - return true; - } - return false; -} - -/// Verify - Verify that a compile unit is well formed. -bool DICompileUnit::Verify() const { - if (!DbgNode) - return false; - StringRef N = getFilename(); - if (N.empty()) - return false; - // It is possible that directory and produce string is empty. - return true; -} - -/// Verify - Verify that an ObjC property is well formed. -bool DIObjCProperty::Verify() const { - if (!DbgNode) - return false; - unsigned Tag = getTag(); - if (Tag != dwarf::DW_TAG_APPLE_property) return false; - DIType Ty = getType(); - if (!Ty.Verify()) return false; - - // Don't worry about the rest of the strings for now. - return true; -} - -/// Verify - Verify that a type descriptor is well formed. -bool DIType::Verify() const { - if (!DbgNode) - return false; - if (getContext() && !getContext().Verify()) - return false; - unsigned Tag = getTag(); - if (!isBasicType() && Tag != dwarf::DW_TAG_const_type && - Tag != dwarf::DW_TAG_volatile_type && Tag != dwarf::DW_TAG_pointer_type && - Tag != dwarf::DW_TAG_reference_type && Tag != dwarf::DW_TAG_restrict_type - && Tag != dwarf::DW_TAG_vector_type && Tag != dwarf::DW_TAG_array_type - && Tag != dwarf::DW_TAG_enumeration_type - && Tag != dwarf::DW_TAG_subroutine_type - && getFilename().empty()) - return false; - return true; -} - -/// Verify - Verify that a basic type descriptor is well formed. -bool DIBasicType::Verify() const { - return isBasicType(); -} - -/// Verify - Verify that a derived type descriptor is well formed. -bool DIDerivedType::Verify() const { - return isDerivedType(); -} - -/// Verify - Verify that a composite type descriptor is well formed. -bool DICompositeType::Verify() const { - if (!DbgNode) - return false; - if (getContext() && !getContext().Verify()) - return false; - - return true; -} - -/// Verify - Verify that a subprogram descriptor is well formed. -bool DISubprogram::Verify() const { - if (!DbgNode) - return false; - - if (getContext() && !getContext().Verify()) - return false; - - DICompositeType Ty = getType(); - if (!Ty.Verify()) - return false; - return true; -} - -/// Verify - Verify that a global variable descriptor is well formed. -bool DIGlobalVariable::Verify() const { - if (!DbgNode) - return false; - - if (getDisplayName().empty()) - return false; - - if (getContext() && !getContext().Verify()) - return false; - - DIType Ty = getType(); - if (!Ty.Verify()) - return false; - - if (!getGlobal() && !getConstant()) - return false; - - return true; -} - -/// Verify - Verify that a variable descriptor is well formed. -bool DIVariable::Verify() const { - if (!DbgNode) - return false; - - if (getContext() && !getContext().Verify()) - return false; - - DIType Ty = getType(); - if (!Ty.Verify()) - return false; - - return true; -} - -/// Verify - Verify that a location descriptor is well formed. -bool DILocation::Verify() const { - if (!DbgNode) - return false; - - return DbgNode->getNumOperands() == 4; -} - -/// Verify - Verify that a namespace descriptor is well formed. -bool DINameSpace::Verify() const { - if (!DbgNode) - return false; - if (getName().empty()) - return false; - return true; -} - -/// getOriginalTypeSize - If this type is derived from a base type then -/// return base type size. -uint64_t DIDerivedType::getOriginalTypeSize() const { - unsigned Tag = getTag(); - - if (Tag == dwarf::DW_TAG_member || Tag == dwarf::DW_TAG_typedef || - Tag == dwarf::DW_TAG_const_type || Tag == dwarf::DW_TAG_volatile_type || - Tag == dwarf::DW_TAG_restrict_type) { - DIType BaseType = getTypeDerivedFrom(); - // If this type is not derived from any type then take conservative - // approach. - if (!BaseType.isValid()) - return getSizeInBits(); - // If this is a derived type, go ahead and get the base type, unless - // it's a reference then it's just the size of the field. Pointer types - // have no need of this since they're a different type of qualification - // on the type. - if (BaseType.getTag() == dwarf::DW_TAG_reference_type) - return getSizeInBits(); - else if (BaseType.isDerivedType()) - return DIDerivedType(BaseType).getOriginalTypeSize(); - else - return BaseType.getSizeInBits(); - } - - return getSizeInBits(); -} - -/// getObjCProperty - Return property node, if this ivar is associated with one. -MDNode *DIDerivedType::getObjCProperty() const { - if (getVersion() <= LLVMDebugVersion11 || DbgNode->getNumOperands() <= 10) - return NULL; - return dyn_cast_or_null<MDNode>(DbgNode->getOperand(10)); -} - -/// isInlinedFnArgument - Return true if this variable provides debugging -/// information for an inlined function arguments. -bool DIVariable::isInlinedFnArgument(const Function *CurFn) { - assert(CurFn && "Invalid function"); - if (!getContext().isSubprogram()) - return false; - // This variable is not inlined function argument if its scope - // does not describe current function. - return !(DISubprogram(getContext()).describes(CurFn)); -} - -/// describes - Return true if this subprogram provides debugging -/// information for the function F. -bool DISubprogram::describes(const Function *F) { - assert(F && "Invalid function"); - if (F == getFunction()) - return true; - StringRef Name = getLinkageName(); - if (Name.empty()) - Name = getName(); - if (F->getName() == Name) - return true; - return false; -} - -unsigned DISubprogram::isOptimized() const { - assert (DbgNode && "Invalid subprogram descriptor!"); - if (DbgNode->getNumOperands() == 16) - return getUnsignedField(15); - return 0; -} - -MDNode *DISubprogram::getVariablesNodes() const { - if (!DbgNode || DbgNode->getNumOperands() <= 19) - return NULL; - if (MDNode *Temp = dyn_cast_or_null<MDNode>(DbgNode->getOperand(19))) - return dyn_cast_or_null<MDNode>(Temp->getOperand(0)); - return NULL; -} - -DIArray DISubprogram::getVariables() const { - if (!DbgNode || DbgNode->getNumOperands() <= 19) - return DIArray(); - if (MDNode *T = dyn_cast_or_null<MDNode>(DbgNode->getOperand(19))) - if (MDNode *A = dyn_cast_or_null<MDNode>(T->getOperand(0))) - return DIArray(A); - return DIArray(); -} - -StringRef DIScope::getFilename() const { - if (!DbgNode) - return StringRef(); - if (isLexicalBlockFile()) - return DILexicalBlockFile(DbgNode).getFilename(); - if (isLexicalBlock()) - return DILexicalBlock(DbgNode).getFilename(); - if (isSubprogram()) - return DISubprogram(DbgNode).getFilename(); - if (isCompileUnit()) - return DICompileUnit(DbgNode).getFilename(); - if (isNameSpace()) - return DINameSpace(DbgNode).getFilename(); - if (isType()) - return DIType(DbgNode).getFilename(); - if (isFile()) - return DIFile(DbgNode).getFilename(); - llvm_unreachable("Invalid DIScope!"); -} - -StringRef DIScope::getDirectory() const { - if (!DbgNode) - return StringRef(); - if (isLexicalBlockFile()) - return DILexicalBlockFile(DbgNode).getDirectory(); - if (isLexicalBlock()) - return DILexicalBlock(DbgNode).getDirectory(); - if (isSubprogram()) - return DISubprogram(DbgNode).getDirectory(); - if (isCompileUnit()) - return DICompileUnit(DbgNode).getDirectory(); - if (isNameSpace()) - return DINameSpace(DbgNode).getDirectory(); - if (isType()) - return DIType(DbgNode).getDirectory(); - if (isFile()) - return DIFile(DbgNode).getDirectory(); - llvm_unreachable("Invalid DIScope!"); -} - -DIArray DICompileUnit::getEnumTypes() const { - if (!DbgNode || DbgNode->getNumOperands() < 14) - return DIArray(); - - if (MDNode *N = dyn_cast_or_null<MDNode>(DbgNode->getOperand(10))) - if (MDNode *A = dyn_cast_or_null<MDNode>(N->getOperand(0))) - return DIArray(A); - return DIArray(); -} - -DIArray DICompileUnit::getRetainedTypes() const { - if (!DbgNode || DbgNode->getNumOperands() < 14) - return DIArray(); - - if (MDNode *N = dyn_cast_or_null<MDNode>(DbgNode->getOperand(11))) - if (MDNode *A = dyn_cast_or_null<MDNode>(N->getOperand(0))) - return DIArray(A); - return DIArray(); -} - -DIArray DICompileUnit::getSubprograms() const { - if (!DbgNode || DbgNode->getNumOperands() < 14) - return DIArray(); - - if (MDNode *N = dyn_cast_or_null<MDNode>(DbgNode->getOperand(12))) - if (MDNode *A = dyn_cast_or_null<MDNode>(N->getOperand(0))) - return DIArray(A); - return DIArray(); -} - - -DIArray DICompileUnit::getGlobalVariables() const { - if (!DbgNode || DbgNode->getNumOperands() < 14) - return DIArray(); - - if (MDNode *N = dyn_cast_or_null<MDNode>(DbgNode->getOperand(13))) - if (MDNode *A = dyn_cast_or_null<MDNode>(N->getOperand(0))) - return DIArray(A); - return DIArray(); -} - -//===----------------------------------------------------------------------===// -// DIDescriptor: vtable anchors for all descriptors. -//===----------------------------------------------------------------------===// - -void DIScope::anchor() { } - -void DICompileUnit::anchor() { } - -void DIFile::anchor() { } - -void DIType::anchor() { } - -void DIBasicType::anchor() { } - -void DIDerivedType::anchor() { } - -void DICompositeType::anchor() { } - -void DISubprogram::anchor() { } - -void DILexicalBlock::anchor() { } - -void DINameSpace::anchor() { } - -void DILexicalBlockFile::anchor() { } - -//===----------------------------------------------------------------------===// -// DIDescriptor: dump routines for all descriptors. -//===----------------------------------------------------------------------===// - - -/// print - Print descriptor. -void DIDescriptor::print(raw_ostream &OS) const { - OS << "[" << dwarf::TagString(getTag()) << "] "; - OS.write_hex((intptr_t) &*DbgNode) << ']'; -} - -/// print - Print compile unit. -void DICompileUnit::print(raw_ostream &OS) const { - if (getLanguage()) - OS << " [" << dwarf::LanguageString(getLanguage()) << "] "; - - OS << " [" << getDirectory() << "/" << getFilename() << "]"; -} - -/// print - Print type. -void DIType::print(raw_ostream &OS) const { - if (!DbgNode) return; - - StringRef Res = getName(); - if (!Res.empty()) - OS << " [" << Res << "] "; - - unsigned Tag = getTag(); - OS << " [" << dwarf::TagString(Tag) << "] "; - - // TODO : Print context - OS << " [" - << "line " << getLineNumber() << ", " - << getSizeInBits() << " bits, " - << getAlignInBits() << " bit alignment, " - << getOffsetInBits() << " bit offset" - << "] "; - - if (isPrivate()) - OS << " [private] "; - else if (isProtected()) - OS << " [protected] "; - - if (isForwardDecl()) - OS << " [fwd] "; - - if (isBasicType()) - DIBasicType(DbgNode).print(OS); - else if (isDerivedType()) { - DIDerivedType DTy = DIDerivedType(DbgNode); - DTy.print(OS); - DICompositeType CTy = getDICompositeType(DTy); - if (CTy.Verify()) - CTy.print(OS); - } - else if (isCompositeType()) - DICompositeType(DbgNode).print(OS); - else { - OS << "Invalid DIType\n"; - return; - } - - OS << "\n"; -} - -/// print - Print basic type. -void DIBasicType::print(raw_ostream &OS) const { - OS << " [" << dwarf::AttributeEncodingString(getEncoding()) << "] "; -} - -/// print - Print derived type. -void DIDerivedType::print(raw_ostream &OS) const { - OS << "\n\t Derived From: "; - getTypeDerivedFrom().print(OS); - OS << "\n\t"; -} - -/// print - Print composite type. -void DICompositeType::print(raw_ostream &OS) const { - DIArray A = getTypeArray(); - OS << " [" << A.getNumElements() << " elements]"; -} - -/// print - Print subprogram. -void DISubprogram::print(raw_ostream &OS) const { - StringRef Res = getName(); - if (!Res.empty()) - OS << " [" << Res << "] "; - - unsigned Tag = getTag(); - OS << " [" << dwarf::TagString(Tag) << "] "; - - // TODO : Print context - OS << " [" << getLineNumber() << "] "; - - if (isLocalToUnit()) - OS << " [local] "; - - if (isDefinition()) - OS << " [def] "; - - if (getScopeLineNumber() != getLineNumber()) - OS << " [Scope: " << getScopeLineNumber() << "] "; - - OS << "\n"; -} - -/// print - Print global variable. -void DIGlobalVariable::print(raw_ostream &OS) const { - OS << " ["; - StringRef Res = getName(); - if (!Res.empty()) - OS << " [" << Res << "] "; - - unsigned Tag = getTag(); - OS << " [" << dwarf::TagString(Tag) << "] "; - - // TODO : Print context - OS << " [" << getLineNumber() << "] "; - - if (isLocalToUnit()) - OS << " [local] "; - - if (isDefinition()) - OS << " [def] "; - - if (isGlobalVariable()) - DIGlobalVariable(DbgNode).print(OS); - OS << "]\n"; -} - -static void printDebugLoc(DebugLoc DL, raw_ostream &CommentOS, - const LLVMContext &Ctx) { - if (!DL.isUnknown()) { // Print source line info. - DIScope Scope(DL.getScope(Ctx)); - // Omit the directory, because it's likely to be long and uninteresting. - if (Scope.Verify()) - CommentOS << Scope.getFilename(); - else - CommentOS << "<unknown>"; - CommentOS << ':' << DL.getLine(); - if (DL.getCol() != 0) - CommentOS << ':' << DL.getCol(); - DebugLoc InlinedAtDL = DebugLoc::getFromDILocation(DL.getInlinedAt(Ctx)); - if (!InlinedAtDL.isUnknown()) { - CommentOS << " @[ "; - printDebugLoc(InlinedAtDL, CommentOS, Ctx); - CommentOS << " ]"; - } - } -} - -void DIVariable::printExtendedName(raw_ostream &OS) const { - const LLVMContext &Ctx = DbgNode->getContext(); - StringRef Res = getName(); - if (!Res.empty()) - OS << Res << "," << getLineNumber(); - if (MDNode *InlinedAt = getInlinedAt()) { - DebugLoc InlinedAtDL = DebugLoc::getFromDILocation(InlinedAt); - if (!InlinedAtDL.isUnknown()) { - OS << " @["; - printDebugLoc(InlinedAtDL, OS, Ctx); - OS << "]"; - } - } -} - -/// print - Print variable. -void DIVariable::print(raw_ostream &OS) const { - StringRef Res = getName(); - if (!Res.empty()) - OS << " [" << Res << "] "; - - OS << " [" << getLineNumber() << "] "; - getType().print(OS); - OS << "\n"; - - // FIXME: Dump complex addresses -} - -/// dump - Print descriptor to dbgs() with a newline. -void DIDescriptor::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print compile unit to dbgs() with a newline. -void DICompileUnit::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print type to dbgs() with a newline. -void DIType::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print basic type to dbgs() with a newline. -void DIBasicType::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print derived type to dbgs() with a newline. -void DIDerivedType::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print composite type to dbgs() with a newline. -void DICompositeType::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print subprogram to dbgs() with a newline. -void DISubprogram::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print global variable. -void DIGlobalVariable::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// dump - Print variable. -void DIVariable::dump() const { - print(dbgs()); dbgs() << '\n'; -} - -/// fixupObjcLikeName - Replace contains special characters used -/// in a typical Objective-C names with '.' in a given string. -static void fixupObjcLikeName(StringRef Str, SmallVectorImpl<char> &Out) { - bool isObjCLike = false; - for (size_t i = 0, e = Str.size(); i < e; ++i) { - char C = Str[i]; - if (C == '[') - isObjCLike = true; - - if (isObjCLike && (C == '[' || C == ']' || C == ' ' || C == ':' || - C == '+' || C == '(' || C == ')')) - Out.push_back('.'); - else - Out.push_back(C); - } -} - -/// getFnSpecificMDNode - Return a NameMDNode, if available, that is -/// suitable to hold function specific information. -NamedMDNode *llvm::getFnSpecificMDNode(const Module &M, DISubprogram Fn) { - SmallString<32> Name = StringRef("llvm.dbg.lv."); - StringRef FName = "fn"; - if (Fn.getFunction()) - FName = Fn.getFunction()->getName(); - else - FName = Fn.getName(); - char One = '\1'; - if (FName.startswith(StringRef(&One, 1))) - FName = FName.substr(1); - fixupObjcLikeName(FName, Name); - return M.getNamedMetadata(Name.str()); -} - -/// getOrInsertFnSpecificMDNode - Return a NameMDNode that is suitable -/// to hold function specific information. -NamedMDNode *llvm::getOrInsertFnSpecificMDNode(Module &M, DISubprogram Fn) { - SmallString<32> Name = StringRef("llvm.dbg.lv."); - StringRef FName = "fn"; - if (Fn.getFunction()) - FName = Fn.getFunction()->getName(); - else - FName = Fn.getName(); - char One = '\1'; - if (FName.startswith(StringRef(&One, 1))) - FName = FName.substr(1); - fixupObjcLikeName(FName, Name); - - return M.getOrInsertNamedMetadata(Name.str()); -} - -/// createInlinedVariable - Create a new inlined variable based on current -/// variable. -/// @param DV Current Variable. -/// @param InlinedScope Location at current variable is inlined. -DIVariable llvm::createInlinedVariable(MDNode *DV, MDNode *InlinedScope, - LLVMContext &VMContext) { - SmallVector<Value *, 16> Elts; - // Insert inlined scope as 7th element. - for (unsigned i = 0, e = DV->getNumOperands(); i != e; ++i) - i == 7 ? Elts.push_back(InlinedScope) : - Elts.push_back(DV->getOperand(i)); - return DIVariable(MDNode::get(VMContext, Elts)); -} - -/// cleanseInlinedVariable - Remove inlined scope from the variable. -DIVariable llvm::cleanseInlinedVariable(MDNode *DV, LLVMContext &VMContext) { - SmallVector<Value *, 16> Elts; - // Insert inlined scope as 7th element. - for (unsigned i = 0, e = DV->getNumOperands(); i != e; ++i) - i == 7 ? - Elts.push_back(llvm::Constant::getNullValue(Type::getInt32Ty(VMContext))): - Elts.push_back(DV->getOperand(i)); - return DIVariable(MDNode::get(VMContext, Elts)); -} - -//===----------------------------------------------------------------------===// -// DebugInfoFinder implementations. -//===----------------------------------------------------------------------===// - -/// processModule - Process entire module and collect debug info. -void DebugInfoFinder::processModule(Module &M) { - if (NamedMDNode *CU_Nodes = M.getNamedMetadata("llvm.dbg.cu")) { - for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) { - DICompileUnit CU(CU_Nodes->getOperand(i)); - addCompileUnit(CU); - if (CU.getVersion() > LLVMDebugVersion10) { - DIArray GVs = CU.getGlobalVariables(); - for (unsigned i = 0, e = GVs.getNumElements(); i != e; ++i) { - DIGlobalVariable DIG(GVs.getElement(i)); - if (addGlobalVariable(DIG)) - processType(DIG.getType()); - } - DIArray SPs = CU.getSubprograms(); - for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) - processSubprogram(DISubprogram(SPs.getElement(i))); - DIArray EnumTypes = CU.getEnumTypes(); - for (unsigned i = 0, e = EnumTypes.getNumElements(); i != e; ++i) - processType(DIType(EnumTypes.getElement(i))); - DIArray RetainedTypes = CU.getRetainedTypes(); - for (unsigned i = 0, e = RetainedTypes.getNumElements(); i != e; ++i) - processType(DIType(RetainedTypes.getElement(i))); - return; - } - } - } - - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - for (Function::iterator FI = (*I).begin(), FE = (*I).end(); FI != FE; ++FI) - for (BasicBlock::iterator BI = (*FI).begin(), BE = (*FI).end(); BI != BE; - ++BI) { - if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(BI)) - processDeclare(DDI); - - DebugLoc Loc = BI->getDebugLoc(); - if (Loc.isUnknown()) - continue; - - LLVMContext &Ctx = BI->getContext(); - DIDescriptor Scope(Loc.getScope(Ctx)); - - if (Scope.isCompileUnit()) - addCompileUnit(DICompileUnit(Scope)); - else if (Scope.isSubprogram()) - processSubprogram(DISubprogram(Scope)); - else if (Scope.isLexicalBlockFile()) { - DILexicalBlockFile DBF = DILexicalBlockFile(Scope); - processLexicalBlock(DILexicalBlock(DBF.getScope())); - } - else if (Scope.isLexicalBlock()) - processLexicalBlock(DILexicalBlock(Scope)); - - if (MDNode *IA = Loc.getInlinedAt(Ctx)) - processLocation(DILocation(IA)); - } - - if (NamedMDNode *NMD = M.getNamedMetadata("llvm.dbg.gv")) { - for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) { - DIGlobalVariable DIG(cast<MDNode>(NMD->getOperand(i))); - if (addGlobalVariable(DIG)) { - if (DIG.getVersion() <= LLVMDebugVersion10) - addCompileUnit(DIG.getCompileUnit()); - processType(DIG.getType()); - } - } - } - - if (NamedMDNode *NMD = M.getNamedMetadata("llvm.dbg.sp")) - for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) - processSubprogram(DISubprogram(NMD->getOperand(i))); -} - -/// processLocation - Process DILocation. -void DebugInfoFinder::processLocation(DILocation Loc) { - if (!Loc.Verify()) return; - DIDescriptor S(Loc.getScope()); - if (S.isCompileUnit()) - addCompileUnit(DICompileUnit(S)); - else if (S.isSubprogram()) - processSubprogram(DISubprogram(S)); - else if (S.isLexicalBlock()) - processLexicalBlock(DILexicalBlock(S)); - else if (S.isLexicalBlockFile()) { - DILexicalBlockFile DBF = DILexicalBlockFile(S); - processLexicalBlock(DILexicalBlock(DBF.getScope())); - } - processLocation(Loc.getOrigLocation()); -} - -/// processType - Process DIType. -void DebugInfoFinder::processType(DIType DT) { - if (!addType(DT)) - return; - if (DT.getVersion() <= LLVMDebugVersion10) - addCompileUnit(DT.getCompileUnit()); - if (DT.isCompositeType()) { - DICompositeType DCT(DT); - processType(DCT.getTypeDerivedFrom()); - DIArray DA = DCT.getTypeArray(); - for (unsigned i = 0, e = DA.getNumElements(); i != e; ++i) { - DIDescriptor D = DA.getElement(i); - if (D.isType()) - processType(DIType(D)); - else if (D.isSubprogram()) - processSubprogram(DISubprogram(D)); - } - } else if (DT.isDerivedType()) { - DIDerivedType DDT(DT); - processType(DDT.getTypeDerivedFrom()); - } -} - -/// processLexicalBlock -void DebugInfoFinder::processLexicalBlock(DILexicalBlock LB) { - DIScope Context = LB.getContext(); - if (Context.isLexicalBlock()) - return processLexicalBlock(DILexicalBlock(Context)); - else if (Context.isLexicalBlockFile()) { - DILexicalBlockFile DBF = DILexicalBlockFile(Context); - return processLexicalBlock(DILexicalBlock(DBF.getScope())); - } - else - return processSubprogram(DISubprogram(Context)); -} - -/// processSubprogram - Process DISubprogram. -void DebugInfoFinder::processSubprogram(DISubprogram SP) { - if (!addSubprogram(SP)) - return; - if (SP.getVersion() <= LLVMDebugVersion10) - addCompileUnit(SP.getCompileUnit()); - processType(SP.getType()); -} - -/// processDeclare - Process DbgDeclareInst. -void DebugInfoFinder::processDeclare(DbgDeclareInst *DDI) { - MDNode *N = dyn_cast<MDNode>(DDI->getVariable()); - if (!N) return; - - DIDescriptor DV(N); - if (!DV.isVariable()) - return; - - if (!NodesSeen.insert(DV)) - return; - if (DIVariable(N).getVersion() <= LLVMDebugVersion10) - addCompileUnit(DIVariable(N).getCompileUnit()); - processType(DIVariable(N).getType()); -} - -/// addType - Add type into Tys. -bool DebugInfoFinder::addType(DIType DT) { - if (!DT.isValid()) - return false; - - if (!NodesSeen.insert(DT)) - return false; - - TYs.push_back(DT); - return true; -} - -/// addCompileUnit - Add compile unit into CUs. -bool DebugInfoFinder::addCompileUnit(DICompileUnit CU) { - if (!CU.Verify()) - return false; - - if (!NodesSeen.insert(CU)) - return false; - - CUs.push_back(CU); - return true; -} - -/// addGlobalVariable - Add global variable into GVs. -bool DebugInfoFinder::addGlobalVariable(DIGlobalVariable DIG) { - if (!DIDescriptor(DIG).isGlobalVariable()) - return false; - - if (!NodesSeen.insert(DIG)) - return false; - - GVs.push_back(DIG); - return true; -} - -// addSubprogram - Add subprgoram into SPs. -bool DebugInfoFinder::addSubprogram(DISubprogram SP) { - if (!DIDescriptor(SP).isSubprogram()) - return false; - - if (!NodesSeen.insert(SP)) - return false; - - SPs.push_back(SP); - return true; -} - -/// getDISubprogram - Find subprogram that is enclosing this scope. -DISubprogram llvm::getDISubprogram(const MDNode *Scope) { - DIDescriptor D(Scope); - if (D.isSubprogram()) - return DISubprogram(Scope); - - if (D.isLexicalBlockFile()) - return getDISubprogram(DILexicalBlockFile(Scope).getContext()); - - if (D.isLexicalBlock()) - return getDISubprogram(DILexicalBlock(Scope).getContext()); - - return DISubprogram(); -} - -/// getDICompositeType - Find underlying composite type. -DICompositeType llvm::getDICompositeType(DIType T) { - if (T.isCompositeType()) - return DICompositeType(T); - - if (T.isDerivedType()) - return getDICompositeType(DIDerivedType(T).getTypeDerivedFrom()); - - return DICompositeType(); -} - -/// isSubprogramContext - Return true if Context is either a subprogram -/// or another context nested inside a subprogram. -bool llvm::isSubprogramContext(const MDNode *Context) { - if (!Context) - return false; - DIDescriptor D(Context); - if (D.isSubprogram()) - return true; - if (D.isType()) - return isSubprogramContext(DIType(Context).getContext()); - return false; -} - diff --git a/lib/Analysis/IPA/CMakeLists.txt b/lib/Analysis/IPA/CMakeLists.txt index 8ffef29..34d6d1b 100644 --- a/lib/Analysis/IPA/CMakeLists.txt +++ b/lib/Analysis/IPA/CMakeLists.txt @@ -5,3 +5,5 @@ add_llvm_library(LLVMipa GlobalsModRef.cpp IPA.cpp ) + +add_dependencies(LLVMipa intrinsics_gen) diff --git a/lib/Analysis/IPA/CallGraphSCCPass.cpp b/lib/Analysis/IPA/CallGraphSCCPass.cpp index 963da75..449b7ee 100644 --- a/lib/Analysis/IPA/CallGraphSCCPass.cpp +++ b/lib/Analysis/IPA/CallGraphSCCPass.cpp @@ -246,7 +246,9 @@ bool CGPassManager::RefreshCallGraph(CallGraphSCC &CurSCC, for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { CallSite CS(cast<Value>(I)); - if (!CS || isa<IntrinsicInst>(I)) continue; + if (!CS) continue; + Function *Callee = CS.getCalledFunction(); + if (Callee && Callee->isIntrinsic()) continue; // If this call site already existed in the callgraph, just verify it // matches up to expectations and remove it from CallSites. diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp index c1d8e3e..22f6e96 100644 --- a/lib/Analysis/IPA/GlobalsModRef.cpp +++ b/lib/Analysis/IPA/GlobalsModRef.cpp @@ -329,15 +329,8 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { // Check the value being stored. Value *Ptr = GetUnderlyingObject(SI->getOperand(0)); - if (isMalloc(Ptr)) { - // Okay, easy case. - } else if (CallInst *CI = dyn_cast<CallInst>(Ptr)) { - Function *F = CI->getCalledFunction(); - if (!F || !F->isDeclaration()) return false; // Too hard to analyze. - if (F->getName() != "calloc") return false; // Not calloc. - } else { + if (!isAllocLikeFn(Ptr)) return false; // Too hard to analyze. - } // Analyze all uses of the allocation. If any of them are used in a // non-simple way (e.g. stored to another global) bail out. @@ -454,19 +447,18 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { for (inst_iterator II = inst_begin(SCC[i]->getFunction()), E = inst_end(SCC[i]->getFunction()); II != E && FunctionEffect != ModRef; ++II) - if (isa<LoadInst>(*II)) { + if (LoadInst *LI = dyn_cast<LoadInst>(&*II)) { FunctionEffect |= Ref; - if (cast<LoadInst>(*II).isVolatile()) + if (LI->isVolatile()) // Volatile loads may have side-effects, so mark them as writing // memory (for example, a flag inside the processor). FunctionEffect |= Mod; - } else if (isa<StoreInst>(*II)) { + } else if (StoreInst *SI = dyn_cast<StoreInst>(&*II)) { FunctionEffect |= Mod; - if (cast<StoreInst>(*II).isVolatile()) + if (SI->isVolatile()) // Treat volatile stores as reading memory somewhere. FunctionEffect |= Ref; - } else if (isMalloc(&cast<Instruction>(*II)) || - isFreeCall(&cast<Instruction>(*II))) { + } else if (isAllocationFn(&*II) || isFreeCall(&*II)) { FunctionEffect |= ModRef; } else if (IntrinsicInst *Intrinsic = dyn_cast<IntrinsicInst>(&*II)) { // The callgraph doesn't include intrinsic calls. diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index b80966b..0a6682a 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/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/Analysis/ValueTracking.h" #include "llvm/Target/TargetData.h" #include "llvm/Assembly/Writer.h" #include "llvm/ADT/STLExtras.h" @@ -120,6 +121,12 @@ bool IVUsers::AddUsersImpl(Instruction *I, if (!SE->isSCEVable(I->getType())) return false; // Void and FP expressions cannot be reduced. + // IVUsers is used by LSR which assumes that all SCEV expressions are safe to + // pass to SCEVExpander. Expressions are not safe to expand if they represent + // operations that are not safe to speculate, namely integer division. + if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I, TD)) + return false; + // LSR is not APInt clean, do not touch integers bigger than 64-bits. // 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. diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp index 3e3d2ab..bc1ecd2 100644 --- a/lib/Analysis/InlineCost.cpp +++ b/lib/Analysis/InlineCost.cpp @@ -178,7 +178,7 @@ bool CallAnalyzer::lookupSROAArgAndCost( /// \brief Disable SROA for the candidate marked by this cost iterator. /// -/// This markes the candidate as no longer viable for SROA, and adds the cost +/// This marks the candidate as no longer viable for SROA, and adds the cost /// savings associated with it back into the inline cost measurement. void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) { // If we're no longer able to perform SROA we need to undo its cost savings @@ -398,10 +398,7 @@ bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) { if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) SROAArgValues[&I] = SROAArg; - // A ptrtoint cast is free so long as the result is large enough to store the - // pointer, and a legal integer type. - return TD && TD->isLegalInteger(IntegerSize) && - IntegerSize >= TD->getPointerSizeInBits(); + return isInstructionFree(&I, TD); } bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) { @@ -428,10 +425,7 @@ bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) { if (lookupSROAArgAndCost(Op, SROAArg, CostIt)) SROAArgValues[&I] = SROAArg; - // An inttoptr cast is free so long as the input is a legal integer type - // which doesn't contain values outside the range of a pointer. - return TD && TD->isLegalInteger(IntegerSize) && - IntegerSize <= TD->getPointerSizeInBits(); + return isInstructionFree(&I, TD); } bool CallAnalyzer::visitCastInst(CastInst &I) { @@ -445,24 +439,7 @@ bool CallAnalyzer::visitCastInst(CastInst &I) { // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere. disableSROA(I.getOperand(0)); - // No-op casts don't have any cost. - if (I.isLosslessCast()) - return true; - - // trunc to a native type is free (assuming the target has compare and - // shift-right of the same width). - if (TD && isa<TruncInst>(I) && - TD->isLegalInteger(TD->getTypeSizeInBits(I.getType()))) - return true; - - // Result of a cmp instruction is often extended (to be used by other - // cmp instructions, logical or return instructions). These are usually - // no-ops on most sane targets. - if (isa<CmpInst>(I.getOperand(0))) - return true; - - // Assume the rest of the casts require work. - return false; + return isInstructionFree(&I, TD); } bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) { @@ -636,21 +613,11 @@ bool CallAnalyzer::visitCallSite(CallSite CS) { default: return Base::visitCallSite(CS); - case Intrinsic::dbg_declare: - case Intrinsic::dbg_value: - case Intrinsic::invariant_start: - case Intrinsic::invariant_end: - case Intrinsic::lifetime_start: - case Intrinsic::lifetime_end: case Intrinsic::memset: case Intrinsic::memcpy: case Intrinsic::memmove: - case Intrinsic::objectsize: - case Intrinsic::ptr_annotation: - case Intrinsic::var_annotation: - // SROA can usually chew through these intrinsics and they have no cost - // so don't pay the price of analyzing them in detail. - return true; + // SROA can usually chew through these intrinsics, but they aren't free. + return false; } } @@ -662,7 +629,7 @@ bool CallAnalyzer::visitCallSite(CallSite CS) { return false; } - if (!callIsSmall(F)) { + if (!callIsSmall(CS)) { // We account for the average 1 instruction per call argument setup // here. Cost += CS.arg_size() * InlineConstants::InstrCost; @@ -706,6 +673,11 @@ bool CallAnalyzer::visitCallSite(CallSite CS) { } bool CallAnalyzer::visitInstruction(Instruction &I) { + // Some instructions are free. All of the free intrinsics can also be + // handled by SROA, etc. + if (isInstructionFree(&I, TD)) + return true; + // We found something we don't understand or can't handle. Mark any SROA-able // values in the operand list as no longer viable. for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI) @@ -825,9 +797,33 @@ bool CallAnalyzer::analyzeCall(CallSite CS) { FiftyPercentVectorBonus = Threshold; TenPercentVectorBonus = Threshold / 2; - // Subtract off one instruction per call argument as those will be free after - // inlining. - Cost -= CS.arg_size() * InlineConstants::InstrCost; + // Give out bonuses per argument, as the instructions setting them up will + // be gone after inlining. + for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) { + if (TD && CS.isByValArgument(I)) { + // We approximate the number of loads and stores needed by dividing the + // size of the byval type by the target's pointer size. + PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType()); + unsigned TypeSize = TD->getTypeSizeInBits(PTy->getElementType()); + unsigned PointerSize = TD->getPointerSizeInBits(); + // Ceiling division. + unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize; + + // If it generates more than 8 stores it is likely to be expanded as an + // inline memcpy so we take that as an upper bound. Otherwise we assume + // one load and one store per word copied. + // FIXME: The maxStoresPerMemcpy setting from the target should be used + // here instead of a magic number of 8, but it's not available via + // TargetData. + NumStores = std::min(NumStores, 8U); + + Cost -= 2 * NumStores * InlineConstants::InstrCost; + } else { + // For non-byval arguments subtract off one instruction per call + // argument. + Cost -= InlineConstants::InstrCost; + } + } // If there is only one call of the function, and it has internal linkage, // the cost of inlining it drops dramatically. diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 16e7a72..379a35a 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -47,7 +47,7 @@ struct Query { const DominatorTree *DT; Query(const TargetData *td, const TargetLibraryInfo *tli, - const DominatorTree *dt) : TD(td), TLI(tli), DT(dt) {}; + const DominatorTree *dt) : TD(td), TLI(tli), DT(dt) {} }; static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned); @@ -1719,10 +1719,13 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, return ConstantInt::get(ITy, false); // A local identified object (alloca or noalias call) can't equal any - // incoming argument, unless they're both null. - if (isa<Instruction>(LHSPtr) && isa<Argument>(RHSPtr) && - Pred == CmpInst::ICMP_EQ) - return ConstantInt::get(ITy, false); + // incoming argument, unless they're both null or they belong to + // different functions. The latter happens during inlining. + if (Instruction *LHSInst = dyn_cast<Instruction>(LHSPtr)) + if (Argument *RHSArg = dyn_cast<Argument>(RHSPtr)) + if (LHSInst->getParent()->getParent() == RHSArg->getParent() && + Pred == CmpInst::ICMP_EQ) + return ConstantInt::get(ITy, false); } // Assume that the constant null is on the right. @@ -1732,14 +1735,17 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, else if (Pred == CmpInst::ICMP_NE) return ConstantInt::get(ITy, true); } - } else if (isa<Argument>(LHSPtr)) { + } else if (Argument *LHSArg = dyn_cast<Argument>(LHSPtr)) { RHSPtr = RHSPtr->stripInBoundsOffsets(); - // An alloca can't be equal to an argument. - if (isa<AllocaInst>(RHSPtr)) { - if (Pred == CmpInst::ICMP_EQ) - return ConstantInt::get(ITy, false); - else if (Pred == CmpInst::ICMP_NE) - return ConstantInt::get(ITy, true); + // An alloca can't be equal to an argument unless they come from separate + // functions via inlining. + if (AllocaInst *RHSInst = dyn_cast<AllocaInst>(RHSPtr)) { + if (LHSArg->getParent() == RHSInst->getParent()->getParent()) { + if (Pred == CmpInst::ICMP_EQ) + return ConstantInt::get(ITy, false); + else if (Pred == CmpInst::ICMP_NE) + return ConstantInt::get(ITy, true); + } } } diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index 5ca2746..9140786 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -172,7 +172,7 @@ public: if (NewR.isEmptySet()) return markOverdefined(); - bool changed = Range == NewR; + bool changed = Range != NewR; Range = NewR; return changed; } @@ -457,8 +457,10 @@ void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { void LazyValueInfoCache::solve() { while (!BlockValueStack.empty()) { std::pair<BasicBlock*, Value*> &e = BlockValueStack.top(); - if (solveBlockValue(e.second, e.first)) + if (solveBlockValue(e.second, e.first)) { + assert(BlockValueStack.top() == e); BlockValueStack.pop(); + } } } @@ -766,15 +768,10 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, return true; } -/// getEdgeValue - This method attempts to infer more complex -bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo, LVILatticeVal &Result) { - // If already a constant, there is nothing to compute. - if (Constant *VC = dyn_cast<Constant>(Val)) { - Result = LVILatticeVal::get(VC); - return true; - } - +/// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if +/// Val is not constrained on the edge. +static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, + BasicBlock *BBTo, LVILatticeVal &Result) { // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we // know that v != 0. if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) { @@ -818,7 +815,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1)); if (CI && (ICI->getOperand(0) == Val || NegOffset)) { // Calculate the range of values that would satisfy the comparison. - ConstantRange CmpRange(CI->getValue(), CI->getValue()+1); + ConstantRange CmpRange(CI->getValue()); ConstantRange TrueValues = ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange); @@ -827,25 +824,8 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, // If we're interested in the false dest, invert the condition. if (!isTrueDest) TrueValues = TrueValues.inverse(); - - // Figure out the possible values of the query BEFORE this branch. - if (!hasBlockValue(Val, BBFrom)) { - BlockValueStack.push(std::make_pair(BBFrom, Val)); - return false; - } - - LVILatticeVal InBlock = getBlockValue(Val, BBFrom); - if (!InBlock.isConstantRange()) { - Result = LVILatticeVal::getRange(TrueValues); - return true; - } - - // Find all potential values that satisfy both the input and output - // conditions. - ConstantRange PossibleValues = - TrueValues.intersectWith(InBlock.getConstantRange()); - - Result = LVILatticeVal::getRange(PossibleValues); + + Result = LVILatticeVal::getRange(TrueValues); return true; } } @@ -855,40 +835,71 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, // If the edge was formed by a switch on the value, then we may know exactly // what it is. if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) { - if (SI->getCondition() == Val) { - // We don't know anything in the default case. - if (SI->getDefaultDest() == BBTo) { - Result.markOverdefined(); - return true; - } - - // We only know something if there is exactly one value that goes from - // BBFrom to BBTo. - unsigned NumEdges = 0; - ConstantInt *EdgeVal = 0; - for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); - i != e; ++i) { - if (i.getCaseSuccessor() != BBTo) continue; - if (NumEdges++) break; - EdgeVal = i.getCaseValue(); - } - assert(EdgeVal && "Missing successor?"); - if (NumEdges == 1) { - Result = LVILatticeVal::get(EdgeVal); - return true; - } + if (SI->getCondition() != Val) + return false; + + bool DefaultCase = SI->getDefaultDest() == BBTo; + unsigned BitWidth = Val->getType()->getIntegerBitWidth(); + ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/); + + for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); + i != e; ++i) { + ConstantRange EdgeVal(i.getCaseValue()->getValue()); + if (DefaultCase) + EdgesVals = EdgesVals.difference(EdgeVal); + else if (i.getCaseSuccessor() == BBTo) + EdgesVals = EdgesVals.unionWith(EdgeVal); } - } - - // Otherwise see if the value is known in the block. - if (hasBlockValue(Val, BBFrom)) { - Result = getBlockValue(Val, BBFrom); + Result = LVILatticeVal::getRange(EdgesVals); return true; } - BlockValueStack.push(std::make_pair(BBFrom, Val)); return false; } +/// \brief Compute the value of Val on the edge BBFrom -> BBTo, or the value at +/// the basic block if the edge does not constraint Val. +bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, + BasicBlock *BBTo, LVILatticeVal &Result) { + // If already a constant, there is nothing to compute. + if (Constant *VC = dyn_cast<Constant>(Val)) { + Result = LVILatticeVal::get(VC); + return true; + } + + if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) { + if (!Result.isConstantRange() || + Result.getConstantRange().getSingleElement()) + return true; + + // FIXME: this check should be moved to the beginning of the function when + // LVI better supports recursive values. Even for the single value case, we + // can intersect to detect dead code (an empty range). + if (!hasBlockValue(Val, BBFrom)) { + BlockValueStack.push(std::make_pair(BBFrom, Val)); + return false; + } + + // Try to intersect ranges of the BB and the constraint on the edge. + LVILatticeVal InBlock = getBlockValue(Val, BBFrom); + if (!InBlock.isConstantRange()) + return true; + + ConstantRange Range = + Result.getConstantRange().intersectWith(InBlock.getConstantRange()); + Result = LVILatticeVal::getRange(Range); + return true; + } + + if (!hasBlockValue(Val, BBFrom)) { + BlockValueStack.push(std::make_pair(BBFrom, Val)); + return false; + } + + // if we couldn't compute the value on the edge, use the value from the BB + Result = getBlockValue(Val, BBFrom); + return true; +} + LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) { DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '" << BB->getName() << "'\n"); diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index f7a60a1..20c33a3 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -18,6 +18,7 @@ #include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Assembly/Writer.h" @@ -29,6 +30,10 @@ #include <algorithm> using namespace llvm; +// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. +template class llvm::LoopBase<BasicBlock, Loop>; +template class llvm::LoopInfoBase<BasicBlock, Loop>; + // Always verify loopinfo if expensive checking is enabled. #ifdef XDEBUG static bool VerifyLoopInfo = true; @@ -507,7 +512,7 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { // bool LoopInfo::runOnFunction(Function &) { releaseMemory(); - LI.Calculate(getAnalysis<DominatorTree>().getBase()); // Update + LI.Analyze(getAnalysis<DominatorTree>().getBase()); return false; } @@ -589,9 +594,6 @@ void LoopInfo::verifyAnalysis() const { } // Verify that blocks are mapped to valid loops. - // - // FIXME: With an up-to-date DFS (see LoopIterator.h) and DominatorTree, we - // could also verify that the blocks are still in the correct loops. for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(), E = LI.BBMap.end(); I != E; ++I) { assert(Loops.count(I->second) && "orphaned loop"); diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp index aba700a..1540112 100644 --- a/lib/Analysis/LoopPass.cpp +++ b/lib/Analysis/LoopPass.cpp @@ -162,7 +162,7 @@ void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) { // Recurse through all subloops and all loops into LQ. static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { LQ.push_back(L); - for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) + for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I) addLoopIntoQueue(*I, LQ); } @@ -183,8 +183,12 @@ bool LPPassManager::runOnFunction(Function &F) { // Collect inherited analysis from Module level pass manager. populateInheritedAnalysis(TPM->activeStack); - // Populate Loop Queue - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) + // Populate the loop queue in reverse program order. There is no clear need to + // process sibling loops in either forward or reverse order. There may be some + // advantage in deleting uses in a later loop before optimizing the + // definitions in an earlier loop. If we find a clear reason to process in + // forward order, then a forward variant of LoopPassManager should be created. + for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I) addLoopIntoQueue(*I, LQ); if (LQ.empty()) // No loops, skip calling finalizers diff --git a/lib/Analysis/MemDepPrinter.cpp b/lib/Analysis/MemDepPrinter.cpp index 22414b3..8578a63 100644 --- a/lib/Analysis/MemDepPrinter.cpp +++ b/lib/Analysis/MemDepPrinter.cpp @@ -32,7 +32,7 @@ namespace { Unknown }; - static const char* DepTypeStr[]; + static const char *const DepTypeStr[]; typedef PointerIntPair<const Instruction *, 2, DepType> InstTypePair; typedef std::pair<InstTypePair, const BasicBlock *> Dep; @@ -88,7 +88,7 @@ FunctionPass *llvm::createMemDepPrinter() { return new MemDepPrinter(); } -const char* MemDepPrinter::DepTypeStr[] +const char *const MemDepPrinter::DepTypeStr[] = {"Clobber", "Def", "NonFuncLocal", "Unknown"}; bool MemDepPrinter::runOnFunction(Function &F) { diff --git a/lib/Analysis/MemoryBuiltins.cpp b/lib/Analysis/MemoryBuiltins.cpp index b145650..c0cc27b 100644 --- a/lib/Analysis/MemoryBuiltins.cpp +++ b/lib/Analysis/MemoryBuiltins.cpp @@ -12,80 +12,168 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "memory-builtins" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Constants.h" +#include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" +#include "llvm/Intrinsics.h" +#include "llvm/Metadata.h" #include "llvm/Module.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetData.h" +#include "llvm/Transforms/Utils/Local.h" using namespace llvm; -//===----------------------------------------------------------------------===// -// malloc Call Utility Functions. -// +enum AllocType { + MallocLike = 1<<0, // allocates + CallocLike = 1<<1, // allocates + bzero + ReallocLike = 1<<2, // reallocates + StrDupLike = 1<<3, + AllocLike = MallocLike | CallocLike | StrDupLike, + AnyAlloc = MallocLike | CallocLike | ReallocLike | StrDupLike +}; + +struct AllocFnsTy { + const char *Name; + AllocType AllocTy; + unsigned char NumParams; + // First and Second size parameters (or -1 if unused) + signed char FstParam, SndParam; +}; + +// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to +// know which functions are nounwind, noalias, nocapture parameters, etc. +static const AllocFnsTy AllocationFnData[] = { + {"malloc", MallocLike, 1, 0, -1}, + {"valloc", MallocLike, 1, 0, -1}, + {"_Znwj", MallocLike, 1, 0, -1}, // new(unsigned int) + {"_ZnwjRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new(unsigned int, nothrow) + {"_Znwm", MallocLike, 1, 0, -1}, // new(unsigned long) + {"_ZnwmRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new(unsigned long, nothrow) + {"_Znaj", MallocLike, 1, 0, -1}, // new[](unsigned int) + {"_ZnajRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow) + {"_Znam", MallocLike, 1, 0, -1}, // new[](unsigned long) + {"_ZnamRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow) + {"posix_memalign", MallocLike, 3, 2, -1}, + {"calloc", CallocLike, 2, 0, 1}, + {"realloc", ReallocLike, 2, 1, -1}, + {"reallocf", ReallocLike, 2, 1, -1}, + {"strdup", StrDupLike, 1, -1, -1}, + {"strndup", StrDupLike, 2, 1, -1} +}; + + +static Function *getCalledFunction(const Value *V, bool LookThroughBitCast) { + if (LookThroughBitCast) + V = V->stripPointerCasts(); -/// isMalloc - Returns true if the value is either a malloc call or a -/// bitcast of the result of a malloc call. -bool llvm::isMalloc(const Value *I) { - return extractMallocCall(I) || extractMallocCallFromBitCast(I); + CallSite CS(const_cast<Value*>(V)); + if (!CS.getInstruction()) + return 0; + + Function *Callee = CS.getCalledFunction(); + if (!Callee || !Callee->isDeclaration()) + return 0; + return Callee; } -static bool isMallocCall(const CallInst *CI) { - if (!CI) - return false; +/// \brief Returns the allocation data for the given value if it is a call to a +/// known allocation function, and NULL otherwise. +static const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy, + bool LookThroughBitCast = false) { + Function *Callee = getCalledFunction(V, LookThroughBitCast); + if (!Callee) + return 0; - Function *Callee = CI->getCalledFunction(); - 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; + unsigned i = 0; + bool found = false; + for ( ; i < array_lengthof(AllocationFnData); ++i) { + if (Callee->getName() == AllocationFnData[i].Name) { + found = true; + break; + } + } + if (!found) + return 0; - // Check malloc prototype. - // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin - // attribute will exist. + const AllocFnsTy *FnData = &AllocationFnData[i]; + if ((FnData->AllocTy & AllocTy) == 0) + return 0; + + // Check function prototype. + // FIXME: Check the nobuiltin metadata?? (PR5130) + int FstParam = FnData->FstParam; + int SndParam = FnData->SndParam; FunctionType *FTy = Callee->getFunctionType(); - return FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && - FTy->getNumParams() == 1 && - (FTy->getParamType(0)->isIntegerTy(32) || - FTy->getParamType(0)->isIntegerTy(64)); + + if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && + FTy->getNumParams() == FnData->NumParams && + (FstParam < 0 || + (FTy->getParamType(FstParam)->isIntegerTy(32) || + FTy->getParamType(FstParam)->isIntegerTy(64))) && + (SndParam < 0 || + FTy->getParamType(SndParam)->isIntegerTy(32) || + FTy->getParamType(SndParam)->isIntegerTy(64))) + return FnData; + return 0; } -/// extractMallocCall - Returns the corresponding CallInst if the instruction -/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we -/// ignore InvokeInst here. -const CallInst *llvm::extractMallocCall(const Value *I) { - const CallInst *CI = dyn_cast<CallInst>(I); - return (isMallocCall(CI)) ? CI : NULL; +static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) { + ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V); + return CS && CS.hasFnAttr(Attribute::NoAlias); } -CallInst *llvm::extractMallocCall(Value *I) { - CallInst *CI = dyn_cast<CallInst>(I); - return (isMallocCall(CI)) ? CI : NULL; + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup +/// like). +bool llvm::isAllocationFn(const Value *V, bool LookThroughBitCast) { + return getAllocationData(V, AnyAlloc, LookThroughBitCast); } -static bool isBitCastOfMallocCall(const BitCastInst *BCI) { - if (!BCI) - return false; - - return isMallocCall(dyn_cast<CallInst>(BCI->getOperand(0))); +/// \brief Tests if a value is a call or invoke to a function that returns a +/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). +bool llvm::isNoAliasFn(const Value *V, bool LookThroughBitCast) { + // it's safe to consider realloc as noalias since accessing the original + // pointer is undefined behavior + return isAllocationFn(V, LookThroughBitCast) || + hasNoAliasAttr(V, LookThroughBitCast); +} + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates uninitialized memory (such as malloc). +bool llvm::isMallocLikeFn(const Value *V, bool LookThroughBitCast) { + return getAllocationData(V, MallocLike, LookThroughBitCast); +} + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates zero-filled memory (such as calloc). +bool llvm::isCallocLikeFn(const Value *V, bool LookThroughBitCast) { + return getAllocationData(V, CallocLike, LookThroughBitCast); +} + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates memory (either malloc, calloc, or strdup like). +bool llvm::isAllocLikeFn(const Value *V, bool LookThroughBitCast) { + return getAllocationData(V, AllocLike, LookThroughBitCast); } -/// extractMallocCallFromBitCast - Returns the corresponding CallInst if the -/// instruction is a bitcast of the result of a malloc call. -CallInst *llvm::extractMallocCallFromBitCast(Value *I) { - BitCastInst *BCI = dyn_cast<BitCastInst>(I); - return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0)) - : NULL; +/// \brief Tests if a value is a call or invoke to a library function that +/// reallocates memory (such as realloc). +bool llvm::isReallocLikeFn(const Value *V, bool LookThroughBitCast) { + return getAllocationData(V, ReallocLike, LookThroughBitCast); } -const CallInst *llvm::extractMallocCallFromBitCast(const Value *I) { - const BitCastInst *BCI = dyn_cast<BitCastInst>(I); - return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0)) - : NULL; +/// extractMallocCall - Returns the corresponding CallInst if the instruction +/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we +/// ignore InvokeInst here. +const CallInst *llvm::extractMallocCall(const Value *I) { + return isMallocLikeFn(I) ? dyn_cast<CallInst>(I) : 0; } static Value *computeArraySize(const CallInst *CI, const TargetData *TD, @@ -134,7 +222,7 @@ const CallInst *llvm::isArrayMalloc(const Value *I, const TargetData *TD) { /// 1: PointerType is the bitcast's result type. /// >1: Unique PointerType cannot be determined, return NULL. PointerType *llvm::getMallocType(const CallInst *CI) { - assert(isMalloc(CI) && "getMallocType and not malloc call"); + assert(isMallocLikeFn(CI) && "getMallocType and not malloc call"); PointerType *MallocType = NULL; unsigned NumOfBitCastUses = 0; @@ -176,13 +264,17 @@ Type *llvm::getMallocAllocatedType(const CallInst *CI) { /// determined. Value *llvm::getMallocArraySize(CallInst *CI, const TargetData *TD, bool LookThroughSExt) { - assert(isMalloc(CI) && "getMallocArraySize and not malloc call"); + assert(isMallocLikeFn(CI) && "getMallocArraySize and not malloc call"); return computeArraySize(CI, TD, LookThroughSExt); } -//===----------------------------------------------------------------------===// -// free Call Utility Functions. -// + +/// extractCallocCall - Returns the corresponding CallInst if the instruction +/// is a calloc call. +const CallInst *llvm::extractCallocCall(const Value *I) { + return isCallocLikeFn(I) ? cast<CallInst>(I) : 0; +} + /// isFreeCall - Returns non-null if the value is a call to the builtin free() const CallInst *llvm::isFreeCall(const Value *I) { @@ -211,3 +303,438 @@ const CallInst *llvm::isFreeCall(const Value *I) { return CI; } + + + +//===----------------------------------------------------------------------===// +// Utility functions to compute size of objects. +// + + +/// \brief Compute the size of the object pointed by Ptr. Returns true and the +/// object size in Size if successful, and false otherwise. +/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, +/// byval arguments, and global variables. +bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const TargetData *TD, + bool RoundToAlign) { + if (!TD) + return false; + + ObjectSizeOffsetVisitor Visitor(TD, Ptr->getContext(), RoundToAlign); + SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); + if (!Visitor.bothKnown(Data)) + return false; + + APInt ObjSize = Data.first, Offset = Data.second; + // check for overflow + if (Offset.slt(0) || ObjSize.ult(Offset)) + Size = 0; + else + Size = (ObjSize - Offset).getZExtValue(); + return true; +} + + +STATISTIC(ObjectVisitorArgument, + "Number of arguments with unsolved size and offset"); +STATISTIC(ObjectVisitorLoad, + "Number of load instructions with unsolved size and offset"); + + +APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) { + if (RoundToAlign && Align) + return APInt(IntTyBits, RoundUpToAlignment(Size.getZExtValue(), Align)); + return Size; +} + +ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const TargetData *TD, + LLVMContext &Context, + bool RoundToAlign) +: TD(TD), RoundToAlign(RoundToAlign) { + IntegerType *IntTy = TD->getIntPtrType(Context); + IntTyBits = IntTy->getBitWidth(); + Zero = APInt::getNullValue(IntTyBits); +} + +SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { + V = V->stripPointerCasts(); + + if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) + return visitGEPOperator(*GEP); + if (Instruction *I = dyn_cast<Instruction>(V)) + return visit(*I); + if (Argument *A = dyn_cast<Argument>(V)) + return visitArgument(*A); + if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V)) + return visitConstantPointerNull(*P); + if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) + return visitGlobalVariable(*GV); + if (UndefValue *UV = dyn_cast<UndefValue>(V)) + return visitUndefValue(*UV); + if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) + if (CE->getOpcode() == Instruction::IntToPtr) + return unknown(); // clueless + + DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V + << '\n'); + return unknown(); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) { + if (!I.getAllocatedType()->isSized()) + return unknown(); + + APInt Size(IntTyBits, TD->getTypeAllocSize(I.getAllocatedType())); + if (!I.isArrayAllocation()) + return std::make_pair(align(Size, I.getAlignment()), Zero); + + Value *ArraySize = I.getArraySize(); + if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) { + Size *= C->getValue().zextOrSelf(IntTyBits); + return std::make_pair(align(Size, I.getAlignment()), Zero); + } + return unknown(); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) { + // no interprocedural analysis is done at the moment + if (!A.hasByValAttr()) { + ++ObjectVisitorArgument; + return unknown(); + } + PointerType *PT = cast<PointerType>(A.getType()); + APInt Size(IntTyBits, TD->getTypeAllocSize(PT->getElementType())); + return std::make_pair(align(Size, A.getParamAlignment()), Zero); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) { + const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc); + if (!FnData) + return unknown(); + + // handle strdup-like functions separately + if (FnData->AllocTy == StrDupLike) { + APInt Size(IntTyBits, GetStringLength(CS.getArgument(0))); + if (!Size) + return unknown(); + + // strndup limits strlen + if (FnData->FstParam > 0) { + ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); + if (!Arg) + return unknown(); + + APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); + if (Size.ugt(MaxSize)) + Size = MaxSize + 1; + } + return std::make_pair(Size, Zero); + } + + ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); + if (!Arg) + return unknown(); + + APInt Size = Arg->getValue().zextOrSelf(IntTyBits); + // size determined by just 1 parameter + if (FnData->SndParam < 0) + return std::make_pair(Size, Zero); + + Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam)); + if (!Arg) + return unknown(); + + Size *= Arg->getValue().zextOrSelf(IntTyBits); + return std::make_pair(Size, Zero); + + // TODO: handle more standard functions (+ wchar cousins): + // - strdup / strndup + // - strcpy / strncpy + // - strcat / strncat + // - memcpy / memmove + // - strcat / strncat + // - memset +} + +SizeOffsetType +ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) { + return std::make_pair(Zero, Zero); +} + +SizeOffsetType +ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) { + return unknown(); +} + +SizeOffsetType +ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { + // Easy cases were already folded by previous passes. + return unknown(); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { + SizeOffsetType PtrData = compute(GEP.getPointerOperand()); + if (!bothKnown(PtrData) || !GEP.hasAllConstantIndices()) + return unknown(); + + SmallVector<Value*, 8> Ops(GEP.idx_begin(), GEP.idx_end()); + APInt Offset(IntTyBits,TD->getIndexedOffset(GEP.getPointerOperandType(),Ops)); + return std::make_pair(PtrData.first, PtrData.second + Offset); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){ + if (!GV.hasDefinitiveInitializer()) + return unknown(); + + APInt Size(IntTyBits, TD->getTypeAllocSize(GV.getType()->getElementType())); + return std::make_pair(align(Size, GV.getAlignment()), Zero); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) { + // clueless + return unknown(); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { + ++ObjectVisitorLoad; + return unknown(); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) { + // too complex to analyze statically. + return unknown(); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { + // ignore malformed self-looping selects + if (I.getTrueValue() == &I || I.getFalseValue() == &I) + return unknown(); + + SizeOffsetType TrueSide = compute(I.getTrueValue()); + SizeOffsetType FalseSide = compute(I.getFalseValue()); + if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide) + return TrueSide; + return unknown(); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { + return std::make_pair(Zero, Zero); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) { + DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n'); + return unknown(); +} + + +ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const TargetData *TD, + LLVMContext &Context) +: TD(TD), Context(Context), Builder(Context, TargetFolder(TD)), +Visitor(TD, Context) { + IntTy = TD->getIntPtrType(Context); + Zero = ConstantInt::get(IntTy, 0); +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { + SizeOffsetEvalType Result = compute_(V); + + if (!bothKnown(Result)) { + // erase everything that was computed in this iteration from the cache, so + // that no dangling references are left behind. We could be a bit smarter if + // we kept a dependency graph. It's probably not worth the complexity. + for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) { + CacheMapTy::iterator CacheIt = CacheMap.find(*I); + // non-computable results can be safely cached + if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second)) + CacheMap.erase(CacheIt); + } + } + + SeenVals.clear(); + return Result; +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) { + SizeOffsetType Const = Visitor.compute(V); + if (Visitor.bothKnown(Const)) + return std::make_pair(ConstantInt::get(Context, Const.first), + ConstantInt::get(Context, Const.second)); + + V = V->stripPointerCasts(); + + // check cache + CacheMapTy::iterator CacheIt = CacheMap.find(V); + if (CacheIt != CacheMap.end()) + return CacheIt->second; + + // always generate code immediately before the instruction being + // processed, so that the generated code dominates the same BBs + Instruction *PrevInsertPoint = Builder.GetInsertPoint(); + if (Instruction *I = dyn_cast<Instruction>(V)) + Builder.SetInsertPoint(I); + + // record the pointers that were handled in this run, so that they can be + // cleaned later if something fails + SeenVals.insert(V); + + // now compute the size and offset + SizeOffsetEvalType Result; + if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { + Result = visitGEPOperator(*GEP); + } else if (Instruction *I = dyn_cast<Instruction>(V)) { + Result = visit(*I); + } else if (isa<Argument>(V) || + (isa<ConstantExpr>(V) && + cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) || + isa<GlobalVariable>(V)) { + // ignore values where we cannot do more than what ObjectSizeVisitor can + Result = unknown(); + } else { + DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " + << *V << '\n'); + Result = unknown(); + } + + if (PrevInsertPoint) + Builder.SetInsertPoint(PrevInsertPoint); + + // Don't reuse CacheIt since it may be invalid at this point. + CacheMap[V] = Result; + return Result; +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) { + if (!I.getAllocatedType()->isSized()) + return unknown(); + + // must be a VLA + assert(I.isArrayAllocation()); + Value *ArraySize = I.getArraySize(); + Value *Size = ConstantInt::get(ArraySize->getType(), + TD->getTypeAllocSize(I.getAllocatedType())); + Size = Builder.CreateMul(Size, ArraySize); + return std::make_pair(Size, Zero); +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { + const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc); + if (!FnData) + return unknown(); + + // handle strdup-like functions separately + if (FnData->AllocTy == StrDupLike) { + // TODO + return unknown(); + } + + Value *FirstArg = CS.getArgument(FnData->FstParam); + FirstArg = Builder.CreateZExt(FirstArg, IntTy); + if (FnData->SndParam < 0) + return std::make_pair(FirstArg, Zero); + + Value *SecondArg = CS.getArgument(FnData->SndParam); + SecondArg = Builder.CreateZExt(SecondArg, IntTy); + Value *Size = Builder.CreateMul(FirstArg, SecondArg); + return std::make_pair(Size, Zero); + + // TODO: handle more standard functions (+ wchar cousins): + // - strdup / strndup + // - strcpy / strncpy + // - strcat / strncat + // - memcpy / memmove + // - strcat / strncat + // - memset +} + +SizeOffsetEvalType +ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) { + return unknown(); +} + +SizeOffsetEvalType +ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) { + return unknown(); +} + +SizeOffsetEvalType +ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) { + SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand()); + if (!bothKnown(PtrData)) + return unknown(); + + Value *Offset = EmitGEPOffset(&Builder, *TD, &GEP, /*NoAssumptions=*/true); + Offset = Builder.CreateAdd(PtrData.second, Offset); + return std::make_pair(PtrData.first, Offset); +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) { + // clueless + return unknown(); +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { + return unknown(); +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { + // create 2 PHIs: one for size and another for offset + PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); + PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); + + // insert right away in the cache to handle recursive PHIs + CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI); + + // compute offset/size for each PHI incoming pointer + for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) { + Builder.SetInsertPoint(PHI.getIncomingBlock(i)->getFirstInsertionPt()); + SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); + + if (!bothKnown(EdgeData)) { + OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy)); + OffsetPHI->eraseFromParent(); + SizePHI->replaceAllUsesWith(UndefValue::get(IntTy)); + SizePHI->eraseFromParent(); + return unknown(); + } + SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i)); + OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i)); + } + + Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp; + if ((Tmp = SizePHI->hasConstantValue())) { + Size = Tmp; + SizePHI->replaceAllUsesWith(Size); + SizePHI->eraseFromParent(); + } + if ((Tmp = OffsetPHI->hasConstantValue())) { + Offset = Tmp; + OffsetPHI->replaceAllUsesWith(Offset); + OffsetPHI->eraseFromParent(); + } + return std::make_pair(Size, Offset); +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) { + // ignore malformed self-looping selects + if (I.getTrueValue() == &I || I.getFalseValue() == &I) + return unknown(); + + SizeOffsetEvalType TrueSide = compute_(I.getTrueValue()); + SizeOffsetEvalType FalseSide = compute_(I.getFalseValue()); + + if (!bothKnown(TrueSide) || !bothKnown(FalseSide)) + return unknown(); + if (TrueSide == FalseSide) + return TrueSide; + + Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first, + FalseSide.first); + Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second, + FalseSide.second); + return std::make_pair(Size, Offset); +} + +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) { + DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n'); + return unknown(); +} diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 3a544f3..059e574 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -16,13 +16,11 @@ #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" #include "llvm/LLVMContext.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" @@ -229,13 +227,18 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, // Otherwise if the two calls don't interact (e.g. InstCS is readnone) // keep scanning. - break; + continue; default: return MemDepResult::getClobber(Inst); } } + + // If we could not obtain a pointer for the instruction and the instruction + // touches memory then assume that this is a dependency. + if (MR != AliasAnalysis::NoModRef) + return MemDepResult::getClobber(Inst); } - + // No dependence found. If this is the entry block of the function, it is // unknown, otherwise it is non-local. if (BB != &BB->getParent()->getEntryBlock()) @@ -339,86 +342,6 @@ getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, } } -namespace { - /// Only find pointer captures which happen before the given instruction. Uses - /// the dominator tree to determine whether one instruction is before another. - struct CapturesBefore : public CaptureTracker { - CapturesBefore(const Instruction *I, DominatorTree *DT) - : BeforeHere(I), DT(DT), Captured(false) {} - - void tooManyUses() { Captured = true; } - - bool shouldExplore(Use *U) { - Instruction *I = cast<Instruction>(U->getUser()); - BasicBlock *BB = I->getParent(); - if (BeforeHere != I && - (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I))) - return false; - return true; - } - - bool captured(Use *U) { - Instruction *I = cast<Instruction>(U->getUser()); - BasicBlock *BB = I->getParent(); - if (BeforeHere != I && - (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I))) - return false; - Captured = true; - return true; - } - - const Instruction *BeforeHere; - DominatorTree *DT; - - bool Captured; - }; -} - -AliasAnalysis::ModRefResult -MemoryDependenceAnalysis::getModRefInfo(const Instruction *Inst, - const AliasAnalysis::Location &MemLoc) { - AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); - if (MR != AliasAnalysis::ModRef) return MR; - - // FIXME: this is really just shoring-up a deficiency in alias analysis. - // BasicAA isn't willing to spend linear time determining whether an alloca - // was captured before or after this particular call, while we are. However, - // with a smarter AA in place, this test is just wasting compile time. - if (!DT) return AliasAnalysis::ModRef; - const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD); - if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object)) - return AliasAnalysis::ModRef; - ImmutableCallSite CS(Inst); - if (!CS.getInstruction()) return AliasAnalysis::ModRef; - - CapturesBefore CB(Inst, DT); - llvm::PointerMayBeCaptured(Object, &CB); - - if (isa<Constant>(Object) || CS.getInstruction() == Object || CB.Captured) - return AliasAnalysis::ModRef; - - unsigned ArgNo = 0; - for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); - CI != CE; ++CI, ++ArgNo) { - // Only look at the no-capture or byval pointer arguments. If this - // pointer were passed to arguments that were neither of these, then it - // couldn't be no-capture. - if (!(*CI)->getType()->isPointerTy() || - (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) - continue; - - // If this is a no-capture pointer argument, see if we can tell that it - // is impossible to alias the pointer we're checking. If not, we have to - // assume that the call could touch the pointer, even though it doesn't - // escape. - if (!AA->isNoAlias(AliasAnalysis::Location(*CI), - AliasAnalysis::Location(Object))) { - return AliasAnalysis::ModRef; - } - } - return AliasAnalysis::NoModRef; -} - /// 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 @@ -556,8 +479,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // a subsequent bitcast of the malloc call result. There can be stores to // the malloced memory between the malloc call and its bitcast uses, and we // need to continue scanning until the malloc call. - if (isa<AllocaInst>(Inst) || - (isa<CallInst>(Inst) && extractMallocCall(Inst))) { + if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst)) { const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD); if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr)) @@ -566,7 +488,11 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. - switch (getModRefInfo(Inst, MemLoc)) { + AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); + // If necessary, perform additional analysis. + if (MR == AliasAnalysis::ModRef) + MR = AA->callCapturesBefore(Inst, MemLoc, DT); + switch (MR) { case AliasAnalysis::NoModRef: // If the call has no effect on the queried pointer, just ignore it. continue; @@ -984,7 +910,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, if (!Pair.second) { if (CacheInfo->Size < Loc.Size) { // The query's Size is greater than the cached one. Throw out the - // cached data and procede with the query at the greater size. + // cached data and proceed with the query at the greater size. CacheInfo->Pair = BBSkipFirstBlockPair(); CacheInfo->Size = Loc.Size; for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), diff --git a/lib/Analysis/ModuleDebugInfoPrinter.cpp b/lib/Analysis/ModuleDebugInfoPrinter.cpp index e7e999c..f8c7514 100644 --- a/lib/Analysis/ModuleDebugInfoPrinter.cpp +++ b/lib/Analysis/ModuleDebugInfoPrinter.cpp @@ -16,10 +16,10 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/DebugInfo.h" #include "llvm/Assembly/Writer.h" -#include "llvm/Pass.h" +#include "llvm/DebugInfo.h" #include "llvm/Function.h" +#include "llvm/Pass.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/Statistic.h" diff --git a/lib/Analysis/PathNumbering.cpp b/lib/Analysis/PathNumbering.cpp index 80c5222..d4ad726 100644 --- a/lib/Analysis/PathNumbering.cpp +++ b/lib/Analysis/PathNumbering.cpp @@ -31,11 +31,11 @@ #include "llvm/Instructions.h" #include "llvm/Module.h" #include "llvm/Pass.h" +#include "llvm/TypeBuilder.h" #include "llvm/Support/CFG.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/TypeBuilder.h" #include "llvm/Support/raw_ostream.h" #include <queue> diff --git a/lib/Analysis/ProfileInfoLoader.cpp b/lib/Analysis/ProfileInfoLoader.cpp index eaa38da..5c7c97c 100644 --- a/lib/Analysis/ProfileInfoLoader.cpp +++ b/lib/Analysis/ProfileInfoLoader.cpp @@ -83,10 +83,8 @@ const unsigned ProfileInfoLoader::Uncounted = ~0U; // program if the file is invalid or broken. // ProfileInfoLoader::ProfileInfoLoader(const char *ToolName, - const std::string &Filename, - Module &TheModule) : - Filename(Filename), - M(TheModule), Warned(false) { + const std::string &Filename) + : Filename(Filename) { FILE *F = fopen(Filename.c_str(), "rb"); if (F == 0) { errs() << ToolName << ": Error opening '" << Filename << "': "; diff --git a/lib/Analysis/ProfileInfoLoaderPass.cpp b/lib/Analysis/ProfileInfoLoaderPass.cpp index c4da807..5ecf052 100644 --- a/lib/Analysis/ProfileInfoLoaderPass.cpp +++ b/lib/Analysis/ProfileInfoLoaderPass.cpp @@ -152,7 +152,7 @@ void LoaderPass::readEdge(ProfileInfo::Edge e, } bool LoaderPass::runOnModule(Module &M) { - ProfileInfoLoader PIL("profile-loader", Filename, M); + ProfileInfoLoader PIL("profile-loader", Filename); EdgeInformation.clear(); std::vector<unsigned> Counters = PIL.getRawEdgeCounts(); diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp index b507b1e..868f483 100644 --- a/lib/Analysis/RegionInfo.cpp +++ b/lib/Analysis/RegionInfo.cpp @@ -47,7 +47,7 @@ static cl::opt<enum Region::PrintStyle> printStyle("print-region-style", cl::values( clEnumValN(Region::PrintNone, "none", "print no details"), clEnumValN(Region::PrintBB, "bb", - "print regions in detail with block_iterator"), + "print regions in detail with block_node_iterator"), clEnumValN(Region::PrintRN, "rn", "print regions in detail with element_iterator"), clEnumValEnd)); @@ -246,19 +246,19 @@ void Region::verifyRegionNest() const { verifyRegion(); } -Region::block_iterator Region::block_begin() { +Region::block_node_iterator Region::block_node_begin() { return GraphTraits<FlatIt<Region*> >::nodes_begin(this); } -Region::block_iterator Region::block_end() { +Region::block_node_iterator Region::block_node_end() { return GraphTraits<FlatIt<Region*> >::nodes_end(this); } -Region::const_block_iterator Region::block_begin() const { +Region::const_block_node_iterator Region::block_node_begin() const { return GraphTraits<FlatIt<const Region*> >::nodes_begin(this); } -Region::const_block_iterator Region::block_end() const { +Region::const_block_node_iterator Region::block_node_end() const { return GraphTraits<FlatIt<const Region*> >::nodes_end(this); } @@ -425,7 +425,9 @@ void Region::print(raw_ostream &OS, bool print_tree, unsigned level, OS.indent(level*2 + 2); if (Style == PrintBB) { - for (const_block_iterator I = block_begin(), E = block_end(); I!=E; ++I) + for (const_block_node_iterator I = block_node_begin(), + E = block_node_end(); + I != E; ++I) OS << **I << ", "; // TODO: remove the last "," } else if (Style == PrintRN) { for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I) diff --git a/lib/Analysis/RegionPass.cpp b/lib/Analysis/RegionPass.cpp index 3a3529b..c97b5eb 100644 --- a/lib/Analysis/RegionPass.cpp +++ b/lib/Analysis/RegionPass.cpp @@ -195,7 +195,8 @@ public: virtual bool runOnRegion(Region *R, RGPassManager &RGM) { Out << Banner; - for (Region::block_iterator I = R->block_begin(), E = R->block_end(); + for (Region::block_node_iterator I = R->block_node_begin(), + E = R->block_node_end(); I != E; ++I) (*I)->getEntry()->print(Out); diff --git a/lib/Analysis/RegionPrinter.cpp b/lib/Analysis/RegionPrinter.cpp index a1730b0..8b23cc7 100644 --- a/lib/Analysis/RegionPrinter.cpp +++ b/lib/Analysis/RegionPrinter.cpp @@ -122,13 +122,11 @@ struct DOTGraphTraits<RegionInfo*> : public DOTGraphTraits<RegionNode*> { RegionInfo *RI = R->getRegionInfo(); for (Region::const_block_iterator BI = R->block_begin(), - BE = R->block_end(); BI != BE; ++BI) { - BasicBlock *BB = (*BI)->getNodeAs<BasicBlock>(); - if (RI->getRegionFor(BB) == R) + BE = R->block_end(); BI != BE; ++BI) + if (RI->getRegionFor(*BI) == R) O.indent(2 * (depth + 1)) << "Node" - << static_cast<const void*>(RI->getTopLevelRegion()->getBBNode(BB)) + << static_cast<const void*>(RI->getTopLevelRegion()->getBBNode(*BI)) << ";\n"; - } O.indent(2 * depth) << "}\n"; } diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 205227c..a654648 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -826,8 +826,7 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) return getConstant( - cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), - getEffectiveSCEVType(Ty)))); + cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty))); // trunc(trunc(x)) --> trunc(x) if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) @@ -879,13 +878,6 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap); } - // As a special case, fold trunc(undef) to undef. We don't want to - // know too much about SCEVUnknowns, but this special case is handy - // and harmless. - if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Op)) - if (isa<UndefValue>(U->getValue())) - return getSCEV(UndefValue::get(Ty)); - // The cast wasn't folded; create an explicit cast node. We can reuse // the existing insert position since if we get here, we won't have // made any changes which would invalidate it. @@ -906,8 +898,7 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) return getConstant( - cast<ConstantInt>(ConstantExpr::getZExt(SC->getValue(), - getEffectiveSCEVType(Ty)))); + cast<ConstantInt>(ConstantExpr::getZExt(SC->getValue(), Ty))); // zext(zext(x)) --> zext(x) if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) @@ -976,12 +967,15 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no unsigned overflow. const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step); - const SCEV *Add = getAddExpr(Start, ZMul); + const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul), WideTy); + const SCEV *WideStart = getZeroExtendExpr(Start, WideTy); + const SCEV *WideMaxBECount = + getZeroExtendExpr(CastedMaxBECount, WideTy); const SCEV *OperandExtendedAdd = - getAddExpr(getZeroExtendExpr(Start, WideTy), - getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, getZeroExtendExpr(Step, WideTy))); - if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) { + if (ZAdd == 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. @@ -991,13 +985,11 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, } // Similar to above, only this time treat the step value as signed. // This covers loops that count down. - const SCEV *SMul = getMulExpr(CastedMaxBECount, Step); - Add = getAddExpr(Start, SMul); OperandExtendedAdd = - getAddExpr(getZeroExtendExpr(Start, WideTy), - getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, getSignExtendExpr(Step, WideTy))); - if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) { + if (ZAdd == 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); @@ -1164,8 +1156,7 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) return getConstant( - cast<ConstantInt>(ConstantExpr::getSExt(SC->getValue(), - getEffectiveSCEVType(Ty)))); + cast<ConstantInt>(ConstantExpr::getSExt(SC->getValue(), Ty))); // sext(sext(x)) --> sext(x) if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) @@ -1242,12 +1233,15 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no signed overflow. const SCEV *SMul = getMulExpr(CastedMaxBECount, Step); - const SCEV *Add = getAddExpr(Start, SMul); + const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul), WideTy); + const SCEV *WideStart = getSignExtendExpr(Start, WideTy); + const SCEV *WideMaxBECount = + getZeroExtendExpr(CastedMaxBECount, WideTy); const SCEV *OperandExtendedAdd = - getAddExpr(getSignExtendExpr(Start, WideTy), - getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, getSignExtendExpr(Step, WideTy))); - if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) { + if (SAdd == 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. @@ -1257,13 +1251,11 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, } // 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); - Add = getAddExpr(Start, UMul); OperandExtendedAdd = - getAddExpr(getSignExtendExpr(Start, WideTy), - getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, getZeroExtendExpr(Step, WideTy))); - if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) { + if (SAdd == 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. @@ -1345,13 +1337,6 @@ const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW); } - // As a special case, fold anyext(undef) to undef. We don't want to - // know too much about SCEVUnknowns, but this special case is handy - // and harmless. - if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Op)) - if (isa<UndefValue>(U->getValue())) - return getSCEV(UndefValue::get(Ty)); - // If the expression is obviously signed, use the sext cast value. if (isa<SCEVSMaxExpr>(Op)) return SExt; @@ -1839,7 +1824,7 @@ static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) { /// Compute the result of "n choose k", the binomial coefficient. If an /// intermediate computation overflows, Overflow will be set and the return will -/// be garbage. Overflow is not cleared on absense of overflow. +/// be garbage. Overflow is not cleared on absence of overflow. static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow) { // We use the multiplicative formula: // n(n-1)(n-2)...(n-(k-1)) / k(k-1)(k-2)...1 . @@ -2038,63 +2023,67 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, for (unsigned OtherIdx = Idx+1; OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]); ++OtherIdx) { - if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) { - // {A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L> - // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [ - // choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z - // ]]],+,...up to x=2n}. - // Note that the arguments to choose() are always integers with values - // known at compile time, never SCEV objects. - // - // The implementation avoids pointless extra computations when the two - // addrec's are of different length (mathematically, it's equivalent to - // an infinite stream of zeros on the right). - bool OpsModified = false; - for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]); - ++OtherIdx) - if (const SCEVAddRecExpr *OtherAddRec = - dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx])) - if (OtherAddRec->getLoop() == AddRecLoop) { - bool Overflow = false; - Type *Ty = AddRec->getType(); - bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64; - SmallVector<const SCEV*, 7> AddRecOps; - for (int x = 0, xe = AddRec->getNumOperands() + - OtherAddRec->getNumOperands() - 1; - x != xe && !Overflow; ++x) { - const SCEV *Term = getConstant(Ty, 0); - for (int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) { - uint64_t Coeff1 = Choose(x, 2*x - y, Overflow); - for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1), - ze = std::min(x+1, (int)OtherAddRec->getNumOperands()); - z < ze && !Overflow; ++z) { - uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow); - uint64_t Coeff; - if (LargerThan64Bits) - Coeff = umul_ov(Coeff1, Coeff2, Overflow); - else - Coeff = Coeff1*Coeff2; - const SCEV *CoeffTerm = getConstant(Ty, Coeff); - const SCEV *Term1 = AddRec->getOperand(y-z); - const SCEV *Term2 = OtherAddRec->getOperand(z); - Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1,Term2)); - } - } - AddRecOps.push_back(Term); - } - if (!Overflow) { - const SCEV *NewAddRec = getAddRecExpr(AddRecOps, - AddRec->getLoop(), - SCEV::FlagAnyWrap); - if (Ops.size() == 2) return NewAddRec; - Ops[Idx] = AddRec = cast<SCEVAddRecExpr>(NewAddRec); - Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; - OpsModified = true; - } + if (AddRecLoop != cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) + continue; + + // {A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L> + // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [ + // choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z + // ]]],+,...up to x=2n}. + // Note that the arguments to choose() are always integers with values + // known at compile time, never SCEV objects. + // + // The implementation avoids pointless extra computations when the two + // addrec's are of different length (mathematically, it's equivalent to + // an infinite stream of zeros on the right). + bool OpsModified = false; + for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]); + ++OtherIdx) { + const SCEVAddRecExpr *OtherAddRec = + dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]); + if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop) + continue; + + bool Overflow = false; + Type *Ty = AddRec->getType(); + bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64; + SmallVector<const SCEV*, 7> AddRecOps; + for (int x = 0, xe = AddRec->getNumOperands() + + OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) { + const SCEV *Term = getConstant(Ty, 0); + for (int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) { + uint64_t Coeff1 = Choose(x, 2*x - y, Overflow); + for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1), + ze = std::min(x+1, (int)OtherAddRec->getNumOperands()); + z < ze && !Overflow; ++z) { + uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow); + uint64_t Coeff; + if (LargerThan64Bits) + Coeff = umul_ov(Coeff1, Coeff2, Overflow); + else + Coeff = Coeff1*Coeff2; + const SCEV *CoeffTerm = getConstant(Ty, Coeff); + const SCEV *Term1 = AddRec->getOperand(y-z); + const SCEV *Term2 = OtherAddRec->getOperand(z); + Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1,Term2)); } - if (OpsModified) - return getMulExpr(Ops); + } + AddRecOps.push_back(Term); + } + if (!Overflow) { + const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(), + SCEV::FlagAnyWrap); + if (Ops.size() == 2) return NewAddRec; + Ops[Idx] = NewAddRec; + Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; + OpsModified = true; + AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec); + if (!AddRec) + break; + } } + if (OpsModified) + return getMulExpr(Ops); } // Otherwise couldn't fold anything into this recurrence. Move onto the @@ -2723,7 +2712,7 @@ const SCEV *ScalarEvolution::getCouldNotCompute() { const SCEV *ScalarEvolution::getSCEV(Value *V) { assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); - ValueExprMapType::const_iterator I = ValueExprMap.find(V); + ValueExprMapType::const_iterator I = ValueExprMap.find_as(V); if (I != ValueExprMap.end()) return I->second; const SCEV *S = createSCEV(V); @@ -2960,7 +2949,7 @@ ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) { if (!Visited.insert(I)) continue; ValueExprMapType::iterator It = - ValueExprMap.find(static_cast<Value *>(I)); + ValueExprMap.find_as(static_cast<Value *>(I)); if (It != ValueExprMap.end()) { const SCEV *Old = It->second; @@ -3017,7 +3006,7 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { if (BEValueV && StartValueV) { // While we are analyzing this PHI node, handle its value symbolically. const SCEV *SymbolicName = getUnknown(PN); - assert(ValueExprMap.find(PN) == ValueExprMap.end() && + assert(ValueExprMap.find_as(PN) == ValueExprMap.end() && "PHI node already processed?"); ValueExprMap.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); @@ -4081,7 +4070,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { if (!Visited.insert(I)) continue; ValueExprMapType::iterator It = - ValueExprMap.find(static_cast<Value *>(I)); + ValueExprMap.find_as(static_cast<Value *>(I)); if (It != ValueExprMap.end()) { const SCEV *Old = It->second; @@ -4132,7 +4121,8 @@ void ScalarEvolution::forgetLoop(const Loop *L) { Instruction *I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - ValueExprMapType::iterator It = ValueExprMap.find(static_cast<Value *>(I)); + ValueExprMapType::iterator It = + ValueExprMap.find_as(static_cast<Value *>(I)); if (It != ValueExprMap.end()) { forgetMemoizedResults(It->second); ValueExprMap.erase(It); @@ -4165,7 +4155,8 @@ void ScalarEvolution::forgetValue(Value *V) { I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - ValueExprMapType::iterator It = ValueExprMap.find(static_cast<Value *>(I)); + ValueExprMapType::iterator It = + ValueExprMap.find_as(static_cast<Value *>(I)); if (It != ValueExprMap.end()) { forgetMemoizedResults(It->second); ValueExprMap.erase(It); @@ -5379,6 +5370,12 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { SqrtTerm *= B; SqrtTerm -= Four * (A * C); + if (SqrtTerm.isNegative()) { + // The loop is provably infinite. + const SCEV *CNC = SE.getCouldNotCompute(); + return std::make_pair(CNC, CNC); + } + // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest // integer value or else APInt::sqrt() will assert. APInt SqrtVal(SqrtTerm.sqrt()); @@ -5481,7 +5478,7 @@ ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { // 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) + if (StepC == 0 || StepC->getValue()->equalsInt(0)) return getCouldNotCompute(); // For positive steps (counting up until unsigned overflow): @@ -5602,9 +5599,14 @@ static bool HasSameValue(const SCEV *A, const SCEV *B) { /// predicate Pred. Return true iff any changes were made. /// bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, - const SCEV *&LHS, const SCEV *&RHS) { + const SCEV *&LHS, const SCEV *&RHS, + unsigned Depth) { bool Changed = false; + // If we hit the max recursion limit bail out. + if (Depth >= 3) + return false; + // Canonicalize a constant to the right side. if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) { // Check for both operands constant. @@ -5642,6 +5644,16 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_NE: + // Fold ((-1) * %a) + %b == 0 (equivalent to %b-%a == 0) into %a == %b. + if (!RA) + if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(LHS)) + if (const SCEVMulExpr *ME = dyn_cast<SCEVMulExpr>(AE->getOperand(0))) + if (AE->getNumOperands() == 2 && ME->getNumOperands() == 2 && + ME->getOperand(0)->isAllOnesValue()) { + RHS = AE->getOperand(1); + LHS = ME->getOperand(1); + Changed = true; + } break; case ICmpInst::ICMP_UGE: if ((RA - 1).isMinValue()) { @@ -5843,6 +5855,11 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, // TODO: More simplifications are possible here. + // Recursively simplify until we either hit a recursion limit or nothing + // changes. + if (Changed) + return SimplifyICmpOperands(Pred, LHS, RHS, Depth+1); + return Changed; trivially_true: @@ -6040,12 +6057,34 @@ ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L, return false; } +/// RAII wrapper to prevent recursive application of isImpliedCond. +/// ScalarEvolution's PendingLoopPredicates set must be empty unless we are +/// currently evaluating isImpliedCond. +struct MarkPendingLoopPredicate { + Value *Cond; + DenseSet<Value*> &LoopPreds; + bool Pending; + + MarkPendingLoopPredicate(Value *C, DenseSet<Value*> &LP) + : Cond(C), LoopPreds(LP) { + Pending = !LoopPreds.insert(Cond).second; + } + ~MarkPendingLoopPredicate() { + if (!Pending) + LoopPreds.erase(Cond); + } +}; + /// isImpliedCond - Test whether the condition described by Pred, LHS, /// and RHS is true whenever the given Cond value evaluates to true. bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, Value *FoundCondValue, bool Inverse) { + MarkPendingLoopPredicate Mark(FoundCondValue, PendingLoopPredicates); + if (Mark.Pending) + return false; + // Recursively handle And and Or conditions. if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FoundCondValue)) { if (BO->getOpcode() == Instruction::And) { @@ -6572,6 +6611,8 @@ void ScalarEvolution::releaseMemory() { I->second.clear(); } + assert(PendingLoopPredicates.empty() && "isImpliedCond garbage"); + BackedgeTakenCounts.clear(); ConstantEvolutionLoopExitValue.clear(); ValuesAtScopes.clear(); @@ -6859,44 +6900,27 @@ bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) { return getBlockDisposition(S, BB) == ProperlyDominatesBlock; } -bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const { - switch (S->getSCEVType()) { - case scConstant: - return false; - case scTruncate: - case scZeroExtend: - case scSignExtend: { - const SCEVCastExpr *Cast = cast<SCEVCastExpr>(S); - const SCEV *CastOp = Cast->getOperand(); - return Op == CastOp || hasOperand(CastOp, Op); - } - case scAddRecExpr: - case scAddExpr: - case scMulExpr: - case scUMaxExpr: - case scSMaxExpr: { - const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); - for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); - I != E; ++I) { - const SCEV *NAryOp = *I; - if (NAryOp == Op || hasOperand(NAryOp, Op)) - return true; - } - return false; - } - case scUDivExpr: { - const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); - const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS(); - return LHS == Op || hasOperand(LHS, Op) || - RHS == Op || hasOperand(RHS, Op); - } - case scUnknown: - return false; - case scCouldNotCompute: - llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); - default: - llvm_unreachable("Unknown SCEV kind!"); +namespace { +// Search for a SCEV expression node within an expression tree. +// Implements SCEVTraversal::Visitor. +struct SCEVSearch { + const SCEV *Node; + bool IsFound; + + SCEVSearch(const SCEV *N): Node(N), IsFound(false) {} + + bool follow(const SCEV *S) { + IsFound |= (S == Node); + return !IsFound; } + bool isDone() const { return IsFound; } +}; +} + +bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const { + SCEVSearch Search(Op); + visitAll(S, Search); + return Search.IsFound; } void ScalarEvolution::forgetMemoizedResults(const SCEV *S) { diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index 69507be..62710c5 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -37,7 +37,7 @@ Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, // We use this precondition to produce a cast that will dominate all its // uses. In particular, this is crucial for the case where the builder's // insertion point *is* the point where we were asked to put the cast. - // Since we don't know the the builder's insertion point is actually + // Since we don't know the builder's insertion point is actually // where the uses will be added (only that it dominates it), we are // not allowed to move it. BasicBlock::iterator BIP = Builder.GetInsertPoint(); @@ -955,7 +955,8 @@ bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) { // InsertPos must itself dominate IncV so that IncV's new position satisfies // its existing users. - if (!SE.DT->dominates(InsertPos->getParent(), IncV->getParent())) + if (isa<PHINode>(InsertPos) + || !SE.DT->dominates(InsertPos->getParent(), IncV->getParent())) return false; // Check that the chain of IV operands leading back to Phi can be hoisted. @@ -1699,3 +1700,44 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, } return NumElim; } + +namespace { +// Search for a SCEV subexpression that is not safe to expand. Any expression +// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely +// UDiv expressions. We don't know if the UDiv is derived from an IR divide +// instruction, but the important thing is that we prove the denominator is +// nonzero before expansion. +// +// IVUsers already checks that IV-derived expressions are safe. So this check is +// only needed when the expression includes some subexpression that is not IV +// derived. +// +// Currently, we only allow division by a nonzero constant here. If this is +// inadequate, we could easily allow division by SCEVUnknown by using +// ValueTracking to check isKnownNonZero(). +struct SCEVFindUnsafe { + bool IsUnsafe; + + SCEVFindUnsafe(): IsUnsafe(false) {} + + bool follow(const SCEV *S) { + const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S); + if (!D) + return true; + const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS()); + if (SC && !SC->getValue()->isZero()) + return true; + IsUnsafe = true; + return false; + } + bool isDone() const { return IsUnsafe; } +}; +} + +namespace llvm { +bool isSafeToExpand(const SCEV *S) { + SCEVFindUnsafe Search; + visitAll(S, Search); + return !Search.IsUnsafe; +} +} diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index 1418e01..cea34e1 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -694,7 +694,7 @@ void llvm::ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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) + if (dyn_cast_or_null<UndefValue>(P->hasConstantValue())) break; KnownZero = APInt::getAllOnesValue(BitWidth); @@ -1796,6 +1796,37 @@ llvm::GetUnderlyingObject(Value *V, const TargetData *TD, unsigned MaxLookup) { return V; } +void +llvm::GetUnderlyingObjects(Value *V, + SmallVectorImpl<Value *> &Objects, + const TargetData *TD, + unsigned MaxLookup) { + SmallPtrSet<Value *, 4> Visited; + SmallVector<Value *, 4> Worklist; + Worklist.push_back(V); + do { + Value *P = Worklist.pop_back_val(); + P = GetUnderlyingObject(P, TD, MaxLookup); + + if (!Visited.insert(P)) + continue; + + if (SelectInst *SI = dyn_cast<SelectInst>(P)) { + Worklist.push_back(SI->getTrueValue()); + Worklist.push_back(SI->getFalseValue()); + continue; + } + + if (PHINode *PN = dyn_cast<PHINode>(P)) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + Worklist.push_back(PN->getIncomingValue(i)); + continue; + } + + Objects.push_back(P); + } while (!Worklist.empty()); +} + /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer /// are lifetime markers. /// |
