diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/Passes.h | 8 | ||||
| -rw-r--r-- | llvm/include/llvm/InitializePasses.h | 1 | ||||
| -rw-r--r-- | llvm/include/llvm/LinkAllPasses.h | 1 | ||||
| -rw-r--r-- | llvm/lib/Analysis/Analysis.cpp | 1 | ||||
| -rw-r--r-- | llvm/lib/Analysis/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | llvm/lib/Analysis/MustExecute.cpp | 102 | ||||
| -rw-r--r-- | llvm/test/Analysis/MustExecute/loop-header.ll | 80 |
7 files changed, 194 insertions, 0 deletions
diff --git a/llvm/include/llvm/Analysis/Passes.h b/llvm/include/llvm/Analysis/Passes.h index 6d8f14fa32f..09b28a0b088 100644 --- a/llvm/include/llvm/Analysis/Passes.h +++ b/llvm/include/llvm/Analysis/Passes.h @@ -96,6 +96,14 @@ namespace llvm { // FunctionPass *createMemDerefPrinter(); + //===--------------------------------------------------------------------===// + // + // createMustExecutePrinter - This pass collects information about which + // instructions within a loop are guaranteed to execute if the loop header is + // entered and prints it with -analyze. + // + FunctionPass *createMustExecutePrinter(); + } #endif diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index 10f66562f0c..3bcc39dcf48 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -268,6 +268,7 @@ void initializeMergedLoadStoreMotionLegacyPassPass(PassRegistry&); void initializeMetaRenamerPass(PassRegistry&); void initializeModuleDebugInfoPrinterPass(PassRegistry&); void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&); +void initializeMustExecutePrinterPass(PassRegistry&); void initializeNameAnonGlobalLegacyPassPass(PassRegistry&); void initializeNaryReassociateLegacyPassPass(PassRegistry&); void initializeNewGVNLegacyPassPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h index 39d1ec6cffb..a407d59850d 100644 --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -207,6 +207,7 @@ namespace { (void) llvm::createRewriteSymbolsPass(); (void) llvm::createStraightLineStrengthReducePass(); (void) llvm::createMemDerefPrinter(); + (void) llvm::createMustExecutePrinter(); (void) llvm::createFloat2IntPass(); (void) llvm::createEliminateAvailableExternallyPass(); (void) llvm::createScalarizeMaskedMemIntrinPass(); diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp index 0e0b5c92a91..401ce7a25a7 100644 --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -65,6 +65,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeMemoryDependenceWrapperPassPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); initializeModuleSummaryIndexWrapperPassPass(Registry); + initializeMustExecutePrinterPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializeOptimizationRemarkEmitterWrapperPassPass(Registry); initializePostDominatorTreeWrapperPassPass(Registry); diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index 86f51cc0dff..8b4bb36c6ae 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -58,6 +58,7 @@ add_llvm_library(LLVMAnalysis MemorySSAUpdater.cpp ModuleDebugInfoPrinter.cpp ModuleSummaryAnalysis.cpp + MustExecute.cpp ObjCARCAliasAnalysis.cpp ObjCARCAnalysisUtils.cpp ObjCARCInstKind.cpp diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp new file mode 100644 index 00000000000..3d98a61c0ed --- /dev/null +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -0,0 +1,102 @@ +//===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +using namespace llvm; + +namespace { + struct MustExecutePrinter : public FunctionPass { + DenseMap<Value*, SmallVector<Loop*, 4> > MustExec; + SmallVector<Value *, 4> Ordering; + + static char ID; // Pass identification, replacement for typeid + MustExecutePrinter() : FunctionPass(ID) { + initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry()); + } + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + AU.addRequired<DominatorTreeWrapperPass>(); + AU.addRequired<LoopInfoWrapperPass>(); + } + bool runOnFunction(Function &F) override; + void print(raw_ostream &OS, const Module * = nullptr) const override; + void releaseMemory() override { + MustExec.clear(); + Ordering.clear(); + } + }; +} + +char MustExecutePrinter::ID = 0; +INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", + "Instructions which execute on loop entry", false, true) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute", + "Instructions which execute on loop entry", false, true) + +FunctionPass *llvm::createMustExecutePrinter() { + return new MustExecutePrinter(); +} + +bool isMustExecuteIn(Instruction &I, Loop *L, DominatorTree *DT) { + // TODO: move loop specific code to analysis + //LoopSafetyInfo LSI; + //computeLoopSafetyInfo(&LSI, L); + //return isGuaranteedToExecute(I, DT, L, &LSI); + return isGuaranteedToExecuteForEveryIteration(&I, L); +} + +bool MustExecutePrinter::runOnFunction(Function &F) { + auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); + auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); + for (auto &I: instructions(F)) { + Loop *L = LI.getLoopFor(I.getParent()); + while (L) { + if (isMustExecuteIn(I, L, &DT)) { + if (!MustExec.count(&I)) + Ordering.push_back(&I); + MustExec[&I].push_back(L); + } + L = L->getParentLoop(); + }; + } + return false; +} + +void MustExecutePrinter::print(raw_ostream &OS, const Module *M) const { + OS << "The following are guaranteed to execute (for the respective loops):\n"; + for (Value *V: Ordering) { + V->printAsOperand(OS); + auto NumLoops = MustExec.lookup(V).size(); + if (NumLoops > 1) + OS << "\t(mustexec in " << NumLoops << " loops: "; + else + OS << "\t(mustexec in: "; + + bool first = true; + for (const Loop *L : MustExec.lookup(V)) { + if (!first) + OS << ", "; + first = false; + OS << L->getHeader()->getName(); + } + OS << ")\n"; + } + OS << "\n"; +} diff --git a/llvm/test/Analysis/MustExecute/loop-header.ll b/llvm/test/Analysis/MustExecute/loop-header.ll new file mode 100644 index 00000000000..a505e85efa8 --- /dev/null +++ b/llvm/test/Analysis/MustExecute/loop-header.ll @@ -0,0 +1,80 @@ +; RUN: opt -analyze -print-mustexecute %s + +; CHECK: Printing analysis 'Instructions which execute on loop entry' for function 'header_with_icf': +; CHECK: The following are guaranteed to execute (for the respective loops): +; CHECK: %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] (mustexec in: loop) +; CHECK: %v = load i32, i32* %p (mustexec in: loop) +; CHECK: call void @maythrow_and_use(i32 %v) (mustexec in: loop) +; CHECK-NOT: add +define i1 @header_with_icf(i32* noalias %p, i32 %high) { +entry: + br label %loop + +loop: + %iv = phi i32 [0, %entry], [%iv.next, %loop] + %v = load i32, i32* %p + call void @maythrow_and_use(i32 %v) + %iv.next = add nsw nuw i32 %iv, 1 + %exit.test = icmp slt i32 %iv, %high + br i1 %exit.test, label %exit, label %loop + +exit: + ret i1 false +} + +; CHECK: Printing analysis 'Instructions which execute on loop entry' for function 'test': +; CHECK: The following are guaranteed to execute (for the respective loops): +; CHECK: %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] (mustexec in: loop) +; CHECK: %v = load i32, i32* %p (mustexec in: loop) +; CHECK: br label %next (mustexec in: loop) +define i1 @test(i32* noalias %p, i32 %high) { +entry: + br label %loop + +loop: + %iv = phi i32 [0, %entry], [%iv.next, %next] + %v = load i32, i32* %p + br label %next +next: + call void @maythrow_and_use(i32 %v) + %iv.next = add nsw nuw i32 %iv, 1 + %exit.test = icmp slt i32 %iv, %high + br i1 %exit.test, label %exit, label %loop + +exit: + ret i1 false +} + +; CHECK: Printing analysis 'Instructions which execute on loop entry' for function 'nested': +; CHECK: The following are guaranteed to execute (for the respective loops): +; CHECK: %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] (mustexec in: loop) +; CHECK: br label %inner_loop (mustexec in: loop) +; FIXME: These three are also must execute for the outer loop. +; CHECK: %v = load i32, i32* %p (mustexec in: inner_loop) +; CHECK: %inner.test = icmp eq i32 %v, 0 (mustexec in: inner_loop) +; CHECK: br i1 %inner.test, label %inner_loop, label %next (mustexec in: inner_loop) +define i1 @nested(i32* noalias %p, i32 %high) { +entry: + br label %loop + +loop: + %iv = phi i32 [0, %entry], [%iv.next, %next] + br label %inner_loop + +inner_loop: + %v = load i32, i32* %p + %inner.test = icmp eq i32 %v, 0 + br i1 %inner.test, label %inner_loop, label %next + +next: + call void @maythrow_and_use(i32 %v) + %iv.next = add nsw nuw i32 %iv, 1 + %exit.test = icmp slt i32 %iv, %high + br i1 %exit.test, label %exit, label %loop + +exit: + ret i1 false +} + + +declare void @maythrow_and_use(i32) |
