[loop-deletion] Improve analysis on calls when deleting a loop.

[trentxintong]

Summary

[loop-deletion] Improve analysis on calls when deleting a loop.

[efriedma]

test/Transforms/LoopDeletion/no-sideeffect-call.ll

26

mayHaveSideEffects isn't returning the expected result on your testcase because this call isn't marked nounwind. (I suspect your patch isn't actually doing anything useful.)

[trentxintong]

test/Transforms/LoopDeletion/no-sideeffect-call.ll

26

I debugged this a bit, basically we return FMRB_DoesNotAccessMemory if the callsite has the ReadNone attribute and that makes AliasAnalysis::onlyReadsMemory(Bev) true.

581 / Returns the behavior when calling the given call site.
582 FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
-> 583 if (CS.doesNotAccessMemory())
584 Can't do better than this.
585 return FMRB_DoesNotAccessMemory;

I used to think readnone/readonly cant not unwind implicitly. But it seems it has been changed. Maybe the check here needs to be ReadNone/ReadOnly + Nounwind. With this that means the call can not write to LLVM visible memory nor LLVM invisible memory (Nounwind).

[trentxintong]

test/Transforms/LoopDeletion/no-sideeffect-call.ll

26

I think you are right. I think calling mayHaveSideEffects on the CallInst will check for callsite specific attributes as well as attributes on the function. I wonder what the comment "This could be made more aggressive by using aliasing information to identify readonly and readnone calls." is there then. Maybe its out-of-dated or there is something I am missing here.

[efriedma]

Well, you could in theory delete a loop which contains an argmemonly call if you can prove the modified memory isn't used outside the loop... but that doesn't come up in practice, as far as I know. Beyond that, I don't think you can do anything interesting with alias analysis.

[trentxintong]

In D30284#684849, @efriedma wrote:

Well, you could in theory delete a loop which contains an argmemonly call if you can prove the modified memory isn't used outside the loop... but that doesn't come up in practice, as far as I know. Beyond that, I don't think you can do anything interesting with alias analysis.

Yes, as you are deleting the loop as a whole. I think its OK to remove that comment then at this point, right ?

[efriedma]

Yes, please do.

lib/Transforms/Scalar/LoopDeletion.cpp

 #define DEBUG_TYPE "loop-delete"
 
 STATISTIC(NumDeleted, "Number of loops deleted");
 
 /// Determines if a loop is dead.
 ///
 /// This assumes that we've already checked for unique exit and exiting blocks,
 /// and that the code is in LCSSA form.
-static bool isLoopDead(Loop *L, ScalarEvolution &SE,
+static bool isLoopDead(Loop *L, ScalarEvolution &SE, AAResults &AA,
                        SmallVectorImpl<BasicBlock *> &ExitingBlocks,
                        BasicBlock *ExitBlock, bool &Changed,
                        BasicBlock *Preheader) {
   // Make sure that all PHI entries coming from the loop are loop invariant.
   // Because the code is in LCSSA form, any values used outside of the loop
   // must pass through a PHI in the exit block, meaning that this check is
   // sufficient to guarantee that no loop-variant values are used outside
   // of the loop.
static bool isLoopDead(Loop *L, ScalarEvolution &SE, AAResults &AA,
   if (Changed)
     SE.forgetLoopDispositions(L);
 
   if (!AllEntriesInvariant || !AllOutgoingValuesSame)
     return false;
 
   // Make sure that no instructions in the block have potential side-effects.
   // This includes instructions that could write to memory, and loads that are
-  // marked volatile.  This could be made more aggressive by using aliasing
-  // information to identify readonly and readnone calls.
+  // marked volatile.
   for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
        LI != LE; ++LI) {
     for (Instruction &I : **LI) {
+      // Maybe we will have more luck looking at the callsite.
+      if (auto CS = CallSite(&I)) {
+        FunctionModRefBehavior Bev = AA.getModRefBehavior(CS);
+        // NOTE: this kind of instructions will likely to have been remove from
+        // the loop at this point, but since deleting a loop can result in
+        // significant performance gain, we should try to be aggressive.
+        // This covers calls that does not write to memory. i.e. calls 
+        // that only read memory or does not read memory.
+        if (AliasAnalysis::onlyReadsMemory(Bev))
+          continue;
+        else 
+          return false;
+      }
+
       if (I.mayHaveSideEffects())
         return false;
     }
   }
 
   return true;
 }
 

 ///
 /// \returns true if any changes were made. This may mutate the loop even if it
 /// is unable to delete it due to hoisting trivially loop invariant
 /// instructions out of the loop.
 ///
 /// This also updates the relevant analysis information in \p DT, \p SE, and \p
 /// LI. It also updates the loop PM if an updater struct is provided.
 static bool deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
-                             LoopInfo &LI, LPMUpdater *Updater = nullptr) {
+                             LoopInfo &LI, AAResults &AA,
+                             LPMUpdater *Updater = nullptr) {
   assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
 
   // We can only remove the loop if there is a preheader that we can
   // branch from after removing it.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader)
     return false;
 
static bool deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
   // block will be branched to, or trying to preserve the branching logic in
   // a loop invariant manner.
   BasicBlock *ExitBlock = L->getUniqueExitBlock();
   if (!ExitBlock)
     return false;
 
   // Finally, we have to check that the loop really is dead.
   bool Changed = false;
-  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader))
+  if (!isLoopDead(L, SE, AA, ExitingBlocks, ExitBlock, Changed, Preheader))
     return Changed;
 
   // Don't remove loops for which we can't solve the trip count.
   // They could be infinite, in which case we'd be changing program behavior.
   const SCEV *S = SE.getMaxBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(S))
     return Changed;
 
static bool deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
   ++NumDeleted;
 
   return true;
 }
 
 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
                                         LoopStandardAnalysisResults &AR,
                                         LPMUpdater &Updater) {
-  if (!deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, &Updater))
+  if (!deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.AA, &Updater))
     return PreservedAnalyses::all();
 
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 class LoopDeletionLegacyPass : public LoopPass {
 public:

 
 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &) {
   if (skipLoop(L))
     return false;
 
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 
-  return deleteLoopIfDead(L, DT, SE, LI);
+  return deleteLoopIfDead(L, DT, SE, LI, AA);
 }

test/Transforms/LoopDeletion/no-sideeffect-call.ll

+; RUN: opt -S -loop-deletion  < %s | FileCheck %s
+
+; Its possible for the optimizer to add readnone attribute when it knows
+; the input to the sqrtf is going to be greater than 0 and will not cause a
+; domain error (side effect). Make sure we look at the callsite and derive
+; its safe to delete and remove this loop.
+;
+; CHECK-LABEL: define void @loop_with_readnone_call(
+; CHECK-NOT: phi
+; CHECK-NOT: call float @sqrt
+; CHECK: ret
+define void @loop_with_readnone_call(i32 %n, float %x) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %cmp1 = fcmp ogt float %x, 0.000000e+00
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:
+  %call = call float @sqrtf(float %x) #0
+  br label %if.end
+
+if.end:
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}
+
+declare float @sqrtf(float)
+
+attributes #0 = { readnone }