Index: include/llvm/Analysis/EphemeralValues.h =================================================================== --- /dev/null +++ include/llvm/Analysis/EphemeralValues.h @@ -0,0 +1,56 @@ +//===- EphemeralValues.h - Ephemeral value analysis -------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Calculate ephemeral values - those used only (indirectly) by invariants. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_EPHEMERAL_VALUES_H +#define LLVM_ANALYSIS_EPHEMERAL_VALUES_H + +#include "llvm/ADT/DenseSet.h" +#include "llvm/Pass.h" + +namespace llvm { + +class Value; +class raw_ostream; + +//===----------------------------------------------------------------------===// +/// @brief Analysis that finds ephemeral values. +class EphemeralValues : public ModulePass { + DenseSet EphValues; + + EphemeralValues(const EphemeralValues &) LLVM_DELETED_FUNCTION; + const EphemeralValues &operator=(const EphemeralValues &) LLVM_DELETED_FUNCTION; + +public: + // Returns true if the provided value is ephemeral. + bool isEphemeralValue(Value *V) const { + return EphValues.count(V); + } + bool isEphemeralValue(const Value *V) const { + return isEphemeralValue(const_cast(V)); + } + +public: + static char ID; + explicit EphemeralValues(); + + /// @name ModulePass interface + //@{ + virtual bool runOnModule(Module &M); + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void print(raw_ostream &OS, const Module *M) const; + //@} +}; + +} // End llvm namespace +#endif + Index: include/llvm/Analysis/InlineCost.h =================================================================== --- include/llvm/Analysis/InlineCost.h +++ include/llvm/Analysis/InlineCost.h @@ -27,6 +27,7 @@ class CallSite; class DataLayout; + class EphemeralValues; namespace InlineConstants { // Various magic constants used to adjust heuristics. @@ -106,11 +107,14 @@ class InlineCostAnalyzer { // DataLayout if available, or null. const DataLayout *TD; + // EphemeralValues if available, or null. + const EphemeralValues *EV; public: - InlineCostAnalyzer(): TD(0) {} + InlineCostAnalyzer(): TD(0), EV(0) {} void setDataLayout(const DataLayout *TData) { TD = TData; } + void setEphemeralValues(const EphemeralValues *EVals) { EV = EVals; } /// \brief Get an InlineCost object representing the cost of inlining this /// callsite. Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -66,6 +66,12 @@ //===--------------------------------------------------------------------===// // + // createEphemeralValuesPass - This pass identifies ephemeral values. + // + ModulePass *createEphemeralValuesPass(); + + //===--------------------------------------------------------------------===// + // /// createLibCallAliasAnalysisPass - Create an alias analysis pass that knows /// about the semantics of a set of libcalls specified by LCI. The newly /// constructed pass takes ownership of the pointer that is provided. Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -107,6 +107,7 @@ void initializeEdgeBundlesPass(PassRegistry&); void initializeEdgeProfilerPass(PassRegistry&); void initializeExpandPostRAPass(PassRegistry&); +void initializeEphemeralValuesPass(PassRegistry&); void initializePathProfilerPass(PassRegistry&); void initializeGCOVProfilerPass(PassRegistry&); void initializeAddressSanitizerPass(PassRegistry&); Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -42,6 +42,7 @@ initializePostDomPrinterPass(Registry); initializePostDomOnlyViewerPass(Registry); initializePostDomOnlyPrinterPass(Registry); + initializeEphemeralValuesPass(Registry); initializeIVUsersPass(Registry); initializeInstCountPass(Registry); initializeIntervalPartitionPass(Registry); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -17,6 +17,7 @@ DependenceAnalysis.cpp DomPrinter.cpp DominanceFrontier.cpp + EphemeralValues.cpp IVUsers.cpp InlineCost.cpp InstCount.cpp Index: lib/Analysis/EphemeralValues.cpp =================================================================== --- /dev/null +++ lib/Analysis/EphemeralValues.cpp @@ -0,0 +1,114 @@ +//===------------------------ EphemeralValues.cpp ------------------------===// +// Code to perform Alignment Invariant Propagation +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements ephemeral value determination. +// +//===----------------------------------------------------------------------===// + +#define EV_NAME "eph-values" +#define DEBUG_TYPE EV_NAME +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/Analysis/EphemeralValues.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Constant.h" +#include "llvm/DataLayout.h" +#include "llvm/Instruction.h" +#include "llvm/IntrinsicInst.h" +#include "llvm/Intrinsics.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/InstIterator.h" +#include "llvm/Support/raw_ostream.h" +using namespace llvm; + +char EphemeralValues::ID = 0; +static const char ev_name[] = "Ephemeral value analysis"; +INITIALIZE_PASS_BEGIN(EphemeralValues, EV_NAME, + ev_name, false, false) +INITIALIZE_PASS_END(EphemeralValues, EV_NAME, + ev_name, false, false) + +ModulePass *llvm::createEphemeralValuesPass() { + return new EphemeralValues(); +} + +EphemeralValues::EphemeralValues() : ModulePass(ID) { + initializeEphemeralValuesPass(*PassRegistry::getPassRegistry()); +} + +void EphemeralValues::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} + +void EphemeralValues::print(raw_ostream &OS, const Module *M) const { + if (!M) + return; + + OS << "Ephemeral values...\n"; + for (Module::const_iterator L = M->begin(), LE = M->end(); L != LE; ++L) + for (Function::const_iterator I = L->begin(), IE = L->end(); I != IE; ++I) + for (BasicBlock::const_iterator J = I->getFirstInsertionPt(), + JE = I->end(); J != JE; ++J) + if (isEphemeralValue(J)) { + OS << "\tephemeral: " << L->getName() << ": " << I->getName() << + ": " << *J << "\n"; + } +} + +bool EphemeralValues::runOnModule(Module &M) { + DenseSet Visited; + SmallVector WorkSet; + + EphValues.clear(); + + for (Module::iterator L = M.begin(), LE = M.end(); L != LE; ++L) + for (Function::iterator I = L->begin(), IE = L->end(); I != IE; ++I) + for (BasicBlock::iterator J = I->getFirstInsertionPt(), JE = I->end(); + J != JE; ++J) + if (CallInst *CI = dyn_cast(J)) + if (Function *F2 = CI->getCalledFunction()) + if (F2->getIntrinsicID() == Intrinsic::invariant) { + WorkSet.push_back(CI); + EphValues.insert(CI); + } + + while (!WorkSet.empty()) { + Value *V = WorkSet.pop_back_val(); + if (!Visited.insert(V).second) + continue; + + // If all uses of this value are ephemeral, then so is this value. + bool FoundNEUse = false; + for (Value::use_iterator I = V->use_begin(), IE = V->use_end(); + I != IE; ++I) + if (!EphValues.count(*I)) { + FoundNEUse = true; + break; + } + + if (!FoundNEUse) { + EphValues.insert(V); + + if (User *U = dyn_cast(V)) + for (User::op_iterator J = U->op_begin(), JE = U->op_end(); + J != JE; ++J) + WorkSet.push_back(*J); + } + } + + return false; +} + Index: lib/Analysis/InlineCost.cpp =================================================================== --- lib/Analysis/InlineCost.cpp +++ lib/Analysis/InlineCost.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "inline-cost" +#include "llvm/Analysis/EphemeralValues.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" @@ -43,6 +44,8 @@ // DataLayout if available, or null. const DataLayout *const TD; + // EphemeralValues if available, or null. + const EphemeralValues *const EV; // The called function. Function &F; @@ -125,8 +128,9 @@ bool visitCallSite(CallSite CS); public: - CallAnalyzer(const DataLayout *TD, Function &Callee, int Threshold) - : TD(TD), F(Callee), Threshold(Threshold), Cost(0), + CallAnalyzer(const DataLayout *TD, const EphemeralValues *EV, + Function &Callee, int Threshold) + : TD(TD), EV(EV), F(Callee), Threshold(Threshold), Cost(0), IsCallerRecursive(false), IsRecursiveCall(false), ExposesReturnsTwice(false), HasDynamicAlloca(false), AllocatedSize(0), NumInstructions(0), NumVectorInstructions(0), @@ -670,7 +674,7 @@ // during devirtualization and so we want to give it a hefty bonus for // inlining, but cap that bonus in the event that inlining wouldn't pan // out. Pretend to inline the function, with a custom threshold. - CallAnalyzer CA(TD, *F, InlineConstants::IndirectCallThreshold); + CallAnalyzer CA(TD, EV, *F, InlineConstants::IndirectCallThreshold); if (CA.analyzeCall(CS)) { // We were able to inline the indirect call! Subtract the cost from the // bonus we want to apply, but don't go below zero. @@ -714,7 +718,7 @@ // all of the per-instruction logic. The visit tree returns true if we // consumed the instruction in any way, and false if the instruction's base // cost should count against inlining. - if (Base::visit(I)) + if ((EV && EV->isEphemeralValue(I)) || Base::visit(I)) ++NumInstructionsSimplified; else Cost += InlineConstants::InstrCost; @@ -1058,7 +1062,7 @@ DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName() << "...\n"); - CallAnalyzer CA(TD, *Callee, Threshold); + CallAnalyzer CA(TD, EV, *Callee, Threshold); bool ShouldInline = CA.analyzeCall(CS); DEBUG(CA.dump()); Index: lib/Transforms/IPO/InlineSimple.cpp =================================================================== --- lib/Transforms/IPO/InlineSimple.cpp +++ lib/Transforms/IPO/InlineSimple.cpp @@ -14,6 +14,7 @@ #define DEBUG_TYPE "inline" #include "llvm/Transforms/IPO.h" #include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/EphemeralValues.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/CallingConv.h" #include "llvm/DataLayout.h" @@ -42,6 +43,10 @@ InlineCost getInlineCost(CallSite CS) { return CA.getInlineCost(CS, getInlineThreshold(CS)); } + virtual void getAnalysisUsage(AnalysisUsage &Info) const { + Info.addRequired(); + Inliner::getAnalysisUsage(Info); + } using llvm::Pass::doInitialization; virtual bool doInitialization(CallGraph &CG); }; @@ -51,6 +56,7 @@ INITIALIZE_PASS_BEGIN(SimpleInliner, "inline", "Function Integration/Inlining", false, false) INITIALIZE_AG_DEPENDENCY(CallGraph) +INITIALIZE_PASS_DEPENDENCY(EphemeralValues) INITIALIZE_PASS_END(SimpleInliner, "inline", "Function Integration/Inlining", false, false) @@ -64,6 +70,12 @@ // annotated with the noinline attribute. bool SimpleInliner::doInitialization(CallGraph &CG) { CA.setDataLayout(getAnalysisIfAvailable()); + + // FIXME: We need to use getAnalysisIfAvailable instead of getAnalysis + // because, even though the pass was been required, it will not have been + // run. getAnalysisIfAvailable will run the pass now, while getAnalysis + // will not (and will assert instead). + CA.setEphemeralValues(getAnalysisIfAvailable()); return false; } Index: test/Analysis/EphemeralValues/lit.local.cfg =================================================================== --- /dev/null +++ test/Analysis/EphemeralValues/lit.local.cfg @@ -0,0 +1 @@ +config.suffixes = ['.ll', '.c', '.cpp'] Index: test/Analysis/EphemeralValues/simple.ll =================================================================== --- /dev/null +++ test/Analysis/EphemeralValues/simple.ll @@ -0,0 +1,98 @@ +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +; RUN: opt < %s -analyze -eph-values | FileCheck %s + +define i32 @foo(i32* nocapture %a) nounwind uwtable readonly { +entry: + %ptrint = ptrtoint i32* %a to i64 + %maskedptr = and i64 %ptrint, 31 + %maskcond = icmp eq i64 %maskedptr, 0 + tail call void @llvm.invariant(i1 %maskcond) + %0 = load i32* %a, align 4, !tbaa !0 + ret i32 %0 + +; CHECK: ephemeral: foo: entry: %ptrint = ptrtoint i32* %a to i64 +; CHECK: ephemeral: foo: entry: %maskedptr = and i64 %ptrint, 31 +; CHECK: ephemeral: foo: entry: %maskcond = icmp eq i64 %maskedptr, 0 +; CHECK: ephemeral: foo: entry: tail call void @llvm.invariant(i1 %maskcond) +} + +define i32 @foo2(i32* nocapture %a) nounwind uwtable readonly { +entry: + %ptrint = ptrtoint i32* %a to i64 + %offsetptr = add i64 %ptrint, 24 + %maskedptr = and i64 %offsetptr, 31 + %maskcond = icmp eq i64 %maskedptr, 0 + tail call void @llvm.invariant(i1 %maskcond) + %arrayidx = getelementptr inbounds i32* %a, i64 2 + %0 = load i32* %arrayidx, align 4, !tbaa !0 + ret i32 %0 + +; CHECK: ephemeral: foo2: entry: %ptrint = ptrtoint i32* %a to i64 +; CHECK: ephemeral: foo2: entry: %offsetptr = add i64 %ptrint, 24 +; CHECK: ephemeral: foo2: entry: %maskedptr = and i64 %offsetptr, 31 +; CHECK: ephemeral: foo2: entry: %maskcond = icmp eq i64 %maskedptr, 0 +; CHECK: ephemeral: foo2: entry: tail call void @llvm.invariant(i1 %maskcond) +} + +define i32 @hoo(i32* nocapture %a) nounwind uwtable readonly { +entry: + %ptrint = ptrtoint i32* %a to i64 + %maskedptr = and i64 %ptrint, 31 + %maskcond = icmp eq i64 %maskedptr, 0 + br label %for.body + +for.body: ; preds = %entry, %for.body + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %r.06 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %arrayidx = getelementptr inbounds i32* %a, i64 %indvars.iv + %0 = load i32* %arrayidx, align 4, !tbaa !0 + %add = add nsw i32 %0, %r.06 + %indvars.iv.next = add i64 %indvars.iv, 8 + %1 = trunc i64 %indvars.iv.next to i32 + %cmp = icmp slt i32 %1, 2048 + br i1 %cmp, label %for.body, label %for.end + +for.end: ; preds = %for.body + %add.lcssa = phi i32 [ %add, %for.body ] + tail call void @llvm.invariant(i1 %maskcond) + ret i32 %add.lcssa + +; CHECK: ephemeral: hoo: entry: %ptrint = ptrtoint i32* %a to i64 +; CHECK: ephemeral: hoo: entry: %maskedptr = and i64 %ptrint, 31 +; CHECK: ephemeral: hoo: entry: %maskcond = icmp eq i64 %maskedptr, 0 +; CHECK: ephemeral: hoo: for.end: tail call void @llvm.invariant(i1 %maskcond) +} + +define i32 @moo2(i32* nocapture %a, i32* nocapture %b) nounwind uwtable { +entry: + %ptrint = ptrtoint i32* %a to i64 + %maskedptr = and i64 %ptrint, 31 + %maskcond = icmp eq i64 %maskedptr, 0 + tail call void @llvm.invariant(i1 %maskcond) + %ptrint1 = ptrtoint i32* %b to i64 + %maskedptr3 = and i64 %ptrint1, 127 + %maskcond4 = icmp eq i64 %maskedptr3, 0 + tail call void @llvm.invariant(i1 %maskcond4) + %0 = bitcast i32* %a to i8* + %1 = bitcast i32* %b to i8* + tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 64, i32 4, i1 false) + ret i32 undef + +; CHECK: ephemeral: moo2: entry: %ptrint = ptrtoint i32* %a to i64 +; CHECK: ephemeral: moo2: entry: %maskedptr = and i64 %ptrint, 31 +; CHECK: ephemeral: moo2: entry: %maskcond = icmp eq i64 %maskedptr, 0 +; CHECK: ephemeral: moo2: entry: tail call void @llvm.invariant(i1 %maskcond) +; CHECK: ephemeral: moo2: entry: %ptrint1 = ptrtoint i32* %b to i64 +; CHECK: ephemeral: moo2: entry: %maskedptr3 = and i64 %ptrint1, 127 +; CHECK: ephemeral: moo2: entry: %maskcond4 = icmp eq i64 %maskedptr3, 0 +; CHECK: ephemeral: moo2: entry: tail call void @llvm.invariant(i1 %maskcond4) +} + +declare void @llvm.invariant(i1) nounwind readnone + +declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind + +!0 = metadata !{metadata !"int", metadata !1} +!1 = metadata !{metadata !"omnipotent char", metadata !2} +!2 = metadata !{metadata !"Simple C/C++ TBAA"} + Index: test/Transforms/Inline/ephemeral.ll =================================================================== --- /dev/null +++ test/Transforms/Inline/ephemeral.ll @@ -0,0 +1,29 @@ +; RUN: opt -S -Oz %s | FileCheck %s + +@a = global i32 4 + +define i1 @inner() { + %a1 = load volatile i32* @a + %x1 = add i32 %a1, %a1 + %c = icmp eq i32 %x1, 0 + + %a2 = mul i32 %a1, %a1 + %a3 = sub i32 %a1, 5 + %a4 = udiv i32 %a3, -13 + %a5 = mul i32 %a4, %a4 + %a6 = add i32 %a5, %x1 + %ca = icmp sgt i32 %a6, -7 + tail call void @llvm.invariant(i1 %ca) + + ret i1 %c +} + +; @inner() should be inlined for -Oz. +; CHECK-NOT: call i1 @inner +define i1 @outer() optsize { + %r = call i1 @inner() + ret i1 %r +} + +declare void @llvm.invariant(i1) nounwind readnone +