Index: llvm/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/lib/Analysis/ValueTracking.cpp +++ llvm/lib/Analysis/ValueTracking.cpp @@ -2530,6 +2530,75 @@ return isKnownNonZero(Op, Depth + 1, Q); } +static bool isNonEqualPHIs(const PHINode *PN1, const PHINode *PN2, + unsigned Depth, const Query &Q) { + // Check two PHIs are in same block. + if (PN1->getParent() != PN2->getParent()) + return false; + + // Now the two PHIs have same incoming blocks. Let's compare incoming + // values with same incoming block. + SmallPtrSet VisitedBBs; + for (const BasicBlock *Pred : predecessors(PN1->getParent())) { + if (!VisitedBBs.insert(Pred).second) + continue; // Don't reprocess blocks that we have dealt with already. + const Value *IV1 = PN1->getIncomingValueForBlock(Pred); + const Value *IV2 = PN2->getIncomingValueForBlock(Pred); + if (isKnownNonEqual(IV1, IV2, Depth + 1, Q)) + continue; + + // If it is not known NonEqual, check backedge from PHI's incoming block + // to the PHI's block. + if (Q.DT != nullptr && Q.DT->dominates(PN1->getParent(), Pred)) { + // loop: + // %cmp.0 = phi i32 [ 3, %entry ], [ %inc, %loop ] + // %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %loop ] + // ... + // %inc = add i32 %cmp.0, 1 + // br label %loop + // + // On above example, %pos.0 uses previous iteration's %cmp.0 with backedge + // according to PHI's instruction's defintion. If the %inc is not same + // among iterations, we can say the two PHIs are not same. + + // Check a PHI uses other PHI as incoming value. If so, investigate IV. + const Value *IV = (PN1 == IV2) ? IV1 : ((PN2 == IV1) ? IV2 : nullptr); + const Value *PN = (PN1 == IV2) ? PN1 : ((PN2 == IV1) ? PN2 : nullptr); + if (auto *BinOp = dyn_cast(IV)) { + switch (BinOp->getOpcode()) { + default: + break; + case Instruction::Add: + // Check add does not have zero as operand. + if (all_of(BinOp->operands(), [=](const Value *Op) { + // Skip PHI operand. + if (Op == PN) + return true; + return isKnownNonZero(Op, Depth + 1, Q); + })) + continue; + break; + case Instruction::Mul: + // Check mul does not have zero or one as operand. + if (all_of(BinOp->operands(), [=](const Value *Op) { + // Skip PHI operand. + if (Op == PN) + return true; + Constant *One = ConstantInt::get(Op->getType(), 1); + return isKnownNonZero(Op, Depth + 1, Q) && + isKnownNonEqual(One, Op, Depth + 1, Q); + })) + continue; + break; + } + } + } + + return false; + } + + return true; +} /// Return true if it is known that V1 != V2. static bool isKnownNonEqual(const Value *V1, const Value *V2, unsigned Depth, @@ -2582,12 +2651,20 @@ case Instruction::SExt: case Instruction::ZExt: if (O1->getOperand(0)->getType() == O2->getOperand(0)->getType()) - return isKnownNonEqual(O1->getOperand(0), O2->getOperand(0), - Depth + 1, Q); + return isKnownNonEqual(O1->getOperand(0), O2->getOperand(0), Depth + 1, + Q); + break; + case Instruction::PHI: + const PHINode *PN1 = cast(V1); + const PHINode *PN2 = cast(V2); + // FIXME: This is missing a generalization to handle the case where one is + // a PHI and another one isn't. + if (isNonEqualPHIs(PN1, PN2, Depth + 1, Q)) + return true; break; }; } - + if (isAddOfNonZero(V1, V2, Depth, Q) || isAddOfNonZero(V2, V1, Depth, Q)) return true; Index: llvm/test/Analysis/ValueTracking/non-equal-two-phis.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/ValueTracking/non-equal-two-phis.ll @@ -0,0 +1,104 @@ +; RUN: opt < %s -basic-aa -instcombine -S 2>&1 | FileCheck %s + +target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128" + +%struct.data = type { i32, i32 } + +define void @redundant_load_with_two_phi_index_and_mul_IV(%struct.data* %data, i32 %max) { +entry: + br label %while.cond + +while.cond: ; preds = %while.body, %entry +; %pos.0 uses previous iteration's %cmp.0 with backedge according to PHI's +; instruction's defintion. If the %mul is not same among iterations, we can say +; the two PHIs are not same. + %cmp.0 = phi i32 [ 3, %entry ], [ %mul, %while.body ] + %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %while.body ] + %cmp1 = icmp slt i32 %cmp.0, %max + br i1 %cmp1, label %while.body, label %while.end + +while.body: ; preds = %while.cond + %sub = add nsw i32 %cmp.0, -1 + %idxprom = sext i32 %sub to i64 + %newVal = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom, i32 1 + +; CHECK-LABEL: redundant_load_with_two_phi_index_and_mul_IV +; CHECK: [[LOAD0:%[a-zA-Z0-9_]+]] = load i32, i32* %newVal, align 4, !tbaa !0 + %0 = load i32, i32* %newVal, align 4, !tbaa !0 + + %sub2 = add nsw i32 %pos.0, -1 + %idxprom3 = sext i32 %sub2 to i64 + %arrayidx4 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3 + %newVal5 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3, i32 1 + store i32 %0, i32* %newVal5, align 4, !tbaa !0 + +; Above store blocks to remove below load becasue MayAlias between %newVal and +; %newVal5. The address %newVal has no alias with %newVal5. If BasicAA +; recognizes it, below load should be removed with instcombine. A ad-hoc pattern +; with two PHIs is added to isKnownNonEqual and it should help BasicAA to return +; NoAlias in this case. + +; CHECK-NOT: [[LOAD1:%[a-zA-Z0-9_]+]] = load i32, i32* %newVal, align 4, !tbaa !0 + %1 = load i32, i32* %newVal, align 4, !tbaa !0 + + %oldVal = getelementptr inbounds %struct.data, %struct.data* %arrayidx4, i32 0, i32 0 + store i32 %1, i32* %oldVal, align 4, !tbaa !5 + %mul = mul nsw i32 %cmp.0, 2 + br label %while.cond + +while.end: ; preds = %while.cond + ret void +} + +define void @redundant_load_with_two_phi_index_and_add_IV(%struct.data* %data, i32 %max) { +entry: + br label %while.cond + +while.cond: ; preds = %while.body, %entry +; %pos.0 uses previous iteration's %cmp.0 with backedge according to PHI's +; instruction's defintion. If the %add is not same among iterations, we can say +; the two PHIs are not same. + %cmp.0 = phi i32 [ 3, %entry ], [ %add, %while.body ] + %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %while.body ] + %cmp1 = icmp slt i32 %cmp.0, %max + br i1 %cmp1, label %while.body, label %while.end + +while.body: ; preds = %while.cond + %sub = add nsw i32 %cmp.0, -1 + %idxprom = sext i32 %sub to i64 + %newVal = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom, i32 1 + +; CHECK-LABEL: redundant_load_with_two_phi_index_and_add_IV +; CHECK: [[LOAD0:%[a-zA-Z0-9_]+]] = load i32, i32* %newVal, align 4, !tbaa !0 + %0 = load i32, i32* %newVal, align 4, !tbaa !0 + + %sub2 = add nsw i32 %pos.0, -1 + %idxprom3 = sext i32 %sub2 to i64 + %arrayidx4 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3 + %newVal5 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3, i32 1 + store i32 %0, i32* %newVal5, align 4, !tbaa !0 + +; Above store blocks to remove below load becasue MayAlias between %newVal and +; %newVal5. The address %newVal has no alias with %newVal5. If BasicAA +; recognizes it, below load should be removed with instcombine. A ad-hoc pattern +; with two PHIs is added to isKnownNonEqual and it should help BasicAA to return +; NoAlias in this case. + +; CHECK-NOT: [[LOAD1:%[a-zA-Z0-9_]+]] = load i32, i32* %newVal, align 4, !tbaa !0 + %1 = load i32, i32* %newVal, align 4, !tbaa !0 + + %oldVal = getelementptr inbounds %struct.data, %struct.data* %arrayidx4, i32 0, i32 0 + store i32 %1, i32* %oldVal, align 4, !tbaa !5 + %add = add nsw i32 %cmp.0, 2 + br label %while.cond + +while.end: ; preds = %while.cond + ret void +} + +!0 = !{!1, !2, i64 4} +!1 = !{!"_ZTS4data", !2, i64 0, !2, i64 4} +!2 = !{!"int", !3, i64 0} +!3 = !{!"omnipotent char", !4, i64 0} +!4 = !{!"Simple C++ TBAA"} +!5 = !{!1, !2, i64 0}