HELP: compute-insns
{ $values { "cfg" cfg } }
-{ $description "Computes a mapping from vregs to the instructions that define them and store the result in the " { $link insns } " variable." } ;
+{ $description "Computes a mapping from vregs to the instructions that define them and store the result in the " { $link insns } " variable. The " { $link insn-of } " word can then be used to access the assoc." } ;
HELP: defs-vregs
{ $values { "insn" insn } { "seq" sequence } }
-USING: alien arrays assocs classes compiler.cfg compiler.cfg.value-numbering
-compiler.codegen.gc-maps cpu.architecture help.markup help.syntax kernel
-layouts sequences slots.private system ;
+USING: alien arrays assocs classes compiler.cfg compiler.cfg.ssa.destruction
+compiler.cfg.value-numbering compiler.codegen.gc-maps cpu.architecture
+help.markup help.syntax kernel layouts sequences slots.private system ;
IN: compiler.cfg.instructions
HELP: ##alien-invoke
HELP: ##no-tco
{ $class-description "A dummy instruction that simply inhibits TCO." } ;
+HELP: ##parallel-copy
+{ $class-description "An instruction for performing multiple copies. It allows for optimizations or (or prunings) if more than one source or destination vreg is the same. They are transformed into " { $link ##copy } " instructions in " { $link destruct-ssa } ". It has the following slots:"
+ { $table
+ { { $slot "values" } { "An assoc mapping source vregs to destinations." } }
+ }
+} ;
+
HELP: ##peek
{ $class-description
"Copies a value from a stack location to a machine register."
{ $class-description "Instruction that copies an 8 byte value from a XMM register to a memory location addressed by a normal register. This instruction is often turned into a cheaper " { $link ##store-memory } " instruction in the " { $link value-numbering } " pass." } ;
HELP: ##vector>scalar
-{ $class-description "This instruction is very similar to " { $link ##copy } "." }
+{ $class-description
+ "This instruction is very similar to " { $link ##copy } "."
+ { $table
+ { { $slot "dst" } { "destination vreg" } }
+ { { $slot "src" } { "source vreg" } }
+ { { $slot "rep" } { "representation for the source vreg" } }
+ }
+}
+{ $notes "The two vregs must not necessarily share the same representation." }
{ $see-also %vector>scalar } ;
HELP: ##write-barrier
"Instruction classes for moving values around:"
{ $subsections
##copy
+ ##parallel-copy
##peek
##reload
##replace
##load-integer
##load-reference
}
-"Floating point instructions:"
+"Floating point SIMD instructions:"
{ $subsections
##add-float
##div-float
--- /dev/null
+USING: compiler.cfg.instructions compiler.tree help.markup help.syntax
+math.vectors ;
+IN: compiler.cfg.intrinsics.simd
+
+HELP: emit-simd-v+
+{ $values { "node" node } }
+{ $description "Emits instructions for SIMD vector addition." }
+{ $see-also ##add-vector v+ } ;
USING: assocs compiler.cfg compiler.cfg.instructions
-compiler.cfg.linear-scan.live-intervals compiler.cfg.registers heaps help.markup
-help.syntax math ;
+compiler.cfg.linear-scan.live-intervals
+compiler.cfg.linear-scan.allocation.state compiler.cfg.liveness
+compiler.cfg.registers heaps help.markup help.syntax math ;
IN: compiler.cfg.linear-scan.assignment
HELP: add-pending
{ $values { "gc-map" gc-map } }
{ $description "Assigns spill slots for all gc roots in a gc map." } ;
+HELP: assign-registers-in-block
+{ $values { "bb" basic-block } }
+{ $description "Assigns registers and also inserts " { $link ##reload } " and " { $link ##spill } " instructions." } ;
+
HELP: assign-registers-in-insn
{ $values { "insn" insn } }
{ $description "Assigns physical registers and spill slots for the virtual registers used by the instruction." } ;
{ $var-description "Mapping from basic blocks to predecessors to values which are live on a particular incoming edge." } ;
HELP: machine-live-ins
-{ $var-description "Mapping from basic blocks to values which are live at the start on all incoming CFG edges." } ;
+{ $var-description "Mapping from basic blocks to values which are live at the start on all incoming CFG edges. It's like " { $link live-ins } " except the registers are physical instead of virtual." } ;
HELP: machine-live-outs
{ $var-description "Mapping from " { $link basic-block } " to an " { $link assoc } " of pairs which are the values that are live at the end. The keys of the pairs are virtual registers and the values are either real registers or spill slots." } ;
{ $var-description { $link min-heap } " of live intervals which still need a register allocation." } ;
HELP: vreg>reg
-{ $values { "vreg" "virtual register" } { "reg" "register" } }
-{ $description "If a live vreg is not in the pending set, then it must have been spilled." }
-{ $errors "Can throw a " { $link bad-vreg } " error." }
-{ $see-also pending-interval-assoc } ;
+{ $values { "vreg" "virtual register" } { "reg/spill-slot" "a register or a spill slot" } }
+{ $description "Translates a virtual register to a physical one. If the vreg is not in the pending set, then it must have been spilled and its spill slot is returned." }
+{ $errors "Can throw a " { $link bad-vreg } " error if the vreg is not in the " { $link pending-interval-assoc } " and also doesn't have a spill slot registered." }
+{ $see-also lookup-spill-slot pending-interval-assoc } ;
HELP: vregs>regs
{ $values { "vregs" "a sequence of virtual registers" } { "assoc" assoc } }
ARTICLE: "compiler.cfg.linear-scan.assignment" "Assigning registers to live intervals"
"The " { $vocab-link "compiler.cfg.linear-scan.assignment" } " assigns registers to live intervals." $nl
"Pending intervals:"
-{ $subsections add-pending pending-interval-assoc remove-pending }
+{ $subsections
+ activate-interval
+ add-pending
+ pending-interval-assoc
+ remove-pending
+}
"Vreg transformations:"
{ $subsections vreg>reg vreg>spill-slot vregs>regs } ;
: remove-pending ( live-interval -- )
vreg>> pending-interval-assoc get delete-at ;
-:: vreg>reg ( vreg -- reg )
+:: vreg>reg ( vreg -- reg/spill-slot )
vreg leader :> leader
leader pending-interval-assoc get at* [
drop leader vreg rep-of lookup-spill-slot
: compute-live-out ( bb -- )
[ live-out keys vregs>regs ] keep machine-live-outs get set-at ;
-: init-assignment ( live-intervals -- )
- [ [ start>> ] map ] keep zip >min-heap unhandled-intervals set
- <min-heap> pending-interval-heap set
- H{ } clone pending-interval-assoc set
- H{ } clone machine-live-ins set
- H{ } clone machine-edge-live-ins set
- H{ } clone machine-live-outs set ;
-
: heap-pop-while ( heap quot: ( key -- ? ) -- values )
'[ dup heap-empty? [ f f ] [ dup heap-peek @ ] if ]
[ over heap-pop* ] produce 2nip ; inline
] each
] V{ } make
] change-instructions drop
+
bb compute-live-out ;
+: init-assignment ( live-intervals -- )
+ [ [ start>> ] map ] keep zip >min-heap unhandled-intervals set
+ <min-heap> pending-interval-heap set
+ H{ } clone pending-interval-assoc set
+ H{ } clone machine-live-ins set
+ H{ } clone machine-edge-live-ins set
+ H{ } clone machine-live-outs set ;
+
: assign-registers ( cfg live-intervals -- )
init-assignment
linearization-order [ kill-block?>> not ] filter
-USING: compiler.cfg.instructions help.markup help.syntax ;
+USING: compiler.cfg compiler.cfg.instructions
+compiler.cfg.linear-scan.allocation cpu.architecture help.markup help.syntax
+math sequences ;
IN: compiler.cfg.linear-scan.live-intervals
+HELP: <live-interval>
+{ $values
+ { "vreg" "virtual register" }
+ { "reg-class" "register class" }
+ { "live-interval" live-interval-state }
+}
+{ $description "Creates a new live interval for a virtual register. Initially the range is empty." } ;
+
+HELP: block-from
+{ $values { "bb" basic-block } { "n" integer } }
+{ $description "The instruction number immediately preceeding this block." } ;
+
+HELP: finish-live-intervals
+{ $values { "live-intervals" sequence } { "seq" sequence } }
+{ $description "Since live intervals are computed in a backward order, we have to reverse some sequences, and compute the start and end." } ;
+
+HELP: live-interval-state
+{ $class-description "A class encoding the \"liveness\" of a virtual register. It has the following slots:"
+ { $table
+ { { $slot "vreg" } { "The vreg this live interval state is bound to." } }
+ {
+ { $slot "reg" }
+ { "The allocated register, set in the " { $link allocate-registers } " step." }
+ }
+ {
+ { $slot "spill-to" }
+ { { $link spill-slot } " to use for spilling, if it needs to be spilled." }
+ }
+ { { $slot "start" } { "Earliest insn# where the interval is live." } }
+ { { $slot "end" } { "Latest insn# where the interval is live." } }
+ {
+ { $slot "ranges" }
+ { "Inclusive ranges where the live interval is live. This is because the [start,end] interval can have gaps." }
+ }
+ {
+ { $slot "uses" } { "sequence of references to instructions that use the register in the live interval." }
+ }
+ {
+ { $slot "reg-class" }
+ { "Register class of the interval, either "
+ { $link int-regs } " or " { $link float-regs } "." }
+
+ }
+ }
+}
+{ $notes "The " { $slot "uses" } " and " { $slot "ranges" } " will never be empty because then the interval would be unused." } ;
+
+
HELP: live-intervals
{ $var-description "Mapping from vreg to " { $link live-interval-state } "." } ;
HELP: sync-point
-{ $class-description "A location where all registers have to be spilled. It has the following slots:"
+{ $class-description "A location where all registers have to be spilled. For example when garbage collection is run or an alien ffi call is invoked. Figuring out where in the " { $link cfg } " the sync points are is done in the " { $link compute-live-intervals } " step. The tuple has the following slots:"
{ $table
{ { $slot "n" } { "Set from an instructions sequence number." } }
}
}
{ $see-also insn } ;
-HELP: live-interval-state
-{ $class-description "A class encoding the \"liveness\" of a virtual register." } ;
-
-HELP: <live-interval>
-{ $values
- { "vreg" "virtual register" }
- { "reg-class" "register class" }
- { "live-interval" live-interval-state }
-}
-{ $description "Creates a new live interval for a virtual register. Initially the range is empty." } ;
+HELP: sync-points
+{ $var-description "Sequence of sync points." } ;
USING: accessors assocs binary-search combinators
compiler.cfg.def-use compiler.cfg.instructions
compiler.cfg.linearization compiler.cfg.liveness
-compiler.cfg.registers compiler.cfg.ssa.destruction.leaders
-cpu.architecture fry kernel locals math math.order namespaces
-sequences ;
+compiler.cfg.registers compiler.cfg.ssa.destruction.leaders cpu.architecture
+fry kernel locals math math.intervals math.order namespaces sequences ;
IN: compiler.cfg.linear-scan.live-intervals
TUPLE: live-range from to ;
C: <sync-point> sync-point
-! Sequence of sync points
SYMBOL: sync-points
GENERIC: compute-sync-points* ( insn -- )
M: insn compute-sync-points* drop ;
: compute-live-intervals-step ( bb -- )
- dup kill-block?>> [ drop ] [
- {
- [ block-from from set ]
- [ block-to to set ]
- [ handle-live-out ]
- [
- instructions>> <reversed> [
- [ compute-live-intervals* ]
- [ compute-sync-points* ]
- bi
- ] each
- ]
- } cleave
- ] if ;
+ {
+ [ block-from from set ]
+ [ block-to to set ]
+ [ handle-live-out ]
+ [
+ instructions>> <reversed> [
+ [ compute-live-intervals* ]
+ [ compute-sync-points* ]
+ bi
+ ] each
+ ]
+ } cleave ;
: init-live-intervals ( -- )
H{ } clone live-intervals set
dup start>> -1 = [ bad-live-interval ] [ drop ] if ;
: finish-live-intervals ( live-intervals -- seq )
- ! Since live intervals are computed in a backward order, we have
- ! to reverse some sequences, and compute the start and end.
values dup [
{
[ [ { } like reverse! ] change-ranges drop ]
: compute-live-intervals ( cfg -- live-intervals sync-points )
init-live-intervals
- linearization-order <reversed> [ compute-live-intervals-step ] each
+ linearization-order <reversed> [ kill-block?>> not ] filter
+ [ compute-live-intervals-step ] each
live-intervals get finish-live-intervals
sync-points get ;
{ $var-description "Mapping from vregs to base pointer vregs. If the vreg doesn't have a base pointer, then it will be mapped to " { $link f } "." }
{ $see-also lookup-base-pointer } ;
+HELP: compute-live-sets
+{ $values { "cfg" cfg } }
+{ $description "Main entry point for vocab. Pass must only be run after representation selection. In this pass " { $slot "gc-roots" } " are set." } ;
+
+HELP: edge-live-ins
+{ $var-description "Assoc mapping basic blocks to sequences of sets of vregs; each sequence is in correspondence with a predecessor." } ;
+
HELP: fill-gc-map
{ $values { "live-set" assoc } { "gc-map" gc-map } }
{ $description "Assigns values to the " { $slot "gc-roots" } " and " { $slot "derived-roots" } " slots of the " { $link gc-map } ". Does nothing if the " { $link select-representations } " pass hasn't ran." } ;
{ $description "Tries to figure out what the base pointer for a vreg is. Can't use cache here because of infinite recursion inside the quotation passed to cache" }
{ $see-also base-pointers } ;
-HELP: edge-live-ins
-{ $var-description "Assoc mapping basic blocks to sequences of sets of vregs; each sequence is in correspondence with a predecessor." } ;
-
ARTICLE: "compiler.cfg.liveness" "Liveness analysis"
"Similar to http://en.wikipedia.org/wiki/Liveness_analysis, with three additions:"
$nl
"With SSA, it is not sufficient to have a single live-in set per block. There is also an edge-live-in set per edge, consisting of phi inputs from each predecessor."
"Liveness analysis annotates call sites with GC maps indicating the spill slots in the stack frame that contain tagged pointers, and thus have to be visited if a GC occurs inside the call."
{ "GC maps can contain derived pointers. A derived pointer is a pointer into the middle of a data heap object. Each derived pointer has a base pointer, to keep it up to date when objects are moved by the garbage collector. This extends live intervals and inserts new " { $link ##phi } " instructions." }
-} ;
+}
+$nl
+"Querying liveness data:"
+{ $subsections live-in live-in? live-out live-out? } ;
ABOUT: "compiler.cfg.liveness"
HELP: parallel-copy-rep
{ $values { "mapping" { $link assoc } " of { dst src } virtual register pairs" } { "insns" array } }
-{ $description "Creates " { $link ##copy } " instructions." } ;
+{ $description "Creates " { $link ##copy } " instructions. Representation selection must have been run previously." } ;
ARTICLE: "compiler.cfg.parallel-copy" "Parallel copy"
"Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency http://hal.archives-ouvertes.fr/docs/00/34/99/25/PDF/OutSSA-RR.pdf, Algorithm 1" ;
{ $description "Gets the representation for a virtual register. This word cannot be called before representation selection has run; use any-rep for " { $link ##copy } " instructions and so on." }
{ $notes "Throws " { $link bad-vreg } " if the representation for the vreg isn't known." } ;
+HELP: representations
+{ $var-description "Mapping from vregs to their representations." } ;
+
HELP: set-rep-of
{ $values { "rep" representation } { "vreg" number } }
{ $description "Sets the representation for a virtual register." } ;
--- /dev/null
+USING: help.markup help.syntax ;
+IN: compiler.cfg.representations
+
+ARTICLE: "compiler.cfg.representations" "Virtual register representation selection" "Virtual register representation selection. This is where decisions about integer tagging and float and vector boxing are made. The appropriate conversion operations inserted after a cost analysis." ;
+
+ABOUT: "compiler.cfg.representations"
compiler.cfg.utilities ;
IN: compiler.cfg.representations
-! Virtual register representation selection. This is where
-! decisions about integer tagging and float and vector boxing
-! are made. The appropriate conversion operations inserted
-! after a cost analysis.
-
: select-representations ( cfg -- )
{
needs-loops
-USING: compiler.cfg.instructions help.markup help.syntax ;
+USING: compiler.cfg compiler.cfg.instructions
+compiler.cfg.ssa.destruction.private help.markup help.syntax ;
IN: compiler.cfg.ssa.destruction
+HELP: cleanup-cfg
+{ $values { "cfg" cfg } }
+{ $description "In this step, " { $link ##parallel-copy } " instructions are substituted with more concreete " { $link ##copy } " instructions. " { $link ##phi } " instructions are removed here." } ;
+
ARTICLE: "compiler.cfg.ssa.destruction" "SSA Destruction"
"Because of the design of the register allocator, this pass has three peculiar properties."
{ $list
IN: compiler.cfg.stacks.finalize
HELP: inserting-peeks
-{ $values { "from" basic-block } { "to" basic-block } { "assoc" assoc } }
+{ $values { "from" basic-block } { "to" basic-block } { "set" assoc } }
{ $description
"A peek is inserted on an edge if the destination anticipates the stack location, the source does not anticipate it and it is not available from the source in a register." } ;
HELP: inserting-replaces
-{ $values { "from" basic-block } { "to" basic-block } { "assoc" assoc } }
+{ $values { "from" basic-block } { "to" basic-block } { "set" assoc } }
{ $description
"A replace is inserted on an edge if two conditions hold:"
{ $list
{ $examples
{ $example
"USING: compiler.cfg.stacks.local compiler.cfg.registers compiler.cfg.debugger namespaces prettyprint ;"
- "{ { 3 0 } { 0 0 } } D 7 translate-local-loc ."
+ "D 7 { { 3 0 } { 0 0 } } translate-local-loc ."
"D 4"
}
}
} ;
HELP: emit-changes
+{ $values { "replaces" sequence } { "state" sequence } }
{ $description "Insert height and stack changes prior to the last instruction." } ;
HELP: inc-stack
{ $description "Creates a quotation which wraps " { $link call-effect-unsafe } "." } ;
HELP: call-effect-unsafe?
-{ $values { "cached-effect" "an effect or +unknown+" } { "effect" effect } { "?" "a boolean" } }
-{ $description "Checks if the given effect is safe with regards to the cached one." } ;
+{ $values { "quot" quotation } { "effect" effect } { "?" "a boolean" } }
+{ $description "Checks if the given effect is safe with regards to the quotation." } ;
HELP: update-inline-cache
{ $values { "word/quot" "word or quotation" } { "ic" inline-cache } }
projects / factor.git / commitdiff