[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Data structure documentation & BUG?
> From: Guy Laden <laden@math.tau.ac.il>
> Date: Sat, 10 Feb 1996 00:17:03 +0200 (GMT+0200)
>
> > If I were to add information to the GSA tree, such as register allocations, etc.
> > how should that be done? What happens to references to external memory (such
> > as arrays, records, etc)?
>
> operands and results (Data.Opnd, Data.Result) have a 'location' field with
> the (abstract) type Data.Location. Data.Location should be extended in the
> backend for different types of 'locations': stack, register, heap etc...
> The frontend itself extends Data.Location - see Data.SymLocation - and
> fills the location field of the operands of exit/collect and the results
> of enter/reclaim with records of the Data.SymLocation. The location
> fields for all other operands/results should be NIL (note that i think
> if you enable --gsa-assign some 'debug' info is stored in some other
> 'location' fields). The backend storage/register-allocater should fill in
> most of the NIL 'location' fields with ptr's to the extended Location
> types.
I have nothing to add to this. I can elaborate on the --gsa-assign
option, though. When it is set, assignments to variables set the
location of the value (ie, Data.Result) being assigned to the variable
itself. This is used to increase the readability of the output of
WriteGSA.Body by adding assigment hints. Instead of writing just
(5) copy 0
it's possible to write
(5) i := copy 0
This info CANNOT be used be the back-end (eg to simplify storage
allocation) for two of reasons: it's not always set and it may
contradict the actual data flow.
> References to external memory are modeled with the GSA instructions access*
> and update* (see Opcode.Mod).
>
> All the above is just what I've been able to understand - I'm hoping
> Michael will correct me.
There is nothing to correct. And I'm very grateful for your elaborate
answer. This gives me more time to answer your questions below ;-).
> I've been trying to figure out the fastest way of putting together a
> quick-and-*dirty*, _simple_ backend, just to gain a better understanding
> of compilers, GSA, the OOC frontend, the 386, linux and life in general. ;-)
> This backend will not have a register allocator (i think all the
> 386 instructions I need can operate directly on memory), nor a
> peephole-optimizer. It will output GAS assembler and will have the bare
> minimum instruction scheduling (ie: calling TopologicalOrder.Order
> (its in the optimizers directory), followed by a traversal of the
> GSA converting guards and merges to cmps,branches etc.. btw: whats the status
> of TopologicalOrder.Mod - is it supposed to be complete? it seems to be
> unused in the current version of the compiler)
AFAIK TopSort is usable and might even be used as a framework for a
general instruction scheduler. It's Juergen's module, he's the one to
ask about the status and how it's intended to be used.
> I'm starting with the storage allocator for procedures. What I had in mind is:
> i think that before doing all the rest, a traversal of the region's
> instructions must be done, and for each gate, a location
> must be set that is the same for all of the different paths.
> ie: for each gate, we allocate a new location. then,
> we must traverse the useList for each of the gate's operands,
> setting it's location to the newly allocated one.
I'm quite sure that this won't work. A gate operand might be a gate
itself. Applying the above strategy will map _all_ results that
directly or indirectly (ie, across other gates) deliver their value
into a single gate onto a single location.
> For a procedures local-variables:
> foreach instruction in the procedure's region
> if the instruction is Legal() then:
> foreach result of the current instruction
> if result.useList # NIL then
> allocate a location (ie: an object of a type that extends
> Data.Location, eg: StackLocation)
> foreach element in the result's useList, set it's location field to
> the newly allocated location that we assigned for the current result.
> At the moment Legal() is anything BUT enter,exit,reclaim,collect,an opcode
> of the classes: classGuard or classMerge, create-store,
> delete-store.
I'm a bit worried about the "For a procedures local-variables". It's
not sufficient to consider only the local vars. Procedure inlining
and LOOPs (by creating $exit vars) introduce variables that are not
declared locally. And it is possible for a single variable to hold
more than one value at a given point in the program, preventing a
one-to-one mapping of a variable onto a memory location.
Here is an example (Fig. 18) from [CFRWZ91]:
--------------------------------------------------------------------------------
V_2 := 6
WHILE (...) DO WHILE (...) DO WHILE (...) DO
W_3 := phi(W_0, W_2) W_3 := phi(W_0, W_2)
V_3 := phi(V_0, V_2) V_3 := phi(V_0, V_2)
read V; read V_1 read V_1
W := V + W W_1 := V_1 + W_3 W_1 := V_1 + W_3
V := 6 V_2 := 6
W := W + V W_2 := V_2 + W_1 W_2 := V_2 + W_1
END END END
*** a) *** *** b) *** *** c) ***
Fig. 18: Program that really uses two instances for a variable after
code motion. (a) Source program; (b) unoptimized SSA form; (c) result
of code motion
--------------------------------------------------------------------------------
While there is only one variable V, there are two instances of it in
the WHILE loop of (c). The assignment "V:=6" is detected as being
constant for the whole loop and moved out of the loop. So at the
point of "read V_1" in c) the value of V_2 is in use, together with
V_1.
> Michael, is it true to say that in addition, we dont need to allocate locations
> for:
> a. any instructions which have the flag instrIsDisabled
Instructions with `instrIsDisabled' are removed in the final call to
DeadCodeElimination (with `removedDisable=TRUE') iff they are dead
code. I suggest you ignore this flag in the back-end, and rather sift
out instructions like `delete-store' (which is technically disabled,
but in general not `dead') by hand.
FYI: Instructions with set `instrIsDisabled' are inserted into the
code to have semantic information like index restrictions available in
the intermediate code for optimizations and additional error checks.
> b. any instructions which have $store as a result.
Before I answer this I better check where such a result may appear:
Instructions with a $store result are create-store, reclaim,
update-heap, update-nonlocal, and update-var-param.
So the answer is yes, since storage that is referred to by one of
the update instructions is allocated elsewhere.
> For a procedures parameters:
> use Data.EnterInstr to find the 'enter' instruction.
> traverse the enter's results (which are the procedures parameters) allocating
> their locations (eg: at positive stack offsets) and traversing their useList's
> like before.
The enter instruction has also results for variables from enclosing
scopes that are accessed locally and pseudo-values for types (ie,
Data.Struct), describing accesses of heap objects.
> More questions:
>
> How do I get a list of the module's global variables,
> from the symbol-table, or from the gsa? if from the symbol-table,
> what about variables that are not used and not exported, must I check
> for this myself? if from the gsa, do i need to maintain a list of
> access/updates that refer to global variables or ...?
If you have the module object, you get the variables by traversing the
binary tree in `mod. localDecl'. All objects in this tree with
`obj. mode = Data.objVar' are global variables. Of course you can
check for unused variables (their `objIsUsed' flag isn't set; this
flag is always set for exported vars), but I wouldn't suggest it. The
user gets warnings for unused variables, IMO this is sufficient.
> For access-var-param instructions, the operand seems to refer to the variable
> itself. How do I access the location of the _address_ of the parameter
> (which is a result of the 'enter' instruction)
I inserted the address of the parameter as second operand into
access-var-param resp. update-var-param. Does this answer your
question?
Note that for nested procedures an accesses to a parameter tag
(address, type tag, length) may actually refer to a parameter of the
enclosing region. The tags are also part of the `nonlocal access'
section of the nested region's enter instruction, but they have to be
treated differently from `local' parameters when calculating their
actual location.
> On other issues:
> Is it possible to expand the range of allowed parameters to HALT?
> I'm not sure what the language specification reads about this, but
> for compatibility with other Oberon implementations it should
> be possible to specify negative numbers and 0 (actually, i just
> remembered this would be needed for the proposed exception mechanism,
> so i guess it was coming anyway)
The range of valid trap numbers for HALT and ASSERT is defined in
Config.Mod (part of the back-end directory). The report leaves this
range undefined, although most implementations limit it to a suitable
subrange of integers. It should be considered back-end dependent IMO.
> I think there might be an error in line 146 of oo2c.Mod in the new release.
> it seems to read: IF (a = x) & (a = y) ...
Oops. Thanks!
> Has anyone tried to compile ooc with the free native-code linux GPO compiler?
> I'm going to try, perhaps this will bring out bugs in ooc/o2c/gpo (gcc is
> so very tedious to wait for)
GCC is somewhat on the slow side, but bearable for systems from 486/33
onward. Unless you do a `--make --all' all the time ;-). You'll
probably need to inserte a intermediate lib level that maps the o2c
libs onto GPO (which might lead to name clashes) in order to find out
if ooc compiles. I might even try GPO myself, if, and only if, you're
successful.
-- Michael