8.10
3.2 Compiler Support
| (require cpsc411/compiler-lib) | package: cpsc411-lib |
This library provides support functions and parameters for implementing the CPSC411 project compiler.
3.2.1 Data Types
These data types are used in the implementation of the CPSC411 compiler for representing intermediate language constructs.
procedure
(dispoffset? v) → boolean?
v : any/c
A predicate that returns #t when v is a valid displacement
mode offset for x86-64.
Examples:
> (dispoffset? 0) #t
> (dispoffset? 1) #f
> (dispoffset? 2) #f
> (dispoffset? 3) #f
> (dispoffset? 4) #f
> (dispoffset? 8) #t
> (dispoffset? 8) #t
> (dispoffset? 15) #f
> (dispoffset? 16) #t
> (dispoffset? 17) #f
> (dispoffset? 'x) #f
A predicate that returns #t when v is a valid register on the
target machine, and #f otherwise.
Examples:
3.2.1.1 Labels
A predicate that returns #t when v is a valid label in
in the CPSC411 languages.
Examples:
> (label? 'L.start.1) #t
> (label? 'Lstart.1) #f
> (label? 'L.start1) #f
> (label? 'start.1) #f
> (label? "L.start.1") #f
procedure
(fresh-label [x]) → label?
x : (or/c string? symbol?) = 'tmp
Returns a fresh label, distinct from any label that has previously been
generated.
Assumes all other labels in the program have been generated using this
procedure, to ensure freshness.
Optionally, takes a base label to generate from.
Examples:
> (fresh-label) 'L.tmp.1
> (fresh-label) 'L.tmp.2
> (fresh-label) 'L.tmp.3
> (fresh-label 'meow) 'L.meow.4
> (fresh-label "hello") 'L.hello.5
procedure
(sanitize-label l) → string?
l : label?
Transform l into a string that is valid as a nasm label, escaping
any special characters.
Examples:
> (sanitize-label 'L.main.1) "L.main.1"
> (sanitize-label 'L.$!!@#*main.2) "L.$24$$21$$21$@#$2a$main.2"
3.2.1.2 Identifiers
A predicate that returns #t when v is a valid lexical
identifier in the CPSC411 languages.
Examples:
> (name? 'L.start.1) #t
> (name? 'Lstart.1) #t
> (name? 'L.start1) #t
> (name? 'start.1) #t
> (name? 'start) #t
> (name? 'x) #t
> (name? "L.start.1") #f
> (name? "x") #f
> (name? 5) #f
A predicate that return #t when v is a valid abstract location
in the CPSC411 languages.
Examples:
> (aloc? 0) #f
> (aloc? 'x) #f
> (aloc? 'x.1) #t
> (aloc? 'L.start.1) #f
> (aloc? 'Lstart.1) #t
> (aloc? 'L.start1) #f
> (aloc? 'start.1) #t
> (aloc? 'start) #f
> (aloc? 'x) #f
> (aloc? "L.start.1") #f
> (aloc? "x") #f
> (aloc? 5) #f
Returns a fresh aloc?, unique from every other aloc? that has
been generated by fresh.
It is not guaranteed to be unique when used in an arbitrary program, unless all
aloc?s in the program were generated using fresh.
Optionally takes a symbol v to represent the name part of the aloc?.
Examples:
> (fresh) 'tmp.1
> (fresh) 'tmp.2
> (fresh) 'tmp.3
> (fresh 'L.start.1) '.L.start.1.4
> (fresh 'L.start.1) '.L.start.1.5
3.2.1.3 Frame Variables
A predicate that returns #t when v is a valid frame variable.
Examples:
> (fvar? 0) #f
> (fvar? 'x) #f
> (fvar? 'x.1) #f
> (fvar? 'fv) #f
> (fvar? 'fv.1) #f
> (fvar? 'fv1) #t
> (fvar? 'fv2) #t
procedure
i : exact-nonnegative-integer?
Returns an fvar? with index i.
Examples:
procedure
v : fvar?
Returns the index component of an fvar?.
Examples:
> (fvar->index (make-fvar 1)) 1
> (fvar->index 'fv1) 1
3.2.1.4 Undead Sets
procedure
(undead-set? v) → boolean?
v : any/c
A predicate that returns #t when v is an undead set,
and #f otherwise.
Examples:
> (undead-set? '(a.1 b.2 c.3)) #t
> (undead-set? '(a.1 b.2 a.1)) #t
> (undead-set? '(5 3)) #f
procedure
(undead-set-tree? ust) → boolean?
ust : any/c
A predicate that returns #t when ust is an undead set tree,
and #f otherwise.
Examples:
> (undead-set-tree? '(a.1 b.2 c.3)) #t
> (undead-set-tree? '((a.1 b.2 c.3))) #t
> (undead-set-tree? '((a.1 b.2 c.3) (a.1 b.2 c.3) (a.1 b.2 c.3))) #t
> (undead-set-tree? '((a.1 b.2 c.3) ((a.1 b.2 c.3) (a.1 b.2 c.3) (a.1 b.2 c.3)))) #t
> (undead-set-tree? '((5 b.2 c.3) ((a.1 b.2 c.3) (a.1 b.2 c.3) (a.1 b.2 c.3)))) #f
procedure
(undead-set-tree/rloc? ust) → boolean?
ust : any/c
A predicate that returns #t when ust is an undead set tree
that might contain physical locations or abstract locations,and #f otherwise.
Examples:
> (undead-set-tree/rloc? '(a.1 b.2 c.3)) #t
> (undead-set-tree/rloc? '((a.1 b.2 c.3))) #t
> (undead-set-tree/rloc? '((a.1 b.2 c.3) (a.1 b.2 c.3) (a.1 b.2 c.3))) #t
> (undead-set-tree/rloc? '((a.1 b.2 c.3) ((a.1 b.2 c.3) (a.1 b.2 c.3) (a.1 b.2 c.3)))) #t
> (undead-set-tree/rloc? '((5 b.2 c.3) ((a.1 b.2 c.3) (a.1 b.2 c.3) (a.1 b.2 c.3)))) #f
> (undead-set-tree/rloc? '((rax rbx r8 c.3) ((a.1 r9 c.3) (a.1 b.2 c.3) (a.1 b.2 c.3)))) #t
3.2.2 Compilation Harness
This section describes abstractions for executing the compiler and compiled code in Racket.
procedure
(bin-format [type]) →
(or/c "elf64" "macho64" "win64") type : (or/c 'unix 'windows 'macosx) = (system-type)
Returns the binary format used by nasm to generate executable on the operating system
specified by type.
Defaults to the current system.
Assumes an x86-64 target machine.
Examples:
> (bin-format) "elf64"
> (bin-format 'macosx) "macho64"
> (bin-format 'unix) "elf64"
Returns additional linker flags for ld to generate a linked execute on the
operating system specified by type.
Defaults to the current system.
Examples:
> (ld-flags) '("-e" "start")
> (ld-flags 'macosx) '("-static" "-e" "start")
> (ld-flags 'unix) '("-e" "start")
value
start-label : string? = "start"
Defines the initial label used by the run-time system linker.
Returns the write system call number for the specified operating system.
Defaults to the current system.
Doesn’t work for Windows since Windows doesn’t support system calls.
Returns the exit system call number for the specified operating system.
Defaults to the current system.
Doesn’t work for Windows since Windows doesn’t support system calls.
Returns the mapped memory system call number for the specified operating system.
Defaults to the current system.
Doesn’t work for Windows since Windows doesn’t support system calls.
parameter
(current-pass-list) → (list-of (-> any/c any/c))
(current-pass-list passes) → void? passes : (list-of (-> any/c any/c))
= exn:fail
A parameter? that defines the list of compiler passes to use when
running compile or execute.
The list of procedures is composed in order, so the output of the n-th
procedure should match the input expected by the n+1 th.
Raises an error when accessed before being initialized with a valid pass list.
Examples:
> (current-pass-list) #f
> (parameterize ([current-pass-list (list (lambda (x) (displayln x)))]) (compile 'x)) x
> (current-pass-list (list (lambda (x) (displayln x)))) > (compile 'x) x
Compiles e using the current-pass-list, and returns the
resulting program.
Expects e to be a valid input program to the first pass in the current-pass-list.
parameter
(current-run/read) → (-> string? any/c)
(current-run/read run/read) → void? run/read : (-> string? any/c)
= nasm-run/read
Defines a default run-reader to be used with execute when none
is specified directly.
A run-reader, run/read, takes a string representing a complete x64 program in Intel syntax, capable of compiling via nasm, linking via ld, and running as a binary, and should return the result of the program as a Racket value. The default, nasm-run/read, compiles and executes the program and returns the result of the standard output as read by read.
See also nasm-run/exit-code, nasm-run/print-string, nasm-run/print-number, nasm-run/error-string, nasm-run/error-string+code, and nasm-run/observe.
procedure
v : any/c run/read : (-> string? any/c) = (current-run/read)
Compiles v using the current-pass-list and then runs the
program using the run/read argument, and returns the result.
The intention is that the program is compiled to assembly, then assembled with nasm, then linked, then the binary is executed and the result returned as a Racket value, enabling testing the end-to-end compiler.
Expects e to be a valid input program to the first pass in the current-pass-list, and the compiler to produce a valid input to the run/read procedure.
Examples:
> (require cpsc411/reference/a2-solution cpsc411/2c-run-time)
> (parameterize ([current-pass-list (list generate-x64 wrap-x64-run-time wrap-x64-boilerplate)]) (execute '(begin (set! rax 120)))) 120
> (parameterize ([current-pass-list (list implement-fvars generate-x64 wrap-x64-run-time wrap-x64-boilerplate)]) (execute '(begin (set! fv1 120) (set! rax fv1)))) 120
> (require cpsc411/reference/a1-solution)
> (parameterize ([current-pass-list (list generate-x64 wrap-x64-run-time wrap-x64-boilerplate)]) (execute '(begin (set! rax 120)) nasm-run/exit-code)) 120
Returns a run-reader that compiles and links its input to an
executable using nasm, and passes the executable path to runner to
be executed.
The runner is expected to run the executable, and return an observation.
This procedure performs additional error checking and cleans up temporary files before returning the observation.
procedure
(nasm-run/exit-code s) → (in-range/c 0 256)
s : string?
A run-reader that returns the process’s exit code.
procedure
(nasm-run/print-string s) → string?
s : string?
A run-reader that returns the contents of the standard output port of the
process, as a string.
procedure
(nasm-run/print-number s) → number?
s : string?
A run-reader that parses the standard output of the process as a Racket number.
procedure
(nasm-run/read s) → any/c
s : string?
A run-reader that parses the standard output of the process using
read, returning some valid Racket value.
procedure
(nasm-run/error-string s) → string?
s : string?
A run-reader that returns the contents of the standard error port of the
process, as a string.
A run-reader that returns a pair of the exit code and the contents of the standard error port of the
process as a string.
procedure
(trace-compiler!) → void?
Instruments the current-pass-list to trace the entire compiler using racket/trace.
procedure
Un-instruments the current-pass-list. Must only be called after calling trace-compiler!.
Executes the expression e in a context where the
current-pass-list is locally traced, leaving current-pass-list
in its original state after execution.
3.2.3 Compiler Parameters
This section describes parameters defining various values used in the CPSC411 compiler, such as those defining design choices or target machine details.
parameter
(current-word-size-bytes size) → void? size : exact-nonnegative-integer?
= 8
The number of bytes in a single machine word on the machine targeted by the
compiler.
parameter
(current-register-set) → (set/c symbol?)
(current-register-set set) → void? set : (set/c symbol?)
= '(rsp rbp rax rbx rcx rdx rsi rdi r8 r9 r10 r11 r12 r13 r14 r15)
The set of registers provided by the machine targeted by the compiler.
parameter
(current-stack-size size) → void? size : exact-nonnegative-integer?
= (* 8 1024 1024)
Deprecated; has no effect. The stack size is now defined by the operating system
using the SYS V ABI.
parameter
(current-heap-size size) → void? size : exact-nonnegative-integer?
= (* 128 1024 1024)
Defines the maximum size of the heap, in bytes, created by the run-time system.
Defaults to 128MB.
parameter
(current-frame-base-pointer-register reg) → void? reg : register?
= 'rbp
Defines the register in which the run-time system stores the base of the frame;
everything above this address is free space.
procedure
v : any/c
A predicate that returns #t when v is equal to the
current-frame-base-pointer-register, and #f otherwise.
parameter
(current-auxiliary-registers reg) → void? reg : register?
= '(r10 r11)
Defines the set of registers used as auxiliary registers when compiling
instructions to match x86-64 restrictions on which instructons use which kinds
of physical locations.
parameter
(current-patch-instructions-registers reg) → void? reg : register?
= '(r10 r11)
An alias for current-auxiliary-registers.
parameter
(current-return-value-register reg) → void? reg : register?
= 'rax
Defines the register that the run-time system and calling convention expects to
contain the return value.
parameter
(current-assignable-registers reg) → void? reg : register?
= '(rsp rbx rcx rdx rsi rdi r8 r9 r13 r14 r15)
Defines the set of registers that can be assigned by register allocations.
This set is derived from the current-register-set and the other
parameters that reserve registers.
parameter
(current-parameter-registers reg) → void? reg : (set/c register?)
= '(rdi rsi rdx rcx r8 r9)
Define the set of registers using for passing the first n arguments in
a procedure call, where n is the size of the set defined by this
parameter.
The remaining arguments are passed on the stack.
parameter
(current-return-address-register reg) → void? reg : register?
= 'r15
Define the register that the run-time system and calling convention expect to
contain the return address.
parameter
(current-heap-base-pointer-register reg) → void? reg : register?
= 'r12
Define the register that the run-time system initializes to the base address of
the heap; everything above this address is free space.
3.2.4 Two’s Complement Integers
This section defines utilities for working with fixed-width two’s complement integers.
procedure
v : exact-nonnegative-integer?
Returns the maximum two’s complement signed integer representable in v bits.
Examples:
procedure
v : exact-nonnegative-integer?
Returns the minimum two’s complement signed integer representable in v bits.
Examples:
procedure
word-size : exact-nonnegative-integer? i : number?
A predicate that decides whether i is in the range for a two’s complement signed
word-size-bit integer.
Examples:
> (int-size? 2 1) #t
> (int-size? 2 5) #f
> (int-size? 2 (max-int 2)) #t
> (int-size? 2 (min-int 2)) #t
> (int-size? 2 (- (min-int 2) 1)) #f
> (int-size? 2 (+ (min-int 2) 1)) #t
> (int-size? 32 (max-int 32)) #t
> (int-size? 32 (min-int 32)) #t
> (int-size? 32 (- (min-int 32) 1)) #f
> (int-size? 32 (+ (min-int 32) 1)) #t
Returns #t when i is in the range for an two’s complement
unsigned 8-bit integer.
Examples:
A predicate that decides whether i is in the range for a two’s complement signed
32-bit integer; shorthand for (int-size 32 i).
Examples:
> (int32? 0) #t
> (int32? 5) #t
> (int32? (max-int 32)) #t
> (int32? (min-int 32)) #t
> (int32? (- (min-int 32) 1)) #f
> (int32? (+ (min-int 32) 1)) #t
> (int32? 'x) #f
> (int32? 'x.1) #f
A predicate that decides whether i is in the range for a two’s complement signed
64-bit integer; shorthand for (int-size 64 i).
Examples:
> (int64? 0) #t
> (int64? 5) #t
> (int64? (max-int 64)) #t
> (int64? (min-int 64)) #t
> (int64? (- (min-int 64) 1)) #f
> (int64? (+ (min-int 64) 1)) #t
> (int64? 'x) #f
> (int64? 'x.1) #f
A predicate that decides whether i is in the range for a two’s complement signed
61-bit integer; shorthand for (int-size 61 i).
Examples:
> (int61? 0) #t
> (int61? 5) #t
> (int61? (max-int 61)) #t
> (int61? (min-int 61)) #t
> (int61? (- (min-int 61) 1)) #f
> (int61? (+ (min-int 61) 1)) #t
> (int61? 'x) #f
> (int61? 'x.1) #f
procedure
(handle-overflow word-size x) → number?
word-size : exact-nonnegative-integer? x : number?
Transform the number x into its representation as a
word-size-bit two’s complement signed integer.
When x is greater than the range, this overflows x until it is
range.
By contrast, if x is less than the range, this underflows x
until it is range.
Has no affect if x is in range.
Examples:
> (handle-overflow 32 (sub1 (min-int 32))) 2147483647
> (handle-overflow 32 (min-int 32)) -2147483648
> (handle-overflow 32 (max-int 32)) 2147483647
> (handle-overflow 32 (add1 (max-int 32))) -2147483648
procedure
(twos-complement-add word-size n1 n2)
→ (in-range/c (min-int word-size) (max-int word-size)) word-size : exact-nonnegative-integer? n1 : number? n2 : number?
Returns the result of adding n1 and n2 as
word-size-bit two’s complement integers.
Examples:
> (twos-complement-add 32 5 10) 15
> (twos-complement-add 32 (sub1 (max-int 32)) 1) 2147483647
> (twos-complement-add 32 (max-int 32) 1) -2147483648
> (twos-complement-add 32 (add1 (min-int 32)) -1) -2147483648
> (twos-complement-add 32 (min-int 32) -1) 2147483647
procedure
(twos-complement-sub word-size n1 n2)
→ (in-range/c (min-int word-size) (max-int word-size)) word-size : exact-nonnegative-integer? n1 : number? n2 : number?
Returns the result of subtracting n1 by n2 as
word-size-bit two’s complement integers.
Examples:
> (twos-complement-sub 32 5 2) 3
> (twos-complement-sub 32 (max-int 32) 1) 2147483646
> (twos-complement-sub 32 (min-int 32) 1) 2147483647
procedure
(twos-complement-mul word-size n1 n2)
→ (in-range/c (min-int word-size) (max-int word-size)) word-size : exact-nonnegative-integer? n1 : number? n2 : number?
Returns the result of multiplying n1 and n2 as
word-size-bit two’s complement integers.
Examples:
> (twos-complement-mul 32 2 5) 10
> (twos-complement-mul 32 (/ (max-int 32) 2) 2) 2147483647
> (twos-complement-mul 32 (max-int 32) 2) -2
Returns the 64-bit two’s complement addition of n1 and n2.
Examples:
Returns the 64-bit two’s complement subtraction of n1 by n2.
Examples:
Returns the 64-bit two’s complement multiplication of n1 and n2.
Examples:
3.2.5 Ptrs
This section describes the parameters and procedures for working with ptrs.
parameter
(current-fixnum-shift bits) → void? bits : exact-nonnegative-integer?
= 3
The bitwise shift length for the ptr encoding of fixnums.
parameter
(current-fixnum-mask bits) → void? bits : int64?
= #b111
The tag mask for the ptr encoding for fixnums.
parameter
(current-fixnum-tag bits) → void? bits : int64?
= #b000
The tag bits for the ptr encoding for fixnums.
parameter
(current-boolean-shift bits) → void? bits : exact-nonnegative-integer?
= (current-boolean-shift)
The bitwise shfit length for the ptr encoding of booleans.
parameter
(current-boolean-mask bits) → void? bits : int64?
= #b11110111
The tag mask for the ptr encoding of booleans.
parameter
(current-boolean-tag bits) → void? bits : int64?
= #b110
The tag bits for the ptr encoding of booleans.
parameter
(current-true-ptr bits) → void? bits : int64?
= #b1110
The ptr encoding of the true value.
parameter
(current-false-ptr bits) → void? bits : int64?
= #b0110
The ptr encoding of the false value.
Note that this should always be identical to the current-boolean-tag.
parameter
(current-empty-mask bits) → void? bits : int64?
= #b11111111
The tag mask for the ptr encoding of the empty list.
parameter
(current-empty-tag bits) → void? bits : int64?
= #b10110
The tag for the ptr encoding of the empty list.
parameter
(current-empty-ptr bits) → void? bits : int64?
= #b10110
The ptr encoding of the empty list.
Note that this should always be identical to the current-empty-tag.
parameter
(current-void-mask bits) → void? bits : int64?
= #b11111111
The tag mask for the ptr encoding of the void value.
parameter
(current-void-tag bits) → void? bits : int64?
= #b00011110
The tag for the ptr encoding of the void value.
parameter
(current-void-ptr bits) → void? bits : int64?
= #b00011110
The ptr encoding of the void value.
Note that this should always be identical to the current-void-tag.
parameter
(current-ascii-char-shift bits) → void? bits : exact-nonnegative-integer?
= 8
The bitwise shift length for the ptr encoding of ASCII character.
parameter
(current-ascii-char-mask bits) → void? bits : int64?
= #b11111111
The tag mask for the ptr encoding of ASCII characters.
parameter
(current-ascii-char-tag bits) → void? bits : int64?
= #b00101110
The tag for the ptr encoding of ASCII characters.
parameter
(current-error-shift bits) → void? bits : exact-nonnegative-integer?
= 8
The bitwise shift length for error values.
parameter
(current-error-mask bits) → void? bits : int64?
= #b11111111
The tag mask for the ptr encoding of error values.
parameter
(current-error-tag bits) → void? bits : int64?
= #b00111110
The tag for the ptr encoding of error values.
parameter
(current-pair-shift bits) → void? bits : exact-nonnegative-integer?
= 3
The bitwise shift length for the ptr encoding of pairs.
parameter
(current-pair-mask bits) → void? bits : int64?
= #b111
The tag mask for the ptr encoding of pairs.
parameter
(current-pair-tag bits) → void? bits : int64?
= #b001
The tag for the ptr encoding of pairs.
parameter
(current-car-displacement i) → void? i : int64?
= 0
The number of bytes to add to a ptr representing a pair, after masking the tag,
to treat the ptr as a pointer to the first element of the pair.
Probably corresponds to 0 or 1 words.
parameter
(current-cdr-displacement i) → void? i : int64?
= 8
The number of bytes to add to a ptr representing a pair, after masking the tag,
to treat the ptr as a pointer to the second element of the pair.
Probably corresponds to 0 or 1 word.
procedure
(car-offset) → int64?
Returns the offset amount, in bytes, to add to a ptr representing a pair to
compute the address of the first element of the pair.
Includes the amount necessary to mask the tag.
procedure
(cdr-offset) → int64?
Returns the offset amount, in bytes, to add to a ptr representing a pair to
compute the address of the second element of the pair.
Includes the amount necessary to mask the tag.
parameter
(current-pair-size i) → void? i : int64?
= 16
Returns the size of a pair, in bytes, for the current machine target.
parameter
(current-vector-shift bits) → void? bits : exact-nonnegative-integer?
= 3
The bitwise shift length for the ptr encoding of vectors.
parameter
(current-vector-mask bits) → void? bits : int64?
= #b111
The tag mask for the ptr encoding of vectors.
parameter
(current-vector-tag bits) → void? bits : int64?
= #b011
The tag for the ptr encoding of vectors.
parameter
(current-vector-length-displacement bytes) → void? bytes : int64?
= 0
The number of bytes to add to the address of a vector to get the address of the
vector’s length.
Probably corresponds to either 0 or 1 words.
parameter
(current-vector-base-displacement bytes) → void? bytes : int64?
= 8
The number of bytes to add to the address of a vector to get the address of the
vector’s base, which should be followed by the rest of the vector.
Probably corresponds to either 0 or 1 words.
parameter
(current-procedure-shift bits) → void? bits : exact-nonnegative-integer?
= 3
The bitwise shift length for the ptr encoding of procedures.
parameter
(current-procedure-mask bits) → void? bits : int64?
= #b111
The tag mask for the ptr encoding of procedures.
parameter
(current-procedure-tag bits) → void? bits : int64?
= #b010
The tag for the ptr encoding of procedures.
parameter
(current-procedure-label-displacement bytes) → void? bytes : int64?
= 0
The number of bytes to add to the address of a procedure to get the address of
the label of the procedure.
Probably corresponds to 0, 1 or 2 words.
parameter
(current-procedure-arity-displacement bytes) → void? bytes : int64?
= 8
The number of bytes to add to the address of a procedure to get the address of
the arity of the procedure.
Probably corresponds to 0, 1 or 2 words.
parameter
(current-procedure-environment-displacement bytes) → void? bytes : int64?
= 16
The number of bytes to add to the address of a procedure to get the address of
the environment of the procedure.
Probably corresponds to 0, 1 or 2 words.
procedure
(ascii-char-literal? c) → boolean?
c : any/c
Returns #t for ASCII character literals and #f otherwise.
Examples:
> (ascii-char-literal? #\a) #t
> (ascii-char-literal? #\b) #t
> (ascii-char-literal? #\6) #t
> (ascii-char-literal? #\?) #t
> (ascii-char-literal? #\space) #t
> (char? #\λ) #t
> (ascii-char-literal? #\λ) #f
3.2.6 Misc Compiler Helpers
procedure
(make-begin is t) → tail
is : (listof effect) t : tail
A language-generic helper to make begin statements in tail position.
The first arguments is a list of effect-context statements, while the final
argument is a tail-context statement.
make-begin will construct `(begin ,is ... ,t), but try to
minimize begins in the process.
Assumes that t has already been constructed using make-begin.
Examples:
> (make-begin '() '(halt 5)) '(halt 5)
> (make-begin '() '(begin (halt 5))) '(begin (halt 5))
> (make-begin '((set! rax 5)) '(begin (halt 5))) '(begin (set! rax 5) (halt 5))
> (make-begin '((set! rax 5)) '(begin (begin (halt 5)))) '(begin (set! rax 5) (begin (halt 5)))
> (make-begin '((begin (set! rax 5))) '(begin (halt 5))) '(begin (set! rax 5) (halt 5))
> (make-begin '((begin (begin (set! rax 5)))) '(begin (halt 5))) '(begin (set! rax 5) (halt 5))
> (make-begin '((begin (begin (set! rax 5)))) '(begin (begin (halt 5)))) '(begin (set! rax 5) (begin (halt 5)))
> (make-begin '((begin (begin (set! rax 5)))) (make-begin '() (make-begin '() '(halt 5)))) '(begin (set! rax 5) (halt 5))
procedure
(make-begin-effect is) → effect
is : (listof effect)
A language-generic helper to make begin statements effect position.
The first arguments is a list of effect-context statements.
make-begin-effect will construct `(begin ,is ...), but try to
minimize begins in the process.
Examples:
> (make-begin-effect '()) '(begin)
> (make-begin-effect '((begin (set! rax 5)))) '(begin (set! rax 5))
> (make-begin-effect '((set! rax 5))) '(begin (set! rax 5))
> (make-begin-effect '((begin (begin (set! rax 5))) (begin (set! rax 5)))) '(begin (set! rax 5) (set! rax 5))
procedure
(check-assignment p) → any/c
p : any/c
Takes a program in any language where the second element satisfies
(let ([loc? (or/c register? fvar?)]) (info/c (assignment ((aloc? loc?) ...)) (conflicts ((aloc? (aloc? ...)) ...)) (locals (aloc? ...))))
Check that the given assignment is sound with respect to the conflicts graph and complete with respect the locals set. Returns p if so, or raises an error.
To be language agnostic, it doesn’t actually check that the program is valid and only depends on the info field.
Examples:
> (check-assignment `(module ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1)) (conflicts ((p.1 (z.5 t.6 y.4 x.3 w.2)) (t.6 (p.1 z.5)) (z.5 (p.1 t.6 w.2 y.4)) (y.4 (z.5 x.3 p.1 w.2)) (x.3 (y.4 p.1 w.2)) (w.2 (z.5 y.4 p.1 x.3 v.1)) (v.1 (w.2)))) (assignment ((v.1 r15) (w.2 r8) (x.3 r14) (y.4 r9) (z.5 r13) (t.6 r14) (p.1 r15))))))
'(module
((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1))
(conflicts
((p.1 (z.5 t.6 y.4 x.3 w.2))
(t.6 (p.1 z.5))
(z.5 (p.1 t.6 w.2 y.4))
(y.4 (z.5 x.3 p.1 w.2))
(x.3 (y.4 p.1 w.2))
(w.2 (z.5 y.4 p.1 x.3 v.1))
(v.1 (w.2))))
(assignment
((v.1 r15) (w.2 r8) (x.3 r14) (y.4 r9) (z.5 r13) (t.6 r14) (p.1 r15)))))
> (check-assignment `(module ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1)) (conflicts ((p.1 (z.5 t.6 y.4 x.3 w.2)) (t.6 (p.1 z.5)) (z.5 (p.1 t.6 w.2 y.4)) (y.4 (z.5 x.3 p.1 w.2)) (x.3 (y.4 p.1 w.2)) (w.2 (z.5 y.4 p.1 x.3 v.1)) (v.1 (w.2)))) (assignment ((w.2 r8) (x.3 r14) (y.4 r9) (z.5 r13) (t.6 r14) (p.1 r15)))))) check-assignment: Some locals not assigned homes:
homeless locals: v.1
> (check-assignment `(module ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1)) (conflicts ((p.1 (z.5 t.6 y.4 x.3 w.2)) (t.6 (p.1 z.5)) (z.5 (p.1 t.6 w.2 y.4)) (y.4 (z.5 x.3 p.1 w.2)) (x.3 (y.4 p.1 w.2)) (w.2 (z.5 y.4 p.1 x.3 v.1)) (v.1 (w.2)))) (assignment ((v.1 r8) (w.2 r8) (x.3 r14) (y.4 r9) (z.5 r13) (t.6 r14) (p.1 r15)))))) check-assignment: Produced bad assignment:
w.2 and v.1 both assigned to r8
procedure
n : any/c f : procedure? ls : list?
Like map, but returns n lists.
Expects f to returns n return values.
Support mapping over any non-zero number of lists.
Examples:
> (map-n 2 (lambda (x y) (values (add1 x) (sub1 y))) '(1 2 3) '(1 2 3))
'(2 3 4)
'(0 1 2)
> (map-n 3 (lambda (x) (values (add1 x) (sub1 x) (* 2 x))) '(1 2 3))
'(2 3 4)
'(0 1 2)
'(2 4 6)
procedure
f : procedure? ls : list?
Examples: