4f95b98813
Closes the backlog's "which condition guards each END_PHASE". With the CFG from the previous commit this is a graph query, not new machinery. The obvious query is WRONG for this language, and I implemented it first: "one successor reaches END_PHASE and the other does not" finds 1/62/1 guards across Stage 02's three phases, and the 1s are both the same read_freg(0) < 1200 timeout -- every objective test missed. The cause is the dominant idiom: a POLL LOOP's loop-back branch also reaches the exit, one iteration later, so neither successor discriminates. The asymmetric 1/62/1 is what exposed it; a uniform number would have read as plausible. Dominance has no such blind spot: a condition dominates an exit when every path from an entry passes through it, so it is NECESSARY for the phase to end that way, and a poll loop's test dominates its own exit by construction. Iterative dominators converge in 3 passes over 15670/18739 instructions (83.6%). Result for Stage 02 -- every exit in all three phases is dominated by unit_hp_pct(TCN001, Character_Player_Test) != 0, the player's ship being alive, which falls out rather than being assumed. Beyond that, phase 1's objective exit requires hp_pct_test on ADT102, ADT107 and ADT113; phase 3's requires ADT301 and ADT302; read_freg(0) gates at 210 / 300 and times out at 1200; random(3) and random(5) dominate only the exits that pick one of several closing lines. Two of the 15 exits are reachable from NO static entry, both FORCE_END_PHASE. That agrees with the independently measured 389 unreachable routines: they are started from the trigger queue at phase+272, by data rather than code. Practical note recorded: the first dominator run was OOM-killed -- 6743 nodes each holding a Python set of up to 6743 elements. Integer bitmasks run in seconds. Not settled, and said so: dominance gives necessary, not sufficient, conditions; only Stage 02's artefact is committed; one listed condition is still an unresolved <unknown>; read_freg's units are inferred from the gate values, not read. calls, phase-ends and conditions all regenerate byte-identical.
59 lines
2.3 KiB
Python
59 lines
2.3 KiB
Python
import struct, collections, isl, isl_cfg
|
|
|
|
def edges(b, spawn=False):
|
|
"""off -> successors. `spawn` includes the coroutine a start_coroutine creates."""
|
|
offs = isl.linear_offsets(b)
|
|
nxt = {offs[i]: offs[i+1] for i in range(len(offs)-1)}
|
|
bases = isl.phase_bases(b)
|
|
E = collections.defaultdict(list)
|
|
loc, sp = {}, {}
|
|
for off in offs:
|
|
w = struct.unpack_from('>I', b, off)[0]
|
|
op, ln = w & 0xFF, (w >> 8) & 0xFF
|
|
sk, dk = (w >> 24) & 0xFF, (w >> 16) & 0xFF
|
|
words = [struct.unpack_from('>I', b, off+i)[0]
|
|
for i in range(4, max(ln,4), 4) if off+i+4 <= len(b)]
|
|
ph = sum(1 for x in bases if x <= off)
|
|
base = bases[ph-1] if ph else bases[0]
|
|
fall = nxt.get(off)
|
|
if op == 0 and len(words) >= 2:
|
|
v = words[1] if sk == 1 else sp.get(words[1]) if sk == 2 else None
|
|
d = sp if dk == 2 else loc
|
|
if v is None: d.pop(words[0], None)
|
|
else: d[words[0]] = v
|
|
elif op == 19 and words:
|
|
if words[0] == 11: fall = None # end_coroutine: thread dies
|
|
if spawn and words[0] == 1 and 0 in loc:
|
|
t = base + loc[0]
|
|
if t in nxt or t in offs: E[off].append(t)
|
|
loc = {}
|
|
elif op == 12 and words:
|
|
E[off].append(base + words[0]); fall = None
|
|
elif op in isl.REL and words:
|
|
E[off].append(base + words[0])
|
|
if fall: E[off].append(fall)
|
|
return E, nxt
|
|
|
|
def guards(b, spawn=False):
|
|
offs = isl.linear_offsets(b)
|
|
E, nxt = edges(b, spawn)
|
|
rev = collections.defaultdict(list)
|
|
for a, ss in E.items():
|
|
for s in ss: rev[s].append(a)
|
|
ends = {o for o, bid, _ in isl.call_sites(b) if bid in (6, 62)}
|
|
R, q = set(ends), collections.deque(ends)
|
|
while q:
|
|
n = q.popleft()
|
|
for p in rev.get(n, ()):
|
|
if p not in R: R.add(p); q.append(p)
|
|
out = []
|
|
s1, s2 = isl.symbols(b, 1), isl.symbols(b, 2)
|
|
for c in isl_cfg.conditions(b, s1, s2):
|
|
br = nxt.get(c['off'])
|
|
if br is None: continue
|
|
taken, fallth = c['target'], nxt.get(br)
|
|
t, f = taken in R, (fallth in R if fallth else False)
|
|
if t != f:
|
|
out.append({**c, 'ends_when': 'taken' if t else 'not-taken'})
|
|
return out, len(R), len(offs), len(ends)
|