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

[Evgeny Astigeevich via llvm-dev]

Hi,

I have got experience of low-level manipulations of Phi-nodes whilst I was implementing an aggressive jump threading optimization for switches. 
Chandler's proposal will simplify code.

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);
   }
}

I also had to update phi-nodes in B like this:

   for (int i = 0; i < NumEdgesToB; ++i) {
       PhiInB-> removeIncomingValue (B, DontDeletePHIIfEmpty);
   }

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;
    }
   ...
}

3. I  copied A into A'. I needed correct phi-nodes in successors of A. I had to write code like this:

      int VCount = 0;
      for (unsigned Id = 0, IdE = Phi->getNumIncomingValues(); Id != IdE; ++Id) {
        if (Phi->getIncomingBlock(Id) != OriginalBlock)
          continue;
        ++VCount;
      }

      for (; VCount > 0; --VCount)
        Phi->addIncoming(V, BlockCopy);

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.

So in all places where we modify/access a phi-node we have to take into account redundant  incoming values and preserve this feature.

> > 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. 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. I don't this is good. 
As Chandler wrote connections among phi-node values and edges are not expressed in any way. 

> 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.

All cases I've seen required to add/remove all multi-edges. It's interesting to see real-life cases when not all edges are changed.

Thanks,
Evgeny Astigeevich

> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
> Sanjoy Das via llvm-dev
> Sent: Monday, May 01, 2017 5:30 PM
> To: Daniel Berlin
> Cc: llvm-dev
> Subject: Re: [llvm-dev] RFC: Stop using redundant PHI node entries for multi-
> edge predecessors
> 
> Hi,
> 
> On Mon, May 1, 2017 at 8:47 AM, Daniel Berlin via llvm-dev <llvm-
> dev at lists.llvm.org> wrote:
> >> Today, the IR requires that if you have multiple edges from A to B
> >> (typically with a switch) any phi nodes in B must have an equal
> >> number of entries for A, but that all of them must have the same value.
> >
> >> This seems rather annoying....
> >> 1) It creates multiple uses of values in A for no apparently good
> >> reason
> >> 2) It makes updating PHI nodes using sets of predecessors incredibly
> >> hard
> >> 3) There is no correspondence between the edges and the PHI node
> >> entries other than number, making most of the code that does handle
> >> this very ad-hoc "count off N repetitions of the same thing" style
> >> code, which is brittle and hard to test effectively.
> >
> > Having written this code a few times, i'd agree.
> >
> >>
> >> 4) I suspect bugs are quite common given that
> >> PHINode::removeIncomingValue accepts a basic block but only removes
> >> the first incoming value, leaving the others in place.
> >
> >> I can't see any serious use case for this symmetry either. These
> >> aren't uses (and can't be), and there doesn't seem to be any lost
> >> functionality if we only have a single
> >> entry.http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >>
> >> It also seems likely to open up more efficient in-memory
> >> representations if it is possible at some point to build maps of these
> things.
> >>
> >> Thoughts?
> >
> >
> >
> > So would this lead to a case where PHI->getNumOperands() !=
> > std::distance(pred_begin(phiblock), pred_end(phiblock))
> >
> > If so, that would seem problematic to handle as well.
> > :(
> 
> 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.
> 
> Can (2), (3) and (4) be fixed by changing the API instead of the deeper IR
> change you're proposing?
> 
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev