----- Original Message -----> From: "Ashutosh Nema" <Ashutosh.Nema at amd.com> > To: "songlh" <songlh at cs.wisc.edu>, llvmdev at cs.uiuc.edu > Sent: Wednesday, February 11, 2015 3:20:27 AM > Subject: Re: [LLVMdev] question about licm > > Hi, > > LICM can only hoist instructions which dominates all loop exit > blocks. > In this case 'upper[j]' is not dominating exit block as its appearing > in second operand of logical AND operator. > > Prior to hoisting it check for condition in 'isGuaranteedToExecute' > and it decide not to hoist it. > > <File: LICM.cpp> > 666 bool LICM::isGuaranteedToExecute(Instruction &Inst) { > 667 > 668 // We have to check to make sure that the instruction dominates > all > 669 // of the exit blocks. If it doesn't, then there is a path out > of the loop > 670 // which does not execute this instruction, so we can't hoist > it.Yes, and to add to this, the load is not safe to speculatively execute (because, as you mention, j might be larger than 10). Now this is an interesting case because the cases where upper[j] might be an out-of-bounds access are the same as those when lower[j] might be an out-of-bounds access, and lower[j] dominates upper[j]. As a result, we *could* notice this and hoist the load anyway (to after lower[j] in the loop preheader), but we currently have no capability to do this. -Hal> > Hope this helps. > > Regards, > Ashutosh > > -----Original Message----- > From: llvmdev-bounces at cs.uiuc.edu > [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of songlh > Sent: Wednesday, February 11, 2015 10:24 AM > To: llvmdev at cs.uiuc.edu > Subject: [LLVMdev] question about licm > > hi, > > I applied licm with basicaa on the following codes: > > int j = atoi(argc[1]); > int lower[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; > int upper[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; > > for(i = lower[j]; a[i] < 100 && i < upper[j]; i ++); > > I notice that upper[j] is not hoisted out from the loop. Is this > because j could be larger than 10? > > Thanks a lot! > > Best, > > Linhai > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
----- Original Message -----> From: "Hal Finkel" <hfinkel at anl.gov> > To: "Ashutosh Nema" <Ashutosh.Nema at amd.com> > Cc: llvmdev at cs.uiuc.edu > Sent: Wednesday, February 11, 2015 3:58:39 AM > Subject: Re: [LLVMdev] question about licm > > ----- Original Message ----- > > From: "Ashutosh Nema" <Ashutosh.Nema at amd.com> > > To: "songlh" <songlh at cs.wisc.edu>, llvmdev at cs.uiuc.edu > > Sent: Wednesday, February 11, 2015 3:20:27 AM > > Subject: Re: [LLVMdev] question about licm > > > > Hi, > > > > LICM can only hoist instructions which dominates all loop exit > > blocks. > > In this case 'upper[j]' is not dominating exit block as its > > appearing > > in second operand of logical AND operator. > > > > Prior to hoisting it check for condition in 'isGuaranteedToExecute' > > and it decide not to hoist it. > > > > <File: LICM.cpp> > > 666 bool LICM::isGuaranteedToExecute(Instruction &Inst) { > > 667 > > 668 // We have to check to make sure that the instruction > > dominates > > all > > 669 // of the exit blocks. If it doesn't, then there is a path > > out > > of the loop > > 670 // which does not execute this instruction, so we can't hoist > > it. > > Yes, and to add to this, the load is not safe to speculatively > execute (because, as you mention, j might be larger than 10). Now > this is an interesting case because the cases where upper[j] might > be an out-of-bounds access are the same as those when lower[j] might > be an out-of-bounds access, and lower[j] dominates upper[j]. As a > result, we *could* notice this and hoist the load anyway (to after > lower[j] in the loop preheader), but we currently have no capability > to do this.Alright, let me revise this. We do currently hoist that load out of the loop (at least when using Clang and the default optimization pipeline), because we've created a guarded loop preheader. This is done, however, by some combination of LoopSimplify and LICM. I recommend watching the default pipeline in action: $ cat /tmp/l1.c #include <stdio.h> #include <stdlib.h> int *a; int main(int argc, char *argv[]) { int j = atoi(argv[1]); int lower[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; int upper[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; for(int i = lower[j]; a[i] < 100 && i < upper[j]; i++) { printf("iteration %d\n", i); } } $ clang -O3 -S -o - -emit-llvm /tmp/l1.c -mllvm -print-after-all and you'll see what I mean. -Hal> > -Hal > > > > > Hope this helps. > > > > Regards, > > Ashutosh > > > > -----Original Message----- > > From: llvmdev-bounces at cs.uiuc.edu > > [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of songlh > > Sent: Wednesday, February 11, 2015 10:24 AM > > To: llvmdev at cs.uiuc.edu > > Subject: [LLVMdev] question about licm > > > > hi, > > > > I applied licm with basicaa on the following codes: > > > > int j = atoi(argc[1]); > > int lower[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; > > int upper[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; > > > > for(i = lower[j]; a[i] < 100 && i < upper[j]; i ++); > > > > I notice that upper[j] is not hoisted out from the loop. Is this > > because j could be larger than 10? > > > > Thanks a lot! > > > > Best, > > > > Linhai > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Hi Ashutosh and Hal,
Thanks a lot for the explanation! It is clear to me right now.
Best
Linhai
On 02/11/2015 03:58 AM, Hal Finkel wrote:> ----- Original Message -----
>> From: "Ashutosh Nema" <Ashutosh.Nema at amd.com>
>> To: "songlh" <songlh at cs.wisc.edu>, llvmdev at
cs.uiuc.edu
>> Sent: Wednesday, February 11, 2015 3:20:27 AM
>> Subject: Re: [LLVMdev] question about licm
>>
>> Hi,
>>
>> LICM can only hoist instructions which dominates all loop exit
>> blocks.
>> In this case 'upper[j]' is not dominating exit block as its
appearing
>> in second operand of logical AND operator.
>>
>> Prior to hoisting it check for condition in
'isGuaranteedToExecute'
>> and it decide not to hoist it.
>>
>> <File: LICM.cpp>
>> 666 bool LICM::isGuaranteedToExecute(Instruction &Inst) {
>> 667
>> 668 // We have to check to make sure that the instruction dominates
>> all
>> 669 // of the exit blocks. If it doesn't, then there is a path
out
>> of the loop
>> 670 // which does not execute this instruction, so we can't hoist
>> it.
> Yes, and to add to this, the load is not safe to speculatively execute
(because, as you mention, j might be larger than 10). Now this is an interesting
case because the cases where upper[j] might be an out-of-bounds access are the
same as those when lower[j] might be an out-of-bounds access, and lower[j]
dominates upper[j]. As a result, we *could* notice this and hoist the load
anyway (to after lower[j] in the loop preheader), but we currently have no
capability to do this.
>
> -Hal
>
>> Hope this helps.
>>
>> Regards,
>> Ashutosh
>>
>> -----Original Message-----
>> From: llvmdev-bounces at cs.uiuc.edu
>> [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of songlh
>> Sent: Wednesday, February 11, 2015 10:24 AM
>> To: llvmdev at cs.uiuc.edu
>> Subject: [LLVMdev] question about licm
>>
>> hi,
>>
>> I applied licm with basicaa on the following codes:
>>
>> int j = atoi(argc[1]);
>> int lower[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
>> int upper[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
>>
>> for(i = lower[j]; a[i] < 100 && i < upper[j]; i ++);
>>
>> I notice that upper[j] is not hoisted out from the loop. Is this
>> because j could be larger than 10?
>>
>> Thanks a lot!
>>
>> Best,
>>
>> Linhai
>>
_______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
On 02/11/2015 11:34 AM, Hal Finkel wrote:> ----- Original Message ----- >> From: "Hal Finkel" <hfinkel at anl.gov> >> To: "Ashutosh Nema" <Ashutosh.Nema at amd.com> >> Cc: llvmdev at cs.uiuc.edu >> Sent: Wednesday, February 11, 2015 3:58:39 AM >> Subject: Re: [LLVMdev] question about licm >> >> ----- Original Message ----- >>> From: "Ashutosh Nema" <Ashutosh.Nema at amd.com> >>> To: "songlh" <songlh at cs.wisc.edu>, llvmdev at cs.uiuc.edu >>> Sent: Wednesday, February 11, 2015 3:20:27 AM >>> Subject: Re: [LLVMdev] question about licm >>> >>> Hi, >>> >>> LICM can only hoist instructions which dominates all loop exit >>> blocks. >>> In this case 'upper[j]' is not dominating exit block as its >>> appearing >>> in second operand of logical AND operator. >>> >>> Prior to hoisting it check for condition in 'isGuaranteedToExecute' >>> and it decide not to hoist it. >>> >>> <File: LICM.cpp> >>> 666 bool LICM::isGuaranteedToExecute(Instruction &Inst) { >>> 667 >>> 668 // We have to check to make sure that the instruction >>> dominates >>> all >>> 669 // of the exit blocks. If it doesn't, then there is a path >>> out >>> of the loop >>> 670 // which does not execute this instruction, so we can't hoist >>> it. >> Yes, and to add to this, the load is not safe to speculatively >> execute (because, as you mention, j might be larger than 10). Now >> this is an interesting case because the cases where upper[j] might >> be an out-of-bounds access are the same as those when lower[j] might >> be an out-of-bounds access, and lower[j] dominates upper[j]. As a >> result, we *could* notice this and hoist the load anyway (to after >> lower[j] in the loop preheader), but we currently have no capability >> to do this. > Alright, let me revise this. We do currently hoist that load out of the loop (at least when using Clang and the default optimization pipeline), because we've created a guarded loop preheader. This is done, however, by some combination of LoopSimplify and LICM. I recommend watching the default pipeline in action: > > $ cat /tmp/l1.c > #include <stdio.h> > #include <stdlib.h> > > int *a; > > int main(int argc, char *argv[]) { > int j = atoi(argv[1]); > int lower[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; > int upper[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; > > for(int i = lower[j]; a[i] < 100 && i < upper[j]; i++) { > printf("iteration %d\n", i); > } > } > > > $ clang -O3 -S -o - -emit-llvm /tmp/l1.c -mllvm -print-after-all > > and you'll see what I mean.I find that. Last night, I simply try opt -basicaa -licm test.bc > test.opt. "test.bc" is generated without providing any -OX. Thanks a lot! Best Linhai> > -Hal > >> -Hal >> >>> Hope this helps. >>> >>> Regards, >>> Ashutosh >>> >>> -----Original Message----- >>> From: llvmdev-bounces at cs.uiuc.edu >>> [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of songlh >>> Sent: Wednesday, February 11, 2015 10:24 AM >>> To: llvmdev at cs.uiuc.edu >>> Subject: [LLVMdev] question about licm >>> >>> hi, >>> >>> I applied licm with basicaa on the following codes: >>> >>> int j = atoi(argc[1]); >>> int lower[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; >>> int upper[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; >>> >>> for(i = lower[j]; a[i] < 100 && i < upper[j]; i ++); >>> >>> I notice that upper[j] is not hoisted out from the loop. Is this >>> because j could be larger than 10? >>> >>> Thanks a lot! >>> >>> Best, >>> >>> Linhai >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >> -- >> Hal Finkel >> Assistant Computational Scientist >> Leadership Computing Facility >> Argonne National Laboratory >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>