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

Evgeniy Stepanov
2013-11-19T18:57:19Z

On Tue, Nov 19, 2013 at 10:27 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> ----- 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;

And that becomes a data race.

>
>  -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).

What you suggest is effectively reverting unwanted transformations in
TSan instrumentation pass, instead of disabling them. This is not
always possible, because some of them lose information about the
intent of the original code. As in your example, load as part of a ?:
subexpression that is not evaluated is ok; hoisting that load into a
separate statement creates a data race; both are presented to TSan as
identical IR. Similar examples could be made for load widening
(harmful for both ASan and TSan), etc.

Looks like the only _really_ correct way of doing it is with some kind
of help from the frontend. It may also improve speed by excluding
checks that don't make sense or are trivially false in the context of
the source language.

>>
>> -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
>>
>>