X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FAnalysis.cpp;h=4731af5089ac3927fc942cc0a6a23d68ac069195;hb=9e639e8fd95488cb4c8ef2f7f3a41919acb29ac4;hp=dd11d15975c14b6c4d08a5a86dca19e46517ea1e;hpb=5b0d9465375c4e175f5805038c5ef1d7d11193bd;p=oota-llvm.git diff --git a/lib/CodeGen/Analysis.cpp b/lib/CodeGen/Analysis.cpp index dd11d15975c..4731af5089a 100644 --- a/lib/CodeGen/Analysis.cpp +++ b/lib/CodeGen/Analysis.cpp @@ -13,19 +13,17 @@ #include "llvm/CodeGen/Analysis.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/LLVMContext.h" -#include "llvm/Module.h" #include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/SelectionDAG.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Target/TargetLowering.h" -#include "llvm/Target/TargetOptions.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" +#include "llvm/Target/TargetLowering.h" using namespace llvm; /// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence @@ -79,7 +77,7 @@ void llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, uint64_t StartingOffset) { // Given a struct type, recursively traverse the elements. if (StructType *STy = dyn_cast(Ty)) { - const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy); + const StructLayout *SL = TLI.getDataLayout()->getStructLayout(STy); for (StructType::element_iterator EB = STy->element_begin(), EI = EB, EE = STy->element_end(); @@ -91,7 +89,7 @@ void llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, // Given an array type, recursively traverse the elements. if (ArrayType *ATy = dyn_cast(Ty)) { Type *EltTy = ATy->getElementType(); - uint64_t EltSize = TLI.getTargetData()->getTypeAllocSize(EltTy); + uint64_t EltSize = TLI.getDataLayout()->getTypeAllocSize(EltTy); for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets, StartingOffset + i * EltSize); @@ -203,62 +201,161 @@ ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) { } } +static bool isNoopBitcast(Type *T1, Type *T2, + const TargetLowering& TLI) { + return T1 == T2 || (T1->isPointerTy() && T2->isPointerTy()) || + (isa(T1) && isa(T2) && + TLI.isTypeLegal(EVT::getEVT(T1)) && TLI.isTypeLegal(EVT::getEVT(T2))); +} -/// getNoopInput - If V is a noop (i.e., lowers to no machine code), look -/// through it (and any transitive noop operands to it) and return its input -/// value. This is used to determine if a tail call can be formed. -/// -static const Value *getNoopInput(const Value *V, const TargetLowering &TLI) { - // If V is not an instruction, it can't be looked through. - const Instruction *I = dyn_cast(V); - if (I == 0 || !I->hasOneUse() || I->getNumOperands() == 0) return V; - - Value *Op = I->getOperand(0); +/// sameNoopInput - Return true if V1 == V2, else if either V1 or V2 is a noop +/// (i.e., lowers to no machine code), look through it (and any transitive noop +/// operands to it) and check if it has the same noop input value. This is +/// used to determine if a tail call can be formed. +static bool sameNoopInput(const Value *V1, const Value *V2, + SmallVectorImpl &Els1, + SmallVectorImpl &Els2, + const TargetLowering &TLI) { + using std::swap; + bool swapParity = false; + bool equalEls = Els1 == Els2; + while (true) { + if ((equalEls && V1 == V2) || isa(V1) || isa(V2)) { + if (swapParity) + // Revert to original Els1 and Els2 to avoid confusing recursive calls + swap(Els1, Els2); + return true; + } - // Look through truly no-op truncates. - if (isa(I) && - TLI.isTruncateFree(I->getOperand(0)->getType(), I->getType())) - return getNoopInput(I->getOperand(0), TLI); - - // Look through truly no-op bitcasts. - if (isa(I)) { - // No type change at all. - if (Op->getType() == I->getType()) - return getNoopInput(Op, TLI); + // Try to look through V1; if V1 is not an instruction, it can't be looked + // through. + const Instruction *I = dyn_cast(V1); + const Value *NoopInput = 0; + if (I != 0 && I->getNumOperands() > 0) { + Value *Op = I->getOperand(0); + if (isa(I)) { + // Look through truly no-op truncates. + if (TLI.isTruncateFree(Op->getType(), I->getType())) + NoopInput = Op; + } else if (isa(I)) { + // Look through truly no-op bitcasts. + if (isNoopBitcast(Op->getType(), I->getType(), TLI)) + NoopInput = Op; + } else if (isa(I)) { + // Look through getelementptr + if (cast(I)->hasAllZeroIndices()) + NoopInput = Op; + } else if (isa(I)) { + // Look through inttoptr. + // 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()) + 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()) + NoopInput = Op; + } else if (isa(I)) { + // Look through call + for (User::const_op_iterator i = I->op_begin(), + // Skip Callee + e = I->op_end() - 1; + i != e; ++i) { + unsigned attrInd = i - I->op_begin() + 1; + if (cast(I)->paramHasAttr(attrInd, Attribute::Returned) && + isNoopBitcast((*i)->getType(), I->getType(), TLI)) { + NoopInput = *i; + break; + } + } + } else if (isa(I)) { + // Look through invoke + for (User::const_op_iterator i = I->op_begin(), + // Skip BB, BB, Callee + e = I->op_end() - 3; + i != e; ++i) { + unsigned attrInd = i - I->op_begin() + 1; + if (cast(I)->paramHasAttr(attrInd, Attribute::Returned) && + isNoopBitcast((*i)->getType(), I->getType(), TLI)) { + NoopInput = *i; + break; + } + } + } + } - // Pointer to pointer cast. - if (Op->getType()->isPointerTy() && I->getType()->isPointerTy()) - return getNoopInput(Op, TLI); - - if (isa(Op->getType()) && isa(I->getType()) && - TLI.isTypeLegal(EVT::getEVT(Op->getType())) && - TLI.isTypeLegal(EVT::getEVT(I->getType()))) - return getNoopInput(Op, TLI); - } - - // Look through inttoptr. - if (isa(I) && !isa(I->getType())) { - // Make sure this isn't a truncating or extending cast. We could support - // this eventually, but don't bother for now. - if (TLI.getPointerTy().getSizeInBits() == - cast(Op->getType())->getBitWidth()) - return getNoopInput(Op, TLI); - } + if (NoopInput) { + V1 = NoopInput; + continue; + } - // Look through ptrtoint. - if (isa(I) && !isa(I->getType())) { - // Make sure this isn't a truncating or extending cast. We could support - // this eventually, but don't bother for now. - if (TLI.getPointerTy().getSizeInBits() == - cast(I->getType())->getBitWidth()) - return getNoopInput(Op, TLI); + // If we already swapped, avoid infinite loop + if (swapParity) + break; + + // Otherwise, swap V1<->V2, Els1<->Els2 + swap(V1, V2); + swap(Els1, Els2); + swapParity = !swapParity; } + for (unsigned n = 0; n < 2; ++n) { + if (isa(V1)) { + if (isa(V1->getType())) { + // Look through insertvalue + unsigned i, e; + for (i = 0, e = cast(V1->getType())->getNumElements(); + i != e; ++i) { + const Value *InScalar = FindInsertedValue(const_cast(V1), i); + if (InScalar == 0) + break; + Els1.push_back(i); + if (!sameNoopInput(InScalar, V2, Els1, Els2, TLI)) { + Els1.pop_back(); + break; + } + Els1.pop_back(); + } + if (i == e) { + if (swapParity) + swap(Els1, Els2); + return true; + } + } + } else if (!Els1.empty() && isa(V1)) { + const ExtractValueInst *EVI = cast(V1); + unsigned i = Els1.back(); + // If the scalar value being inserted is an extractvalue of the right + // index from the call, then everything is good. + if (isa(EVI->getOperand(0)->getType()) && + EVI->getNumIndices() == 1 && EVI->getIndices()[0] == i) { + // Look through extractvalue + Els1.pop_back(); + if (sameNoopInput(EVI->getOperand(0), V2, Els1, Els2, TLI)) { + Els1.push_back(i); + if (swapParity) + swap(Els1, Els2); + return true; + } + Els1.push_back(i); + } + } - // Otherwise it's not something we can look through. - return V; -} + swap(V1, V2); + swap(Els1, Els2); + swapParity = !swapParity; + } + if (swapParity) + swap(Els1, Els2); + return false; +} /// Test if the given instruction is in a position to be optimized /// with a tail-call. This roughly means that it's in a block with @@ -266,7 +363,7 @@ static const Value *getNoopInput(const Value *V, const TargetLowering &TLI) { /// between it and the return. /// /// This function only tests target-independent requirements. -bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, +bool llvm::isInTailCallPosition(ImmutableCallSite CS, const TargetLowering &TLI) { const Instruction *I = CS.getInstruction(); const BasicBlock *ExitBB = I->getParent(); @@ -313,32 +410,19 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, // 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(); - Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); - if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) - return false; - - // It's not safe to eliminate the sign / zero extension of the return value. - if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) - return false; - - // Otherwise, make sure the unmodified return value of I is the return value. - return getNoopInput(Ret->getOperand(0), TLI) == I; -} - -bool llvm::isInTailCallPosition(SelectionDAG &DAG, SDNode *Node, - SDValue &Chain, const TargetLowering &TLI) { - const Function *F = DAG.getMachineFunction().getFunction(); - - // Conservatively require the attributes of the call to match those of - // the return. Ignore noalias because it doesn't affect the call sequence. - Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); - if (CallerRetAttr & ~Attribute::NoAlias) + AttributeSet CallerAttrs = F->getAttributes(); + if (AttrBuilder(CallerAttrs, AttributeSet::ReturnIndex). + removeAttribute(Attribute::NoAlias) != + AttrBuilder(CallerAttrs, AttributeSet::ReturnIndex). + removeAttribute(Attribute::NoAlias)) return false; // It's not safe to eliminate the sign / zero extension of the return value. - if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) + if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) || + CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt)) return false; - // Check if the only use is a function return node. - return TLI.isUsedByReturnOnly(Node, Chain); + // Otherwise, make sure the return value and I have the same value + SmallVector Els1, Els2; + return sameNoopInput(Ret->getOperand(0), I, Els1, Els2, TLI); }