Add heuristics for irreducible loop metadata under PGO

[hjyamauchi]

Summary

Add the following heuristics for irreducible loop metadata:

• When an irreducible loop header is missing the loop header weight metadata, give it the minimum weight seen among other headers.
• Annotate indirectbr targets with the loop header weight metadata (as they are likely to become irreducible loop headers after indirectbr tail duplication.)

These greatly improve the accuracy of the block frequency info of the Python
interpreter loop (eg. from ~3-16x off down to ~40-55% off) and the Python
performance (eg. unpack_sequence from ~50% slower to ~8% faster than GCC) due to
better register allocation under PGO.

[davidxl]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1170

what is the root cause of missing header weight?

1184

What is the intuition behind this heuristic?

1196

Is this check needed? MinHeaderWeight is always set.

test/Analysis/BlockFrequencyInfo/irreducible_pgo.ll

83

The test simplification change can be committed as a separate patch.

test/Transforms/PGOProfile/irreducible.ll

72

Split out the test simplification change into another patch.

[hjyamauchi]

Rebased and addressed comments.

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1170

General transformations/optimizations that happen after the PGO annotation pass and manipulate the CFG like tail dup, block splitting, etc.

1184

The idea is to not to disrupt the existing trends too much by using a weight that's in the general range of the other headers' weights (eg. don't want to use a weight of 1000000 when the others have weights in the range of 1-10). The average weight, as opposed to the minimum, would also work in that regard. But based on the performance data, the minimum seems to work better. *Maybe* because the average could be off-base if there are major outliers (a few very hot headers) and the cold headers may be more common than warm/hot headers. Added more to the comment.

1196

Done. Still need to check against the zero value which addLocal() has an assert against though.

[davidxl]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1184

Perhaps add a // FIXME to for better update in the passes that drop the header weight

[hjyamauchi]

Updated comment.

[davidxl]

lgtm

include/llvm/Analysis/BlockFrequencyInfoImpl.h

 // See the documentation below for BlockFrequencyInfoImpl for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/BasicBlock.h"

 bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
   // Compute mass in loop.
   DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop) << "\n");
 
   if (Loop.isIrreducible()) {
     DEBUG(dbgs() << "isIrreducible = true\n");
     Distribution Dist;
     unsigned NumHeadersWithWeight = 0;
+    Optional<uint64_t> MinHeaderWeight;
+    DenseSet<uint32_t> HeadersWithoutWeight;
+    HeadersWithoutWeight.reserve(Loop.NumHeaders);
     for (uint32_t H = 0; H < Loop.NumHeaders; ++H) {
       auto &HeaderNode = Loop.Nodes[H];
       const BlockT *Block = getBlock(HeaderNode);
       IsIrrLoopHeader.set(Loop.Nodes[H].Index);
       Optional<uint64_t> HeaderWeight = Block->getIrrLoopHeaderWeight();
-      if (!HeaderWeight)
+      if (!HeaderWeight) {
+        DEBUG(dbgs() << "Missing irr loop header metadata on "
+              << getBlockName(HeaderNode) << "\n");
+        HeadersWithoutWeight.insert(H);
         continue;
+      }
       DEBUG(dbgs() << getBlockName(HeaderNode)
             << " has irr loop header weight " << HeaderWeight.getValue()
             << "\n");
       NumHeadersWithWeight++;
       uint64_t HeaderWeightValue = HeaderWeight.getValue();
-      if (HeaderWeightValue)
+      if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight)
+        MinHeaderWeight = HeaderWeightValue;
+      if (HeaderWeightValue) {
         Dist.addLocal(HeaderNode, HeaderWeightValue);
       }
-    if (NumHeadersWithWeight != Loop.NumHeaders) {
-      // Not all headers have a weight metadata. Distribute weight evenly.
-      Dist = Distribution();
-      for (uint32_t H = 0; H < Loop.NumHeaders; ++H) {
-        auto &HeaderNode = Loop.Nodes[H];
-        Dist.addLocal(HeaderNode, 1);
-      }
+    // As a heuristic, if some headers don't have a weight, give them the
+    // minimium weight seen (not to disrupt the existing trends too much by
+    // using a weight that's in the general range of the other headers' weights,
+    // and the minimum seems to perform better than the average.)
+    // FIXME: better update in the passes that drop the header weight.
+    // If no headers have a weight, give them even weight (use weight 1).
+    if (!MinHeaderWeight)
+      MinHeaderWeight = 1;
+    for (uint32_t H : HeadersWithoutWeight) {
+      auto &HeaderNode = Loop.Nodes[H];
+      const BlockT *Block = getBlock(HeaderNode);
+      assert(!Block->getIrrLoopHeaderWeight() &&
+             "Shouldn't have a weight metadata");
+      uint64_t MinWeight = MinHeaderWeight.getValue();
+      DEBUG(dbgs() << "Giving weight " << MinWeight
+            << " to " << getBlockName(HeaderNode) << "\n");
+      if (MinWeight)
+        Dist.addLocal(HeaderNode, MinWeight);
     }
     distributeIrrLoopHeaderMass(Dist);
     for (const BlockNode &M : Loop.Nodes)
       if (!propagateMassToSuccessors(&Loop, M))
         llvm_unreachable("unhandled irreducible control flow");
-    if (NumHeadersWithWeight != Loop.NumHeaders)
-      // Not all headers have a weight metadata. Adjust header mass.
+    if (NumHeadersWithWeight == 0)
+      // No headers have a metadata. Adjust header mass.
       adjustLoopHeaderMass(Loop);
   } else {
     Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
     if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))
       llvm_unreachable("irreducible control flow to loop header!?");
     for (const BlockNode &M : Loop.members())
       if (!propagateMassToSuccessors(&Loop, M))
         // Irreducible backedge.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

for (unsigned s = 0; s < Size; s++) {
       if (EdgeCount > MaxCount)
         MaxCount = EdgeCount;
       EdgeCounts[SuccNum] = EdgeCount;
     }
     setProfMetadata(M, TI, EdgeCounts, MaxCount);
   }
 }
 
+static bool isIndirectBrTarget(BasicBlock *BB) {
+  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+    if (isa<IndirectBrInst>((*PI)->getTerminator()))
+      return true;
+  }
+  return false;
+}
+
 void PGOUseFunc::annotateIrrLoopHeaderWeights() {
   DEBUG(dbgs() << "\nAnnotating irreducible loop header weights.\n");
   // Find irr loop headers
   for (auto &BB : F) {
-    if (BFI->isIrrLoopHeader(&BB)) {
+    // As a heuristic also annotate indrectbr targets as they have a high chance
+    // to become an irreducible loop header after the indirectbr tail
+    // duplication.
+    if (BFI->isIrrLoopHeader(&BB) || isIndirectBrTarget(&BB)) {
       TerminatorInst *TI = BB.getTerminator();
       const UseBBInfo &BBCountInfo = getBBInfo(&BB);
       setIrrLoopHeaderMetadata(M, TI, BBCountInfo.CountValue);
     }
   }
 }
 
 void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) {

test/Analysis/BlockFrequencyInfo/irreducible_pgo.ll

 
 @targets = local_unnamed_addr global [256 x i8*] zeroinitializer, align 16
 @tracing = local_unnamed_addr global i32 0, align 4
 
 ; Function Attrs: noinline norecurse nounwind uwtable
 define i32 @_Z11irreduciblePh(i8* nocapture readonly %p) !prof !27 {
 entry:
   %0 = load i32, i32* @tracing, align 4
   %1 = trunc i32 %0 to i8
   %tobool = icmp eq i32 %0, 0
   br label %for.cond1
 
 for.cond1:                                        ; preds = %sw.default, %entry
   br label %dispatch_op
 
 dispatch_op:                                      ; preds = %sw.bb6, %for.cond1
   switch i8 %1, label %sw.default [

 ; CHECK-NEXT: - if.then: {{.*}} count = 299
 ; CHECK-NEXT: - TARGET_2: {{.*}} count = 98
 ; CHECK-NEXT: - sw.bb15: {{.*}} count = 99, irr_loop_header_weight = 100
 ; CHECK-NEXT: - if.then18: {{.*}} count = 99
 ; CHECK-NEXT: - unknown_op: {{.*}} count = 0
 ; CHECK-NEXT: - sw.default: {{.*}} count = 0
 ; CHECK-NEXT: - exit: {{.*}} count = 1
 ; CHECK-NEXT: - indirectgoto: {{.*}} count = 399, irr_loop_header_weight = 400
+
+; Missing some irr loop annotations.
+; Function Attrs: noinline norecurse nounwind uwtable
+define i32 @_Z11irreduciblePh2(i8* nocapture readonly %p) !prof !27 {
+entry:
+  %0 = load i32, i32* @tracing, align 4
+  %1 = trunc i32 %0 to i8
+  %tobool = icmp eq i32 %0, 0
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %sw.default, %entry
+  br label %dispatch_op
+
+dispatch_op:                                      ; preds = %sw.bb6, %for.cond1
+switch i8 %1, label %sw.default [
+    i8 0, label %sw.bb
+    i8 1, label %dispatch_op.sw.bb6_crit_edge
+    i8 2, label %sw.bb15
+  ], !prof !36
+
+dispatch_op.sw.bb6_crit_edge:                     ; preds = %dispatch_op
+  br label %sw.bb6
+
+sw.bb:                                            ; preds = %indirectgoto, %dispatch_op
+  br label %exit
+
+TARGET_1:                                         ; preds = %indirectgoto
+  br label %sw.bb6
+
+sw.bb6:                                           ; preds = %TARGET_1, %dispatch_op.sw.bb6_crit_edge
+  br i1 %tobool, label %dispatch_op, label %if.then, !prof !37  ; Missing !irr_loop !38
+
+if.then:                                          ; preds = %sw.bb6
+  br label %indirectgoto
+
+TARGET_2:                                         ; preds = %indirectgoto
+  br label %sw.bb15
+
+sw.bb15:                                          ; preds = %TARGET_2, %dispatch_op
+  br i1 %tobool, label %if.then18, label %exit, !prof !39, !irr_loop !40
+
+if.then18:                                        ; preds = %sw.bb15
+  br label %indirectgoto
+
+unknown_op:                                       ; preds = %indirectgoto
+  br label %sw.default
+
+sw.default:                                       ; preds = %unknown_op, %dispatch_op
+  br label %for.cond1
+
+exit:                                             ; preds = %sw.bb15, %sw.bb
+  ret i32 0
+
+indirectgoto:                                     ; preds = %if.then18, %if.then
+  %idxprom21 = zext i32 %0 to i64
+  %arrayidx22 = getelementptr inbounds [256 x i8*], [256 x i8*]* @targets, i64 0, i64 %idxprom21
+  %target = load i8*, i8** %arrayidx22, align 8
+  indirectbr i8* %target, [label %unknown_op, label %sw.bb, label %TARGET_1, label %TARGET_2], !prof !41, !irr_loop !42
+}
+
+; CHECK-LABEL: Printing analysis {{.*}} for function '_Z11irreduciblePh2':
+; CHECK: block-frequency-info: _Z11irreduciblePh2
+; CHECK: - sw.bb6: {{.*}} count = 100
+; CHECK: - sw.bb15: {{.*}} count = 100, irr_loop_header_weight = 100
+; CHECK: - indirectgoto: {{.*}} count = 400, irr_loop_header_weight = 400

test/Transforms/PGOProfile/irreducible.ll

 
 @targets = local_unnamed_addr global [256 x i8*] zeroinitializer, align 16
 @tracing = local_unnamed_addr global i32 0, align 4
 
 ; Function Attrs: noinline norecurse nounwind uwtable
 define i32 @_Z11irreduciblePh(i8* nocapture readonly %p) {
 entry:
   %0 = load i32, i32* @tracing, align 4
   %1 = trunc i32 %0 to i8
   %tobool = icmp eq i32 %0, 0
   br label %for.cond1
 
 for.cond1:                                        ; preds = %sw.default, %entry
   br label %dispatch_op
 
 dispatch_op:                                      ; preds = %sw.bb6, %for.cond1
   switch i8 %1, label %sw.default [
     i8 0, label %sw.bb
     i8 1, label %dispatch_op.sw.bb6_crit_edge
     i8 2, label %sw.bb15
   ]
 
 dispatch_op.sw.bb6_crit_edge:                     ; preds = %dispatch_op
   br label %sw.bb6
 
 sw.bb:                                            ; preds = %indirectgoto, %dispatch_op
   br label %exit
 
 TARGET_1:                                         ; preds = %indirectgoto
   br label %sw.bb6
+; USE: br label %sw.bb6, !irr_loop {{.*}}
 
 sw.bb6:                                           ; preds = %TARGET_1, %dispatch_op.sw.bb6_crit_edge
   br i1 %tobool, label %dispatch_op, label %if.then
 ; USE: br i1 %tobool, label %dispatch_op, label %if.then, !prof !{{[0-9]+}},
 ; USE-SAME: !irr_loop ![[SW_BB6_IRR_LOOP:[0-9]+]]
 
 if.then:                                          ; preds = %sw.bb6
   br label %indirectgoto
 
 TARGET_2:                                         ; preds = %indirectgoto
   br label %sw.bb15
+; USE: br label %sw.bb15, !irr_loop {{.*}}
 
 sw.bb15:                                          ; preds = %TARGET_2, %dispatch_op
   br i1 %tobool, label %if.then18, label %exit
 ; USE: br i1 %tobool, label %if.then18, label %exit, !prof !{{[0-9]+}},
 ; USE-SAME: !irr_loop ![[SW_BB15_IRR_LOOP:[0-9]+]]
 
 if.then18:                                        ; preds = %sw.bb15
   br label %indirectgoto