[LoopDeletion] Emit a remark when a dead loop is deleted

[thegameg]

Summary

This emits a remark when LoopDeletion deletes a dead loop, using the source location of the loop's header. There are currently two reasons for removing the loop: invariant loop or loop that never executes.

[fhahn]

LGTM, thanks! I've added a few suggestions with respect to tests.

llvm/test/Transforms/LoopDeletion/basic-remark.ll

2

Does this need -mtriple? If so, the test would probably need ; REQUIRES: x86-registered-target or may fail on builds without the x86 target enabled.

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

1–2

I think it would probably be better to just add a second test function with a loop that never executes to basic-remark.ll and not check for remarks in this file. Without checking for the location/containing function of the remarks, it is hard to verify what the check lines check precisely.

[thegameg]

llvm/test/Transforms/LoopDeletion/basic-remark.ll

2

Nope, it doesn't, I removed it.

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

1–2

I agree. I decided to change the test to check the YAML output and use CHECK-LABEL to find the function name. Thanks for pointing this out, turns out 2 checks were in the wrong function :)

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopDeletion.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 

 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
 /// order to make various safety checks work.
 ///
 /// \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.
 static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
                                            ScalarEvolution &SE, LoopInfo &LI,
-                                           MemorySSA *MSSA) {
+                                           MemorySSA *MSSA,
+                                           OptimizationRemarkEmitter &ORE) {
   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. Also, if LoopSimplify form is not available, stay out
   // of trouble.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader || !L->hasDedicatedExits()) {
     LLVM_DEBUG(
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
 
   if (ExitBlock && isLoopNeverExecuted(L)) {
     LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
     // Set incoming value to undef for phi nodes in the exit block.
     for (PHINode &P : ExitBlock->phis()) {
       std::fill(P.incoming_values().begin(), P.incoming_values().end(),
                 UndefValue::get(P.getType()));
     }
+    ORE.emit([&]() {
+      return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
+                                L->getHeader())
+             << "Loop deleted because it never executes";
+    });
     deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
     ++NumDeleted;
     return LoopDeletionResult::Deleted;
   }
 
   // The remaining checks below are for a loop being dead because all statements
   // in the loop are invariant.
   SmallVector<BasicBlock *, 4> ExitingBlocks;
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
   const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(S)) {
     LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
+  ORE.emit([&]() {
+    return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
+                              L->getHeader())
+           << "Loop deleted because it is invariant";
+  });
   deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
   ++NumDeleted;
 
   return LoopDeletionResult::Deleted;
 }
 
 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
                                         LoopStandardAnalysisResults &AR,
                                         LPMUpdater &Updater) {
 
   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
   LLVM_DEBUG(L.dump());
   std::string LoopName = std::string(L.getName());
-  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA);
+  // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
+  // pass. Function analyses need to be preserved across loop transformations
+  // but ORE cannot be preserved (see comment before the pass definition).
+  OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
+  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
   if (Result == LoopDeletionResult::Unmodified)
     return PreservedAnalyses::all();
 
   if (Result == LoopDeletionResult::Deleted)
     Updater.markLoopAsDeleted(L, LoopName);
 
   auto PA = getLoopPassPreservedAnalyses();
   if (AR.MSSA)
if (skipLoop(L))
     return false;
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
   MemorySSA *MSSA = nullptr;
   if (MSSAAnalysis)
     MSSA = &MSSAAnalysis->getMSSA();
+  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
+  // pass.  Function analyses need to be preserved across loop transformations
+  // but ORE cannot be preserved (see comment before the pass definition).
+  OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
 
   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
   LLVM_DEBUG(L->dump());
 
-  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA);
+  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);
 
   if (Result == LoopDeletionResult::Deleted)
     LPM.markLoopAsDeleted(*L);
 
   return Result != LoopDeletionResult::Unmodified;
 }

llvm/test/Transforms/LoopDeletion/basic-remark.ll

+; RUN: opt -loop-deletion %s -o /dev/null --pass-remarks-output=%t --pass-remarks-filter=loop-delete
+; RUN: cat %t | FileCheck %s
+
+; Check that we use the right debug location: the loop header.
+; CHECK:      --- !Passed
+; CHECK-NEXT: Pass:            loop-delete
+; CHECK-NEXT: Name:            Invariant
+; CHECK-NEXT: DebugLoc:        { File: loop.c, Line: 2, Column: 3 }
+; CHECK-NEXT: Function:        main
+; CHECK-NEXT: Args:
+; CHECK-NEXT:   - String:          Loop deleted because it is invariant
+; CHECK-NEXT: ...
+define i32 @main() local_unnamed_addr #0 {
+entry:
+  br label %for.cond, !dbg !9
+
+for.cond:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.cond ]
+  %cmp = icmp ult i32 %i.0, 1000
+  %inc = add nuw nsw i32 %i.0, 1
+  br i1 %cmp, label %for.cond, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret i32 0
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "", isOptimized: true, runtimeVersion: 0, emissionKind: NoDebug, enums: !2, nameTableKind: None, sysroot: "/")
+!1 = !DIFile(filename: "loop.c", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = distinct !DISubprogram(name: "main", scope: !7, file: !7, line: 1, type: !8, scopeLine: 1, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!7 = !DIFile(filename: "loop.c", directory: "")
+!8 = !DISubroutineType(types: !2)
+!9 = !DILocation(line: 2, column: 3, scope: !6)

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

-; RUN: opt < %s -loop-deletion -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -loop-deletion -verify-dom-info --pass-remarks-output=%t --pass-remarks-filter=loop-delete -S | FileCheck %s
+; RUN: cat %t | FileCheck %s --check-prefix=REMARKS
 
 ; Checking that we can delete loops that are never executed.
 ; We do not change the constant conditional branch statement (where the not-taken target
 ; is the loop) to an unconditional one.
 
 ; delete the infinite loop because it is never executed.
 define void @test1(i64 %n, i64 %m) nounwind {
 ; CHECK-LABEL: test1
 ; CHECK-LABEL: entry:
 ; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
 ; CHECK-NOT: bb:
+; REMARKS-LABEL: Function: test1
+; REMARKS: Loop deleted because it never executes
 entry:
   br i1 true, label %return, label %bb
 
 bb:
   %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]
   %t0 = add i64 %x.0, 1
   %t1 = icmp slt i64 %x.0, %n
   %t3 = icmp sgt i64 %x.0, %m

 ; CHECK-NOT: bb2:
 ; CHECK-NOT: bb3:
 ; CHECK-LABEL: return.loopexit:
 ; CHECK-NEXT: %x.lcssa.ph = phi i64 [ undef, %bb.preheader ]
 ; CHECK-NEXT: br label %return
 ; CHECK-LABEL: return:
 ; CHECK-NEXT: %x.lcssa = phi i64 [ 20, %entry ], [ %x.lcssa.ph, %return.loopexit ]
 ; CHECK-NEXT: ret i64 %x.lcssa
+; REMARKS-LABEL: Function: test3
+; REMARKS: Loop deleted because it never executes
 entry:
   br i1 false, label %bb, label %return
 
 bb:
   %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb3 ]
   %t0 = add i64 %x.0, 1
   %t1 = icmp slt i64 %x.0, %n
   br i1 %t1, label %bb2, label %return

 ; multiple constant conditional branches with loop not-taken in all cases.
 define void @test5(i64 %n, i64 %m, i1 %cond) nounwind {
 ; CHECK-LABEL: test5
 ; CHECK-LABEL: looppred1:
 ; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
 ; CHECK-LABEL: looppred2:
 ; CHECK-NEXT: br i1 true, label %return, label %bb.preheader
 ; CHECK-NOT: bb:
+; REMARKS-LABEL: Function: test5
+; REMARKS: Loop deleted because it never executes
 entry:
   br i1 %cond, label %looppred1, label %looppred2
 
 looppred1:
   br i1 true, label %return, label %bb
 
 looppred2:
   br i1 true, label %return, label %bb

 ; CHECK: br i1 true, label %L1Latch, label %L2.preheader
 ; CHECK-LABEL: L2.preheader:
 ; CHECK-NEXT: br label %L1Latch.loopexit
 ; CHECK-LABEL: L1Latch.loopexit:
 ; CHECK: br label %L1Latch
 ; CHECK-LABEL: L1Latch:
 ; CHECK-NEXT: %y = phi i64 [ %y.next, %L1 ], [ %y.L2.lcssa, %L1Latch.loopexit ]
 ; CHECK: br i1 %cond2, label %exit, label %L1
+; REMARKS-LABEL: Function: test7
+; REMARKS: Loop deleted because it never executes
 entry: 
   br label %L1
 
 L1:
   %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]
   br i1 true, label %L1Latch, label %L2
 
 L2:

 ; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge
 ; from L2's preheader to L1's exit block is never taken. So, L1 gets deleted as well.
 define void @test8(i64 %n) {
 ; CHECK-LABEL: test8
 ; CHECK-LABEL: entry:
 ; CHECK-NEXT: br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT: ret void
+; REMARKS-LABEL: Function: test8
+; REMARKS: Loop deleted because it never executes
 entry: 
   br label %L1
 
 L1:
   br i1 true, label %exit, label %L2
 
 L2:
   %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]

 ; CHECK-LABEL: L2.preheader:
 ; CHECK-NEXT: br label %L3.preheader
 ; CHECK-NOT: L2:
 ; CHECK-LABEL: L3.preheader:
 ; CHECK-NEXT: %y.L2.lcssa = phi i64 [ undef, %L2.preheader ]
 ; CHECK-NEXT: br label %L3
 ; CHECK-LABEL: L3:
 ; CHECK: br i1 %cond2, label %L3, label %L1.loopexit
+; REMARKS-LABEL: Function: test9
+; REMARKS: Loop deleted because it never executes
 entry: 
   br label %L1
 
 L1:
   br i1 true, label %exit, label %L2
 
 L2:
   %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]

 ; In the next iteration, since L2 is never executed and has no subloops, we delete
 ; L2 as well. Finally, the outermost loop L1 is deleted.
 define void @test11(i64 %n) {
 ; CHECK-LABEL: test11
 ; CHECK-LABEL: entry:
 ; CHECK-NEXT: br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT: ret void
+; REMARKS-LABEL: Function: test11
+; REMARKS: Loop deleted because it is invariant
+; REMARKS-LABEL: Function: test11
+; REMARKS: Loop deleted because it never executes
+; REMARKS-LABEL: Function: test11
+; REMARKS: Loop deleted because it is invariant
 entry: 
   br label %L1
 
 L1:
   br i1 true, label %exit, label %L2
 
 L2:
   %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]

 ;CHECK-LABEL: @test12
 ; CHECK-NOT: L1:
 ; CHECK-NOT: L1Latch:
 ; CHECK-LABEL: L1.preheader:
 ; CHECK-NEXT:    br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT:    %y.phi = phi i64 [ undef, %L1.preheader ]
 ; CHECK-NEXT:    ret i64 %y.phi
+; REMARKS-LABEL: Function: test12
+; REMARKS: Loop deleted because it never executes
 
 entry:
   br i1 true, label %exit1, label %L1
 
 exit1:
   ret i64 42
 
 L1:                                               ; preds = %L1Latch, %entry

 ; CHECK-LABEL: @test13
 ; CHECK-NOT: L1:
 ; CHECK-NOT: L1Latch:
 ; CHECK-LABEL: L1.preheader:
 ; CHECK-NEXT:    br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT:    %y.phi = phi i64 [ undef, %L1.preheader ]
 ; CHECK-NEXT:    ret i64 %y.phi
+; REMARKS-LABEL: Function: test13
+; REMARKS: Loop deleted because it never executes
 
 entry:
   br i1 true, label %exit1, label %L1
 
 exit1:
   ret i64 42
 
 L1:                                               ; preds = %L1Latch, %entry