Index: llvm/trunk/include/llvm/Analysis/Passes.h =================================================================== --- llvm/trunk/include/llvm/Analysis/Passes.h +++ llvm/trunk/include/llvm/Analysis/Passes.h @@ -96,6 +96,14 @@ // 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 Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -268,6 +268,7 @@ void initializeMetaRenamerPass(PassRegistry&); void initializeModuleDebugInfoPrinterPass(PassRegistry&); void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&); +void initializeMustExecutePrinterPass(PassRegistry&); void initializeNameAnonGlobalLegacyPassPass(PassRegistry&); void initializeNaryReassociateLegacyPassPass(PassRegistry&); void initializeNewGVNLegacyPassPass(PassRegistry&); Index: llvm/trunk/include/llvm/LinkAllPasses.h =================================================================== --- llvm/trunk/include/llvm/LinkAllPasses.h +++ llvm/trunk/include/llvm/LinkAllPasses.h @@ -207,6 +207,7 @@ (void) llvm::createRewriteSymbolsPass(); (void) llvm::createStraightLineStrengthReducePass(); (void) llvm::createMemDerefPrinter(); + (void) llvm::createMustExecutePrinter(); (void) llvm::createFloat2IntPass(); (void) llvm::createEliminateAvailableExternallyPass(); (void) llvm::createScalarizeMaskedMemIntrinPass(); Index: llvm/trunk/lib/Analysis/Analysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/Analysis.cpp +++ llvm/trunk/lib/Analysis/Analysis.cpp @@ -65,6 +65,7 @@ initializeMemoryDependenceWrapperPassPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); initializeModuleSummaryIndexWrapperPassPass(Registry); + initializeMustExecutePrinterPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializeOptimizationRemarkEmitterWrapperPassPass(Registry); initializePostDominatorTreeWrapperPassPass(Registry); Index: llvm/trunk/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Analysis/CMakeLists.txt +++ llvm/trunk/lib/Analysis/CMakeLists.txt @@ -58,6 +58,7 @@ MemorySSAUpdater.cpp ModuleDebugInfoPrinter.cpp ModuleSummaryAnalysis.cpp + MustExecute.cpp ObjCARCAliasAnalysis.cpp ObjCARCAnalysisUtils.cpp ObjCARCInstKind.cpp Index: llvm/trunk/lib/Analysis/MustExecute.cpp =================================================================== --- llvm/trunk/lib/Analysis/MustExecute.cpp +++ llvm/trunk/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 > MustExec; + SmallVector 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(); + AU.addRequired(); + } + 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().getLoopInfo(); + auto &DT = getAnalysis().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"; +} Index: llvm/trunk/test/Analysis/MustExecute/loop-header.ll =================================================================== --- llvm/trunk/test/Analysis/MustExecute/loop-header.ll +++ llvm/trunk/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)