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
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.
Hope this helps.
Regards,
Ashutosh
From: "Ashutosh Nema" <Ashutosh.Nema@amd.com>
To: "songlh" <songlh@cs.wisc.edu>, llvmdev@cs.uiuc.edu
Sent: Wednesday, February 11, 2015 3:20:27 AM
Subject: Re: [LLVMdev] question about licmHi,
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
From: "Hal Finkel" <hfinkel@anl.gov>
To: "Ashutosh Nema" <Ashutosh.Nema@amd.com>
Cc: llvmdev@cs.uiuc.edu
Sent: Wednesday, February 11, 2015 3:58:39 AM
Subject: Re: [LLVMdev] question about licm> From: "Ashutosh Nema" <Ashutosh.Nema@amd.com>
> To: "songlh" <songlh@cs.wisc.edu>, llvmdev@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
Hi Ashutosh and Hal,
Thanks a lot for the explanation! It is clear to me right now.
Best
Linhai
From: "Hal Finkel" <hfinkel@anl.gov>
To: "Ashutosh Nema" <Ashutosh.Nema@amd.com>
Cc: llvmdev@cs.uiuc.edu
Sent: Wednesday, February 11, 2015 3:58:39 AM
Subject: Re: [LLVMdev] question about licmFrom: "Ashutosh Nema" <Ashutosh.Nema@amd.com>
To: "songlh" <songlh@cs.wisc.edu>, llvmdev@cs.uiuc.edu
Sent: Wednesday, February 11, 2015 3:20:27 AM
Subject: Re: [LLVMdev] question about licmHi,
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