cfg_tabled.pl
The analyses of cfg.pl as tabled relations over IR facts, in the two styles the handoff proposed. They exist to answer PLAN's open question by measurement (tests/bench-cfg.pl, docs/m5.md); passes use cfg.pl.
| Style | Loads the facts | Relations |
|---|---|---|
| versioned facts | assert_version/2, retract_version/1 | version_live_in/3, version_live_out/3, version_dominates/3, version_idoms/2, version_frontier/3 |
| incremental tabling | incremental_load/1, incremental_update/1, incremental_clear/0 | incremental_live_in/2, incremental_live_out/2 |
Versioned facts
assert_version/2 asserts the function's edges, entry, blocks, per-block gen and kill sets and phi edge uses as facts tagged with a version V. The relations over them take V as an argument, so every version has its own tables. retract_version/1 drops a version's facts and abolishes every table.
Incremental tabling
incremental_load/1 asserts unversioned facts that are declared incremental. incremental_update/1 replaces the gen, kill and phi edge-use facts that differ from those of the new blocks, and leaves the edges as they are; the host then invalidates only the tables that depend on the changed facts. incremental_clear/0 retracts every incremental fact.
Common ground
Both styles take the gen and kill sets from cfg.pl, which computes them by a local scan of each block: tabling that would only add table overhead.
Facts are asserted and retracted here, which is the "versioned facts at pass boundaries" exception in PLAN's rules. The negations (\+ kill, \+ avoid) are called with ground arguments only, so they are sound.
SWI-Prolog has tabling built in (its library(tabling) is deprecated) and declares incremental dynamic predicates through dynamic/2.
vf_edge(From, To, V)
vf_pred(To, From, V)
vf_entry(V, Entry)
vf_block(B, V)
vf_gen(B, T, V)
vf_kill(B, T, V)
vf_euse(B, Succ, T, V): T read on edge B->Succ
Versioned facts
Assert the edges, entry, blocks, gen/kill sets and phi edge uses of the function Blocks as facts tagged V.
Retract version V's facts and abolish every table (Trealla's abolish_table/1 drops all variants of a predicate, so old tables cannot be dropped one version at a time).
Every call below is a variant of an open version_live_in(V, _, _) or version_live_out(V, _, _), so each version has two tables in all.
Temp T is live on entry to block B in version V.
Trealla 12f4cbd: a \+ or if-then-else written inline after a tabled call in a tabled clause gives wrong answers (it lets version_live_in(start, T) through for a T that start defines); the same negation in its own predicate is right. docs/m5.md has the reproduction.
Temp T is live on exit from block B in version V.
avoid(V, Avoid, B): B is reachable from the entry in version V on a path that does not pass through the label of Avoid: some(D) avoids D, and none gives plain reachability. One table per Avoid.
Pairs is the list B-Idom of the reachable blocks B of version V other than the entry and their immediate dominators, from version_dominates/3: the immediate dominator of B is the strict dominator with the most dominators of its own.
Y is in the dominance frontier of X in version V. A Y can be found once per predecessor that X dominates.
Incremental tabling
if_pred(To, From), if_gen(B, T), if_kill(B, T), if_euse(B, T)
Temp T is live on entry to block B of the loaded function.
See v_not_killed/3.
Temp T is live on exit from block B of the loaded function.
Retract every incremental fact.
Assert the incremental facts (edges, gen/kill sets, phi edge uses) of the function Blocks.
Make the gen, kill and phi edge-use facts those of Blocks: retract the facts no block has any more and assert the new ones. Edges (if_pred/2) are left as they are.
the sorted if_gen, if_kill and if_euse facts of Blocks.