[WIP][Attributor] AAHotCold Use CFG to propagate hot cold.

[kuter]

Summary

This patch makes it possible to propagate hot cold across basic
blocks with in the attributes. It relies on the BranchProbabilityInfo
to check if a edge is hot or cold.

The hot cold information is propagated both to successors and to
predecessors.

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9728

I don't like the true => hot, false = cold encoding. We should make it explicit.

How does the backwards traversal change anything here? I can see how it might if we do more in Propagate.
Also, we should not walk the CFG twice. WDYT about one of the following two:

1. Keep a list of blocks for which we actually want to know hot/cold information. We want to know if there is a call site for which we want to know, and then transitively other blocks around if possible, or
2. Expand from known information. So we use some sources of hotness and only look at the blocks for which we have a hot/cold annotation and try to add more to the set.

[kuter]

rebase, fix tests, change propagation technique.
I will add a test.

[kuter]

Rebase

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

 
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/NoFolder.h"
 #include "llvm/Support/Alignment.h"
 #include "llvm/Support/Casting.h"
ChangeStatus updateImpl(Attributor &A) override {
     };
 
     bool UsedAssumed = false;
     if (!A.checkForAllCallLikeInstructions(CheckCall, *this, UsedAssumed)) {
       // If we haven't looked at all instructions we can't trust this data.
       BlockStatus.clear();
     }
 
+    Function &Fn = *getAssociatedFunction();
+    if (Fn.isDeclaration() || BlockStatus.empty())
+      return Change;
+
+    // Propagate across blocks.
+    BranchProbabilityInfo *BPInfo =
+        A.getInfoCache()
+            .getAnalysisResultForFunction<BranchProbabilityAnalysis>(Fn);
+
+    auto Propagate = [&](BasicBlock *Pred, BasicBlock *Block,
+                         HotColdState &CurrentStatus) {
+      if (!BlockStatus.count(Pred))
+        return true;
+      HotColdState PredStatus = BlockStatus[Pred];
+      if (PredStatus.getAssumed() == INVALID)
+        return true;
+      if (PredStatus.isAssumedHot()) {
+        // One of our predecessors are hot.
+        // If the edge is hot also we can assume that this block is hot.
+        if (BPInfo->isEdgeHot(Pred, Block)) {
+          CurrentStatus &= PredStatus;
+          return false;
+        }
+        return true;
+      }
+
+      CurrentStatus &= PredStatus;
+      return true;
+    };
+
+    SmallPtrSet<BasicBlock *, 16> Visited;
+    SmallVector<BasicBlock *, 16> Worklist;
+
+    // Start from blocks that we know about, and expand from there.
+    for (auto BPair : BlockStatus)
+      Worklist.push_back(BPair.first);
+
+    while (!Worklist.empty()) {
+      BasicBlock *Block = Worklist.pop_back_val();
+      if (!Visited.insert(Block).second)
+        continue;
+
+      for (BasicBlock *Succ : successors(Block))
+        Worklist.push_back(Succ);
+
+      // If the block already has information, skip this block.
+      if (BlockStatus.count(Block))
+        continue;
+
+      HotColdState &CurrentStatus = BlockStatus[Block];
+      HotColdState OldStatus = CurrentStatus;
+      for (BasicBlock *Pred : predecessors(Block)) {
+        if (!Propagate(Pred, Block, CurrentStatus))
+          break;
+      }
+
+      // Track changes.
+      Change |= CurrentStatus == OldStatus ? ChangeStatus::UNCHANGED
+                                           : ChangeStatus::CHANGED;
+    }
+
     return Change;
   }
 
   void trackStatistics() const override {
     STATISTIC(NumFunctionsMarkedHot, "Number of functions marked hot");
     STATISTIC(NumFunctionsMarkedCold, "Number of functions marked cold");
 
     if (isAssumedHot())
const auto Attrs = {
         Attribute::get(Ctx, isAssumedHot() ? Attribute::Hot : Attribute::Cold)};
     return IRAttributeManifest::manifestAttrs(A, this->getIRPosition(), Attrs);
   }
 
   /// This represents the information we have about a basic block.
   /// we use this information to determine if a callsite inside the
   /// block is hot or cold.
   /// A block not being in here means that we don't know if it is hot or cold.
   /// A llvm::None value means that we now that we can't know for sure.
   DenseMap<BasicBlock *, HotColdState> BlockStatus;
 };
 
 struct AAHotColdCallSite : public AAHotColdImpl {
   AAHotColdCallSite(const IRPosition &IRP, Attributor &A)
       : AAHotColdImpl(IRP, A) {}
 
   ChangeStatus updateImpl(Attributor &A) override {

llvm/test/Transforms/Attributor/IPConstantProp/2009-09-24-byval-ptr.ll

 ; IS__TUNIT_OPM-NEXT:    call void @vfu1(%struct.MYstr* nocapture nofree noundef nonnull readonly byval([[STRUCT_MYSTR:%.*]]) align 8 dereferenceable(8) @mystr) #[[ATTR0]]
 ; IS__TUNIT_OPM-NEXT:    [[RESULT:%.*]] = call i32 @vfu2_v2(%struct.MYstr* nocapture nofree noundef nonnull readonly byval([[STRUCT_MYSTR]]) align 8 dereferenceable(8) @mystr) #[[ATTR2]]
 ; IS__TUNIT_OPM-NEXT:    ret i32 [[RESULT]]
 ;
 ; IS__TUNIT_NPM: Function Attrs: nounwind
 ; IS__TUNIT_NPM-LABEL: define {{[^@]+}}@unions_v2
 ; IS__TUNIT_NPM-SAME: () #[[ATTR0]] {
 ; IS__TUNIT_NPM-NEXT:  entry:
-; IS__TUNIT_NPM-NEXT:    [[MYSTR_CAST1:%.*]] = bitcast %struct.MYstr* @mystr to i8*
-; IS__TUNIT_NPM-NEXT:    [[TMP0:%.*]] = load i8, i8* [[MYSTR_CAST1]], align 8
-; IS__TUNIT_NPM-NEXT:    [[MYSTR_0_12:%.*]] = getelementptr [[STRUCT_MYSTR:%.*]], %struct.MYstr* @mystr, i32 0, i32 1
-; IS__TUNIT_NPM-NEXT:    [[TMP1:%.*]] = load i32, i32* [[MYSTR_0_12]], align 8
-; IS__TUNIT_NPM-NEXT:    call void @vfu1(i8 [[TMP0]], i32 [[TMP1]]) #[[ATTR0]]
 ; IS__TUNIT_NPM-NEXT:    [[MYSTR_CAST:%.*]] = bitcast %struct.MYstr* @mystr to i8*
-; IS__TUNIT_NPM-NEXT:    [[TMP2:%.*]] = load i8, i8* [[MYSTR_CAST]], align 8
-; IS__TUNIT_NPM-NEXT:    [[MYSTR_0_1:%.*]] = getelementptr [[STRUCT_MYSTR]], %struct.MYstr* @mystr, i32 0, i32 1
-; IS__TUNIT_NPM-NEXT:    [[TMP3:%.*]] = load i32, i32* [[MYSTR_0_1]], align 8
+; IS__TUNIT_NPM-NEXT:    [[TMP0:%.*]] = load i8, i8* [[MYSTR_CAST]], align 8
+; IS__TUNIT_NPM-NEXT:    [[MYSTR_0_1:%.*]] = getelementptr [[STRUCT_MYSTR:%.*]], %struct.MYstr* @mystr, i32 0, i32 1
+; IS__TUNIT_NPM-NEXT:    [[TMP1:%.*]] = load i32, i32* [[MYSTR_0_1]], align 8
+; IS__TUNIT_NPM-NEXT:    call void @vfu1(i8 [[TMP0]], i32 [[TMP1]]) #[[ATTR0]]
+; IS__TUNIT_NPM-NEXT:    [[MYSTR_CAST1:%.*]] = bitcast %struct.MYstr* @mystr to i8*
+; IS__TUNIT_NPM-NEXT:    [[TMP2:%.*]] = load i8, i8* [[MYSTR_CAST1]], align 8
+; IS__TUNIT_NPM-NEXT:    [[MYSTR_0_12:%.*]] = getelementptr [[STRUCT_MYSTR]], %struct.MYstr* @mystr, i32 0, i32 1
+; IS__TUNIT_NPM-NEXT:    [[TMP3:%.*]] = load i32, i32* [[MYSTR_0_12]], align 8
 ; IS__TUNIT_NPM-NEXT:    [[RESULT:%.*]] = call i32 @vfu2_v2(i8 [[TMP2]], i32 [[TMP3]]) #[[ATTR2]]
 ; IS__TUNIT_NPM-NEXT:    ret i32 [[RESULT]]
 ;
 ; IS__CGSCC_OPM: Function Attrs: nounwind
 ; IS__CGSCC_OPM-LABEL: define {{[^@]+}}@unions_v2
 ; IS__CGSCC_OPM-SAME: () #[[ATTR0]] {
 ; IS__CGSCC_OPM-NEXT:  entry:
 ; IS__CGSCC_OPM-NEXT:    call void @vfu1(%struct.MYstr* noalias nocapture nofree noundef nonnull readonly byval([[STRUCT_MYSTR:%.*]]) align 8 dereferenceable(8) @mystr) #[[ATTR0]]

llvm/test/Transforms/Attributor/depgraph.ll

 ; GRAPH-EMPTY:
 ; GRAPH-NEXT: [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state memory:argument
 ; GRAPH-NEXT:   updates [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]} with state memory:argument
 ; GRAPH-NEXT:   updates [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]} with state memory:argument
 ; GRAPH-EMPTY:
 ; GRAPH-NEXT: [AAHeapToStack] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state [H2S] Mallocs Good/Bad: 0/0
 ; GRAPH-EMPTY:
 ; GRAPH-NEXT: [AAHotCold] for CtxI ' %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state HotCold[Invalid]
+; GRAPH-NEXT: updates [AAHotCold] for CtxI ' %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state HotCold[Invalid]
 ; GRAPH-EMPTY:
 ; GRAPH-NEXT: [AAValueSimplify] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]} with state not-simple
 ; GRAPH-EMPTY:
 ; GRAPH-NEXT: [AAAlign] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]} with state align<1-16>
 ; GRAPH-NEXT:   updates [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]} with state align<1-16>
 ; GRAPH-NEXT:   updates [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]} with state align<1-16>
 ; GRAPH-EMPTY:
 ; GRAPH-NEXT: [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]} with state nonnull