## memory-aliasing-g.pkg
#
# Perform memory aliasing analysis.
#
# The old memory disambiguation module discards aliasing information
# across nextcode function boundaries, which made it not very
# useful for the optimizations I (Allen Leung) have in mind.
#
# This is an alternative module that (I hope) does the right thing.
# The algorithm is inspired by Steensgaard's work on flow insensitive
# points-to analysis, but has been hacked to deal with target level issues.
#
# Some target level issues
# ------------------------
# In the source level two nextcode allocations cannot be aliased by definition.
# However, when allocations are translated into target code, they become
# stores to fixed offsets from the heap pointer. Two allocation stores
# that may write to the same offset are aliased. Allocation stores that are
# in disjoint program paths may be assigned the same heap allocation offset.
# We have to mark these as aliased since we want to allow speculative writes
# to the allocation space.
#
# Representing heap offsets
# -------------------------
#
#
# Language
# --------
# e ::= x <- v.i; k # select
# | x <- v+i; k # offset
# | x <- [v1, ...vn]^hp; k # record allocation at heap pointer hp
# | x <- *v; k # Dereference
# | v1 := v2; k # update
# | f (v1, ..., vn) # tail call
#
# Since the analysis is flow insensitive, the branch constructs are
# irrelevant.
#
# -- Allen Leung
# Compiled by:
# src/lib/compiler/core.sublibstipulate
package ncf = nextcode_form; # nextcode_form is from src/lib/compiler/back/top/nextcode/nextcode-form.pkg package rgn = nextcode_ramregions; # nextcode_ramregions is from src/lib/compiler/back/low/main/nextcode/nextcode-ramregions.pkgherein
api Memory_Aliasing {
#
analyze_memory_aliasing_of_nextcode_functions
:
List( ncf::Function )
->
(ncf::Codetemp -> rgn::Ramregion);
};
end;
stipulate
package ncf = nextcode_form; # nextcode_form is from src/lib/compiler/back/top/nextcode/nextcode-form.pkg package iht = int_hashtable; # int_hashtable is from src/lib/src/int-hashtable.pkg package lem = lowhalf_error_message; # lowhalf_error_message is from src/lib/compiler/back/low/control/lowhalf-error-message.pkg package p = ncf::p;
package pt = points_to; # points_to is from src/lib/compiler/back/low/aliasing/points-to.pkg package rgn = nextcode_ramregions; # nextcode_ramregions is from src/lib/compiler/back/low/main/nextcode/nextcode-ramregions.pkg package rkj = registerkinds_junk; # registerkinds_junk is from src/lib/compiler/back/low/code/registerkinds-junk.pkg package rwv = rw_vector; # rw_vector is from src/lib/std/src/rw-vector.pkgherein
# This generic is invoked (only) in:
#
# src/lib/compiler/back/low/main/main/translate-nextcode-to-treecode-g.pkg #
generic package memory_aliasing_g (
# =================
#
package rgk: Registerkinds; # Registerkinds is from src/lib/compiler/back/low/code/registerkinds.api )
: (weak) Memory_Aliasing # Memory_Aliasing is from src/lib/compiler/back/low/main/nextcode/memory-aliasing-g.pkg {
fun error msg
=
lem::error("memory_aliasing_g", msg);
# The following functions advances the heap pointer.
# These functions are highly dependent on the runtime system and
# how data structures are represented.
# IMPORTANT: we are assuming that the new rw_vector representation is used.
fun record_size (n, hp)
=
n * 4 + 4 + hp; # 64-bit issue: '4' is presumably bytes-per-word.
fun frecord_size (n, hp)
=
{ hp = if (unt::bitwise_and (unt::from_int hp, 0u4) != 0u0) hp+8;
else hp+4;
fi;
8*n + hp;
};
fun vector_size (n, hp)
=
n * 4 + 16 + hp; # 64-bit issue: '4' is presumably bytes-per-word.
fun allot_record (ncf::rk::FLOAT64_BLOCK, vs, hp) => frecord_size (length vs, hp);
allot_record (ncf::rk::FLOAT64_FATE_FN, vs, hp) => frecord_size (length vs, hp);
#
allot_record (ncf::rk::VECTOR, vs, hp) => vector_size (length vs, hp);
allot_record (_, vs, hp) => record_size (length vs, hp);
end;
store_list_size = 8;
array0size = 20;
exception NOT_FOUND;
top = rgn::memory;
# Analyze a set of nextcode functions.
#
# We are called (only) from:
#
# src/lib/compiler/back/low/main/main/translate-nextcode-to-treecode-g.pkg #
fun analyze_memory_aliasing_of_nextcode_functions
#
nextcode_functions
=
if *global_controls::compiler::disambiguate_memory
#
rgn::reset ();
apply define_function nextcode_functions;
apply process nextcode_functions;
\\ r = get_loc r
except _ = top;
else
(\\ _ = top);
fi
where
fun size_of (ncf::DEFINE_RECORD { kind, fields, next, ... }, hp) => size_of (next, allot_record (kind, fields, hp));
#
size_of (ncf::GET_FIELD_I { next, ... }, hp) => size_of (next, hp);
size_of (ncf::GET_ADDRESS_OF_FIELD_I { next, ... }, hp) => size_of (next, hp);
#
size_of (ncf::TAIL_CALL _, hp) => hp;
size_of (ncf::DEFINE_FUNS _, hp) => error "size_of: ncf::DEFINE_FUNS";
size_of (ncf::JUMPTABLE { nexts, ... }, hp) => size_ofs (nexts, hp);
#
size_of (ncf::IF_THEN_ELSE { then_next, else_next, ... }, hp) => int::max (size_of (then_next, hp), size_of (else_next, hp));
#
size_of (ncf::STORE_TO_RAM { op => ncf::p::SET_REFCELL, next, ... }, hp) => size_of (next, hp+store_list_size);
size_of (ncf::STORE_TO_RAM { op => ncf::p::RW_VECTOR_SET, next, ... }, hp) => size_of (next, hp+store_list_size);
size_of (ncf::STORE_TO_RAM { op => ncf::p::SET_VECSLOT_TO_BOXED_VALUE, next, ... }, hp) => size_of (next, hp+store_list_size);
size_of (ncf::STORE_TO_RAM { op => _, next, ... }, hp) => size_of (next, hp );
size_of (ncf::FETCH_FROM_RAM { op => _, next, ... }, hp) => size_of (next, hp );
size_of (ncf::ARITH { next, ... }, hp) => size_of (next, hp );
size_of (ncf::RAW_C_CALL { next, ... }, hp) => size_of (next, hp );
#
size_of (ncf::PURE { op => ncf::p::WRAP_FLOAT64, next, ... }, hp) => size_of (next, frecord_size (1, hp));
size_of (ncf::PURE { op => ncf::p::MAKE_WEAK_POINTER_OR_SUSPENSION, next, ... }, hp) => size_of (next, hp+8); # Weak reference or lazy suspension. # 64-bit issue: '8' is 2*wordbytes
size_of (ncf::PURE { op => ncf::p::MAKE_REFCELL, next, ... }, hp) => size_of (next, hp+8); # 64-bit issue: '8' is 2*wordbytes
size_of (ncf::PURE { op => ncf::p::WRAP_INT1, next, ... }, hp) => size_of (next, hp+8); # 64-bit issue: '8' is 2*wordbytes
size_of (ncf::PURE { op => ncf::p::MAKE_ZERO_LENGTH_VECTOR, next, ... }, hp) => size_of (next, hp+array0size);
size_of (ncf::PURE { op => p, next, ... }, hp) => size_of (next, hp);
#
end
also
fun size_ofs ( [], hp) => hp;
size_ofs (k ! ks, hp) => int::max (size_of (k, hp), size_ofs (ks, hp));
end;
stipulate
loc_hashtable = iht::make_hashtable { size_hint => 37, not_found_exception => NOT_FOUND }; # Variable -> loc
herein
get_loc = iht::get loc_hashtable;
set_loc = iht::set loc_hashtable;
end;
new_mem = rgk::make_codetemp_info_of_kind rkj::RAM_BYTE;
pt::reset new_mem;
fun new_ref _
=
REF (pt::SCELL (new_mem(), REF []));
exception_handler_register = pt::new_sref (); # exception handler
current_thread_ptr = pt::new_sref (); #
fun lookup x
=
get_loc x
except
_ = { r = new_ref ();
set_loc (x, r);
r;
};
fun define_function (fk, f, args, _, cexp)
=
set_loc (f, pt::make_fn xs)
where
xs = map (\\ x = { r = new_ref ();
set_loc (x, r);
r;
}
)
args;
end;
off0 = ncf::SLOT 0;
fun process (fk, f, args, _, cexp)
=
infer (cexp, 0)
where
# Create a table of allocation offset locations
table = rwv::from_fn (size_of (cexp, 0) / 4, new_ref);
fun select (i, ncf::CODETEMP v, x) => set_loc (x, pt::ith_projection (lookup v, i));
select (i, _, x) => ();
end;
fun offset (i, ncf::CODETEMP v, x) => set_loc (x, pt::ith_offset (lookup v, i));
offset (i, _, x) => ();
end;
fun value (ncf::CODETEMP v) => lookup v;
value _ => new_ref ();
end;
fun apply (ncf::CODETEMP f, args) => pt::apply (lookup f, map value args);
apply _ => ();
end;
fun get_path (v, ncf::SLOT 0) => value v;
get_path (v, ncf::SLOT n) => pt::ith_offset (value v, n);
get_path (v, ncf::VIA_SLOT (n, path)) => pt::ith_projection (get_path (v, path), n);
end;
fun get_paths((v, path) ! vs, hp)
=>
{ r = rwv::get (table, hp);
r' = get_path (v, path);
pt::unify (r, r');
r ! get_paths (vs, hp+1);
};
get_paths ([], hp) => [];
end;
fun get_f64paths((v, path) ! vs, hp)
=>
{ r1 = rwv::get (table, hp);
r2 = rwv::get (table, hp+1);
r' = get_path (v, path);
pt::unify (r1, r');
pt::unify (r2, r');
r' ! get_f64paths (vs, hp+2);
};
get_f64paths ([], hp) => [];
end;
# How to make a record
#
stipulate
fun make_rec (f, get_paths, x, vs, hp)
=
{ i = unt::to_int (unt::(>>) (unt::from_int hp, 0u2));
r = f (THE (rwv::get (table, i)), get_paths (vs, i+1));
#
set_loc (x, r);
};
herein
fun make_frecord (x, vs, hp) = make_rec (pt::make_record, get_f64paths, x, vs, hp);
fun make_vector (x, vs, hp) = make_rec (pt::make_record, get_paths, x, vs, hp);
fun make_normal_record (x, vs, hp) = make_rec (pt::make_record, get_paths, x, vs, hp);
end;
fun make_record (ncf::rk::FLOAT64_BLOCK, x, vs, hp) => make_frecord (x, vs, hp);
make_record (ncf::rk::FLOAT64_FATE_FN, x, vs, hp) => make_frecord (x, vs, hp);
#
make_record (ncf::rk::VECTOR, x, vs, hp) => make_vector (x, vs, hp);
make_record (_, x, vs, hp) => make_normal_record (x, vs, hp);
end;
fun make_top m
=
{ pt::unify (m, top);
top;
};
# nextcode pure base ops:
fun arrayptr v
=
pt::ith_projection (value v, 0);
fun make_special (x, v, hp) = make_normal_record (x,[(v, off0)], hp);
fun fwrap (x, v, hp) = make_frecord (x,[(v, off0)], hp);
fun i32wrap (x, v, hp) = make_normal_record (x,[(v, off0)], hp);
fun makeref (x, v, hp) = make_normal_record (x,[(v, off0)], hp);
fun newarray0 (x, hp)
=
set_loc (x, pt::make_record (NULL,[pt::make_record (NULL,[])]));
fun chunklength (x, v) = set_loc (x, pt::ith_projection (value v, -1));
fun length (x, v) = set_loc (x, pt::ith_projection (value v, 1));
fun gettag (x, v) = set_loc (x, pt::ith_projection (value v, -1));
fun getcon (x, v) = set_loc (x, pt::ith_projection (value v, 0));
fun getexn (x, v) = set_loc (x, pt::ith_projection (value v, 0));
fun arraysub (x, a, i) = make_top (pt::weak_get (arrayptr a));
#
fun subscriptv (x, a, i) = arraysub (x, a, i);
fun subscript (x, a, i) = arraysub (x, a, i);
fun pure_numsubscript (x, a, i) = arraysub (x, a, i);
fun numsubscript8 (x, a, i) = arraysub (x, a, i);
fun numsubscriptf64 (x, a, i) = arraysub (x, a, i);
fun recsubscript (x, a, i) = arraysub (x, a, i);
fun raw64subscript (x, a, i) = arraysub (x, a, i);
# nextcode "looker" base ops:
fun deref (x, v) = make_top (pt::strong_get (value v, 0));
fun gethandler x = set_loc (x, pt::strong_get (exception_handler_register, 0));
fun get_current_microthread_register x = set_loc (x, pt::strong_get (current_thread_ptr, 0));
# nextcode "setter" base ops:
fun supdate (a, x) = pt::strong_set (value a, 0, make_top (value x));
fun wupdate (a, x) = pt::weak_set (value a, make_top (value x));
fun arrayupdate (a, i, x) = pt::weak_set (arrayptr a, value x);
fun assign (a, x) = supdate (a, x);
fun unboxedassign (a, x) = supdate (a, x);
fun update (a, i, x) = arrayupdate (a, i, x);
fun boxedupdate (a, i, x) = arrayupdate (a, i, x);
fun unboxed_set (a, i, x) = arrayupdate (a, i, x);
fun numupdate (a, i, x) = arrayupdate (a, i, x);
fun numupdate_f64 (a, i, x) = arrayupdate (a, i, x);
fun sethandler x = pt::strong_set (exception_handler_register, 0, value x);
fun set_current_microthread_register x = pt::strong_set (current_thread_ptr, 0, value x);
# I don't know whether the following makes any sense... XXX BUGGO FIXME
# Basically, I want to ignore this aliasing analysis
# as far as raw access is concerned. The invariant is
# that raw access NEVER occurs to any memory location
# that Mythryl "knows" about. -- Matthias Blume (2000/1/1)
fun set_raw (a, x) = ();
fun rawload (a, x) = top;
fun infer (ncf::DEFINE_RECORD { kind, fields, to_temp, next }, hp)
=>
{ make_record (kind, to_temp, fields, hp);
#
infer (next, allot_record (kind, fields, hp));
};
infer (ncf::GET_FIELD_I { i, record, to_temp, next, ... }, hp) => { select (i, record, to_temp); infer (next, hp); };
infer (ncf::GET_ADDRESS_OF_FIELD_I { i, record, to_temp, next }, hp) => { offset (i, record, to_temp); infer (next, hp); };
#
infer (ncf::TAIL_CALL { fn, args }, hp) => apply (fn, args);
infer (ncf::DEFINE_FUNS _, hp) => error "infer: ncf::DEFINE_FUNS";
#
infer (ncf::JUMPTABLE { nexts, ... }, hp) => infers (nexts, hp);
#
infer (ncf::IF_THEN_ELSE { then_next, else_next, ... }, hp)
=>
{ infer (then_next, hp);
infer (else_next, hp);
};
# These things are misnamed! There is nothing pure about them! XXX SUCKO FIXME
infer ( ncf::PURE { op => ncf::p::HEAPCHUNK_LENGTH_IN_WORDS,
args => [arg],
to_temp,
next,
...
},
hp
)
=>
{ chunklength (to_temp, arg);
infer (next, hp);
};
infer (ncf::PURE { op => ncf::p::VECTOR_LENGTH_IN_SLOTS, args => [v], to_temp, next, ...}, hp) => { length (to_temp, v); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::RO_VECTOR_GET, args => [a, i], to_temp, next, ...}, hp) => { subscriptv (to_temp, a, i); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::PURE_GET_VECSLOT_NUMERIC_CONTENTS { kind_and_size=>ncf::p::INT 8 },args => [a, i], to_temp, next, ...}, hp) => { pure_numsubscript (to_temp, a, i); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::GET_BATAG_FROM_TAGWORD, args => [v], to_temp, next, ...}, hp) => { gettag (to_temp, v); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::MAKE_WEAK_POINTER_OR_SUSPENSION, args => [i, v], to_temp, next, ...}, hp) => { make_special (to_temp, v, hp); infer (next, hp+8);};
infer (ncf::PURE { op => ncf::p::MAKE_REFCELL, args => [v], to_temp, next, ...}, hp) => { makeref (to_temp, v, hp); infer (next, hp+8);};
infer (ncf::PURE { op => ncf::p::WRAP_FLOAT64, args => [v], to_temp, next, ...}, hp) => { fwrap (to_temp, v, hp);
infer (next, frecord_size (1, hp));
};
infer (ncf::PURE { op => ncf::p::WRAP_INT1, args => [v], to_temp, next, ...}, hp) => { i32wrap (to_temp, v, hp); infer (next, hp+8);};
infer (ncf::PURE { op => ncf::p::GETCON, args => [v], to_temp, next, ...}, hp) => { getcon (to_temp, v); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::GETEXN, args => [v], to_temp, next, ...}, hp) => { getexn (to_temp, v); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::RECORD_GET, args => [a, i], to_temp, next, ...}, hp) => { recsubscript (to_temp, a, i); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::RAW64_GET, args => [a, i], to_temp, next, ...}, hp) => { raw64subscript (to_temp, a, i); infer (next, hp);};
infer (ncf::PURE { op => ncf::p::MAKE_ZERO_LENGTH_VECTOR, args => _, to_temp, next, ...}, hp) => { newarray0 (to_temp, hp); infer (next,hp+array0size);};
infer (ncf::PURE { op => p, args => vs, to_temp, next, ...}, hp) => infer (next, hp);
infer (ncf::ARITH { next, ... }, hp) => infer (next, hp);
# Things that access the contents of ram:
#
infer (ncf::FETCH_FROM_RAM { op => ncf::p::GET_REFCELL_CONTENTS, args => [v], to_temp, next, ... }, hp) => { deref (to_temp, v); infer (next, hp);};
infer (ncf::FETCH_FROM_RAM { op => ncf::p::GET_EXCEPTION_HANDLER_REGISTER, args => [], to_temp, next, ... }, hp) => { gethandler to_temp; infer (next, hp);};
infer (ncf::FETCH_FROM_RAM { op => ncf::p::GET_VECSLOT_CONTENTS, args => [a, i], to_temp, next, ... }, hp) => { subscript (to_temp, a, i); infer (next, hp);};
#
infer (ncf::FETCH_FROM_RAM { op => ncf::p::GET_VECSLOT_NUMERIC_CONTENTS { kind_and_size=>ncf::p::INT 8 },args => [a, i], to_temp, next, ... }, hp) => { numsubscript8 (to_temp, a, i); infer (next, hp);};
infer (ncf::FETCH_FROM_RAM { op => ncf::p::GET_VECSLOT_NUMERIC_CONTENTS { kind_and_size=>ncf::p::FLOAT 64 },args => [a, i], to_temp, next, ... }, hp) => { numsubscriptf64 (to_temp, a, i); infer (next, hp);};
infer (ncf::FETCH_FROM_RAM { op => ncf::p::GET_CURRENT_MICROTHREAD_REGISTER, args => [], to_temp, next, ... }, hp) => { get_current_microthread_register to_temp; infer (next, hp);};
#
infer (ncf::FETCH_FROM_RAM { op => ncf::p::DEFLVAR, args => [], to_temp, next, ... }, hp) => /* nop! */ infer (next, hp);
infer (ncf::FETCH_FROM_RAM { op => ncf::p::GET_FROM_NONHEAP_RAM _, args => [a], to_temp, next, ... }, hp) => { rawload (to_temp, a); infer (next, hp);};
# Things that change the contents of ram:
#
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_REFCELL, args => [a, v], next }, hp) => { assign (a, v); infer (next, hp+store_list_size);};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_REFCELL_TO_TAGGED_INT_VALUE, args => [a, v], next }, hp) => { unboxedassign (a, v); infer (next, hp );};
infer (ncf::STORE_TO_RAM { op => ncf::p::RW_VECTOR_SET, args => [a, i, v], next }, hp) => { update (a, i, v); infer (next, hp+store_list_size);};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_VECSLOT_TO_BOXED_VALUE, args => [a, i, v], next }, hp) => { boxedupdate (a, i, v); infer (next, hp+store_list_size);};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_VECSLOT_TO_TAGGED_INT_VALUE, args => [a, i, v], next }, hp) => { unboxed_set (a, i, v); infer (next, hp );};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_VECSLOT_TO_NUMERIC_VALUE { kind_and_size=>ncf::p::INT _}, args => [a, i, v], next }, hp) => { numupdate (a, i, v); infer (next, hp );};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_VECSLOT_TO_NUMERIC_VALUE { kind_and_size=>ncf::p::FLOAT 64 },args => [a, i, v], next }, hp) => { numupdate_f64 (a, i, v); infer (next, hp );};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_EXCEPTION_HANDLER_REGISTER, args => [x], next }, hp) => { sethandler x; infer (next, hp );};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_CURRENT_MICROTHREAD_REGISTER, args => [x], next }, hp) => { set_current_microthread_register x; infer (next, hp );};
infer (ncf::STORE_TO_RAM { op => ncf::p::SET_NONHEAP_RAM _, args => [a, x], next }, hp) => { set_raw (a, x); infer (next, hp );};
#
# Apparently these are nops -- see
# src/lib/compiler/back/low/main/main/translate-nextcode-to-treecode-g.pkg #
infer (ncf::STORE_TO_RAM { op => ncf::p::USELVAR, args => [x], next }, hp) => infer (next, hp );
infer (ncf::STORE_TO_RAM { op => ncf::p::ACCLINK, args => _, next }, hp) => infer (next, hp );
infer (ncf::STORE_TO_RAM { op => ncf::p::SETMARK, args => _, next }, hp) => infer (next, hp );
infer (ncf::STORE_TO_RAM { op => ncf::p::FREE, args => [x], next }, hp) => infer (next, hp );
#
infer (ncf::STORE_TO_RAM { op => ncf::p::PSEUDOREG_SET, args => _, next }, hp) => infer (next, hp );
infer (e, hp)
=>
{ prettyprint_nextcode::print_nextcode_expression e;
print "\n";
error "infer";
};
end
also
fun infers ([], hp) => ();
infers (k ! ks, hp) => { infer (k, hp);
infers (ks, hp);
};
end;
end;
end;
};
end;