The new CFG nodes store four sets - the predecessors and successors that are intra-procedural and inter-procedural (predIntra, predInter, succIntra, succInter). There are a couple points of redundancy here:
For nodes which are non-jumps (i.e. statements in a block), all incoming and outgoing edges are going to be of type RegularEdge. Currently regular edges are stored in both the intra- and inter- procedural edge sets - we are thus storing the same edge in two different sets, when we only ever expect to have one edge for this type of node. This choice to store regular edges in both sets was done to simplify the process of differentiating between the intra-/inter-procedural CFG, and is particularly useful for jumps. However, given the majority of nodes are statements which will not require this distinction, we can reduce the amount of storage required by optimising them away. The exception to this would be the statement at the start of a block, and the statement immediately preceding the jump(s) in a block, as they may have different types of incoming / outgoing edges, thus requiring the distinction to be made. There are a couple ways to optimise - we could switch to having a single set for edges and filtering upon call to succ and pred (for reasons detailed in the comment on CfgNode this was decided against in the original design). We could also introduce a separate set for storing regular edges specifically, though this similarly comes at a computation cost of having to union two sets at each call of succ/pred. It would also be possible to refactor the CfgNode hierarchy to introduce new types and such, though this was decided against in the CFG restructure to maintain alignment with TIP.
There are currently three accessors - succ, succConds and succEdges (and the equivalent for pred). This was done so that the original API (succ returning a set of nodes) would be maintained such that the analyses had to be modified minimally to compile. However, it is likely to be simpler and more complete if these were reduced to a single succ / pred which returns the relevant edges, as edges store all the information encapsulated by the three accessors (destination/originating nodes and associated edge condition). Analyses can then choose to discard what they wish in their transfer functions. This would require a small refactor of all analyses/solvers, and the CFG.
utting
commented
1 year ago
The new CFG nodes store four sets - the predecessors and successors that are intra-procedural and inter-procedural (
predIntra,predInter,succIntra,succInter). There are a couple points of redundancy here:RegularEdge. Currently regular edges are stored in both the intra- and inter- procedural edge sets - we are thus storing the same edge in two different sets, when we only ever expect to have one edge for this type of node. This choice to store regular edges in both sets was done to simplify the process of differentiating between the intra-/inter-procedural CFG, and is particularly useful for jumps. However, given the majority of nodes are statements which will not require this distinction, we can reduce the amount of storage required by optimising them away. The exception to this would be the statement at the start of a block, and the statement immediately preceding the jump(s) in a block, as they may have different types of incoming / outgoing edges, thus requiring the distinction to be made. There are a couple ways to optimise - we could switch to having a single set for edges and filtering upon call tosuccandpred(for reasons detailed in the comment onCfgNodethis was decided against in the original design). We could also introduce a separate set for storing regular edges specifically, though this similarly comes at a computation cost of having to union two sets at each call ofsucc/pred. It would also be possible to refactor theCfgNodehierarchy to introduce new types and such, though this was decided against in the CFG restructure to maintain alignment with TIP.succ,succCondsandsuccEdges(and the equivalent forpred). This was done so that the original API (succreturning a set of nodes) would be maintained such that the analyses had to be modified minimally to compile. However, it is likely to be simpler and more complete if these were reduced to a singlesucc/predwhich returns the relevant edges, as edges store all the information encapsulated by the three accessors (destination/originating nodes and associated edge condition). Analyses can then choose to discard what they wish in theirtransferfunctions. This would require a small refactor of all analyses/solvers, and the CFG.