X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FAnalysis.cpp;h=98d4c8afc7b98b0c2ce53e390f1b0c1669e0957b;hb=273cdae7e91c1b11ae9f55c6a78b1e9d820b9ea9;hp=ca08b5b6e0d52e16aef2caa1f33e6ac10eed0f78;hpb=d113448c1dd5f40522c3c02db96e87a9eb59eaf4;p=oota-llvm.git diff --git a/lib/CodeGen/Analysis.cpp b/lib/CodeGen/Analysis.cpp index ca08b5b6e0d..98d4c8afc7b 100644 --- a/lib/CodeGen/Analysis.cpp +++ b/lib/CodeGen/Analysis.cpp @@ -7,13 +7,14 @@ // //===----------------------------------------------------------------------===// // -// This file defines several CodeGen-specific LLVM IR analysis utilties. +// This file defines several CodeGen-specific LLVM IR analysis utilities. // //===----------------------------------------------------------------------===// #include "llvm/CodeGen/Analysis.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/SelectionDAG.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Function.h" @@ -24,12 +25,14 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include "llvm/Target/TargetLowering.h" +#include "llvm/Target/TargetSubtargetInfo.h" +#include "llvm/Transforms/Utils/GlobalStatus.h" + using namespace llvm; -/// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence -/// of insertvalue or extractvalue indices that identify a member, return -/// the linearized index of the start of the member. -/// +/// Compute the linearized index of a member in a nested aggregate/struct/array +/// by recursing and accumulating CurIndex as long as there are indices in the +/// index list. unsigned llvm::ComputeLinearIndex(Type *Ty, const unsigned *Indices, const unsigned *IndicesEnd, @@ -46,18 +49,25 @@ unsigned llvm::ComputeLinearIndex(Type *Ty, EI != EE; ++EI) { if (Indices && *Indices == unsigned(EI - EB)) return ComputeLinearIndex(*EI, Indices+1, IndicesEnd, CurIndex); - CurIndex = ComputeLinearIndex(*EI, 0, 0, CurIndex); + CurIndex = ComputeLinearIndex(*EI, nullptr, nullptr, CurIndex); } + assert(!Indices && "Unexpected out of bound"); return CurIndex; } // Given an array type, recursively traverse the elements. else if (ArrayType *ATy = dyn_cast(Ty)) { Type *EltTy = ATy->getElementType(); - for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { - if (Indices && *Indices == i) - return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex); - CurIndex = ComputeLinearIndex(EltTy, 0, 0, CurIndex); + unsigned NumElts = ATy->getNumElements(); + // Compute the Linear offset when jumping one element of the array + unsigned EltLinearOffset = ComputeLinearIndex(EltTy, nullptr, nullptr, 0); + if (Indices) { + assert(*Indices < NumElts && "Unexpected out of bound"); + // If the indice is inside the array, compute the index to the requested + // elt and recurse inside the element with the end of the indices list + CurIndex += EltLinearOffset* *Indices; + return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex); } + CurIndex += EltLinearOffset*NumElts; return CurIndex; } // We haven't found the type we're looking for, so keep searching. @@ -71,27 +81,27 @@ unsigned llvm::ComputeLinearIndex(Type *Ty, /// If Offsets is non-null, it points to a vector to be filled in /// with the in-memory offsets of each of the individual values. /// -void llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, - SmallVectorImpl &ValueVTs, +void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL, + Type *Ty, SmallVectorImpl &ValueVTs, SmallVectorImpl *Offsets, uint64_t StartingOffset) { // Given a struct type, recursively traverse the elements. if (StructType *STy = dyn_cast(Ty)) { - const StructLayout *SL = TLI.getDataLayout()->getStructLayout(STy); + const StructLayout *SL = DL.getStructLayout(STy); for (StructType::element_iterator EB = STy->element_begin(), EI = EB, EE = STy->element_end(); EI != EE; ++EI) - ComputeValueVTs(TLI, *EI, ValueVTs, Offsets, + ComputeValueVTs(TLI, DL, *EI, ValueVTs, Offsets, StartingOffset + SL->getElementOffset(EI - EB)); return; } // Given an array type, recursively traverse the elements. if (ArrayType *ATy = dyn_cast(Ty)) { Type *EltTy = ATy->getElementType(); - uint64_t EltSize = TLI.getDataLayout()->getTypeAllocSize(EltTy); + uint64_t EltSize = DL.getTypeAllocSize(EltTy); for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) - ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets, + ComputeValueVTs(TLI, DL, EltTy, ValueVTs, Offsets, StartingOffset + i * EltSize); return; } @@ -99,21 +109,22 @@ void llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, if (Ty->isVoidTy()) return; // Base case: we can get an EVT for this LLVM IR type. - ValueVTs.push_back(TLI.getValueType(Ty)); + ValueVTs.push_back(TLI.getValueType(DL, Ty)); if (Offsets) Offsets->push_back(StartingOffset); } /// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V. -GlobalVariable *llvm::ExtractTypeInfo(Value *V) { +GlobalValue *llvm::ExtractTypeInfo(Value *V) { V = V->stripPointerCasts(); - GlobalVariable *GV = dyn_cast(V); + GlobalValue *GV = dyn_cast(V); + GlobalVariable *Var = dyn_cast(V); - if (GV && GV->getName() == "llvm.eh.catch.all.value") { - assert(GV->hasInitializer() && + if (Var && Var->getName() == "llvm.eh.catch.all.value") { + assert(Var->hasInitializer() && "The EH catch-all value must have an initializer"); - Value *Init = GV->getInitializer(); - GV = dyn_cast(Init); + Value *Init = Var->getInitializer(); + GV = dyn_cast(Init); if (!GV) V = cast(Init); } @@ -222,13 +233,14 @@ static bool isNoopBitcast(Type *T1, Type *T2, static const Value *getNoopInput(const Value *V, SmallVectorImpl &ValLoc, unsigned &DataBits, - const TargetLoweringBase &TLI) { + const TargetLoweringBase &TLI, + const DataLayout &DL) { while (true) { // Try to look through V1; if V1 is not an instruction, it can't be looked // through. const Instruction *I = dyn_cast(V); if (!I || I->getNumOperands() == 0) return V; - const Value *NoopInput = 0; + const Value *NoopInput = nullptr; Value *Op = I->getOperand(0); if (isa(I)) { @@ -244,16 +256,16 @@ static const Value *getNoopInput(const Value *V, // Make sure this isn't a truncating or extending cast. We could // support this eventually, but don't bother for now. if (!isa(I->getType()) && - TLI.getPointerTy().getSizeInBits() == - cast(Op->getType())->getBitWidth()) + DL.getPointerSizeInBits() == + cast(Op->getType())->getBitWidth()) NoopInput = Op; } else if (isa(I)) { // Look through ptrtoint. // Make sure this isn't a truncating or extending cast. We could // support this eventually, but don't bother for now. if (!isa(I->getType()) && - TLI.getPointerTy().getSizeInBits() == - cast(I->getType())->getBitWidth()) + DL.getPointerSizeInBits() == + cast(I->getType())->getBitWidth()) NoopInput = Op; } else if (isa(I) && TLI.allowTruncateForTailCall(Op->getType(), I->getType())) { @@ -284,8 +296,8 @@ static const Value *getNoopInput(const Value *V, } else if (const InsertValueInst *IVI = dyn_cast(V)) { // Value may come from either the aggregate or the scalar ArrayRef InsertLoc = IVI->getIndices(); - if (std::equal(InsertLoc.rbegin(), InsertLoc.rend(), - ValLoc.rbegin())) { + if (ValLoc.size() >= InsertLoc.size() && + std::equal(InsertLoc.begin(), InsertLoc.end(), ValLoc.rbegin())) { // The type being inserted is a nested sub-type of the aggregate; we // have to remove those initial indices to get the location we're // interested in for the operand. @@ -301,8 +313,7 @@ static const Value *getNoopInput(const Value *V, // previous aggregate. Combine the two paths to obtain the true address of // our element. ArrayRef ExtractLoc = EVI->getIndices(); - std::copy(ExtractLoc.rbegin(), ExtractLoc.rend(), - std::back_inserter(ValLoc)); + ValLoc.append(ExtractLoc.rbegin(), ExtractLoc.rend()); NoopInput = Op; } // Terminate if we couldn't find anything to look through. @@ -320,14 +331,16 @@ static const Value *getNoopInput(const Value *V, static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal, SmallVectorImpl &RetIndices, SmallVectorImpl &CallIndices, - const TargetLoweringBase &TLI) { + bool AllowDifferingSizes, + const TargetLoweringBase &TLI, + const DataLayout &DL) { // Trace the sub-value needed by the return value as far back up the graph as // possible, in the hope that it will intersect with the value produced by the // call. In the simple case with no "returned" attribute, the hope is actually // that we end up back at the tail call instruction itself. unsigned BitsRequired = UINT_MAX; - RetVal = getNoopInput(RetVal, RetIndices, BitsRequired, TLI); + RetVal = getNoopInput(RetVal, RetIndices, BitsRequired, TLI, DL); // If this slot in the value returned is undef, it doesn't matter what the // call puts there, it'll be fine. @@ -339,7 +352,7 @@ static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal, // a "returned" attribute, the search will be blocked immediately and the loop // a Noop. unsigned BitsProvided = UINT_MAX; - CallVal = getNoopInput(CallVal, CallIndices, BitsProvided, TLI); + CallVal = getNoopInput(CallVal, CallIndices, BitsProvided, TLI, DL); // There's no hope if we can't actually trace them to (the same part of!) the // same value. @@ -350,7 +363,8 @@ static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal, // all the bits that are needed by the "ret" have been provided by the "tail // call". FIXME: with sufficiently cunning bit-tracking, we could look through // extensions too. - if (BitsProvided < BitsRequired) + if (BitsProvided < BitsRequired || + (!AllowDifferingSizes && BitsProvided != BitsRequired)) return false; return true; @@ -382,9 +396,8 @@ static bool indexReallyValid(CompositeType *T, unsigned Idx) { /// function again on a finished iterator will repeatedly return /// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty /// aggregate or a non-aggregate -static bool -advanceToNextLeafType(SmallVectorImpl &SubTypes, - SmallVectorImpl &Path) { +static bool advanceToNextLeafType(SmallVectorImpl &SubTypes, + SmallVectorImpl &Path) { // First march back up the tree until we can successfully increment one of the // coordinates in Path. while (!Path.empty() && !indexReallyValid(SubTypes.back(), Path.back() + 1)) { @@ -454,8 +467,8 @@ static bool firstRealType(Type *Next, /// Set the iterator data-structures to the next non-empty, non-aggregate /// subtype. -bool nextRealType(SmallVectorImpl &SubTypes, - SmallVectorImpl &Path) { +static bool nextRealType(SmallVectorImpl &SubTypes, + SmallVectorImpl &Path) { do { if (!advanceToNextLeafType(SubTypes, Path)) return false; @@ -473,8 +486,7 @@ bool nextRealType(SmallVectorImpl &SubTypes, /// between it and the return. /// /// This function only tests target-independent requirements. -bool llvm::isInTailCallPosition(ImmutableCallSite CS, - const TargetLowering &TLI) { +bool llvm::isInTailCallPosition(ImmutableCallSite CS, const TargetMachine &TM) { const Instruction *I = CS.getInstruction(); const BasicBlock *ExitBB = I->getParent(); const TerminatorInst *Term = ExitBB->getTerminator(); @@ -489,16 +501,14 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, // longjmp on x86), it can end up causing miscompilation that has not // been fully understood. if (!Ret && - (!TLI.getTargetMachine().Options.GuaranteedTailCallOpt || - !isa(Term))) + (!TM.Options.GuaranteedTailCallOpt || !isa(Term))) return false; // If I will have a chain, make sure no other instruction that will have a // chain interposes between I and the return. if (I->mayHaveSideEffects() || I->mayReadFromMemory() || !isSafeToSpeculativelyExecute(I)) - for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ; - --BBI) { + for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) { if (&*BBI == I) break; // Debug info intrinsics do not get in the way of tail call optimization. @@ -509,6 +519,15 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, return false; } + const Function *F = ExitBB->getParent(); + return returnTypeIsEligibleForTailCall( + F, I, Ret, *TM.getSubtargetImpl(*F)->getTargetLowering()); +} + +bool llvm::returnTypeIsEligibleForTailCall(const Function *F, + const Instruction *I, + const ReturnInst *Ret, + const TargetLoweringBase &TLI) { // If the block ends with a void return or unreachable, it doesn't matter // what the call's return type is. if (!Ret || Ret->getNumOperands() == 0) return true; @@ -517,19 +536,38 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, // return type is. if (isa(Ret->getOperand(0))) return true; - // Conservatively require the attributes of the call to match those of - // the return. Ignore noalias because it doesn't affect the call sequence. - const Function *F = ExitBB->getParent(); - AttributeSet CallerAttrs = F->getAttributes(); - if (AttrBuilder(CallerAttrs, AttributeSet::ReturnIndex). - removeAttribute(Attribute::NoAlias) != - AttrBuilder(CallerAttrs, AttributeSet::ReturnIndex). - removeAttribute(Attribute::NoAlias)) - return false; + // Make sure the attributes attached to each return are compatible. + AttrBuilder CallerAttrs(F->getAttributes(), + AttributeSet::ReturnIndex); + AttrBuilder CalleeAttrs(cast(I)->getAttributes(), + AttributeSet::ReturnIndex); + + // Noalias is completely benign as far as calling convention goes, it + // shouldn't affect whether the call is a tail call. + CallerAttrs = CallerAttrs.removeAttribute(Attribute::NoAlias); + CalleeAttrs = CalleeAttrs.removeAttribute(Attribute::NoAlias); + + bool AllowDifferingSizes = true; + if (CallerAttrs.contains(Attribute::ZExt)) { + if (!CalleeAttrs.contains(Attribute::ZExt)) + return false; + + AllowDifferingSizes = false; + CallerAttrs.removeAttribute(Attribute::ZExt); + CalleeAttrs.removeAttribute(Attribute::ZExt); + } else if (CallerAttrs.contains(Attribute::SExt)) { + if (!CalleeAttrs.contains(Attribute::SExt)) + return false; + + AllowDifferingSizes = false; + CallerAttrs.removeAttribute(Attribute::SExt); + CalleeAttrs.removeAttribute(Attribute::SExt); + } - // It's not safe to eliminate the sign / zero extension of the return value. - if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) || - CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt)) + // If they're still different, there's some facet we don't understand + // (currently only "inreg", but in future who knows). It may be OK but the + // only safe option is to reject the tail call. + if (CallerAttrs != CalleeAttrs) return false; const Value *RetVal = Ret->getOperand(0), *CallVal = I; @@ -564,14 +602,14 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, // The manipulations performed when we're looking through an insertvalue or // an extractvalue would happen at the front of the RetPath list, so since // we have to copy it anyway it's more efficient to create a reversed copy. - using std::copy; - SmallVector TmpRetPath, TmpCallPath; - copy(RetPath.rbegin(), RetPath.rend(), std::back_inserter(TmpRetPath)); - copy(CallPath.rbegin(), CallPath.rend(), std::back_inserter(TmpCallPath)); + SmallVector TmpRetPath(RetPath.rbegin(), RetPath.rend()); + SmallVector TmpCallPath(CallPath.rbegin(), CallPath.rend()); // Finally, we can check whether the value produced by the tail call at this // index is compatible with the value we return. - if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath, TLI)) + if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath, + AllowDifferingSizes, TLI, + F->getParent()->getDataLayout())) return false; CallEmpty = !nextRealType(CallSubTypes, CallPath); @@ -579,3 +617,29 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, return true; } + +bool llvm::canBeOmittedFromSymbolTable(const GlobalValue *GV) { + if (!GV->hasLinkOnceODRLinkage()) + return false; + + if (GV->hasUnnamedAddr()) + return true; + + // If it is a non constant variable, it needs to be uniqued across shared + // objects. + if (const GlobalVariable *Var = dyn_cast(GV)) { + if (!Var->isConstant()) + return false; + } + + // An alias can point to a variable. We could try to resolve the alias to + // decide, but for now just don't hide them. + if (isa(GV)) + return false; + + GlobalStatus GS; + if (GlobalStatus::analyzeGlobal(GV, GS)) + return false; + + return !GS.IsCompared; +}