Here is a first analysis of the issue. The relevant part of the IR is shown below, with some instruction prefixed for reference in the analysis.

  ...

codeRepl:                                         ; preds = %for.body, %entry
E %4 = phi i32* [ %arrayidx13, %for.body ], [ %j, %entry ]
  %targetBlock = call i1 @main_for.cond(i32* %jj7)
  br i1 %targetBlock, label %for.body, label %codeRepl2

for.body:                                         ; preds = %codeRepl
  %5 = load i32* %jj7, align 4, !tbaa !1
  %add = add i32 %5, 1
  %idxprom = zext i32 %add to i64
  %arrayidx3 = getelementptr inbounds [100 x i32]* %uh, i64 0, i64 %idxprom
  %6 = load i32* %arrayidx3, align 4, !tbaa !1
  %idxprom4 = zext i32 %5 to i64
  %arrayidx5 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom4
  %7 = load i32* %arrayidx5, align 4, !tbaa !1
  %sub6 = sub i32 %7, %6
A store i32 %sub6, i32* %arrayidx5, align 4, !tbaa !1
  %8 = load i32* %j, align 4, !tbaa !1
  %sub8 = sub i32 0, %8
  store i32 %sub8, i32* %j, align 4, !tbaa !1
D %9 = load i32* %4, align 4, !tbaa !1
B store i32 %9, i32* %arrayidx5, align 4, !tbaa !1
  %sub11 = add i32 %5, -1
  %idxprom12 = zext i32 %sub11 to i64
  %arrayidx13 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom12
C call void @main_for.inc(i32* %jj7)
  br label %codeRepl

A is (wrongly) removed by DSE, because it believes B kills it. It does not see that %4 in D may alias with %arrayidx5 in A.

BasicAA computes the difference between %arrayidx5 and %arrayidx13 and finds a constant difference, which is not valid as C can (and has !) modified %jj7, which is the index in %oa5.

Created attachment 11683 [details]
Manually reduced testcase

The attached testcase is a manually reduced version of the bugpoint testcase.

(In reply to comment #2)
> Created attachment 11683 [details]
> Manually reduced testcase
> 
> The attached testcase is a manually reduced version of the bugpoint testcase.

Thanks for looking at this! Do you see what part of BasicAA is at fault (I guess that BasicAliasAnalysis::aliasPHI is the problem)?

I more or less see what is at fault. The problem indeed shows up in BasicAliasAnalysis::aliasPHI, but I do not (yet) understand how BasicAA handles loops, and particularly why it does not see that main_for.inc can just do whatever it wants with the pointer.

I definitely need help on this.

This bugs looks rather serious to me, and it may be the same which is biting us in PR18067, in another pass, but with a similar code structure.

Wow this is indeed scary :) … and seems to have been in there for a long long time (I have tested as far back as 3.1, but at least 2.9)


define i32 @pr18068(i32* %jj7, i32* %j) #0 {                                         
entry:
  %oa5 = alloca [100 x i32], align 16                                                
  br label %codeRepl
        
codeRepl:                                         ; preds = %for.body, %entry        
  %0 = phi i32* [ %arrayidx13, %for.body ], [ %j, %entry ]                           
  %targetBlock = call i1 @cond(i32* %jj7)                                            
  br i1 %targetBlock, label %for.body, label %bye                                    
        
for.body:                                         ; preds = %codeRepl                
  %1 = load i32* %jj7, align 4, !tbaa !1    
                                         
  %idxprom4 = zext i32 %1 to i64                                                     
  %arrayidx5 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom4        
  %2 = load i32* %arrayidx5, align 4, !tbaa !1                                       
  %sub6 = sub i32 %2, 6
  store i32 %sub6, i32* %arrayidx5, align 4, !tbaa !1                                
  ; %0 and %arrayidx5 can be aliasing ! It is not safe to DSE the above store.       
  %3 = load i32* %0, align 4, !tbaa !1                                               
  store i32 %3, i32* %arrayidx5, align 4, !tbaa !1
  %sub11 = add i32 %1, -1                                                            
  %idxprom12 = zext i32 %sub11 to i64                                                
  %arrayidx13 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom12      
  call void @inc(i32* %jj7)
  br label %codeRepl

bye:                                        ; preds = %codeRepl                      
  %.reload = load i32* %jj7, align 4
  ret i32 %.reload             
} 

As Arnaud correctly observed the root of this problem is that a query for "aliasCheck(%arrayidx5, %arrayidx13)" returns “NoAlias”. 

This in turn makes the phi “%0” NoAlias "%arrayidx5” because it is believed that 
 noalias(%j, arrayidx5) and noalias(%arrayidx5, %arrayidx13) 
so we believe the operands of the phi “%0” don’t alias "%arrayidx5” which makes the phi not alias “%arrayidx5”.

So, why do we believe “noalias(%arrayidx5, %arrayidx13)”?

When analyze

%arrayidx5 = gep %oa, 0, %load

%arrayidx13 = gep %oa, 0, (%load - #AConst)


aliasGEP()
 … 
 GEP1BaseOffset -= GEP2BaseOffset;
 GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices);
 …
 if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) {
   .. return NoAlias;
 }

We get a constant difference of #AConst (-4) and a variable difference which is the difference between “%load” and “%load”. Because there are paths (%arrayidx13->back edge->%arrayidx5) under which those two loads are not the same execution of a load it is not safe to assume their value is the same.
In fact, we can only assume that “function invariant” values are the same.

I.e the logic that when Dest[i] == Src[j] we can simply ignore it is not a valid one:

GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
                               const SmallVectorImpl<VariableGEPIndex> &Src) {
  if (Src.empty()) return;

  for (unsigned i = 0, e = Src.size(); i != e; ++i) {
    const Value *V = Src[i].V;
    ExtensionKind Extension = Src[i].Extension;
    int64_t Scale = Src[i].Scale;

    // Find V in Dest.  This is N^2, but pointer indices almost never have more
    // than a few variable indexes.
    for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
      if (Dest[j].V != V || Dest[j].Extension != Extension) continue;

      // If we found it, subtract off Scale V's from the entry in Dest.  If it
      // goes to zero, remove the entry.
      if (Dest[j].Scale != Scale)
        Dest[j].Scale -= Scale;
      else
        Dest.erase(Dest.begin()+j); <<< Ignore if Value* are the same ?!
      Scale = 0;
      break;
    }

    // If we didn't consume this entry, add it to the end of the Dest list.
    if (Scale) {
      VariableGEPIndex Entry = { V, Extension, -Scale };
      Dest.push_back(Entry);
    }
  }
}

Or alternatively we have to start looking at possible paths through the cfg (be a lot more careful at phis).

Let me try alternative one and see what that does to llvm test-suite and external (although, I fear badness).

xref: rdar://15653794

The problem really is the evaluation through the phi node:

check-alias(%0 = PHI(%j, %array13), %array5) =
  check-alias(%j, %array5) V
  check-alias(%array13, %array5)
  
because of the cycle (we are following %array13 "to the previous iteration") "Value"s don't necessarily imply value equivalence anymore.

Maybe an approach where we build a set of phi nodes we have followed and when we check value equivalence we also make sure this value dominates the phis would work ...

(In reply to comment #7)
> The problem really is the evaluation through the phi node:
> 
> check-alias(%0 = PHI(%j, %array13), %array5) =
>   check-alias(%j, %array5) V
>   check-alias(%array13, %array5)
>   
> because of the cycle (we are following %array13 "to the previous iteration")
> "Value"s don't necessarily imply value equivalence anymore.
> 
> Maybe an approach where we build a set of phi nodes we have followed and
> when we check value equivalence we also make sure this value dominates the
> phis would work ...

I think that makes sense. I suspect that you'll need a cutoff on the dominance search -- we should try to set this so that we don't regress at least anything in the test suite that this currently catches.

Fixed in r198290.

*** Bug 18067 has been marked as a duplicate of this bug. ***