This is an archive of the discontinued LLVM Phabricator instance.

[BasicBlock] add new function removeEdge()
ClosedPublic

Authored by brzycki on Sep 7 2017, 9:40 AM.

Details

Summary

First let me comment by saying I'm not sure if the community desires to go in this direction. The primary reason for uploading this patch was twofold:

  1. To start a discussion about how we work with edges between blocks in an IR vs CFG manner.
  2. To archive the patch should others find the idea useful in the future.

This patch adds a new function removeEdge() as a BasicBlock primitive. It does exactly what the name implies: removes an outgoing edge from BB1 into BB2. The routine asserts if no such edge exists.

This routine started as a reaction to removePredecessor(); a call that only adjust PHIs in the successor BB. Calls to removePredecessor() quietly do nothing in cases such as the following:

BB1:

br BB2

BB2:

br BB3

BB2->removePredecessor(BB1)

This is a bit surprising until one reads the documentation/source for removePredecessor().

The removeEdge() routine alters the terminator instruction of BB1. Should we call BB1->removeEdge(BB2) the resulting IR would now look like

BB1:

unreachable

BB2:

br BB3

Dominance is preserved if a DT handle is passed in: BB1->removeEdge(BB2, DT).

This new interface gives the caller the option to think more about the CFG than the underlying IR details. This has a few complications related to it:

  1. The successors of BB1 will be altered by the call, making looping over successors different than of call sites using removePredecessor()
  2. removeEdge() does not alter uses.

Even with these drawbacks I think this alternative interface has merit: in too many locations throughout the middle end do we see special-cased code that deals with the details of the IRs many terminator instruction types. At the very least I hope this code spurs a fruitful discussion.

Diff Detail

Event Timeline

brzycki created this revision.Sep 7 2017, 9:40 AM
kuhar edited edge metadata.Sep 8 2017, 5:59 AM

This actually seems a bit orthogonal to what we wanted to do with @dberlin. The idea was to see if it is possible to always preserve dominators, and to do it completely automatically. With this high-level goal in mind, I tried to hack removePredecessor (and others) to grab DominatorTree (if available) and update it internally. That would probably also deprecate the batch updater, as every update DominatorTree update would happen in lockstep with CFG update calls. The problem was however that the existing BasicBlock API doesn't really care about CFG edges and it wasn't really possible to place the DT update calls anywhere.

It looks like this patch could be the one of the first steps towards completely automatic DominatorTree updates. Another interesting thing would be to see if it would be possible to do something equivalent for addEdge -- with these 2 pieces of API in place, it would be much easier to fuzz and benchmarks the incremental DominatorTree updater.

llvm/lib/IR/BasicBlock.cpp
324

s/removedDest/RemovedDest

348

s/removedCase/RemovedCase

351

Consider using auto here

387

s/removedHandler/RemovedHandler

390

Consider using auto here as well

brzycki updated this revision to Diff 114368.Sep 8 2017, 8:19 AM

Fixed formatting comments recommended by @kuhar .

Fixed a corner-case bug when Invoke instructions have the same Normal and Unwind destination and DT is updated.

brzycki marked 5 inline comments as done.EditedSep 8 2017, 8:26 AM

This actually seems a bit orthogonal to what we wanted to do with @dberlin. The idea was to see if it is possible to always preserve dominators, and to do it completely automatically. With this high-level goal in mind, I tried to hack removePredecessor (and others) to grab DominatorTree (if available) and update it internally. That would probably also deprecate the batch updater, as every update DominatorTree update would happen in lockstep with CFG update calls. The problem was however that the existing BasicBlock API doesn't really care about CFG edges and it wasn't really possible to place the DT update calls anywhere.

@sebpop and I tried the exact same thing early on in the D37528 JumpThreading work. We ran into the exact same problem: too many places deal with the minutiae of the IR and we found several CFG cases where dominance couldn't be easily updated. This removeEdge() patch actually came out of that work as yet another attempt to fix the problem. Unfortunately the call sites for removePredecessor() almost always use for (auto Successor: Successors(BB))... and needed more fixup to work with removeEdge().

It looks like this patch could be the one of the first steps towards completely automatic DominatorTree updates. Another interesting thing would be to see if it would be possible to do something equivalent for addEdge -- with these 2 pieces of API in place, it would be much easier to fuzz and benchmarks the incremental DominatorTree updater.

I'd be happy to help move in this direction: it would greatly simplify middle-end work for everyone if we could think about BB chains in the context of CFG nodes and edges instead of constantly programming terminator instruction edge-case logic.

llvm/lib/IR/BasicBlock.cpp
302

Fixed in rev 2, needed to check NormalDestBB != UnwindDestBB in the corner-case where Normal and Unwind are the same basic block.

brzycki marked an inline comment as done.Sep 25 2017, 8:36 AM

ping.

kuhar accepted this revision.EditedSep 25 2017, 11:53 AM

I'm fine with the patch, I think it goes into right direction with CFG-level IR manipulation.
Please wait for someone else to give you a green light on this. Maybe it would be worth to mention this as an RFC on llvm-dev?

This revision is now accepted and ready to land.Sep 25 2017, 11:53 AM

I'm fine with the patch, I think it goes into right direction with CFG-level IR manipulation.
Please wait for someone else to give you a green light on this. Maybe it would be worth to mention this as an RFC on llvm-dev?

Thanks for the review and you bring up a good point about RFC on llvm-dev. I'll make a post tomorrow morning and see where the conversation goes.

dberlin edited edge metadata.Sep 27 2017, 8:45 AM

(repeating comments i forgot to add to review)
This definitely needs an RFC.

I'll note your approach is badly O(N) in some cases.
You could try using the uses instead (they know what operand number and their uses).
I suspect that's hard to pass down everywhere in each pass.

In general If we are going to go this route, either we should: have a real CFG structure that isn't going to be O(N) to remove an edge.
or incrementally, cache data in basic blocks (successor, predecessor lists and uses) that gets invalidated, so you can find the removal points in constant time.

The latter is likely to require a lot of verification to not generate hard to track down bugs in the compiler.

(repeating comments i forgot to add to review)
This definitely needs an RFC.

Thanks for the feedback Daniel. I sent the RFC email to llvm-dev this morning.

I'll note your approach is badly O(N) in some cases.
You could try using the uses instead (they know what operand number and their uses).
I suspect that's hard to pass down everywhere in each pass.

I agree several cases are O(N) (switch, catchswitch, indirect branch). I was not aware uses contained the operand number and I do agree that would save time (and probably simplify some of the logic). One of the reasons I wrote the code this way was investigating actual pass code that changed terminator instructions. A good deal of the original idea came from the huge if()..else blocks inside Local.cpp routines. I also haven't examined the code enough to determine if requiring uses would act as a barrier to use.

In general If we are going to go this route, either we should: have a real CFG structure that isn't going to be O(N) to remove an edge.

I definitely agree that a real CFG structure is needed. Thinking about a higher-level change to the shape of the IR and then switching to the intricacies of the IR to implement it can be quite frustrating.

or incrementally, cache data in basic blocks (successor, predecessor lists and uses) that gets invalidated, so you can find the removal points in constant time.
The latter is likely to require a lot of verification to not generate hard to track down bugs in the compiler.

It would be nice to simply query a method of a BB without having to to write for (Successor: Successors())....Validating the cache would be non-trivial and I would consider it a failure if the user had to worry about the internal state (and call routines to verify/fix it at the call site).

My hope is we can start moving in a meaningful direction to reduce this problem without getting overwhelmed with the changes needed to be added. I greatly prefer incremental changes to an existing design as a method to evolve the code.

brzycki closed this revision.Feb 21 2018, 8:07 AM

This method is too expensive as it is designed today.