[CSSPGO] Deduplicating dangling pseudo probes.

[hoy]

Summary

Same dangling probes are redundant since they all have the same semantic that is to rely on the counts inference tool to get reasonable count for the same original block. Therefore, there's no need to keep multiple copies of them. I've seen jump threading created tons of redundant dangling probes that slowed down the compiler dramatically. Other optimization passes can also result in redundant probes though without an observed impact so far.

This change removes block-wise redundant dangling probes specifically introduced by jump threading. To support removing redundant dangling probes caused by all other passes, a final function-wise deduplication is also added.

An 18% size win of the .pseudo_probe section was seen for SPEC2017. No performance difference was observed.

[wmi]

llvm/lib/IR/PseudoProbe.cpp

139

If the interface can be changed to collectRedundantPseudoProbes(BasicBlock *Block, SmallVectorImpl<PseudoProbeInst *> &ToBeRemoved), it can be reused by the code above to remove redundent probes for the function.

[hoy]

llvm/lib/IR/PseudoProbe.cpp

139

Thanks for the suggestion. The code above actually handles MIR pseudo probe intrinsics while the code here handles IR intrinsics. I was thinking about sharing them but I feel templated code maybe needed and not sure about the worth of that complexity. What do you think?

[wmi]

llvm/lib/IR/PseudoProbe.cpp

139

Ah, ok. I didn't notice the difference. It needs some extra header file to include the template and share it with MIR pass. It may not worth it.

llvm/test/Transforms/SampleProfile/pseudo-probe-dedup.ll

2–3

Do you need two tests one for IR pass and one for MIR pass?

[hoy]

llvm/test/Transforms/SampleProfile/pseudo-probe-dedup.ll

2–3

Oh yeah, the IR test is actually included in D97481: [CSSPGO] Unblocking optimizations by dangling pseudo probes.. Let me move it here.

[hoy]

Adding an IR test.

[hoy]

Fixing existing test code to match exactly only one copy of probes deduplcated.

[wmi]

LGTM.

llvm/include/llvm/IR/PseudoProbe.h

struct PseudoProbe {
   }
 };
 
 Optional<PseudoProbe> extractProbe(const Instruction &Inst);
 
 void setProbeDistributionFactor(Instruction &Inst, float Factor);
 
 bool moveAndDanglePseudoProbes(BasicBlock *From, Instruction *To);
+
+bool removeRedundantPseudoProbes(BasicBlock *Block);
 } // end namespace llvm
 
 #endif // LLVM_IR_PSEUDOPROBE_H

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

 /// must be in L. In addition, This utility calls on another utility:
 /// MergeBlockIntoPredecessor. Blocks are successfully merged when the call to
 /// MergeBlockIntoPredecessor returns true.
 bool MergeBlockSuccessorsIntoGivenBlocks(
     SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L = nullptr,
     DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr);
 
 /// Try to remove redundant dbg.value instructions from given basic block.
-/// Returns true if at least one instruction was removed.
-bool RemoveRedundantDbgInstrs(BasicBlock *BB);
+/// Returns true if at least one instruction was removed. Remove redundant
+/// pseudo ops when RemovePseudoOp is true.
+bool RemoveRedundantDbgInstrs(BasicBlock *BB, bool RemovePseudoOp = false);
 
 /// Replace all uses of an instruction (specified by BI) with a value, then
 /// remove and delete the original instruction.
 void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
                           BasicBlock::iterator &BI, Value *V);
 
 /// Replace the instruction specified by BI with the instruction specified by I.
 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The

llvm/lib/CodeGen/PseudoProbeInserter.cpp

 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/PseudoProbe.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/MC/MCPseudoProbe.h"
 #include "llvm/Target/TargetMachine.h"
-#include <unordered_map>
+#include <unordered_set>
 
 #define DEBUG_TYPE "pseudo-probe-inserter"
 
 using namespace llvm;
 
 namespace {
 class PseudoProbeInserter : public MachineFunctionPass {
 public:
for (MachineBasicBlock &MBB : MF) {
         // to get them a reasonable count.
         for (MachineInstr &MI : MBB) {
           if (MI.isPseudoProbe())
             MI.addPseudoProbeAttribute(PseudoProbeAttributes::Dangling);
         }
       }
     }
 
+    // Remove redundant dangling probes. Same dangling probes are redundant
+    // since they all have the same semantic that is to rely on the counts
+    // inference too to get reasonable count for the same original block.
+    // Therefore, there's no need to keep multiple copies of them.
+    auto Hash = [](const MachineInstr *MI) {
+      return std::hash<uint64_t>()(MI->getOperand(0).getImm()) ^
+             std::hash<uint64_t>()(MI->getOperand(1).getImm());
+    };
+
+    auto IsEqual = [](const MachineInstr *Left, const MachineInstr *Right) {
+      return Left->getOperand(0).getImm() == Right->getOperand(0).getImm() &&
+             Left->getOperand(1).getImm() == Right->getOperand(1).getImm() &&
+             Left->getOperand(3).getImm() == Right->getOperand(3).getImm() &&
+             Left->getDebugLoc() == Right->getDebugLoc();
+    };
+
+    SmallVector<MachineInstr *, 4> ToBeRemoved;
+    std::unordered_set<MachineInstr *, decltype(Hash), decltype(IsEqual)>
+        DanglingProbes(0, Hash, IsEqual);
+
+    for (MachineBasicBlock &MBB : MF) {
+      for (MachineInstr &MI : MBB) {
+        if (MI.isPseudoProbe()) {
+          if ((uint32_t)MI.getPseudoProbeAttribute() &
+              (uint32_t)PseudoProbeAttributes::Dangling)
+            if (!DanglingProbes.insert(&MI).second)
+              ToBeRemoved.push_back(&MI);
+        }
+      }
+    }
+
+    for (auto *MI : ToBeRemoved)
+      MI->eraseFromParent();
+
+    Changed |= !ToBeRemoved.empty();
     return Changed;
   }
 
 private:
   uint64_t getFuncGUID(Module *M, DILocation *DL) {
     auto *SP = DL->getScope()->getSubprogram();
     auto Name = SP->getLinkageName();
     if (Name.empty())

llvm/lib/IR/PseudoProbe.cpp

 // calls.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/PseudoProbe.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
+#include <unordered_set>
 
 using namespace llvm;
 
 namespace llvm {
 
 Optional<PseudoProbe> extractProbeFromDiscriminator(const Instruction &Inst) {
   assert(isa<CallBase>(&Inst) && !isa<IntrinsicInst>(&Inst) &&
          "Only call instructions should have pseudo probe encodes as their "
for (auto &I : *From) {
     }
   }
 
   for (auto *I : ToBeMoved)
     I->moveBefore(To);
 
   return !ToBeMoved.empty();
 }
+
+/// Same dangling probes in one blocks are redundant since they all have the
+/// same semantic that is to rely on the counts inference too to get reasonable
+/// count for the same original block. Therefore, there's no need to keep
+/// multiple copies of them.
+bool removeRedundantPseudoProbes(BasicBlock *Block) {
+
+  auto Hash = [](const PseudoProbeInst *I) {
+    return std::hash<uint64_t>()(I->getFuncGuid()->getZExtValue()) ^
+           std::hash<uint64_t>()(I->getIndex()->getZExtValue());
+  };
+
+  auto IsEqual = [](const PseudoProbeInst *Left, const PseudoProbeInst *Right) {
+    return Left->getFuncGuid() == Right->getFuncGuid() &&
+           Left->getIndex() == Right->getIndex() &&
+           Left->getAttributes() == Right->getAttributes() &&
+           Left->getDebugLoc() == Right->getDebugLoc();
+  };
+
+  SmallVector<PseudoProbeInst *, 4> ToBeRemoved;
+  std::unordered_set<PseudoProbeInst *, decltype(Hash), decltype(IsEqual)>
+      DanglingProbes(0, Hash, IsEqual);
+
+  for (auto &I : *Block) {
+    if (auto *II = dyn_cast<PseudoProbeInst>(&I)) {
+      if (II->getAttributes()->getZExtValue() &
+          (uint32_t)PseudoProbeAttributes::Dangling)
+        if (!DanglingProbes.insert(II).second)
+          ToBeRemoved.push_back(II);
+    }
+  }
+
+  for (auto *I : ToBeRemoved)
+    I->eraseFromParent();
+  return !ToBeRemoved.empty();
+}
 } // namespace llvm

llvm/lib/Transforms/Scalar/JumpThreading.cpp

do {
     for (auto &BB : F) {
       if (Unreachable.count(&BB))
         continue;
       while (processBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = true;
 
       // Jump threading may have introduced redundant debug values into BB
       // which should be removed.
+      // Remove redundant pseudo probes as well.
       if (Changed)
-        RemoveRedundantDbgInstrs(&BB);
+        RemoveRedundantDbgInstrs(&BB, true);
 
       // Stop processing BB if it's the entry or is now deleted. The following
       // routines attempt to eliminate BB and locating a suitable replacement
       // for the entry is non-trivial.
       if (&BB == &F.getEntryBlock() || DTU->isBBPendingDeletion(&BB))
         continue;
 
       if (pred_empty(&BB)) {
for (auto &BB : F) {
         BasicBlock *Succ = BI->getSuccessor(0);
         if (
             // The terminator must be the only non-phi instruction in BB.
             BB.getFirstNonPHIOrDbg(true)->isTerminator() &&
             // Don't alter Loop headers and latches to ensure another pass can
             // detect and transform nested loops later.
             !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
             TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU)) {
-          RemoveRedundantDbgInstrs(Succ);
+          RemoveRedundantDbgInstrs(Succ, true);
           // BB is valid for cleanup here because we passed in DTU. F remains
           // BB's parent until a DTU->getDomTree() event.
           LVI->eraseBlock(&BB);
           Changed = true;
         }
       }
     }
     EverChanged |= Changed;

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/PseudoProbe.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) {
   }
 
   for (auto &Instr : ToBeRemoved)
     Instr->eraseFromParent();
 
   return !ToBeRemoved.empty();
 }
 
-bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) {
+bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB, bool RemovePseudoOp) {
   bool MadeChanges = false;
   // By using the "backward scan" strategy before the "forward scan" strategy we
   // can remove both dbg.value (2) and (3) in a situation like this:
   //
   //   (1) dbg.value V1, "x", DIExpression()
   //       ...
   //   (2) dbg.value V2, "x", DIExpression()
   //   (3) dbg.value V1, "x", DIExpression()
   //
   // The backward scan will remove (2), it is made obsolete by (3). After
   // getting (2) out of the way, the foward scan will remove (3) since "x"
   // already is described as having the value V1 at (1).
   MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB);
   MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB);
+  if (RemovePseudoOp)
+    MadeChanges |= removeRedundantPseudoProbes(BB);
 
   if (MadeChanges)
     LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
                       << BB->getName() << "\n");
   return MadeChanges;
 }
 
 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,

llvm/test/Transforms/SampleProfile/pseudo-probe-dangle.ll

 
 ;; Check block T and F are gone, and their probes (probe 2 and 3) are dangling.
 ; MIR-tail: bb.0
 ; MIR-tail: PSEUDO_PROBE [[#GUID:]], 1, 0, 0
 ; MIR-tail: PSEUDO_PROBE [[#GUID:]], 2, 0, 2
 ; MIR-tail: PSEUDO_PROBE [[#GUID:]], 3, 0, 2
 ; MIR-tail: PSEUDO_PROBE [[#GUID:]], 4, 0, 0
 
+
+define void @foo2() {
+bb:
+  %tmp = call i32 @f1()
+  %tmp1 = icmp eq i32 %tmp, 1
+  br i1 %tmp1, label %bb5, label %bb8
+
+bb2:
+  %tmp4 = icmp ne i32 %tmp, 1
+  switch i1 %tmp4, label %bb2 [
+  i1 0, label %bb5
+  i1 1, label %bb8
+  ]
+
+bb5:
+;; Check the pseudo probe with id 3 only has one copy.
+; JT-COUNT-1: call void @llvm.pseudoprobe(i64 [[#GUID2:]], i64 3, i32 2, i64 -1)
+; JT-NOT: call void @llvm.pseudoprobe(i64 [[#GUID2:]], i64 3, i32 2, i64 -1)
+  %tmp6 = phi i1 [ %tmp1, %bb ], [ false, %bb2 ]
+  br i1 %tmp6, label %bb8, label %bb7
+
+bb7:
+  br label %bb8
+
+bb8:
+  ret void
+}
+
 define i32 @test(i32 %a, i32 %b, i32 %c) {
 ;; Check block bb1 and bb2 are gone, and their probes (probe 2 and 3) are dangling.
 ; SC-LABEL: @test(
 ; SC-LABEL-NO: bb1
 ; SC-LABEL-NO: bb2
 ; SC:    [[T1:%.*]] = icmp eq i32 [[B:%.*]], 0
 ; SC-DAG:    call void @llvm.pseudoprobe(i64 [[#GUID3:]], i64 2, i32 2, i64 -1)
 ; SC-DAG:    call void @llvm.pseudoprobe(i64 [[#GUID3]], i64 3, i32 2, i64 -1)

llvm/test/Transforms/SampleProfile/pseudo-probe-dedup.ll

+; REQUIRES: x86_64-linux
+; RUN: llc -pseudo-probe-for-profiling %s -filetype=asm -o - | FileCheck %s
+
+declare i32 @f1()
+declare void @llvm.pseudoprobe(i64, i64, i32, i64) #0
+
+define void @foo2() {
+bb:
+; CHECK: .pseudoprobe 2494702099028631698 1 0 0
+  call void @llvm.pseudoprobe(i64 2494702099028631698, i64 1, i32 0, i64 -1)
+  %tmp = call i32 @f1()
+  %tmp1 = icmp eq i32 %tmp, 1
+  br i1 %tmp1, label %bb5, label %bb8
+
+bb2:
+;; Check the pseudo probe with id 2 only has one copy.
+; CHECK-COUNT-1: .pseudoprobe 2494702099028631698 2 0 2
+; CHECK-NOT: .pseudoprobe 2494702099028631698 2 0 2
+  call void @llvm.pseudoprobe(i64 2494702099028631698, i64 2, i32 2, i64 -1)
+  %tmp4 = icmp ne i32 %tmp, 1
+  call void @llvm.pseudoprobe(i64 2494702099028631698, i64 2, i32 2, i64 -1)
+  switch i1 %tmp4, label %bb2 [
+  i1 0, label %bb5
+  i1 1, label %bb8
+  ]
+
+bb5:
+  %tmp6 = phi i1 [ %tmp1, %bb ], [ false, %bb2 ]
+  call void @llvm.pseudoprobe(i64 2494702099028631698, i64 2, i32 2, i64 -1)
+  br i1 %tmp6, label %bb8, label %bb7
+
+bb7:
+  br label %bb8
+
+bb8:
+  ret void
+}
+
+!llvm.pseudo_probe_desc = !{!0}
+
+!0 = !{i64 2494702099028631698, i64 281612674956943, !"foo2", null}
 No newline at end of file