[Pseudo Probe] Do not instrument EH blocks.

[hoy]

Summary

This change avoids inserting probes to EH blocks. Pseudo probe can prevent block merging when probes in the blocks look different. This has a chained effect to passes incurring exponential IR growth (such as jump threading) and as a consequence the compilation may time out. Not inserting probes to EH blocks could mitigate the issue. Another benefit is that both IR size and binary size are smaller. Since EH blocks are usually cold, the change should have minimal impact to profile quality.

Testing:

Out of two internal large benchmarks, no perf impact seen. 1% size savings to both the text and the pseudo_probe section.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

257

nit: inclined to say something like KnownColdBlocks, and treating EH as one kind of code blocks.

262

For this BFS to work, you want to start only from EH region entries. I think isLandingPad marks entries, but isEHPad could be in the middle of EH regions? IIUC, isEHPad is a superset of isLandingPad.

Starting from middle will make it look like having non-EH predecessor, which is not true. It probably doesn't lead to wrong result in current implementation for two reasons: 1) most likely lexical order guarantee EH entry is visited first, 2) if middle blocks are visited first and determined having non-EH predecessor, later visit from EH entry will still cover these blocks and mark them EH. But it feel unnecessary to start from the middle.

277–278

Is this necessary? If Predecessor is non-EH, we will break out the loop later; if it's EH, line 274 should have skipped this Predecessor/Successor already.

[hoy]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

257

Sounds good.

262

Yeah, EHPad is a superset of LandingPad, just checking against EHPad should be enough.

Starting from middle will make it look like having non-EH predecessor, which is not true.

Can a middle block of an EH region be reachable from non-EH path? I'm using it as seeds here. isEHPad is define below. I'm not sure how CatchSwitch is but all other types seem can be only run on EH paths?

/// Return true if the instruction is a variety of EH-block.
bool isEHPad() const {
  switch (getOpcode()) {
  case Instruction::CatchSwitch:
  case Instruction::CatchPad:
  case Instruction::CleanupPad:
  case Instruction::LandingPad:
    return true;
  default:
    return false;
  }
}

277–278

It's necessary if the successor forms a self-loop. In such case, the self back edge should be ignored.

[hoy]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262

OK, by definition, CatchSwitch should refer to EH blocks only: https://llvm.org/docs/LangRef.html#catchswitch-instruction

[hoy]

Updating D142747: [Pseudo Probe] Do not instrument EH blocks.

[wlei]

Will this affect PROFI? if we don't insert probe for EH block, does PROFI assign a cold(0) value to the BB or leave it with an unknown value like the dangling probe?

[hoy]

In D142747#4086745, @wlei wrote:

Will this affect PROFI? if we don't insert probe for EH block, does PROFI assign a cold(0) value to the BB or leave it with an unknown value like the dangling probe?

Yes, it will affect Profi. The effect is just like removing those EH blocks from the IR. No corresponding counters (even 0) will show up in the profile. Profi can somehow deal with it smartly: https://github.com/llvm/llvm-project/blob/61eb12e1f423063b0ead944827dc53b02baed0d4/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h#L294.

[wlei]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262–264

Since this skipped some BBs and might assign different id to the same BB, it seems to me this will cause some profile matching issue? say, it's good for on-demand profiling, but for the profile in the production, it still used the old number of BB.

[hoy]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262–264

This is very good point! Yeah, the downwards compatibility is being screwed up there. I guess we can give blocks the same original id, but then it's always going to be like that. Fortunately this change is so far only needed for llvm-15 and there should be no legacy profiles.

[wlei]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262–264

Good to know it's only needed for llvm-15, just I think in this case people need to remind that when upgrading to llvm-15 it should use a new fresh profile, using the profile collected from the old version could cause some regression due to this. Incremental PGO might detect/mitigate this issue if happens :)

[hoy]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262–264

Yeah, platform upgrade should always come with a new round of profile refresh.

[modimo]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262

Can a middle block of an EH region be reachable from non-EH path?

No, https://eel.is/c++draft/except.pre:

A handler will be invoked only by throwing an exception in code executed in the handler's try block or in functions called from the handler's try block.

[modimo]

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

[wenlei]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

277–278

What I'm saying is the self back edge will be ignored without this check (see reasoning above), or am I wrong?

[wenlei]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262–264

Do we require probe Id to be consecutive? If not, skipping blocks we exclude actually isn't a bad idea? It makes probe Id more stable and it gives us flexibility to make changes in this area without breaking compatibility (i.e. we could revert this change in llvm-15, or even exclude other cold blocks later if needed with minimum impact).

[hoy]

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

Oh I just remembered that code. They're basically the same algorithm. But given that IR and MIR routines are usually implemented separately otherwise templated code would be needed, I'd like to keep as is. WDYT?

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

262–264

(i.e. we could revert this change in llvm-15, or even exclude other cold blocks later if needed with minimum impact).

The concern is valid. Probe ids do not need to be consecutive. I'll make it downwards compatible.

277–278

Without this check the self back edge is going to be ignored in a different way such that the block will never be considered EH-only.

[hoy]

Updating D142747: [Pseudo Probe] Do not instrument EH blocks.

[modimo]

In D142747#4087043, @hoy wrote:

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

Oh I just remembered that code. They're basically the same algorithm. But given that IR and MIR routines are usually implemented separately otherwise templated code would be needed, I'd like to keep as is. WDYT?

I'm okay either way. That being said, all of BFI is templated on BB and MBB:

template <class BT> class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase {

Given there's precedence and how identical the code I think it makes sense to combine them so they can't get out of sync.

[wenlei]

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

That diff also used EHPad as seeds for BFS, I thought we only need LandingPads as seeds? Though I think for simple algorithm, having MIR and IR implementation separated is probably fine. I also don't know where to put a merged version..

if (MBB.isEHPad())
  LandingPads.push_back(&MBB);

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

277–278

Ok, but if the purpose is to prevent predecessor from cycle to be considered non-EH. How about landingpad->A->B->A, where there's no self edge to A, but B would prevent A from being marked EH? The need for self cycle special handling looks fishy.. We either handle all cycles, or don't..

[modimo]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

277–278

https://reviews.llvm.org/D131824 handles landingpad->A->B->A by using a lattice and iterating until no change occurs which handles cycles. Even has a test case to make sure it's done right :)

[hoy]

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

277–278

Yeah, I just remembered the issue was also raised up in https://reviews.llvm.org/D131824 so we ended up with a more complicated implementation. Sounds like I should reuse that code here. Then making a shared version makes sense.

[modimo]

In D142747#4087069, @wenlei wrote:

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

That diff also used EHPad as seeds for BFS, I thought we only need LandingPads as seeds? Though I think for simple algorithm, having MIR and IR implementation separated is probably fine. I also don't know where to put a merged version..

if (MBB.isEHPad())
  LandingPads.push_back(&MBB);

LandingPads are the only thing that exists for x86_64 Linux while catchswitch, catchpad, and cleanuppad are all for Windows EH (https://llvm.org/docs/ExceptionHandling.html#new-exception-handling-instructions). Without proper testing on Windows I'd advocate for keeping it to LandingPads only.

[hoy]

In D142747#4087088, @modimo wrote:

In D142747#4087069, @wenlei wrote:

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

That diff also used EHPad as seeds for BFS, I thought we only need LandingPads as seeds? Though I think for simple algorithm, having MIR and IR implementation separated is probably fine. I also don't know where to put a merged version..

if (MBB.isEHPad())
  LandingPads.push_back(&MBB);

LandingPads are the only thing that exists for x86_64 Linux while catchswitch, catchpad, and cleanuppad are all for Windows EH (https://llvm.org/docs/ExceptionHandling.html#new-exception-handling-instructions). Without proper testing on Windows I'd advocate for keeping it to LandingPads only.

MIR only has landing pads right? The windows EH instructions seems on IR only.

[modimo]

In D142747#4087088, @modimo wrote:

In D142747#4087069, @wenlei wrote:

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

That diff also used EHPad as seeds for BFS, I thought we only need LandingPads as seeds? Though I think for simple algorithm, having MIR and IR implementation separated is probably fine. I also don't know where to put a merged version..

if (MBB.isEHPad())
  LandingPads.push_back(&MBB);

LandingPads are the only thing that exists for x86_64 Linux while catchswitch, catchpad, and cleanuppad are all for Windows EH (https://llvm.org/docs/ExceptionHandling.html#new-exception-handling-instructions). Without proper testing on Windows I'd advocate for keeping it to LandingPads only.

For where to put it, right now I'd say there's not a good place for it and we may want to create a new file. Clang has llvm-project/clang/lib/CodeGen/CGException.cpp for all of it's EH support structure but EH on LLVM is very haphazard (I suspect because outside of correctness there was not much optimization thought put into it).

I would support adding a llvm/lib/Analysis/Exceptions.cpp (or whatever name makes sense) like llvm/lib/Analysis/EHPersonalities.cpp exists. Otherwise, if we don't want to add another file I would place it in Function.h/cpp since technically we can consider this calculating a property of the function.

[hoy]

In D142747#4087112, @modimo wrote:

In D142747#4087088, @modimo wrote:

In D142747#4087069, @wenlei wrote:

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

That diff also used EHPad as seeds for BFS, I thought we only need LandingPads as seeds? Though I think for simple algorithm, having MIR and IR implementation separated is probably fine. I also don't know where to put a merged version..

if (MBB.isEHPad())
  LandingPads.push_back(&MBB);

LandingPads are the only thing that exists for x86_64 Linux while catchswitch, catchpad, and cleanuppad are all for Windows EH (https://llvm.org/docs/ExceptionHandling.html#new-exception-handling-instructions). Without proper testing on Windows I'd advocate for keeping it to LandingPads only.

For where to put it, right now I'd say there's not a good place for it and we may want to create a new file. Clang has llvm-project/clang/lib/CodeGen/CGException.cpp for all of it's EH support structure but EH on LLVM is very haphazard (I suspect because outside of correctness there was not much optimization thought put into it).

I would support adding a llvm/lib/Analysis/Exceptions.cpp (or whatever name makes sense) like llvm/lib/Analysis/EHPersonalities.cpp exists. Otherwise, if we don't want to add another file I would place it in Function.h/cpp since technically we can consider this calculating a property of the function.

I'm thinking about llvm/include/llvm/Analysis/CFG.h as a place to put the templated code. WDTY?

[wenlei]

In D142747#4087114, @hoy wrote:

In D142747#4087112, @modimo wrote:

In D142747#4087088, @modimo wrote:

In D142747#4087069, @wenlei wrote:

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

That diff also used EHPad as seeds for BFS, I thought we only need LandingPads as seeds? Though I think for simple algorithm, having MIR and IR implementation separated is probably fine. I also don't know where to put a merged version..

if (MBB.isEHPad())
  LandingPads.push_back(&MBB);

LandingPads are the only thing that exists for x86_64 Linux while catchswitch, catchpad, and cleanuppad are all for Windows EH (https://llvm.org/docs/ExceptionHandling.html#new-exception-handling-instructions). Without proper testing on Windows I'd advocate for keeping it to LandingPads only.

For where to put it, right now I'd say there's not a good place for it and we may want to create a new file. Clang has llvm-project/clang/lib/CodeGen/CGException.cpp for all of it's EH support structure but EH on LLVM is very haphazard (I suspect because outside of correctness there was not much optimization thought put into it).

I would support adding a llvm/lib/Analysis/Exceptions.cpp (or whatever name makes sense) like llvm/lib/Analysis/EHPersonalities.cpp exists. Otherwise, if we don't want to add another file I would place it in Function.h/cpp since technically we can consider this calculating a property of the function.

I'm thinking about llvm/include/llvm/Analysis/CFG.h as a place to put the templated code. WDTY?

No, clearly CFG.h operates on a different abstraction level that is unaware of high level concepts like EH. I think we should keep it that way..

I would support adding a llvm/lib/Analysis/Exceptions.cpp (or whatever name makes sense) like llvm/lib/Analysis/EHPersonalities.cpp exists. Otherwise, if we don't want to add another file I would place it in Function.h/cpp since technically we can consider this calculating a property of the function.

I'm not sure this is useful enough to be part of core IR constructs like function/basicblock. Adding its own file seems like a better place than any of the existing ones, though just for one not commonly used function.. That's why I say I don't know :)

[modimo]

In D142747#4087114, @hoy wrote:

I'm thinking about llvm/include/llvm/Analysis/CFG.h as a place to put the templated code. WDTY?

Unfortunately (or really fortunately cause it's doing the right thing) llvm/include/llvm/Analysis/CFG.h is a very clean file and I think this code would look a bit out of place. I would fully support a new file being created since it's really not a big deal (check out how small llvm/lib/Analysis/EHPersonalities.cpp is) and it'll likely be useful to have in the future as well.

[modimo]

In D142747#4087141, @wenlei wrote:

In D142747#4087114, @hoy wrote:

In D142747#4087112, @modimo wrote:

In D142747#4087088, @modimo wrote:

In D142747#4087069, @wenlei wrote:

In D142747#4086978, @modimo wrote:

We've got the same EH-ness propagation code in MFS already: https://reviews.llvm.org/D131824. Consider merging the code?

That diff also used EHPad as seeds for BFS, I thought we only need LandingPads as seeds? Though I think for simple algorithm, having MIR and IR implementation separated is probably fine. I also don't know where to put a merged version..

if (MBB.isEHPad())
  LandingPads.push_back(&MBB);

LandingPads are the only thing that exists for x86_64 Linux while catchswitch, catchpad, and cleanuppad are all for Windows EH (https://llvm.org/docs/ExceptionHandling.html#new-exception-handling-instructions). Without proper testing on Windows I'd advocate for keeping it to LandingPads only.

For where to put it, right now I'd say there's not a good place for it and we may want to create a new file. Clang has llvm-project/clang/lib/CodeGen/CGException.cpp for all of it's EH support structure but EH on LLVM is very haphazard (I suspect because outside of correctness there was not much optimization thought put into it).

I would support adding a llvm/lib/Analysis/Exceptions.cpp (or whatever name makes sense) like llvm/lib/Analysis/EHPersonalities.cpp exists. Otherwise, if we don't want to add another file I would place it in Function.h/cpp since technically we can consider this calculating a property of the function.

I'm thinking about llvm/include/llvm/Analysis/CFG.h as a place to put the templated code. WDTY?

No, clearly CFG.h operates on a different abstraction level that is unaware of high level concepts like EH. I think we should keep it that way..

I would support adding a llvm/lib/Analysis/Exceptions.cpp (or whatever name makes sense) like llvm/lib/Analysis/EHPersonalities.cpp exists. Otherwise, if we don't want to add another file I would place it in Function.h/cpp since technically we can consider this calculating a property of the function.

I'm not sure this is useful enough to be part of core IR constructs like function/basicblock. Adding its own file seems like a better place than any of the existing ones, though just for one not commonly used function.. That's why I say I don't know :)

I'm not confident on what exactly is the right thing to do here either. Looking through the code base we've got other code that could fit better in a llvm/lib/Analysis/Exceptions.cpp like https://github.com/llvm/llvm-project/blame/main/llvm/lib/CodeGen/Analysis.cpp#L729. Looks like Analysis.cpp is a dumping ground for functions that don't fit elsewhere which is another ref-count to me that a dedicated file for EH makes sense.

[hoy]

Addressing feedbacks.

[hoy]

Updating D142747: [Pseudo Probe] Do not instrument EH blocks.

[wenlei]

llvm/include/llvm/Analysis/EHUtils.h

18

1. Is the need for AccessorTraits because of the different API between MBB (member predecessors()) vs BB (standalone predecessors())?

2. If we have to use AccessorTraits, can we avoid exposing it as template type at the top level API (computeEHOnlyBlocks)? I think we should be able to select the right traits based on BlockT.

3. Since we only need successor/predecessor, I'd suggest we decouple this from afdo_detail::IRTraits. That is, we define two small traits here for both MBB and BB.

llvm/lib/CodeGen/MachineFunctionSplitter.cpp

89

As mentioned above, this better be moved into EHUtils.h.

[hoy]

llvm/include/llvm/Analysis/EHUtils.h

18

Is the need for AccessorTraits because of the different API between MBB (member predecessors()) vs BB (standalone predecessors())?

Yes. I don't see code shared between BB and MBB often. I guess that's one reason preventing it from being shared easily.

If we have to use AccessorTraits, can we avoid exposing it as template type at the top level API (computeEHOnlyBlocks)? I think we should be able to select the right traits based on BlockT

Can you elaborate a little more? Iike based on typeid check?

Since we only need successor/predecessor, I'd suggest we decouple this from afdo_detail::IRTraits. That is, we define two small traits here for both MBB and BB.

Makes sense.

llvm/lib/CodeGen/MachineFunctionSplitter.cpp

89

I thought about that, but I ended up defining them here because otherwise it'll introduce a cyclic dependency between Analysis and Codegen.

[wenlei]

llvm/include/llvm/Analysis/EHUtils.h

18

Can you elaborate a little more? Iike based on typeid check?

I haven't looked at how. But I suppose with some investigation we should be able to find a way to hide the traits from API. We have precedence - there's not any need for specifying the traits when instantiating a sample loader.

llvm/lib/CodeGen/MachineFunctionSplitter.cpp

89

Ok, I see. I guess that's why IRTraits<MachineBasicBlock> for sample loader is also in codegen.

This is not ideal - the traits is supposed to be part of the infra/framework, but now you're defining it at the client side. This is also worse than the MIRSampleProfile case because one can argue it's still part of framework there.

[hoy]

llvm/include/llvm/Analysis/EHUtils.h

18

Actually just figured out that there are predecessors/successors API defined for MBB in MachineSSAContext.h. We can use that and AccessorTraits will not be needed at all.

[hoy]

Updating D142747: [Pseudo Probe] Do not instrument EH blocks.

[wenlei]

lgtm, thanks.

llvm/include/llvm/Analysis/EHUtils.h

18

Great - that's why I asked the first question. :)

[hoy]

llvm/include/llvm/Analysis/EHUtils.h

18

BTW, I'm thinking about moving the predecessors/successors definition from MachineSSAContext.h to MachineBasicBlocks.h since they could be useful in general for code sharing between IR and MIR. WDYT?

[wenlei]

llvm/include/llvm/Analysis/EHUtils.h

18

That makes sense. (though I just realized the counterpart for IR is in CFG.h, instead of BasicBlock.h)

[hoy]

moving the predecessors/successors definition from MachineSSAContext.h to MachineBasicBlocks.h

llvm/include/llvm/Analysis/EHUtils.h

18

Yeah, I didn't find the counterpart of CFG.h in Codegen.

[hoy]

Removing unnecessary header inclusions.

llvm/include/llvm/Analysis/EHUtils.h

+//===-- Analysis/EHUtils.h - Exception handling related utils --*-//C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+
+#ifndef LLVM_ANALYSIS_EHUTILS_H
+#define LLVM_ANALYSIS_EHUTILS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+
+namespace llvm {
+
+/// Compute a list of blocks that are only reachable via EH paths.
+template <typename FunctionT, typename BlockT>
+static void computeEHOnlyBlocks(FunctionT &F, DenseSet<BlockT *> &EHBlocks) {
+  // A block can be unknown if its not reachable from anywhere
+  // EH if its only reachable from start blocks via some path through EH pads
+  // NonEH if it's reachable from Non EH blocks as well.
+  enum Status { Unknown = 0, EH = 1, NonEH = 2 };
+  DenseSet<BlockT *> WorkList;
+  DenseMap<BlockT *, Status> Statuses;
+
+  auto GetStatus = [&](BlockT *BB) {
+    if (Statuses.find(BB) != Statuses.end())
+      return Statuses[BB];
+    else
+      return Unknown;
+  };
+
+  auto CheckPredecessors = [&](BlockT *BB, Status Stat) {
+    for (auto *PredBB : predecessors(BB)) {
+      Status PredStatus = GetStatus(PredBB);
+      // If status of predecessor block has gone above current block
+      // we update current blocks status.
+      if (PredStatus > Stat)
+        Stat = PredStatus;
+    }
+    return Stat;
+  };
+
+  auto AddSuccesors = [&](BlockT *BB) {
+    for (auto *SuccBB : successors(BB)) {
+      if (!SuccBB->isEHPad())
+        WorkList.insert(SuccBB);
+    }
+  };
+
+  // Insert the successors of start block and landing pads successor.
+  BlockT *StartBlock = &F.front();
+  Statuses[StartBlock] = NonEH;
+  AddSuccesors(StartBlock);
+
+  for (auto &BB : F) {
+    if (BB.isEHPad()) {
+      AddSuccesors(&BB);
+      Statuses[&BB] = EH;
+    }
+  }
+
+  // Worklist iterative algorithm.
+  while (!WorkList.empty()) {
+    auto *BB = *WorkList.begin();
+    WorkList.erase(BB);
+
+    Status OldStatus = GetStatus(BB);
+
+    // Check on predecessors and check for
+    // Status update.
+    Status NewStatus = CheckPredecessors(BB, OldStatus);
+
+    // Did the block status change?
+    bool Changed = OldStatus != NewStatus;
+    if (Changed) {
+      AddSuccesors(BB);
+      Statuses[BB] = NewStatus;
+    }
+  }
+
+  EHBlocks.clear();
+  for (auto Entry : Statuses) {
+    if (Entry.second == EH)
+      EHBlocks.insert(Entry.first);
+  }
+}
+} // namespace llvm
+
+#endif

llvm/include/llvm/CodeGen/MachineBasicBlock.h

template <> struct GraphTraits<Inverse<const MachineBasicBlock*>> {
   static NodeRef getEntryNode(Inverse<const MachineBasicBlock *> G) {
     return G.Graph;
   }
 
   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
+// These accessors are handy for sharing templated code between IR and MIR.
+inline auto successors(const MachineBasicBlock *BB) { return BB->successors(); }
+inline auto predecessors(const MachineBasicBlock *BB) {
+  return BB->predecessors();
+}
+
 /// MachineInstrSpan provides an interface to get an iteration range
 /// containing the instruction it was initialized with, along with all
 /// those instructions inserted prior to or following that instruction
 /// at some point after the MachineInstrSpan is constructed.
 class MachineInstrSpan {
   MachineBasicBlock &MBB;
   MachineBasicBlock::iterator I, B, E;
 

llvm/include/llvm/CodeGen/MachineSSAContext.h

 namespace llvm {
 class MachineRegisterInfo;
 class MachineInstr;
 class MachineFunction;
 class Register;
 template <typename _FunctionT> class GenericSSAContext;
 template <typename, bool> class DominatorTreeBase;
 
-inline auto successors(const MachineBasicBlock *BB) { return BB->successors(); }
-inline auto predecessors(const MachineBasicBlock *BB) {
-  return BB->predecessors();
-}
 inline unsigned succ_size(const MachineBasicBlock *BB) {
   return BB->succ_size();
 }
 inline unsigned pred_size(const MachineBasicBlock *BB) {
   return BB->pred_size();
 }
 inline auto instrs(const MachineBasicBlock &BB) { return BB.instrs(); }
 

llvm/lib/CodeGen/MachineFunctionSplitter.cpp

 // the overall changes to the binary size are negligible; only a small number of
 // additional jump instructions may be introduced.
 //
 // For the original RFC of this pass please see
 // https://groups.google.com/d/msg/llvm-dev/RUegaMg-iqc/wFAVxa6fCgAJ
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/EHUtils.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/CodeGen/BasicBlockSectionUtils.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/Passes.h"
public:
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction &F) override;
 };
 } // end anonymous namespace
 
 /// setDescendantEHBlocksCold - This splits all EH pads and blocks reachable
-/// only by EH pad as cold. This will help mark EH pads statically cold instead
-/// of relying on profile data.
-static void
-setDescendantEHBlocksCold(SmallVectorImpl<MachineBasicBlock *> &EHBlocks,
-                          MachineFunction &MF) {
-  MachineBasicBlock *StartBlock = &MF.front();
-  // A block can be unknown if its not reachable from anywhere
-  // EH if its only reachable from start blocks via some path through EH pads
-  // NonEH if it's reachable from Non EH blocks as well.
-  enum Status { Unknown = 0, EH = 1, NonEH = 2 };
-  DenseSet<MachineBasicBlock *> WorkList;
-  DenseMap<MachineBasicBlock *, Status> Statuses;
-
-  auto getStatus = [&](MachineBasicBlock *MBB) {
-    if (Statuses.find(MBB) != Statuses.end())
-      return Statuses[MBB];
-    else
-      return Unknown;
-  };
-
-  auto checkPredecessors = [&](MachineBasicBlock *MBB, Status Stat) {
-    for (auto *PredMBB : MBB->predecessors()) {
-      Status PredStatus = getStatus(PredMBB);
-      // If status of predecessor block has gone above current block
-      // we update current blocks status.
-      if (PredStatus > Stat)
-        Stat = PredStatus;
-    }
-    return Stat;
-  };
-
-  auto addSuccesors = [&](MachineBasicBlock *MBB) {
-    for (auto *SuccMBB : MBB->successors()) {
-      if (!SuccMBB->isEHPad())
-        WorkList.insert(SuccMBB);
-    }
-  };
-
-  // Insert the successors of start block
-  // and landing pads successor.
-  Statuses[StartBlock] = NonEH;
-  addSuccesors(StartBlock);
-  for (auto *LP : EHBlocks) {
-    addSuccesors(LP);
-    Statuses[LP] = EH;
-  }
-
-  // Worklist iterative algorithm.
-  while (!WorkList.empty()) {
-    auto *MBB = *WorkList.begin();
-    WorkList.erase(MBB);
-
-    Status OldStatus = getStatus(MBB);
-
-    // Check on predecessors and check for
-    // Status update.
-    Status NewStatus = checkPredecessors(MBB, OldStatus);
-
-    // Did the block status change?
-    bool changed = OldStatus != NewStatus;
-    if (changed) {
-      addSuccesors(MBB);
-      Statuses[MBB] = NewStatus;
-    }
-  }
-
-  for (auto Entry : Statuses) {
-    if (Entry.second == EH)
-      Entry.first->setSectionID(MBBSectionID::ColdSectionID);
+/// only by EH pad as cold. This will help mark EH pads statically cold
+/// instead of relying on profile data.
+static void setDescendantEHBlocksCold(MachineFunction &MF) {
+  DenseSet<MachineBasicBlock *> EHBlocks;
+  computeEHOnlyBlocks(MF, EHBlocks);
+  for (auto Block : EHBlocks) {
+    Block->setSectionID(MBBSectionID::ColdSectionID);
   }
 }
 
 static bool isColdBlock(const MachineBasicBlock &MBB,
                         const MachineBlockFrequencyInfo *MBFI,
                         ProfileSummaryInfo *PSI) {
   std::optional<uint64_t> Count = MBFI->getBlockProfileCount(&MBB);
   if (!Count)
for (auto &MBB : MF) {
     if (MBB.isEHPad())
       LandingPads.push_back(&MBB);
     else if (UseProfileData && isColdBlock(MBB, MBFI, PSI) && !SplitAllEHCode)
       MBB.setSectionID(MBBSectionID::ColdSectionID);
   }
 
   // Split all EH code and it's descendant statically by default.
   if (SplitAllEHCode)
-    setDescendantEHBlocksCold(LandingPads, MF);
+    setDescendantEHBlocksCold(MF);
   // We only split out eh pads if all of them are cold.
   else {
     bool HasHotLandingPads = false;
     for (const MachineBasicBlock *LP : LandingPads) {
       if (!isColdBlock(*LP, MBFI, PSI))
         HasHotLandingPads = true;
     }
     if (!HasHotLandingPads) {

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

 //===- SampleProfileProbe.cpp - Pseudo probe Instrumentation -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the SampleProfileProber transformation.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/SampleProfileProbe.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/EHUtils.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/PseudoProbe.h"
 #include "llvm/ProfileData/SampleProf.h"
 #include "llvm/Support/CRC.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <unordered_set>
 #include <vector>
 
 using namespace llvm;
-#define DEBUG_TYPE "sample-profile-probe"
+#define DEBUG_TYPE "pseudo-probe"
 
 STATISTIC(ArtificialDbgLine,
           "Number of probes that have an artificial debug line");
 
 static cl::opt<bool>
     VerifyPseudoProbe("verify-pseudo-probe", cl::init(false), cl::Hidden,
                       cl::desc("Do pseudo probe verification"));
 
void SampleProfileProber::computeCFGHash() {
   LLVM_DEBUG(dbgs() << "\nFunction Hash Computation for " << F->getName()
                     << ":\n"
                     << " CRC = " << JC.getCRC() << ", Edges = "
                     << Indexes.size() << ", ICSites = " << CallProbeIds.size()
                     << ", Hash = " << FunctionHash << "\n");
 }
 
 void SampleProfileProber::computeProbeIdForBlocks() {
+  DenseSet<BasicBlock *> KnownColdBlocks;
+  computeEHOnlyBlocks(*F, KnownColdBlocks);
+  // Insert pseudo probe to non-cold blocks only. This will reduce IR size as
+  // well as the binary size while retaining the profile quality.
   for (auto &BB : *F) {
-    BlockProbeIds[&BB] = ++LastProbeId;
+    ++LastProbeId;
+    if (!KnownColdBlocks.contains(&BB))
+      BlockProbeIds[&BB] = LastProbeId;
   }
 }
 
 void SampleProfileProber::computeProbeIdForCallsites() {
   for (auto &BB : *F) {
     for (auto &I : BB) {
       if (!isa<CallBase>(I))
         continue;
       if (isa<IntrinsicInst>(&I))
         continue;
       CallProbeIds[&I] = ++LastProbeId;
     }
   }
 }
 
 uint32_t SampleProfileProber::getBlockId(const BasicBlock *BB) const {
   auto I = BlockProbeIds.find(const_cast<BasicBlock *>(BB));
   return I == BlockProbeIds.end() ? 0 : I->second;
 }
 
 uint32_t SampleProfileProber::getCallsiteId(const Instruction *Call) const {
   auto Iter = CallProbeIds.find(const_cast<Instruction *>(Call));

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

+; REQUIRES: x86_64-linux
+; RUN: opt < %s -passes=pseudo-probe -function-sections -S -o - | FileCheck %s
+
+;; Check the generation of pseudoprobe intrinsic call for non-EH blocks only.
+
+declare i32 @__gxx_personality_v0(...)
+declare i32 @llvm.eh.typeid.for(ptr) nounwind
+declare ptr @__cxa_begin_catch(ptr)
+declare void @__cxa_end_catch()
+declare void @bar()
+
+@_ZTIi = external constant ptr
+
+define void @foo() uwtable ssp personality ptr @__gxx_personality_v0 {
+entry:
+; CHECK: call void @llvm.pseudoprobe
+  invoke void @bar()
+          to label %ret unwind label %lpad
+
+ret:
+; CHECK: call void @llvm.pseudoprobe
+  ret void
+
+lpad:                                             ; preds = %entry
+; CHECK-NOT: call void @llvm.pseudoprobe
+  %exn = landingpad {ptr, i32}
+            catch ptr @_ZTIi
+  %eh.exc = extractvalue { ptr, i32 } %exn, 0
+  %eh.selector = extractvalue { ptr, i32 } %exn, 1
+  %0 = call i32 @llvm.eh.typeid.for(ptr @_ZTIi) nounwind
+  %1 = icmp eq i32 %eh.selector, %0
+  br i1 %1, label %catch, label %eh.resume
+
+catch:
+; CHECK-NOT: call void @llvm.pseudoprobe
+  %ignored = call ptr @__cxa_begin_catch(ptr %eh.exc) nounwind
+  call void @__cxa_end_catch() nounwind
+  br label %ret
+
+eh.resume:
+; CHECK-NOT: call void @llvm.pseudoprobe
+  resume { ptr, i32 } %exn
+}