[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

79

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.

80–81

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

82

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.

88

Should be const functions.

89

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;

108

Why drop the const?

lib/Transforms/Scalar/LICM.cpp

97 ↗

(On Diff #159644)

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

[fedor.sergeev]

include/llvm/Analysis/MustExecute.h

80–81

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

88

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

79

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.

88

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

108

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 ↗

(On Diff #159644)

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

79

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

80–81

It's already in cpp file.

89

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

89

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

88

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

 /// control flow has changed, or in case of other meaningful modifications, the
 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
 /// loop were made and the info wasn't recomputed properly, the behavior of all
 /// methods except for computeLoopSafetyInfo is undefined.
 class LoopSafetyInfo {
   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 for which this info is calculated.
+  Loop *CurLoop = nullptr;
 
 public:
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
   /// Returns true iff the header block of the loop for which this info is
   /// calculated contains an instruction that may throw or otherwise exit
   /// abnormally.
   bool headerMayThrow() const;
 
   /// Returns true iff any block of the loop for which this info is contains an
   /// instruction that may throw or otherwise exit abnormally.
   bool anyBlockMayThrow() const;
 
   /// 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(Loop *);
 
   LoopSafetyInfo() = default;
+
+  LoopSafetyInfo(Loop *L) {
+    computeLoopSafetyInfo(L);
+  }
 };
 
 /// 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);
 
 }
 
 #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;
 
 bool LoopSafetyInfo::headerMayThrow() const {
+  assert(CurLoop && "Should calculate the info first!");
   return HeaderMayThrow;
 }
 
 bool LoopSafetyInfo::anyBlockMayThrow() const {
+  assert(CurLoop && "Should calculate the info first!");
   return MayThrow;
 }
 
-void LoopSafetyInfo::computeLoopSafetyInfo(Loop *CurLoop) {
+void LoopSafetyInfo::computeLoopSafetyInfo(Loop *L) {
+  CurLoop = L;
   assert(CurLoop != nullptr && "CurLoop can't be null");
   BasicBlock *Header = CurLoop->getHeader();
   // Iterate over header and compute safety info.
   HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
   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.
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) {
   // 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())

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;
-  SafetyInfo.computeLoopSafetyInfo(CurLoop);
+  LoopSafetyInfo SafetyInfo(CurLoop);
   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/Utils/LoopUnrollAndJam.cpp

bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
   // outer loop
   if (!hasInvariantIterationCount(SubLoop, 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;
-  LSI.computeLoopSafetyInfo(L);
+  LoopSafetyInfo LSI(L);
   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.