Re: Basic blocks and compilers

George Neuner <>
9 Jan 2006 23:48:53 -0500

          From comp.compilers

Related articles
Basic blocks and compilers (Christian Christmann) (2006-01-07)
Re: Basic blocks and compilers (George Neuner) (2006-01-09)
Re: Basic blocks and compilers ( (2006-01-09)
Re: Basic blocks and compilers (2006-01-09)
Re: Basic blocks and compilers (Hans-Peter Diettrich) (2006-01-09)
Re: Basic blocks and compilers (Paolo Bonzini) (2006-01-09)
Re: Basic blocks and compilers (Ken Rose) (2006-01-09)
Re: Basic blocks and compilers (Stephen Clarke) (2006-01-09)
[1 later articles]
| List of all articles for this month |

From: George Neuner <>
Newsgroups: comp.compilers
Date: 9 Jan 2006 23:48:53 -0500
Organization: Compilers Central
References: 06-01-009
Keywords: analysis
Posted-Date: 09 Jan 2006 23:48:53 EST

On 7 Jan 2006 21:44:36 -0500, Christian Christmann <>

>Here is the code for a simple C function "loopfunc" that is
>called from the main function (not included):
> ld.w %d15, [%a10] 8
> ld.w %d0, [%a10] 12
> jlt %d15, %d0, .L5
> j .L3
> ld.w %d15, [%a10] 4
> add %d0, %d15, 1
> st.w [%a10] 4, %d0
> ld.w %d15, [%a10] 8
> add %d0, %d15, 1
> st.w [%a10] 8, %d0
> j .L2
> ld.w %d15, [%a10] 4
> mov %d2, %d15
> j .L1
> ret
> .align 1
> .global main
> .type main,@function

First, it would be a lot easier to understand the assembler if the HLL
that produced it was included.

>I don't understand why the compiler
>1) is not spliting basic block .L2 into two blocks where
>the second block just contains the instruction "j .L3".

The code sequence
                jlt %d15, %d0, .L5
                j .L3
is a standard encoding of an exiting IF.

Notice also that .L3 jumps to .L1 instead of just falling through.

The splitting algorithm needs to guarantee that each block ends with
an *unconditional* control transfer (a jump or return) so that the
blocks may be rearranged without messing up the program logic. A
block which ends in IF is coded as a conditional branch to the IF part
followed by and unconditional branch to the ELSE part (or to whatever
follows the IF).

Using a higher optimization level should result in better merging of
the blocks and eliminate (at least some of) the redundant jumps.

>I though that each re-direction of the control flow imposes the
>creation of a new basic block (like .L4 and .L3). The instuction
>"jlt %d15, %d0, .L5" can possibly direct the program flow to .L5 and
>thus, in my opinion, the basic block should end here.

There is no prohibition against a block having multiple exits so long
as no non-exit processing is performed between them.

On machines that have a separate compare instruction and non-computing
jumps you may see 3-way exits that look like
                cmp %d1, %d2
                jlt .L4
                jgt .L5
                j .L3

You can also see such code using subtract instead of compare.

>2) splits block .L5 and .L4? There are no
>calls to label .L4, so, according to my understanding, all instructions
>of blocks .L5 and .L4 should be held in one block.

It looks like the compiler created a new block label for each HLL
statement (just in case). After splitting it turned out that the
label .L4 did not really name a block entry point - but the label was
retained anyway.

This is, again, a normal side effect. It's extra work to go back and
relabel after merging blocks ... I've never seen a (non research)
compiler bother to do it.


Post a followup to this message

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