Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -688,12 +688,13 @@ MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, Instruction::BinaryOps Opc, BranchProbability TW, - BranchProbability FW); + BranchProbability FW, bool InvertCond); void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, - BranchProbability TW, BranchProbability FW); + BranchProbability TW, BranchProbability FW, + bool InvertCond); bool ShouldEmitAsBranches(const std::vector &Cases); bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); void CopyToExportRegsIfNeeded(const Value *V); Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1581,7 +1581,8 @@ MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, BranchProbability TProb, - BranchProbability FProb) { + BranchProbability FProb, + bool InvertCond) { const BasicBlock *BB = CurBB->getBasicBlock(); // If the leaf of the tree is a comparison, merge the condition into @@ -1595,10 +1596,14 @@ isExportableFromCurrentBlock(BOp->getOperand(1), BB))) { ISD::CondCode Condition; if (const ICmpInst *IC = dyn_cast(Cond)) { - Condition = getICmpCondCode(IC->getPredicate()); + ICmpInst::Predicate Pred = + InvertCond ? IC->getInversePredicate() : IC->getPredicate(); + Condition = getICmpCondCode(Pred); } else { const FCmpInst *FC = cast(Cond); - Condition = getFCmpCondCode(FC->getPredicate()); + FCmpInst::Predicate Pred = + InvertCond ? FC->getInversePredicate() : FC->getPredicate(); + Condition = getFCmpCondCode(Pred); if (TM.Options.NoNaNsFPMath) Condition = getFCmpCodeWithoutNaN(Condition); } @@ -1611,7 +1616,8 @@ } // Create a CaseBlock record representing this branch. - CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(*DAG.getContext()), + ISD::CondCode Opc = InvertCond ? ISD::SETNE : ISD::SETEQ; + CaseBlock CB(Opc, Cond, ConstantInt::getTrue(*DAG.getContext()), nullptr, TBB, FBB, CurBB, TProb, FProb); SwitchCases.push_back(CB); } @@ -1624,16 +1630,42 @@ MachineBasicBlock *SwitchBB, Instruction::BinaryOps Opc, BranchProbability TProb, - BranchProbability FProb) { - // If this node is not part of the or/and tree, emit it as a branch. + BranchProbability FProb, + bool InvertCond) { + // Skip over not part of the tree and remember to invert op and operands at + // next level. + if (BinaryOperator::isNot(Cond) && Cond->hasOneUse()) { + Cond = cast(Cond)->getOperand(0); + FindMergedConditions(Cond, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb, + !InvertCond); + return; + } + const Instruction *BOp = dyn_cast(Cond); + // 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; + if (BOp) { + BOpc = BOp->getOpcode(); + if (InvertCond) { + if (BOpc == Instruction::And) + BOpc = Instruction::Or; + else if (BOpc == Instruction::Or) + BOpc = Instruction::And; + } + } + + // If this node is not part of the or/and tree, emit it as a branch. if (!BOp || !(isa(BOp) || isa(BOp)) || - (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() || + BOpc != Opc || !BOp->hasOneUse() || BOp->getParent() != CurBB->getBasicBlock() || !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, - TProb, FProb); + TProb, FProb, InvertCond); return; } @@ -1668,14 +1700,14 @@ auto NewFalseProb = TProb / 2 + FProb; // Emit the LHS condition. FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc, - NewTrueProb, NewFalseProb); + 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]); + Probs[0], Probs[1], InvertCond); } else { assert(Opc == Instruction::And && "Unknown merge op!"); // Codegen X & Y as: @@ -1701,14 +1733,14 @@ auto NewFalseProb = FProb / 2; // Emit the LHS condition. FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc, - NewTrueProb, NewFalseProb); + 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]); + Probs[0], Probs[1], InvertCond); } } @@ -1792,7 +1824,8 @@ FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB, Opcode, getEdgeProbability(BrMBB, Succ0MBB), - getEdgeProbability(BrMBB, Succ1MBB)); + getEdgeProbability(BrMBB, Succ1MBB), + /*InvertCond=*/false); // If the compares in later blocks need to use values not currently // exported from this block, export them now. This block should always // be the first entry. Index: test/CodeGen/AArch64/br-cond-not-merge.ll =================================================================== --- /dev/null +++ test/CodeGen/AArch64/br-cond-not-merge.ll @@ -0,0 +1,32 @@ +; RUN: llc -mtriple=aarch64 -verify-machineinstrs < %s | FileCheck %s + +declare void @foo() + +; Check that the inverted or doesn't inhibit the splitting of the +; complex conditional into three branch instructions. +; CHECK-LABEL: test_and_not +; CHECK: cbz w0, [[L:\.LBB[0-9_]+]] +; CHECK: cmp w1, #2 +; CHECK: b.lo [[L]] +; CHECK: cmp w2, #2 +; CHECK: b.hi [[L]] +define void @test_and_not(i32 %a, i32 %b, i32 %c) { +bb1: + %cmp1 = icmp ult i32 %a, 1 + %cmp2 = icmp ult i32 %b, 2 + %cmp3 = icmp ult i32 %c, 3 + %or = or i1 %cmp1, %cmp2 + %not.or = xor i1 %or, -1 + %and = and i1 %not.or, %cmp3 + br i1 %and, label %bb2, label %bb3 + +bb2: + ret void + +bb3: + call void @foo() + ret void +} + + + Index: test/CodeGen/X86/cmov.ll =================================================================== --- test/CodeGen/X86/cmov.ll +++ test/CodeGen/X86/cmov.ll @@ -70,7 +70,7 @@ @g_100 = external global i8 ; [#uses=2] @_2E_str = external constant [15 x i8], align 1 ; <[15 x i8]*> [#uses=1] -define i32 @test4() nounwind { +define i1 @test4() nounwind { entry: %0 = load i8, i8* @g_3, align 1 ; [#uses=2] %1 = sext i8 %0 to i32 ; [#uses=1] @@ -107,10 +107,11 @@ func_1.exit: ; preds = %bb.i.i, %func_4.exit.i %g_96.tmp.0.i = phi i8 [ %g_96.promoted.i, %bb.i.i ], [ %.mux.i, %func_4.exit.i ] ; [#uses=2] + %ret = phi i1 [ 0, %bb.i.i ], [ %.not.i, %func_4.exit.i ] store i8 %g_96.tmp.0.i, i8* @g_96 %6 = zext i8 %g_96.tmp.0.i to i32 ; [#uses=1] %7 = tail call i32 (i8*, ...) @printf(i8* noalias getelementptr ([15 x i8], [15 x i8]* @_2E_str, i64 0, i64 0), i32 %6) nounwind ; [#uses=0] - ret i32 0 + ret i1 %ret } declare i32 @printf(i8* nocapture, ...) nounwind Index: test/CodeGen/X86/dagcombine-and-setcc.ll =================================================================== --- test/CodeGen/X86/dagcombine-and-setcc.ll +++ test/CodeGen/X86/dagcombine-and-setcc.ll @@ -12,10 +12,11 @@ ;CHECK: cmpl -;CHECK: setg +;CHECK: setl ;CHECK: cmpl -;CHECK: setg -;CHECK: andb +;CHECK: setl +;CHECK: orb +;CHECK: je @.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1 ; Function Attrs: optsize ssp uwtable