[HardwareLoops] Optimisation remarks

[SjoerdMeijer]

Summary

This adds the initial plumbing to support optimisation remarks in
the IR hardware-loop pass.

I have left a TODO in a comment where we can improve the reporting,
but I will iterate on that once we have this initial support in.

[hiraditya]

Nice!

[hiraditya]

llvm/lib/CodeGen/HardwareLoops.cpp

83

if (I)

84

nit, ' '

254

Checking ForceHardwareLoops should be cheaper, so we can check that first.

[SjoerdMeijer]

Thanks for taking a look!
Comments addressed.

[shchenz]

llvm/lib/CodeGen/HardwareLoops.cpp

247

Maybe can add a report here, Parent hardware loop does not support containing a nested hardware loop?

251

And also here? Invalid loop for example the one which contains irreducible control flow?

[SjoerdMeijer]

Added two more remarks

[SjoerdMeijer]

Just wanted to check if we are happy with this as an initial commit?

[samparker]

I agree that it would be good to know why a loop isn't a candidate, but this looks like a good start to me!

[SjoerdMeijer]

Thanks for reviewing!

llvm/lib/CodeGen/HardwareLoops.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Pass.h"
 #include "llvm/PassRegistry.h"
 #include "llvm/PassSupport.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"

 
 static cl::opt<bool>
 ForceGuardLoopEntry(
   "force-hardware-loop-guard", cl::Hidden, cl::init(false),
   cl::desc("Force generation of loop guard intrinsic"));
 
 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
 
+#ifndef NDEBUG
+static void debugHWLoopFailure(const StringRef DebugMsg,
+    Instruction *I) {
+  dbgs() << "HWLoops: " << DebugMsg;
+  if (I != nullptr)
+    dbgs() << " " << *I;
+  else
+    dbgs() << '.';
+  dbgs() << '\n';
+}
+#endif
+
+static OptimizationRemarkAnalysis
+createHWLoopAnalysis(StringRef RemarkName, Loop *L, Instruction *I) {
+  Value *CodeRegion = L->getHeader();
+  DebugLoc DL = L->getStartLoc();
+
+  if (I) {
+    CodeRegion = I->getParent();
+    // If there is no debug location attached to the instruction, revert back to
+    // using the loop's.
+    if (I->getDebugLoc())
+      DL = I->getDebugLoc();
+  }
+
+  OptimizationRemarkAnalysis R(DEBUG_TYPE, RemarkName, DL, CodeRegion);
+  R << "hardware-loop not created: ";
+  return R;
+}
+
 namespace {
 
+  void reportHWLoopFailure(const StringRef Msg, const StringRef ORETag,
+      OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I = nullptr) {
+    LLVM_DEBUG(debugHWLoopFailure(Msg, I));
+    ORE->emit(createHWLoopAnalysis(ORETag, TheLoop, I) << Msg);
+  }
+
   using TTI = TargetTransformInfo;
 
   class HardwareLoops : public FunctionPass {
   public:
     static char ID;
 
     HardwareLoops() : FunctionPass(ID) {
       initializeHardwareLoopsPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addRequired<ScalarEvolutionWrapperPass>();
       AU.addRequired<AssumptionCacheTracker>();
       AU.addRequired<TargetTransformInfoWrapperPass>();
+      AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
     }
 
     // Try to convert the given Loop into a hardware loop.
     bool TryConvertLoop(Loop *L);
 
     // Given that the target believes the loop to be profitable, try to
     // convert it.
     bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
 
   private:
     ScalarEvolution *SE = nullptr;
     LoopInfo *LI = nullptr;
     const DataLayout *DL = nullptr;
+    OptimizationRemarkEmitter *ORE = nullptr;
     const TargetTransformInfo *TTI = nullptr;
     DominatorTree *DT = nullptr;
     bool PreserveLCSSA = false;
     AssumptionCache *AC = nullptr;
     TargetLibraryInfo *LibInfo = nullptr;
     Module *M = nullptr;
     bool MadeChange = false;
   };
class HardwareLoop {
     PHINode *InsertPHICounter(Value *NumElts, Value *EltsRem);
 
     // Create a new cmp, that checks the returned value of loop_decrement*,
     // and update the exit branch to use it.
     void UpdateBranch(Value *EltsRem);
 
   public:
     HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
-                 const DataLayout &DL) :
-      SE(SE), DL(DL), L(Info.L), M(L->getHeader()->getModule()),
+                 const DataLayout &DL,
+                 OptimizationRemarkEmitter *ORE) :
+      SE(SE), DL(DL), ORE(ORE), L(Info.L), M(L->getHeader()->getModule()),
       ExitCount(Info.ExitCount),
       CountType(Info.CountType),
       ExitBranch(Info.ExitBranch),
       LoopDecrement(Info.LoopDecrement),
       UsePHICounter(Info.CounterInReg),
       UseLoopGuard(Info.PerformEntryTest) { }
 
     void Create();
 
   private:
     ScalarEvolution &SE;
     const DataLayout &DL;
+    OptimizationRemarkEmitter *ORE = nullptr;
     Loop *L                 = nullptr;
     Module *M               = nullptr;
     const SCEV *ExitCount   = nullptr;
     Type *CountType         = nullptr;
     BranchInst *ExitBranch  = nullptr;
     Value *LoopDecrement    = nullptr;
     bool UsePHICounter      = false;
     bool UseLoopGuard       = false;
bool HardwareLoops::runOnFunction(Function &F) {
 
   LLVM_DEBUG(dbgs() << "HWLoops: Running on " << F.getName() << "\n");
 
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   DL = &F.getParent()->getDataLayout();
+  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   LibInfo = TLIP ? &TLIP->getTLI(F) : nullptr;
   PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   M = F.getParent();
 
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
     Loop *L = *I;
     if (!L->getParentLoop())
       TryConvertLoop(L);
   }
 
   return MadeChange;
 }
 
 // Return true if the search should stop, which will be when an inner loop is
 // converted and the parent loop doesn't support containing a hardware loop.
 bool HardwareLoops::TryConvertLoop(Loop *L) {
   // Process nested loops first.
   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
     if (TryConvertLoop(*I))
       return true; // Stop search.
 
   HardwareLoopInfo HWLoopInfo(L);
   if (!HWLoopInfo.canAnalyze(*LI))
     return false;
 
-  if (TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo) ||
-      ForceHardwareLoops) {
+  if (!TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo) &&
+      !ForceHardwareLoops) {
+    reportHWLoopFailure("it's not profitable to create a hardware-loop",
+                        "HWLoopNotProfitable", ORE, L);
+    return false;
+  }
 
-    // Allow overriding of the counter width and loop decrement value.
-    if (CounterBitWidth.getNumOccurrences())
-      HWLoopInfo.CountType =
-        IntegerType::get(M->getContext(), CounterBitWidth);
 
-    if (LoopDecrement.getNumOccurrences())
-      HWLoopInfo.LoopDecrement =
-        ConstantInt::get(HWLoopInfo.CountType, LoopDecrement);
 
-    MadeChange |= TryConvertLoop(HWLoopInfo);
-    return MadeChange && (!HWLoopInfo.IsNestingLegal && !ForceNestedLoop);
-  }
 
-  return false;
-}
-
 bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
 
   Loop *L = HWLoopInfo.L;
   LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
 
   if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop,
-                                          ForceHardwareLoopPHI))
+                                          ForceHardwareLoopPHI)) {
+    // TODO: there can be many reasons why a loop is not considered a
+    // candidate, so we should let isHardwareLoopCandidate fill in the
+    // reason, and report a better message here.
+    reportHWLoopFailure("loop is not a candidate", "HWLoopNoCandidate", ORE, L);
     return false;
+  }
 
   assert(
       (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
       "Hardware Loop must have set exit info.");
 
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // If we don't have a preheader, then insert one.
   if (!Preheader)
     Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
   if (!Preheader)
     return false;
 
-  HardwareLoop HWLoop(HWLoopInfo, *SE, *DL);
+  HardwareLoop HWLoop(HWLoopInfo, *SE, *DL, ORE);
   HWLoop.Create();
   ++NumHWLoops;
   return true;
 }
 
 void HardwareLoop::Create() {
   LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
- 
   Value *LoopCountInit = InitLoopCount();
-  if (!LoopCountInit)
+  if (!LoopCountInit) {
+    reportHWLoopFailure("could not safely create a loop count expression",
+                        "HWLoopNotSafe", ORE, L);
     return;
+  }
 
   InsertIterationSetup(LoopCountInit);
 
   if (UsePHICounter || ForceHardwareLoopPHI) {
     Instruction *LoopDec = InsertLoopRegDec(LoopCountInit);
     Value *EltsRem = InsertPHICounter(LoopCountInit, LoopDec);
     LoopDec->setOperand(0, EltsRem);
     UpdateBranch(LoopDec);

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; CHECK-NEXT:    Rewrite Symbols
 ; CHECK-NEXT:    FunctionPass Manager
 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Exception handling preparation
 ; CHECK-NEXT:      Merge internal globals
 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      Scalar Evolution Analysis
+; CHECK-NEXT:      Lazy Branch Probability Analysis
+; CHECK-NEXT:      Lazy Block Frequency Analysis
+; CHECK-NEXT:      Optimization Remark Emitter
 ; CHECK-NEXT:      Hardware Loop Insertion
 ; CHECK-NEXT:      Scalar Evolution Analysis
 ; CHECK-NEXT:      Loop Pass Manager
 ; CHECK-NEXT:        Transform predicated vector loops to use MVE tail predication
 ; CHECK-NEXT:      Safe Stack instrumentation pass
 ; CHECK-NEXT:      Insert stack protectors
 ; CHECK-NEXT:      Module Verifier
 ; CHECK-NEXT:      Dominator Tree Construction

llvm/test/Transforms/HardwareLoops/ARM/opt-remarks.ll

+; RUN: opt -mtriple=thumbv8.1m.main-arm-none-eabi -mattr=+mve -hardware-loops \
+; RUN:     -disable-arm-loloops=true -pass-remarks-analysis=hardware-loops \
+; RUN:     -S %s -o - 2>&1 | FileCheck %s
+
+; CHECK: remark: <unknown>:0:0: hardware-loop not created: it's not profitable to create a hardware-loop
+
+define void @while_lt(i32 %i, i32 %N, i32* nocapture %A) {
+entry:
+  %cmp4 = icmp ult i32 %i, %N
+  br i1 %cmp4, label %while.body, label %while.end
+
+while.body:
+  %i.addr.05 = phi i32 [ %inc, %while.body ], [ %i, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.addr.05
+  store i32 %i.addr.05, i32* %arrayidx, align 4
+  %inc = add nuw i32 %i.addr.05, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %while.end, label %while.body
+
+while.end:
+  ret void
+}
+
+

llvm/test/Transforms/HardwareLoops/unconditional-latch.ll

 ; RUN: opt -force-hardware-loops=true -hardware-loop-decrement=1 -hardware-loop-counter-bitwidth=32 -hardware-loops -S %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALLOW
 ; RUN: opt -force-hardware-loops=true -hardware-loop-decrement=1 -hardware-loop-counter-bitwidth=32 -hardware-loops -force-hardware-loop-guard=true -S %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALLOW
-; RUN: opt -force-hardware-loops=true -hardware-loop-decrement=1 -hardware-loop-counter-bitwidth=32 -force-hardware-loop-phi=true -hardware-loops -S %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-LATCH
+;
+; RUN: opt -force-hardware-loops=true -hardware-loop-decrement=1 \
+; RUN:     -hardware-loop-counter-bitwidth=32 -force-hardware-loop-phi=true \
+; RUN:     -hardware-loops -S -pass-remarks-analysis=hardware-loops %s -o - \
+; RUN:     2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-LATCH
+
+; CHECK-LATCH: remark: <unknown>:0:0: hardware-loop not created: loop is not a candidate
 
 ; CHECK-LABEL: not_rotated
 ; CHECK-LATCH-NOT: call void @llvm.set.loop.iterations
 ; CHECK-LATCH-NOT: call i1 @llvm.loop.decrement
 
 ; CHECK-ALLOW: bb:
 ; CHECK-ALLOW:   [[COUNT:%[^ ]+]] = add i32 %arg, 1
 ; CHECK-ALLOW:   br label %bb3