-! Copyright (C) 2008, 2009 Slava Pestov.
+! Copyright (C) 2008, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors assocs heaps kernel namespaces sequences fry math
math.order combinators arrays sorting compiler.utilities locals
! If the live interval has a usage at 'n', don't spill it,
! since this means its being defined by the sync point
! instruction. Output t if this is the case.
- 2dup [ uses>> ] dip swap member? [ 2drop t ] [ spill f ] if ;
+ 2dup [ uses>> ] dip '[ n>> _ = ] any?
+ [ 2drop t ] [ spill f ] if ;
: handle-sync-point ( n -- )
[ active-intervals get values ] dip
-! Copyright (C) 2009 Slava Pestov.
+! Copyright (C) 2009, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors arrays assocs combinators fry hints kernel locals
math sequences sets sorting splitting namespaces linked-assocs
] [ drop ] if ;
: trim-before-ranges ( live-interval -- )
- [ ranges>> ] [ uses>> last 1 + ] bi
+ [ ranges>> ] [ uses>> last n>> 1 + ] bi
[ '[ from>> _ <= ] filter! drop ]
[ swap last (>>to) ]
2bi ;
: trim-after-ranges ( live-interval -- )
- [ ranges>> ] [ uses>> first ] bi
+ [ ranges>> ] [ uses>> first n>> ] bi
[ '[ to>> _ >= ] filter! drop ]
[ swap first (>>from) ]
2bi ;
split-interval [ spill-before ] [ spill-after ] bi* ;
: find-use-position ( live-interval new -- n )
- [ uses>> ] [ start>> '[ _ >= ] ] bi* find nip 1/0. or ;
+ [ uses>> ] [ start>> '[ n>> _ >= ] ] bi* find nip
+ [ n>> ] [ 1/0. ] if* ;
: find-use-positions ( live-intervals new assoc -- )
'[ [ _ find-use-position ] [ reg>> ] bi _ add-use-position ] each ;
>alist alist-max ;
: spill-new? ( new pair -- ? )
- [ uses>> first ] [ second ] bi* > ;
+ [ uses>> first n>> ] [ second ] bi* > ;
: spill-new ( new pair -- )
drop spill-after add-unhandled ;
-! Copyright (C) 2009 Slava Pestov.
+! Copyright (C) 2009, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors arrays assocs combinators fry hints kernel locals
math sequences sets sorting splitting namespaces
] bi ;
: split-uses ( uses n -- before after )
- '[ _ <= ] partition ;
+ '[ n>> _ <= ] partition ;
ERROR: splitting-too-early ;
-! Copyright (C) 2008, 2009 Slava Pestov.
+! Copyright (C) 2008, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors kernel math assocs namespaces sequences heaps
-fry make combinators sets locals arrays
+fry make combinators combinators.short-circuit sets locals arrays
cpu.architecture layouts
compiler.cfg
compiler.cfg.def-use
: insert-reload ( live-interval -- )
[ reg>> ] [ vreg>> rep-of ] [ reload-from>> ] tri _reload ;
+: insert-reload? ( live-interval -- ? )
+ ! Don't insert a reload if the register will be written to
+ ! before being read again.
+ {
+ [ reload-from>> ]
+ [ uses>> first type>> +use+ eq? ]
+ } 1&& ;
+
: handle-reload ( live-interval -- )
- dup reload-from>> [ insert-reload ] [ drop ] if ;
+ dup insert-reload? [ insert-reload ] [ drop ] if ;
: activate-interval ( live-interval -- )
[ add-pending ] [ handle-reload ] bi ;
{ vreg 1 }
{ start 0 }
{ end 2 }
- { uses V{ 0 1 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } } }
{ ranges V{ T{ live-range f 0 2 } } }
{ spill-to T{ spill-slot f 0 } }
}
{ vreg 1 }
{ start 5 }
{ end 5 }
- { uses V{ 5 } }
+ { uses V{ T{ vreg-use f 5 } } }
{ ranges V{ T{ live-range f 5 5 } } }
{ reload-from T{ spill-slot f 0 } }
}
{ vreg 1 }
{ start 0 }
{ end 5 }
- { uses V{ 0 1 5 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } T{ vreg-use f 5 } } }
{ ranges V{ T{ live-range f 0 5 } } }
} 2 split-for-spill
] unit-test
{ vreg 2 }
{ start 0 }
{ end 1 }
- { uses V{ 0 } }
+ { uses V{ T{ vreg-use f 0 } } }
{ ranges V{ T{ live-range f 0 1 } } }
{ spill-to T{ spill-slot f 4 } }
}
{ vreg 2 }
{ start 1 }
{ end 5 }
- { uses V{ 1 5 } }
+ { uses V{ T{ vreg-use f 1 } T{ vreg-use f 5 } } }
{ ranges V{ T{ live-range f 1 5 } } }
{ reload-from T{ spill-slot f 4 } }
}
{ vreg 2 }
{ start 0 }
{ end 5 }
- { uses V{ 0 1 5 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } T{ vreg-use f 5 } } }
{ ranges V{ T{ live-range f 0 5 } } }
} 0 split-for-spill
] unit-test
{ vreg 3 }
{ start 0 }
{ end 1 }
- { uses V{ 0 } }
+ { uses V{ T{ vreg-use f 0 } } }
{ ranges V{ T{ live-range f 0 1 } } }
{ spill-to T{ spill-slot f 8 } }
}
{ vreg 3 }
{ start 20 }
{ end 30 }
- { uses V{ 20 30 } }
+ { uses V{ T{ vreg-use f 20 } T{ vreg-use f 30 } } }
{ ranges V{ T{ live-range f 20 30 } } }
{ reload-from T{ spill-slot f 8 } }
}
{ vreg 3 }
{ start 0 }
{ end 30 }
- { uses V{ 0 20 30 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 20 } T{ vreg-use f 30 } } }
{ ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
} 10 split-for-spill
] unit-test
{ reg 1 }
{ start 1 }
{ end 15 }
- { uses V{ 1 3 7 10 15 } }
+ { uses V{ T{ vreg-use f 1 } T{ vreg-use f 3 } T{ vreg-use f 7 } T{ vreg-use f 10 } T{ vreg-use f 15 } } }
}
T{ live-interval
{ vreg 2 }
{ reg 2 }
{ start 3 }
{ end 8 }
- { uses V{ 3 4 8 } }
+ { uses V{ T{ vreg-use f 3 } T{ vreg-use f 4 } T{ vreg-use f 8 } } }
}
T{ live-interval
{ vreg 3 }
{ reg 3 }
{ start 3 }
{ end 10 }
- { uses V{ 3 10 } }
+ { uses V{ T{ vreg-use f 3 } T{ vreg-use f 10 } } }
}
}
}
{ vreg 1 }
{ start 5 }
{ end 5 }
- { uses V{ 5 } }
+ { uses V{ T{ vreg-use f 5 } } }
}
spill-status
] unit-test
{ reg 1 }
{ start 1 }
{ end 15 }
- { uses V{ 1 } }
+ { uses V{ T{ vreg-use f 1 } } }
}
T{ live-interval
{ vreg 2 }
{ reg 2 }
{ start 3 }
{ end 8 }
- { uses V{ 3 8 } }
+ { uses V{ T{ vreg-use f 3 } T{ vreg-use f 8 } } }
}
}
}
{ vreg 3 }
{ start 5 }
{ end 5 }
- { uses V{ 5 } }
+ { uses V{ T{ vreg-use f 5 } } }
}
spill-status
] unit-test
{ vreg 1 }
{ start 0 }
{ end 100 }
- { uses V{ 0 100 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
{ ranges V{ T{ live-range f 0 100 } } }
}
}
{ vreg 1 }
{ start 0 }
{ end 10 }
- { uses V{ 0 10 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } } }
{ ranges V{ T{ live-range f 0 10 } } }
}
T{ live-interval
{ vreg 2 }
{ start 11 }
{ end 20 }
- { uses V{ 11 20 } }
+ { uses V{ T{ vreg-use f 11 } T{ vreg-use f 20 } } }
{ ranges V{ T{ live-range f 11 20 } } }
}
}
{ vreg 1 }
{ start 0 }
{ end 100 }
- { uses V{ 0 100 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
{ ranges V{ T{ live-range f 0 100 } } }
}
T{ live-interval
{ vreg 2 }
{ start 30 }
{ end 60 }
- { uses V{ 30 60 } }
+ { uses V{ T{ vreg-use f 30 } T{ vreg-use f 60 } } }
{ ranges V{ T{ live-range f 30 60 } } }
}
}
{ vreg 1 }
{ start 0 }
{ end 100 }
- { uses V{ 0 100 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
{ ranges V{ T{ live-range f 0 100 } } }
}
T{ live-interval
{ vreg 2 }
{ start 30 }
{ end 200 }
- { uses V{ 30 200 } }
+ { uses V{ T{ vreg-use f 30 } T{ vreg-use f 200 } } }
{ ranges V{ T{ live-range f 30 200 } } }
}
}
{ vreg 1 }
{ start 0 }
{ end 100 }
- { uses V{ 0 100 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
{ ranges V{ T{ live-range f 0 100 } } }
}
T{ live-interval
{ vreg 2 }
{ start 30 }
{ end 100 }
- { uses V{ 30 100 } }
+ { uses V{ T{ vreg-use f 30 } T{ vreg-use f 100 } } }
{ ranges V{ T{ live-range f 30 100 } } }
}
}
{ vreg 1 }
{ start 0 }
{ end 20 }
- { uses V{ 0 10 20 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } T{ vreg-use f 20 } } }
{ ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
}
T{ live-interval
{ vreg 2 }
{ start 0 }
{ end 20 }
- { uses V{ 0 10 20 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } T{ vreg-use f 20 } } }
{ ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
}
T{ live-interval
{ vreg 3 }
{ start 4 }
{ end 8 }
- { uses V{ 6 } }
+ { uses V{ T{ vreg-use f 6 } } }
{ ranges V{ T{ live-range f 4 8 } } }
}
T{ live-interval
{ vreg 4 }
{ start 4 }
{ end 8 }
- { uses V{ 8 } }
+ { uses V{ T{ vreg-use f 8 } } }
{ ranges V{ T{ live-range f 4 8 } } }
}
{ vreg 5 }
{ start 4 }
{ end 8 }
- { uses V{ 8 } }
+ { uses V{ T{ vreg-use f 8 } } }
{ ranges V{ T{ live-range f 4 8 } } }
}
}
{ vreg 1 }
{ start 0 }
{ end 10 }
- { uses V{ 0 6 10 } }
+ { uses V{ T{ vreg-use f 0 } T{ vreg-use f 6 } T{ vreg-use f 10 } } }
{ ranges V{ T{ live-range f 0 10 } } }
}
{ vreg 5 }
{ start 2 }
{ end 8 }
- { uses V{ 8 } }
+ { uses V{ T{ vreg-use f 8 } } }
{ ranges V{ T{ live-range f 2 8 } } }
}
}
{ start 8 }
{ end 10 }
{ ranges V{ T{ live-range f 8 10 } } }
- { uses V{ 8 10 } }
+ { uses V{ T{ vreg-use f 8 } T{ vreg-use f 10 } } }
}
register-status
] unit-test
-! Copyright (C) 2008, 2009 Slava Pestov.
+! Copyright (C) 2008, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: namespaces kernel assocs accessors sequences math math.order fry
combinators binary-search compiler.cfg.instructions compiler.cfg.registers
C: <live-range> live-range
+SYMBOLS: +def+ +use+ +memory+ ;
+
+TUPLE: vreg-use n type ;
+
+C: <vreg-use> vreg-use
+
TUPLE: live-interval
vreg
reg spill-to reload-from
2dup extend-range?
[ extend-range ] [ add-new-range ] if ;
-GENERIC: operands-in-registers? ( insn -- ? )
-
-M: vreg-insn operands-in-registers? drop t ;
-
-M: partial-sync-insn operands-in-registers? drop f ;
-
-: add-def ( insn live-interval -- )
- [ insn#>> ] [ uses>> ] bi* push ;
-
-: add-use ( insn live-interval -- )
- ! Every use is a potential def, no SSA here baby!
- over operands-in-registers? [ add-def ] [ 2drop ] if ;
+: add-use ( insn live-interval type -- )
+ dup +memory+ eq? [ 3drop ] [
+ swap [ [ insn#>> ] dip <vreg-use> ] dip
+ uses>> push
+ ] if ;
: <live-interval> ( vreg -- live-interval )
\ live-interval new
: block-to ( bb -- n ) instructions>> last insn#>> ;
-M: live-interval hashcode*
- nip [ start>> ] [ end>> 1000 * ] bi + ;
-
! Mapping from vreg to live-interval
SYMBOL: live-intervals
M: insn compute-live-intervals* drop ;
-: handle-output ( insn vreg -- )
- live-interval
- [ [ insn#>> ] dip shorten-range ] [ add-def ] 2bi ;
+: handle-output ( insn vreg type -- )
+ [ live-interval ] dip
+ [ drop [ insn#>> ] dip shorten-range ] [ add-use ] 3bi ;
-: handle-input ( insn vreg -- )
- live-interval
- [ [ [ basic-block get block-from ] dip insn#>> ] dip add-range ] [ add-use ] 2bi ;
+: handle-input ( insn vreg type -- )
+ [ live-interval ] dip
+ [ drop [ [ basic-block get block-from ] dip insn#>> ] dip add-range ]
+ [ add-use ]
+ 3bi ;
: handle-temp ( insn vreg -- )
live-interval
- [ [ insn#>> dup ] dip add-range ] [ add-use ] 2bi ;
+ [ [ insn#>> dup ] dip add-range ] [ +def+ add-use ] 2bi ;
M: vreg-insn compute-live-intervals*
- [ dup defs-vreg [ handle-output ] with when* ]
- [ dup uses-vregs [ handle-input ] with each ]
+ [ dup defs-vreg [ +def+ handle-output ] with when* ]
+ [ dup uses-vregs [ +use+ handle-input ] with each ]
+ [ dup temp-vregs [ handle-temp ] with each ]
+ tri ;
+
+M: partial-sync-insn compute-live-intervals*
+ [ dup defs-vreg [ +use+ handle-output ] with when* ]
+ [ dup uses-vregs [ +memory+ handle-input ] with each ]
[ dup temp-vregs [ handle-temp ] with each ]
tri ;