why gvn does not work for global variables

Hi, All,

Suppose I have a very simple code like this and variable ‘a’ is a global variable:

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