Loop Invariants Detection questions

Hi all!

I’m new here, and would like to implement my own Loop Invariant Detection adding some more information on Quasi-Invariants.

First, is there anything about Quasi-Invariants detection in LLVM I would missed?

I’ve seen LICM using LoopInfo::isLoopInvariant for finding invariants.

It seems that this method considers a Value invariant if:

  • it’s an Instruction not presents in the current loop (what does it mean? There is no dependence analysis on In and Out “variables” of all instructions in the loop?)

  • this Value is not an Instruction (then a Constant I guess…).

I’ve seen LoopAccessAnalysis using it too. What does this analysis do exactly on loop invariant address?

Also DependenceAnalysis seems to give dependence information on memory refs. But it seems to not be used by LICM…

Also MemoryDependenceAnalysis “determines, for a given memory operation, what preceding memory operations it depends on”.

My question is: Where is really done this dependence analysis. The one which figures out which Instructions depends on others?

Simply if I have:
%0 = load i32, i32* %coucou, align 4
%1 = load i32, i32* %fact, align 4

%2 = load i32, i32* %i, align 4

%mul = mul nsw i32 %1, %2

mul instruction will depends on the two precedents loads because it uses their results %1 and %2 but not the first one.

I guess this is done somewhere, and there is a special representation of this information but I didn’t find, I’m a bit lost ^^’

Is someone can show me the way? Or just explain what he knows about Invariants and Instructions dependencies detection in LLVM… or just a good link I should follow…

Ty :slight_smile:

Hi all!

I'm new here, and would like to implement my own Loop Invariant Detection adding some more information on Quasi-Invariants.

First, is there anything about Quasi-Invariants detection in LLVM I would missed?

I've seen LICM using LoopInfo::isLoopInvariant for finding invariants.
It seems that this method considers a Value invariant if:
- it's an Instruction not presents in the current loop (what does it mean? There is no dependence analysis on In and Out "variables" of all instructions in the loop?)

isLoopInvariant just checks whether the definition of a value is an instruction inside the loop.

- this Value is not an Instruction (then a Constant I guess…).

Or an function argument, or a few other obscure things which don't really matter in this context.

I've seen LoopAccessAnalysis using it too. What does this analysis do exactly on loop invariant address?

ScalarEvolution::isLoopInvariant works on SCEV expressions instead of Values, but it's essentially the same thing.

Also DependenceAnalysis seems to give dependence information on memory refs. But it seems to not be used by LICM…

Yes, the current LICM uses alias analysis in a more direct manner (look for AliasSetTracker).

Also MemoryDependenceAnalysis "determines, for a given memory operation, what preceding memory operations it depends on".

My question is: Where is really done this dependence analysis. The one which figures out which Instructions depends on others?

Simply if I have:
%0 = load i32, i32* %coucou, align 4
%1 = load i32, i32* %fact, align 4
%2 = load i32, i32* %i, align 4
%mul = mul nsw i32 %1, %2

mul instruction will depends on the two precedents loads because it uses their results %1 and %2 but not the first one.

I guess this is done somewhere, and there is a special representation of this information but I didn't find, I'm a bit lost ^^'

If you call "operands()" on the Instruction, it will return %1 and %2. Please keep in mind that LLVM IR is SSA.

-Eli

Ty Eli for your answer.

Exactly. If LICM can prove the load is in fact invariant, it will move it out of the loop. Can you show me the complete function you’re looking at? Have you run mem2reg on your IR? -Eli

Ty Eli for your answer.

Hi all!

I'm new here, and would like to implement my own Loop Invariant
Detection adding some more information on Quasi-Invariants.

First, is there anything about Quasi-Invariants detection in LLVM I
would missed?

I've seen LICM using LoopInfo::isLoopInvariant for finding invariants.
It seems that this method considers a Value invariant if:
- it's an Instruction not presents in the current loop (what does it
mean? There is no dependence analysis on In and Out "variables" of all
instructions in the loop?)

isLoopInvariant just checks whether the definition of a value is an
instruction inside the loop.

Ok, the term "definition" makes it clear. Do, if here it's:
%1 = load i32, i32* %fact, align 4
%mul = mul nsw i32 %1, %2

load i32, i32* %fact, align 4 is the def of %1 and it's inside the loop
then it's not invariant…

Exactly. If LICM can prove the load is in fact invariant, it will move it
out of the loop.

- this Value is not an Instruction (then a Constant I guess…).

Or an function argument, or a few other obscure things which don't really
matter in this context.

I've seen LoopAccessAnalysis using it too. What does this analysis do

exactly on loop invariant address?

ScalarEvolution::isLoopInvariant works on SCEV expressions instead of
Values, but it's essentially the same thing.

What can offer this SCEV expression more than Values?

See the comment at the beginning of lib/Analysis/ScalarEvolution.cpp for
a brief description and some references.

Also DependenceAnalysis seems to give dependence information on memory
refs. But it seems to not be used by LICM…

Yes, the current LICM uses alias analysis in a more direct manner (look
for AliasSetTracker).

Also MemoryDependenceAnalysis "determines, for a given memory operation,
what preceding memory operations it depends on".

My question is: Where is really done this dependence analysis. The one
which figures out which Instructions depends on others?

Simply if I have:
%0 = load i32, i32* %coucou, align 4
%1 = load i32, i32* %fact, align 4
%2 = load i32, i32* %i, align 4
%mul = mul nsw i32 %1, %2

mul instruction will depends on the two precedents loads because it uses
their results %1 and %2 but not the first one.

I guess this is done somewhere, and there is a special representation of
this information but I didn't find, I'm a bit lost ^^'

If you call "operands()" on the Instruction, it will return %1 and %2.
Please keep in mind that LLVM IR is SSA.

Yes but if I understand well, the AliasSetTracker can tell me which load
it corresponds to…
How can I use this AliasSetTracker to disambiguate the registers?
Here it's just having the correspondence %1 → %fact and %2 → %i

It would be just perfect for me to have the "real" In and Out of each
Instruction.
Maybe I should work on another level or with another object representation?

Ty again :slight_smile:

Can you show me the complete function you're looking at? Have you run
mem2reg on your IR?

I was looking the LoopInvariantCodeMotion::runOnLoop.

No I didn't run mem2reg on my IR…
Is it necessary?

I finally use the address of the operands and instruction to have a kind of
ID of each %<num>
It seems that it refers well what I want…

Let be the Instruction I:
%0 = mul nsw i32 %1, %2

&I = 0x3d9f850 → %0
operands(0)→get() = 0x3d9f7bc → %1
operands(1)→get() = 0x3d9f80c → %2

then it should be ok if I take this for finding my dependencies between
Instructions?

It’s not necessary for correctness, but if you want to understand how the LLVM optimizer works in practice, you’ll want to look at realistic input to LICM. Yes, you can use an Instruction* to identify an instruction. -Eli

Thank you again Eli,

I would like to know if it’s not better to use DependenceAnalysis to know which instruction depends on others…

I’m running this pass on a simple example:

while.body: ; preds = %while.cond
%1 = load i32, i32* %y, align 4 ← I1
%2 = load i32, i32* %y, align 4
%mul = mul nsw i32 %1, %2 ← I2
store i32 %mul, i32* %z, align 4
%3 = load i32, i32* %z, align 4
call void @use(i32 %3)
%4 = load i32, i32* %x, align 4
%5 = load i32, i32* %x, align 4
%add = add nsw i32 %4, %5
store i32 %add, i32* %y, align 4
%6 = load i32, i32* %y, align 4
call void @use(i32 %6)
%7 = load i32, i32* %x2, align 4
store i32 %7, i32* %x, align 4
%8 = load i32, i32* %x, align 4
call void @use(i32 %8)
br label %while.cond

and here, for instance, I’m expecting to have a dependence between
%1 = load i32, i32* %y, align 4 → I1
… ↓ …
%mul = mul nsw i32 %1, %2 → I2

simply because the %mul uses %1 as input.

But when I dump the dependence “depends(I1,I2,true)” I have nothing… null.

Did I forget something?

DependenceAnalysis computes whether the memory accesses in two instructions overlap. A multiply doesn't access memory, therefore the memory accesses don't overlap.

-Eli

Yes, in fact I was not searching for that bur more dependence between instructions.
And we can have that by recursively search on operands. I didn’t know that thank to the SSA form, operands give us the associated assignment instructions then the potentially dependence tree.

Thank you for your help Eli :slight_smile: