Talk:Basic block

Conservative concept

Yaronf,

Your edits are okay, but you've made the concept more conservative and blurred the idea that basic blocks are intraprocedural entities (CFG edges don't leave the procedure). Generally, we allow function calls in the middle of basic blocks, as long as we know they will return; exceptions and continuations can mess this up. If you concur I'd like to revert some of your changes.

Derrick Coetzee 02:12, 29 Feb 2004 (UTC)

Hi Derrick,

When performing static code analysis, you rarely have complete information about who's calling a certain procedure. More precisely, this is a question of whether procedure addresses are observeable externally, e.g. through a linker-generated symbol table for dynamic loading. So often you have to assume that the procedure's boundary is also the start of a basic block. You can certainly optimize across function calls, but in such cases you are optimizing across basic blocks! Dynamic :analysis is different for example in a trace cache you can have a single trace with code from different :procedures.

Also, exceptions are associated with instructions at this level, not with functions.

BTW, I used "instruction" while you're using "statement". The former may prevent confusion with high-level language statements, but in any case, the article should only use one of the terms for consistency.

Yaronf 12:15, Feb 29, 2004 (UTC)

First use of the term

The material on this page is fine, but it would be nice if it referenced the earliest use of "basic block" (that I know if) which is J. Backus 1957 paper cited in the (current as of 2010-03-04) footnote 7 of http://en.wikipedia.org/wiki/Fortran . Anyone feel responsible for this page? —Preceding unsigned comment added by 75.18.168.242 (talk) 22:34, 4 March 2010 (UTC)

Clarifications

The code may be source code, assembly code or some other sequence of instructions.

Well... Assembly code is just a special case of source code, isn't it? I suggest to remove that sentence, and add source code at the very beginning of the article.

"dominates", or always executes before

The or gives the impression it's an alternative: either it's dominating, or it executes before. If I understand correctly the topics, it's just a rephrasing. I suggest to replace or with i.e. or parentheses to make that clear.

--MathsPoetry (talk) 02:03, 11 September 2011 (UTC)

Bad/incomplete short definitions

It's actually kinda hard to find sources which don't mess up when giving a one-liner definition of BB. I found some good ones, which I'm going to add to the article, but for the benefit of future textbook (and even research paper) writers, here is how some short ones (actually found in publications out there) are bad/incomplete:

just SESE

I.e. single-entry, single-exit. Well, obviously Dijkstra could tell you that an if x < 0 then y = -1 else y = 1 is SESE, but this is clearly not a single BB. Entry/exit point is a notion with respect to the outside of the program/block/construct, not from the inside, i.e. SESE does not prohibit, with the usual meaning of "entry point" and "exit point", internal jumps/branches inside the block as long as those jump points aren't referenced from outside the program/block/construct.

instructions execute "together"

... or, more wordily stated "if one is executed then all are executed". This is more arguable that is actually wrong, but it lacks some timing/repetition info. Consider:

i = 0;
while (i < 2) {
  if (i == 0) {
    something0 = 0;
  } else {
    something1 = 1;
  }
  i = i + 1;
}

Assuming no external jumps into the code fragment besides to the first instruction, then if one of the instructions above is executed, then all are, but some are executed more than once! This example is actually inspired from the Böhm-Jacopini proof; it uses a variable (i) to encode flow control within the fragment. (You can obviously drop the whole "if" part, but I added it for clarity.)

It is more arguable that is actually a bad/incomplete definition, because you can interpret "if one is executed then all are executed" as implying that when i = i + 1 executes [a second time], then i = 0 must also execute [a second time]. "if one is executed then all are executed" lacks an explicit time frame info for when the "then" part is supposed to happen; note that it's not enough for them to execute "together" even within a single call (entry/exit sequence) to the block. So a complete/unambiguous formulation starting with this expression is "if one is executed then all are executed before any one of them may be executed again, [i.e. a second time]". Which is of course a rather cumbersome way to say. The issue here is that you're really trying to express a temporal logic constraint using only classical logic, so it is going to sound awkward/imprecise.

HTH. Intllgnt sgn unlss cmpltly knwn (talk) 04:47, 19 July 2014 (UTC)

Adding an example?

To the previous redactors: would it be clever to put an example of "basic block", a textual description is not concrete.

Relation to Program Structure Tree and single-entry-single-exit ?

Are https://en.wikipedia.org/wiki/Single-entry_single-exit and this article equivalent? Intellec7 (talk) 09:14, 4 July 2020 (UTC)

Suggesting a change in the output definition of Creation algorithm

Shouldn't the "statement" in the output definition of Creation algorithm be "instruction"?

Input: A sequence of instructions (mostly three-address code).

Output: A list of basic blocks with each three-address statement in exactly one block.