Re: Definition of basic blocks

Ray Dillinger <>
27 Nov 2005 00:36:52 -0500

          From comp.compilers

Related articles
Definition of basic blocks (Christian Christmann) (2005-11-08)
Re: Definition of basic blocks (SM Ryan) (2005-11-12)
Re: Definition of basic blocks (Thomas Schilling) (2005-11-12)
Re: Definition of basic blocks (A Pietu Pohjalainen) (2005-11-12)
Re: Definition of basic blocks (Ray Dillinger) (2005-11-27)
Re: Definition of basic blocks (Hans-Peter Diettrich) (2005-11-29)
| List of all articles for this month |

From: Ray Dillinger <>
Newsgroups: comp.compilers
Date: 27 Nov 2005 00:36:52 -0500
Organization: Sonic.Net
References: 05-11-053
Keywords: analysis

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.


Post a followup to this message

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