Teach basicaa that x|c == x+c when the c bits of x are clear. This

allows us to compile the example in readme.txt into:

LBB1_1:                                                     ## %bb
	movl	4(%rdx,%rax), %ecx
	movl	%ecx, %esi
	imull	(%rdx,%rax), %esi
	imull	%esi, %ecx
	movl	%esi, 8(%rdx,%rax)
	imull	%ecx, %esi
	movl	%ecx, 12(%rdx,%rax)
	movl	%esi, 16(%rdx,%rax)
	imull	%ecx, %esi
	movl	%esi, 20(%rdx,%rax)
	addq	$16, %rax
	cmpq	$4000, %rax
	jne	LBB1_1

instead of:

LBB1_1: 
	movl	(%rdx,%rax), %ecx
	imull	4(%rdx,%rax), %ecx
	movl	%ecx, 8(%rdx,%rax)
	imull	4(%rdx,%rax), %ecx
	movl	%ecx, 12(%rdx,%rax)
	imull	8(%rdx,%rax), %ecx
	movl	%ecx, 16(%rdx,%rax)
	imull	12(%rdx,%rax), %ecx
	movl	%ecx, 20(%rdx,%rax)
	addq	$16, %rax
	cmpq	$4000, %rax
	jne	LBB1_1

GCC (4.2) doesn't seem to be able to eliminate the loads in this 
testcase either, it generates:

L2:
	movl	(%rdx), %eax
	imull	4(%rdx), %eax
	movl	%eax, 8(%rdx)
	imull	4(%rdx), %eax
	movl	%eax, 12(%rdx)
	imull	8(%rdx), %eax
	movl	%eax, 16(%rdx)
	imull	12(%rdx), %eax
	movl	%eax, 20(%rdx)
	addl	$4, %ecx
	addq	$16, %rdx
	cmpl	$1002, %ecx
	jne	L2

llvm-svn: 89952

1 files changed, 13 insertions, 5 deletions

diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index fb6b9df608d..f8d8873c4f6 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -14,8 +14,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/CaptureTracking.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
@@ -26,6 +24,9 @@
 #include "llvm/IntrinsicInst.h"
 #include "llvm/Operator.h"
 #include "llvm/Pass.h"
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
@@ -381,15 +382,22 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) {
 /// GetLinearExpression - Analyze the specified value as a linear expression:
 /// "A*V + B".  Return the scale and offset values as APInts and return V as a
 /// Value*.  The incoming Value is known to be a scalar integer.
-static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset) {
+static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
+                                  const TargetData *TD) {
   assert(isa<IntegerType>(V->getType()) && "Not an integer value");
   
   if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
       switch (BOp->getOpcode()) {
       default: break;
+      case Instruction::Or:
+        // X|C == X+C if all the bits in C are unset in X.  Otherwise we can't
+        // analyze it.
+        if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), TD))
+          break;
+        // FALL THROUGH.
       case Instruction::Add:
-        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset);
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD);
         Offset += RHSC->getValue();
         return V;
       // TODO: SHL, MUL, OR.
@@ -482,7 +490,7 @@ static const Value *DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
       
       unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth();
       APInt IndexScale(Width, 0), IndexOffset(Width, 0);
-      Index = GetLinearExpression(Index, IndexScale, IndexOffset);
+      Index = GetLinearExpression(Index, IndexScale, IndexOffset, TD);
       
       Scale *= IndexScale.getZExtValue();
       BaseOffs += IndexOffset.getZExtValue()*Scale;