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

[Sanjoy Das via llvm-dev]

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.

Another example is JumpThreading:

// If the terminator is branching on an undef, we can pick any of the
// successors to branch to.  Let GetBestDestForJumpOnUndef decide.
if (isa<UndefValue>(Condition)) {
  unsigned BestSucc = GetBestDestForJumpOnUndef(BB);

  // Fold the branch/switch.
  TerminatorInst *BBTerm = BB->getTerminator();
  for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
    if (i == BestSucc) continue;
    BBTerm->getSuccessor(i)->removePredecessor(BB, true);
  }
  // ..
}

where we'll have to worry about if BestSucc'th successor is the same
as any other successor or not with your representation change.

I didn't look beyond these two.

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

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

-- Sanjoy