X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FAnalysis.cpp;h=1f3f5a5f3836469c8fce37d65106b05257bedb4b;hb=ebd7eabca4c090175b71f221e880f8bd937a4523;hp=2cf3c6666cd7765dc7e94c65a2db0aea794f3238;hpb=44ab89eb376af838d1123293a79975aede501464;p=oota-llvm.git diff --git a/lib/CodeGen/Analysis.cpp b/lib/CodeGen/Analysis.cpp index 2cf3c6666cd..1f3f5a5f383 100644 --- a/lib/CodeGen/Analysis.cpp +++ b/lib/CodeGen/Analysis.cpp @@ -1,4 +1,4 @@ -//===-- Analysis.cpp - CodeGen LLVM IR Analysis Utilities --*- C++ ------*-===// +//===-- Analysis.cpp - CodeGen LLVM IR Analysis Utilities -----------------===// // // The LLVM Compiler Infrastructure // @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/Analysis.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/DerivedTypes.h" #include "llvm/Function.h" #include "llvm/Instructions.h" @@ -19,6 +20,7 @@ #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" @@ -30,7 +32,7 @@ using namespace llvm; /// of insertvalue or extractvalue indices that identify a member, return /// the linearized index of the start of the member. /// -unsigned llvm::ComputeLinearIndex(const Type *Ty, +unsigned llvm::ComputeLinearIndex(Type *Ty, const unsigned *Indices, const unsigned *IndicesEnd, unsigned CurIndex) { @@ -39,7 +41,7 @@ unsigned llvm::ComputeLinearIndex(const Type *Ty, return CurIndex; // Given a struct type, recursively traverse the elements. - if (const StructType *STy = dyn_cast(Ty)) { + if (StructType *STy = dyn_cast(Ty)) { for (StructType::element_iterator EB = STy->element_begin(), EI = EB, EE = STy->element_end(); @@ -51,8 +53,8 @@ unsigned llvm::ComputeLinearIndex(const Type *Ty, return CurIndex; } // Given an array type, recursively traverse the elements. - else if (const ArrayType *ATy = dyn_cast(Ty)) { - const Type *EltTy = ATy->getElementType(); + 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); @@ -71,12 +73,12 @@ unsigned llvm::ComputeLinearIndex(const 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, const Type *Ty, +void llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, SmallVectorImpl &ValueVTs, SmallVectorImpl *Offsets, uint64_t StartingOffset) { // Given a struct type, recursively traverse the elements. - if (const StructType *STy = dyn_cast(Ty)) { + if (StructType *STy = dyn_cast(Ty)) { const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy); for (StructType::element_iterator EB = STy->element_begin(), EI = EB, @@ -87,8 +89,8 @@ void llvm::ComputeValueVTs(const TargetLowering &TLI, const Type *Ty, return; } // Given an array type, recursively traverse the elements. - if (const ArrayType *ATy = dyn_cast(Ty)) { - const Type *EltTy = ATy->getElementType(); + if (ArrayType *ATy = dyn_cast(Ty)) { + Type *EltTy = ATy->getElementType(); uint64_t EltSize = TLI.getTargetData()->getTypeAllocSize(EltTy); for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets, @@ -148,33 +150,37 @@ llvm::hasInlineAsmMemConstraint(InlineAsm::ConstraintInfoVector &CInfos, /// consideration of global floating-point math flags. /// ISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) { - ISD::CondCode FPC, FOC; switch (Pred) { - case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break; - case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break; - case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break; - case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break; - case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break; - case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break; - case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break; - case FCmpInst::FCMP_ORD: FOC = FPC = ISD::SETO; break; - case FCmpInst::FCMP_UNO: FOC = FPC = ISD::SETUO; break; - case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break; - case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break; - case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break; - case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break; - case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break; - case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break; - case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break; - default: - llvm_unreachable("Invalid FCmp predicate opcode!"); - FOC = FPC = ISD::SETFALSE; - break; + case FCmpInst::FCMP_FALSE: return ISD::SETFALSE; + case FCmpInst::FCMP_OEQ: return ISD::SETOEQ; + case FCmpInst::FCMP_OGT: return ISD::SETOGT; + case FCmpInst::FCMP_OGE: return ISD::SETOGE; + case FCmpInst::FCMP_OLT: return ISD::SETOLT; + case FCmpInst::FCMP_OLE: return ISD::SETOLE; + case FCmpInst::FCMP_ONE: return ISD::SETONE; + case FCmpInst::FCMP_ORD: return ISD::SETO; + case FCmpInst::FCMP_UNO: return ISD::SETUO; + case FCmpInst::FCMP_UEQ: return ISD::SETUEQ; + case FCmpInst::FCMP_UGT: return ISD::SETUGT; + case FCmpInst::FCMP_UGE: return ISD::SETUGE; + case FCmpInst::FCMP_ULT: return ISD::SETULT; + case FCmpInst::FCMP_ULE: return ISD::SETULE; + case FCmpInst::FCMP_UNE: return ISD::SETUNE; + case FCmpInst::FCMP_TRUE: return ISD::SETTRUE; + default: llvm_unreachable("Invalid FCmp predicate opcode!"); + } +} + +ISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) { + switch (CC) { + case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ; + case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE; + case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT; + case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE; + case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT; + case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE; + default: return CC; } - if (NoNaNsFPMath) - return FOC; - else - return FPC; } /// getICmpCondCode - Return the ISD condition code corresponding to @@ -194,10 +200,66 @@ ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) { case ICmpInst::ICMP_UGT: return ISD::SETUGT; default: llvm_unreachable("Invalid ICmp predicate opcode!"); - return ISD::SETNE; } } + +/// 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); + + // 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); + + // 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); + } + + // 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); + } + + + // Otherwise it's not something we can look through. + return V; +} + + /// 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 /// a return and there's nothing that needs to be scheduled @@ -210,7 +272,6 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, const BasicBlock *ExitBB = I->getParent(); const TerminatorInst *Term = ExitBB->getTerminator(); const ReturnInst *Ret = dyn_cast(Term); - const Function *F = ExitBB->getParent(); // The block must end in a return statement or unreachable. // @@ -221,12 +282,14 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, // longjmp on x86), it can end up causing miscompilation that has not // been fully understood. if (!Ret && - (!GuaranteedTailCallOpt || !isa(Term))) return false; + (!TLI.getTargetMachine().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() || - !I->isSafeToSpeculativelyExecute()) + !isSafeToSpeculativelyExecute(I)) for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ; --BBI) { if (&*BBI == I) @@ -235,7 +298,7 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, if (isa(BBI)) continue; if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() || - !BBI->isSafeToSpeculativelyExecute()) + !isSafeToSpeculativelyExecute(BBI)) return false; } @@ -249,37 +312,55 @@ 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. - unsigned CallerRetAttr = F->getAttributes().getRetAttributes(); + 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)) + if (CallerRetAttr.hasZExtAttr() || CallerRetAttr.hasSExtAttr()) return false; // Otherwise, make sure the unmodified return value of I is the return value. - for (const Instruction *U = dyn_cast(Ret->getOperand(0)); ; - U = dyn_cast(U->getOperand(0))) { - if (!U) + // We handle two cases: multiple return values + scalars. + Value *RetVal = Ret->getOperand(0); + if (!isa(RetVal) || !isa(RetVal->getType())) + // Handle scalars first. + return getNoopInput(Ret->getOperand(0), TLI) == I; + + // If this is an aggregate return, look through the insert/extract values and + // see if each is transparent. + for (unsigned i = 0, e =cast(RetVal->getType())->getNumElements(); + i != e; ++i) { + const Value *InScalar = FindInsertedValue(RetVal, i); + if (InScalar == 0) return false; + InScalar = getNoopInput(InScalar, TLI); + + // If the scalar value being inserted is an extractvalue of the right index + // from the call, then everything is good. + const ExtractValueInst *EVI = dyn_cast(InScalar); + if (EVI == 0 || EVI->getOperand(0) != I || EVI->getNumIndices() != 1 || + EVI->getIndices()[0] != i) return false; - if (!U->hasOneUse()) - return false; - if (U == I) - break; - // Check for a truly no-op truncate. - if (isa(U) && - TLI.isTruncateFree(U->getOperand(0)->getType(), U->getType())) - continue; - // Check for a truly no-op bitcast. - if (isa(U) && - (U->getOperand(0)->getType() == U->getType() || - (U->getOperand(0)->getType()->isPointerTy() && - U->getType()->isPointerTy()))) - continue; - // Otherwise it's not a true no-op. - return false; } - + return true; } +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) + return false; + + // It's not safe to eliminate the sign / zero extension of the return value. + if (CallerRetAttr.hasZExtAttr() || CallerRetAttr.hasSExtAttr()) + return false; + + // Check if the only use is a function return node. + return TLI.isUsedByReturnOnly(Node, Chain); +}