Re: Basic blocks and compilers

On 7 Jan 2006 21:44:36 -0500, Christian Christmann <plfriko@yahoo.de>
wrote:


>Here is the code for a simple C function "loopfunc" that is
>called from the main function (not included):
>
<snip>
>.L2:
> ld.w %d15, [%a10] 8
> ld.w %d0, [%a10] 12
> jlt %d15, %d0, .L5
> j .L3
>.L5:
> ld.w %d15, [%a10] 4
> add %d0, %d15, 1
> st.w [%a10] 4, %d0
>.L4:
> ld.w %d15, [%a10] 8
> add %d0, %d15, 1
> st.w [%a10] 8, %d0
> j .L2
>.L3:
> ld.w %d15, [%a10] 4
> mov %d2, %d15
> j .L1
>.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.


George

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