diff --git a/llvm/include/llvm/CodeGen/SelectionDAG.h b/llvm/include/llvm/CodeGen/SelectionDAG.h --- a/llvm/include/llvm/CodeGen/SelectionDAG.h +++ b/llvm/include/llvm/CodeGen/SelectionDAG.h @@ -419,6 +419,7 @@ void clear(); MachineFunction &getMachineFunction() const { return *MF; } + MachineBasicBlock *getMachineBasicBlock() const { return FLI->MBB; } const Pass *getPass() const { return SDAGISelPass; } const DataLayout &getDataLayout() const { return MF->getDataLayout(); } diff --git a/llvm/include/llvm/Support/KnownBits.h b/llvm/include/llvm/Support/KnownBits.h --- a/llvm/include/llvm/Support/KnownBits.h +++ b/llvm/include/llvm/Support/KnownBits.h @@ -122,6 +122,28 @@ return ~Zero; } + /// Return the minimal signed value possible given these KnownBits. + APInt getSignedMinValue() const { + // Assume that all bits that aren't known-ones are zeros. + // If the sign bit is unknown, assume it is set + APInt Val = One; + if (!isNonNegative()) + Val.setSignBit(); + + return Val; + } + + /// Return the maximal signed value possible given these KnownBits. + APInt getSignedMaxValue() const { + // Assume that all bits that aren't known-zeros are ones. + // If the sign bit is unknown, assume it is cleared + APInt Val = ~Zero; + if (!isNegative()) + Val.clearSignBit(); + + return Val; + } + /// Return known bits for a truncation of the value we're tracking. KnownBits trunc(unsigned BitWidth) const { return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp --- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -14126,6 +14126,27 @@ // Instcombine/SimplifyCFG should have handled the available opportunities. // If we did this folding here, it would be necessary to update the // MachineBasicBlock CFG, which is awkward. + if (auto *N1C = dyn_cast(N1.getNode())) { + auto *TgtMBB = cast(N2)->getBasicBlock(); + auto *CurMBB = DAG.getMachineBasicBlock(); + if (!N1C->isNullValue()) { + // unconditionally take the branch, remove all other successors of CurBB + auto SuccMBB = CurMBB->succ_begin(); + while (SuccMBB != CurMBB->succ_end()) { + if (*SuccMBB != TgtMBB) { + SuccMBB = CurMBB->removeSuccessor(SuccMBB); + } else { + ++SuccMBB; + } + } + return DAG.getNode(ISD::BR, SDLoc(N), MVT::Other, Chain, + N2.getOperand(0)); + } else { + // do not take the branch, remove it from the CFG + CurMBB->removeSuccessor(TgtMBB); + return Chain; + } + } // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal // on the target. diff --git a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp --- a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp @@ -3379,6 +3379,91 @@ isCondCodeLegal(SwappedCC, N0.getSimpleValueType()))) return DAG.getSetCC(dl, VT, N1, N0, SwappedCC); + // If we can guarantee that the known bits of the operands restricts the range + // of values that each can take such that the comparison is guaranteed to be + // true or false, replace the setcc with the respective constant + if (OpVT.isInteger()) { + KnownBits LHSKnown = DAG.computeKnownBits(N0); + KnownBits RHSKnown = DAG.computeKnownBits(N1); + + switch (Cond) { + default: + llvm_unreachable("Unknown integer setcc!"); + case ISD::SETEQ: + if (LHSKnown.Zero.intersects(RHSKnown.One) || + LHSKnown.One.intersects(RHSKnown.Zero)) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETNE: + if (LHSKnown.Zero.intersects(RHSKnown.One) || + LHSKnown.One.intersects(RHSKnown.Zero)) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } + break; + case ISD::SETGT: + if (LHSKnown.getSignedMinValue().sgt(RHSKnown.getSignedMaxValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getSignedMaxValue().sle( + RHSKnown.getSignedMinValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETGE: + if (LHSKnown.getSignedMinValue().sge(RHSKnown.getSignedMaxValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getSignedMaxValue().slt( + RHSKnown.getSignedMinValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETLT: + if (LHSKnown.getSignedMaxValue().slt(RHSKnown.getSignedMinValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getSignedMinValue().sge( + RHSKnown.getSignedMaxValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETLE: + if (LHSKnown.getSignedMaxValue().sle(RHSKnown.getSignedMinValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getSignedMinValue().sgt( + RHSKnown.getSignedMaxValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETUGT: + if (LHSKnown.getMinValue().ugt(RHSKnown.getMaxValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getMaxValue().ule(RHSKnown.getMinValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETUGE: + if (LHSKnown.getMinValue().uge(RHSKnown.getMaxValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getMaxValue().ult(RHSKnown.getMinValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETULT: + if (LHSKnown.getMaxValue().ult(RHSKnown.getMinValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getMinValue().uge(RHSKnown.getMaxValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + case ISD::SETULE: + if (LHSKnown.getMaxValue().ule(RHSKnown.getMinValue())) { + return DAG.getBoolConstant(true, dl, VT, OpVT); + } else if (LHSKnown.getMinValue().ugt(RHSKnown.getMaxValue())) { + return DAG.getBoolConstant(false, dl, VT, OpVT); + } + break; + } + } + // If we have a subtract with the same 2 non-constant operands as this setcc // -- but in reverse order -- then try to commute the operands of this setcc // to match. A matching pair of setcc (cmp) and sub may be combined into 1 diff --git a/llvm/test/CodeGen/X86/combine-known-bits-vector.ll b/llvm/test/CodeGen/X86/combine-known-bits-vector.ll new file mode 100644 --- /dev/null +++ b/llvm/test/CodeGen/X86/combine-known-bits-vector.ll @@ -0,0 +1,55 @@ +; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s + +%vi32 = type <4 x i32> +%vi1 = type <4 x i1> + +; CHECK-LABEL: @test_eq +; CHECK: ## %bb.0 +; CHECK-NEXT: xorps %xmm0, %xmm0 +; CHECK-NEXT: retq +define %vi1 @test_eq(%vi32 %a0) { + %1 = and %vi32 %a0, + %2 = icmp eq %vi32 %1, + ret %vi1 %2 +} + +; CHECK-LABEL: @test_ne +; CHECK: ## %bb.0 +; CHECK-NEXT: pcmpeqd %xmm0, %xmm0 +; CHECK-NEXT: retq +define %vi1 @test_ne(%vi32 %a0) { + %1 = and %vi32 %a0, + %2 = icmp ne %vi32 %1, + ret %vi1 %2 +} + +; CHECK-LABEL: @test_slt +; CHECK: ## %bb.0 +; CHECK-NEXT: por LCPI2_0(%rip), %xmm0 +;; first element can be combined, rest cannot +define %vi1 @test_slt(%vi32 %a0) { + %1 = or %vi32 %a0, + %2 = icmp slt %vi32 , %1 + ret %vi1 %2 +} + +; CHECK-LABEL: @test_sgt +; CHECK: ## %bb.0 +; CHECK-NEXT: por LCPI3_0(%rip), %xmm0 +;; first element can be combined, rest cannot +define %vi1 @test_sgt(%vi32 %a0) { + %1 = or %vi32 %a0, + %2 = icmp sgt %vi32 %1, + ret %vi1 %2 +} + + +; CHECK-LABEL: @test_sgt2 +; CHECK: ## %bb.0 +; CHECK-NEXT: pcmpeqd %xmm0, %xmm0 +; CHECK-NEXT: retq +define %vi1 @test_sgt2(%vi32 %a0) { + %1 = or %vi32 %a0, + %2 = icmp sgt %vi32 %1, + ret %vi1 %2 +} \ No newline at end of file diff --git a/llvm/test/CodeGen/X86/combine-known-bits.ll b/llvm/test/CodeGen/X86/combine-known-bits.ll new file mode 100644 --- /dev/null +++ b/llvm/test/CodeGen/X86/combine-known-bits.ll @@ -0,0 +1,267 @@ +; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s + +;; EQ +; CHECK-LABEL: @test_eq +; CHECK: ## %bb.0: +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_eq(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp eq i32 %1, -2 + ret i1 %2 +} + +;; NE +; CHECK-LABEL: @test_ne +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_ne(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp ne i32 %1, -2 + ret i1 %2 +} + +;; UGE +; CHECK-LABEL: @test_uge1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_uge1(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp uge i32 %1, 242 + ret i1 %2 +} + +; CHECK-LABEL: @test_uge2 +; CHECK: ## %bb.0 +; CHECK-NEXT: andl $127, %edi +define i1 @test_uge2(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp uge i32 %1, 127 + ret i1 %2 +} + +; CHECK-LABEL: @test_uge3 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_uge3(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = icmp uge i32 %1, 127 + ret i1 %2 +} + +;; ULE +; CHECK-LABEL: @test_ule1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_ule1(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = icmp ule i32 %1, 17 + ret i1 %2 +} + +; CHECK-LABEL: @test_ule2 +; CHECK: ## %bb.0 +; CHECK-NEXT: andl $242, %edi +define i1 @test_ule2(i32 %a0) { + %1 = and i32 %a0, 242 + %2 = icmp ule i32 %1, 127 + ret i1 %2 +} + +; CHECK-LABEL: @test_ule3 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_ule3(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp ule i32 %1, 127 + ret i1 %2 +} + +;; SGE +; CHECK-LABEL: @test_sge1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_sge1(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp sge i32 %1, 128 + ret i1 %2 +} + +; CHECK-LABEL: @test_sge2 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_sge2(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = and i32 %1, 2147483647 ; i32_MAX + %3 = icmp sge i32 %2, 127 + ret i1 %3 +} + +; CHECK-LABEL: @test_sge3 +; CHECK: ## %bb.0 +; CHECK-NEXT: orl $127, %edi +define i1 @test_sge3(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = icmp sge i32 %1, 0 + ret i1 %2 +} + +;; SLE +; CHECK-LABEL: @test_sle1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_sle1(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp sle i32 128, %1 + ret i1 %2 +} + +; CHECK-LABEL: @test_sle2 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_sle2(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = and i32 %1, 2147483647 ; i32_MAX + %3 = icmp sle i32 126, %2 + ret i1 %3 +} + +; CHECK-LABEL: @test_sle3 +; CHECK: ## %bb.0 +; CHECK-NEXT: andl $242, %edi +define i1 @test_sle3(i32 %a0) { + %1 = and i32 %a0, 242 + %2 = icmp sle i32 %1, 127 + ret i1 %2 +} + +;; SLT +; CHECK-LABEL: @test_slt1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_slt1(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp slt i32 %1, -42 + ret i1 %2 +} + +; CHECK-LABEL: @test_slt2 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_slt2(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = and i32 %1, 2147483647 ; i32_MAX + %3 = icmp slt i32 126, %2 + ret i1 %3 +} + +; CHECK-LABEL: @test_slt3 +; CHECK: ## %bb.0 +; CHECK-NEXT: orl $242, %edi +define i1 @test_slt3(i32 %a0) { + %1 = or i32 %a0, 242 + %2 = icmp slt i32 127, %1 + ret i1 %2 +} + +;; ULT +; CHECK-LABEL: @test_ult1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_ult1(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = icmp ult i32 %1, 42 + ret i1 %2 +} + +; CHECK-LABEL: @test_ult2 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_ult2(i32 %a0) { + %1 = and i32 %a0, 17 + %2 = icmp ult i32 %1, 42 + ret i1 %2 +} + +; CHECK-LABEL: @test_ult3 +; CHECK: ## %bb.0 +; CHECK-NEXT: andl $242, %edi +define i1 @test_ult3(i32 %a0) { + %1 = and i32 %a0, 242 + %2 = icmp ult i32 %1, 127 + ret i1 %2 +} + + +;; UGT +; CHECK-LABEL: @test_ugt1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_ugt1(i32 %a0) { + %1 = or i32 %a0, 127 + %2 = icmp ugt i32 42, %1 + ret i1 %2 +} + +; CHECK-LABEL: @test_ugt2 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_ugt2(i32 %a0) { + %1 = and i32 %a0, 17 + %2 = icmp ugt i32 42, %1 + ret i1 %2 +} + +; CHECK-LABEL: @test_ugt3 +; CHECK: ## %bb.0 +; CHECK-NEXT: andl $242, %edi +define i1 @test_ugt3(i32 %a0) { + %1 = and i32 %a0, 242 + %2 = icmp ugt i32 %1, 127 + ret i1 %2 +} + +;; SGT +; CHECK-LABEL: @test_sgt1 +; CHECK: ## %bb.0 +; CHECK-NEXT: xorl %eax, %eax +; CHECK-NEXT: retq +define i1 @test_sgt1(i32 %a0) { + %1 = and i32 %a0, 127 + %2 = icmp sgt i32 -17, %1 + ret i1 %2 +} + +; CHECK-LABEL: @test_sgt2 +; CHECK: ## %bb.0 +; CHECK-NEXT: movb $1, %al +; CHECK-NEXT: retq +define i1 @test_sgt2(i32 %a0) { + %1 = and i32 %a0, 17 + %2 = icmp sgt i32 42, %1 + ret i1 %2 +} + +; CHECK-LABEL: @test_sgt3 +; CHECK: ## %bb.0 +; CHECK-NEXT: orl $242, %edi +define i1 @test_sgt3(i32 %a0) { + %1 = or i32 %a0, 242 + %2 = icmp sgt i32 %1, 127 + ret i1 %2 +}