Targeted Procedure In-lining

[Thomas-Malcolm]

NOTE: whether or not this development is worth completing is dependent on whether procedure in-lining will be of use to us at all. Consult Mark / Kirsten / Nick before committing any serious amount of time to this.

The broad CFG generation algorithm goes:

1. Generate intra-procedural CFG for each known procedure
2. While not at inline depth, for each leaf call node in those intra-procedural CFGs, inline that procedure.
3. At inline depth, for each leaf call node, link that (as an inter-procedural call edge) to the target's intra-procedural CFG.

This feature targets step (2). Currently the approach to in-lining is flat, in the sense we have a maximum in-line depth, and we continue to inline every leaf call node we identify until we reach that depth. One of the main problems with in-lining is that it increases space complexity exponentially, which is not fantastic. However, some optimisations can be made. Instead of blindly in-lining every function we come across, we can introduce a "smarter" approach to this which in-lines certain functions to certain depths.

There are a couple ways this could be achieved. We could request input from the user, e.g. via a config, to specify manual inline depths - though this is cumbersome, and the less input required from the user the better. Another approach is to profile certain procedures and decide how much to in-line them. For example, it is pointless to in-line a self-recursive function 5 times. We can also blacklist procedures to bar them from being in-lined, e.g., ELF internal functions such as frame_dummy. There are a number of approaches that could be taken, some with different benefits, of which Mark / Kirsten / Nick should be consulted to make a decision on what's best.