llvm dev - Feb 2011 - [LLVMdev] A question about LICM (Loop Invariant Code Motion)

Hi,

I recently looked into the LICM(Loop Invariant Code Motion) pass of
LLVM and got a question about hoist load instruction to loop
preheader. I would like to show two examples:

Example 1:
int func(int n, int *fp) {
 int i;
 int a[1000];
 for (i = 0; i < n; ++i) {
     a[i] += *fp; // load from *fp pointer, no hoist
 }
}

Here, load *fp CAN NOT be hoisted to loop preheader. If replace *fp
with an local pointer, the load can not be hoisted either.

However, with this example:

int gv = 3;//global var
int func(int n) {
 int i;
 int a[1000];
 for (i = 0; i < n; ++i) {
     a[i] += gv; // load from the @gv pointer, hoist
 }
}

load for the global var gv's value CAN be hoist to loop preheader.

After tracking the LICM pass, I find that both loads are loop
invariant, and canSinkOrHoist() also returns true; however the
difference is at Instruction::isSafeToSpeculativelyExecute(),
for load from function parameter pointer, it return false; with load
from a global var pointer, it returns true. As a result no hoist
happens for a load *fp:

**LICM.cpp
if (isLoopInvariantInst(I) && canSinkOrHoistInst(I) &&
         isSafeToExecuteUnconditionally(I))   // invokes
I->IsSafeToSpeculativelyExecute()
       hoist(I);

But I do not know why we need to treat fp/local pointer different with
global pointer here. I think hoisting fp/local pointers should be fine
if they are loop invariant and does not alias with other pointers..

Anyone can help me to figure this out?

Thank you very much.

-Yuelu, UIUC

Hi Yuelu,
> After tracking the LICM pass, I find that both loads are loop
> invariant, and canSinkOrHoist() also returns true; however the
> difference is at Instruction::isSafeToSpeculativelyExecute(),
> for load from function parameter pointer, it return false; with load
> from a global var pointer, it returns true. As a result no hoist
> happens for a load *fp:
the function parameter pointer might be null.

Ciao, Duncan.

On Tue, Feb 8, 2011 at 4:55 AM, Duncan Sands <baldrick at free.fr>
wrote:
> Hi Yuelu,
>
>> After tracking the LICM pass, I find that both loads are loop
>> invariant, and canSinkOrHoist() also returns true; however the
>> difference is at Instruction::isSafeToSpeculativelyExecute(),
>> for load from function parameter pointer, it return false; with load
>> from a global var pointer, it returns true. As a result no hoist
>> happens for a load *fp:
>
> the function parameter pointer might be null.
I suppose you could peel a single iteration to try to work around that.

Reid

On Feb 7, 2011, at 2:13 PM, Yuelu Duan wrote:
> Hi,
> 
> I recently looked into the LICM(Loop Invariant Code Motion) pass of
> LLVM and got a question about hoist load instruction to loop
> preheader. I would like to show two examples:
> 
> Example 1:
> int func(int n, int *fp) {
> int i;
> int a[1000];
> for (i = 0; i < n; ++i) {
>     a[i] += *fp; // load from *fp pointer, no hoist
> }
> }
> 
> Here, load *fp CAN NOT be hoisted to loop preheader. If replace *fp
> with an local pointer, the load can not be hoisted either.
clang -O2 hoists the load of fp out of the loop, since loop rotation transforms
the loop.  Are you not seeing this?

-Chris