Re: Definition of basic blocks

Christian Christmann wrote:


> What I actually want to know, is, if call instructions are treated like
> any other instruction or if they cause the end of a basic block.
> I've encountered both versions. Some people use call instructions amid
> a basic block, other use them at the end of a basic block and continue
> with the subsequent instructions in a new block.


> Are both version correct?


Depends on the language and semantics. If your language is strictly
call-by-value and there's no "funny stuff" going on (such as
continuations or implicit side effects) then you can take a call as
part of a basic block.


If it's call-by-reference, things are a little murkier; I defer to
someone with superior knowledge.


As our moderator pointed out, if there are implicit side effects -
variables in scope that aren't passed explicitly to the function, but
the function can modify them - you need to break the block there.


If there is a chance that a call will cause an "unusual execution
path" to be taken (eg, the routine being called or some member of the
transitive closure of the set of routines *it* calls can execute a
throw past the calling code, or a call to a reified continuation), you
need to break the block there.


If the language is fully recursive and the calling function is a
member of the set of functions that is the transitive closure of
functions called by the called function, then you need to break the
block with the call.


If the continuation (the return from the call) can be captured and
reified in your language so that it can be stored in a variable and
called like a routine any number of times, as in some lisps, you
definitely need to break the block there, because in that case a call
to the continuation is a "jump" to the code after the call that can be
executed from anywhere the variable holding the continuation as a
value is in scope.


Hmmm, I'm trying to think of any other "funny stuff" that causes you
to need to break a basic block with a call. There's probably more,
some of it quite esoteric. F'r example, I'm pretty sure that
call-by-name semantics, which are ridiculously rare in computer
languages and generally considered to be hazardous by those who fully
understand them, would require you to break a basic block with a call.


Bear

Return to the comp.compilers page.
Search the comp.compilers archives again.