compiler.cfg.linear-scan.live-intervals ;
IN: compiler.cfg.linear-scan.allocation.state
+! Start index of current live interval. We ensure that all
+! live intervals added to the unhandled set have a start index
+! strictly greater than this one. This ensures that we can catch
+! infinite loop situations. We also ensure that all live
+! intervals added to the handled set have an end index strictly
+! smaller than this one. This helps catch bugs.
+SYMBOL: progress
+
+: check-unhandled ( live-interval -- )
+ start>> progress get <= [ "check-unhandled" throw ] when ; inline
+
+: check-handled ( live-interval -- )
+ end>> progress get > [ "check-handled" throw ] when ; inline
+
! Mapping from register classes to sequences of machine registers
SYMBOL: registers
SYMBOL: handled-intervals
: add-handled ( live-interval -- )
- handled-intervals get push ;
+ [ check-handled ] [ handled-intervals get push ] bi ;
: finished? ( n live-interval -- ? ) end>> swap < ;
! Minheap of live intervals which still need a register allocation
SYMBOL: unhandled-intervals
-! Start index of current live interval. We ensure that all
-! live intervals added to the unhandled set have a start index
-! strictly greater than ths one. This ensures that we can catch
-! infinite loop situations.
-SYMBOL: progress
-
-: check-progress ( live-interval -- )
- start>> progress get <= [ "No progress" throw ] when ; inline
-
: add-unhandled ( live-interval -- )
- [ check-progress ]
+ [ check-unhandled ]
[ dup start>> unhandled-intervals get heap-push ]
bi ;
} cleave f swap \ _copy boa , ;
: handle-copy ( live-interval -- )
- dup [ spill-to>> not ] [ split-next>> ] bi and
- [ insert-copy ] [ drop ] if ;
+ dup split-next>> [ insert-copy ] [ drop ] if ;
: expire-old-intervals ( n -- )
[ pending-intervals get ] dip '[
[ reg>> ]
[ vreg>> reg-class>> ]
[ reload-from>> ]
- [ end>> ]
+ [ start>> ]
} cleave f swap \ _reload boa , ;
: handle-reload ( live-interval -- )
#! Any live intervals which start on the current instruction
#! are added to the active set.
unhandled-intervals get dup heap-empty? [ 2drop ] [
- 2dup heap-peek drop start>> >= [
+ 2dup heap-peek drop start>> = [
heap-pop drop
[ add-active ] [ handle-reload ] bi
activate-new-intervals
[
bb begin-block
[
- [ insn#>> prepare-insn ]
- [ assign-registers-in-insn ]
- [ , ]
- tri
+ {
+ [ insn#>> 1 - prepare-insn ]
+ [ insn#>> prepare-insn ]
+ [ assign-registers-in-insn ]
+ [ , ]
+ } cleave
] each
bb end-block
] V{ } make
IN: compiler.cfg.linear-scan.tests
USING: tools.test random sorting sequences sets hashtables assocs
kernel fry arrays splitting namespaces math accessors vectors locals
-math.order grouping
+math.order grouping strings strings.private
cpu.architecture
compiler.cfg
compiler.cfg.optimizer
compiler.cfg.linearization
compiler.cfg.debugger
compiler.cfg.linear-scan
+compiler.cfg.linear-scan.numbering
compiler.cfg.linear-scan.live-intervals
compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
check-allocation? on
check-assignment? on
+check-numbering? on
[
{ T{ live-range f 1 10 } T{ live-range f 15 15 } }
4 get 6 get 1vector >>successors drop
5 get 6 get 1vector >>successors drop
+[ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
+
+! Another push-all reduction to demonstrate numbering anamoly
+V{ T{ ##prologue } T{ ##branch } }
+0 test-bb
+
+V{
+ T{ ##peek { dst V int-regs 1 } { loc D 0 } }
+ T{ ##slot-imm
+ { dst V int-regs 5 }
+ { obj V int-regs 1 }
+ { slot 3 }
+ { tag 7 }
+ }
+ T{ ##peek { dst V int-regs 7 } { loc D 1 } }
+ T{ ##slot-imm
+ { dst V int-regs 12 }
+ { obj V int-regs 7 }
+ { slot 1 }
+ { tag 6 }
+ }
+ T{ ##add
+ { dst V int-regs 25 }
+ { src1 V int-regs 5 }
+ { src2 V int-regs 12 }
+ }
+ T{ ##compare-branch
+ { src1 V int-regs 25 }
+ { src2 V int-regs 5 }
+ { cc cc> }
+ }
+}
+1 test-bb
+
+V{
+ T{ ##slot-imm
+ { dst V int-regs 41 }
+ { obj V int-regs 1 }
+ { slot 2 }
+ { tag 7 }
+ }
+ T{ ##slot-imm
+ { dst V int-regs 44 }
+ { obj V int-regs 41 }
+ { slot 1 }
+ { tag 6 }
+ }
+ T{ ##compare-branch
+ { src1 V int-regs 25 }
+ { src2 V int-regs 44 }
+ { cc cc> }
+ }
+}
+2 test-bb
+
+V{
+ T{ ##add-imm
+ { dst V int-regs 54 }
+ { src1 V int-regs 25 }
+ { src2 8 }
+ }
+ T{ ##load-immediate { dst V int-regs 55 } { val 24 } }
+ T{ ##inc-d { n 4 } }
+ T{ ##inc-r { n 1 } }
+ T{ ##replace { src V int-regs 25 } { loc D 2 } }
+ T{ ##replace { src V int-regs 1 } { loc D 3 } }
+ T{ ##replace { src V int-regs 5 } { loc D 4 } }
+ T{ ##replace { src V int-regs 1 } { loc D 1 } }
+ T{ ##replace { src V int-regs 54 } { loc D 0 } }
+ T{ ##replace { src V int-regs 12 } { loc R 0 } }
+ T{ ##fixnum-mul
+ { src1 V int-regs 54 }
+ { src2 V int-regs 55 }
+ { temp1 V int-regs 58 }
+ { temp2 V int-regs 59 }
+ }
+ T{ ##branch }
+}
+3 test-bb
+
+V{
+ T{ ##peek { dst V int-regs 60 } { loc D 1 } }
+ T{ ##slot-imm
+ { dst V int-regs 66 }
+ { obj V int-regs 60 }
+ { slot 2 }
+ { tag 7 }
+ }
+ T{ ##inc-d { n 1 } }
+ T{ ##inc-r { n 1 } }
+ T{ ##replace { src V int-regs 66 } { loc D 0 } }
+ T{ ##replace { src V int-regs 60 } { loc R 0 } }
+ T{ ##call { word resize-string } }
+ T{ ##branch }
+}
+4 test-bb
+
+V{
+ T{ ##peek { dst V int-regs 67 } { loc R 0 } }
+ T{ ##peek { dst V int-regs 68 } { loc D 0 } }
+ T{ ##set-slot-imm
+ { src V int-regs 68 }
+ { obj V int-regs 67 }
+ { slot 2 }
+ { tag 7 }
+ }
+ T{ ##write-barrier
+ { src V int-regs 67 }
+ { card# V int-regs 75 }
+ { table V int-regs 76 }
+ }
+ T{ ##inc-d { n -1 } }
+ T{ ##inc-r { n -1 } }
+ T{ ##peek { dst V int-regs 94 } { loc D 0 } }
+ T{ ##peek { dst V int-regs 96 } { loc D 1 } }
+ T{ ##peek { dst V int-regs 98 } { loc D 2 } }
+ T{ ##peek { dst V int-regs 100 } { loc D 3 } }
+ T{ ##peek { dst V int-regs 102 } { loc D 4 } }
+ T{ ##peek { dst V int-regs 106 } { loc R 0 } }
+ T{ ##copy { dst V int-regs 95 } { src V int-regs 94 } }
+ T{ ##copy { dst V int-regs 97 } { src V int-regs 96 } }
+ T{ ##copy { dst V int-regs 99 } { src V int-regs 98 } }
+ T{ ##copy { dst V int-regs 101 } { src V int-regs 100 } }
+ T{ ##copy { dst V int-regs 103 } { src V int-regs 102 } }
+ T{ ##copy { dst V int-regs 107 } { src V int-regs 106 } }
+ T{ ##branch }
+}
+5 test-bb
+
+V{
+ T{ ##inc-d { n 3 } }
+ T{ ##inc-r { n 1 } }
+ T{ ##copy { dst V int-regs 95 } { src V int-regs 1 } }
+ T{ ##copy { dst V int-regs 97 } { src V int-regs 25 } }
+ T{ ##copy { dst V int-regs 99 } { src V int-regs 1 } }
+ T{ ##copy { dst V int-regs 101 } { src V int-regs 5 } }
+ T{ ##copy { dst V int-regs 103 } { src V int-regs 7 } }
+ T{ ##copy { dst V int-regs 107 } { src V int-regs 12 } }
+ T{ ##branch }
+}
+6 test-bb
+
+V{
+ T{ ##load-immediate
+ { dst V int-regs 78 }
+ { val 4611686018427387896 }
+ }
+ T{ ##and
+ { dst V int-regs 81 }
+ { src1 V int-regs 97 }
+ { src2 V int-regs 78 }
+ }
+ T{ ##set-slot-imm
+ { src V int-regs 81 }
+ { obj V int-regs 95 }
+ { slot 3 }
+ { tag 7 }
+ }
+ T{ ##inc-d { n -2 } }
+ T{ ##copy { dst V int-regs 110 } { src V int-regs 99 } }
+ T{ ##copy { dst V int-regs 111 } { src V int-regs 101 } }
+ T{ ##copy { dst V int-regs 112 } { src V int-regs 103 } }
+ T{ ##copy { dst V int-regs 117 } { src V int-regs 107 } }
+ T{ ##branch }
+}
+7 test-bb
+
+V{
+ T{ ##inc-d { n 1 } }
+ T{ ##inc-r { n 1 } }
+ T{ ##copy { dst V int-regs 110 } { src V int-regs 1 } }
+ T{ ##copy { dst V int-regs 111 } { src V int-regs 5 } }
+ T{ ##copy { dst V int-regs 112 } { src V int-regs 7 } }
+ T{ ##copy { dst V int-regs 117 } { src V int-regs 12 } }
+ T{ ##branch }
+}
+8 test-bb
+
+V{
+ T{ ##inc-d { n 1 } }
+ T{ ##inc-r { n -1 } }
+ T{ ##replace { src V int-regs 117 } { loc D 0 } }
+ T{ ##replace { src V int-regs 110 } { loc D 1 } }
+ T{ ##replace { src V int-regs 111 } { loc D 2 } }
+ T{ ##replace { src V int-regs 112 } { loc D 3 } }
+ T{ ##epilogue }
+ T{ ##return }
+}
+9 test-bb
+
+0 get 1 get 1vector >>successors drop
+1 get 2 get 8 get V{ } 2sequence >>successors drop
+2 get 3 get 6 get V{ } 2sequence >>successors drop
+3 get 4 get 1vector >>successors drop
+4 get 5 get 1vector >>successors drop
+5 get 7 get 1vector >>successors drop
+6 get 7 get 1vector >>successors drop
+7 get 9 get 1vector >>successors drop
+8 get 9 get 1vector >>successors drop
+
[ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
\ No newline at end of file