Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -398,6 +398,10 @@ /// 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 findDefsUsedOutsideOfLoop(Loop *L); Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -86,9 +86,6 @@ 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, @@ -737,9 +734,9 @@ 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, + const DominatorTree *DT, const Loop *CurLoop, + const LICMSafetyInfo *SafetyInfo) { // 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 Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -188,6 +188,8 @@ 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. @@ -431,6 +433,9 @@ currentLoop = L; Function *F = currentLoop->getHeader()->getParent(); + if (F->hasFnAttribute(Attribute::SanitizeMemory)) + computeLICMSafetyInfo(&SafetyInfo, L); + EnabledPGO = F->getEntryCount().hasValue(); if (LoopUnswitchWithBlockFrequency && EnabledPGO) { @@ -524,12 +529,26 @@ 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(TI)) { // If this isn't branching on an invariant condition, we can't unswitch // it. Index: test/Transforms/LoopUnswitch/msan.ll =================================================================== --- /dev/null +++ test/Transforms/LoopUnswitch/msan.ll @@ -0,0 +1,153 @@ +; 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 +}