[LLVMdev] question about licm

[Linhai]

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
>>