From a7ac0dd0cf2be760ea847b5c6ed154cae33b67e7 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Thu, 6 Oct 2022 17:17:37 +0100 Subject: [PATCH] [ConstraintElimination] Generalize AND matching. Extend more general matching used for chains of ORs to also support chains of ANDs. --- .../Transforms/Scalar/ConstraintElimination.cpp | 48 +++++++++++----------- llvm/test/Transforms/ConstraintElimination/and.ll | 26 ++++++------ 2 files changed, 37 insertions(+), 37 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index b5329ac..6013650 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -578,51 +578,51 @@ void State::addInfoFor(BasicBlock &BB) { if (!Br || !Br->isConditional()) return; - // If the condition is a chain of ORs and the false successor only has - // the current block as predecessor, queue the negated conditions for the - // false successor. + Value *Cond = Br->getCondition(); + + // If the condition is a chain of ORs/AND and the successor only has the + // current block as predecessor, queue conditions for the successor. Value *Op0, *Op1; - if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1)))) { - BasicBlock *FalseSuccessor = Br->getSuccessor(1); - if (canAddSuccessor(BB, FalseSuccessor)) { + if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) || + match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { + bool IsOr = match(Cond, m_LogicalOr()); + bool IsAnd = match(Cond, m_LogicalAnd()); + // If there's a select that matches both AND and OR, we need to commit to + // one of the options. Arbitrarily pick OR. + if (IsOr && IsAnd) + IsAnd = false; + + BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0); + if (canAddSuccessor(BB, Successor)) { SmallVector CondWorkList; SmallPtrSet SeenCond; auto QueueValue = [&CondWorkList, &SeenCond](Value *V) { if (SeenCond.insert(V).second) CondWorkList.push_back(V); }; - QueueValue(Op0); QueueValue(Op1); + QueueValue(Op0); while (!CondWorkList.empty()) { Value *Cur = CondWorkList.pop_back_val(); if (auto *Cmp = dyn_cast(Cur)) { - WorkList.emplace_back(DT.getNode(FalseSuccessor), Cmp, true); + WorkList.emplace_back(DT.getNode(Successor), Cmp, IsOr); continue; } - if (match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) { + if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) { + QueueValue(Op1); QueueValue(Op0); + continue; + } + if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { QueueValue(Op1); + QueueValue(Op0); + continue; } } } return; } - // If the condition is an AND of 2 compares and the true successor only has - // the current block as predecessor, queue both conditions for the true - // successor. - if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) && - isa(Op0) && isa(Op1)) { - BasicBlock *TrueSuccessor = Br->getSuccessor(0); - if (canAddSuccessor(BB, TrueSuccessor)) { - WorkList.emplace_back(DT.getNode(TrueSuccessor), cast(Op0), - false); - WorkList.emplace_back(DT.getNode(TrueSuccessor), cast(Op1), - false); - } - return; - } - auto *CmpI = dyn_cast(Br->getCondition()); if (!CmpI) return; diff --git a/llvm/test/Transforms/ConstraintElimination/and.ll b/llvm/test/Transforms/ConstraintElimination/and.ll index 284f98c..25fab8d 100644 --- a/llvm/test/Transforms/ConstraintElimination/and.ll +++ b/llvm/test/Transforms/ConstraintElimination/and.ll @@ -203,13 +203,13 @@ define i1 @test_and_chain_ule_1(i4 %x, i4 %y, i4 %z, i4 %a) { ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i4 [[X]], [[Z]] ; CHECK-NEXT: [[T_2:%.*]] = icmp ule i4 [[X]], [[Y]] -; CHECK-NEXT: [[R_1:%.*]] = xor i1 [[T_1]], [[T_2]] +; CHECK-NEXT: [[R_1:%.*]] = xor i1 true, true ; CHECK-NEXT: [[T_3:%.*]] = icmp ule i4 [[Y]], [[Z]] -; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[T_3]] +; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], true ; CHECK-NEXT: [[T_4:%.*]] = icmp ule i4 3, [[X]] -; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], [[T_4]] +; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], true ; CHECK-NEXT: [[T_5:%.*]] = icmp ule i4 3, [[A]] -; CHECK-NEXT: [[R_4:%.*]] = xor i1 [[R_3]], [[T_5]] +; CHECK-NEXT: [[R_4:%.*]] = xor i1 [[R_3]], true ; CHECK-NEXT: [[C_5:%.*]] = icmp ule i4 [[X]], [[A]] ; CHECK-NEXT: [[R_5:%.*]] = xor i1 [[R_4]], [[C_5]] ; CHECK-NEXT: ret i1 [[R_5]] @@ -291,13 +291,13 @@ define i1 @test_and_chain_ule_2(i4 %x, i4 %y, i4 %z, i4 %a) { ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i4 [[X]], [[Z]] ; CHECK-NEXT: [[T_2:%.*]] = icmp ule i4 [[X]], [[Y]] -; CHECK-NEXT: [[R_1:%.*]] = xor i1 [[T_1]], [[T_2]] +; CHECK-NEXT: [[R_1:%.*]] = xor i1 true, true ; CHECK-NEXT: [[T_3:%.*]] = icmp ule i4 [[Y]], [[Z]] -; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[T_3]] +; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], true ; CHECK-NEXT: [[T_4:%.*]] = icmp ule i4 3, [[X]] -; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], [[T_4]] +; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], true ; CHECK-NEXT: [[T_5:%.*]] = icmp ule i4 3, [[A]] -; CHECK-NEXT: [[R_4:%.*]] = xor i1 [[R_3]], [[T_5]] +; CHECK-NEXT: [[R_4:%.*]] = xor i1 [[R_3]], true ; CHECK-NEXT: [[C_5:%.*]] = icmp ule i4 [[X]], [[A]] ; CHECK-NEXT: [[R_5:%.*]] = xor i1 [[R_4]], [[C_5]] ; CHECK-NEXT: ret i1 [[R_5]] @@ -380,9 +380,9 @@ define i1 @test_and_chain_with_other_insts_ule(i4 %x, i4 %y, i4 %z, i4 %a, i1 %a ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i4 [[X]], [[Z]] ; CHECK-NEXT: [[T_2:%.*]] = icmp ule i4 [[X]], [[Y]] -; CHECK-NEXT: [[R_1:%.*]] = xor i1 [[T_1]], [[T_2]] +; CHECK-NEXT: [[R_1:%.*]] = xor i1 true, true ; CHECK-NEXT: [[T_3:%.*]] = icmp ule i4 [[Y]], [[Z]] -; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[T_3]] +; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], true ; CHECK-NEXT: [[C_4:%.*]] = icmp ule i4 3, [[X]] ; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], [[C_4]] ; CHECK-NEXT: [[C_5:%.*]] = icmp ule i4 3, [[A:%.*]] @@ -466,13 +466,13 @@ define i1 @test_and_chain_select_ule(i4 %x, i4 %y, i4 %z, i4 %a) { ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i4 [[X]], [[Z]] ; CHECK-NEXT: [[T_2:%.*]] = icmp ule i4 [[X]], [[Y]] -; CHECK-NEXT: [[R_1:%.*]] = xor i1 [[T_1]], [[T_2]] +; CHECK-NEXT: [[R_1:%.*]] = xor i1 [[T_1]], true ; CHECK-NEXT: [[T_3:%.*]] = icmp ule i4 [[Y]], [[Z]] ; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[T_3]] ; CHECK-NEXT: [[T_4:%.*]] = icmp ule i4 3, [[X]] -; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], [[T_4]] +; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], true ; CHECK-NEXT: [[T_5:%.*]] = icmp ule i4 3, [[A]] -; CHECK-NEXT: [[R_4:%.*]] = xor i1 [[R_3]], [[T_5]] +; CHECK-NEXT: [[R_4:%.*]] = xor i1 [[R_3]], true ; CHECK-NEXT: [[C_5:%.*]] = icmp ule i4 [[X]], [[A]] ; CHECK-NEXT: [[R_5:%.*]] = xor i1 [[R_4]], [[C_5]] ; CHECK-NEXT: ret i1 [[R_5]] -- 2.7.4