[LLVMdev] Curiosity about transform changes under Sanitizers (Was: [PATCH] Disable branch folding with MemorySanitizer)
Hal Finkel
hfinkel at anl.gov
Tue Nov 19 10:27:35 PST 2013
----- Original Message -----
> From: "David Blaikie" <dblaikie at gmail.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Kostya Serebryany" <kcc at google.com>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Tuesday, November 19, 2013 12:19:46 PM
> Subject: Re: [LLVMdev] Curiosity about transform changes under Sanitizers (Was: [PATCH] Disable branch folding with
> MemorySanitizer)
>
>
>
>
>
>
>
> 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.
This is a good point. It is more like:
int i = g;
return cond ? i : 0;
-Hal
>
>
> }
>
> 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
>
>
--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
More information about the llvm-dev
mailing list