[llvm-dev] clang10 mis-compiles simple C program transpiled from brainfxxk
Alina Sbirlea via llvm-dev
llvm-dev at lists.llvm.org
Fri Oct 23 15:48:09 PDT 2020
Hi Haoran,
Yes, you're right, the instances you added in the patch can also pass along
the AAQI param.
Do you have commit access to check in this change or should I do it on your
behalf?
The fix Nikita proposed (https://reviews.llvm.org/D90066) should resolve
the original issue in AA and BatchAA, but please let us know if you're
still seeing it with this patch.
Best,
Alina
On Fri, Oct 23, 2020 at 1:25 PM Haoran Xu <haoranxu510 at gmail.com> wrote:
> Hi Alina,
>
> Thanks for your reply! That makes sense to me.
> Regarding the other point I mentioned (the missing AAQI parameters in some
> of the function calls), do you think they make sense, or is it intentional
> that you use the non-batchAA version there?
> My current understanding is that changing them to use BatchAA might expose
> more issues that triggers the `isValueEqualInPotentialCycles` bug, but if
> you have the bug fixed, make them use BatchAA as well could probably
> improve performance a bit.
>
> Best,
> Haoran
>
> Alina Sbirlea <asbirlea at google.com> 于2020年10月23日周五 上午11:21写道：
>
>> Some clarifications to the description in https://reviews.llvm.org/D89991
>> :
>> The clearing of the cache is not supposed to be done in BatchAA. The
>> patch introducing BatchAA was not a refactoring patch, and it did not
>> accidentally miss the lines to clear those caches.
>>
>> Nikita flagged the issue and I looked into it. The condition that's
>> broken in BatchAA is the `isValueEqualInPotentialCycles`. This condition
>> can be satisfied in a query and a result cached, but the condition broken
>> in a subsequent query. Working out a fix is not straightforward.
>> Yes, clearing the whole cache is a big hammer we can use, and, yes, it
>> will lose all the performance benefits.
>>
>> For visibility, I uploaded a WIP fix:
>> https://reviews.llvm.org/D90062
>> There are still problems I have yet to solve in the above patch, hence
>> the lack of reviewers. However, please feel free to test it and let me know
>> if it resolves your failure.
>>
>> Best,
>> Alina
>>
>>
>> On Thu, Oct 22, 2020 at 6:47 AM Haoran Xu <haoranxu510 at gmail.com> wrote:
>>
>>> I don't know anything about LLVM internals, but solely from the commit
>>> message of your diff I think it's very likely.
>>> So my current understanding is that the ``shrink_and_clear()`` is
>>> required to produce correct aliasing result, but if we naively do it for
>>> AAQI (as my patch proposed), we probably lose most of the performance
>>> benefits of BatchedAA.
>>>
>>> However, this is only my understanding after spending 2 hours reading
>>> the code from zero background knowledge, so I guess I can't say much about
>>> it.
>>>
>>>
>>> Nikita Popov <nikita.ppv at gmail.com> 于2020年10月22日周四 上午6:41写道：
>>>
>>>> I suspect that you found the same issue as
>>>> https://github.com/llvm/llvm-project/commit/ddd0f083184feb489684f87cf28d5eb10e0a244e.
>>>> We're trying to find a solution to that, but it's not entirely simple.
>>>>
>>>> Nikita
>>>>
>>>> On Thu, Oct 22, 2020 at 3:33 PM Haoran Xu via llvm-dev <
>>>> llvm-dev at lists.llvm.org> wrote:
>>>>
>>>>> I managed to bisected out the diff introducing the bug:
>>>>> https://github.com/llvm/llvm-project/commit/bfc779e491099213d74c057b5727bde976c7ba02
>>>>>
>>>>> And I managed to figured out a fix: it seems (to me) that the diff is
>>>>> mostly a code refactoring diff, but the author accidentally removed two
>>>>> lines of functional logic, resulting in the bug.
>>>>> After adding the two lines back, the miscompiled code works fine now.
>>>>> However, I'm not certain of the performance implications of clearing the
>>>>> whole AAQI.
>>>>>
>>>>>> diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
>>>>>> b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
>>>>>> index 232132958f7..9a8ca46093d 100644
>>>>>> --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
>>>>>> +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
>>>>>> @@ -836,6 +836,8 @@ AliasResult BasicAAResult::alias(const
>>>>>> MemoryLocation &LocA,
>>>>>> AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags,
>>>>>> LocB.Ptr,
>>>>>> LocB.Size, LocB.AATags, AAQI);
>>>>>>
>>>>>> + AAQI.AliasCache.shrink_and_clear();
>>>>>> + AAQI.IsCapturedCache.shrink_and_clear();
>>>>>> VisitedPhiBBs.clear();
>>>>>> return Alias;
>>>>>> }
>>>>>>
>>>>>
>>>>> I also noticed that the author forgot to change a few function calls
>>>>> to use his new API, but I'm not sure if it is a correctness issue or not.
>>>>> At least it's not causing the brainfxxk code miscompilation.
>>>>>
>>>>>> diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp
>>>>>> b/llvm/lib/Analysis/AliasAnalysis.cpp
>>>>>> index 06a33f659c1..94a9d12eb17 100644
>>>>>> --- a/llvm/lib/Analysis/AliasAnalysis.cpp
>>>>>> +++ b/llvm/lib/Analysis/AliasAnalysis.cpp
>>>>>> @@ -231,7 +231,7 @@ ModRefInfo AAResults::getModRefInfo(const
>>>>>> CallBase *Call,
>>>>>>
>>>>>> // If Loc is a constant memory location, the call definitely could
>>>>>> not
>>>>>> // modify the memory location.
>>>>>> - if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/
>>>>>> false))
>>>>>> + if (isModSet(Result) && pointsToConstantMemory(Loc, AAQI,
>>>>>> /*OrLocal*/ false))
>>>>>> Result = clearMod(Result);
>>>>>>
>>>>>> return Result;
>>>>>> @@ -308,7 +308,7 @@ ModRefInfo AAResults::getModRefInfo(const
>>>>>> CallBase *Call1,
>>>>>>
>>>>>> // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and
>>>>>> we use
>>>>>> // above ArgMask to update dependence info.
>>>>>> - ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc);
>>>>>> + ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc, AAQI);
>>>>>> ArgMask = intersectModRef(ArgMask, ModRefC1);
>>>>>>
>>>>>> // Conservatively clear IsMustAlias unless only MustAlias is
>>>>>> found.
>>>>>> @@ -349,7 +349,7 @@ ModRefInfo AAResults::getModRefInfo(const
>>>>>> CallBase *Call1,
>>>>>> // might Mod Call1ArgLoc, then we care about either a Mod or a
>>>>>> Ref by
>>>>>> // Call2. If Call1 might Ref, then we care only about a Mod by
>>>>>> Call2.
>>>>>> ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
>>>>>> - ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc);
>>>>>> + ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc, AAQI);
>>>>>> if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
>>>>>> (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
>>>>>> R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
>>>>>>
>>>>>
>>>>> I'll submit a patch for review, but I would really appreciate any
>>>>> comments here as well.
>>>>>
>>>>> Thanks.
>>>>>
>>>>> Best,
>>>>> Haoran
>>>>>
>>>>> Haoran Xu <haoranxu510 at gmail.com> 于2020年10月22日周四 上午12:12写道：
>>>>>
>>>>>> Hi David,
>>>>>>
>>>>>> I just tried creduce, but it generated a code with completely
>>>>>> undefined behavior (out of range accesses, etc).
>>>>>> The "interesting" criteria I used is "timeout in -O1 but finishes in
>>>>>> 20s in -O0". However, it turns out that the undefined behavior in
>>>>>> creduce-generated code just makes the criteria "happens to" pass.
>>>>>>
>>>>>> Best,
>>>>>> Haoran
>>>>>>
>>>>>> Haoran Xu <haoranxu510 at gmail.com> 于2020年10月21日周三 下午10:32写道：
>>>>>>
>>>>>>> I was just able to determine the offending IR code before and after
>>>>>>> the transformation. I'm now almost certain it's a bug in LLVM.
>>>>>>>
>>>>>>> Before transformation, we have the following IR (I renamed all %xxx
>>>>>>> for brevity):
>>>>>>>
>>>>>>>> %1 = load i8, i8* %0, align 1
>>>>>>>> %2 = add i8 %1, -1
>>>>>>>> store i8 %2, i8* %0, align 1
>>>>>>>>
>>>>>>> The above IR is inside a loop, so the value in %0 can be different
>>>>>>> in each run.
>>>>>>>
>>>>>>> The optimization pass changed the IR above to the following:
>>>>>>>
>>>>>>>> store i8 %3, i8* %0, align 1
>>>>>>>>
>>>>>>> where %3 is defined by
>>>>>>>
>>>>>>>> %4 = load i8, i8* %0, align 1
>>>>>>>> %3 = add i8 %4, -1
>>>>>>>>
>>>>>>> in an earlier piece of IR.
>>>>>>>
>>>>>>> Apparently the pass treated %3 the same thing as %2 and it fired
>>>>>>> CSE, without realizing that the content in %0 may have been changed by the
>>>>>>> loop.
>>>>>>>
>>>>>>>
>>>>>>> David Blaikie <dblaikie at gmail.com> 于2020年10月21日周三 下午10:18写道：
>>>>>>>
>>>>>>>> Might be worth running the c source file through creduce or similar
>>>>>>>> to narrow it down a bit that way too.
>>>>>>>>
>>>>>>>> On Wed, Oct 21, 2020 at 9:12 PM Haoran Xu via llvm-dev <
>>>>>>>> llvm-dev at lists.llvm.org> wrote:
>>>>>>>>
>>>>>>>>> A further bisect using opt's -opt-bisect-limit option shows that
>>>>>>>>> the following pass is causing the issue:
>>>>>>>>>
>>>>>>>>>> BISECT: running pass (39) Early CSE w/ MemorySSA on function
>>>>>>>>>> (main)
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Haoran Xu <haoranxu510 at gmail.com> 于2020年10月21日周三 下午9:00写道：
>>>>>>>>>
>>>>>>>>>> I did a simple bisect on clang version, and it seems like clang
>>>>>>>>>> 8.0.0 works correctly, but clang 9.0.0 failed to compile the code correctly.
>>>>>>>>>> https://godbolt.org/z/676Grr <- if you change the clang version
>>>>>>>>>> to 8.0.0, you will see the expected output in 'output' section.
>>>>>>>>>> I don't have the ability to bisect on clang git history. I would
>>>>>>>>>> greatly appreciate it if any one is willing to do that.
>>>>>>>>>>
>>>>>>>>>> Thanks!
>>>>>>>>>>
>>>>>>>>>> Haoran Xu <haoranxu510 at gmail.com> 于2020年10月21日周三 下午8:47写道：
>>>>>>>>>>
>>>>>>>>>>> Hello,
>>>>>>>>>>>
>>>>>>>>>>> I'm really amazed to find out that under -O3, a simple piece of
>>>>>>>>>>> C code generated from a brainfxxk-to-C transpiler is miscompiled.
>>>>>>>>>>> As one probably know, the C code transpiled from brainfxxk only
>>>>>>>>>>> contains 3 kind of statements:
>>>>>>>>>>>
>>>>>>>>>>>> (1) ++(*ptr) / --(*ptr)
>>>>>>>>>>>> (2) ++ptr / --ptr
>>>>>>>>>>>> (3) while (*ptr) { ... }
>>>>>>>>>>>>
>>>>>>>>>>> where ptr is a uint8_t*.
>>>>>>>>>>> So it seems very clear to me that the code contains no undefined
>>>>>>>>>>> behavior (the pointer is uint8_t* and unsigned integer overflow is not UD).
>>>>>>>>>>>
>>>>>>>>>>> After further investigation, it seems like clang compiled this
>>>>>>>>>>> loop:
>>>>>>>>>>>
>>>>>>>>>>>> while (*ptr) {
>>>>>>>>>>>> --(*ptr);
>>>>>>>>>>>> ++ptr;
>>>>>>>>>>>> ++(*ptr);
>>>>>>>>>>>> --ptr;
>>>>>>>>>>>> }
>>>>>>>>>>>>
>>>>>>>>>>> to an unconditional infinite loop under -O3, resulting in the
>>>>>>>>>>> bug. The code snippet above seems completely benign to me.
>>>>>>>>>>>
>>>>>>>>>>> I attached the offending program. With
>>>>>>>>>>>
>>>>>>>>>>>> clang a.c -O0
>>>>>>>>>>>>
>>>>>>>>>>> it worked fine (it should print out an ASCII-art picture of
>>>>>>>>>>> mandelbrot fracture). However, with -O1 or -O3, it goes into a dead loop
>>>>>>>>>>> (in the code snippet above) after printing out a few characters.
>>>>>>>>>>>
>>>>>>>>>>> I also tried UndefinedBehaviorSanitizer. Strangely, when
>>>>>>>>>>> compiling using
>>>>>>>>>>>
>>>>>>>>>>>> clang a.c -O3 -fsanitize=undefined
>>>>>>>>>>>>
>>>>>>>>>>> the code worked again, with no infinite loop, and no undefined
>>>>>>>>>>> behavior reported.
>>>>>>>>>>>
>>>>>>>>>>> So it seems to me a LLVM optimizer bug. I would greatly
>>>>>>>>>>> appreciate if any one is willing to investigate.
>>>>>>>>>>>
>>>>>>>>>>> Best,
>>>>>>>>>>> Haoran
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> _______________________________________________
>>>>>>>>> LLVM Developers mailing list
>>>>>>>>> llvm-dev at lists.llvm.org
>>>>>>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>>>>
>>>>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> llvm-dev at lists.llvm.org
>>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>
>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201023/b112b27b/attachment-0001.html>
More information about the llvm-dev
mailing list