[LLVMdev] Curiosity about transform changes under Sanitizers (Was: [PATCH] Disable branch folding with MemorySanitizer)

Kostya Serebryany
2013-11-19T17:58:53Z

On Tue, Nov 19, 2013 at 9:56 PM, Kuperstein, Michael M <
michael.m.kuperstein at intel.com> wrote:

>  What I’m trying to say is that according to my understanding of the
> C++11 memory model, even in that small reproducer, the store to g and the
> load from g are in fact a data race.
>
> (This is regardless of the fact the load is protected by a branch that is
> not taken.)
>

My understanding of the standard is quite the opposite.


>
>
> *From:* Kostya Serebryany [mailto:kcc at google.com]
> *Sent:* Tuesday, November 19, 2013 19:46
> *To:* Kuperstein, Michael M
> *Cc:* Evgeniy Stepanov; LLVM Developers Mailing List
>
> *Subject:* Re: [LLVMdev] Curiosity about transform changes under
> Sanitizers (Was: [PATCH] Disable branch folding with MemorySanitizer)
>
>
>
>
>
>
>
> On Tue, Nov 19, 2013 at 9:05 PM, Kuperstein, Michael M <
> michael.m.kuperstein at intel.com> wrote:
>
> My $0.02 - I'm not sure the transformation introduces a data race.
>
> To the best of my understanding, the point of the C++11/C11 memory model
> is to allow a wide array of compiler transformations - including
> speculative loads - for non-atomic variables.
> I believe what's most likely happening (without looking at the Mozilla
> source) is that the original program contains a C++ data race, and the
> transformation exposes it to TSan.
>
>
>
> The original program is race-free.
>
> I've posted a minimized reproducer that actually triggers a tsan false
> positive at O1 here:
>
> https://code.google.com/p/thread-sanitizer/issues/detail?id=40#c5
>
>
>
>
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On
> Behalf Of Evgeniy Stepanov
> Sent: Tuesday, November 19, 2013 18:55
> To: Kostya Serebryany
> Cc: LLVM Developers Mailing List
> Subject: Re: [LLVMdev] Curiosity about transform changes under Sanitizers
> (Was: [PATCH] Disable branch folding with MemorySanitizer)
>
> The root cause of those issues is the fact that sanitizers verify
> C++-level semantics with LLVM IR level instrumentation. For example,
> speculative loads are OK in IR if it can be proved that the load won't
> trap, but in C++ it would be a data race.
>
>
> On Tue, Nov 19, 2013 at 8:38 PM, Kostya Serebryany <kcc at
google.com> wrote:
> >
> >
> >
> > On Tue, Nov 19, 2013 at 8:25 PM, David Blaikie <dblaikie at
gmail.com>
> wrote:
> >>
> >> Just moving this branch of the thread out of the review because I
> >> don't want to derail the review  thread...
> >>
> >> Kostya - why are these two cases not optimization bugs in general?
> >> (why do they only affect sanitizers?)
> >
> >
> > The recent case from mozilla
> > (https://code.google.com/p/thread-sanitizer/issues/detail?id=40#c2) is
> > a legal optimization -- it hoists a safe load (i.e. a load which is
> > known not to
> > fail) out of conditional branch.
> > It reduces the number of basic blocks and branches, and so I think
> > it's good in general.
> > I can't imagine a case where this optimization will break a valid
> program.
> > Which is the second one you are referring to?
> >
> > --kcc
> >
> >>
> >>
> >>
> >>
> >> On Mon, Nov 18, 2013 at 8:37 PM, Kostya Serebryany <kcc at
google.com>
> wrote:
> >>>
> >>> And we've been just informed by the mozilla folks about
yet another
> >>> case of optimization being hostile to sanitizers:
> >>> hoisting a safe load out of conditional branch introduces a
race
> >>> which tsan happily reports.
> >>>
https://code.google.com/p/thread-sanitizer/issues/detail?id=40#c2
> >>>
> >>> --kcc
> >>>
> >>>
> >>> On Tue, Nov 19, 2013 at 8:06 AM, Kostya Serebryany <kcc at
google.com>
> >>> wrote:
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> On Tue, Nov 19, 2013 at 1:27 AM, David Blaikie
<dblaikie at gmail.com>
> >>>> wrote:
> >>>>>
> >>>>> Do we have precedence for this kind of change (where
sanitizers
> >>>>> affect optimizations in arbitrary internal ways - not
simply by
> >>>>> enabling/disabling certain passes)?
> >>>>
> >>>>
> >>>> Yes. AddressSanitizer and ThreadSanitizer disable load
widening
> >>>> that would create a partially out-of-bounds or a racy
access.
> >>>> See lib/Analysis/MemoryDependenceAnalysis.cpp (search for
> >>>> Attribute::SanitizeAddress and Attribute::SanitizeThread).
> >>>> This case with MemorySanitizer is slightly different
because we are
> >>>> not fighting a false positive, but rather a
debug-info-damaging
> optimization.
> >>>>
> >>>> --kcc
> >>>>
> >>>>>
> >>>>> If not, does this need some deeper discussion about
alternatives
> >>>>> (is it important that we be able to produce equivalent
code
> >>>>> without the sanitizers enabled?)?
> >>>>>
> >>>>>
> >>>>> On Mon, Nov 18, 2013 at 7:02 AM, Evgeniy Stepanov
> >>>>> <eugenis at google.com>
> >>>>> wrote:
> >>>>>>
> >>>>>> Branch folding optimization often leads to
confusing MSan reports
> >>>>>> due to lost debug info.
> >>>>>> For example,
> >>>>>> 1: if (x < 0)
> >>>>>> 2:   if (y < 0)
> >>>>>> 3:    do_something();
> >>>>>> is transformed into something like
> >>>>>>   %0 = and i32 %y, %x
> >>>>>>   %1 = icmp slt i32 %0, 0
> >>>>>>   br i1 %1, label %if.then2, label %if.end3 where
all 3
> >>>>>> instructions are associated with line 1.
> >>>>>>
> >>>>>> This patch disables folding of conditional
branches in functions
> >>>>>> with sanitize_memory attribute.
> >>>>>>
> >>>>>> http://llvm-reviews.chandlerc.com/D2214
> >>>>>>
> >>>>>> Files:
> >>>>>>   lib/Transforms/Utils/SimplifyCFG.cpp
> >>>>>>   test/Transforms/SimplifyCFG/branch-fold-msan.ll
> >>>>>>
> >>>>>> Index: lib/Transforms/Utils/SimplifyCFG.cpp
> >>>>>>
================================================================>
>>>>>> => >>>>>> ---
lib/Transforms/Utils/SimplifyCFG.cpp
> >>>>>> +++ lib/Transforms/Utils/SimplifyCFG.cpp
> >>>>>> @@ -1967,6 +1967,13 @@
> >>>>>>  bool llvm::FoldBranchToCommonDest(BranchInst *BI)
{
> >>>>>>    BasicBlock *BB = BI->getParent();
> >>>>>>
> >>>>>> +  // This optimization results in confusing
MemorySanitizer
> reports.
> >>>>>> Use of
> >>>>>> +  // uninitialized value in this branch
instruction is reported
> >>>>>> + with
> >>>>>> the
> >>>>>> +  // predecessor's debug location.
> >>>>>> +  if
(BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory) &&
> >>>>>> +      BI->isConditional())
> >>>>>> +    return false;
> >>>>>> +
> >>>>>>    Instruction *Cond = 0;
> >>>>>>    if (BI->isConditional())
> >>>>>>      Cond =
dyn_cast<Instruction>(BI->getCondition());
> >>>>>> Index:
test/Transforms/SimplifyCFG/branch-fold-msan.ll
> >>>>>>
================================================================>
>>>>>> => >>>>>> ---
test/Transforms/SimplifyCFG/branch-fold-msan.ll
> >>>>>> +++
test/Transforms/SimplifyCFG/branch-fold-msan.ll
> >>>>>> @@ -0,0 +1,29 @@
> >>>>>> +; RUN: opt < %s -simplifycfg -S | FileCheck %s
> >>>>>> +
> >>>>>> +declare void @callee()
> >>>>>> +
> >>>>>> +; Test that conditional branches are not folded
with
> sanitize_memory.
>
> >>>>>> +define void @caller(i32 %x, i32 %y)
sanitize_memory { ; CHECK:
> >>>>>> +define void @caller(i32 [[X:%.*]], i32 [[Y:%.*]])
; CHECK: icmp
> >>>>>> +slt i32 {{.*}}[[X]] ; CHECK: icmp slt i32
{{.*}}[[Y]] ; CHECK:
> >>>>>> +ret void
>
> >>>>>> +
> >>>>>> +entry:
> >>>>>> +  %cmp = icmp slt i32 %x, 0
> >>>>>> +  br i1 %cmp, label %if.then, label %if.end3
> >>>>>> +
> >>>>>> +if.then:
; preds = %entry
> >>>>>> +  %cmp1 = icmp slt i32 %y, 0
> >>>>>> +  br i1 %cmp1, label %if.then2, label %if.end
> >>>>>> +
> >>>>>> +if.then2:
; preds > %if.then
> >>>>>> +  call void @callee()
> >>>>>> +  br label %if.end
> >>>>>> +
> >>>>>> +if.end:
; preds > >>>>>> %if.then2, %if.then
> >>>>>> +  br label %if.end3
> >>>>>> +
> >>>>>> +if.end3:
; preds > %if.end,
> >>>>>> %entry
> >>>>>> +  ret void
> >>>>>> +}
> >>>>>>
> >>>>>> _______________________________________________
> >>>>>> llvm-commits mailing list
> >>>>>> llvm-commits at cs.uiuc.edu
> >>>>>>
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
> >>>>>>
> >>>>>
> >>>>>
> >>>>> _______________________________________________
> >>>>> llvm-commits mailing list
> >>>>> llvm-commits at cs.uiuc.edu
> >>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
> >>>>>
> >>>>
> >>>
> >>
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
>
>
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131119/cc6e567d/attachment.html>