[CSSPGO] Unblock optimizations with pseudo probe instrumentation.

[hoy]

Summary

The IR/MIR pseudo probe intrinsics don't get materialized into real machine instructions and therefore they don't incur runtime cost directly. However, they come with indirect cost by blocking certain optimizations. Some of the blocking are intentional (such as blocking code merge) for better counts quality while the others are accidental. This change unblocks perf-critical optimizations that do not affect counts quality. They include:

1. IR InstCombine, sinking load operation to shorten lifetimes.
2. MIR LiveRangeShrink, similar to #1
3. MIR MachineSinking, similar to #1
4. MIR TwoAddressInstructionPass, i.e, opeq transform
5. MIR function argument copy elision
6. IR stack protection. (though not perf-critical but nice to have).

[hoy]

Updating D95982: [CSSPGO] Unblock optimizations with pseudo probe instrumentation.

[wmi]

Is it possible to add testcases for those cases where optimizations were unblocked by the patch?

[hoy]

In D95982#2546648, @wmi wrote:

Is it possible to add testcases for those cases where optimizations were unblocked by the patch?

Good point. Let me try add some tests.

[hoy]

Adding test cases for optimizations blocked by pseudo probes.

Test omitted for certain cases where debug instrinsic checks are replaced with debug and pseudo probe checks.

[wmi]

llvm/lib/CodeGen/TwoAddressInstructionPass.cpp

805–810

Similar to IR pass, add a MachineInstr::isDebugOrPseudoInstr()?

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

152–157

Make it a little more general?

if (auto *CB = dyn_cast<CallBase>(I))
  if (CB->onlyAccessesInaccessibleMemory())
    continue;

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

595

Make it a little more general in the same way as above.

[hoy]

llvm/lib/CodeGen/TwoAddressInstructionPass.cpp

805–810

Good suggestion, thanks.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

152–157

I think we might want to be a bit conservative here, since in theory onlyAccessesInaccessibleMemory still accesses memory. This may lead to

1. Functions with onlyAccessesInaccessibleMemory calls may not be free to be removed.
2. Calls with onlyAccessesInaccessibleMemory may not be moved around across each other.

Pseudo probe don't have such effects thus checking against pseudo probes here should have minimal impact. What do you think?

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

595

Sounds good to generalize here since the LoadInst to be sinked doesn't access inaccessible memory.

[hoy]

Addressing Wei's feedbacks.

[wmi]

LGTM.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

152–157

Right. It is better to be conservative here.

llvm/lib/CodeGen/LiveRangeShrink.cpp

for (MachineBasicBlock::iterator Next = MBB.begin(); Next != MBB.end();) {
             BarrierMI = UseMap[MO.getReg()].second;
           }
       }
 
       if (!MI.isSafeToMove(nullptr, SawStore)) {
         // If MI has side effects, it should become a barrier for code motion.
         // IOM is rebuild from the next instruction to prevent later
         // instructions from being moved before this MI.
-        if (MI.hasUnmodeledSideEffects() && Next != MBB.end()) {
+        if (MI.hasUnmodeledSideEffects() && !MI.isPseudoProbe() &&
+            Next != MBB.end()) {
           BuildInstOrderMap(Next, IOM);
           SawStore = false;
         }
         continue;
       }
 
       const MachineOperand *DefMO = nullptr;
       MachineInstr *Insert = nullptr;

llvm/lib/CodeGen/MachineBlockPlacement.cpp

bool MachineBlockPlacement::maybeTailDuplicateBlock(
   }
   return Removed;
 }
 
 // Count the number of actual machine instructions.
 static uint64_t countMBBInstruction(MachineBasicBlock *MBB) {
   uint64_t InstrCount = 0;
   for (MachineInstr &MI : *MBB) {
-    if (!MI.isPHI() && !MI.isMetaInstruction())
+    if (!MI.isPHI() && !MI.isMetaInstruction() && !MI.isPseudoProbe())
       InstrCount += 1;
   }
   return InstrCount;
 }
 
 // The size cost of duplication is the instruction size of the duplicated block.
 // So we should scale the threshold accordingly. But the instruction size is not
 // available on all targets, so we use the number of instructions instead.

llvm/lib/CodeGen/MachineInstr.cpp

 bool MachineInstr::hasOrderedMemoryRef() const {
   // An instruction known never to access memory won't have a volatile access.
   if (!mayStore() &&
       !mayLoad() &&
       !isCall() &&
       !hasUnmodeledSideEffects())
     return false;
 
+  // A pseudo probe instruction doesn't really have a memory volatile access.
+  if (isPseudoProbe())
+    return false;
+
   // Otherwise, if the instruction has no memory reference information,
   // conservatively assume it wasn't preserved.
   if (memoperands_empty())
     return true;
 
   // Check if any of our memory operands are ordered.
   return llvm::any_of(memoperands(), [](const MachineMemOperand *MMO) {
     return !MMO->isUnordered();
if (isInlineAsm()) {
     if (ExtraInfo & InlineAsm::Extra_HasSideEffects)
       return true;
   }
 
   return false;
 }
 
 bool MachineInstr::isLoadFoldBarrier() const {
-  return mayStore() || isCall() || hasUnmodeledSideEffects();
+  return mayStore() || isCall() ||
+         (hasUnmodeledSideEffects() && !isPseudoProbe());
 }
 
 /// allDefsAreDead - Return true if all the defs of this instruction are dead.
 ///
 bool MachineInstr::allDefsAreDead() const {
   for (const MachineOperand &MO : operands()) {
     if (!MO.isReg() || MO.isUse())
       continue;

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

findArgumentCopyElisionCandidates(const DataLayout &DL,
   // FIXME: Handle structs initialized with multiple stores.
   for (const Instruction &I : FuncInfo->Fn->getEntryBlock()) {
     // Look for stores, and handle non-store uses conservatively.
     const auto *SI = dyn_cast<StoreInst>(&I);
     if (!SI) {
       // We will look through cast uses, so ignore them completely.
       if (I.isCast())
         continue;
-      // Ignore debug info intrinsics, they don't escape or store to allocas.
-      if (isa<DbgInfoIntrinsic>(I))
+      // Ignore debug info and pseudo op intrinsics, they don't escape or store
+      // to allocas.
+      if (I.isDebugOrPseudoInst())
         continue;
       // This is an unknown instruction. Assume it escapes or writes to all
       // static alloca operands.
       for (const Use &U : I.operands()) {
         if (StaticAllocaInfo *Info = GetInfoIfStaticAlloca(U))
           *Info = StaticAllocaInfo::Clobbered;
       }
       continue;

llvm/lib/CodeGen/StackProtector.cpp

for (const User *U : AI->users()) {
     case Instruction::PtrToInt:
       if (AI == cast<PtrToIntInst>(I)->getOperand(0))
         return true;
       break;
     case Instruction::Call: {
       // Ignore intrinsics that do not become real instructions.
       // TODO: Narrow this to intrinsics that have store-like effects.
       const auto *CI = cast<CallInst>(I);
-      if (!isa<DbgInfoIntrinsic>(CI) && !CI->isLifetimeStartOrEnd())
+      if (!CI->isDebugOrPseudoInst() && !CI->isLifetimeStartOrEnd())
         return true;
       break;
     }
     case Instruction::Invoke:
       return true;
     case Instruction::GetElementPtr: {
       // If the GEP offset is out-of-bounds, or is non-constant and so has to be
       // assumed to be potentially out-of-bounds, then any memory access that

llvm/lib/CodeGen/TwoAddressInstructionPass.cpp

bool TwoAddressInstructionPass::rescheduleMIBelowKill(
   }
 
   // Check if the reschedule will not break dependencies.
   unsigned NumVisited = 0;
   MachineBasicBlock::iterator KillPos = KillMI;
   ++KillPos;
   for (MachineInstr &OtherMI : make_range(End, KillPos)) {
     // Debug instructions cannot be counted against the limit.
     if (OtherMI.isDebugInstr())
       continue;
+    // Pseudo probe instructions cannot be counted against the limit.
+    if (OtherMI.isPseudoProbe())
+      continue;
     if (NumVisited > 10)  // FIXME: Arbitrary limit to reduce compile time cost.
       return false;
     ++NumVisited;
     if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
         OtherMI.isBranch() || OtherMI.isTerminator())
       // Don't move pass calls, etc.
       return false;
     for (const MachineOperand &MO : OtherMI.operands()) {
       if (!MO.isReg())
bool TwoAddressInstructionPass::rescheduleKillAboveMI(
 
   // Check if the reschedule will not break depedencies.
   unsigned NumVisited = 0;
   for (MachineInstr &OtherMI :
        make_range(mi, MachineBasicBlock::iterator(KillMI))) {
     // Debug instructions cannot be counted against the limit.
     if (OtherMI.isDebugInstr())
       continue;
+    // Pseudo probe instructions cannot be counted against the limit.
+    if (OtherMI.isPseudoProbe())
+      continue;
     if (NumVisited > 10)  // FIXME: Arbitrary limit to reduce compile time cost.
       return false;
     ++NumVisited;
     if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
         OtherMI.isBranch() || OtherMI.isTerminator())
       // Don't move pass calls, etc.
       return false;
     SmallVector<Register, 2> OtherDefs;

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

if (auto *Call = dyn_cast<CallBase>(I)) {
         continue;
       FunctionModRefBehavior MRB = AAR.getModRefBehavior(Call);
       ModRefInfo MRI = createModRefInfo(MRB);
 
       // If the call doesn't access memory, we're done.
       if (isNoModRef(MRI))
         continue;
 
+      // A pseudo probe call shouldn't change any function attribute since it
+      // doesn't translate to a real instruction. It comes with a memory access
+      // tag to prevent itself being removed by optimizations and not block
+      // other instructions being optimized.
+      if (isa<PseudoProbeInst>(I))
+        continue;
+
       if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
         // The call could access any memory. If that includes writes, note it.
         if (isModSet(MRI))
           WritesMemory = true;
         // If it reads, note it.
         if (isRefSet(MRI))
           ReadsMemory = true;
         continue;

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

 ///
 /// Finally, it is safe, but not profitable, to sink a load targeting a
 /// non-address-taken alloca.  Doing so will cause us to not promote the alloca
 /// to a register.
 static bool isSafeAndProfitableToSinkLoad(LoadInst *L) {
   BasicBlock::iterator BBI = L->getIterator(), E = L->getParent()->end();
 
   for (++BBI; BBI != E; ++BBI)
-    if (BBI->mayWriteToMemory())
+    if (BBI->mayWriteToMemory() && !isa<PseudoProbeInst>(BBI))
       return false;
 
   // Check for non-address taken alloca.  If not address-taken already, it isn't
   // profitable to do this xform.
   if (AllocaInst *AI = dyn_cast<AllocaInst>(L->getOperand(0))) {
     bool isAddressTaken = false;
     for (User *U : AI->users()) {
       if (isa<LoadInst>(U)) continue;

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
           LLVM_DEBUG(dbgs() << "IC: ConstFold operand of: " << *Inst
                             << "\n    Old = " << *C
                             << "\n    New = " << *FoldRes << '\n');
           U = FoldRes;
           MadeIRChange = true;
         }
       }
 
-      // Skip processing debug intrinsics in InstCombine. Processing these call instructions
-      // consumes non-trivial amount of time and provides no value for the optimization.
-      if (!isa<DbgInfoIntrinsic>(Inst)) {
+      // Skip processing debug and pseudo intrinsics in InstCombine. Processing
+      // these call instructions consumes non-trivial amount of time and
+      // provides no value for the optimization.
+      if (!Inst->isDebugOrPseudoInst()) {
         InstrsForInstCombineWorklist.push_back(Inst);
         SeenAliasScopes.analyse(Inst);
       }
     }
 
     // Recursively visit successors.  If this is a branch or switch on a
     // constant, only visit the reachable successor.
     Instruction *TI = BB->getTerminator();