diff --git a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h --- a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h +++ b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h @@ -113,6 +113,9 @@ APInt Scale; + /// True if (V * Scale) % X produces the same result for any X. + bool PreservesModulo; + // Context instruction to use when querying information about this index. const Instruction *CxtI; @@ -180,11 +183,13 @@ /// Tracks instructions visited by pointsToConstantMemory. SmallPtrSet Visited; - static const Value * - GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset, - unsigned &ZExtBits, unsigned &SExtBits, - const DataLayout &DL, unsigned Depth, AssumptionCache *AC, - DominatorTree *DT, bool &NSW, bool &NUW); + static const Value *GetLinearExpression(const Value *V, APInt &Scale, + APInt &Offset, unsigned &ZExtBits, + unsigned &SExtBits, + const DataLayout &DL, unsigned Depth, + AssumptionCache *AC, + DominatorTree *DT, bool &NSW, + bool &NUW, bool &PreservesModulo); static DecomposedGEP DecomposeGEPExpression(const Value *V, const DataLayout &DL, diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -235,7 +235,8 @@ /*static*/ const Value *BasicAAResult::GetLinearExpression( const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits, unsigned &SExtBits, const DataLayout &DL, unsigned Depth, - AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) { + AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW, + bool &PreservesModulo) { assert(V->getType()->isIntegerTy() && "Not an integer value"); // Limit our recursion depth. @@ -263,6 +264,7 @@ // extensions below (see the isa / isa cases). APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth()); + bool LocalPreservesModulo = false; switch (BOp->getOpcode()) { default: // We don't understand this instruction, so we can't decompose it any @@ -282,23 +284,28 @@ LLVM_FALLTHROUGH; case Instruction::Add: V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); + SExtBits, DL, Depth + 1, AC, DT, NSW, NUW, + PreservesModulo); Offset += RHS; break; case Instruction::Sub: V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); + SExtBits, DL, Depth + 1, AC, DT, NSW, NUW, + PreservesModulo); Offset -= RHS; break; case Instruction::Mul: V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); + SExtBits, DL, Depth + 1, AC, DT, NSW, NUW, + PreservesModulo); Offset *= RHS; Scale *= RHS; + LocalPreservesModulo = RHS.isPowerOf2(); break; case Instruction::Shl: V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); + SExtBits, DL, Depth + 1, AC, DT, NSW, NUW, + PreservesModulo); // We're trying to linearize an expression of the kind: // shl i8 -128, 36 @@ -317,13 +324,17 @@ // the semantics of nsw and nuw for left shifts don't match those of // multiplications, so we won't propagate them. NSW = NUW = false; + // shl preserves modulo. return V; } if (isa(BOp)) { NUW &= BOp->hasNoUnsignedWrap(); NSW &= BOp->hasNoSignedWrap(); + LocalPreservesModulo |= + BOp->hasNoUnsignedWrap() && BOp->hasNoSignedWrap(); } + PreservesModulo = LocalPreservesModulo; return V; } } @@ -338,7 +349,7 @@ unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits; const Value *Result = GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL, - Depth + 1, AC, DT, NSW, NUW); + Depth + 1, AC, DT, NSW, NUW, PreservesModulo); // zext(zext(%x)) == zext(%x), and similarly for sext; we'll handle this // by just incrementing the number of bits we've extended by. @@ -542,10 +553,11 @@ // Use GetLinearExpression to decompose the index into a C1*V+C2 form. APInt IndexScale(Width, 0), IndexOffset(Width, 0); - bool NSW = true, NUW = true; + bool NSW = true, NUW = true, PreservesModulo = true; const Value *OrigIndex = Index; Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits, - SExtBits, DL, 0, AC, DT, NSW, NUW); + SExtBits, DL, 0, AC, DT, NSW, NUW, + PreservesModulo); // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. @@ -592,7 +604,8 @@ Scale = adjustToPointerSize(Scale, PointerSize); if (!!Scale) { - VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale, CxtI}; + VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, + Scale, PreservesModulo, CxtI}; Decomposed.VarIndices.push_back(Entry); } } @@ -1141,7 +1154,9 @@ bool AllNonPositive = DecompGEP1.Offset.isNonPositive(); for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { const APInt &Scale = DecompGEP1.VarIndices[i].Scale; - if (i == 0) + if (!DecompGEP1.VarIndices[i].PreservesModulo) + GCD = APInt(Scale.getBitWidth(), 1); + else if (i == 0) GCD = Scale.abs(); else GCD = APIntOps::GreatestCommonDivisor(GCD, Scale.abs()); @@ -1707,9 +1722,11 @@ // 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) + if (Dest[j].Scale != Scale) { Dest[j].Scale -= Scale; - else + // Conservatively assume modulo is not preserved. + Dest[j].PreservesModulo = false; + } else Dest.erase(Dest.begin() + j); Scale = 0; break; @@ -1717,7 +1734,8 @@ // If we didn't consume this entry, add it to the end of the Dest list. if (!!Scale) { - VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale, Src[i].CxtI}; + VariableGEPIndex Entry = { + V, ZExtBits, SExtBits, -Scale, Src[i].PreservesModulo, Src[i].CxtI}; Dest.push_back(Entry); } } @@ -1748,14 +1766,17 @@ APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0), V1Offset(Width, 0); - bool NSW = true, NUW = true; + bool NSW = true, NUW = true, PreservesModulo = true; unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0; - const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits, - V0SExtBits, DL, 0, AC, DT, NSW, NUW); + const Value *V0 = + GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits, V0SExtBits, DL, + 0, AC, DT, NSW, NUW, PreservesModulo); NSW = true; NUW = true; - const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits, - V1SExtBits, DL, 0, AC, DT, NSW, NUW); + PreservesModulo = true; + const Value *V1 = + GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits, V1SExtBits, DL, + 0, AC, DT, NSW, NUW, PreservesModulo); if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits || V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1)) diff --git a/llvm/test/Analysis/BasicAA/gep-alias.ll b/llvm/test/Analysis/BasicAA/gep-alias.ll --- a/llvm/test/Analysis/BasicAA/gep-alias.ll +++ b/llvm/test/Analysis/BasicAA/gep-alias.ll @@ -161,7 +161,7 @@ define i8 @test9([4 x i8] *%P, i32 %i, i32 %j) { %i2 = shl i32 %i, 2 - %i3 = add i32 %i2, 1 + %i3 = add nuw nsw i32 %i2, 1 ; P2 = P + 1 + 4*i %P2 = getelementptr [4 x i8], [4 x i8] *%P, i32 0, i32 %i3 diff --git a/llvm/test/Analysis/BasicAA/gep-modulo.ll b/llvm/test/Analysis/BasicAA/gep-modulo.ll --- a/llvm/test/Analysis/BasicAA/gep-modulo.ll +++ b/llvm/test/Analysis/BasicAA/gep-modulo.ll @@ -7,7 +7,7 @@ ; CHECK-LABEL: Function: may_overflow_mul_add_i8: 3 pointers, 0 call sites ; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx ; CHECK-NEXT: PartialAlias: [16 x i8]* %ptr, i8* %gep.6 -; CHECK-NEXT: NoAlias: i8* %gep.6, i8* %gep.idx +; CHECK-NEXT: MayAlias: i8* %gep.6, i8* %gep.idx ; %mul = mul i8 %idx, 5 %add = add i8 %mul, 2 @@ -38,7 +38,7 @@ ; CHECK-LABEL: Function: may_overflow_mul_sub_i8: 3 pointers, 0 call sites ; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx ; CHECK-NEXT: PartialAlias: [16 x i8]* %ptr, i8* %gep.3 -; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx +; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx ; %mul = mul i8 %idx, 5 %sub = sub i8 %mul, 1 @@ -70,7 +70,7 @@ ; CHECK-LABEL: Function: may_overflow_mul_sub_i64: 3 pointers, 0 call sites ; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx ; CHECK-NEXT: PartialAlias: [16 x i8]* %ptr, i8* %gep.3 -; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx +; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx ; %mul = mul i64 %idx, 5 %sub = sub i64 %mul, 1