compiler.cfg.def-use
compiler.cfg.gvn.graph
compiler.cfg.predecessors
+compiler.cfg.renaming.functor
compiler.cfg.rpo ;
FROM: assocs => change-at ;
FROM: namespaces => set ;
M: avail-analysis transfer-set drop defined assoc-union ;
-! Strict idea of availability, for now. Would like to see if
-! searching the VN congruence classes for the smallest
-! available vn would work at all / better.
+: available? ( vn -- ? ) basic-block get avail-in key? ;
-: available? ( vn -- ? )
+: best-vreg ( available-vregs -- vreg )
+ [ f ] [ infimum ] if-empty ;
+
+: >avail-vreg ( vreg -- vreg/f )
final-iteration? get [
- basic-block get avail-in key?
- ] [ drop t ] if ;
+ congruence-class [ available? ] filter best-vreg
+ ] when ;
: available-uses? ( insn -- ? )
- uses-vregs [ available? ] all? ;
+ uses-vregs [ >avail-vreg ] all? ;
: with-available-uses? ( quot -- ? )
keep swap [ available-uses? ] [ drop f ] if ; inline
: make-available ( vreg -- )
basic-block get avail-ins get [ dupd clone ?set-at ] change-at ;
+
+RENAMING: >avail [ ] [ dup >avail-vreg swap or ] [ ]
! assoc mapping value numbers to instructions
SYMBOL: vns>insns
+! assoc mapping each value number to a sequence of vregs
+! sharing that value number (i.e., the congruence class)
+SYMBOL: vns>vregs
+
! boolean to track whether vregs>vns changes
SYMBOL: changed?
: vreg>insn ( vreg -- insn ) vreg>vn vn>insn ;
+: congruence-class ( vreg -- vregs )
+ vreg>vn vns>vregs get at ;
+
: clear-exprs ( -- )
exprs>vns get clear-assoc
vns>insns get clear-assoc ;
+: compute-congruence-classes ( -- )
+ vregs>vns get H{ } clone [
+ [ push-at ] curry assoc-each
+ ] keep vns>vregs set ;
+
: init-value-graph ( -- )
0 input-expr-counter set
H{ } clone vregs>vns set
] unit-test
] when
-! FIXME rewrite redundancy elimination to search for available
-! registers that compute the same value number, instead of just
-! relying on the availability of the canonical leader
+! Make sure to search for available registers that compute the
+! same value number, instead of just relying on the
+! availability of the canonical leader.
V{ T{ ##branch } } 0 test-bb
value-numbering drop
] unit-test
-! ##load-integer cannot be turned into a ##copy because the
-! canonical leader for the value 100 is unavailable.
+! First ##load-integer cannot be turned into a ##copy because
+! the canonical leader for the value 100 is unavailable, but
+! the rest should still be redundant.
[ t ] [ 4 get instructions>> first ##load-integer? ] unit-test
-
-! Not fixed yet; and would need to change if value-numbering
-! subsumed copy-prop.
-! [ t ] [ 4 get instructions>> rest [ ##copy? ] all? ] unit-test
+[ 1 ] [ 4 get instructions>> [ ##load-integer? ] count ] unit-test
! Global optimization
V{ T{ ##prologue } T{ ##branch } } 0 test-bb
GENERIC: simplify ( insn -- insn' )
-M: insn simplify dup rewrite [ simplify ] [ ] ?if ;
+M: insn simplify dup rewrite [ simplify ] [ dup >avail-insn-uses ] ?if ;
M: array simplify [ simplify ] map ;
M: ##copy simplify ;
] [ drop defs-available ] if ;
: eliminate-redundancy ( insn -- insn' )
- dup >expr exprs>vns get at
+ dup >expr exprs>vns get at >avail-vreg
[ ?eliminate ] [ defs-available ] if* ;
M: ##phi gcse
: eliminate-common-subexpressions ( cfg -- )
final-iteration? on
+ compute-congruence-classes
dup compute-avail-sets
[ gcse-step ] simple-optimization ;