[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 11:21:33 PDT 2020
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/ba70dfcc/attachment-0001.html>
More information about the llvm-dev
mailing list