Disable MSan-hostile loop unswitching.

[eugenis]

Summary

Loop unswitching may cause MSan false positive when the unswitch
condition is not guaranteed to execute.

This is very similar to ASan and TSan special case in
llvm::isSafeToSpeculativelyExecute (they don't like speculative loads
and stores), but for branch instructions.

Fixes PR28054.

[chandlerc]

It seems strange to me that this is an MSan-specific issue...

Is that because MSan causes a branch on an uninitialized value to immediately become a side-effect, while LLVM doesn't? If that's the case, I'd really like Sanjoy and David to look at this because we keep finding reasons why branching on undef has more effect than you would naively expect, so I'm worried this could actually lead to a problem outside of MSan....

[sanjoy]

I want to think this through some more, but overall this doesn't sound
too scary to me. Generally, I don't think we _can_ have branches on
undef be side effects, since we'd like to allow transforming:

%v = maybe_undef()
if (some_cond)
  return;
%v0 = select i1 %v, X, Y

to

%v = maybe_undef()
%v0 = select i1 %v, X, Y
if (some_cond)
  return;

to

%v = maybe_undef()
br %v, label %left, label %right

left:
  br merge

right:
  br merge

merge:
  %v0 = phi([X, left], [Y, right])

if (some_cond)
  return;

In other words, since we want selects to be side-effect free, and also
selects to be equivalent to br-phi, we need branches to be side-effect
free as well.

[chandlerc]

Thanks Sanjoy for thinking about this.

Provided that my reasoning holds (this is only a problem for MSan because it is essentially treating branch-on-uninit as a side-effect, I have one more high level question: is that even remotely reasonable?

Should the MSan report be suppressed until the side-effect bearing instruction is executed? I think that would cause MSan to not have a false positive here. I'd love to hear the thoughts of the MSan people here.

-Chandler

[eugenis]

In D21165#453075, @chandlerc wrote:

Should the MSan report be suppressed until the side-effect bearing instruction is executed? I think that would cause MSan to not have a false positive here. I'd love to hear the thoughts of the MSan people here.

Take this example:

while()

if (a)
  if (undef)
    doX
  else
    doY

is transformed to

if (undef)

while()
  if (a)
    doX

else

while()
  if (a)
    doY

The only way to see that the new code is fine (for some definition of fine) when a == false is to execute both branches and make sure that they have the same set of side effects. This sounds like an extremely difficult task in the general case.

[eugenis]

Of course, the loop may have other side-effect instructions that do not depend on a.
So we need to suppress reporting of "if undef" not just when the "then" BB has no side effects, but when "then" and "else" BBs have exactly the same set of side effects.

[eugenis]

Here is another example where it is basically impossible for MSan to propagate initializeness information exactly after the unswitching optimization.

This loop is unswitched on y, then we have 2 copies of the loop calculating "a" and phi + ret at the end. When y is undef, if we just track a single-bit "control flow is poisoned" state, we end up with "a" being undef, too. To conclude that a is defined MSan has to prove that both loops calculate "a" with the same sequence of operations which sounds impossible in the general case.

volatile int sink;
y = undef
z = 1
int f(bool y, unsigned z) {

int a = 42;
for (int i = 0; i < z; ++i) {
  if (i)
    if (y)
      sink = 1;
  a ^= 123;
}
return a;

}

[eugenis]

I've updated the bug with a better description of the problem and possible solutions.
I've added a comment to LoopUnswitch.

It looks like this CL is the only way of fixing this problem quickly. The sanitizer-x86_64-bootstrap bot is currently broken due to this, so I'd like to go ahead and commit this change.

[chandlerc]

Thanks for all the work to understand the nature of this discrepancy between MSan's semantics and the LLVM IR semantics. That bug will hopefully let us converge eventually. This seems like a reasonably isolated and minimal workaround in the mean time. Some factoring comments below.

include/llvm/Transforms/Utils/LoopUtils.h

401–403

This no longer seems like LICM-specific safety?

lib/Transforms/Scalar/LICM.cpp

737

The definition should probably move out of LICM at this point.

Maybe do this in a separate patch if it is going to touch a bunch of stuff?

[eugenis]

Depends on the refactoring in D21234

[chandlerc]

LGTM with a minor tweak below.

lib/Transforms/Scalar/LoopUnswitch.cpp

532–533

We have a member variable for optimizing for size, I would make this a member variable. That way you can initialize it once above for the function (with cleaner syntax) and then just re-use it everywhere.

[eugenis]

r272421

[eugenis]

Somehow I've lost the test in Diff 3.
I'll commit it separately.

include/llvm/Transforms/Utils/LoopUtils.h

bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &,
                                   Loop *, AliasSetTracker *, LICMSafetyInfo *);
 
 /// \brief Computes safety information for a loop
 /// checks loop body & header for the possibility of may throw
 /// exception, it takes LICMSafetyInfo and loop as argument.
 /// Updates safety information in LICMSafetyInfo argument.
 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
 
+bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
+                           const Loop *CurLoop,
+                           const LICMSafetyInfo *SafetyInfo);
+
 /// \brief Returns the instructions that use values defined in the loop.
 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
 
 /// \brief Find string metadata for loop
 ///
 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
 /// operand or null otherwise.  If the string metadata is not found return
 /// Optional's not-a-value.

lib/Transforms/Scalar/LICM.cpp

 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
                             const LICMSafetyInfo *SafetyInfo);
 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   const LICMSafetyInfo *SafetyInfo);
 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
                  const Loop *CurLoop, AliasSetTracker *CurAST,
                  const LICMSafetyInfo *SafetyInfo);
-static bool isGuaranteedToExecute(const Instruction &Inst,
-                                  const DominatorTree *DT, const Loop *CurLoop,
-                                  const LICMSafetyInfo *SafetyInfo);
 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
                                            const DominatorTree *DT,
                                            const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LICMSafetyInfo *SafetyInfo,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
                                            const LICMSafetyInfo *SafetyInfo,
                                            const Instruction *CtxI) {
   if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
     return true;
 
   return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
 }
 
-static bool isGuaranteedToExecute(const Instruction &Inst,
-                                  const DominatorTree *DT, const Loop *CurLoop,
-                                  const LICMSafetyInfo *SafetyInfo) {
+bool llvm::isGuaranteedToExecute(const Instruction &Inst,
 
   // We have to check to make sure that the instruction dominates all
   // of the exit blocks.  If it doesn't, then there is a path out of the loop
   // which does not execute this instruction, so we can't hoist it.
 
   // If the instruction is in the header block for the loop (which is very
   // common), it is always guaranteed to dominate the exit blocks.  Since this
   // is a common case, and can save some work, check it now.

lib/Transforms/Scalar/LoopUnswitch.cpp

class LoopUnswitch : public LoopPass {
     bool OptimizeForSize;
     bool redoLoop;
 
     Loop *currentLoop;
     DominatorTree *DT;
     BasicBlock *loopHeader;
     BasicBlock *loopPreheader;
 
+    LICMSafetyInfo SafetyInfo;
+
     // LoopBlocks contains all of the basic blocks of the loop, including the
     // preheader of the loop, the body of the loop, and the exit blocks of the
     // loop, in that order.
     std::vector<BasicBlock*> LoopBlocks;
     // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
     std::vector<BasicBlock*> NewBlocks;
 
   public:
bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
       *L->getHeader()->getParent());
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   LPM = &LPM_Ref;
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   currentLoop = L;
   Function *F = currentLoop->getHeader()->getParent();
 
+  if (F->hasFnAttribute(Attribute::SanitizeMemory))
+    computeLICMSafetyInfo(&SafetyInfo, L);
+
   EnabledPGO = F->getEntryCount().hasValue();
 
   if (LoopUnswitchWithBlockFrequency && EnabledPGO) {
     BranchProbabilityInfo BPI(*F, *LI);
     BFI.calculate(*L->getHeader()->getParent(), BPI, *LI);
 
     // Use BranchProbability to compute a minimum frequency based on
     // function entry baseline frequency. Loops with headers below this
if (LoopUnswitchWithBlockFrequency && EnabledPGO) {
     // loop (loopHeader in this case since inner loops should be
     // processed before outer loop). If it is less than ColdFrequency,
     // we should not unswitch.
     BlockFrequency LoopEntryFreq = BFI.getBlockFreq(loopHeader);
     if (LoopEntryFreq < ColdEntryFreq)
       return false;
   }
 
+  bool SanitizingMemory = currentLoop->getHeader()->getParent()->hasFnAttribute(
+      Attribute::SanitizeMemory);
+
   // Loop over all of the basic blocks in the loop.  If we find an interior
   // block that is branching on a loop-invariant condition, we can unswitch this
   // loop.
   for (Loop::block_iterator I = currentLoop->block_begin(),
          E = currentLoop->block_end(); I != E; ++I) {
     TerminatorInst *TI = (*I)->getTerminator();
+
+    // Unswitching on a potentially uninitialized predicate is not
+    // MSan-friendly. Limit this to the cases when the original predicate is
+    // guaranteed to execute, to avoid creating a use-of-uninitialized-value
+    // in the code that did not have one.
+    // This is a workaround for the discrepancy between LLVM IR and MSan
+    // semantics. See PR28054 for more details.
+    if (SanitizingMemory &&
+        !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo))
+      continue;
+
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       // If this isn't branching on an invariant condition, we can't unswitch
       // it.
       if (BI->isConditional()) {
         // See if this, or some part of it, is loop invariant.  If so, we can
         // unswitch on it if we desire.
         Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
                                                currentLoop, Changed);

test/Transforms/LoopUnswitch/msan.ll

+; RUN: opt < %s -loop-unswitch -verify-loop-info -S < %s 2>&1 | FileCheck %s
+
+@sink = global i32 0, align 4
+@y = global i64 0, align 8
+
+; The following is approximately:
+; void f(bool x, int p, int q) {
+;   volatile bool x2 = x;
+;   for (int i = 0; i < 1; ++i) {
+;     if (x2) {
+;       if (y)
+;         sink = p;
+;       else
+;         sink = q;
+;     }
+;   }
+; }
+; With MemorySanitizer, the loop can not be unswitched on "y", because "y" could
+; be uninitialized when x == false.
+; Test that the branch on "y" is inside the loop (after the first unconditional
+; branch).
+
+define void @may_not_execute(i1 zeroext %x, i32 %p, i32 %q) sanitize_memory {
+; CHECK-LABEL: @may_not_execute(
+entry:
+; CHECK: %[[Y:.*]] = load i64, i64* @y, align 8
+; CHECK: %[[YB:.*]] = icmp eq i64 %[[Y]], 0
+; CHECK-NOT: br i1
+; CHECK: br label
+; CHECK: br i1 %[[YB]]
+
+  %x2 = alloca i8, align 1
+  %frombool1 = zext i1 %x to i8
+  store volatile i8 %frombool1, i8* %x2, align 1
+  %0 = load i64, i64* @y, align 8
+  %tobool3 = icmp eq i64 %0, 0
+  br label %for.body
+
+for.body:
+  %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %x2.0. = load volatile i8, i8* %x2, align 1
+  %tobool2 = icmp eq i8 %x2.0., 0
+  br i1 %tobool2, label %for.inc, label %if.then
+
+if.then:
+  br i1 %tobool3, label %if.else, label %if.then4
+
+if.then4:
+  store volatile i32 %p, i32* @sink, align 4
+  br label %for.inc
+
+if.else:
+  store volatile i32 %q, i32* @sink, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.01, 1
+  %cmp = icmp slt i32 %inc, 1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+
+; The same as above, but "y" is a function parameter instead of a global.
+; This shows that it is not enough to suppress hoisting of load instructions,
+; the actual problem is in the speculative branching.
+
+define void @may_not_execute2(i1 zeroext %x, i1 zeroext %y, i32 %p, i32 %q) sanitize_memory {
+; CHECK-LABEL: @may_not_execute2(
+entry:
+; CHECK-NOT: br i1
+; CHECK: br label
+; CHECK: br i1 %y,
+  %x2 = alloca i8, align 1
+  %frombool2 = zext i1 %x to i8
+  store volatile i8 %frombool2, i8* %x2, align 1
+  br label %for.body
+
+for.body:
+  %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %x2.0. = load volatile i8, i8* %x2, align 1
+  %tobool3 = icmp eq i8 %x2.0., 0
+  br i1 %tobool3, label %for.inc, label %if.then
+
+if.then:
+  br i1 %y, label %if.then5, label %if.else
+
+if.then5:
+  store volatile i32 %p, i32* @sink, align 4
+  br label %for.inc
+
+if.else:
+  store volatile i32 %q, i32* @sink, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.01, 1
+  %cmp = icmp slt i32 %inc, 1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+
+; The following is approximately:
+; void f(bool x, int p, int q) {
+;   volatile bool x2 = x;
+;   for (int i = 0; i < 1; ++i) {
+;     if (y)
+;       sink = p;
+;     else
+;       sink = q;
+;   }
+; }
+; "if (y)" is guaranteed to execute; the loop can be unswitched.
+
+define void @must_execute(i1 zeroext %x, i32 %p, i32 %q) sanitize_memory {
+; CHECK-LABEL: @must_execute(
+entry:
+; CHECK:       %[[Y:.*]] = load i64, i64* @y, align 8
+; CHECK-NEXT:  %[[YB:.*]] = icmp eq i64 %[[Y]], 0
+; CHECK-NEXT:  br i1 %[[YB]],
+
+  %x2 = alloca i8, align 1
+  %frombool1 = zext i1 %x to i8
+  store volatile i8 %frombool1, i8* %x2, align 1
+  %0 = load i64, i64* @y, align 8
+  %tobool2 = icmp eq i64 %0, 0
+  br label %for.body
+
+for.body:
+  %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  br i1 %tobool2, label %if.else, label %if.then
+
+if.then:
+  store volatile i32 %p, i32* @sink, align 4
+  br label %for.inc
+
+if.else:
+  store volatile i32 %q, i32* @sink, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.01, 1
+  %cmp = icmp slt i32 %inc, 1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}