Add an analysis printer for must execute reasoning

[reames]

Summary

Many of our loop passes make use of so called "must execute" or "guaranteed to execute" facts to prove the legality of code motion. The basic notion is that we know (by assumption) an instruction didn't fault at it's original location, so if the location we move it to is strictly post dominated by the original, then we can't have introduced a new fault.

At the moment, the testing for this logic is somewhat adhoc and done mostly through LICM. Since I'm working on that code, I want to improve the testing. This patch is the first step in that direction. It doesn't actually test the variant used by the loop passes - I need to move that to the Analysis library first - but instead exercises an alternate implementation used by SCEV. (I plan on merging both implementations.)

[anna]

Just to note, other printer passes like print-memoryssa, print-lvi, print-predicate-info, we print the annotations as comments just above the IR (using the asm printer interface). It's easier to see which instruction we are referring to and quickly spot the loops they were part of , *if loops are properly annotated in the IR*. It would be useful when debugging large code base IR and spotting the missing cases.
IMO, the missing cases may be hard to spot in this printer. One workaround is to print the number of loops where it's not guaranteed to execute. That can be a separate add on after landing this as well.

From a testing perspective of the utility, this version works well for me.

lib/Analysis/MustExecute.cpp

25 ↗

(On Diff #138576)

Any reason for 4? Given we are looking at all instructions within all loops that's guaranteed to execute, it can be a much larger number.

85 ↗

(On Diff #138576)

I think we can use printAsOperand so that nameless values are handled properly.

87 ↗

(On Diff #138576)

Perhaps rename this to exactlyOneLoop and define that as MustExec[V]->size() == 1

test/Analysis/MustExecute/loop-header.ll

4 ↗

(On Diff #138576)

From a usability perspective in large IR where multiple transforms already done, we will have print statements like this:

; %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]  (mustexec in loop.split.unroll.split.split.crit_edge.... , another loop header name etc)

It seems difficult to read. If the usecase of the printer is to test existing code, it's fine.
However, printing this from large IR can make it pretty difficult to parse.
How about something like:

; %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]  (mustexec in 3 loops: <header names> of all 3 loops)

This number 3 can be retrieved from MustExec[V]->size()

[reames]

In D44524#1040018, @anna wrote:

Just to note, other printer passes like print-memoryssa, print-lvi, print-predicate-info, we print the annotations as comments just above the IR (using the asm printer interface). It's easier to see which instruction we are referring to and quickly spot the loops they were part of , *if loops are properly annotated in the IR*. It would be useful when debugging large code base IR and spotting the missing cases.
IMO, the missing cases may be hard to spot in this printer. One workaround is to print the number of loops where it's not guaranteed to execute. That can be a separate add on after landing this as well.

From a testing perspective of the utility, this version works well for me.

This is a good idea. I'd copied the basic structure of this from the mem deref printer, but I like the annotation version better. Mind if I submit this one (so that I can start getting some basic testing around this code), and then return to the annotation as a follow on? I'll change over mem-deref while I'm at it.

lib/Analysis/MustExecute.cpp

25 ↗

(On Diff #138576)

4 is simply the initial size and chosen fairly randomly. The SmallVector will resize if needed. Suggestions?

85 ↗

(On Diff #138576)

Good idea!

87 ↗

(On Diff #138576)

Er, what? I don't understand your comment. The "first" variable is simply being used to join a set of strings with a comma in between.

test/Analysis/MustExecute/loop-header.ll

4 ↗

(On Diff #138576)

Good idea. Will implement.

[anna]

lib/Analysis/MustExecute.cpp

87 ↗

(On Diff #138576)

What I meant is we can do something like this instead of using the first variable:

const bool exactlyOneLoop = MustExec[V]->size()  == 1;
for (const Loop *L : MustExec.lookup(V)) {
      OS << L->getHeader()->getName();
      if (!ExactlyOneLoop)
          OS << ", ";
}

[anna]

In D44524#1040307, @reames wrote:

In D44524#1040018, @anna wrote:

Just to note, other printer passes like print-memoryssa, print-lvi, print-predicate-info, we print the annotations as comments just above the IR (using the asm printer interface). It's easier to see which instruction we are referring to and quickly spot the loops they were part of , *if loops are properly annotated in the IR*. It would be useful when debugging large code base IR and spotting the missing cases.
IMO, the missing cases may be hard to spot in this printer. One workaround is to print the number of loops where it's not guaranteed to execute. That can be a separate add on after landing this as well.

From a testing perspective of the utility, this version works well for me.

This is a good idea. I'd copied the basic structure of this from the mem deref printer, but I like the annotation version better. Mind if I submit this one (so that I can start getting some basic testing around this code), and then return to the annotation as a follow on? I'll change over mem-deref while I'm at it.

SGTM.

lib/Analysis/MustExecute.cpp

25 ↗

(On Diff #138576)

Yes, it would resize. It's just that this feels we would definitely resize. I don't have another good suggestion though. We could do something like Ordering.reserve(F.size()), i.e. reserve the number of instructions in the function, but that's just wasted space...
And I don't think there's an easy way to get num instructions in all loops.
So, we can just stick with 4 I guess.

[reames]

lib/Analysis/MustExecute.cpp

87 ↗

(On Diff #138576)

Ah, I see where you're going. And actually you're pointing out a bug in the code. What I'd actually wanted was: "name, name, name". What I'd wrote produced "name name, name, " Your suggestion is a cleanup of the code as written, but doesn't work once I fix the formatting bug.

[anna]

lib/Analysis/MustExecute.cpp

87 ↗

(On Diff #138576)

I didn't notice the bug originally, but I think the cleanup should fix the bug :)
We should produce "name, name, name" because the boolean exactlyOneLoop is a constant and set outside the loop. We don't change it (unlike the first variable which was changed in the loop, and was the reason for the bug).

[anna]

lib/Analysis/MustExecute.cpp

87 ↗

(On Diff #138576)

nvm.. just took a look at it again. It fixes one part of the formatting: one comma after the first name. However, there's one extra comma after the last one.

[reames]

lib/Analysis/MustExecute.cpp

87 ↗

(On Diff #138576)

Nope, your variant produces: "name, name, ". (With the trailing ", ")

[reames]

Fix Anna's comments.

p.s. I realize the whole multiple loop printing code is effectively dead at the moment. The current analysis isn't smart enough to ever return true for the outer loops.

[anna]

lgtm!

include/llvm/Analysis/Passes.h

101 ↗

(On Diff #138776)

Stale comment here.

llvm/trunk/include/llvm/Analysis/Passes.h

namespace llvm {
 
   //===--------------------------------------------------------------------===//
   //
   // createMemDerefPrinter - This pass collects memory dereferenceability
   // information and prints it with -analyze.
   //
   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

llvm/trunk/include/llvm/InitializePasses.h

 void initializeMemorySSAWrapperPassPass(PassRegistry&);
 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeMergeICmpsPass(PassRegistry&);
 void initializeMergedLoadStoreMotionLegacyPassPass(PassRegistry&);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&);
+void initializeMustExecutePrinterPass(PassRegistry&);
 void initializeNameAnonGlobalLegacyPassPass(PassRegistry&);
 void initializeNaryReassociateLegacyPassPass(PassRegistry&);
 void initializeNewGVNLegacyPassPass(PassRegistry&);
 void initializeObjCARCAAWrapperPassPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createPartiallyInlineLibCallsPass();
       (void) llvm::createScalarizerPass();
       (void) llvm::createSeparateConstOffsetFromGEPPass();
       (void) llvm::createSpeculativeExecutionPass();
       (void) llvm::createSpeculativeExecutionIfHasBranchDivergencePass();
       (void) llvm::createRewriteSymbolsPass();
       (void) llvm::createStraightLineStrengthReducePass();
       (void) llvm::createMemDerefPrinter();
+      (void) llvm::createMustExecutePrinter();
       (void) llvm::createFloat2IntPass();
       (void) llvm::createEliminateAvailableExternallyPass();
       (void) llvm::createScalarizeMaskedMemIntrinPass();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::ScalarEvolutionWrapperPass();
       llvm::Function::Create(nullptr, llvm::GlobalValue::ExternalLinkage)->viewCFGOnly();
       llvm::RGPassManager RGM;

llvm/trunk/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeLazyValueInfoPrinterPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceWrapperPassPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeModuleSummaryIndexWrapperPassPass(Registry);
+  initializeMustExecutePrinterPass(Registry);
   initializeObjCARCAAWrapperPassPass(Registry);
   initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
   initializePostDominatorTreeWrapperPassPass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);

llvm/trunk/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp
   MemoryLocation.cpp
   MemorySSA.cpp
   MemorySSAUpdater.cpp
   ModuleDebugInfoPrinter.cpp
   ModuleSummaryAnalysis.cpp
+  MustExecute.cpp
   ObjCARCAliasAnalysis.cpp
   ObjCARCAnalysisUtils.cpp
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
   OrderedBasicBlock.cpp
   PHITransAddr.cpp
   PostDominators.cpp
   ProfileSummaryInfo.cpp

llvm/trunk/lib/Analysis/MustExecute.cpp

+//===- 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";
+}

llvm/trunk/test/Analysis/MustExecute/loop-header.ll

+; 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)