Add one more No-alias case to alias analysis.

[jaykang10]

Summary

Let's look at following C code snippet.

char buf[4];
int idx = any value;
char *a = buf[3 - idx];
char *b = buf[idx];

a and b are not aliased. As a result, if the offsets has form as below,
we can say it is not aliased.

offset1 = odd number - index;
offset2 = index;

[hfinkel]

I put this on the llvm-dev thread, but to repeat it here:

In your example, we have:

3 - idx == idx => 3 == 2*idx

and you've generalized this slightly to make this:

(odd number) == 2*idx

which makes sense. I think that we can go further looking at:

n == 2*idx

and, calling computeKnownBits on n and idx, then asking whether:

knownZeros(n) == (knownZeros(idx) << 1) | 1 and
knownOnes(n) == knownOnes(idx) << 1

(please note the comment in aliasSameBasePointerGEPs regarding avoiding
PR32314)

also, if we have more than one array access, we can have:

n - idx == m - idx

then we have:

n-m == 2*idx

and so we can check:

knownZeros(n-m) == (knownZeros(idx) << 1) | 1 and
knownOnes(n-m) == knownOnes(idx) << 1

Sadly, we don't have a good API to do the knownBits check on the
subtraction of non-constants, but you only need the constants in your
case, and we can leave the more-general case for future work.

[nlopes]

lib/Analysis/BasicAliasAnalysis.cpp

1813

you don't need the zext here. The value should have at least 1 bit, so that's sufficient to test for even/odd.

[nlopes]

lib/Analysis/BasicAliasAnalysis.cpp

1883

BTW don't you need to limit this trick to 1 byte accesses?

[hfinkel]

I think that this optimization is going to be very fragile in practice without also handling the case where both sides look like (m-idx). Nevertheless, it's good to make AA changes in minimal small increments. Let's try this single case for now.

Even with this, however, regarding this:

It seems the 'computeKnownBits' does not handle non-constant values well.

For example,

define void @test(i32 %idx) {
entry:
 %sub = sub nsw i32 3, %idx

It fails to get Zero and One from %idx.

I'm not sure you mean? In this case, nothing is known about idx, so what would it get?

However, if you do something like:

 ... @test(i32 %i) {
  %idx = and i32 %i, 3
  %sub nsw i32 3, %idx
}

then computeKnownBits will know something about the bits of idx.

lib/Analysis/BasicAliasAnalysis.cpp

1812

Don't need { } here.

1816

Don't need { } here.

1822

Don't need { } here. Also, is there an extra set of parenthesis here?

1879

Don't need { } here.

[jaykang10]

lib/Analysis/BasicAliasAnalysis.cpp

1813

Oops, sorry... I have updated it with @hfinkel 's comment.

[jaykang10]

knownZeros(n) == (knownZeros(idx) << 1) | 1 and
knownOnes(n) == knownOnes(idx) << 1

I meant if nothing is known about idx, we fail to get No-alias opportunity. If there is nothing for KnownBits, let's just check odd number and the idx is used by both offsets as below.

if (success of computeKnownBits with `n` and `idx`) {
  knownZeros(n) == (knownZeros(idx) << 1) | 1 and
  knownOnes(n) == knownOnes(idx) << 1
} else {
  check just LHS is odd number and RHS is shared by offsets.
}

How do you think about it? @hfinkel

[hfinkel]

In D48066#1129585, @jaykang10 wrote:

knownZeros(n) == (knownZeros(idx) << 1) | 1 and
knownOnes(n) == knownOnes(idx) << 1

I meant if nothing is known about idx, we fail to get No-alias opportunity. If there is nothing for KnownBits, let's just check odd number and the idx is used by both offsets as below.

if (success of computeKnownBits with `n` and `idx`) {
  knownZeros(n) == (knownZeros(idx) << 1) | 1 and
  knownOnes(n) == knownOnes(idx) << 1
} else {
  check just LHS is odd number and RHS is shared by offsets.
}

How do you think about it? @hfinkel

I don't understand what you're saying. Once you shift, you know that the lowest-order bit is zero. You can naturally combine that with whatever other information also happens to be known about idx.

[jaykang10]

I don't understand what you're saying. Once you shift, you know that the lowest-order bit is zero. You can naturally combine that with whatever other information also happens to be known about idx.

Ah... I understand it now... I am sorry for late understand... I am not smart person. I have updated code. Please review whether it is correct or not. If it is correct, I will write the code for "n - m == 2 * idx". Thank you very much @hfinkel !!!

lib/Analysis/BasicAliasAnalysis.cpp

for (unsigned i = 0, e = Src.size(); i != e; ++i) {
     // If we didn't consume this entry, add it to the end of the Dest list.
     if (Scale) {
       VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
       Dest.push_back(Entry);
     }
   }
 }
 
+static bool checkFormOddNumSubOffset(const Value *V1, const Value *V2,
+                                     unsigned BitWidth, const DataLayout &DL) {
+  if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V1)) {
+    if (BOp->getOpcode() != Instruction::Sub) {
+      return false;
+    }
+
+    if (BOp->getOperand(1) != V2) {
+      return false;
+    }
+
+    KnownBits KnownLHS = computeKnownBits(BOp->getOperand(0), DL);
+    // Check odd number.
+    if ((KnownLHS.One.countTrailingZeros()) == 0) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
 bool BasicAAResult::constantOffsetHeuristic(
     const SmallVectorImpl<VariableGEPIndex> &VarIndices, LocationSize V1Size,
     LocationSize V2Size, int64_t BaseOffset, AssumptionCache *AC,
     DominatorTree *DT) {
   if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
       V2Size == MemoryLocation::UnknownSize)
     return false;
 
bool BasicAAResult::constantOffsetHeuristic(
   const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
                                         V0SExtBits, DL, 0, AC, DT, NSW, NUW);
   NSW = true;
   NUW = true;
   const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
                                         V1SExtBits, DL, 0, AC, DT, NSW, NUW);
 
   if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
-      V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
+      V0SExtBits != V1SExtBits) {
+    return false;
+  }
+
+  if (!isValueEqualInPotentialCycles(V0, V1)) {
+    // Let's look at following C code snippet.
+    //
+    // char buf[4];
+    // int idx = any value;
+    // char *a = buf[3 - idx];
+    // char *b = buf[idx];
+    //
+    // a and b are not aliased. As a result, if the offsets has form as below,
+    // we can say it is not aliased.
+    //
+    // offset1 = odd number - index;
+    // offset2 = index;
+    if (V1Size != V2Size) {
       return false;
+    }
+    unsigned BitWidth = V1Offset.getBitWidth();
+    if (checkFormOddNumSubOffset(V0, V1, BitWidth, DL) ||
+        checkFormOddNumSubOffset(V1, V0, BitWidth, DL)) {
+      return true;
+    }
+
+    return false;
+  }
 
   // We have a hit - Var0 and Var1 only differ by a constant offset!
 
   // If we've been sext'ed then zext'd the maximum difference between Var0 and
   // Var1 is possible to calculate, but we're just interested in the absolute
   // minimum difference between the two. The minimum distance may occur due to
   // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
   // the minimum distance between %i and %i + 5 is 3.

test/Analysis/AliasSet/oddnum-sub-index.ll

+; RUN: opt -basicaa -print-alias-sets -S -o - < %s 2>&1 | FileCheck %s --check-prefix=CHECK
+
+@buf = common local_unnamed_addr global [4 x i8] zeroinitializer, align 1
+
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod       Pointers: (i8* %arrayidx, 1)
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod       Pointers: (i8* %arrayidx2, 1)
+define void @test(i32 %idx) {
+entry:
+  %sub = sub nsw i32 3, %idx
+  %idxprom = sext i32 %sub to i64
+  %arrayidx = getelementptr inbounds [4 x i8], [4 x i8]* @buf, i64 0, i64 %idxprom
+  %idxprom1 = sext i32 %idx to i64
+  %arrayidx2 = getelementptr inbounds [4 x i8], [4 x i8]* @buf, i64 0, i64 %idxprom1
+  store i8 1, i8* %arrayidx, align 1
+  store i8 2, i8* %arrayidx2, align 1
+  ret void
+}