Thomas RUBIANO via llvm-dev
2017-Jan-19 10:16 UTC
[llvm-dev] Loop Invariants Detection questions
On Wed, Jan 18, 2017 at 8:05 PM, Friedman, Eli <efriedma at codeaurora.org> wrote:> On 1/18/2017 2:56 AM, Thomas RUBIANO wrote: > > Ty Eli for your answer. > > On Tue, Jan 17, 2017 at 8:11 PM, Friedman, Eli <efriedma at codeaurora.org> > wrote: > >> On 1/17/2017 7:12 AM, Thomas RUBIANO via llvm-dev wrote: >> >>> 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 :) > > > 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?> > -Eli > > -- > Employee of Qualcomm Innovation Center, Inc. > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project > >-- RUBIANO Thomas -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170119/14a05939/attachment.html>
Friedman, Eli via llvm-dev
2017-Jan-19 19:04 UTC
[llvm-dev] Loop Invariants Detection questions
On 1/19/2017 2:16 AM, Thomas RUBIANO wrote:> > > On Wed, Jan 18, 2017 at 8:05 PM, Friedman, Eli > <efriedma at codeaurora.org <mailto:efriedma at codeaurora.org>> wrote: > > On 1/18/2017 2:56 AM, Thomas RUBIANO wrote: >> Ty Eli for your answer. >> >> On Tue, Jan 17, 2017 at 8:11 PM, Friedman, Eli >> <efriedma at codeaurora.org <mailto:efriedma at codeaurora.org>> wrote: >> >> On 1/17/2017 7:12 AM, Thomas RUBIANO via llvm-dev wrote: >> >> 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 :) > > 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?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.> > 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?Yes, you can use an Instruction* to identify an instruction. -Eli -- Employee of Qualcomm Innovation Center, Inc. Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170119/e973feea/attachment.html>
Thomas RUBIANO via llvm-dev
2017-Jan-20 12:43 UTC
[llvm-dev] Loop Invariants Detection questions
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? On Thu, Jan 19, 2017 at 8:04 PM, Friedman, Eli <efriedma at codeaurora.org> wrote:> On 1/19/2017 2:16 AM, Thomas RUBIANO wrote: > > > > On Wed, Jan 18, 2017 at 8:05 PM, Friedman, Eli <efriedma at codeaurora.org> > wrote: > >> On 1/18/2017 2:56 AM, Thomas RUBIANO wrote: >> >> Ty Eli for your answer. >> >> On Tue, Jan 17, 2017 at 8:11 PM, Friedman, Eli <efriedma at codeaurora.org> >> wrote: >> >>> On 1/17/2017 7:12 AM, Thomas RUBIANO via llvm-dev wrote: >>> >>>> 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 :) >> >> >> 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? > > > 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. > > > 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? > > > > Yes, you can use an Instruction* to identify an instruction. > > -Eli > > -- > Employee of Qualcomm Innovation Center, Inc. > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project > >-- RUBIANO Thomas -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170120/4ad92b26/attachment.html>