commit 86c229545c585a7098edfc7bc2452033766ae6e5
parent 3c2cd14fc90f271cecd3eab71c77dcdd9cb218f5
Author: erai <erai@omiltem.net>
Date: Sat, 15 Feb 2025 20:54:29 +0000
backlink ir
Diffstat:
| M | ir.om | | | 148 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------- |
| M | ircout.om | | | 55 | +------------------------------------------------------ |
2 files changed, 135 insertions(+), 68 deletions(-)
diff --git a/ir.om b/ir.om
@@ -66,6 +66,8 @@ struct irblock {
ops_len: int;
ops_cap: int;
done: int;
+ back: **irblock; // WARNING: if the flow graph changes, this is stale.
+ back_len: int;
out: *irblock;
alt: *irblock;
label: *label;
@@ -92,6 +94,7 @@ struct irvar {
t: *type;
n: int;
offset: int;
+ dead: int;
mark: int;
}
@@ -107,6 +110,8 @@ struct irfunc {
blocks: **irblock;
blocks_len: int;
blocks_cap: int;
+ returns: **irblock; // WARNING: if the flow graph changes, this is stale.
+ returns_len: int;
cur: *irblock;
labels_tree: *irlabel;
vars_tree: *irvar;
@@ -2441,16 +2446,27 @@ func irblock_fold(ic: *irfunc, b: *irblock) {
func irblock_flow2(ic: *irfunc, ib: *irblock) {
var kind: int;
+ var op: *irop;
+ // If we visit a block twice, mark it as having two incoming links
if ib.mark {
ib.mark = 2;
return;
}
-
ib.mark = 1;
- kind = ib.ops[ib.ops_len - 1].kind;
+ op = ib.ops[ib.ops_len - 1];
+ kind = op.kind;
+
+ // Convert useless branches to jumps
+ if kind == IOP_BRANCH && ib.out == ib.alt {
+ kind = IOP_JUMP;
+ op.kind = IOP_JUMP;
+ op.a = nil;
+ ib.alt = nil;
+ }
+ // Follow the alt link of a branch
if kind == IOP_BRANCH {
irblock_flow2(ic, ib.alt);
@@ -2459,6 +2475,7 @@ func irblock_flow2(ic: *irfunc, ib: *irblock) {
}
}
+ // Follow the out link of a jump/call/branch
if kind == IOP_BRANCH || kind == IOP_CALL || kind == IOP_JUMP {
irblock_flow2(ic, ib.out);
@@ -2473,42 +2490,47 @@ func irblock_flow3(ic: *irfunc, ib: *irblock) {
var kind: int;
var i: int;
+ // Attempt to merge once
if ib.mark == 3 {
return;
}
-
ib.mark = 3;
loop {
kind = ib.ops[ib.ops_len - 1].kind;
+ // Merge down the alt branch first
if kind == IOP_BRANCH {
irblock_flow3(ic, ib.alt);
break;
}
+ // Only merge blocks that end in a jump
if kind != IOP_JUMP {
break;
}
out = ib.out;
+ // If a block has two incoming edges, then don't merge.
+ // But continue attempting to merge down the chain.
if out.mark == 2 {
ib = out;
ib.mark = 3;
continue;
}
+ // If this chain reached a merge point then go to the next chain.
if out.mark == 3 {
break;
}
- // Delete the jump
+ // Delete the jump.
ib.out = nil;
ib.ops_len = ib.ops_len - 1;
ib.done = 0;
- // Concatenate the block
+ // Concatenate the blocks.
i = 0;
loop {
if i == out.ops_len {
@@ -2520,7 +2542,7 @@ func irblock_flow3(ic: *irfunc, ib: *irblock) {
i = i + 1;
}
- // Possible branch
+ // Update our links.
ib.out = out.out;
ib.alt = out.alt;
ib.done = 1;
@@ -2566,7 +2588,7 @@ func irfunc_fold(ic: *irfunc) {
}
}
-func irblock_value(ic: *irfunc, ib: *irblock) {
+func irblock_basic_value(ic: *irfunc, ib: *irblock) {
var i: int;
i = 0;
@@ -2581,7 +2603,7 @@ func irblock_value(ic: *irfunc, ib: *irblock) {
}
}
-func irfunc_value(ic: *irfunc) {
+func irfunc_basic_value(ic: *irfunc) {
var i: int;
// Forward simple stores to their use
@@ -2591,28 +2613,126 @@ func irfunc_value(ic: *irfunc) {
break;
}
- irblock_value(ic, ic.blocks[i]);
+ irblock_basic_value(ic, ic.blocks[i]);
i = i + 1;
}
}
+func irblock_backlink(ic: *irfunc, ib: *irblock, from: *irblock) {
+ var kind: int;
+
+ // Add an incoming edge.
+ if from {
+ if ib.back {
+ ib.back[ib.back_len] = from;
+ }
+ ib.back_len = ib.back_len + 1;
+ }
+
+ // Descend to out/alt blocks once.
+ if ib.mark {
+ return;
+ }
+ ib.mark = 1;
+
+ // Add incoming edges for unique blocks.
+ kind = ib.ops[ib.ops_len - 1].kind;
+ if kind == IOP_CALL || kind == IOP_JUMP {
+ irblock_backlink(ic, ib.out, ib);
+ } else if kind == IOP_BRANCH {
+ irblock_backlink(ic, ib.out, ib);
+ if ib.out != ib.alt {
+ irblock_backlink(ic, ib.alt, ib);
+ } else {
+ die("useless branch");
+ }
+ } else if kind == IOP_RETURN {
+ if ic.returns {
+ ic.returns[ic.returns_len] = ib;
+ }
+ ic.returns_len = ic.returns_len + 1;
+ } else {
+ die("invalid block");
+ }
+}
+
+func irfunc_backlink(ic: *irfunc) {
+ var ib: *irblock;
+ var i: int;
+ var j: int;
+
+ // Clear the reachable returns
+ if ic.returns {
+ free(ic.a, ic.returns as *byte);
+ }
+ ic.returns = nil;
+ ic.returns_len = 0;
+
+ // Clear the known backlinks
+ i = 0;
+ loop {
+ if i == ic.blocks_len {
+ break;
+ }
+
+ ib = ic.blocks[i];
+
+ if ib.back {
+ free(ic.a, ib.back as *byte);
+ }
+ ib.back = nil;
+ ib.back_len = 0;
+
+ i = i + 1;
+ }
+
+ // Walk the call graph to find the reachable blocks
+ irblock_backlink(ic, ic.blocks[0], nil);
+
+ // Allocate space for returns
+ ic.returns = alloc(ic.a, ic.returns_len * sizeof(*ic.returns)) as **irblock;
+
+ // Find returns, clear marks, and allocate backlinks
+ i = 0;
+ j = 0;
+ loop {
+ if i == ic.blocks_len {
+ break;
+ }
+
+ ib = ic.blocks[i];
+
+ if ib.back_len {
+ ib.back = alloc(ic.a, ib.back_len * sizeof(*ib.back)) as **irblock;
+ }
+
+ ib.back_len = 0;
+ ib.mark = 0;
+
+ i = i + 1;
+ }
+
+ // Fill in the backlink arrays
+ irblock_backlink(ic, ic.blocks[0], nil);
+ irreset(ic.blocks[0]);
+}
+
func ir_optimize(ic: *irfunc) {
// Do the easy simplifications first.
irfunc_dead(ic);
irfunc_fold(ic);
irfunc_flow(ic);
+ irfunc_backlink(ic);
- irfunc_value(ic);
+ // Do some data flow analysis within a basic block
+ irfunc_basic_value(ic);
// Do them again.
- irfunc_dead(ic);
irfunc_fold(ic);
irfunc_flow(ic);
+ irfunc_backlink(ic);
- // Do some data flow analysis
- // Do value forwarding
- // Do common expression elimination
// Do instruction selection
// Do register allocation
}
diff --git a/ircout.om b/ircout.om
@@ -104,8 +104,6 @@ func ircdefine(c: *compiler, d: *decl) {
iv = ic.vars[i];
- iv.mark = 0;
-
i = i + 1;
}
@@ -123,7 +121,7 @@ func ircdefine(c: *compiler, d: *decl) {
iv = ic.vars[i];
- if !iv.mark {
+ if iv.dead {
i = i + 1;
continue;
}
@@ -162,19 +160,6 @@ func ircdefine(c: *compiler, d: *decl) {
irreset(top);
fputs(c.cout, "}\n");
-
- i = 0;
- loop {
- if i == ic.vars_len {
- break;
- }
-
- iv = ic.vars[i];
-
- iv.mark = 0;
-
- i = i + 1;
- }
}
func ircuse(c: *compiler, ic: *irfunc, ib: *irblock) {
@@ -191,17 +176,6 @@ func ircuse(c: *compiler, ic: *irfunc, ib: *irblock) {
ib.mark = 2;
- i = 0;
- loop {
- if i == ib.ops_len {
- break;
- }
-
- ircuseop(c, ic, ib, ib.ops[i]);
-
- i = i + 1;
- }
-
if ib.out {
ircuse(c, ic, ib.out);
}
@@ -212,33 +186,6 @@ func ircuse(c: *compiler, ic: *irfunc, ib: *irblock) {
}
}
-func ircuseop(c: *compiler, ic: *irfunc, ib: *irblock, op: *irop) {
- var kind: int;
-
- kind = op.kind;
- if kind == IOP_VAR || kind == IOP_VARREF {
- ic.vars[op.n].mark = 1;
- } else if kind == IOP_STORE || kind == IOP_ADD || kind == IOP_AND
- || kind == IOP_OR || kind == IOP_XOR || kind == IOP_DIV
- || kind == IOP_MOD || kind == IOP_LSH || kind == IOP_RSH
- || kind == IOP_MUL || kind == IOP_SUB || kind == IOP_EQ
- || kind == IOP_NE || kind == IOP_GT || kind == IOP_GE
- || kind == IOP_LT || kind == IOP_LE {
- // Binary operators
- ircuseop(c, ic, ib, op.a);
- ircuseop(c, ic, ib, op.b);
- } else if kind == IOP_NEG || kind == IOP_NOT || kind == IOP_LOAD
- || kind == IOP_RETVAL || kind == IOP_ARG || kind == IOP_CALL
- || kind == IOP_BRANCH || kind == IOP_RETURN {
- // Unary operators
- ircuseop(c, ic, ib, op.a);
- } else if kind == IOP_FUNC || kind == IOP_CONST || kind == IOP_STR || kind == IOP_JUMP {
- // No variable possible
- } else {
- die("invalid op");
- }
-}
-
func ircbody(c: *compiler, ic: *irfunc, ib: *irblock) {
if !ib || ib.mark & 1 {
return;
