[SimplifyCFG] Don't SimplifyBranchOnICmpChain with ExtraCase

[vitalybuka]

Summary

Here we try to avoid issues with "explicit branch" with SimplifyBranchOnICmpChain
which can check on undef. Msan by design reports branches on uninitialized
memory and undefs, so we have false report here.

In general msan does not like when we convert

// If at least one of them is true we can MSAN is ok if another is undefs
if (a || b)
  return;

into

// If 'a' is undef MSAN will complain even if 'b' is true
if (a)
  return;
if (b)
  return;

Example

Before optimization we had something like this:

while (true) {
  bool maybe_undef = doStuff();

  while (true) {
    char c = getChar();
    if (c != 10 && c != 13)
     continue
    break;
  }

  // we know that c == 10 || c == 13 if we get here,
  // so msan know that branch is not affected by maybe_undef
  if (maybe_undef || c == 10 || c == 13) 
    continue;
  return;
}

SimplifyBranchOnICmpChain will convert that into

while (true) {
  bool maybe_undef = doStuff();

  while (true) {
    char c = getChar();
    if (c != 10 && c != 13)
      continue;
    break;
  }

  // however msan will complain here:
  if (maybe_undef)
    continue; 

  // we know that c == 10 || c == 13, so either way we will get continue
  switch(c) {
    case 10: continue;
    case 13: continue;
  }
  return;
}

[vitalybuka]

typo

[vitalybuka]

Assertions really have been autogenerated by utils/update_test_checks.py

[vitalybuka]

regenerate assertions with patched compiler

[efriedma]

You description of the issue uses "||" in the pseudo-code; I assume you actually mean a non-short-circuiting "|"?

Is there a general description somewhere of what restrictions msan places on IR transforms vs. normal IR semantics? It's not obvious to me that this transform, specifically, is incorrect, as opposed to whatever transform is producing this IR.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3748

Can you fix this so we return early before the LLVM_DEBUG log?

[vitalybuka]

early return

[eugenis]

Basically, the only rule is that you should not speculatively introduce a conditional branch on value that might be undef and is not guaranteed to execute in the input IR.

You can find an investigation of a similar problem in LoopUnswitch in this bug:
https://bugs.llvm.org/show_bug.cgi?id=28054
It has some ideas of a better approach at the end, but we never acted on those. It sounds like a very hard problem.

[vitalybuka]

In D67205#1659684, @efriedma wrote:

You description of the issue uses "||" in the pseudo-code; I assume you actually mean a non-short-circuiting "|"?

yes, updated description

Is there a general description somewhere of what restrictions msan places on IR transforms vs. normal IR semantics? It's not obvious to me that this transform, specifically, is incorrect, as opposed to whatever transform is producing this IR.

I don't have one. @eugenis ?

[efriedma]

LGTM

Basically, the only rule is that you should not speculatively introduce a conditional branch on value that might be undef and is not guaranteed to execute in the input IR.

That makes sense... can we put a brief description of that in LangRef?

[eugenis]

LGTM

I'll update LangRef.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
   // Figure out which block is which destination.
   BasicBlock *DefaultBB = BI->getSuccessor(1);
   BasicBlock *EdgeBB = BI->getSuccessor(0);
   if (!TrueWhenEqual)
     std::swap(DefaultBB, EdgeBB);
 
   BasicBlock *BB = BI->getParent();
 
+  // MSAN does not like undefs as branch condition which can be introduced
+  // with "explicit branch".
+  if (ExtraCase && BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory))
+    return false;
+
   LLVM_DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
                     << " cases into SWITCH.  BB is:\n"
                     << *BB);
 
   // If there are any extra values that couldn't be folded into the switch
-  // then we evaluate them with an explicit branch first.  Split the block
+  // then we evaluate them with an explicit branch first. Split the block
   // right before the condbr to handle it.
   if (ExtraCase) {
     BasicBlock *NewBB =
         BB->splitBasicBlock(BI->getIterator(), "switch.early.test");
     // Remove the uncond branch added to the old block.
     Instruction *OldTI = BB->getTerminator();
     Builder.SetInsertPoint(OldTI);
 
     if (TrueWhenEqual)
       Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
     else
       Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
 
     OldTI->eraseFromParent();

llvm/test/Transforms/SimplifyCFG/switch_msan.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -simplifycfg < %s | FileCheck %s
+
+declare i8 @next_char();
+
+define void @test_no_msan() {
+; CHECK-LABEL: @test_no_msan(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    br label [[WHILE_BODY_I:%.*]]
+; CHECK:       while.body.i:
+; CHECK-NEXT:    [[MAYBE_UNDEF:%.*]] = phi i1 [ undef, [[WHILE_BODY]] ], [ [[NEXT_MAYBE_UNDEF:%.*]], [[WHILE_BODY_I]] ]
+; CHECK-NEXT:    [[C:%.*]] = call fastcc signext i8 @next_char()
+; CHECK-NEXT:    [[C_10:%.*]] = icmp eq i8 [[C]], 10
+; CHECK-NEXT:    [[C_13:%.*]] = icmp eq i8 [[C]], 13
+; CHECK-NEXT:    [[C_10_OR_13:%.*]] = or i1 [[C_10]], [[C_13]]
+; CHECK-NEXT:    [[NEXT_MAYBE_UNDEF]] = or i1 [[MAYBE_UNDEF]], [[C_10_OR_13]]
+; CHECK-NEXT:    [[C_NOT_10_OR_13:%.*]] = xor i1 [[C_10_OR_13]], true
+; CHECK-NEXT:    br i1 [[C_NOT_10_OR_13]], label [[WHILE_BODY_I]], label [[WHILE_BODY_I_BREAK:%.*]]
+; CHECK:       while.body.i.break:
+; CHECK-NEXT:    br i1 [[MAYBE_UNDEF]], label [[WHILE_BODY]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK:       switch.early.test:
+; CHECK-NEXT:    switch i8 [[C]], label [[RETURN:%.*]] [
+; CHECK-NEXT:    i8 13, label [[WHILE_BODY]]
+; CHECK-NEXT:    i8 10, label [[WHILE_BODY]]
+; CHECK-NEXT:    ]
+; CHECK:       return:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  br label %while.body
+
+while.body:
+  br label %while.body.i
+
+while.body.i:
+  %maybe_undef = phi i1 [ undef, %while.body ], [ %next_maybe_undef, %while.body.i ]
+  %c = call fastcc signext i8 @next_char()
+  %c_10 = icmp eq i8 %c, 10
+  %c_13 = icmp eq i8 %c, 13
+  %c_10_or_13 = or i1 %c_10, %c_13
+  %next_maybe_undef = or i1 %maybe_undef, %c_10_or_13
+  %c_not_10_or_13 = xor i1 %c_10_or_13, true
+  br i1 %c_not_10_or_13, label %while.body.i, label %while.body.i.break
+
+while.body.i.break:
+  ; NEXT_MAYBE_UNDEF is never undef if here
+  br i1 %next_maybe_undef, label %while.body, label %return
+
+
+return:
+  ret void
+}
+
+
+define void @test_msan() sanitize_memory {
+; CHECK-LABEL: @test_msan(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    br label [[WHILE_BODY_I:%.*]]
+; CHECK:       while.body.i:
+; CHECK-NEXT:    [[MAYBE_UNDEF:%.*]] = phi i1 [ undef, [[WHILE_BODY]] ], [ [[NEXT_MAYBE_UNDEF:%.*]], [[WHILE_BODY_I]] ]
+; CHECK-NEXT:    [[C:%.*]] = call fastcc signext i8 @next_char()
+; CHECK-NEXT:    [[C_10:%.*]] = icmp eq i8 [[C]], 10
+; CHECK-NEXT:    [[C_13:%.*]] = icmp eq i8 [[C]], 13
+; CHECK-NEXT:    [[C_10_OR_13:%.*]] = or i1 [[C_10]], [[C_13]]
+; CHECK-NEXT:    [[NEXT_MAYBE_UNDEF]] = or i1 [[MAYBE_UNDEF]], [[C_10_OR_13]]
+; CHECK-NEXT:    [[C_NOT_10_OR_13:%.*]] = xor i1 [[C_10_OR_13]], true
+; CHECK-NEXT:    br i1 [[C_NOT_10_OR_13]], label [[WHILE_BODY_I]], label [[WHILE_BODY_I_BREAK:%.*]]
+; CHECK:       while.body.i.break:
+; CHECK-NEXT:    br i1 [[NEXT_MAYBE_UNDEF]], label [[WHILE_BODY]], label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  br label %while.body
+
+while.body:
+  br label %while.body.i
+
+while.body.i:
+  %maybe_undef = phi i1 [ undef, %while.body ], [ %next_maybe_undef, %while.body.i ]
+  %c = call fastcc signext i8 @next_char()
+  %c_10 = icmp eq i8 %c, 10
+  %c_13 = icmp eq i8 %c, 13
+  %c_10_or_13 = or i1 %c_10, %c_13
+  %next_maybe_undef = or i1 %maybe_undef, %c_10_or_13
+  %c_not_10_or_13 = xor i1 %c_10_or_13, true
+  br i1 %c_not_10_or_13, label %while.body.i, label %while.body.i.break
+
+while.body.i.break:
+  ; NEXT_MAYBE_UNDEF is never undef if here
+  br i1 %next_maybe_undef, label %while.body, label %return
+
+
+return:
+  ret void
+}