[LLVMdev] A case where llvm created different cfg for same code

[Bill Wendling]

On Aug 13, 2008, at 12:03 AM, Sheng Zhou wrote:

>>>>
>>>> The prime difference is that: cfg of form2 has additional basic  
>>>> block
>>>> which has a back edge to a non-header-block
>>>> I think the loop in that cfg is not canonical.
>>>>
>>>> I tried -loopsimplify and -indvars , but no improvement.
>>>>
>>>> Any comments for this? Thanks in advance.
>>>>
>>>
>> The code is not the same. 7 is commented out in the first and 8 in  
>> the
>> second. Why would you expect the CFGs to match? Is there something
>> wrong (inefficient) in the resulting output of these two functions
>> when compiled?
>>
> 7 for(i=0; i<j && i+j+1<N; i++) {
>
> 8 for(i=0; i<j && i<N-j-1; i++) {
>
>
> Line 7 and Line 8 actually have the same expression,

The expressions are logically similar, but they aren't the same to the  
compiler unless some pass that recognizes these types of polynomial  
equations and can prove that they are the same is run (I'm not sure if  
such a pass exists in LLVM). For instance, because you use "j - 1" in  
8, you now have a situation where you have a negative number when j ==  
0, etc.

> Line 8 just move the "j+1" to the right hand of the inequation.
>
> I just wonder why the two equal inequation result in different cfg,  
> the
> additional basicblock, backedge...
> Surely the two cfg are all correct, but just the additional backedge
> makes it hard for loop pipeline.
>
> Can we improve it?
>
>>

For what it's worth, I got the exact same code for both forms when  
compiling at -O3.

-bw