In this homework, you are asked to implement an intra-procedural range analysis based on abstract interpretation on interval domain. We assume there are only integer variables (ignoring any integer overflow) and there is no alias relation among pointers.

The test input is test.c:

int test(int x) {
  int y = 0;
  if (x < 5) {
    y = x + 3; // < 8 
  } else {
    y = x - 3; // >= 2
  }

  x = 1;
  while (x < 100) {
    x = x + 1;
  }

  y = x;
  return y;
}

Compile the test file with the following command:

clang -O0 -fno-discard-value-names -g -emit-llvm test.c -c -o test.bc && opt -mem2reg test.bc -o test.bc

Note that we passed the option -fno-discard-value-name to keep variable names in the IR and also use LLVM optimization pass -mem2reg to eliminate redundant load & store instructions, since we assume no pointer aliasing in the program.

Your task is to implement abstract interpretation on the interval domain and output the value ranges of variable x, y after different program points (i.e., line numbers). The desired output looks like:

Line 2:
x: [-inf,inf]; y: [0,0]; 
Line 4:
x: [-inf,4]; y: [-inf,7]; 
...

Note that since a given line in the source code could map to multiple instructions in LLVM IR, you are only required to output the analysis result after line 2,4,6,9,11,14 (i.e, after an assignment statement in the source code, you could locate all the store instructions in the bitcode and easily map them to the source code line numbers).

Something to keep in mind when doing the implementation:

• You should implement the interval domain and its basic operations like addition and subtraction
• You should consider how branch condition transfers your abstract state
• You should use widening to handle loops for quick termination
• You only need to implement transfer functions which are required by this test program, since a full set of transfer functions on interval domain requires too much effort.