Add special BasicBlock::Entry node?

[acl-cqc]

The original call for this has largely gone, but the points/questions remain...
@cqc-alec:

Maybe this is the excuse we need to make the CFG's entry node special, exactly mirroring the exit node -- so it would not be a DFB, but just have outputs and no DFG inside it.

At the cost of introducing an extra node, if it makes the replacement API simpler I think it may be worth it. Thoughts?

@acl-cqc:

Yes, I had been wondering something similar. (Actually I'd been wishing we'd done that thing whereby Entry/Exit, and Input/Output for DFGs, were edges to/from the parent/container node, but never mind ;-) ). There are some possibilities:

• Require the entry node to have no predecessors. In which case there's no need to have any children, either (they could go outside the CFG and their outputs wired as inputs to the CFG). So...
• Add a new "Entry block" subtype (BasicBlock::Entry - we have BasicBlock::DFB and BasicBlock::Exit currently). I guess this has no inputs (implicitly these are the same as the CFG's inputs, just as the outputs of a BasicBlock::Exit are the same as the CFG's outputs), but the same predicate_variants and other_outputs as a normal DFB. [Note the Entry node could include a branch. If it doesn't branch, then really its single successor should have other predecessors, or else we could normalize by merging basic blocks.]
• Combine the proposed BasicBlock::Entry with BasicBlock::Exit into a BasicBlock::Identity and use that for both entry and exit. I guess this would have predicate_variants and other_outputs, with the idea that
  • for the entry block, the CFG inputs are equal to the Sum of the predicate_variants, plus the other outputs
  • for the exit block, the predicate_variants are the empty list (this is consistent with it having no successors) - that is, a 0-ary Sum, a type of which there are no instances. The inputs and other_outputs are then identical with the outputs of the CFG.
    The latter seems both the most sensible and also a bit weird. Hmmm, I'll keep thinking.

@cqc-alec:

I'm thinking some sort of hybrid of these ideas:

• Have distinct node types BasicBlock::{Entry,Exit,DFB}. I think using the same node type for both entry and exit is a little confusing since the conditions on them are different, although operationally they are both the identity.
• Neither Entry nor Exit has children.
• Require the Entry node to have no predecessors, no inputs and a single successor; the inputs to the DFG in that successor are just the inputs to the CFG. (We have a choice between doing the logic for the first branch in a DFB node or in a node preceding the CFG; here I choose the first option since it seems a bit less weird.)

[acl-cqc]

So merge_bbs also has some special-casing for the extra/implicit "entry edge". If we had an entry node then instead we'd special-case to avoid entry blocks, which would be a simpler special-case...

The non-uniformity though (and the raison d'être for ExitBlock) is that ExitBlock allows multiple predecessors, which is very hard to do otherwise. But having EntryBlock with multiple successors, i.e. a branch....sounds a bit mad....