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

David Blaikie
2013-11-19T18:19:46Z

On Tue, Nov 19, 2013 at 10:08 AM, Hal Finkel <hfinkel at anl.gov> wrote:

> ----- Original Message -----
> > From: "Kostya Serebryany" <kcc at google.com>
> > To: "Michael M Kuperstein" <michael.m.kuperstein at
intel.com>
> > Cc: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>
> > Sent: Tuesday, November 19, 2013 11:45:39 AM
> > 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
> >
> >
>
> Here's my problem:
>
> int g;
> int foo(int cond) {
>   if (cond)
>     return g;
>   return 0;
> }
>
> is being transformed into this (at the IR level):
>
> int g;
> int foo(int cond) {
>   return cond ? g : 0;
>

This doesn't have the same semantics as the IR transformed 'select',
though, does it?

In IR 'g' is unconditionally loaded before the select. In C++,
'g' is
completely unevaluated if 'cond' is false.


> }
>
> but I could have just as easily made that transformation at the C++ level
> as well, and I don't see that as introducing a data race here (in
> practice). When you have a load that is used only conditionally, TSAN
> should only record it when the condition is true. IMHO, to do otherwise, is
> a bug in TSAN. Furthermore, if you try and do this by disabling all
> optimizations that transform conditionally-executed blocks into selects,
> you'll have a lot more work to do (because you'll also need to
handle every
> place in the backend that does if conversion).
>
>  -Hal
>
> >
> >
> >
> >
> > -----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.
> >
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131119/833989b2/attachment.html>