=================================================== =================================================== Draft for Block Closure Semantics for Squeak v0.5.1 =================================================== =================================================== Author: Stephan Rudlof Date: 02.04.2001 Changes: v0.5.1: better title v0.5: Exploiting read only property of temps (typically method/block arguments). Open Questions ============== Better terminology: Use the term 'binding' instead of 'reference'? New Ideas not worked out ======================== Basic Ideas =========== - Make it as simple as possible first, improve it later if necessary (this principle has seen some iterations yet); - introduce local block variables, with - direct references (oops) for - block arguments (as used to for BlockMethods), - locally created temps (by '| |' expressions), - readonly temporay variables from outer contexts; - indirect references (see below) for - read/write temporary variables from outer contexts; - store these variables in the indexable fields of a new block context class. Legend ====== - temps -> directly referencable temporary variables residing in indexable fields; holding oops of - readonly method/block arguments, or - readonly outer temps, or - read/write temps created by '| |' expressions; - local temps -> temps in current method or block context; - locally created temps -> temps created by '| |' expression in current context; - outer temps -> temps in outer method or block contexts; - indexable fields for outer temps -> indexable fields containing r/w or readonly references (o/i pairs or readonly oops) to outer temps; - indexable fields for indirect references: indexable fields containing o/i pairs; - outer references part of indexable fields -> indexable fields containing outer temps; BCSBlockContexts ================ BCS stands for 'block closure semantics'. BCSBlockContexts have some properties of MethodContexts: their indexable fields layout regarding temps is like the one from MethodContexts, which has place for storing temporary variables. But in addition to MethodContexts there are references to outer temps in the indexable fields before the first stack entry, if needed. Indexable Fields Layout of BCSBlockContexts =========================================== Currently there are just block arguments stored in a BlockContext's indexable fields. Let's enhance the indexable fields functionality as follows for BCSBlockContexts: Example ------- In this example the block has - 2 arguments (a's); - 3 read only outer references (r's); - 4 read/write outer temps (o/i pairs); - 5 locally created temps (l's); After block copy: ???????rrroioioioi -----------^ At begin of evaluating the block: ???????rrroioioioiaa -----------^ | After initialization of locally created temps with nil: ??00000rrroioioioiaa -----------^ | After storing block arguments into local temps: aa00000rrroioioioi -----------^ After assigning to all locally created temps: aalllllrrroioioioi -----------^ ?: uninitialized; a: read only block argument, stored as temp at begin of evaluating the block; 0: locally created temp (by '| |' expression) initialized with nil; l: oop of locally created temp; r: readonly outer temp, stored directly as oop here; o: oop of outer block or method context; i: index of local temp (l) location in indexable fields of outer context o; -: outer references, direct (r's) and indirect (o/i pairs) ones; ^: stack pointer after copying outer references to the indexable fields (start of the stack after the blockCopy: operation and before arguments copied to it later); |: stack pointer just after copying the block arguments from the stack of the outer context to the current one while evaluating the block (in the next step these block arguments are pop'ed and store'd into the first indexable fields). r's have to be globally read only during the lifetime of this block. Typically they are (outer) block/method arguments stored as temps in their indexable fields, but with a smart compiler there may be more. o's and i's here belong together, they always appear as pairs. Such an o/i pair represents the indirect reference to a *writable* temp l in an outer context. Block copy with outer temps --------------------------- A block copy has to generate a BCSBlockContext with space for - block arguments (a's) (like for MethodContexts), - locally created temps (l's) (like for MethodContexts), - read only outer temps (r's), - read/write outer temps (o/i pairs), and - the stack (like for Block/MethodContexts), in its indexable fields. Before a block copy the readonly oops of local (args) or outer temps are pushed in one and the indices of locally created and outer read/write temps in another bunch (later followed by their number) onto the stack. A block copy copies them as readonly oops in the first and as o/i pairs in the second case to the indexable fields for indirect references of a newly created BCSBlockContext then. In the current context there may be locally created (directly referenced) *and* outer (indirectly referenced) r/w temps, seen from the new one these are both outer r/w temps. Stack of current context before block copy: ...iiirrrCWRLA. i: index of outer or local r/w temp in current context; r: oop of readonly temp in current context; C: current Context; W: number of outer r/w temps (o/i pairs) of to be created BCSBlockContext; R: number of outer readonly temps of to be created BCSBlockContext; L: number of locally created temps (l's); A: number of block arguments. Index i here has another semantics as the index above (in 'Example'): It refers to an o/i pair or to an oop in the indexable fields of the current context. After copying the corresponding r/w temps to an inner BCSBlockContext they are all indirectly referenced o/i pairs there! To know which index i refers to an - indirectly referenced outer, and which to a - directly referenced local r/w temp in the current context, there has to be an additional instance variable in BCSBlockContext: - numOfDirectlyReferencedTemps, which is computed by numOfDirectlyReferencedTemps := A + L + R. This is sufficient to identify the type (oop or o/i pair) of the to be copied temp references during the block copy operation. Further condition: numOfIndexableFieldsBeforeStack := numOfDirectlyReferencedTemps + (2 * numOfIndirectlyReferencedTemps). Important: All outer references have to be copied to the outer references (part of the) indexable fields of the newly created BCSBlockContext, which are used - inside the blockContext of the actually blockCopied block, and - in later created blockContexts, created while evaluating the actual block. The latter means that an outer reference has to be propagated from the outer BCSBlockContexts to the inner ones until the last block is reached, which uses it. Evaluation ---------- Read/write local temps (l's) are always nil'ed if the block has to be evaluated: this means to change the semantics of the #value method family. Arguments are pushed onto the local stack if the block has to be evaluated like it is done currently. What the Compiler has to do =========================== - differentiating between different kind of variables: - intelligent naming scheme, - qualifying as - local and outer context, - readonly and read/write temps; - generating bytecodes (see below) for - accessing (storing/getting) indirect referenced outer context temps, - block copy operations generating BCSBlockContexts; - dealing with the propagation of outer references from outer BCSBlockContexts to inner ones. What the VM has to do ===================== - clearing locally created block temps in the #value family of primitives (by switching there between BlockContext and BCSBlockContext (as long as there isn't a clean BCS image)); - ... Misc ==== - Outer temps living in MethodContexts are treated as outer temps in BCSBlockContexts (and not accessed as used to by their home pointer (containing the MethodContext)). Used current bytecodes ---------------------- ( 16 31 pushTemporaryVariableBytecode) (104 111 storeAndPopTemporaryVariableBytecode) They are usable for BCSBlockContexts, since they behave like MethodContexts here. Proposed new bytecodes ====================== Bytecode for reaching outer read/write temporaries -------------------------------------------------- Bytecode 126 (currently unused) extendedOuterAccessBytecode "This 2-byte code performs access to read/write temporary variables in outer contexts. This access is an indirect one: variableIndex refers to the indexable fields for indirect references of the current BCSBlockContext. These contain oops of outer Block/MethodContexts followed by an index of a local temporary residing in their (the outer contexts) indexable fields. The 2nd byte consists of a 2-bit operation type, and a 6-bit temporary variable index." | descriptor opType variableIndex | descriptor := self fetchByte. opType := (descriptor >> 6) bitAnd: 2r11. "high 2 bits shifted down" variableIndex := descriptor bitAnd: 2r111111. "all but high 2 bits" opType caseOf: { [0] -> [self pushOuterTemporary: variableIndex]. [1] -> [self storeOuterTemporary: variableIndex]. [2] -> [self storePopOuterTemporary: variableIndex]. [3] -> [self moreExtendedOuterAccess: variableIndex "variableIndex is not the final index here"]. }. Case [3] eats one or more extra bytes for reaching more than 63 or 64 variables (variableIndex is just 6 of the bits needed then). We don't need a lexical level here, since access to the outer temps is realized by indirect references stored in the indexable fields of the current BCSBlockContext. The variableIndex here refers to indexable fields for indirect references located behind local and readonly outer temporary variables and before arguments on the stack. But how do indirect references reach the newly created BCSBlockContext? They have to be copied to its indexable fields for indirect references after its direct referenced ones by new Interpreter block copy methods. These methods create the BCSBlockContexts. So there is a need for more bytecodes: Bytecodes for block copying --------------------------- Bytecode 138 (currently experimental) bytecodePrimBCSBlockCopy "clean block" | numOfArguments numOfLocallyCreatedTemps | numOfArguments := self stackIntegerValue: 0. numOfLocallyCreatedTemps := self stackIntegerValue: 1. context := self stackValue: 2. self primitiveBCSBlockCopyArgs: numOfArguments numOfLocallyCreatedTemps: numOfLocallyCreatedTemps context: context. Bytecode 139 (currently experimental) bytecodePrimBCSBlockCopyWithOuterTemps "block with outer references" | numOfArguments numOfLocallyCreatedTemps numOfOuterReadOnlyTemps numOfOuterReadWriteTemps | numOfArguments := self stackIntegerValue: 0. numOfLocallyCreatedTemps := self stackIntegerValue: 1. numOfOuterReadOnlyTemps := self stackIntegerValue: 2. numOfOuterReadWriteTemps := self stackIntegerValue: 3. "or another index..." context := self stackValue: 4. self primitiveBCSBlockCopyArgs: numOfArguments numOfLocallyCreatedTemps: numOfLocallyCreatedTemps numOfOuterReadOnlyTemps: numOfOuterReadOnlyTemps numOfOuterReadWriteTemps: numOfOuterReadWriteTemps context: context. Interpreter>>primitiveBCSBlockCopyArgs:numOfLocallyCreatedTemps:numOfOuterReadOnlyTemps:numOfOuterReadWriteTemps:context: has to copy the outer references (pushed as oops or indices to indexable fields of the current context onto the stack) as readonly oops or read/write o/i pairs to the indexable fields of a newly created BCSBlockContext. Note: These methods are written to get the idea, the concrete implementation may differ (and I haven't tried to compile them). Limitations =========== Unknown so far. Compatibility and Upgrading =========================== This proposal is as compatible as possible with the old scheme: - (old) BlockContext's generated in already translated methods behave as before; - a new VM is needed for BCS (block closure semantics); - if the (modified) compiler starts to translate with BCS the semantics change for newly compiled methods -> this affects recompiling; - older images are usable with a BCS VM; - after upgrading to a BCS compiler the image isn't usable by a pre BCS VM! There has to be caution in the process of upgrading!