[LLVMdev] why gvn does not work for global variables

[Nick Lewycky]

Xiangyang Guo wrote:
> Hi, All,
>
> Suppose I have a very simple code like this and variable 'a' is a global
> variable:
> ***************************************************************************
> /double ** a;/
> /int main(){/
> /    a[5][10] = 0.1;/
> /    a[5][20] = 0.5;/
> /    return 0;/
> /}/
> ***************************************************************************/
> /
>
> Then I can get the IR without any optimization like this:
> ***************************************************************************
> /@a = global double** null, align 8/
> /
> /
> /; Function Attrs: nounwind uwtable/
> /define i32 @main() #0 {/
> /  %1 = alloca i32, align 4/
> /  store i32 0, i32* %1/
> /  %2 = load double*** @a, align 8/
> /  %3 = getelementptr inbounds double** %2, i64 5/
> /  %4 = load double** %3, align 8/
> /  %5 = getelementptr inbounds double* %4, i64 10/
> /  store double 1.000000e-01, double* %5, align 8/
> /  %6 = load double*** @a, align 8/
> /  %7 = getelementptr inbounds double** %6, i64 5/
> /  %8 = load double** %7, align 8/
> /  %9 = getelementptr inbounds double* %8, i64 20/
> /  store double 5.000000e-01, double* %9, align 8/
> /  ret i32 0/
> /}/
> ***************************************************************************
>
> I hope GVN can get rid of redundant 'load' and 'getelementptr'
> instructions such as '/%2 = load double*** @a, align 8/' and '/%6 = load
> double*** @a, align 8/'. So I use 'opt input.ll -basicaa -gvn -S -o
> output.ll ' , I still get :
> ***************************************************************************
> /  %2 = load double*** @a, align 8/
> /  %3 = getelementptr inbounds double** %2, i64 5/
> /  %4 = load double** %3, align 8/
> /  %5 = getelementptr inbounds double* %4, i64 10/
> /  store double 1.000000e-01, double* %5, align 8/
> /  %6 = load double*** @a, align 8/
> /  %7 = getelementptr inbounds double** %6, i64 5/
> /  %8 = load double** %7, align 8/
> /  %9 = getelementptr inbounds double* %8, i64 20/
> /  store double 5.000000e-01, double* %9, align 8/
> ***************************************************************************/
> /
>
> It seems GVN doesn't work. Then I use '-aa-eval', it seems LLVM thinks
> that is "*may alias*". But '%2' and '%6' are alias, right?
> ***************************************************************************
> /===== Alias Analysis Evaluator Report =====/
> /  45 Total Alias Queries Performed/
> /  13 no alias responses (28.8%)/
> /  32 may alias responses (71.1%)/
> /  0 partial alias responses (0.0%)/
> /  0 must alias responses (0.0%)/
> /  Alias Analysis Evaluator Pointer Alias Summary: 28%/71%/0%/0%/
> /  Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!/
> ***************************************************************************
>
> Can anyone help me to use GVN in this situation? Thanks

There's not much you can do here; nothing tells GVN that %5 != @a, so it 
thinks it needs to reload @a after you store to it.

Because 'a' is an externally visible variable, a global initialize could 
have initializes 'a' in any way before main begins. To be deliberately 
hostile, I could prepare it as such:

   a[5] = (double*)&a[-10];

In the exact case you posted there's two other facts we could optimize 
on. Firstly, there's the fact that you have two accesses. That means the 
cases break down like this:
   a) a[5] = &a[-10] therefore the later run of a[5][20] will be UB
   b) a[5] = &a[-20] therefore the earlier run of a[5][10] was UB
   c) a[5] doesn't alias 'a'
but how sure are we about (a) and (b)? What if I arrange for a linker 
script that puts 'a' here and 10 pointer-sizes later puts another global 
variable there?

The second thing we have is an 'inbounds' qualifier on getelementptr. In 
C/C++ there are rules about not being allowed to even form pointers 
outside the range of an [object begin, object end + 1], but those rules 
don't exist in llvm ir except for the 'inbounds' attribute on 
getelementptr. An inbounds getelementptr means that the base pointer 
must be within the bounds (including a one-off-the-end pointer) of a 
concrete object, which means that (a[5]) can't be pointing to &a[-10], 
given that 'a' is only sizeof(double).

Nick