[NFC][MustExecute] Rework API to start making better analysis, part 2

[mkazantsev]

Summary

We plan to make MustExecute analysis smarter in D50377, in particular
we want to be able to answer "is this Must Execute if the loop is entered?"
less conservatively for every loop block or instruction.

This patch reworks API just to make the functional change compact and
easier to review.

[reames]

include/llvm/Analysis/MustExecute.h

44

Drop the DT from this patch. That wasn't the API change with the risky implications.

Also, shouldn't L always be non-null? If so, assert or use reference.

Reading down in the patch, I see that L can be null. You'd be better with two constructors here. One which explicitly created an uninitialized object and the other which always created an initialized one.

53

Should be const functions.

57

Move the previous comment from computeLoopSafeyInfo to here with appropriate editing.

59

It's idiomatic to put private variables at the top of the class def, not the bottom. In this particular case, it'll reduce the textual diff as well.

66

Not sure it's safe to keep a raw reference here. The loop pass manager can delete loops in some cases. I'd suggest splitting this out into it's own patch for ease of review and revert.

lib/Analysis/MustExecute.cpp

29

Bad API. A better adapter implementation:
if (getHeader() == BB)

return HeaderMayThrow;

else
return MayThrow;

120

Why drop the const?

lib/Transforms/Scalar/LICM.cpp

97

If you need to drop const everywhere, you need to revisit your API. (clue: you don't)

[fedor.sergeev]

include/llvm/Analysis/MustExecute.h

57

Just 'reset' seems to be somewhat misleading.
I would still prefer to see this function having 'compute' in its name, since it does nontrivial amount of work.
Besides everything else it does a call to colorEHFunclets which has a comment - "Consider this analysis to be expensive".

lib/Analysis/MustExecute.cpp

33

typo: any block in the current loop

[fedor.sergeev]

include/llvm/Analysis/MustExecute.h

53

This most definitely is a "preparation" for D50377, where LoopSafetyInfo gets more state and mayThrow becomes non-const.

Said that, I do question the need for doing a separate API change that goes w/o a semantical context that necessitates the change.

[mkazantsev]

include/llvm/Analysis/MustExecute.h

44

If we check it on non-null, it fails some unit tests. I can add add this assertion only with unit tests modification in a separate patch.

53

I agree with Fedor, I would rather not do all these methods const because in the follow-up they all become non-const because of caching added.

lib/Analysis/MustExecute.cpp

120

Because in the follow-up patch for which this API change was made https://reviews.llvm.org/D50377, caching is added and this becomes non-const. I can leave const here, but then it will be dropped in this patch. The entire idea of making API change separately is to avoid modifying a lot of files with changes like that.

Please do not consider this patch as being something self-valuable, it will only be merged with follow-up. That is why all constant modifiers changes are made here. It's for convenience of the reviewers of functional change, not because it is something needed in NFC.

lib/Transforms/Scalar/LICM.cpp

97

Adding caching logic always leads to drop of const modifiers. We can leave it const and super-slow though. :)

[mkazantsev]

include/llvm/Analysis/MustExecute.h

44

As for motivation for this, DT is here not because otherwise it would have any risky implications, but because all files where we create LoopSafetyInfo need update because we are going to use it in the future. If we can make a mass update in the main patch, there is no point in this NFC at all.

[mkazantsev]

include/llvm/Analysis/MustExecute.h

57

It's already in cpp file.

66

Whoever removes a loop should stop using its safety info, otherwise it makes no sense. Currently, most use-cases of this is just create + call throws check with in place, except for loop unswitching which makes reset for every use. So I see no reason why it would be mo dangerous than keeping track of loop blocks in ICF or SCEV.

I also doubt that it would be easily revertable: the patch on top of that touches methods for which it will change signatures.

lib/Analysis/MustExecute.cpp

29

What you suggested contradicts the method's specification. It is not supposed to give false-positive answers.

[mkazantsev]

Addressed some of the comments, to others I have conter-arguments to not follow this way.

[fedor.sergeev]

include/llvm/Analysis/MustExecute.h

66

Whoever removes a loop should stop using its safety info

Alternative would be to always take Loop as a parameter to all query functions (similar to how it is passed to isGuaranteedToExecute) and use CurLoop only for something like:

assert(CurLoop == Loop && "this is a wrong loop")

To me, ideal scheme for LoopSafetyInfo would be to make it part of Loop, effectively converting it into a transparent helper cache for queries to Loop like isGuaranteedToExecute rather than something that should be managed separately by users of those queries.

why it would be more dangerous than keeping track of loop blocks in ICF

To me ICF's manual handling of invalidateBlock is dangerous.
Caching might be the only way to get a sane compilation time, however trading compile-time for correctness is always a scary trade-off. See my rants in D50377.

except for loop unswitching which makes reset for every use

And I dont see anything in loop unswitching code that specifically requires this particular reset pattern.
We could make LoopSafetyInfo local to processCurrentLoop without any visible downsides and providing a benefit of updated SafetyInfo on a subsequent redoLoop.

[reames]

include/llvm/Analysis/MustExecute.h

53

These methods are semantically const. If the internal caching is needed for efficiency, the ICF info can be marked mutable.

lib/Analysis/MustExecute.cpp

25

Style: document methods only in header, not cpp.

29

Er, I disagree. "may" always allows a conservative answer.

A valid answer to the question "may X happen"? Is *always* yes.

(To avoid confusion: this is not normal english usage, it is specifically jargon used within the compiler field. "may" and "must" have very specific meaning. For examples, see may alias and must alias)

[mkazantsev]

This one seems too big. I will split it.

[mkazantsev]

lib/Analysis/MustExecute.cpp

29

I would agree if there was no context. But this method has a comment which clearly states what it returns.

[mkazantsev]

Storing the CurLoop is not as necessary as we thought it was. Abandoning per this is no longer needed.

include/llvm/Analysis/MustExecute.h

 
 namespace llvm {
 
 class Instruction;
 class DominatorTree;
 class Loop;
 
 /// Captures loop safety information.
-/// It keep information for loop & its header may throw exception or otherwise
+/// It keep information for loop blocks may throw exception or otherwise
 /// exit abnormaly on any iteration of the loop which might actually execute
 /// at runtime.  The primary way to consume this infromation is via
 /// isGuaranteedToExecute below, but some callers bailout or fallback to
 /// alternate reasoning if a loop contains any implicit control flow.
-struct LoopSafetyInfo {
-  bool MayThrow = false;       // The current loop contains an instruction which
-                               // may throw.
-  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
+class LoopSafetyInfo {
+public:
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
-  LoopSafetyInfo() = default;
-};
+  LoopSafetyInfo(Loop *L, DominatorTree *DT) {
+    // TODO: DT will later be used by ICF analysis that will come in a follow-up
+    // patch. So far we only need it to make signature changes properly.
+    if (DT)
+      (void)DT;
+    if (L)
+      reset(L);
+  }
+
+  bool mayThrow(const BasicBlock *BB);
 
-/// Computes safety information for a loop checks loop body & header for
-/// the possibility of may throw exception, it takes LoopSafetyInfo and loop as
-/// argument. Updates safety information in LoopSafetyInfo argument.
-/// Note: This is defined to clear and reinitialize an already initialized
-/// LoopSafetyInfo.  Some callers rely on this fact.
-void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
+  bool anyBlockMayThrow();
+
+  void reset(Loop *L);
+
+private:
+  bool MayThrow = false;       // The current loop contains an instruction which
+                               // may throw.
+  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
+  // The current loop this LoopSafetyInfo is working with. It should be set via
+  // constructor or via the method "reset" to a non-null value before any query
+  // is done to this LoopSafetyInfo.
+  Loop *CurLoop = nullptr;
+};
 
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once (under the assumption that the loop is entered).
 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
                            const Loop *CurLoop,
-                           const LoopSafetyInfo *SafetyInfo);
+                           LoopSafetyInfo *SafetyInfo);
 
 }
 
 #endif

lib/Analysis/MustExecute.cpp

 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
+/// Returns true if the block \p BB contains an instruction that may throw or
+/// otherwise exit abnormally.
+bool LoopSafetyInfo::mayThrow(const BasicBlock *BB) {
+  assert(CurLoop && "Should calculate the info first!");
+  assert(CurLoop->getHeader() == BB && "Currently we only support header!");
+  return HeaderMayThrow;
+}
+
+/// Returns true if any loop in the current loop contains an instruction that
+/// may throw or otherwise exit abnormally.
+bool LoopSafetyInfo::anyBlockMayThrow() {
+  assert(CurLoop && "Should calculate the info first!");
+  return MayThrow;
+}
+
 /// Computes loop safety information, checks loop body & header
 /// for the possibility of may throw exception.
 ///
-void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
+void LoopSafetyInfo::reset(Loop *CurLoop) {
   assert(CurLoop != nullptr && "CurLoop can't be null");
+  this->CurLoop = CurLoop;
   BasicBlock *Header = CurLoop->getHeader();
   // Setting default safety values.
-  SafetyInfo->MayThrow = false;
-  SafetyInfo->HeaderMayThrow = false;
+  MayThrow = false;
+  HeaderMayThrow = false;
   // Iterate over header and compute safety info.
-  SafetyInfo->HeaderMayThrow =
-    !isGuaranteedToTransferExecutionToSuccessor(Header);
+  HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
 
-  SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
+  MayThrow = HeaderMayThrow;
   // Iterate over loop instructions and compute safety info.
   // Skip header as it has been computed and stored in HeaderMayThrow.
   // The first block in loopinfo.Blocks is guaranteed to be the header.
   assert(Header == *CurLoop->getBlocks().begin() &&
          "First block must be header");
   for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
                             BBE = CurLoop->block_end();
-       (BB != BBE) && !SafetyInfo->MayThrow; ++BB)
-    SafetyInfo->MayThrow |=
-      !isGuaranteedToTransferExecutionToSuccessor(*BB);
+       (BB != BBE) && !MayThrow; ++BB)
+    MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
 
   // Compute funclet colors if we might sink/hoist in a function with a funclet
   // personality routine.
   Function *Fn = CurLoop->getHeader()->getParent();
   if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())
       if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
-        SafetyInfo->BlockColors = colorEHFunclets(*Fn);
+        BlockColors = colorEHFunclets(*Fn);
 }
 
 /// Return true if we can prove that the given ExitBlock is not reached on the
 /// first iteration of the given loop.  That is, the backedge of the loop must
 /// be executed before the ExitBlock is executed in any dynamic execution trace.
 static bool CanProveNotTakenFirstIteration(BasicBlock *ExitBlock,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop) {
static bool CanProveNotTakenFirstIteration(BasicBlock *ExitBlock,
   assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
   return SimpleCst->isAllOnesValue();
 }
 
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once.
 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
                                  const DominatorTree *DT, const Loop *CurLoop,
-                                 const LoopSafetyInfo *SafetyInfo) {
+                                 LoopSafetyInfo *SafetyInfo) {
   // We have to check to make sure that the instruction dominates all
   // of the exit blocks.  If it doesn't, then there is a path out of the loop
   // which does not execute this instruction, so we can't hoist it.
 
   // If the instruction is in the header block for the loop (which is very
   // common), it is always guaranteed to dominate the exit blocks.  Since this
   // is a common case, and can save some work, check it now.
   if (Inst.getParent() == CurLoop->getHeader())
     // If there's a throw in the header block, we can't guarantee we'll reach
     // Inst unless we can prove that Inst comes before the potential implicit
     // exit.  At the moment, we use a (cheap) hack for the common case where
     // the instruction of interest is the first one in the block.
-    return !SafetyInfo->HeaderMayThrow ||
+    return !SafetyInfo->mayThrow(CurLoop->getHeader()) ||
       Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
 
   // Somewhere in this loop there is an instruction which may throw and make us
   // exit the loop.
-  if (SafetyInfo->MayThrow)
+  if (SafetyInfo->anyBlockMayThrow())
     return false;
 
   // Note: There are two styles of reasoning intermixed below for
   // implementation efficiency reasons.  They are:
   // 1) If we can prove that the instruction dominates all exit blocks, then we
   // know the instruction must have executed on *some* iteration before we
   // exit.  We do not prove *which* iteration the instruction must execute on.
   // 2) If we can prove that the instruction dominates the latch and all exits

 FunctionPass *llvm::createMustExecutePrinter() {
   return new MustExecutePrinter();
 }
 
 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
   // TODO: merge these two routines.  For the moment, we display the best
   // result obtained by *either* implementation.  This is a bit unfair since no
   // caller actually gets the full power at the moment.
-  LoopSafetyInfo LSI;
-  computeLoopSafetyInfo(&LSI, L);
+  LoopSafetyInfo LSI(L, DT);
   return isGuaranteedToExecute(I, DT, L, &LSI) ||
     isGuaranteedToExecuteForEveryIteration(&I, L);
 }
 
 namespace {
 /// An assembly annotator class to print must execute information in
 /// comments.
 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {

lib/Transforms/Scalar/LICM.cpp

static cl::opt<uint32_t> MaxNumUsesTraversed(
     cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
                                   const LoopSafetyInfo *SafetyInfo,
                                   TargetTransformInfo *TTI, bool &FreeInLoop);
 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
-                  const LoopSafetyInfo *SafetyInfo,
+                  LoopSafetyInfo *SafetyInfo,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
                  OptimizationRemarkEmitter *ORE, bool FreeInLoop);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
-                                           const LoopSafetyInfo *SafetyInfo,
+                                           LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST);
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
                             const LoopInfo *LI,
bool LoopInvariantCodeMotion::runOnLoop(
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA);
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Compute loop safety information.
-  LoopSafetyInfo SafetyInfo;
-  computeLoopSafetyInfo(&SafetyInfo, L);
+  LoopSafetyInfo SafetyInfo(L, DT);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
#endif
   }
   return Changed;
 }
 
 /// When an instruction is found to only use loop invariant operands that
 /// is safe to hoist, this instruction is called to do the dirty work.
 ///
 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
-                  const LoopSafetyInfo *SafetyInfo,
+                  LoopSafetyInfo *SafetyInfo,
                   OptimizationRemarkEmitter *ORE) {
   auto *Preheader = CurLoop->getLoopPreheader();
   LLVM_DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
                     << "\n");
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
                                                          << ore::NV("Inst", &I);
   });

 }
 
 /// Only sink or hoist an instruction if it is not a trapping instruction,
 /// or if the instruction is known not to trap when moved to the preheader.
 /// or if it is a trapping instruction and is guaranteed to execute.
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
-                                           const LoopSafetyInfo *SafetyInfo,
+                                           LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI) {
   if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
     return true;
 
   bool GuaranteedToExecute =
       isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
 
bool llvm::promoteLoopAccessesToScalars(
   // Keep track of which types of access we see
   bool SawUnorderedAtomic = false;
   bool SawNotAtomic = false;
   AAMDNodes AATags;
 
   const DataLayout &MDL = Preheader->getModule()->getDataLayout();
 
   bool IsKnownThreadLocalObject = false;
-  if (SafetyInfo->MayThrow) {
+  if (SafetyInfo->anyBlockMayThrow()) {
     // If a loop can throw, we have to insert a store along each unwind edge.
     // That said, we can't actually make the unwind edge explicit. Therefore,
     // we have to prove that the store is dead along the unwind edge.  We do
     // this by proving that the caller can't have a reference to the object
     // after return and thus can't possibly load from the object.
     Value *Object = GetUnderlyingObject(SomePtr, MDL);
     if (!isKnownNonEscaping(Object, TLI))
       return false;

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

bool LoopIdiomRecognize::runOnCountableLoop() {
   LLVM_DEBUG(dbgs() << "loop-idiom Scanning: F["
                     << CurLoop->getHeader()->getParent()->getName()
                     << "] Loop %" << CurLoop->getHeader()->getName() << "\n");
 
   bool MadeChange = false;
 
   // The following transforms hoist stores/memsets into the loop pre-header.
   // Give up if the loop has instructions may throw.
-  LoopSafetyInfo SafetyInfo;
-  computeLoopSafetyInfo(&SafetyInfo, CurLoop);
-  if (SafetyInfo.MayThrow)
+  LoopSafetyInfo SafetyInfo(CurLoop, DT);
+  if (SafetyInfo.anyBlockMayThrow())
     return MadeChange;
 
   // Scan all the blocks in the loop that are not in subloops.
   for (auto *BB : CurLoop->getBlocks()) {
     // Ignore blocks in subloops.
     if (LI->getLoopFor(BB) != CurLoop)
       continue;
 

lib/Transforms/Scalar/LoopUnswitch.cpp

class LoopUnswitch : public LoopPass {
     std::vector<BasicBlock*> NewBlocks;
 
     bool hasBranchDivergence;
 
   public:
     static char ID; // Pass ID, replacement for typeid
 
     explicit LoopUnswitch(bool Os = false, bool hasBranchDivergence = false)
-        : LoopPass(ID), OptimizeForSize(Os),
+        : LoopPass(ID), OptimizeForSize(Os), SafetyInfo(nullptr, DT),
           hasBranchDivergence(hasBranchDivergence) {
         initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
     bool processCurrentLoop();
     bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
 
bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   LPM = &LPM_Ref;
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   currentLoop = L;
   Function *F = currentLoop->getHeader()->getParent();
 
   SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
   if (SanitizeMemory)
-    computeLoopSafetyInfo(&SafetyInfo, L);
+    SafetyInfo.reset(L);
 
   bool Changed = false;
   do {
     assert(currentLoop->isLCSSAForm(*DT));
     redoLoop = false;
     Changed |= processCurrentLoop();
   } while(redoLoop);
 

lib/Transforms/Utils/LoopUnrollAndJam.cpp

bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
   };
   if (!CheckInnerLoopIterationCountInvariant(SubLoop, L, SE)) {
     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "
                          "not consistent on each iteration\n");
     return false;
   }
 
   // Check the loop safety info for exceptions.
-  LoopSafetyInfo LSI;
-  computeLoopSafetyInfo(&LSI, L);
-  if (LSI.MayThrow) {
+  LoopSafetyInfo LSI(L, &DT);
+  if (LSI.anyBlockMayThrow()) {
     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n");
     return false;
   }
 
   // We've ruled out the easy stuff and now need to check that there are no
   // interdependencies which may prevent us from moving the:
   //  ForeBlocks before Subloop and AftBlocks.
   //  Subloop before AftBlocks.