Index: llvm/trunk/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/trunk/lib/Analysis/ValueTracking.cpp +++ llvm/trunk/lib/Analysis/ValueTracking.cpp @@ -1860,19 +1860,42 @@ (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE)) continue; + SmallVector WorkList; + SmallPtrSet Visited; for (auto *CmpU : U->users()) { - if (const BranchInst *BI = dyn_cast(CmpU)) { - assert(BI->isConditional() && "uses a comparison!"); + assert(WorkList.empty() && "Should be!"); + if (Visited.insert(CmpU).second) + WorkList.push_back(CmpU); + + while (!WorkList.empty()) { + auto *Curr = WorkList.pop_back_val(); + + // If a user is an AND, add all its users to the work list. We only + // propagate "pred != null" condition through AND because it is only + // correct to assume that all conditions of AND are met in true branch. + // TODO: Support similar logic of OR and EQ predicate? + if (Pred == ICmpInst::ICMP_NE) + if (auto *BO = dyn_cast(Curr)) + if (BO->getOpcode() == Instruction::And) { + for (auto *BOU : BO->users()) + if (Visited.insert(BOU).second) + WorkList.push_back(BOU); + continue; + } + + if (const BranchInst *BI = dyn_cast(Curr)) { + assert(BI->isConditional() && "uses a comparison!"); - BasicBlock *NonNullSuccessor = - BI->getSuccessor(Pred == ICmpInst::ICMP_EQ ? 1 : 0); - BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor); - if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent())) + BasicBlock *NonNullSuccessor = + BI->getSuccessor(Pred == ICmpInst::ICMP_EQ ? 1 : 0); + BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor); + if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent())) + return true; + } else if (Pred == ICmpInst::ICMP_NE && + match(Curr, m_Intrinsic()) && + DT->dominates(cast(Curr), CtxI)) { return true; - } else if (Pred == ICmpInst::ICMP_NE && - match(CmpU, m_Intrinsic()) && - DT->dominates(cast(CmpU), CtxI)) { - return true; + } } } } Index: llvm/trunk/test/Transforms/LICM/hoist-deref-load.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/hoist-deref-load.ll +++ llvm/trunk/test/Transforms/LICM/hoist-deref-load.ll @@ -556,5 +556,171 @@ ret void } +; Check that branch by condition "null check AND something" allows to hoist the +; load. +define void @test14(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 { + +; CHECK-LABEL: @test14 +; CHECK: load i32, i32* %c, align 4 +; CHECK: for.body: + +entry: + %not_null = icmp ne i32* %c, null + %dummy_and = and i1 %not_null, %dummy_cond + br i1 %dummy_and, label %not.null, label %for.end + +not.null: + %cmp11 = icmp sgt i32 %n, 0 + br i1 %cmp11, label %for.body, label %for.end + +for.body: ; preds = %not.null, %for.inc + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %not.null ] + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4 + %cmp1 = icmp sgt i32 %0, 0 + br i1 %cmp1, label %if.then, label %for.inc + +if.then: ; preds = %for.body + %1 = load i32, i32* %c, align 4 + %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv + %2 = load i32, i32* %arrayidx3, align 4 + %mul = mul nsw i32 %2, %1 + store i32 %mul, i32* %arrayidx, align 4 + br label %for.inc + +for.inc: ; preds = %for.body, %if.then + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp eq i32 %lftr.wideiv, %n + br i1 %exitcond, label %for.end, label %for.body + +for.end: ; preds = %for.inc, %entry, %not.null + ret void +} + +; Check that guard by condition "null check AND something" allows to hoist the +; load. +define void @test15(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 { + +; CHECK-LABEL: @test15 +; CHECK: load i32, i32* %c, align 4 +; CHECK: for.body: + +entry: + %not_null = icmp ne i32* %c, null + %dummy_and = and i1 %not_null, %dummy_cond + call void(i1, ...) @llvm.experimental.guard(i1 %dummy_and) [ "deopt"() ] + %cmp11 = icmp sgt i32 %n, 0 + br i1 %cmp11, label %for.body, label %for.end + +for.body: ; preds = %entry, %for.inc + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4 + %cmp1 = icmp sgt i32 %0, 0 + br i1 %cmp1, label %if.then, label %for.inc + +if.then: ; preds = %for.body + %1 = load i32, i32* %c, align 4 + %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv + %2 = load i32, i32* %arrayidx3, align 4 + %mul = mul nsw i32 %2, %1 + store i32 %mul, i32* %arrayidx, align 4 + br label %for.inc + +for.inc: ; preds = %for.body, %if.then + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp eq i32 %lftr.wideiv, %n + br i1 %exitcond, label %for.end, label %for.body + +for.end: ; preds = %for.inc, %entry + ret void +} + +; Ensure that (c == null && other_cond) does not automatically mean that c is +; non-null in false branch. So the condition ((c == null && other_cond) == false) +; is not sufficient to conclude that c != null. +define void @test16(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 { + +; CHECK-LABEL: @test16 +; CHECK: for.body: +; CHECK: load i32, i32* %c, align 4 + +entry: + %not_null = icmp eq i32* %c, null + %dummy_and = and i1 %not_null, %dummy_cond + br i1 %dummy_and, label %for.end, label %not.null + +not.null: + %cmp11 = icmp sgt i32 %n, 0 + br i1 %cmp11, label %for.body, label %for.end + +for.body: ; preds = %not.null, %for.inc + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %not.null ] + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4 + %cmp1 = icmp sgt i32 %0, 0 + br i1 %cmp1, label %if.then, label %for.inc + +if.then: ; preds = %for.body + %1 = load i32, i32* %c, align 4 + %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv + %2 = load i32, i32* %arrayidx3, align 4 + %mul = mul nsw i32 %2, %1 + store i32 %mul, i32* %arrayidx, align 4 + br label %for.inc + +for.inc: ; preds = %for.body, %if.then + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp eq i32 %lftr.wideiv, %n + br i1 %exitcond, label %for.end, label %for.body + +for.end: ; preds = %for.inc, %entry, %not.null + ret void +} + +; Ensure that (c == null && other_cond) does not automatically mean that c is +; non-null in false branch. So the condition ((c == null && other_cond) == false) +; is not sufficient to conclude that c != null. +define void @test17(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 { + +; CHECK-LABEL: @test17 +; CHECK: for.body: +; CHECK: load i32, i32* %c, align 4 + +entry: + %not_null = icmp eq i32* %c, null + %dummy_and = and i1 %not_null, %dummy_cond + call void(i1, ...) @llvm.experimental.guard(i1 %dummy_and) [ "deopt"() ] + %cmp11 = icmp sgt i32 %n, 0 + br i1 %cmp11, label %for.end, label %for.body + +for.body: ; preds = %entry, %for.inc + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4 + %cmp1 = icmp sgt i32 %0, 0 + br i1 %cmp1, label %if.then, label %for.inc + +if.then: ; preds = %for.body + %1 = load i32, i32* %c, align 4 + %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv + %2 = load i32, i32* %arrayidx3, align 4 + %mul = mul nsw i32 %2, %1 + store i32 %mul, i32* %arrayidx, align 4 + br label %for.inc + +for.inc: ; preds = %for.body, %if.then + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp eq i32 %lftr.wideiv, %n + br i1 %exitcond, label %for.end, label %for.body + +for.end: ; preds = %for.inc, %entry + ret void +} + attributes #0 = { nounwind uwtable } !0 = !{i64 4}