HomePhabricator

[LoopUnswitch] unswitch if cond is in select form of and/or as well

Authored by aqjune on Mar 7 2021, 8:05 AM.

Description

[LoopUnswitch] unswitch if cond is in select form of and/or as well

Hello all,
I'm trying to fix unsafe propagation of poison values in and/or conditions by using
equivalent select forms (select i1 A, i1 B, i1 false and select i1 A, i1 true, i1 false)
instead.
D93065 has links to patches for this.

This patch allows unswitch to happen if the condition is in this form as well.
collectHomogenousInstGraphLoopInvariants is updated to keep traversal if
Root and the visiting I matches both m_LogicalOr()/m_LogicalAnd().
Other than this, the remaining changes are almost straightforward and simply replaces
Instruction::And/Or check with match(m_LogicalOr()/m_LogicalAnd()).

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D97756

Event Timeline

Hi! This commit causes miscompilation.
Here's the test:

define i32 @foo(i32* %arg1, i1 %arg2, i1* %arg3, i1* %arg4) {
bb:
  %tmp7 = icmp ne i1 %arg2, 0
  %tmp9 = xor i1 %tmp7, true
  %tmp10 = or i1 %tmp7, %tmp9
  br label %bb11

bb11:
  %tmp13 = load volatile i1, i1* %arg3
  %tmp16 = xor i1 %tmp13, true
  %tmp17 = and i1 %tmp16, %tmp10
  %tmp18 = select i1 %tmp17, i1 true, i1 false
  br i1 %tmp18, label %bb20, label %bb21

bb20:
  store i32 42, i32* %arg1
  br label %bb21

bb21:
  %tmp23 = load volatile i1, i1* %arg4
  br i1 %tmp23, label %bb26, label %bb11

bb26:
  %tmp33 = load atomic i32, i32* %arg1 unordered, align 8
  ret i32 %tmp33
}

Non-trivial loop unswitch (bin/opt -passes='unswitch<nontrivial>' -S repro.ll) does the following:

define i32 @foo(i32* %arg1, i1 %arg2, i1* %arg3, i1* %arg4) {
bb:
  %tmp7 = icmp ne i1 %arg2, false
  %tmp9 = xor i1 %tmp7, true
  %tmp10 = or i1 %tmp7, %tmp9
  br i1 %tmp10, label %bb.split.us, label %bb.split

bb.split.us:                                      ; preds = %bb
  br label %bb11.us

bb11.us:                                          ; preds = %bb21.us, %bb.split.us
  %tmp13.us = load volatile i1, i1* %arg3, align 1
  %tmp16.us = xor i1 %tmp13.us, true
  %tmp17.us = and i1 %tmp16.us, true
  %tmp18.us = select i1 %tmp17.us, i1 true, i1 false
  br label %bb20.us

bb20.us:                                          ; preds = %bb11.us
  store i32 42, i32* %arg1, align 4
  br label %bb21.us

bb21.us:                                          ; preds = %bb20.us
  %tmp23.us = load volatile i1, i1* %arg4, align 1
  br i1 %tmp23.us, label %bb26.split.us, label %bb11.us

bb26.split.us:                                    ; preds = %bb21.us
  br label %bb26

bb.split:                                         ; preds = %bb
  br label %bb11

bb11:                                             ; preds = %bb21, %bb.split
  %tmp13 = load volatile i1, i1* %arg3, align 1
  %tmp16 = xor i1 %tmp13, true
  %tmp17 = and i1 %tmp16, false
  %tmp18 = select i1 %tmp17, i1 true, i1 false
  br i1 %tmp18, label %bb20, label %bb21

bb20:                                             ; preds = %bb11
  store i32 42, i32* %arg1, align 4
  br label %bb21

bb21:                                             ; preds = %bb20, %bb11
  %tmp23 = load volatile i1, i1* %arg4, align 1
  br i1 %tmp23, label %bb26.split, label %bb11

bb26.split:                                       ; preds = %bb21
  br label %bb26

bb26:                                             ; preds = %bb26.split.us, %bb26.split
  %tmp33 = load atomic i32, i32* %arg1 unordered, align 8
  ret i32 %tmp33
}

The problem is that in the version where %tmp10 == true the br i1 %tmp18, label %bb20, label %bb21 is folded away and we unconditionally jump to bb20.us even though we shouldn't.
If I remove %tmp18 and replace its use with %tmp17, it is unswitched correctly.
I think I know why this is happening. This code (llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp:1995):

bool Direction = true;
int ClonedSucc = 0;
if (!FullUnswitch) {
  if (!match(BI->getCondition(), m_LogicalOr())) {
    assert(match(BI->getCondition(), m_LogicalAnd()) &&
           "Only `or`, `and`, an `select` instructions can combine "
           "invariants being unswitched.");
    Direction = false;
    ClonedSucc = 1;
  }
}

Assumes that the condition is either m_LogicalOr() or m_LogicalAnd(), but doesn't check this assumption. In the reproducer both m_LogicalOr() and m_LogicalAnd() are true for the tmp18 which leads to incorrect RetainedSuccBB selection.
Without the fuzzy matching introduced by this patch it wasn't possible to reach such state, so please fix this issue or revert your patch.

I'll make a fix for this, thanks.

I made a fix to keep the main branch in a good state, but not sure this is a real solution because there might be a hidden problem. I'm investigating it.

I made a fix to keep the main branch in a good state, but not sure this is a real solution because there might be a hidden problem. I'm investigating it.

Please add an assertion that m_LogicalOr() and m_LogicalAnd() aren't true at the same time.

I made a fix to keep the main branch in a good state, but not sure this is a real solution because there might be a hidden problem. I'm investigating it.

Please add an assertion that m_LogicalOr() and m_LogicalAnd() aren't true at the same time.

Added it; test-suite passed successfully at least.
I'll wait and see if there is any reported failure from the assertion. Sorry for the bug.