M: gc-map-insn clone call-next-method [ clone ] change-gc-map ;
-TUPLE: gc-map scrub-d check-d scrub-r check-r gc-roots derived-roots ;
+TUPLE: gc-map scrub-d scrub-r gc-roots derived-roots ;
: <gc-map> ( -- gc-map ) gc-map new ;
USING: assocs compiler.cfg help.markup help.syntax ;
IN: compiler.cfg.stacks.map
+HELP: initial-state
+{ $description "Initially the stack bottom is at 0 for both the data and retain stacks and no replaces have been registered." } ;
+
HELP: trace-stack-state
{ $values { "cfg" cfg } { "assoc" assoc } }
{ $description "Outputs an assoc with the instruction numbers as keys and as values two tuples of the data and retain stacks shapes before that instruction. All instructions in the cfg gets numbered as a side-effect." } ;
-USING: compiler.cfg compiler.cfg.instructions help.markup help.syntax sequences
-strings ;
+USING: compiler.cfg compiler.cfg.instructions compiler.cfg.stacks.map
+help.markup help.syntax sequences strings ;
IN: compiler.cfg.stacks.vacant
ARTICLE: "compiler.cfg.stacks.vacant" "Uninitialized/overinitialized stack location analysis"
}
"The GC check runs before stack locations 0 and 1 have been initialized, and so the GC needs to scrub them so that they don't get traced. This is achieved by computing uninitialized locations with a dataflow analysis, and recording the information in GC maps. The call_frame_slot_visitor object in vm/slot_visitor.hpp reads this information from GC maps and performs the scrubbing." ;
-! HELP: initial-state
-! { $description "Initially the stack bottom is at 0 for both the data and retain stacks and no replaces have been registered." } ;
+HELP: fill-gc-maps
+{ $values { "cfg" cfg } }
+{ $description "Populates the scrub-d, check-d, scrub-r and check-r slots of all gc maps in the cfg." } ;
+
+HELP: state>gc-data
+{ $values { "state" } { "gc-data" } }
+{ $description "Takes a stack state on the format given by " { $link trace-stack-state } " and emits an array containing two bit-patterns with locations on the data and retain stacks to scrub." } ;
HELP: vacant>bits
{ $values
}
} ;
-HELP: overinitialized>bits
-{ $values
- { "overinitialized" "sequence of overinitialized stack locations" }
- { "bits" "sequence of 1:s and 0:s" }
-}
-{ $description "Converts a sequence of overinitialized stack locations to the pattern of 1:s and 0:s that can be put in the " { $slot "check-d" } " and " { $slot "check-r" } " slots of a " { $link gc-map } ". 0:s are initialized locations and 0:s are empty ones. First element is stack location -1,second -2 and so on." } ;
-
-HELP: fill-gc-maps
-{ $values { "cfg" cfg } }
-{ $description "Populates the scrub-d, check-d, scrub-r and check-r slots of all gc maps in the cfg." } ;
-
ABOUT: "compiler.cfg.stacks.vacant"
IN: compiler.cfg.stacks.vacant.tests
{
- { { { } { 0 0 0 } } { { } { 0 } } }
+ { { } { } }
} [
{ { 4 { 3 2 1 -3 0 -2 -1 } } { 0 { -1 } } } state>gc-data
] unit-test
-! Replace -1, then gc. Peek is ok here because the -1 should be
-! checked.
-{ { 0 } } [
- V{
- T{ ##replace { src 10 } { loc D -1 } }
- T{ ##alien-invoke { gc-map T{ gc-map { scrub-d { } } } } }
- T{ ##peek { dst 0 } { loc D -1 } }
- }
- [ insns>cfg fill-gc-maps ]
- [ second gc-map>> check-d>> ] bi
-] unit-test
-
-! Replace -1, then gc. Peek is ok here because the -1 should be
-! checked.
-{ { 0 } } [
- V{
- T{ ##replace { src 10 } { loc D -1 } }
- T{ ##alien-invoke { gc-map T{ gc-map { scrub-d { } } } } }
- T{ ##peek { dst 0 } { loc D -1 } }
- }
- [ insns>cfg fill-gc-maps ]
- [ second gc-map>> check-d>> ] bi
+{ { { 1 0 0 } { 0 } } } [
+ { { 3 { 0 } } { 1 { } } } state>gc-data
] unit-test
! visit-insn should set the gc info.
[ '[ _ 0 -rot set-nth ] each ] keep
] if-empty ;
-: stack>overinitialized ( stack -- seq )
- second [ 0 < ] filter ;
-
-: overinitialized>bits ( overinitialized -- bits )
- [ neg 1 - ] map vacant>bits ;
-
-: stack>scrub-and-check ( stack -- pair )
- [ stack>vacant vacant>bits ]
- [ stack>overinitialized overinitialized>bits ] bi 2array ;
-
! Operations on the analysis state
: state>gc-data ( state -- gc-data )
- [ stack>scrub-and-check ] map ;
+ [ stack>vacant vacant>bits ] map ;
: set-gc-map ( state gc-map -- )
- swap state>gc-data concat
- { >>scrub-d >>check-d >>scrub-r >>check-r } write-slots ;
+ swap state>gc-data { >>scrub-d >>scrub-r } write-slots ;
+ ! swap state>gc-data { { } { } } append
+ ! { >>scrub-d >>scrub-r >>check-d >>check-r } write-slots ;
: fill-gc-maps ( cfg -- )
[ trace-stack-state ] [ cfg>insns [ gc-map-insn? ] filter ] bi
{ $list
"scrubbed data stack locations"
"scrubbed retain stack locations"
- "checked data stack locations"
- "checked retain stack locations"
"GC root spill slots"
}
}
"uint[] return addresses"
"uint largest scrubbed data stack location"
"uint largest scrubbed retain stack location"
- "uint largest checked data stack location"
- "uint largest checked retain stack location"
"uint largest GC root spill slot"
"uint largest derived root spill slot"
"int number of return addresses"
} ;
HELP: emit-gc-info-bitmaps
-{ $values { "scrub-and-check-counts" "counts of the five different types of gc checks" } }
+{ $values { "counts" "counts of the three different types of gc checks" } }
{ $description "Emits the scrub location data in all gc-maps registered in the " { $link gc-maps } " variable to the make sequence being created. The result is a concatenation of all datastack scrub locations, retainstack scrub locations and gc root locations converted into a byte-array. Given that byte-array and knowledge of the number of scrub locations, the original gc-map can be reconstructed." } ;
HELP: emit-scrub
[
100 <byte-array> %
- ! The below data is 46 bytes -- 14 bytes padding needed to
+ ! The below data is 38 bytes -- 6 bytes padding needed to
! align
- 14 <byte-array> %
+ 6 <byte-array> %
! Bitmap - 2 bytes
?{
! Return addresses
uint-array{ 100 } underlying>> %
- ! GC info footer - 28 bytes
+ ! GC info footer - 20 bytes
S{ vm:gc-info
{ scrub-d-count 5 }
{ scrub-r-count 2 }
- { check-d-count 0 }
- { check-r-count 0 }
{ gc-root-count 4 }
{ derived-root-count 3 }
{ return-address-count 1 }
] with-variable
] unit-test
- ! scrub-d scrub-r check-d check-r gc-roots
- { { 0 0 0 0 5 } } [
+ ! scrub-d scrub-r gc-roots
+ { { 0 0 5 } } [
T{ stack-frame { spill-area-base 0 } } stack-frame [
T{ gc-map
{ gc-roots {
] with-variable
] unit-test
- ! scrub-d scrub-r check-d check-r gc-roots
- { { 0 0 0 0 9 } } [
+ ! scrub-d scrub-r gc-roots
+ { { 0 0 9 } } [
T{ stack-frame { spill-area-base 32 } } stack-frame [
T{ gc-map
{ gc-roots {
! gc-map-needed?
{ t t } [
T{ gc-map { scrub-d { 0 1 1 1 0 } } { scrub-r { 1 0 } } } gc-map-needed?
- T{ gc-map { check-d { 0 1 1 1 } } } gc-map-needed?
+ T{ gc-map { scrub-d { 0 1 1 1 } } } gc-map-needed?
] unit-test
! emit-scrub
! emit-gc-info-bitmaps
{
- { 4 2 0 0 0 }
+ { 4 2 0 }
V{ 1 }
} [
{ T{ gc-map { scrub-d { 0 1 1 1 } } { scrub-r { 1 1 } } } } gc-maps set
] unit-test
{
- { 1 0 1 0 0 }
- V{ 3 }
+ { 1 0 0 }
+ V{ 1 }
} [
- { T{ gc-map { scrub-d { 0 } } { check-d { 0 } } } } gc-maps set
+ { T{ gc-map { scrub-d { 0 } } } } gc-maps set
[ emit-gc-info-bitmaps ] V{ } make
] unit-test
[ emit-base-tables ] B{ } make
] unit-test
-
! serialize-gc-maps
{
B{ 0 0 0 0 }
] unit-test
{
- B{
- 17 123 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 1 0 0 0
- }
+ B{ 17 123 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 }
} [
{ 123 } return-addresses set
{ T{ gc-map { scrub-d { 0 1 1 1 0 } } } } gc-maps set
serialize-gc-maps
] unit-test
-! gc-info + ret-addr + 9bits (5+2+2) = 28 + 4 + 2 = 34
-{ 34 } [
+! gc-info + ret-addr + 9bits (5+2+2) = 20 + 4 + 2 = 26
+{ 26 } [
{
T{ gc-map
{ scrub-d { 0 1 1 1 0 } }
serialize-gc-maps length
] unit-test
-! gc-info + ret-addr + 3 base-pointers + 9bits = 28 + 4 + 12 + 2 = 46
-{ 46 } [
+! gc-info + ret-addr + 3 base-pointers + 9bits = 20 + 4 + 12 + 2 = 38
+{ 38 } [
{
T{ gc-map
{ scrub-d { 0 1 1 1 0 } }
! Copyright (C) 2011 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors arrays assocs bit-arrays classes.tuple
-combinators compiler.codegen.relocation cpu.architecture fry
-kernel layouts make math math.order namespaces sequences
-sequences.generalizations ;
+compiler.codegen.relocation cpu.architecture fry kernel layouts make math
+math.order namespaces sequences ;
IN: compiler.codegen.gc-maps
SYMBOLS: return-addresses gc-maps ;
: emit-gc-roots ( seqs -- n )
! seqs is a sequence of sequences of integers 0..n-1
- dup largest-spill-slot
- [ '[ _ integers>bits % ] each ] keep ;
+ dup largest-spill-slot [ '[ _ integers>bits % ] each ] keep ;
: emit-uint ( n -- )
building get push-uint ;
: gc-root-offsets ( gc-map -- offsets )
gc-roots>> [ gc-root-offset ] map ;
-: emit-gc-info-bitmaps ( -- scrub-and-check-counts )
+: emit-gc-info-bitmaps ( -- counts )
[
- gc-maps get {
- [ [ scrub-d>> ] map emit-scrub ]
- [ [ scrub-r>> ] map emit-scrub ]
- [ [ check-d>> ] map emit-scrub ]
- [ [ check-r>> ] map emit-scrub ]
- [ [ gc-root-offsets ] map emit-gc-roots ]
- } cleave 5 narray
+ gc-maps get
+ [ [ scrub-d>> ] map emit-scrub ]
+ [ [ scrub-r>> ] map emit-scrub ]
+ [ [ gc-root-offsets ] map emit-gc-roots ] tri 3array
] ?{ } make underlying>> % ;
: emit-base-table ( alist longest -- )
STRUCT: gc-info
{ scrub-d-count uint read-only }
{ scrub-r-count uint read-only }
- { check-d-count uint read-only }
- { check-r-count uint read-only }
{ gc-root-count uint read-only }
{ derived-root-count uint read-only }
{ return-address-count uint read-only } ;
{
"Each value is a two-tuple where:"
{ $list
- "The first element is a five-tuple containing the scrub patterns for the datastack, retainstack, then the check patterns for them and gc roots."
+ "The first element is a three-tuple containing the scrub patterns for the datastack, retainstack and gc roots."
"The second element is a sequence of derived roots for the callsite."
}
}
{ t } [
\ effects:<effect> word>gc-info scrub-bits
{
- ?{ t t t t f t t t t } ! 64-bit
- ?{ t t t t f f f f f t t t t } ! 32-bit
+ ?{ t t t f t t t t } ! 64-bit
+ ?{ t t t t f f f f f t t t t } ! 32-bit TODO
} member?
] unit-test
[ f ] [ {
[ [ scrub-d>> length ] map supremum ]
[ [ scrub-r>> length ] map supremum ]
- [ [ check-d>> length ] map supremum ]
- [ [ check-r>> length ] map supremum ]
[ [ gc-root-offsets ] map largest-spill-slot ]
[ [ derived-root-offsets ] map [ keys ] map largest-spill-slot ]
[ length ]
- } cleave 7 narray ] if-empty ;
+ } cleave 5 narray ] if-empty ;
! Like word>gc-info but uses the compiler
: word>gc-info-expected ( word -- seq/f )
c-direct-array-constructor execute( alien len -- seq ) ;
: bit-counts ( gc-info -- counts )
- struct-slot-values 5 head ;
+ struct-slot-values 3 head ;
: total-bitmap-bits ( gc-info -- n )
[ bit-counts sum ] [ return-address-count>> ] bi * ;
namespace factor {
// gc_info should be kept in sync with:
-// core/vm/vm.factor
+// basis/vm/vm.factor
struct gc_info {
uint32_t scrub_d_count;
uint32_t scrub_r_count;
- uint32_t check_d_count;
- uint32_t check_r_count;
uint32_t gc_root_count;
uint32_t derived_root_count;
uint32_t return_address_count;
cell callsite_bitmap_size() {
- return
- scrub_d_count +
- scrub_r_count +
- check_d_count +
- check_r_count +
- gc_root_count;
+ return scrub_d_count + scrub_r_count + gc_root_count;
}
cell total_bitmap_size() {
return base + index * scrub_r_count;
}
- cell callsite_check_d(cell index) {
- cell base =
- return_address_count * scrub_d_count +
- return_address_count * scrub_r_count;
- return base + index * check_d_count;
- }
-
- cell callsite_check_r(cell index) {
- cell base =
- return_address_count * scrub_d_count +
- return_address_count * scrub_r_count +
- return_address_count * check_d_count;
- return base + index * check_r_count;
- }
-
cell callsite_gc_roots(cell index) {
cell base =
return_address_count * scrub_d_count +
- return_address_count * scrub_r_count +
- return_address_count * check_d_count +
- return_address_count * check_r_count;
+ return_address_count * scrub_r_count;
return base + index * gc_root_count;
}