Dear Squeakers,
here is the next version: exploiting read only property of temps has changed a
lot!
Greetings,
Stephan
================================================
================================================
Draft for BlockClosure Semantics for Squeak v0.5
================================================
================================================
Author: Stephan Rudlof
Date: 28.03.2001
Changes:
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!
--
Stephan Rudlof (sr(a)evolgo.de)
"Genius doesn't work on an assembly line basis.
You can't simply say, 'Today I will be brilliant.'"
-- Kirk, "The Ultimate Computer", stardate 4731.3
