wks
commented
9 years ago This goto-with-values is actually the way used by PyPy's internal representation.
I think it is equivalent to the PHI node. I don't really object this idea, but PHI looks better to me. We may internally move the PHI to the jump site to help the code generator.
However, in the µVM, branching is not the only instruction that causes control flow transfer, but we also have SWITCH (like C's switch statement), INVOKE (calling a function and catch exceptions), TRAP (go to the client and may return to the µVM with an exception) and IINVOKE (calling an "intrinsic function" (which will be renamed "common instruction") and may receive exceptions)
In the future, even more instructions will have exceptional jump targets. They are:
- Some binary operations, comparisons and conversions. The exceptional destination designates arithmetic errors including divide-by-zero, floating point exceptions and so on.
- Memory allocation. Out-of-memory error.
- Memory accessing. Mainly the NULL pointer error. µVM may also forward some (but obviously not all) exceptions from the OS to the µVM program.
- SWAPSTACK. When swapping stack, it is an option to raise an exception in the destination stack.
If the values are to be added in the jumping site, all those instructions must be augmented to add the values at the destinations. In fact, doing so does not change the complexity of the code at all (when using PHI functions, all cases must also be covered). But PHI functions simplify the instruction format.
Some simple comparison:
Arithmetic exceptions:
%entry:
%result = DIV <@i64> %param1 %param2 EXC(%nor %exc)
%nor:
%a = PHI <@i64> { %entry: %param1, %other_bb: ...; }
%b = PHI <@float> { %entry: 0.0f, %other_bb: ...; }
%c = PHI <@i64> {%entry: %result, %other_bb: ...; }
...
%exc:
%error_code = PHI <@i32> { %entry: @SIGFPE, %other_error_source: ...; }
...%entry:
%result = DIV <@i64> %param1 %param2 EXC(%nor(%a=%param1, %b=0.0f, %c=%result) %exc(%error_code=@SIGFPE))
%nor(%a:@i64, %b:@float, %c:@i64):
...
%exc(%error_code:@i32):
...Function call with exception:
NOTE: The CALL instruction with EXC(...) clause is the proposed future grammar. Currently it is a separate "INVOKE" instruction.
%entry:
%retval = CALL <@func_sig> @func (%arg1 %arg2 ...) EXC(%nor %exc)
%nor:
...
%exc:
%the_exception = LANDINGPAD // Do we want to remove this, too?
%another_val = PHI <@i64> { %entry: 42; %other_bb: 43; }
...%entry
%retval = CALL <@func_sig> @func (%arg1 %arg2 ...) EXC(%nor() %exc(%the_exception=THE_EXCEPTION, %another_val=42))
// We use the special THE_EXCEPTION keyword to pass the value to another basic block
%nor():
...
%exc(%the_exception:@REF_TO_VOID, %another_val:@I64):
...Alternatively we can treat exceptions specially
%entry
%retval = CALL <@func_sig> @func (%arg1 %arg2 ...) EXC(%nor() %exc(%another_val=42))
%nor():
...
%exc(%another_val:@I64):
%the_exception = LANDINGPAD // This is still too similar to PHI
...
qinsoon
sampsyo
eliotmoss
This is an update of a proposal from a year ago.
The current Mu definition of SSA-form has labels, branches to labels, and Phi functions just after labels.
I propose an alternative, which we might call "goto with values". It is similar to continuation passing style except that all the continuations are statically defined (one for each label). This alternative would work as follows:
Example: x = 3; y = 25; goto l(x, y); ... l: (x2:int<32>,y2:int<8>)
This form makes it clear that the association ("assignment") of values to phi-variables has to happen as part of the control transfer. Phi-functions are simply one way of representing that, but they're not not a way that seems immediately helpful for code generation.
I further observe that the current definition apparently allows any value to be passed in to a Phi, but I think it should be restricted to global/constant SSA variables or SSA variables defined in the sending block. The new form perhaps makes that clear, not least because with it you can explicitly disallow referring to local SSA variables defined in other blocks.
Putting these another way, non-global SSA-variables have a scope only from where they are defined to the end of their block. Some may be defined at the label that start the block and others may be defined later, but all live values must be mentioned at branches and explicitly passed on.
Compared with traditional SSA form this may appear verbose. However it has at least a couple of advantages: