A question about LICM (Loop Invariant Code Motion)

Project Infrastructure LLVM Dev List Archives
1

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

2

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.

3

I suppose you could peel a single iteration to try to work around that.

Reid

4

Peeling is a good idea for small loops with invariant loads or
conditions. I'm not sure why we don't do it. But it would cause code
bloat (in the absense of profile data) and it's not a general solution.

If null checks were the only problem, then the compiler could hoist the
load under a non-null condition (e.g. select), replacing the original
with a trap under the inverse condition. But even if the entire loop
is dominated by a null check, it's still unsafe to hoist the load.

The fundamental problem is that the language needs to guarantee that
the load is safe to speculate. Modern languages do this. But I don't know
how to represent that information in LLVM IR. We would need a way
to indicate a load's control dependent conditions (null checks, type
checks, and such).

-Andy

5

clang -O2 hoists the load of fp out of the loop, since loop rotation transforms the loop. Are you not seeing this?

-Chris