ast_cfg: Blocks generated in the wrong order

[Matt Giuca]

When basic blocks are generated, they are generated in a very strange order, due to the algorithm for compound statements:

1. Generate an exit block,
2. Generate the blocks inside the compound statement,
3. Set the branch from the final block to the exit block.

This means you get output where, for example, the entry is always block #0 and the exit is always block #1. This doesn't affect the program, but makes it hard to read when you read the assembly code, and also may hamper optimisation (depending on the back-end).

[Matt Giuca (mgiuca)]

To fix this, change the internal type of bbref from int to list(int), which allows block numbers to be represented by an arbitrarily-long sequence of numbers. This allows blocks to be inserted between existing blocks. For example, if block 3 and 4 exist, a new block can be inserted after block 3, which will be known as block 3.1 (represented as [3, 1]). If blocks 3.1 and 3.2 exist, a new block can be inserted after block 3.1, which will be known as block 3.1.1.

Creating a block no longer places it at the end of the CFG. Instead, it requires a block be specified, and the block will be placed after the given block, in the code. This placement has no effect on the execution order of the blocks (as Mars bytecode does not allow fallthrough). It merely affects the printout order (and possibly the order of code generation, so it may have a performance impact in some backends of adding/removing unconditional branches).

A fold over the CFG would traverse the blocks in lexicographical order (3, 3.1, 4).

Once this technology is in place, blocks should be generated in order such that the printout order is roughly the same as the order the blocks were in in the source code. This would make the code much easier to read.

A CFG operation, "flatten", can be written, which lexicographically sorts the blocks, then re-numbers them sequentially, so each block has just a single integer ID. This would be ideally performed after the block is generated, so the user doesn't see the strangely-numbered blocks (although the numbers would imply some kind of code structure).

[Matt Giuca (mgiuca)]

A major problem with this approach is that we are currently using the current block ID to label SSA variables. With this approach, we can't name them the correct name.

(Internally, cfg.ref_id is now meaningless and all dependencies on it -- now solely in ast_cfg -- need to be removed.)

We'll probably have to change ast_cfg so it generates names unique to the function, not the block, and don't involve the block ID in naming the variable at all.

[Matt Giuca (mgiuca)]

In the end, we didn't use the complex numbering scheme. It was fixed with the following approach:
- Blocks now have an optional number, separate from the block ID.
- When creating a block, it is unnumbered.
- Blocks are given a number in the same order as they appear in the source code, so that the block numbers correspond to source code order.
- Folding over a CFG does so in block number order, not block ref order.
We now number and print blocks in the correct order, with the exception of switch statements. Switch statements generate the case bodies first, then the unpacking blocks -- this is fairly difficult to fix and considered acceptable.
Fixed in trunk r1247.