compiler.cfg: convert code into two-operand form before SSA destruction; SSA destruct...

diff --git a/basis/compiler/cfg/linear-scan/allocation/allocation.factor b/basis/compiler/cfg/linear-scan/allocation/allocation.factor
index d55266e6e4b63ef5bc3b939eaf0327ee77decf97..4b504d97f55d82743c628f7fb373a60e59809900 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/allocation.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/allocation.factor
@@ -3,7 +3,6 @@
 USING: accessors assocs heaps kernel namespaces sequences fry math
 math.order combinators arrays sorting compiler.utilities
 compiler.cfg.linear-scan.live-intervals
-compiler.cfg.linear-scan.allocation.coalescing
 compiler.cfg.linear-scan.allocation.spilling
 compiler.cfg.linear-scan.allocation.splitting
 compiler.cfg.linear-scan.allocation.state ;
@@ -29,13 +28,11 @@ IN: compiler.cfg.linear-scan.allocation
     second 0 = ; inline
 
 : assign-register ( new -- )
-    dup coalesce? [ coalesce ] [
-        dup register-status {
-            { [ dup no-free-registers? ] [ drop assign-blocked-register ] }
-            { [ 2dup register-available? ] [ register-available ] }
-            [ drop assign-blocked-register ]
-        } cond
-    ] if ;
+    dup register-status {
+        { [ dup no-free-registers? ] [ drop assign-blocked-register ] }
+        { [ 2dup register-available? ] [ register-available ] }
+        [ drop assign-blocked-register ]
+    } cond ;
 
 : handle-interval ( live-interval -- )
     [

diff --git a/basis/compiler/cfg/linear-scan/allocation/coalescing/coalescing.factor b/basis/compiler/cfg/linear-scan/allocation/coalescing/coalescing.factor
deleted file mode 100644 (file)
index ef8a9c5..0000000
--- a/basis/compiler/cfg/linear-scan/allocation/coalescing/coalescing.factor
+++ /dev/null
@@ -1,35 +0,0 @@
-! Copyright (C) 2009 Slava Pestov.
-! See http://factorcode.org/license.txt for BSD license.
-USING: accessors kernel sequences namespaces assocs fry
-combinators.short-circuit
-compiler.cfg.linear-scan.live-intervals
-compiler.cfg.linear-scan.allocation.state ;
-IN: compiler.cfg.linear-scan.allocation.coalescing
-
-: active-interval ( vreg -- live-interval )
-    dup [ dup active-intervals-for [ vreg>> = ] with find nip ] when ;
-
-: avoids-inactive-intervals? ( live-interval -- ? )
-    dup vreg>> inactive-intervals-for
-    [ intervals-intersect? not ] with all? ;
-
-: coalesce? ( live-interval -- ? )
-    {
-        [ copy-from>> active-interval ]
-        [ [ start>> ] [ copy-from>> active-interval end>> ] bi = ]
-        [ avoids-inactive-intervals? ]
-    } 1&& ;
-
-: reuse-spill-slot ( old new -- )
-    [ vreg>> spill-slots get at ] dip '[ _ vreg>> spill-slots get set-at ] when* ;
-
-: reuse-register ( old new -- )
-    reg>> >>reg drop ;
-
-: (coalesce) ( old new -- )
-    [ add-active ] [ [ delete-active ] [ add-handled ] bi ] bi* ;
-
-: coalesce ( live-interval -- )
-    dup copy-from>> active-interval
-    [ reuse-spill-slot ] [ reuse-register ] [ (coalesce) ] 2tri ;
- 
\ No newline at end of file

diff --git a/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor b/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor
index 874523d70a7fb57e2653fda036d4cd9425390ef2..1a2b0f2f2bdceae154b0e8b71d3a2691f1fdd1ef 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor
@@ -45,7 +45,7 @@ ERROR: splitting-atomic-interval ;
     f >>spill-to ; inline
 
 : split-after ( after -- after' )
-    f >>copy-from f >>reg f >>reload-from ; inline
+    f >>reg f >>reload-from ; inline
 
 :: split-interval ( live-interval n -- before after )
     live-interval n check-split

diff --git a/basis/compiler/cfg/linear-scan/debugger/debugger.factor b/basis/compiler/cfg/linear-scan/debugger/debugger.factor
index c9c1b77a0dedb68240fc7194cfac7c2474ba7483..68ff8d4f886559f7d134bd41226a7d66e7cac391 100644 (file)
--- a/basis/compiler/cfg/linear-scan/debugger/debugger.factor
+++ b/basis/compiler/cfg/linear-scan/debugger/debugger.factor
@@ -18,9 +18,8 @@ IN: compiler.cfg.linear-scan.debugger
 
 : interval-picture ( interval -- str )
     [ uses>> picture ]
-    [ copy-from>> unparse ]
     [ vreg>> unparse ]
-    tri 3array ;
+    bi 2array ;
 
 : live-intervals. ( seq -- )
     [ interval-picture ] map simple-table. ;

diff --git a/basis/compiler/cfg/linear-scan/linear-scan-tests.factor b/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
index 2164cef4291758c8918a1f9d1783911bc9a65a09..7cca94c06146b6ae03a3105f35b9f958e7a1fdcb 100644 (file)
--- a/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
+++ b/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
@@ -470,7 +470,6 @@ USING: math.private ;
         clone dup [ start>> ] [ end>> ] bi <live-range> 1vector >>ranges
     ] map ;
 
-! Coalescing interacted badly with splitting
 [ ] [
     {
         T{ live-interval
@@ -478,7 +477,6 @@ USING: math.private ;
             { start 14 }
             { end 17 }
             { uses V{ 14 15 16 17 } }
-            { copy-from V int-regs 67 }
         }
         T{ live-interval
             { vreg V int-regs 67 }
@@ -503,7 +501,6 @@ USING: math.private ;
             { start 10 }
             { end 18 }
             { uses V{ 10 11 12 18 } }
-            { copy-from V int-regs 56 }
         }
         T{ live-interval
             { vreg V int-regs 60 }
@@ -559,7 +556,6 @@ USING: math.private ;
             { start 44 }
             { end 56 }
             { uses V{ 44 45 45 46 56 } }
-            { copy-from V int-regs 3686445 }
         }
         T{ live-interval
             { vreg V int-regs 3686198 }
@@ -572,7 +568,6 @@ USING: math.private ;
             { start 46 }
             { end 49 }
             { uses V{ 46 47 47 49 } }
-            { copy-from V int-regs 3686449 }
         }
         T{ live-interval
             { vreg V int-regs 3686196 }
@@ -603,7 +598,6 @@ USING: math.private ;
             { start 49 }
             { end 52 }
             { uses V{ 49 50 50 52 } }
-            { copy-from V int-regs 3686454 }
         }
         T{ live-interval
             { vreg V int-regs 3686461 }
@@ -622,42 +616,36 @@ USING: math.private ;
             { start 54 }
             { end 76 }
             { uses V{ 54 55 55 76 } }
-            { copy-from V int-regs 3686464 }
         }
         T{ live-interval
             { vreg V int-regs 3686470 }
             { start 58 }
             { end 60 }
             { uses V{ 58 59 59 60 } }
-            { copy-from V int-regs 3686469 }
         }
         T{ live-interval
             { vreg V int-regs 3686469 }
             { start 56 }
             { end 58 }
             { uses V{ 56 57 57 58 } }
-            { copy-from V int-regs 3686449 }
         }
         T{ live-interval
             { vreg V int-regs 3686473 }
             { start 60 }
             { end 62 }
             { uses V{ 60 61 61 62 } }
-            { copy-from V int-regs 3686470 }
         }
         T{ live-interval
             { vreg V int-regs 3686479 }
             { start 62 }
             { end 64 }
             { uses V{ 62 63 63 64 } }
-            { copy-from V int-regs 3686473 }
         }
         T{ live-interval
             { vreg V int-regs 3686735 }
             { start 78 }
             { end 96 }
             { uses V{ 78 79 79 96 } }
-            { copy-from V int-regs 3686372 }
         }
         T{ live-interval
             { vreg V int-regs 3686482 }
@@ -688,7 +676,6 @@ USING: math.private ;
             { start 66 }
             { end 75 }
             { uses V{ 66 67 67 75 } }
-            { copy-from V int-regs 3686483 }
         }
         T{ live-interval
             { vreg V int-regs 3687509 }
@@ -719,7 +706,6 @@ USING: math.private ;
             { start 69 }
             { end 74 }
             { uses V{ 69 70 70 74 } }
-            { copy-from V int-regs 3686491 }
         }
         T{ live-interval
             { vreg V int-regs 3687778 }
@@ -762,7 +748,6 @@ USING: math.private ;
             { start 72 }
             { end 74 }
             { uses V{ 72 73 73 74 } }
-            { copy-from V int-regs 3686499 }
         }
         T{ live-interval
             { vreg V int-regs 3687780 }
@@ -877,7 +862,6 @@ USING: math.private ;
             { start 27 }
             { end 30 }
             { uses V{ 27 28 28 30 } }
-            { copy-from V int-regs 3686300 }
         }
         T{ live-interval
             { vreg V int-regs 3686306 }
@@ -950,7 +934,6 @@ USING: math.private ;
             { start 243 }
             { end 245 }
             { uses V{ 243 244 244 245 } }
-            { copy-from V int-regs 3687845 }
         }
         T{ live-interval
             { vreg V int-regs 3687850 }
@@ -1119,7 +1102,6 @@ USING: math.private ;
             { start 141 }
             { end 143 }
             { uses V{ 141 142 142 143 } }
-            { copy-from V int-regs 3687377 }
         }
         T{ live-interval
             { vreg V int-regs 3687381 }
@@ -1174,7 +1156,6 @@ USING: math.private ;
             { start 293 }
             { end 295 }
             { uses V{ 293 294 294 295 } }
-            { copy-from V int-regs 3687087 }
         }
         T{ live-interval
             { vreg V int-regs 3687403 }
@@ -1345,7 +1326,6 @@ USING: math.private ;
             { start 78 }
             { end 96 }
             { uses V{ 78 79 96 } }
-            { copy-from V int-regs 6372 }
         }
         T{ live-interval
             { vreg V int-regs 6483 }

diff --git a/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor b/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
index 48bef197e62b2284ae55ec576a420296369a03c9..8cc28e41e246c4494ee590b15d241f2ffe48ac36 100644 (file)
--- a/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
+++ b/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
@@ -13,8 +13,7 @@ C: <live-range> live-range
 TUPLE: live-interval
 vreg
 reg spill-to reload-from
-start end ranges uses
-copy-from ;
+start end ranges uses ;
 
 GENERIC: covers? ( insn# obj -- ? )
 
@@ -102,15 +101,6 @@ M: vreg-insn compute-live-intervals*
     [ [ temp-vregs ] 2dip '[ [ _ ] dip _ handle-temp ] each ]
     3tri ;
 
-: record-copy ( insn -- )
-    [ dst>> live-intervals get at ] [ src>> ] bi >>copy-from drop ;
-
-M: ##copy compute-live-intervals*
-    [ call-next-method ] [ record-copy ] bi ;
-
-M: ##copy-float compute-live-intervals*
-    [ call-next-method ] [ record-copy ] bi ;
-
 : handle-live-out ( bb -- )
     live-out keys
     basic-block get [ block-from ] [ block-to ] bi

diff --git a/basis/compiler/cfg/mr/mr.factor b/basis/compiler/cfg/mr/mr.factor
index cb198d51498069facfe8b27456f2e1506899e28b..77d9f1ce187ddddfbd422ed903b960838c98e04c 100644 (file)
--- a/basis/compiler/cfg/mr/mr.factor
+++ b/basis/compiler/cfg/mr/mr.factor
@@ -1,12 +1,11 @@
 ! Copyright (C) 2009 Slava Pestov.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: compiler.cfg.linearization compiler.cfg.two-operand
-compiler.cfg.gc-checks compiler.cfg.linear-scan
-compiler.cfg.build-stack-frame compiler.cfg.rpo ;
+USING: compiler.cfg.linearization compiler.cfg.gc-checks
+compiler.cfg.linear-scan compiler.cfg.build-stack-frame
+compiler.cfg.rpo ;
 IN: compiler.cfg.mr
 
 : build-mr ( cfg -- mr )
-    convert-two-operand
     insert-gc-checks
     linear-scan
     flatten-cfg

diff --git a/basis/compiler/cfg/optimizer/optimizer.factor b/basis/compiler/cfg/optimizer/optimizer.factor
index 8e2df04ccaeb9a0eb083acaf68e4ecc01df22e00..2026cdb4c3d1e4921f24ac806fff2d806f4ae583 100644 (file)
--- a/basis/compiler/cfg/optimizer/optimizer.factor
+++ b/basis/compiler/cfg/optimizer/optimizer.factor
@@ -11,6 +11,7 @@ compiler.cfg.value-numbering
 compiler.cfg.copy-prop
 compiler.cfg.dce
 compiler.cfg.write-barrier
+compiler.cfg.two-operand
 compiler.cfg.ssa.destruction
 compiler.cfg.empty-blocks
 compiler.cfg.predecessors
@@ -42,6 +43,7 @@ SYMBOL: check-optimizer?
         copy-propagation
         eliminate-dead-code
         eliminate-write-barriers
+        convert-two-operand
         destruct-ssa
         delete-empty-blocks
         ?check

diff --git a/basis/compiler/cfg/ssa/destruction/destruction.factor b/basis/compiler/cfg/ssa/destruction/destruction.factor
index 3e6172229ab86ee6da122b5d5502de3ad6eef873..02e48962cb63f94dc9bcbd7fb865b0e9e51ead1d 100644 (file)
--- a/basis/compiler/cfg/ssa/destruction/destruction.factor
+++ b/basis/compiler/cfg/ssa/destruction/destruction.factor
@@ -58,9 +58,13 @@ SYMBOL: copies
 
 GENERIC: prepare-insn ( insn -- )
 
-M: ##copy prepare-insn
+: prepare-copy ( insn -- )
     [ dst>> ] [ src>> ] bi 2array copies get push ;
 
+M: ##copy prepare-insn prepare-copy ;
+
+M: ##copy-float prepare-insn prepare-copy ;
+
 M: ##phi prepare-insn
     [ dst>> ] [ inputs>> values ] bi
     [ eliminate-copy ] with each ;
@@ -81,8 +85,10 @@ M: insn prepare-insn drop ;
         [ 2drop ] [ eliminate-copy ] if
     ] assoc-each ;
 
+UNION: copy-insn ##copy ##copy-float ;
+
 : useless-copy? ( ##copy -- ? )
-    dup ##copy? [ [ dst>> ] [ src>> ] bi eq? ] [ drop f ] if ;
+    dup copy-insn? [ [ dst>> ] [ src>> ] bi eq? ] [ drop f ] if ;
 
 : perform-renaming ( cfg -- )
     leader-map get keys [ dup leader ] H{ } map>assoc renamings set
@@ -95,13 +101,11 @@ M: insn prepare-insn drop ;
     ] each-basic-block ;
 
 : destruct-ssa ( cfg -- cfg' )
-    dup cfg-has-phis? [
-        dup construct-cssa
-        dup compute-defs
-        dup compute-dominance
-        compute-ssa-live-sets
-        dup compute-live-ranges
-        dup prepare-coalescing
-        process-copies
-        dup perform-renaming
-    ] when ;
\ No newline at end of file
+    dup construct-cssa
+    dup compute-defs
+    dup compute-dominance
+    compute-ssa-live-sets
+    dup compute-live-ranges
+    dup prepare-coalescing
+    process-copies
+    dup perform-renaming ;
\ No newline at end of file

diff --git a/basis/compiler/cfg/ssa/interference/interference.factor b/basis/compiler/cfg/ssa/interference/interference.factor
index dd002ec977eaa4c5e179d987fc63d35cabd25c63..a76b55cd83dcc8fecd489af7f800e10d05ea85ae 100644 (file)
--- a/basis/compiler/cfg/ssa/interference/interference.factor
+++ b/basis/compiler/cfg/ssa/interference/interference.factor
@@ -6,6 +6,11 @@ compiler.cfg.def-use compiler.cfg.dominance
 compiler.cfg.ssa.interference.live-ranges ;
 IN: compiler.cfg.ssa.interference
 
+! Interference testing using SSA properties. Actually the only SSA property
+! used here is that definitions dominate uses; because of this, the input
+! is allowed to have multiple definitions of each vreg as long as they're
+! all in the same basic block. This is needed because two-operand conversion
+! runs before coalescing, which uses SSA interference testing.
 <PRIVATE
 
 :: kill-after-def? ( vreg1 vreg2 bb -- ? )
@@ -47,9 +52,10 @@ PRIVATE>
         [ 2drop 2drop f ]
     } cond ;
 
-! Debug this stuff later
 <PRIVATE
 
+! Debug this stuff later
+
 : quadratic-test? ( seq1 seq2 -- ? ) [ length ] bi@ + 10 < ;
 
 : quadratic-test ( seq1 seq2 -- ? )

diff --git a/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor b/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor
index 151af8bea4e706e662b78b3cf02b5fed8963abd8..c094b18ce9a3e3184b948d86cd2a59705c47e410 100644 (file)
--- a/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor
+++ b/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor
@@ -11,8 +11,13 @@ IN: compiler.cfg.ssa.interference.live-ranges
 
 SYMBOLS: local-def-indices local-kill-indices ;
 
-: record-def ( n vregs -- )
-    dup [ local-def-indices get set-at ] [ 2drop ] if ;
+: record-def ( n vreg -- )
+    ! We allow multiple defs of a vreg as long as they're
+    ! all in the same basic block
+    dup [
+        local-def-indices get 2dup key?
+        [ 3drop ] [ set-at ] if
+    ] [ 2drop ] if ;
 
 : record-uses ( n vregs -- )
     local-kill-indices get '[ _ set-at ] with each ;

diff --git a/basis/compiler/cfg/two-operand/two-operand-tests.factor b/basis/compiler/cfg/two-operand/two-operand-tests.factor
index 0717f1c536238621b861ec3ca1925971b3ac2564..fb0ab6ff0362418ecba6f6ac795df8edc405fdbc 100644 (file)
--- a/basis/compiler/cfg/two-operand/two-operand-tests.factor
+++ b/basis/compiler/cfg/two-operand/two-operand-tests.factor
@@ -14,25 +14,3 @@ compiler.cfg.registers cpu.architecture namespaces tools.test ;
         T{ ##sub f V int-regs 1 V int-regs 2 V int-regs 3 }
     } (convert-two-operand)
 ] unit-test
-
-[
-    V{
-        T{ ##sub f V int-regs 1 V int-regs 1 V int-regs 2 }
-    }
-] [
-    {
-        T{ ##sub f V int-regs 1 V int-regs 1 V int-regs 2 }
-    } (convert-two-operand)
-] unit-test
-
-[
-    V{
-        T{ ##copy f V int-regs 4 V int-regs 1 }
-        T{ ##copy f V int-regs 1 V int-regs 2 }
-        T{ ##sub f V int-regs 1 V int-regs 1 V int-regs 4 }
-    }
-] [
-    {
-        T{ ##sub f V int-regs 1 V int-regs 2 V int-regs 1 }
-    } (convert-two-operand)
-] unit-test

diff --git a/basis/compiler/cfg/two-operand/two-operand.factor b/basis/compiler/cfg/two-operand/two-operand.factor
index 7a8b160acdcd8b9e1803968a55dc0a125d0a7240..729c476cc457f14c971a5b0ce023a5df7a5b3763 100644 (file)
--- a/basis/compiler/cfg/two-operand/two-operand.factor
+++ b/basis/compiler/cfg/two-operand/two-operand.factor
@@ -5,27 +5,17 @@ compiler.cfg.registers compiler.cfg.instructions
 compiler.cfg.rpo cpu.architecture ;
 IN: compiler.cfg.two-operand
 
-! This pass runs after SSA coalescing and normalizes instructions
-! to fit the x86 two-address scheme. Possibilities are:
-
-! 1) x = x op y
-! 2) x = y op x
-! 3) x = y op z
-
-! In case 1, there is nothing to do.
-
-! In case 2, we convert to
-! z = y
-! z = z op x
-! x = z
-
-! In case 3, we convert to
+! This pass runs before SSA coalescing and normalizes instructions
+! to fit the x86 two-address scheme. Since the input is in SSA,
+! it suffices to convert
+!
+! x = y op z
+!
+! to
+!
 ! x = y
 ! x = x op z
-
-! In case 2 and case 3, linear scan coalescing will eliminate a
-! copy if the value y is never used again.
-
+!
 ! We don't bother with ##add, ##add-imm, ##sub-imm or ##mul-imm
 ! since x86 has LEA and IMUL instructions which are effectively
 ! three-operand addition and multiplication, respectively.
@@ -59,37 +49,15 @@ GENERIC: convert-two-operand* ( insn -- )
         { double-float-regs [ ##copy-float ] }
     } case ; inline
 
-: case-1? ( insn -- ? ) [ dst>> ] [ src1>> ] bi = ; inline
-
-: case-1 ( insn -- ) , ; inline
-
-: case-2? ( insn -- ? ) [ dst>> ] [ src2>> ] bi = ; inline
-
-: case-2 ( insn -- )
-    dup dst>> reg-class>> next-vreg
-    [ swap src2>> emit-copy ]
-    [ drop [ src2>> ] [ src1>> ] bi emit-copy ]
-    [ >>src2 dup dst>> >>src1 , ]
-    2tri ; inline
-
-: case-3 ( insn -- )
+M: two-operand-insn convert-two-operand*
     [ [ dst>> ] [ src1>> ] bi emit-copy ]
     [ dup dst>> >>src1 , ]
-    bi ; inline
-
-M: two-operand-insn convert-two-operand*
-    {
-        { [ dup case-1? ] [ case-1 ] }
-        { [ dup case-2? ] [ case-2 ] }
-        [ case-3 ]
-    } cond ; inline
+    bi ;
 
 M: ##not convert-two-operand*
-    dup [ dst>> ] [ src>> ] bi = [
-        [ [ dst>> ] [ src>> ] bi ##copy ]
-        [ dup dst>> >>src ]
-        bi
-    ] unless , ;
+    [ [ dst>> ] [ src>> ] bi emit-copy ]
+    [ dup dst>> >>src , ]
+    bi ;
 
 M: insn convert-two-operand* , ;