[LLVMbugs] [Bug 2194] New: Wrong NoAlias from Andersens alias analysis in combination with loop-reduce

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=2194

           Summary: Wrong NoAlias from Andersens alias analysis in
                    combination with loop-reduce
           Product: libraries
           Version: 2.2
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Keywords: miscompilation
          Severity: major
          Priority: P2
         Component: Interprocedural Analyses
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: giuma.cordes at gmail.com
                CC: llvmbugs at cs.uiuc.edu


Andersens returns NoAlias for pointers subject to integer pointer arithmetics:

/* anders-bug.c */
f3(int *p, int *q, int N) {
  int i, ret = 0;
  for (i = 0; i < N; i++) {
    *p++ = i;
    ret += *q++;
  }
  return ret;
}

> llvm-gcc -c -O2 -emit-llvm anders-bug.c -o anders-bug.bc
> opt -loop-reduce  -anders-aa -debug-only=anders-aa -o anders-bug.obc -f anders-bug.bc 


llvm instructions after opt:

bb:             ; preds = %bb, %bb.preheader
        %iv. = phi i32 [ 0, %bb.preheader ], [ %iv..inc, %bb ]          ; <i32>
[#uses=3]
        %ret.0.reg2mem.0 = phi i32 [ 0, %bb.preheader ], [ %tmp8, %bb ]        
; <i32> [#uses=1]
        %tmp4 = mul i32 %iv., 4         ; <i32> [#uses=2]
        %tmp5 = add i32 %p2, %tmp4              ; <i32> [#uses=1]
        %tmp56 = inttoptr i32 %tmp5 to i32*             ; <i32*> [#uses=1]
        %tmp7 = add i32 %q1, %tmp4              ; <i32> [#uses=1]
        %tmp78 = inttoptr i32 %tmp7 to i32*             ; <i32*> [#uses=1]
        store i32 %iv., i32* %tmp56, align 4
        %tmp6 = load i32* %tmp78, align 4               ; <i32> [#uses=1]
        %tmp8 = add i32 %tmp6, %ret.0.reg2mem.0         ; <i32> [#uses=2]
        %iv..inc = add i32 %iv., 1              ; <i32> [#uses=2]
        %exitcond = icmp eq i32 %iv..inc, %tmp30                ; <i1>
[#uses=1]
        br i1 %exitcond, label %bb18.loopexit, label %bb


debug output of opt, due to -debug-only=anders-aa:

Beginning constraint optimization
Beginning HVN
Finished HVN
Beginning HU
Finished HU
Finished constraint optimization
Uniting remaining pointer equivalences
Finished remaining pointer equivalences
Starting iteration #1
Starting iteration #2
Points-to graph:
[1] <universal> --> <universal>
[1] <nullptr>   --> <null>
[0] <null>      --> 
[0] artificial142534524 --> 
[1] f3:p        --> <universal>
[1] f3:q        --> <universal>
[0] f3:tmp56    --> 
[0] f3:tmp78    --> 


tmp56 and tmp78 are p and q inside the loop.  The debug output is from
-debug-only=anders-aa, and it shows that the PointsTo set of the nodes
associated to tmp56 and tmp78 are empty.  When asking to the alias analysis if
they alias, I get a NoAlias back, because indeed the intersection between two
empty sets is empty, that in this context means that they don't alias (while of
course in this case they could).

If I understand correctly, their PointTo set should rather be <universal>.

It seems to me that the problem may come from the fact that the Andersens
implementation considers only instructions of PointerType, while in this case,
the loop-reduce generates integer arithmetics for computing tmp56 and tmp78. 
So in effect tmp56 and tmp78 are disconnected in the points-to graph, and
therefore the constraint propagation phase never propagates <universal> to
them.

At a minimum the Andersens::alias method should not return NoAlias for nodes
whose PointsTo set is empty.

Ideally it would be much nicer if Andersens could be extended to make a deeper
analysis of instructions leading to pointers, i.e. not restricting it to
PointerType.  Or otherwise loop-reduce and other similar transformations should
keep the type of pointer-manipulating instructions as pointers, instead of
converting them to integers (I don't know if this would be semantically correct
though).

Thanks.


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.