[LLVMdev] question about licm

[Hal Finkel]

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