Alias analysis bug with compilation flags -O1 -Xclang -disable-O0-optnone

[yiansu]

Hello, we found that the following program (test.cpp) exposes a bug in SVF's alias analysis when compiling with flags -O1 -Xclang -disable-O0-optnone using clang.

#include <aliascheck.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Dot{
  int val;
} Dot;

typedef struct IndirectDot {
  Dot *dot;
} IndirectDot;

int main (int argc, char *argv[]) {
  Dot *dot = (Dot *)malloc(sizeof(Dot));
  IndirectDot *indirectDot = (IndirectDot *)malloc(sizeof(IndirectDot));
  indirectDot->dot = dot;

  // Dot array allocation and initialization
  Dot **dotArray = (Dot **)malloc(sizeof(Dot *) * argc);
  for (int i = 0; i < argc; i++) {
    Dot *tmp = (Dot *)malloc(sizeof(Dot));
    tmp->val = argc++;
    dotArray[i] = tmp;
  }

  // Main computation
  int result = 0;
  for (int i = 0; i < argc; i++) {
    dot->val = dotArray[i]->val;
    Dot *dot2 = indirectDot->dot;
    MAYALIAS(&(dot->val), &(dot2->val));
    result += sqrt(dot2->val);
  }

  printf("%d\n", result);

  return 0;
}

How to reproduce the bug

1. Add __attribute__((noinline)) in the MAYALIAS function in aliascheck.h such that this call doesn't get dead code eliminated by clang.
2. run clang++ -O1 -Xclang -disable-O0-optnone -c -emit-llvm -g test.cpp -o test.bc
3. run any Andersen-based pointer analysis wpa -ander -stat=false test.bc, this will fail the MAYALIAS test

Note

The bug is not exposed using different compilation flags, such as

1. clang++ -O0 -Xclang -disable-O0-optnone -c -emit-llvm -g test.cpp -o test.bc
2. clang++ -c -emit-llvm -g test.cpp -o test.bc

[LegalZhang]

We will review the issue and take care of the bug.

[yiansu]

Hi, has there been any progress on fixing this bug?

[yuleisui]

Could you also provide the two bc files, before and after optimization?

[yuleisui]

Could you also try to make the example as small as possible so that my debugging would be easier?

[yuleisui]

Unfortunately, I can't reproduce your error. After optimisation under -O1 -Xclang -disable-O0-optnone, the two arguments at the MAYALIAS become the same pointer (see attached).

test.bc-under-O1.zip

[yiansu]

Thanks for taking a look over this. Below is the exact step I followed to produce the bug. I trimmed the test a little bit to make it cleaner.

1. Download and build SVF:

git clone https://github.com/SVF-tools/SVF.git
cd SVF
source ./build.sh

2. Download the SVF Test-Suite:

git clone https://github.com/SVF-tools/Test-Suite.git
cd Test-Suite

3. Add the __attribute__((noinline)) in front of both MAYALIAS and NOALIAS functions.
4. Add the following test case in the same directory called test.cpp

#include "aliascheck.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Dot{
  int val;
} Dot;

typedef struct IndirectDot {
  Dot *dot;
} IndirectDot;

int main (int argc, char *argv[]) {
  Dot *dot = (Dot *)malloc(sizeof(Dot));
  IndirectDot *indirectDot = (IndirectDot *)malloc(sizeof(IndirectDot));
  indirectDot->dot = dot;

  // Main computation
  int result = 0;
  Dot *dot2 = indirectDot->dot;
  MAYALIAS(&(dot->val), &(dot2->val));
  result += sqrt(dot2->val);

  printf("%d\n", result);

  return 0;
}

5. Run the following command to reproduce the bug

clang++ -O1 -Xclang -disable-O0-optnone -c -emit-llvm -g test.cpp -o test.bc
wpa -ander -stat=false test.bc

Below is what prints out on my terminal:

[AndersenWPA] Checking _Z8MAYALIASPvS_
	 FAILURE :_Z8MAYALIASPvS_ check <id:1, id:1> at ({ "ln": 25, "cl": 5, "fl": "test.cpp" })
Assertion failed: (false && "test case failed!"), function validateSuccessTests, file PointerAnalysis.cpp, line 560.
zsh: abort      wpa -ander -stat=false test.bc

However, if you replace the verify function MAYALIAS to be NOALIAS and re-run the same command, it prints

[AndersenWPA] Checking _Z7NOALIASPvS_
	 SUCCESS :_Z7NOALIASPvS_ check <id:1, id:1> at ({ "ln": 25, "cl": 5, "fl": "test.cpp" })

but this result is incorrect, the two memory addresses &(dot->val) and &(dot2->val) obviously MAYALIAS.

I attach the test source along with the bitcode files here: test.zip

[yuleisui]

@yiansu the bc file you gave me the two arguments are llvm's poison pointers after optimisation tail call void @_Z8MAYALIASPvS_(ptr poison, ptr poison), !dbg !258. Hence the SVFVars for both argument pointers are reserved blackhole pointer ID as 1 (you could see it in your message FAILURE :_Z8MAYALIASPvS_ check <id:1, id:1> at ({ "ln": 25, "cl": 5, "fl": "test.cpp" }).

Could you redo the correct optimization and send back the bc?

Thanks,

[yiansu]

@yuleisui Sorry for not getting back to you sooner.

Unfortunately, the test case needs to remain a certain level of complexity, so I borrowed it from my original repost. Also, our group uses LLVM-14.0.6, so I checked out SVF-2.9. I'm not sure if this bug still exists in the master branch because LLVM 16 optimizes the bitcode differently than 14, making the bug hard to reproduce.

Below is the exact step I followed to generate the bug:

1. Download SVF-2.9:

git clone https://github.com/SVF-tools/SVF.git
cd SVF
git fetch && git checkout tags/SVF-2.9 -b SVF-2.9

2. Modify line 210 of script build.sh to be the following, this is a bug and exists for script setup.sh (line 70) as well

LD_LIBRARY_PATH=$LLVM_DIR/lib:$Z3_DIR/bin:$LD_LIBRARY_PATH

3. Build SVF-2.9

source build.sh

4. Download SVF Test-Suite:

git clone https://github.com/SVF-tools/Test-Suite.git
cd Test-Suite

5. Add the [[clang::optnone]] in front of both MAYALIAS and NOALIAS functions.
6. Add the following test case in the same directory called test.cpp

#include "aliascheck.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Dot{
  int dummy_field;
  int val;
} Dot;

typedef struct IndirectDot {
  Dot *dot;
} IndirectDot;

int main (int argc, char *argv[]) {
  Dot *dot = (Dot *)malloc(sizeof(Dot));
  IndirectDot *indirectDot = (IndirectDot *)malloc(sizeof(IndirectDot));
  indirectDot->dot = dot;

  // Dot array allocation and initialization
  Dot **dotArray = (Dot **)malloc(sizeof(Dot *) * argc);
  for (int i = 0; i < argc; i++) {
    Dot *tmp = (Dot *)malloc(sizeof(Dot));
    tmp->val = argc++;
    dotArray[argc - 1] = tmp;
  }

  // Main computation
  Dot *dot2 = indirectDot->dot;
  MAYALIAS(&(dot->val), &(dot2->val));
  int result = 0;
  for (int i = 0; i < argc; i++) {
    dot->val = dotArray[argc - 1]->val;
    result += sqrt(dot2->val);
  }

  printf("%d\n", result);

  return 0;
}

7. Run the following command to reproduce the bug

clang++ -O1 -Xclang -disable-O0-optnone -c -emit-llvm -g test.cpp -o test.bc
wpa -ander -stat=false test.bc

Below is what prints out on my terminal:

[AndersenWPA] Checking _Z8MAYALIASPvS_
	 FAILURE :_Z8MAYALIASPvS_ check <id:214, id:216> at ({ "ln": 30, "cl": 3, "fl": "test.cpp" })
wpa: /home/yiansu/SVF/svf/lib/MemoryModel/PointerAnalysis.cpp:560: virtual void SVF::PointerAnalysis::validateSuccessTests(std::string): Assertion `false && "test case failed!"' failed.
Aborted (core dumped)

However, if you replace the verify function MAYALIAS to be NOALIAS and re-run the same command, it prints

[AndersenWPA] Checking _Z7NOALIASPvS_
	 SUCCESS :_Z7NOALIASPvS_ check <id:214, id:216> at ({ "ln": 30, "cl": 3, "fl": "test.cpp" })

but this result is incorrect, the two memory addresses &(dot->val) and &(dot2->val) obviously MAYALIAS.

I attach the test source along with the bitcode files here: test.zip

[yuleisui]

I have just read your LLVM-14 bitcode. It appears to me that this version of LLVM has an 'incorrect' optimisation (from my point of view) that uses an unbalanced method of storing a value in the first field of IndirectDot and reading the same value from it. Consequently, SVF is unable to perform the correct aliasing on this 'incorrectly' optimised bitcode.

  %5 = call noalias dereferenceable_or_null(8) i8* @malloc(i64 noundef 8) #9, !dbg !728
  %6 = bitcast i8* %5 to %struct.IndirectDot*, !dbg !729
  %7 = getelementptr inbounds %struct.IndirectDot, %struct.IndirectDot* %6, i64 0, i32 0, !dbg !730
  %8 = bitcast i8* %5 to i8**, !dbg !731
  store i8* %3, i8** %8, align 8, !dbg !731, !tbaa !732
  %20 = load %struct.Dot*, %struct.Dot** %7, align 8, !dbg !741, !tbaa !732

In the above bitcode, %5 and %8 both point to the result of malloc(sizeof(IndirectDot)), while %3 points to malloc(sizeof(Dot)). When storing %3 in %8, which corresponds to indirectDot->dot = dot, there is no field access (getelementptr). However, when loading the first field dot2 = indirectDot->dot, %7 is first obtained through getelementptr, which is unbalanced compared to the store operation. I believe this is due to aggressive optimisation. If you want to make the first field and base object the same, SVF has an option -ff-eq-base. If you add this option, it should pass the MAYALIAS, but be aware that this optimised bitcode does look unusual after optimisation.

[yiansu]

Thanks for the explanation; that makes sense to me.

I've added the -ff-eq-base option to our compilation pipeline and our failing tests now passed. Many thanks!