[llvm-dev] RFC: Stop using redundant PHI node entries for multi-edge predecessors

[Daniel Berlin via llvm-dev]

On Tue, May 2, 2017 at 5:36 AM, Evgeny Astigeevich <
Evgeny.Astigeevich at arm.com> wrote:

> Hi,
>
> I have got experience of low-level manipulations of Phi-nodes whilst I was
> implementing an aggressive jump threading optimization for switches.
>

And i've done it a lot in GVN and NewGVN


> Chandler's proposal will simplify code.

With no offense to him, i strongly doubt this :)


>
>
Cases I had:
>
> 1. A->B->C, A has multi-edges to B. A is redirected to C.
>
> I had to write the code something like this:
>
> int NumEdgesToB = changeteTerminatorTarget(A->getTerminator(), B, C);
> for (phi: all Phi-nodes in C) {
>    V = get incoming value to C from B
>    for (int i = 0; i < NumEdgesToB; ++i) {
>        phi->addIncoming(V, A);
>    }
> }
>

Yup.


>
> I also had to update phi-nodes in B like this:
>
>    for (int i = 0; i < NumEdgesToB; ++i) {
>        PhiInB-> removeIncomingValue (B, DontDeletePHIIfEmpty);
>    }
>
> Yup

This seems perfectly normal to me, and you would need it regardless of what
happens to switch statements :)

br i1 undef, bb2, bb2
etc



> 2.  I needed to analyze all values incoming to B. As there can be
> multi-edges I had to write the code something like this:
>
> SmallPtrSet<BasicBlock *, 8> SeenBlocks;
> for (unsigned I = 0, E = CurPhi->getNumIncomingValues(); I != E; ++I) {
>     if (!SeenBlocks.insert(CurPhi->getIncomingBlock(I)).second) {
>       continue;
>     }
>    ...
> }
>
> Errr, this is not safe in general
You actually *must* know whether there are single or multiple edges into a
block to know  whether it is safe to propagate a value.


> 4. In order not to deal with duplicated incoming values I had to simplify
> a phi-nodes Def-Use graph by making some copy of it and removing redundant
> incoming values.
>

I'd love to understand why.
You actually need to deal with them anyway.

The only thing chandler's representation saves is space at the cost of time.
The analysis code should generally have to do precisely the same thing it
did before.

IE given:

switch (a)
{
  case 32: br foo
  case 64: br foo

}

Right now you would end up with:

phi({a, 1}, {a, 1})


You would know that, looking at this phi, it is unsafe to propagate into
the value.

If it is was phi({a, 1}), you cannot tell this, you'd also have to "mix the
dfg and cfg" as you say, to tell that there are multiple edges.


> So in all places where we modify/access a phi-node we have to take into
> account redundant  incoming values and preserve this feature.
>
Yes, and you will still have to do much the same analysis, just you'll end
up doing it forwards from the switch, instead of also being able to do it
backwards from the phi.


>
> > > So would this lead to a case where PHI->getNumOperands() !=
> > > std::distance(pred_begin(phiblock), pred_end(phiblock))
>
> I cannot imagine when this kind of code could be needed.


As i said, you often need to know how many edges exist into a block to know
whether it is safe to propagate along a path.


> When we work with phi-nodes we almost work with DFG they are part of. The
> code you provided is an attempt of mixing DFG and CFG.


Except that PHI nodes exist precisely for this purpose?

> I don't this is good.
>

I'm going to strongly disagree.

As Chandler wrote connections among phi-node values and edges are not
> expressed in any way.
>
> ????
Sure it is.

There is *always* a correspondence between phi nodes and incoming edges.
That is why phi nodes exist.
To be able to say "when i came from this edge, i have this value".

If you mean "the operands of the switch are not uses of the phi", that's
also true in every other compiler too.

This is even solvable if you like, by a bit of indirection, so that there
is a 1:1 mapping from case successor to a unique phi operand.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170502/8a955345/attachment.html>