[CSSPGO] Move pseudo probes to the beginning of a block to unblock SelectionDAG combine.

[hoy]

Summary

Pseudo probes, when scattered in a block, can be chained dependencies of other regular DAG nodes and block DAG combine optimizations. To fix this, scattered probes in a block are grouped and placed at the beginning of the block. This shouldn't affect the profile quality.

Test Plan:

[hoy]

Fixing test issue.

[wmi]

llvm/lib/CodeGen/CodeGenPrepare.cpp

8004–8005

Why pseudo probes need to be put after debug instructions on the top, is it necessary?

[hoy]

llvm/lib/CodeGen/CodeGenPrepare.cpp

8004–8005

Probes are not necessary to be after debug instructions, but thought it would be nice to keep existing probes that are in the beginning of the block in order.

[wmi]

LGTM.

[wenlei]

llvm/lib/CodeGen/CodeGenPrepare.cpp

8001

For dbg values, redundancy removal and placement are separate. Do we want to follow that?

Since removeRedundantPseudoProbes is part of RemoveRedundantDbgInstrs already, how critical is this extra removal?

[hoy]

llvm/lib/CodeGen/CodeGenPrepare.cpp

8001

Good point. They should be separate for pseudo probes as well, to be consistent with debug instrs.

The removal is not critical. It doesn't block DAG optimizations. Though it would be nice to remove redundancy from time to time for compilation time. This can be done as a separate change to find more promising places for redundancy removal. Removing it for now.

[hoy]

Removing removeRedundantPseudoProbes calls.

[wenlei]

lgtm, thanks.

llvm/lib/CodeGen/CodeGenPrepare.cpp

private:
     bool optimizeFunnelShift(IntrinsicInst *Fsh);
     bool optimizeSelectInst(SelectInst *SI);
     bool optimizeShuffleVectorInst(ShuffleVectorInst *SVI);
     bool optimizeSwitchInst(SwitchInst *SI);
     bool optimizeExtractElementInst(Instruction *Inst);
     bool dupRetToEnableTailCallOpts(BasicBlock *BB, bool &ModifiedDT);
     bool fixupDbgValue(Instruction *I);
     bool placeDbgValues(Function &F);
+    bool placePseudoProbes(Function &F);
     bool canFormExtLd(const SmallVectorImpl<Instruction *> &MovedExts,
                       LoadInst *&LI, Instruction *&Inst, bool HasPromoted);
     bool tryToPromoteExts(TypePromotionTransaction &TPT,
                           const SmallVectorImpl<Instruction *> &Exts,
                           SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
                           unsigned CreatedInstsCost = 0);
     bool mergeSExts(Function &F);
     bool splitLargeGEPOffsets();
for (BasicBlock &BB : F)
           Statepoints.push_back(SP);
     for (auto &I : Statepoints)
       EverMadeChange |= simplifyOffsetableRelocate(*I);
   }
 
   // Do this last to clean up use-before-def scenarios introduced by other
   // preparatory transforms.
   EverMadeChange |= placeDbgValues(F);
+  EverMadeChange |= placePseudoProbes(F);
 
 #ifndef NDEBUG
   if (VerifyBFIUpdates)
     verifyBFIUpdates(F);
 #endif
 
   return EverMadeChange;
 }
for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
         MadeChange = true;
         ++NumDbgValueMoved;
       }
     }
   }
   return MadeChange;
 }
 
+// Group scattered pseudo probes in a block to favor SelectionDAG. Scattered
+// probes can be chained dependencies of other regular DAG nodes and block DAG
+// combine optimizations.
+bool CodeGenPrepare::placePseudoProbes(Function &F) {
+  bool MadeChange = false;
+  for (auto &Block : F) {
+    // Move the rest probes to the beginning of the block.
+    auto FirstInst = Block.getFirstInsertionPt();
+    while (FirstInst != Block.end() && FirstInst->isDebugOrPseudoInst())
+      ++FirstInst;
+    BasicBlock::iterator I(FirstInst);
+    I++;
+    while (I != Block.end()) {
+      if (auto *II = dyn_cast<PseudoProbeInst>(I++)) {
+        II->moveBefore(&*FirstInst);
+        MadeChange = true;
+      }
+    }
+  }
+  return MadeChange;
+}
+
 /// Scale down both weights to fit into uint32_t.
 static void scaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) {
   uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
   uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
   NewTrue = NewTrue / Scale;
   NewFalse = NewFalse / Scale;
 }
 

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

+; REQUIRES: x86_64-linux
+; RUN: opt < %s -codegenprepare -mtriple=x86_64 -S -o %t 
+; RUN: FileCheck %s < %t --check-prefix=IR
+; RUN: llc -mtriple=x86_64-- -stop-after=finalize-isel %t -o - | FileCheck %s --check-prefix=MIR
+
+define internal i32 @arc_compare() {
+entry:
+  %0 = load i64, i64* undef, align 8
+  br i1 undef, label %return, label %if.end
+
+if.end:                                           ; preds = %entry
+;; Check pseudo probes are next to each other at the beginning of this block.
+; IR-label: if.end
+; IR: call void @llvm.pseudoprobe(i64 5116412291814990879, i64 1, i32 0, i64 -1)
+; IR: call void @llvm.pseudoprobe(i64 5116412291814990879, i64 3, i32 0, i64 -1)
+  call void @llvm.pseudoprobe(i64 5116412291814990879, i64 1, i32 0, i64 -1)
+  %1          = load i16, i16* undef, align 8
+  call void @llvm.pseudoprobe(i64 5116412291814990879, i64 3, i32 0, i64 -1)
+  %2          = and i16 %1, 16
+  %3          = icmp eq i16 %2, 0
+;; Check the load-and-cmp sequence is fold into a test instruction.
+; MIR-label: bb.1.if.end
+; MIR: %[[#REG:]]:gr64 = IMPLICIT_DEF
+; MIR: TEST8mi killed %[[#REG]], 1, $noreg, 0, $noreg, 16
+; MIR: JCC_1
+  br i1 %3, label %return, label %if.end6
+
+if.end6:                                          ; preds = %if.end
+  call void @llvm.pseudoprobe(i64 5116412291814990879, i64 5, i32 0, i64 -1)
+  br label %return
+
+return:                                           ; preds = %if.end6, %if.end, %entry
+  ret i32 undef
+}
+
+; Function Attrs: inaccessiblememonly nounwind willreturn
+declare void @llvm.pseudoprobe(i64, i64, i32, i64) #0
+
+attributes #0 = { inaccessiblememonly nounwind willreturn }