X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FCodeMetrics.cpp;h=4090b4cd752b64113ba10d6ee32f28744d07517c;hb=e78257c891d8a6148703cb74655640d175e3f570;hp=1dff3d4948960cc6e611ac87dc3c8005576c80f7;hpb=0b8c9a80f20772c3793201ab5b251d3520b9cea3;p=oota-llvm.git diff --git a/lib/Analysis/CodeMetrics.cpp b/lib/Analysis/CodeMetrics.cpp index 1dff3d49489..4090b4cd752 100644 --- a/lib/Analysis/CodeMetrics.cpp +++ b/lib/Analysis/CodeMetrics.cpp @@ -11,120 +11,106 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CodeMetrics.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Function.h" #include "llvm/IR/IntrinsicInst.h" -#include "llvm/Support/CallSite.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +#define DEBUG_TYPE "code-metrics" 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(ImmutableCallSite CS) { - if (isa(CS.getInstruction())) - return true; +static void completeEphemeralValues(SmallVector &WorkSet, + SmallPtrSetImpl &EphValues) { + SmallPtrSet Visited; - const Function *F = CS.getCalledFunction(); - if (!F) return false; + // Make sure that all of the items in WorkSet are in our EphValues set. + EphValues.insert(WorkSet.begin(), WorkSet.end()); - if (F->hasLocalLinkage()) return false; + // Note: We don't speculate PHIs here, so we'll miss instruction chains kept + // alive only by ephemeral values. - if (!F->hasName()) return false; + while (!WorkSet.empty()) { + const Value *V = WorkSet.front(); + WorkSet.erase(WorkSet.begin()); - StringRef Name = F->getName(); + if (!Visited.insert(V).second) + continue; - // These will all likely lower to a single selection DAG node. - if (Name == "copysign" || Name == "copysignf" || Name == "copysignl" || - Name == "fabs" || Name == "fabsf" || Name == "fabsl" || - Name == "sin" || Name == "sinf" || Name == "sinl" || - Name == "cos" || Name == "cosf" || Name == "cosl" || - Name == "sqrt" || Name == "sqrtf" || Name == "sqrtl" ) - return true; + // If all uses of this value are ephemeral, then so is this value. + if (!std::all_of(V->user_begin(), V->user_end(), + [&](const User *U) { return EphValues.count(U); })) + continue; - // These are all likely to be optimized into something smaller. - if (Name == "pow" || Name == "powf" || Name == "powl" || - Name == "exp2" || Name == "exp2l" || Name == "exp2f" || - Name == "floor" || Name == "floorf" || Name == "ceil" || - Name == "round" || Name == "ffs" || Name == "ffsl" || - Name == "abs" || Name == "labs" || Name == "llabs") - return true; + EphValues.insert(V); + DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n"); - return false; + if (const User *U = dyn_cast(V)) + for (const Value *J : U->operands()) { + if (isSafeToSpeculativelyExecute(J)) + WorkSet.push_back(J); + } + } } -bool llvm::isInstructionFree(const Instruction *I, const DataLayout *TD) { - if (isa(I)) - return true; - - // If a GEP has all constant indices, it will probably be folded with - // a load/store. - if (const GetElementPtrInst *GEP = dyn_cast(I)) - return GEP->hasAllConstantIndices(); - - if (const IntrinsicInst *II = dyn_cast(I)) { - switch (II->getIntrinsicID()) { - default: - return false; - 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::objectsize: - case Intrinsic::ptr_annotation: - case Intrinsic::var_annotation: - // These intrinsics don't count as size. - return true; - } +// Find all ephemeral values. +void CodeMetrics::collectEphemeralValues( + const Loop *L, AssumptionCache *AC, + SmallPtrSetImpl &EphValues) { + SmallVector WorkSet; + + for (auto &AssumeVH : AC->assumptions()) { + if (!AssumeVH) + continue; + Instruction *I = cast(AssumeVH); + + // Filter out call sites outside of the loop so we don't to a function's + // worth of work for each of its loops (and, in the common case, ephemeral + // values in the loop are likely due to @llvm.assume calls in the loop). + if (!L->contains(I->getParent())) + continue; + + WorkSet.push_back(I); } - if (const CastInst *CI = dyn_cast(I)) { - // Noop casts, including ptr <-> int, don't count. - 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(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(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(CI) && - TD->isLegalInteger(TD->getTypeSizeInBits(CI->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 - // nop on most sane targets. - if (isa(CI->getOperand(0))) - return true; + completeEphemeralValues(WorkSet, EphValues); +} + +void CodeMetrics::collectEphemeralValues( + const Function *F, AssumptionCache *AC, + SmallPtrSetImpl &EphValues) { + SmallVector WorkSet; + + for (auto &AssumeVH : AC->assumptions()) { + if (!AssumeVH) + continue; + Instruction *I = cast(AssumeVH); + assert(I->getParent()->getParent() == F && + "Found assumption for the wrong function!"); + WorkSet.push_back(I); } - return false; + completeEphemeralValues(WorkSet, EphValues); } /// analyzeBasicBlock - Fill in the current structure with information gleaned /// from the specified block. void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB, - const DataLayout *TD) { + const TargetTransformInfo &TTI, + SmallPtrSetImpl &EphValues) { ++NumBlocks; unsigned NumInstsBeforeThisBB = NumInsts; for (BasicBlock::const_iterator II = BB->begin(), E = BB->end(); II != E; ++II) { - if (isInstructionFree(II, TD)) + // Skip ephemeral values. + if (EphValues.count(&*II)) continue; // Special handling for calls. @@ -144,12 +130,10 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB, // for that case. if (F == BB->getParent()) isRecursive = true; - } - - if (!callIsSmall(CS)) { - // Each argument to a call takes on average one instruction to set up. - NumInsts += CS.arg_size(); + if (TTI.isLoweredToCall(F)) + ++NumCalls; + } else { // We don't want inline asm to count as a call - that would prevent loop // unrolling. The argument setup cost is still real, though. if (!isa(CS.getCalledValue())) @@ -165,15 +149,18 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB, if (isa(II) || II->getType()->isVectorTy()) ++NumVectorInsts; + if (II->getType()->isTokenTy() && II->isUsedOutsideOfBlock(BB)) + notDuplicatable = true; + if (const CallInst *CI = dyn_cast(II)) - if (CI->hasFnAttr(Attribute::NoDuplicate)) + if (CI->cannotDuplicate()) notDuplicatable = true; if (const InvokeInst *InvI = dyn_cast(II)) - if (InvI->hasFnAttr(Attribute::NoDuplicate)) + if (InvI->cannotDuplicate()) notDuplicatable = true; - ++NumInsts; + NumInsts += TTI.getUserCost(&*II); } if (isa(BB->getTerminator())) @@ -195,18 +182,3 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB, // Remember NumInsts for this BB. NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB; } - -void CodeMetrics::analyzeFunction(Function *F, const DataLayout *TD) { - // If this function contains a call that "returns twice" (e.g., setjmp or - // _setjmp) and it isn't marked with "returns twice" itself, never inline it. - // This is a hack because we depend on the user marking their local variables - // as volatile if they are live across a setjmp call, and they probably - // won't do this in callers. - exposesReturnsTwice = F->callsFunctionThatReturnsTwice() && - !F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, - Attribute::ReturnsTwice); - - // Look at the size of the callee. - for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - analyzeBasicBlock(&*BB, TD); -}