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

[Chandler Carruth via llvm-dev]

On Mon, May 1, 2017 at 11:34 PM Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:

> Hi,
>
> On Mon, May 1, 2017 at 10:18 AM, Chandler Carruth <chandlerc at google.com>
> wrote:
> >> Also, IIUC, today deleting an edge from A to B only requires
> >> removeIncomingValue(A) on B's PHI nodes, but after this change you'll
> >> have to check if you're deleting the last edge or not.
> >
> > Are there many places where this is a feature rather than a bug though?
> >
> > I didn't do a survey of every caller of removeIncomingValue, but the 4
> or 5
> > I looked at were all inside of a loop already. Which actually means they
> > would get more efficient with this change, if in some cases needing to
> keep
> > a set around.
> >
> > This doesn't seem too bad to me, but again, maybe I'm looking at the
> wrong
> > bits of code. Is there specific code you have in mind that wants to
> remove
> > one edge (but not one predecessor block)?
>
> I think most calls to BasicBlock::removePredecessor would need
> auditing.  For instance, in llvm::ConstantFoldTerminator when we
> transform:
>
> BB:
>   br true, A, B
>
> to
>
> BB:
>   br A
>
> then we only need to call B->removePredecessor(BB) which, in turn,
> only needs to PhiInB->removeIncomingValue(BB).  With your
> representation we'll have to worry if A == B.
>

I guess I expect that after B->removePredecessor(BB), BB is *not* a
predecessor any more.

I guess you're saying that a 'predecessor' is really an 'edge'. Ok, if
confusing to me.

Still, wouldn't we just need to audit the *implementation* of
removePredecessor? It should hide all of this. My real point was that
directly manipulating the PHI node seems to be rare.

>> Can (2), (3) and (4) be fixed by changing the API instead of the
> >> deeper IR change you're proposing?
> >
> > Maybe, but I don't see easy ways. Ideas?
>
> For (2), will it help if there was a setIncomingValueForBlock(BB, V)
> that DTRT with setting (all) the incoming value(s) for BB to V?
>
> For (4) perhaps we could add a removeAllIncomingValuesForBlock helper?
>

These, IMO, turn the PHI incoming values into an inefficient set. ;] We'll
still be reasoning about whether we're decreasing the count of edges to
zero or not, but we'll be storing an incoming value and a block for each
edge instead of just counting the edges that are already there.

Somewhat worse, this duplication is magnified by the number of PHI nodes.


>
> I'm not sure what exactly you meant by (3).
>

If I want to change the incoming value for one *edge*, but not for others,
I find it confusing that I just find any old incoming value for that edge
and remove it. It just seems odd that we keep N copies, but they don't have
any semantic beyond the count of them being N. We never check which edge we
flow in through to pick which of the N copies to use because we insist that
they're all the same.

Anyways, this isn't causing any immediate pain, I just wanted to understand
why we're using what seems like a very confusing representation to me.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170502/28c2ad77/attachment.html>