diff --git a/llvm/lib/CodeGen/CodeGenPrepare.cpp b/llvm/lib/CodeGen/CodeGenPrepare.cpp --- a/llvm/lib/CodeGen/CodeGenPrepare.cpp +++ b/llvm/lib/CodeGen/CodeGenPrepare.cpp @@ -7838,9 +7838,10 @@ // %cond2 = icmp|fcmp|binary instruction ... // %cond.or = or|and i1 %cond1, cond2 // br i1 %cond.or label %dest1, label %dest2" - BinaryOperator *LogicOp; + Instruction *LogicOp; BasicBlock *TBB, *FBB; - if (!match(BB.getTerminator(), m_Br(m_OneUse(m_BinOp(LogicOp)), TBB, FBB))) + if (!match(BB.getTerminator(), + m_Br(m_OneUse(m_Instruction(LogicOp)), TBB, FBB))) continue; auto *Br1 = cast(BB.getTerminator()); @@ -7853,17 +7854,22 @@ unsigned Opc; Value *Cond1, *Cond2; - if (match(LogicOp, m_And(m_OneUse(m_Value(Cond1)), - m_OneUse(m_Value(Cond2))))) + if (match(LogicOp, + m_LogicalAnd(m_OneUse(m_Value(Cond1)), m_OneUse(m_Value(Cond2))))) Opc = Instruction::And; - else if (match(LogicOp, m_Or(m_OneUse(m_Value(Cond1)), - m_OneUse(m_Value(Cond2))))) + else if (match(LogicOp, m_LogicalOr(m_OneUse(m_Value(Cond1)), + m_OneUse(m_Value(Cond2))))) Opc = Instruction::Or; else continue; - if (!match(Cond1, m_CombineOr(m_Cmp(), m_BinOp())) || - !match(Cond2, m_CombineOr(m_Cmp(), m_BinOp())) ) + auto IsGoodCond = [](Value *Cond) { + return match( + Cond, + m_CombineOr(m_Cmp(), m_CombineOr(m_LogicalAnd(m_Value(), m_Value()), + m_LogicalOr(m_Value(), m_Value())))); + }; + if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2)) continue; LLVM_DEBUG(dbgs() << "Before branch condition splitting\n"; BB.dump()); diff --git a/llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp b/llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp --- a/llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp +++ b/llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp @@ -426,14 +426,19 @@ } const Instruction *BOp = dyn_cast(Cond); + const Value *BOpOp0, *BOpOp1; // Compute the effective opcode for Cond, taking into account whether it needs // to be inverted, e.g. // and (not (or A, B)), C // gets lowered as // and (and (not A, not B), C) - unsigned BOpc = 0; + Instruction::BinaryOps BOpc = (Instruction::BinaryOps)0; if (BOp) { - BOpc = BOp->getOpcode(); + BOpc = match(BOp, m_LogicalAnd(m_Value(BOpOp0), m_Value(BOpOp1))) + ? Instruction::And + : (match(BOp, m_LogicalOr(m_Value(BOpOp0), m_Value(BOpOp1))) + ? Instruction::Or + : (Instruction::BinaryOps)0); if (InvertCond) { if (BOpc == Instruction::And) BOpc = Instruction::Or; @@ -443,11 +448,11 @@ } // If this node is not part of the or/and tree, emit it as a branch. - if (!BOp || !(isa(BOp) || isa(BOp)) || - BOpc != static_cast(Opc) || !BOp->hasOneUse() || - BOp->getParent() != CurBB->getBasicBlock() || - !isValInBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || - !isValInBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { + // Note that all nodes in the tree should have same opcode. + bool BOpIsInOrAndTree = BOpc && BOpc == Opc && BOp->hasOneUse(); + if (!BOpIsInOrAndTree || BOp->getParent() != CurBB->getBasicBlock() || + !isValInBlock(BOpOp0, CurBB->getBasicBlock()) || + !isValInBlock(BOpOp1, CurBB->getBasicBlock())) { emitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, TProb, FProb, InvertCond); return; @@ -483,15 +488,15 @@ auto NewTrueProb = TProb / 2; auto NewFalseProb = TProb / 2 + FProb; // Emit the LHS condition. - findMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc, - NewTrueProb, NewFalseProb, InvertCond); + findMergedConditions(BOpOp0, TBB, TmpBB, CurBB, SwitchBB, Opc, NewTrueProb, + NewFalseProb, InvertCond); // Normalize A/2 and B to get A/(1+B) and 2B/(1+B). SmallVector Probs{TProb / 2, FProb}; BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); // Emit the RHS condition into TmpBB. - findMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - Probs[0], Probs[1], InvertCond); + findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0], + Probs[1], InvertCond); } else { assert(Opc == Instruction::And && "Unknown merge op!"); // Codegen X & Y as: @@ -516,15 +521,15 @@ auto NewTrueProb = TProb + FProb / 2; auto NewFalseProb = FProb / 2; // Emit the LHS condition. - findMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc, - NewTrueProb, NewFalseProb, InvertCond); + findMergedConditions(BOpOp0, TmpBB, FBB, CurBB, SwitchBB, Opc, NewTrueProb, + NewFalseProb, InvertCond); // Normalize A and B/2 to get 2A/(1+A) and B/(1+A). SmallVector Probs{TProb, FProb / 2}; BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); // Emit the RHS condition into TmpBB. - findMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - Probs[0], Probs[1], InvertCond); + findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0], + Probs[1], InvertCond); } } @@ -601,15 +606,20 @@ // cmp D, E // jle foo using namespace PatternMatch; - if (const BinaryOperator *BOp = dyn_cast(CondVal)) { - Instruction::BinaryOps Opcode = BOp->getOpcode(); - Value *Vec, *BOp0 = BOp->getOperand(0), *BOp1 = BOp->getOperand(1); - if (!TLI.isJumpExpensive() && BOp->hasOneUse() && - !BrInst.hasMetadata(LLVMContext::MD_unpredictable) && - (Opcode == Instruction::And || Opcode == Instruction::Or) && - !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) && - match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value())))) { - findMergedConditions(BOp, Succ0MBB, Succ1MBB, &CurMBB, &CurMBB, Opcode, + const Instruction *CondI = dyn_cast(CondVal); + if (!TLI.isJumpExpensive() && CondI && CondI->hasOneUse() && + !BrInst.hasMetadata(LLVMContext::MD_unpredictable)) { + Instruction::BinaryOps Opcode = (Instruction::BinaryOps)0; + Value *Vec; + const Value *BOp0, *BOp1; + if (match(CondI, m_LogicalAnd(m_Value(BOp0), m_Value(BOp1)))) + Opcode = Instruction::And; + else if (match(CondI, m_LogicalOr(m_Value(BOp0), m_Value(BOp1)))) + Opcode = Instruction::Or; + + if (Opcode && !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) && + match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value())))) { + findMergedConditions(CondI, Succ0MBB, Succ1MBB, &CurMBB, &CurMBB, Opcode, getEdgeProbability(&CurMBB, Succ0MBB), getEdgeProbability(&CurMBB, Succ1MBB), /*InvertCond=*/false); diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2085,14 +2085,19 @@ } const Instruction *BOp = dyn_cast(Cond); + const Value *BOpOp0, *BOpOp1; // Compute the effective opcode for Cond, taking into account whether it needs // to be inverted, e.g. // and (not (or A, B)), C // gets lowered as // and (and (not A, not B), C) - unsigned BOpc = 0; + Instruction::BinaryOps BOpc = (Instruction::BinaryOps)0; if (BOp) { - BOpc = BOp->getOpcode(); + BOpc = match(BOp, m_LogicalAnd(m_Value(BOpOp0), m_Value(BOpOp1))) + ? Instruction::And + : (match(BOp, m_LogicalOr(m_Value(BOpOp0), m_Value(BOpOp1))) + ? Instruction::Or + : (Instruction::BinaryOps)0); if (InvertCond) { if (BOpc == Instruction::And) BOpc = Instruction::Or; @@ -2102,11 +2107,11 @@ } // If this node is not part of the or/and tree, emit it as a branch. - if (!BOp || !(isa(BOp) || isa(BOp)) || - BOpc != unsigned(Opc) || !BOp->hasOneUse() || - BOp->getParent() != CurBB->getBasicBlock() || - !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || - !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { + // Note that all nodes in the tree should have same opcode. + bool BOpIsInOrAndTree = BOpc && BOpc == Opc && BOp->hasOneUse(); + if (!BOpIsInOrAndTree || BOp->getParent() != CurBB->getBasicBlock() || + !InBlock(BOpOp0, CurBB->getBasicBlock()) || + !InBlock(BOpOp1, CurBB->getBasicBlock())) { EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, TProb, FProb, InvertCond); return; @@ -2142,15 +2147,15 @@ auto NewTrueProb = TProb / 2; auto NewFalseProb = TProb / 2 + FProb; // Emit the LHS condition. - FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc, - NewTrueProb, NewFalseProb, InvertCond); + FindMergedConditions(BOpOp0, TBB, TmpBB, CurBB, SwitchBB, Opc, NewTrueProb, + NewFalseProb, InvertCond); // Normalize A/2 and B to get A/(1+B) and 2B/(1+B). SmallVector Probs{TProb / 2, FProb}; BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); // Emit the RHS condition into TmpBB. - FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - Probs[0], Probs[1], InvertCond); + FindMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0], + Probs[1], InvertCond); } else { assert(Opc == Instruction::And && "Unknown merge op!"); // Codegen X & Y as: @@ -2175,15 +2180,15 @@ auto NewTrueProb = TProb + FProb / 2; auto NewFalseProb = FProb / 2; // Emit the LHS condition. - FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc, - NewTrueProb, NewFalseProb, InvertCond); + FindMergedConditions(BOpOp0, TmpBB, FBB, CurBB, SwitchBB, Opc, NewTrueProb, + NewFalseProb, InvertCond); // Normalize A and B/2 to get 2A/(1+A) and B/(1+A). SmallVector Probs{TProb, FProb / 2}; BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); // Emit the RHS condition into TmpBB. - FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc, - Probs[0], Probs[1], InvertCond); + FindMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0], + Probs[1], InvertCond); } } @@ -2260,16 +2265,20 @@ // je foo // cmp D, E // jle foo - if (const BinaryOperator *BOp = dyn_cast(CondVal)) { - Instruction::BinaryOps Opcode = BOp->getOpcode(); - Value *Vec, *BOp0 = BOp->getOperand(0), *BOp1 = BOp->getOperand(1); - if (!DAG.getTargetLoweringInfo().isJumpExpensive() && BOp->hasOneUse() && - !I.hasMetadata(LLVMContext::MD_unpredictable) && - (Opcode == Instruction::And || Opcode == Instruction::Or) && - !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) && - match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value())))) { - FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB, - Opcode, + const Instruction *BOp = dyn_cast(CondVal); + if (!DAG.getTargetLoweringInfo().isJumpExpensive() && BOp && + BOp->hasOneUse() && !I.hasMetadata(LLVMContext::MD_unpredictable)) { + Value *Vec; + const Value *BOp0, *BOp1; + Instruction::BinaryOps Opcode = (Instruction::BinaryOps)0; + if (match(BOp, m_LogicalAnd(m_Value(BOp0), m_Value(BOp1)))) + Opcode = Instruction::And; + else if (match(BOp, m_LogicalOr(m_Value(BOp0), m_Value(BOp1)))) + Opcode = Instruction::Or; + + if (Opcode && !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) && + match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value())))) { + FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB, Opcode, getEdgeProbability(BrMBB, Succ0MBB), getEdgeProbability(BrMBB, Succ1MBB), /*InvertCond=*/false); diff --git a/llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-condbr-lower-tree.ll b/llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-condbr-lower-tree.ll --- a/llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-condbr-lower-tree.ll +++ b/llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-condbr-lower-tree.ll @@ -41,6 +41,46 @@ ret void } +define void @or_cond_select(i32 %X, i32 %Y, i32 %Z) nounwind { + ; CHECK-LABEL: name: or_cond_select + ; CHECK: bb.1.entry: + ; CHECK: successors: %bb.2(0x20000000), %bb.4(0x60000000) + ; CHECK: liveins: $w0, $w1, $w2 + ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0 + ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY $w1 + ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY $w2 + ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 0 + ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 5 + ; CHECK: [[C2:%[0-9]+]]:_(s1) = G_CONSTANT i1 true + ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(slt), [[COPY1]](s32), [[C1]] + ; CHECK: [[SELECT:%[0-9]+]]:_(s1) = G_SELECT [[ICMP1]](s1), [[C2]], [[ICMP]] + ; CHECK: [[ICMP2:%[0-9]+]]:_(s1) = G_ICMP intpred(slt), [[COPY1]](s32), [[C1]] + ; CHECK: G_BRCOND [[ICMP2]](s1), %bb.2 + ; CHECK: G_BR %bb.4 + ; CHECK: bb.4.entry: + ; CHECK: successors: %bb.2(0x2aaaaaab), %bb.3(0x55555555) + ; CHECK: [[ICMP3:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: G_BRCOND [[ICMP3]](s1), %bb.2 + ; CHECK: G_BR %bb.3 + ; CHECK: bb.2.cond_true: + ; CHECK: TCRETURNdi @bar, 0, csr_aarch64_aapcs, implicit $sp + ; CHECK: bb.3.UnifiedReturnBlock: + ; CHECK: RET_ReallyLR +entry: + %tmp1 = icmp eq i32 %X, 0 + %tmp3 = icmp slt i32 %Y, 5 + %tmp4 = select i1 %tmp3, i1 true, i1 %tmp1 + br i1 %tmp4, label %cond_true, label %UnifiedReturnBlock + +cond_true: + %tmp5 = tail call i32 (...) @bar( ) + ret void + +UnifiedReturnBlock: + ret void +} + define void @and_cond(i32 %X, i32 %Y, i32 %Z) nounwind { ; CHECK-LABEL: name: and_cond ; CHECK: bb.1.entry: @@ -80,6 +120,46 @@ ret void } +define void @and_cond_select(i32 %X, i32 %Y, i32 %Z) nounwind { + ; CHECK-LABEL: name: and_cond_select + ; CHECK: bb.1.entry: + ; CHECK: successors: %bb.4(0x60000000), %bb.3(0x20000000) + ; CHECK: liveins: $w0, $w1, $w2 + ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0 + ; CHECK: [[COPY1:%[0-9]+]]:_(s32) = COPY $w1 + ; CHECK: [[COPY2:%[0-9]+]]:_(s32) = COPY $w2 + ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 0 + ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 5 + ; CHECK: [[C2:%[0-9]+]]:_(s1) = G_CONSTANT i1 false + ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(slt), [[COPY1]](s32), [[C1]] + ; CHECK: [[SELECT:%[0-9]+]]:_(s1) = G_SELECT [[ICMP1]](s1), [[ICMP]], [[C2]] + ; CHECK: [[ICMP2:%[0-9]+]]:_(s1) = G_ICMP intpred(slt), [[COPY1]](s32), [[C1]] + ; CHECK: G_BRCOND [[ICMP2]](s1), %bb.4 + ; CHECK: G_BR %bb.3 + ; CHECK: bb.4.entry: + ; CHECK: successors: %bb.2(0x55555555), %bb.3(0x2aaaaaab) + ; CHECK: [[ICMP3:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: G_BRCOND [[ICMP3]](s1), %bb.2 + ; CHECK: G_BR %bb.3 + ; CHECK: bb.2.cond_true: + ; CHECK: TCRETURNdi @bar, 0, csr_aarch64_aapcs, implicit $sp + ; CHECK: bb.3.UnifiedReturnBlock: + ; CHECK: RET_ReallyLR +entry: + %tmp1 = icmp eq i32 %X, 0 + %tmp3 = icmp slt i32 %Y, 5 + %tmp4 = select i1 %tmp3, i1 %tmp1, i1 false + br i1 %tmp4, label %cond_true, label %UnifiedReturnBlock + +cond_true: + %tmp5 = tail call i32 (...) @bar( ) + ret void + +UnifiedReturnBlock: + ret void +} + ; Don't emit two branches for same operands. define void @or_cond_same_values_cmp(i32 %X, i32 %Y, i32 %Z) nounwind { ; CHECK-LABEL: name: or_cond_same_values_cmp diff --git a/llvm/test/CodeGen/AArch64/arm64_32.ll b/llvm/test/CodeGen/AArch64/arm64_32.ll --- a/llvm/test/CodeGen/AArch64/arm64_32.ll +++ b/llvm/test/CodeGen/AArch64/arm64_32.ll @@ -701,6 +701,23 @@ ret void } +define void @test_multiple_icmp_ptr_select(i8* %l, i8* %r) { +; CHECK-LABEL: test_multiple_icmp_ptr_select: +; CHECK: tbnz w0, #31, [[FALSEBB:LBB[0-9]+_[0-9]+]] +; CHECK: tbnz w1, #31, [[FALSEBB]] + %tst1 = icmp sgt i8* %l, inttoptr (i32 -1 to i8*) + %tst2 = icmp sgt i8* %r, inttoptr (i32 -1 to i8*) + %tst = select i1 %tst1, i1 %tst2, i1 false + br i1 %tst, label %true, label %false + +true: + call void(...) @bar() + ret void + +false: + ret void +} + define { [18 x i8] }* @test_gep_nonpow2({ [18 x i8] }* %a0, i32 %a1) { ; CHECK-LABEL: test_gep_nonpow2: ; CHECK-OPT: mov w[[SIZE:[0-9]+]], #18 diff --git a/llvm/test/CodeGen/AArch64/fast-isel-branch-cond-split.ll b/llvm/test/CodeGen/AArch64/fast-isel-branch-cond-split.ll --- a/llvm/test/CodeGen/AArch64/fast-isel-branch-cond-split.ll +++ b/llvm/test/CodeGen/AArch64/fast-isel-branch-cond-split.ll @@ -18,6 +18,24 @@ ret i64 %2 } +; CHECK-LABEL: test_or_select +; CHECK: cbnz w0, {{LBB[0-9]+_2}} +; CHECK: cbz w1, {{LBB[0-9]+_1}} +define i64 @test_or_select(i32 %a, i32 %b) { +bb1: + %0 = icmp eq i32 %a, 0 + %1 = icmp eq i32 %b, 0 + %or.cond = select i1 %0, i1 true, i1 %1 + br i1 %or.cond, label %bb3, label %bb4, !prof !0 + +bb3: + ret i64 0 + +bb4: + %2 = call i64 @bar() + ret i64 %2 +} + ; CHECK-LABEL: test_and ; CHECK: cbnz w0, {{LBB[0-9]+_2}} ; CHECK: cbz w1, {{LBB[0-9]+_1}} @@ -36,6 +54,24 @@ ret i64 %2 } +; CHECK-LABEL: test_and_select +; CHECK: cbnz w0, {{LBB[0-9]+_2}} +; CHECK: cbz w1, {{LBB[0-9]+_1}} +define i64 @test_and_select(i32 %a, i32 %b) { +bb1: + %0 = icmp ne i32 %a, 0 + %1 = icmp ne i32 %b, 0 + %or.cond = select i1 %0, i1 %1, i1 false + br i1 %or.cond, label %bb4, label %bb3, !prof !1 + +bb3: + ret i64 0 + +bb4: + %2 = call i64 @bar() + ret i64 %2 +} + ; If the branch is unpredictable, don't add another branch. ; CHECK-LABEL: test_or_unpredictable