Fix MSan false positive due to select folding.

[eugenis]

Summary

Select folding in JumpThreading can create a conditional branch on a
code patch that did not have one in the original program. This is not a
valid transformation in sanitize_memory functions.

Note that JumpThreading does select folding in 3 different places. Two
of them seem safe - they apply to a select instruction in a BB that ends
with an unconditional branch to another BB, which (in turn) ends with a
conditional branch or a switch with the same condition.

Fixes PR45220.

[eugenis]

For the reference, this revision added the LangRef blurb about msan and conditional branches:
https://reviews.llvm.org/D67244

[efriedma]

I'm not sure this transform is actually safe even outside of msan workflows.

[spatel]

In D76332#1927877, @efriedma wrote:

I'm not sure this transform is actually safe even outside of msan workflows.

According to Alive2 (cc @regehr @aqjune ), it's not:
http://volta.cs.utah.edu:8080/z/53knD3
(Hopefully, I reduced the test posted here correctly.)

[aqjune]

In this example, giving -disable-undef-input (which assumes the input is never undef) shows a clearer output: http://volta.cs.utah.edu:8080/z/N5eP_-
If %b is false, the source program does not have UB where as the optimized program has conditional branch on %x which can introduce UB.

[eugenis]

Interesting. Poison semantics are very similar to MemorySanitizer model.
Should I remove TryToUnfoldSelectInCurrBB completely? I don't see how it can be saved.
Am I right about the other two instances of select folding in this pass being safe? They insert new conditional branches only on code paths that already had a branch with the same condition.

[spatel]

In D76332#1929390, @aqjune wrote:

In this example, giving -disable-undef-input (which assumes the input is never undef) shows a clearer output: http://volta.cs.utah.edu:8080/z/N5eP_-
If %b is false, the source program does not have UB where as the optimized program has conditional branch on %x which can introduce UB.

I'm catching back up on my poison reading. :)
In the original program with select: if %b is false, then %v becomes poison. Then the select condition is poisoned, so the result must be poison, right? Is there some reason that we didn't make the select semantics for poison explicit in the LangRef?
https://bugs.llvm.org/show_bug.cgi?id=20895
https://lists.llvm.org/pipermail/llvm-dev/2014-September/076634.html

[spatel]

In D76332#1929671, @eugenis wrote:

Interesting. Poison semantics are very similar to MemorySanitizer model.
Should I remove TryToUnfoldSelectInCurrBB completely? I don't see how it can be saved.

I'm looking at a similar question with D76153. Without 'freeze', I suspect we're going to hit perf regressions. But AFAIK, nobody has measured those.

[efriedma]

Is there some reason that we didn't make the select semantics for poison explicit in the LangRef?

The exact semantics were evolving for a while, and nobody actually wrote up where we landed with Alive2.

Should I remove TryToUnfoldSelectInCurrBB completely? I don't see how it can be saved.

See the documentation comment on TryToUnfoldSelectInCurrBB. The ultimate transform we're actually hoping to perform, which is jump threading to simplify the select, is legal. So it's probably worth trying to do that, still, even if the intermediate step TryToUnfoldSelectInCurrBB actually implements isn't legal.

We already have some other code that tries to handle selects; I'm not sure how much of an optimization gap would remain if we just delete TryToUnfoldSelectInCurrBB.

[spatel]

In D76332#1929773, @efriedma wrote:

Is there some reason that we didn't make the select semantics for poison explicit in the LangRef?

The exact semantics were evolving for a while, and nobody actually wrote up where we landed with Alive2.

Thanks - I pushed the text from the bug report here:
rGfaba1d034a04
If we need to amend/extend that in some way, let me know.

Should I remove TryToUnfoldSelectInCurrBB completely? I don't see how it can be saved.

See the documentation comment on TryToUnfoldSelectInCurrBB. The ultimate transform we're actually hoping to perform, which is jump threading to simplify the select, is legal. So it's probably worth trying to do that, still, even if the intermediate step TryToUnfoldSelectInCurrBB actually implements isn't legal.

We already have some other code that tries to handle selects; I'm not sure how much of an optimization gap would remain if we just delete TryToUnfoldSelectInCurrBB.

I added the reduced example from this report as a regression test, so we can adjust this patch to just delete the whole function without having to add an MSan-specific test:
rG22c66c1a28c0

(can use 'utils/update_test_checks.py --function=TryToUnfoldSelectInCurrBB' to auto-gen the new CHECK lines for that test only)

[eugenis]

Going back to this change... It does not look like I'll have the cycles any time soon to reimplement TryToUnfoldSelectInCurrBB properly. Sorry about that.
WDYT about landing this change as-is to fix the immediate issue with MemorySanitizer?

[efriedma]

Sure, we can land this in the meantime. But please update the code comment to note the result of this discussion.

[eugenis]

updated the comment

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 /// And expand the select into a branch structure. This later enables
 /// jump-threading over bb in this pass.
 ///
 /// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold
 /// select if the associated PHI has at least one constant.  If the unfolded
 /// select is not jump-threaded, it will be folded again in the later
 /// optimizations.
 bool JumpThreadingPass::TryToUnfoldSelectInCurrBB(BasicBlock *BB) {
+  // This transform can introduce a UB (a conditional branch that depends on a
+  // poison value) that was not present in the original program. See
+  // @TryToUnfoldSelectInCurrBB test in test/Transforms/JumpThreading/select.ll.
+  // Disable this transform under MemorySanitizer.
+  // FIXME: either delete it or replace with a valid transform. This issue is
+  // not limited to MemorySanitizer (but has only been observed as an MSan false
+  // positive in practice so far).
+  if (BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory))
+    return false;
+
   // If threading this would thread across a loop header, don't thread the edge.
   // See the comments above FindLoopHeaders for justifications and caveats.
   if (LoopHeaders.count(BB))
     return false;
 
   for (BasicBlock::iterator BI = BB->begin();
        PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
     // Look for a Phi having at least one constant incoming value.

llvm/test/Transforms/JumpThreading/select-unfold-msan.ll

+; PR45220
+; RUN: opt -S -jump-threading < %s | FileCheck %s
+
+declare i1 @NOP()
+
+define dso_local i32 @f(i1 %b, i1 %u) sanitize_memory {
+entry:
+  br i1 %b, label %if.end, label %if.else
+
+if.else:
+  %call = call i1 @NOP()
+  br label %if.end
+
+if.end:
+; Check that both selects in this BB are still in place,
+; and were not replaced with a conditional branch.
+; CHECK:      phi
+; CHECK-NEXT: phi
+; CHECK-NEXT: select
+; CHECK-NEXT: select
+; CHECK-NEXT: ret
+  %u1 = phi i1 [ true, %if.else ], [ %u, %entry ]
+  %v = phi i1 [ %call, %if.else ], [ false, %entry ]
+  %s = select i1 %u1, i32 22, i32 0
+  %v1 = select i1 %v, i32 %s, i32 42
+  ret i32 %v1
+}
+