[SimpleLoopUnswitch] Don't unswitch constant conditions

[DaniilSuchkov]

Summary

Added an additional check for constants after simplification of select _, true, false pattern. We need to prevent attempts to unswitch constant conditions for two reasons:
a) Doing that doesn't make any sense, in the best case it will just burn some compile time.
b) SimpleLoopUnswitch isn't designed to unswitch constant conditions (due to (a)), so attempting that can cause miscompiles. The attached testcase is an example of such miscompile.

Also I added an assertion that'll make sure we aren't trying to replace constants, so it will help us prevent such bugs in future. The assertion from D110751 is another layer of protection against such cases.

[aeubanks]

can you add the motivation for this change to the description?

[DaniilSuchkov]

In D110752#3032108, @aeubanks wrote:

can you add the motivation for this change to the description?

Does it look good now? Or you think something else should be added?

[aeubanks]

thanks, the description is good, but the test doesn't seem right

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-invariant-select-bug.ll

7

this doesn't actually happen right now?

[DaniilSuchkov]

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-invariant-select-bug.ll

7

Right now, since neither this patch, nor D110751 are landed, that's exactly what happens. Sorry, I forgot to add D110751 as a dependency. With that patch we get an assertion failure in this case instead of what you see in CHECKs.

[lebedev.ri]

Is this falling into the traditional trap of the fact that constants and constant expressions are both represented by the Constant class?
Presumably while we obviously shouldn't unswitch immediate constants, constant expressions are a fair game still?

[DaniilSuchkov]

In D110752#3034441, @lebedev.ri wrote:

Is this falling into the traditional trap of the fact that constants and constant expressions are both represented by the Constant class?
Presumably while we obviously shouldn't unswitch immediate constants, constant expressions are a fair game still?

I don't quite understand your question. Let me explain what's going on.

This bug is introduced by this quick fix: https://reviews.llvm.org/rG6b4b1dc6ec6f
Before that we would never add a constant (i.e. Value with isa<Constant> == true) to the list of unswitch candidates. After that patch it became possible for true or false to become a condition that we're trying to unswitch.

As for the assertion which I added, in replaceLoopInvariantUses there's a piece of code that does very similar thing and it has assert(!isa<Constant>(Invariant) && "Why are we unswitching on a constant?");, so lack of such an assertion in this code seems just an oversight.

[DaniilSuchkov]

Rebased on top of new version of D110751. Now it should be easier to understand what's going on with the test.

[aeubanks]

rebasing this on D110751 is confusing, especially since the test is XFAIL in that patch
I'd just add the test and run update_test_checks.py on it in this patch

then just add the asserts in D110751 in don't touch any test cases in that patch

[DaniilSuchkov]

In D110752#3034962, @aeubanks wrote:

rebasing this on D110751 is confusing, especially since the test is XFAIL in that patch
I'd just add the test and run update_test_checks.py on it in this patch

then just add the asserts in D110751 in don't touch any test cases in that patch

Well, D110751 turns the miscompile into and assertion failure, and with this patch instead of assertion failure we'll get a completely valid result.
I think this sequence of changes makes sense.

[aeubanks]

In D110752#3035012, @DaniilSuchkov wrote:

In D110752#3034962, @aeubanks wrote:

rebasing this on D110751 is confusing, especially since the test is XFAIL in that patch
I'd just add the test and run update_test_checks.py on it in this patch

then just add the asserts in D110751 in don't touch any test cases in that patch

Well, D110751 turns the miscompile into and assertion failure, and with this patch instead of assertion failure we'll get a completely valid result.
I think this sequence of changes makes sense.

Probably a matter a preference, but I think we should fix the issue first. I'm not a fan of XFAIL tests. You could even merge the two patches into one.
Any other preferences from other reviewers?

[nikic]

In D110752#3035034, @aeubanks wrote:

In D110752#3035012, @DaniilSuchkov wrote:

In D110752#3034962, @aeubanks wrote:

rebasing this on D110751 is confusing, especially since the test is XFAIL in that patch
I'd just add the test and run update_test_checks.py on it in this patch

then just add the asserts in D110751 in don't touch any test cases in that patch

Well, D110751 turns the miscompile into and assertion failure, and with this patch instead of assertion failure we'll get a completely valid result.
I think this sequence of changes makes sense.

Probably a matter a preference, but I think we should fix the issue first. I'm not a fan of XFAIL tests. You could even merge the two patches into one.
Any other preferences from other reviewers?

Agree, we should fix the issue first and then land the assert. We shouldn't add asserts that are known to fail in advance.

[DaniilSuchkov]

Now D110751 is on top of this change.

[aeubanks]

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-invariant-select-bug.ll

7

where is this diff coming from? the test isn't in tree
could just add this test in this patch

(otherwise this patch lg)

[DaniilSuchkov]

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-invariant-select-bug.ll

7

I'll land this test with the patch (in a separate commit). I prefer to add tests separately because otherwise reviewers have to guess how the patch is connected with the test.

[aeubanks]

lg, thanks!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

bool ReplaceUnswitched =
         FullUnswitch || (Invariants.size() == 1) || PartiallyInvariant;
 
     ConstantInt *UnswitchedReplacement =
         Direction ? ConstantInt::getTrue(BI->getContext())
                   : ConstantInt::getFalse(BI->getContext());
     ConstantInt *ContinueReplacement =
         Direction ? ConstantInt::getFalse(BI->getContext())
                   : ConstantInt::getTrue(BI->getContext());
-    for (Value *Invariant : Invariants)
+    for (Value *Invariant : Invariants) {
+      assert(!isa<Constant>(Invariant) &&
+             "Should not be replacing constant values!");
       // Use make_early_inc_range here as set invalidates the iterator.
       for (Use &U : llvm::make_early_inc_range(Invariant->uses())) {
         Instruction *UserI = dyn_cast<Instruction>(U.getUser());
         if (!UserI)
           continue;
 
         // Replace it with the 'continue' side if in the main loop body, and the
         // unswitched if in the cloned blocks.
         if (DT.dominates(LoopPH, UserI->getParent()))
           U.set(ContinueReplacement);
         else if (ReplaceUnswitched &&
                  DT.dominates(ClonedPH, UserI->getParent()))
           U.set(UnswitchedReplacement);
       }
     }
+  }
 
   // We can change which blocks are exit blocks of all the cloned sibling
   // loops, the current loop, and any parent loops which shared exit blocks
   // with the current loop. As a consequence, we need to re-form LCSSA for
   // them. But we shouldn't need to re-form LCSSA for any child loops.
   // FIXME: This could be made more efficient by tracking which exit blocks are
   // new, and focusing on them, but that isn't likely to be necessary.
   //
for (auto *BB : L.blocks()) {
 
     // If BI's condition is 'select _, true, false', simplify it to confuse
     // matchers
     Value *Cond = BI->getCondition(), *CondNext;
     while (match(Cond, m_Select(m_Value(CondNext), m_One(), m_Zero())))
       Cond = CondNext;
     BI->setCondition(Cond);
 
+    if (isa<Constant>(Cond))
+      continue;
+
     if (L.isLoopInvariant(BI->getCondition())) {
       UnswitchCandidates.push_back({BI, {BI->getCondition()}});
       continue;
     }
 
     Instruction &CondI = *cast<Instruction>(BI->getCondition());
     if (match(&CondI, m_CombineOr(m_LogicalAnd(), m_LogicalOr()))) {
       TinyPtrVector<Value *> Invariants =

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-invariant-select-bug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='simple-loop-unswitch<nontrivial>' -S < %s | FileCheck %s
 
-; FIXME: We should not replace `true` with `false` here!
+; If we try to replace uses of `true` outside of `@foo`, we'll see it here.
 define i1 @bar() {
 ; CHECK-LABEL: @bar(
-; CHECK-NEXT:    ret i1 false
+; CHECK-NEXT:    ret i1 true
 ;
   ret i1 true
 }
 
-; FIXME: We shouldn't unswitch this loop!
+; We shouldn't unswitch this loop.
 define void @foo() {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 true, label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
-; CHECK:       entry.split.us:
-; CHECK-NEXT:    br label [[HEADER_US:%.*]]
-; CHECK:       header.us:
-; CHECK-NEXT:    [[VAL_US:%.*]] = select i1 true, i1 true, i1 false
-; CHECK-NEXT:    br label [[EXIT_SPLIT_US:%.*]]
-; CHECK:       exit.split.us:
-; CHECK-NEXT:    br label [[EXIT:%.*]]
-; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[VAL:%.*]] = select i1 false, i1 false, i1 false
-; CHECK-NEXT:    br label [[HEADER]]
+; CHECK-NEXT:    [[VAL:%.*]] = select i1 true, i1 true, i1 false
+; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %header
 
 header:
   %val = select i1 true, i1 true, i1 false
   br i1 %val, label %exit, label %header
 
 exit:
   ret void
 }