Page MenuHomePhabricator

[TRE] allow TRE for non-capturing calls.
ClosedPublic

Authored by avl on Jun 18 2020, 5:27 AM.

Details

Summary

The current implementation of Tail Recursion Elimination has a very restricted
pre-requisite: AllCallsAreTailCalls. i.e. it requires that no function
call receives a pointer to local stack. Generally, function calls that
receive a pointer to local stack but do not capture it - should not
break TRE. This fix allows us to do TRE if it is proved that no pointer
to the local stack is escaped. To make sure whether pointer escaped or not,
it examines called function.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
avl added a comment.Jun 18 2020, 2:15 PM

It makes sense to teach tail recursion elimination not to depend so heavily on tail markings. But I don't think that implies we want to mess with the markings themselves.

Ok. Thus I need to drop part of this patch related to more strict tail marking, and continue with part which changes pre-requisite for TRE.

avl updated this revision to Diff 272378.Jun 22 2020, 3:57 AM
  1. deleted code doing more strict tailcall marking.
  2. left removal of "AllCallsAreTailCalls".
  3. added check for non-capturing calls while tracking alloca.
  4. re-titled the patch.
avl retitled this revision from [TRE] markTails marks call sites as tailcalls though some of them are not. to [TRE] allow TRE for non-capturing calls..Jun 22 2020, 3:58 AM
avl edited the summary of this revision. (Show Details)
avl added a subscriber: lxfind.Jun 22 2020, 4:01 AM
efriedma added inline comments.Jun 22 2020, 1:00 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
145

Please don't add code to examine the callee; if we're not deducing nocapture appropriately, we should fix that elsewhere.

332

What is the new handling for lifetime.end/assume doing?

830

Do you have to redo the AllocaDerivedValueTracker analysis? Is it not enough that the call you're trying to TRE is marked "tail"?

857

I thought we had some tests where we TRE in the presence of recursive calls, like a simple recursive fibonacci. Am I misunderstanding this?

avl marked 4 inline comments as done.Jun 22 2020, 2:23 PM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
145

Ok.

332

They are just skipped. In following test case:

call void @_Z5test5i(i32 %sub)
call void @llvm.lifetime.end.p0i8(i64 24, i8* nonnull %1) #5
call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %0) #5
br label %return

they are generated in between call and ret. It is safe to ignore them while checking whether transformation is possible.

830

Do you have to redo the AllocaDerivedValueTracker analysis?

AllocaDerivedValueTracker analysis(done in markTails) could be reused here.
But marking, done in markTails(), looks like separate tasks. i.e. it is better
to make TRE not depending on markTails(). There is a review for this - https://reviews.llvm.org/D60031
Thus such separation looks useful(To not reuse result of markTails but have it computed inplace).

Is it not enough that the call you're trying to TRE is marked "tail"?

It is not enough that call which is subject to TRE is marked "Tail".
It also should be checked that other calls does not capture pointer to local stack:

// do not do TRE if any pointer to local stack has escaped.
if (!Tracker.EscapePoints.empty())
   return false;
857

right, there is a testcase for fibonacchi:

llvm/test/Transforms/TailCallElim/accum_recursion.ll:@test3_fib

areAllLastFuncCallsRecursive() checking works well for fibonacci testcase:

return fib(x-1)+fib(x-2);

Since, Last funcs call chain is : fib()->fib()->ret.
That check should prevent from such cases:

return fib(x-1)+another_call()+fib(x-2);
efriedma added inline comments.Jun 22 2020, 2:48 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

It is not enough that call which is subject to TRE is marked "Tail". It also should be checked that other calls does not capture pointer to local stack:

If there's an escaped pointer to the local stack, we wouldn't infer "tail" in the first place, would we?

857

That check should prevent from such cases: return fib(x-1)+another_call()+fib(x-2);

Why do we need to prevent this?

laytonio added inline comments.Jun 22 2020, 3:05 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
828

There is no need to pass the function here since its a member variable.

hiraditya added inline comments.Jun 22 2020, 3:52 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
806

can we use isa<> here?

821

CI->getCalledFunction() != &F seems cheaper than canMoveAboveCall

845

Do we need to visit all the instructions twice?

avl marked 3 inline comments as done.Jun 22 2020, 4:15 PM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
828

Ok.

830

If function receives pointer to alloca then it would not be marked with "Tail". Then we do not have a possibility to understand whether this function receives pointer to alloca but does not capture it:

void test(int recurseCount)
{
    if (recurseCount == 0) return;
    int temp = 10;
    globalIncrement(&temp);
    test(recurseCount - 1);
}

test - marked with Tail.
globalIncrement - not marked with Tail. But TRE could be done since it does not capture pointer. But if it will capture the pointer then we could not do TRE. So we need to check !Tracker.EscapePoints.empty().

857

We do not. I misunderstood the canTransformAccumulatorRecursion(). That check could be removed.

efriedma added inline comments.Jun 22 2020, 6:14 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

test - marked with Tail.

For the given code, TRE won't mark the recursive call "tail". That transform isn't legal: the recursive call could access the caller's version of "temp".

avl marked an inline comment as done.Jun 23 2020, 12:54 AM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

For the given code, TRE won't mark the recursive call "tail". That transform isn't legal: the recursive call could access the caller's version of "temp".

it looks like recursive call could NOT access the caller's version of "temp":

test(recurseCount - 1);

Caller`s version of temp is accessed by non-recursive call:

globalIncrement(&temp);

If globalIncrement does not capture the "&temp" then TRE looks to be legal for that case.

globalIncrement() would not be marked with "Tail". test() would be marked with Tail.

Thus the pre-requisite for TRE would be: tail-recursive call must not receive pointer to local stack(Tail) and non-recursive calls must not capture the pointer to local stack.

efriedma added inline comments.Jun 23 2020, 11:30 AM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

Can you give a complete IR example where we infer "tail", but TRE is illegal?

Can you give a complete IR example, we we don't infer "tail", but we still do the TRE transform here?

avl marked an inline comment as done.Jun 23 2020, 12:09 PM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

Can you give a complete IR example where we infer "tail", but TRE is illegal?

there is no such example. Currently all cases where we infer "tail" would be valid for TRE.

Can you give a complete IR example, we we don't infer "tail", but we still do the TRE transform here?

For the following example current code base would not infer "tail" for _Z15globalIncrementPKi and as the result would not do TRE for _Z4testi.
This patch changes this behavior: so that if _Z15globalIncrementPKi is not marked with "tail" and does not capture its pointer argument - TRE would be allowed for _Z4testi.

@count = dso_local local_unnamed_addr global i32 0, align 4

; Function Attrs: nofree noinline norecurse nounwind uwtable
define dso_local void @_Z15globalIncrementPKi(i32* nocapture readonly %param) local_unnamed_addr #0 {
entry:
  %0 = load i32, i32* %param, align 4
  %1 = load i32, i32* @count, align 4
  %add = add nsw i32 %1, %0
  store i32 %add, i32* @count, align 4
  ret void
}

; Function Attrs: nounwind uwtable
define dso_local void @_Z4testi(i32 %recurseCount) local_unnamed_addr #1 {
entry:
  %temp = alloca i32, align 4
  %cmp = icmp eq i32 %recurseCount, 0
  br i1 %cmp, label %return, label %if.end

if.end:                                           ; preds = %entry
  %0 = bitcast i32* %temp to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %0) #6
  store i32 10, i32* %temp, align 4
  call void @_Z15globalIncrementPKi(i32* nonnull %temp)
  %sub = add nsw i32 %recurseCount, -1
  call void @_Z4testi(i32 %sub)
  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %0) #6
  br label %return

return:                                           ; preds = %entry, %if.end
  ret void
}

; Function Attrs: argmemonly nounwind willreturn
declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #2

; Function Attrs: argmemonly nounwind willreturn
declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #2

attributes #0 = { nofree noinline norecurse nounwind uwtable }
attributes #1 = { nounwind uwtable }
attributes #2 = { argmemonly nounwind willreturn }
efriedma added inline comments.Jun 23 2020, 1:01 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

In your example, we don't infer "tail" for globalIncrement... but we do infer it for the recursive call to test(). I'm suggesting you could just check for "tail" on test(), instead of using AllocaDerivedValueTracker.

avl marked an inline comment as done.Jun 23 2020, 1:48 PM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

Checking only test() is not enough. There additionally should be checked globalIncrement().

It is correct that while checking test() there could be checked "Tail" flag. Which does not require using AllocaDerivedValueTracker.

But while checking globalIncrement() there should be checked whether some alloca value escaped or not. "Tail" flag could not be used for that. AllocaDerivedValueTracker allow to do such check:

Tracker.EscapePoints.empty()

If we would not do check for globalIncrement then it is not valid to do TRE. Thus it seems we need to check globalIncrement for escaping pointer and we need to use AllocaDerivedValueTracker for that.

avl updated this revision to Diff 272829.Jun 23 2020, 2:25 PM
avl edited the summary of this revision. (Show Details)

addressed comments:

  1. removed PointerMayBeCaptured() used for CalledFunction.
  2. rewrote CanTRE() to visiting instructions only once.
  3. replaced areAllLastFuncCallsRecursive() with isInTREPosition().

I did not address request for not using AllocaDerivedValueTracker yet.
Since there is open question on it. I would address it as soon as the question would be resolved.

efriedma added inline comments.Jun 23 2020, 2:41 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

Checking only test() is not enough. There additionally should be checked globalIncrement().

Can you give a complete IR example where we infer "tail", but TRE is illegal?

there is no such example. Currently all cases where we infer "tail" would be valid for TRE.

I'm not sure how to reconcile this. Are you saying we could infer "tail" in some case where TRE is illegal, but don't right now? Or are you saying that you plan to extend TRE to handle cases where we can't infer "tail" on the recursive call?

avl marked an inline comment as done.Jun 23 2020, 3:16 PM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

Or are you saying that you plan to extend TRE to handle cases where we can't infer "tail" on the recursive call?

I think not exactly. more precise would probably be : "I am saying that plan to extend TRE to handle cases where we can't infer "tail" on the NON-recursive NON-last call"

globalIncrement() is non-recursive non-last call in above example. But we need to check whether it captures argument pointer or not to decide whether it is OK to do TRE.

To make things clear - I am suggesting instead of current pre-requisite for TRE :

"All call sites are marked with Tail"

to make following:

"Recursive last calls are marked with "Tail", non-recursive non-last calls are proved to not capture alloca".

For the above example it means : the requirement for test() should stay the same(should be marked with Tail). The requirement for globalIncrement() should be "does not capture alloca".

efriedma added inline comments.Jun 23 2020, 3:30 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

"Recursive last calls are marked with 'tail'" implies "non-recursive non-last calls are proved to not capture alloca".

avl marked an inline comment as done.Jun 24 2020, 7:45 AM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
830

I see, thank you for explanations.
There is a test which makes me think that above rule is not always correct:

Transforms/TailCallElim/basic.ll:@test1

; PR615. Make sure that we do not move the alloca so that it interferes with the tail call.
define i32 @test1() {
; CHECK: i32 @test1()
; CHECK-NEXT: alloca
        %A = alloca i32         ; <i32*> [#uses=2]
        store i32 5, i32* %A
        call void @use(i32* %A)
; CHECK: tail call i32 @test1
        %X = tail call i32 @test1()             ; <i32> [#uses=1]
        ret i32 %X
}

I removed usages of AllocaDerivedValueTracker and corrected the test1 from Transforms/TailCallElim/basic.ll.

avl updated this revision to Diff 273029.Jun 24 2020, 8:14 AM

removed usages of AllocaDerivedValueTracker from canTRE().

laytonio added inline comments.Jun 24 2020, 9:06 AM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
831

You can use for (Instruction &I : instructions(F)) here.

845

Is this correct? I think we want to check these per TRE candidate in findTRECandidate, not just disable TRE in general if one is found.

avl marked an inline comment as done.Jun 24 2020, 2:29 PM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
845

I tried to minimize changes and keep old logic here - but yes, it is better to move that check into findTRECandidate(). Will do.

avl updated this revision to Diff 273174.Jun 24 2020, 3:29 PM

check valid TRE candidate into findTRECandidate()().

laytonio added inline comments.Jun 25 2020, 5:34 AM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
843

Is there any reason to find and validate candidates now only to have to redo it when we actually perform the eliminations? If so, is there any reason this needs to follow a different code path than findTRECandidate? findTRECandidate is doing the same checks, except for canMoveAboveCall and canTransformAccumulatorRecursion, which should probably be refactored into findTRECandidate from eliminateCall anyway. If not then all of this code goes away and we're left with the same canTRE as in trunk.

avl marked an inline comment as done.Jun 25 2020, 8:32 AM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
843

We are enumerating all instructions here, so we could understand if there are not TRE candidates and stop earlier. That is the reason for doing it here.

I agree that findTRECandidate should be refactored to have the same checks as here.

What do you think is better to do:

  • leave early check for TRE candidates in canTRE or remove it
  • refactor findTRECandidate or leave it as is

?

laytonio added inline comments.Jun 25 2020, 9:00 AM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
843

Yes we are iterating all the instructions here but, unless I am missing something, we would literally just be doing the checks twice for no reason. Look at it this way, best case scenario we have to check all possible candidates once, find none and we're done. Worst case, we check all possible candidates once, find one and have to check all possible candidates a second time. Where as if we remove the early checks we only ever have to check the candidates once. So we wouldn't really be stopping any earlier.

As for refactoring findTRECandidate, I do think that should be done and we should strive to move all the failure conditions out of eliminateCall in order to avoid having to fold a return only to find out we didn't need to. But, I think that is out of the scope of this change, and if we do decide to keep the early checks here then we should say that findTRECandidate does a good enough job to consider this function as having valid candidates.

avl marked an inline comment as done.Jun 25 2020, 10:22 AM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
843

Yes we are iterating all the instructions here but, unless I am missing something, we would literally just be doing the checks twice for no reason. Look at it this way, best case scenario we have to check all possible candidates once, find none and we're done. Worst case, we check all possible candidates once, find one and have to check all possible candidates a second time. Where as if we remove the early checks we only ever have to check the candidates once. So we wouldn't really be stopping any earlier.

yes. we would do check twice if there are TRE candidates. my idea was that number of cases when TRE is applicable less then when TRE is not applicable. Thus we would do double instruction navigation more often than double check for candidates. But, I did not measure real impact. Thus, let`s return old logic here as you suggested.

avl updated this revision to Diff 273457.Jun 25 2020, 10:56 AM

removed early check for TRE candidates from canTRE().

avl updated this revision to Diff 275123.Jul 2 2020, 7:48 AM

rebased.

avl added a comment.Jul 2 2020, 1:19 PM

@efriedma What do you think about current state of this patch? Is it OK?

efriedma added inline comments.Jul 7 2020, 3:09 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
95

If we're not going to try to do TRE at all on calls not marked "tail", we can probably drop this check.

332

It makes sense we can ignore lifetime.end on an alloca: we know the call doesn't refer to the alloca. (Maybe we should check that the pointer argument is pointing at an alloca? That should usually be true anyway, but better to be on the safe side, I guess.)

I don't think it's safe to hoist assume without additional checks; I think we'd need to check that the call is marked "willreturn"?

Since this is sort of tricky, I'd prefer to split this off into a followup.

811–812

Can you move this FIXME into a more appropriate spot?

avl marked 3 inline comments as done.Jul 8 2020, 8:59 AM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
95

It looks to me that original idea(PR962) was to avoid inefficient code which is generated for dynamic alloca.

Currently there would still be generated inefficient code:

Doing TRE for dynamic alloca requires correct stack adjustment to avoid extra stack usage.
i.e. dynamic stack reservation done for alloca should be restored
in the end of the current iteration. Current TRE implementation does not do this.

Please, consider the test case:

#include <alloca.h>

int count;
__attribute__((noinline)) void globalIncrement(const int* param) { 
	count += *param; 
}

void test(int recurseCount)
{
    if (recurseCount == 0) return;
    {
    int *temp = (int*)alloca(100);
    globalIncrement(temp);
    }
    test(recurseCount - 1);
}

Following is the x86 asm generated for the above test case in assumption that dynamic allocas are possible:

.LBB1_2:
        movq    %rsp, %rdi
        addq    $-112, %rdi   <<<<<<<<<<<<<< dynamic stack reservation, need to be restored before "jne .LBB1_2"
        movq    %rdi, %rsp
        callq   _Z15globalIncrementPKi
        addl    $-1, %ebx
        jne     .LBB1_2

So, it looks like we still have inefficient code here and it was a reason for avoiding TRE.

332

It makes sense we can ignore lifetime.end on an alloca: we know the call doesn't refer to the alloca. (Maybe we should check that the pointer argument is pointing at an alloca? That should usually be true anyway, but better to be on the safe side, I guess.)

OK, I would add checking that the pointer argument of lifetime.end is pointing to an alloca.

I don't think it's safe to hoist assume without additional checks; I think we'd need to check that the call is marked "willreturn"?

Since this is sort of tricky, I'd prefer to split this off into a followup.

Ok, I would split Intrinsic::assume into another review.

811–812

OK.

efriedma added inline comments.Jul 8 2020, 12:08 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
95

I guess we can leave this for a later patch.

This isn't really any worse than the stack usage before TRE, assuming we can't emit a sibling call in the backend. And we could avoid this by making TRE insert stacksave/stackrestore intrinsics. But better to do one thing at a time.

avl updated this revision to Diff 276591.Jul 8 2020, 4:06 PM

addressed comments.

I think I'd like to see a testcase where there are multiple recursive calls, but only one is a tail call that can be eliminated.

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
474

The hasOperandBundles() check looks completely new; is there some test for it?

The isNoTailCall() check is currently redundant; it isn't legal to write "tail notail". I guess it makes sense to guard against that, though.

llvm/test/Transforms/TailCallElim/basic.ll
23

I'm not sure this is testing what it was originally supposed to. I guess that's okay, but please fix the comment at least.

llvm/test/Transforms/TailCallElim/tre-noncapturing-alloca-calls.ll
20

For the purpose of this testcase, we don't need the definition of _Z15globalIncrementPKi.

37

I think I'd prefer to just generate this with update_test_checks.py

avl marked an inline comment as done.Jul 8 2020, 4:43 PM
avl added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
474

The hasOperandBundles() check looks completely new; is there some test for it?

it is not new. it is copied from 245 line. Now, when patch changed from its original state all above conditions could be changed just to :

if (!CI->isTailCall())

the test is Transforms/TailCallElim/deopt-bundle.ll

The isNoTailCall() check is currently redundant; it isn't legal to write "tail notail". I guess it makes sense to guard against that, though.

would add checking for that.

avl updated this revision to Diff 276799.Jul 9 2020, 12:01 PM

addressed comments:

added test for multiple recursive calls,
removed duplicated check for operand bundles,
simplified and commented tests.

efriedma accepted this revision.Jul 9 2020, 4:15 PM

LGTM

This revision is now accepted and ready to land.Jul 9 2020, 4:15 PM
avl added a comment.Jul 9 2020, 4:20 PM

Thank you, for the review.

This revision was automatically updated to reflect the committed changes.

Hello. I have an auto-bisecting multi-stage bot that is failing on two after this change. Can we please revert this or commit a quick fix?

FAIL: Clang :: CXX/class/class.compare/class.spaceship/p1.cpp (6232 of 64222)
******************** TEST 'Clang :: CXX/class/class.compare/class.spaceship/p1.cpp' FAILED ********************
Script:
--
: 'RUN: at line 1';   /tmp/_update_lc/t/bin/clang -cc1 -internal-isystem /tmp/_update_lc/t/lib/clang/11.0.0/include -nostdsysteminc -std=c++2a -verify /home/dave/s/lp/clang/test/CXX/class/class.compare/class.spaceship/p1.cpp -fcxx-exceptions
--
Exit Code: 134

Command Output (stderr):
--
clang: /home/dave/s/lp/clang/lib/Basic/SourceManager.cpp:917: clang::FileID clang::SourceManager::getFileIDLoaded(unsigned int) const: Assertion `0 && "Invalid SLocOffset or bad function choice"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.  Program arguments: /tmp/_update_lc/t/bin/clang -cc1 -internal-isystem /tmp/_update_lc/t/lib/clang/11.0.0/include -nostdsysteminc -std=c++2a -verify /home/dave/s/lp/clang/test/CXX/class/class.compare/class.spaceship/p1.cpp -fcxx-exceptions
1.  /home/dave/s/lp/clang/test/CXX/class/class.compare/class.spaceship/p1.cpp:127:38: current parser token ','
2.  /home/dave/s/lp/clang/test/CXX/class/class.compare/class.spaceship/p1.cpp:39:1: parsing namespace 'Deletedness'
3.  /home/dave/s/lp/clang/test/CXX/class/class.compare/class.spaceship/p1.cpp:123:12: parsing function body 'Deletedness::g'
4.  /home/dave/s/lp/clang/test/CXX/class/class.compare/class.spaceship/p1.cpp:123:12: in compound statement ('{}')
 #0 0x000000000359273f llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/tmp/_update_lc/t/bin/clang+0x359273f)
 #1 0x0000000003590912 llvm::sys::RunSignalHandlers() (/tmp/_update_lc/t/bin/clang+0x3590912)
 #2 0x0000000003592bb5 SignalHandler(int) (/tmp/_update_lc/t/bin/clang+0x3592bb5)
 #3 0x00007ffff7fa6a90 __restore_rt (/lib64/libpthread.so.0+0x14a90)
 #4 0x00007ffff7b3da25 raise (/lib64/libc.so.6+0x3ca25)
 #5 0x00007ffff7b26895 abort (/lib64/libc.so.6+0x25895)
 #6 0x00007ffff7b26769 _nl_load_domain.cold (/lib64/libc.so.6+0x25769)
 #7 0x00007ffff7b35e86 (/lib64/libc.so.6+0x34e86)
 #8 0x000000000375636c clang::SourceManager::getFileIDLoaded(unsigned int) const (/tmp/_update_lc/t/bin/clang+0x375636c)
 #9 0x0000000003ee0bbb clang::VerifyDiagnosticConsumer::HandleDiagnostic(clang::DiagnosticsEngine::Level, clang::Diagnostic const&) (/tmp/_update_lc/t/bin/clang+0x3ee0bbb)
#10 0x00000000037501ab clang::DiagnosticIDs::ProcessDiag(clang::DiagnosticsEngine&) const (/tmp/_update_lc/t/bin/clang+0x37501ab)
#11 0x0000000003749fca clang::DiagnosticsEngine::EmitCurrentDiagnostic(bool) (/tmp/_update_lc/t/bin/clang+0x3749fca)
#12 0x0000000004df0c60 clang::Sema::EmitCurrentDiagnostic(unsigned int) (/tmp/_update_lc/t/bin/clang+0x4df0c60)
#13 0x0000000005092783 (anonymous namespace)::DefaultedComparisonAnalyzer::visitBinaryOperator(clang::OverloadedOperatorKind, llvm::ArrayRef<clang::Expr*>, (anonymous namespace)::DefaultedComparisonSubobject, clang::OverloadCandidateSet*) (/tmp/_update_lc/t/bin/clang+0x5092783)
#14 0x0000000005091dba (anonymous namespace)::DefaultedComparisonAnalyzer::visitExpandedSubobject(clang::QualType, (anonymous namespace)::DefaultedComparisonSubobject) (/tmp/_update_lc/t/bin/clang+0x5091dba)
#15 0x0000000005091b86 (anonymous namespace)::DefaultedComparisonVisitor<(anonymous namespace)::DefaultedComparisonAnalyzer, (anonymous namespace)::DefaultedComparisonInfo, (anonymous namespace)::DefaultedComparisonInfo, (anonymous namespace)::DefaultedComparisonSubobject>::visitSubobjects((anonymous namespace)::DefaultedComparisonInfo&, clang::CXXRecordDecl*, clang::Qualifiers) (/tmp/_update_lc/t/bin/clang+0x5091b86)
#16 0x0000000005058c8c (anonymous namespace)::DefaultedComparisonAnalyzer::visit() (/tmp/_update_lc/t/bin/clang+0x5058c8c)
#17 0x000000000505ab22 clang::Sema::DiagnoseDeletedDefaultedFunction(clang::FunctionDecl*) (/tmp/_update_lc/t/bin/clang+0x505ab22)
#18 0x00000000053e60ed clang::Sema::CreateOverloadedBinOp(clang::SourceLocation, clang::BinaryOperatorKind, clang::UnresolvedSetImpl const&, clang::Expr*, clang::Expr*, bool, bool, clang::FunctionDecl*) (/tmp/_update_lc/t/bin/clang+0x53e60ed)
#19 0x000000000514270a BuildOverloadedBinOp(clang::Sema&, clang::Scope*, clang::SourceLocation, clang::BinaryOperatorKind, clang::Expr*, clang::Expr*) (/tmp/_update_lc/t/bin/clang+0x514270a)
#20 0x00000000050fbf49 clang::Sema::ActOnBinOp(clang::Scope*, clang::SourceLocation, clang::tok::TokenKind, clang::Expr*, clang::Expr*) (/tmp/_update_lc/t/bin/clang+0x50fbf49)
#21 0x0000000004d52ccc clang::Parser::ParseRHSOfBinaryExpression(clang::ActionResult<clang::Expr*, true>, clang::prec::Level) (/tmp/_update_lc/t/bin/clang+0x4d52ccc)
#22 0x0000000004d51be9 clang::Parser::ParseAssignmentExpression(clang::Parser::TypeCastState) (/tmp/_update_lc/t/bin/clang+0x4d51be9)
#23 0x0000000004d60dba clang::Parser::ParseExpressionList(llvm::SmallVectorImpl<clang::Expr*>&, llvm::SmallVectorImpl<clang::SourceLocation>&, llvm::function_ref<void ()>) (/tmp/_update_lc/t/bin/clang+0x4d60dba)
#24 0x0000000004d542d9 clang::Parser::ParsePostfixExpressionSuffix(clang::ActionResult<clang::Expr*, true>) (/tmp/_update_lc/t/bin/clang+0x4d542d9)
#25 0x0000000004d55b95 clang::Parser::ParseCastExpression(clang::Parser::CastParseKind, bool, bool&, clang::Parser::TypeCastState, bool, bool*) (/tmp/_update_lc/t/bin/clang+0x4d55b95)
#26 0x0000000004d51b89 clang::Parser::ParseAssignmentExpression(clang::Parser::TypeCastState) (/tmp/_update_lc/t/bin/clang+0x4d51b89)
#27 0x0000000004d51ac9 clang::Parser::ParseExpression(clang::Parser::TypeCastState) (/tmp/_update_lc/t/bin/clang+0x4d51ac9)
#28 0x0000000004d78368 clang::Parser::ParseExprStatement(clang::Parser::ParsedStmtContext) (/tmp/_update_lc/t/bin/clang+0x4d78368)
#29 0x0000000004d76ba0 clang::Parser::ParseStatementOrDeclarationAfterAttributes(llvm::SmallVector<clang::Stmt*, 32u>&, clang::Parser::ParsedStmtContext, clang::SourceLocation*, clang::Parser::ParsedAttributesWithRange&) (/tmp/_update_lc/t/bin/clang+0x4d76ba0)
#30 0x0000000004d76614 clang::Parser::ParseStatementOrDeclaration(llvm::SmallVector<clang::Stmt*, 32u>&, clang::Parser::ParsedStmtContext, clang::SourceLocation*) (/tmp/_update_lc/t/bin/clang+0x4d76614)
#31 0x0000000004d7ecd2 clang::Parser::ParseCompoundStatementBody(bool) (/tmp/_update_lc/t/bin/clang+0x4d7ecd2)
#32 0x0000000004d7fcd0 clang::Parser::ParseFunctionStatementBody(clang::Decl*, clang::Parser::ParseScope&) (/tmp/_update_lc/t/bin/clang+0x4d7fcd0)
#33 0x0000000004cfacc0 clang::Parser::ParseFunctionDefinition(clang::ParsingDeclarator&, clang::Parser::ParsedTemplateInfo const&, clang::Parser::LateParsedAttrList*) (/tmp/_update_lc/t/bin/clang+0x4cfacc0)
#34 0x0000000004d28f2d clang::Parser::ParseDeclGroup(clang::ParsingDeclSpec&, clang::DeclaratorContext, clang::SourceLocation*, clang::Parser::ForRangeInit*) (/tmp/_update_lc/t/bin/clang+0x4d28f2d)
#35 0x0000000004cf9f32 clang::Parser::ParseDeclOrFunctionDefInternal(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec&, clang::AccessSpecifier) (/tmp/_update_lc/t/bin/clang+0x4cf9f32)
#36 0x0000000004cf9938 clang::Parser::ParseDeclarationOrFunctionDefinition(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec*, clang::AccessSpecifier) (/tmp/_update_lc/t/bin/clang+0x4cf9938)
#37 0x0000000004cf86fc clang::Parser::ParseExternalDeclaration(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec*) (/tmp/_update_lc/t/bin/clang+0x4cf86fc)
#38 0x0000000004d02c15 clang::Parser::ParseInnerNamespace(llvm::SmallVector<clang::Parser::InnerNamespaceInfo, 4u> const&, unsigned int, clang::SourceLocation&, clang::ParsedAttributes&, clang::BalancedDelimiterTracker&) (/tmp/_update_lc/t/bin/clang+0x4d02c15)
#39 0x0000000004d0251a clang::Parser::ParseNamespace(clang::DeclaratorContext, clang::SourceLocation&, clang::SourceLocation) (/tmp/_update_lc/t/bin/clang+0x4d0251a)
#40 0x0000000004d22f0a clang::Parser::ParseDeclaration(clang::DeclaratorContext, clang::SourceLocation&, clang::Parser::ParsedAttributesWithRange&, clang::SourceLocation*) (/tmp/_update_lc/t/bin/clang+0x4d22f0a)
#41 0x0000000004cf7e39 clang::Parser::ParseExternalDeclaration(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec*) (/tmp/_update_lc/t/bin/clang+0x4cf7e39)
#42 0x0000000004cf6858 clang::Parser::ParseTopLevelDecl(clang::OpaquePtr<clang::DeclGroupRef>&, bool) (/tmp/_update_lc/t/bin/clang+0x4cf6858)
#43 0x0000000004cf16ed clang::ParseAST(clang::Sema&, bool, bool) (/tmp/_update_lc/t/bin/clang+0x4cf16ed)
#44 0x0000000003e3eb21 clang::FrontendAction::Execute() (/tmp/_update_lc/t/bin/clang+0x3e3eb21)
#45 0x0000000003dba0e3 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/tmp/_update_lc/t/bin/clang+0x3dba0e3)
#46 0x0000000003ee796b clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/tmp/_update_lc/t/bin/clang+0x3ee796b)
#47 0x0000000002244636 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/tmp/_update_lc/t/bin/clang+0x2244636)
#48 0x000000000224297d ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/tmp/_update_lc/t/bin/clang+0x224297d)
#49 0x0000000002242619 main (/tmp/_update_lc/t/bin/clang+0x2242619)
#50 0x00007ffff7b28042 __libc_start_main (/lib64/libc.so.6+0x27042)
#51 0x000000000223f8ce _start (/tmp/_update_lc/t/bin/clang+0x223f8ce)
/tmp/_update_lc/t/tools/clang/test/CXX/class/class.compare/class.spaceship/Output/p1.cpp.script: line 1: 4146089 Aborted                 /tmp/_update_lc/t/bin/clang -cc1 -internal-isystem /tmp/_update_lc/t/lib/clang/11.0.0/include -nostdsysteminc -std=c++2a -verify /home/dave/s/lp/clang/test/CXX/class/class.compare/class.spaceship/p1.cpp -fcxx-exceptions

--

********************
Testing:  0..
FAIL: Clang :: CXX/class/class.compare/class.eq/p2.cpp (6242 of 64222)
******************** TEST 'Clang :: CXX/class/class.compare/class.eq/p2.cpp' FAILED ********************
Script:
--
: 'RUN: at line 1';   /tmp/_update_lc/t/bin/clang -cc1 -internal-isystem /tmp/_update_lc/t/lib/clang/11.0.0/include -nostdsysteminc -std=c++2a -verify /home/dave/s/lp/clang/test/CXX/class/class.compare/class.eq/p2.cpp
--
Exit Code: 134

Command Output (stderr):
--
clang: /home/dave/s/lp/clang/lib/Basic/SourceManager.cpp:917: clang::FileID clang::SourceManager::getFileIDLoaded(unsigned int) const: Assertion `0 && "Invalid SLocOffset or bad function choice"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.  Program arguments: /tmp/_update_lc/t/bin/clang -cc1 -internal-isystem /tmp/_update_lc/t/lib/clang/11.0.0/include -nostdsysteminc -std=c++2a -verify /home/dave/s/lp/clang/test/CXX/class/class.compare/class.eq/p2.cpp
1.  /home/dave/s/lp/clang/test/CXX/class/class.compare/class.eq/p2.cpp:47:30: current parser token ')'
2.  /home/dave/s/lp/clang/test/CXX/class/class.compare/class.eq/p2.cpp:30:13: parsing function body 'test'
3.  /home/dave/s/lp/clang/test/CXX/class/class.compare/class.eq/p2.cpp:30:13: in compound statement ('{}')
 #0 0x000000000359273f llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/tmp/_update_lc/t/bin/clang+0x359273f)
 #1 0x0000000003590912 llvm::sys::RunSignalHandlers() (/tmp/_update_lc/t/bin/clang+0x3590912)
 #2 0x0000000003592bb5 SignalHandler(int) (/tmp/_update_lc/t/bin/clang+0x3592bb5)
 #3 0x00007ffff7fa6a90 __restore_rt (/lib64/libpthread.so.0+0x14a90)
 #4 0x00007ffff7b3da25 raise (/lib64/libc.so.6+0x3ca25)
 #5 0x00007ffff7b26895 abort (/lib64/libc.so.6+0x25895)
 #6 0x00007ffff7b26769 _nl_load_domain.cold (/lib64/libc.so.6+0x25769)
 #7 0x00007ffff7b35e86 (/lib64/libc.so.6+0x34e86)
 #8 0x000000000375636c clang::SourceManager::getFileIDLoaded(unsigned int) const (/tmp/_update_lc/t/bin/clang+0x375636c)
 #9 0x0000000003ee0bbb clang::VerifyDiagnosticConsumer::HandleDiagnostic(clang::DiagnosticsEngine::Level, clang::Diagnostic const&) (/tmp/_update_lc/t/bin/clang+0x3ee0bbb)
#10 0x00000000037501ab clang::DiagnosticIDs::ProcessDiag(clang::DiagnosticsEngine&) const (/tmp/_update_lc/t/bin/clang+0x37501ab)
#11 0x0000000003749fca clang::DiagnosticsEngine::EmitCurrentDiagnostic(bool) (/tmp/_update_lc/t/bin/clang+0x3749fca)
#12 0x0000000004df0c60 clang::Sema::EmitCurrentDiagnostic(unsigned int) (/tmp/_update_lc/t/bin/clang+0x4df0c60)
#13 0x00000000050928b7 (anonymous namespace)::DefaultedComparisonAnalyzer::visitBinaryOperator(clang::OverloadedOperatorKind, llvm::ArrayRef<clang::Expr*>, (anonymous namespace)::DefaultedComparisonSubobject, clang::OverloadCandidateSet*) (/tmp/_update_lc/t/bin/clang+0x50928b7)
#14 0x0000000005091dba (anonymous namespace)::DefaultedComparisonAnalyzer::visitExpandedSubobject(clang::QualType, (anonymous namespace)::DefaultedComparisonSubobject) (/tmp/_update_lc/t/bin/clang+0x5091dba)
#15 0x0000000005091b86 (anonymous namespace)::DefaultedComparisonVisitor<(anonymous namespace)::DefaultedComparisonAnalyzer, (anonymous namespace)::DefaultedComparisonInfo, (anonymous namespace)::DefaultedComparisonInfo, (anonymous namespace)::DefaultedComparisonSubobject>::visitSubobjects((anonymous namespace)::DefaultedComparisonInfo&, clang::CXXRecordDecl*, clang::Qualifiers) (/tmp/_update_lc/t/bin/clang+0x5091b86)
#16 0x0000000005058c8c (anonymous namespace)::DefaultedComparisonAnalyzer::visit() (/tmp/_update_lc/t/bin/clang+0x5058c8c)
#17 0x000000000505ab22 clang::Sema::DiagnoseDeletedDefaultedFunction(clang::FunctionDecl*) (/tmp/_update_lc/t/bin/clang+0x505ab22)
#18 0x00000000053e60ed clang::Sema::CreateOverloadedBinOp(clang::SourceLocation, clang::BinaryOperatorKind, clang::UnresolvedSetImpl const&, clang::Expr*, clang::Expr*, bool, bool, clang::FunctionDecl*) (/tmp/_update_lc/t/bin/clang+0x53e60ed)
#19 0x000000000514270a BuildOverloadedBinOp(clang::Sema&, clang::Scope*, clang::SourceLocation, clang::BinaryOperatorKind, clang::Expr*, clang::Expr*) (/tmp/_update_lc/t/bin/clang+0x514270a)
#20 0x00000000050fbf49 clang::Sema::ActOnBinOp(clang::Scope*, clang::SourceLocation, clang::tok::TokenKind, clang::Expr*, clang::Expr*) (/tmp/_update_lc/t/bin/clang+0x50fbf49)
#21 0x0000000004d52ccc clang::Parser::ParseRHSOfBinaryExpression(clang::ActionResult<clang::Expr*, true>, clang::prec::Level) (/tmp/_update_lc/t/bin/clang+0x4d52ccc)
#22 0x0000000004d51be9 clang::Parser::ParseAssignmentExpression(clang::Parser::TypeCastState) (/tmp/_update_lc/t/bin/clang+0x4d51be9)
#23 0x0000000004d60dba clang::Parser::ParseExpressionList(llvm::SmallVectorImpl<clang::Expr*>&, llvm::SmallVectorImpl<clang::SourceLocation>&, llvm::function_ref<void ()>) (/tmp/_update_lc/t/bin/clang+0x4d60dba)
#24 0x0000000004d4b29c clang::Parser::ParseCXXTypeConstructExpression(clang::DeclSpec const&) (/tmp/_update_lc/t/bin/clang+0x4d4b29c)
#25 0x0000000004d57617 clang::Parser::ParseCastExpression(clang::Parser::CastParseKind, bool, bool&, clang::Parser::TypeCastState, bool, bool*) (/tmp/_update_lc/t/bin/clang+0x4d57617)
#26 0x0000000004d51b89 clang::Parser::ParseAssignmentExpression(clang::Parser::TypeCastState) (/tmp/_update_lc/t/bin/clang+0x4d51b89)
#27 0x0000000004d51ac9 clang::Parser::ParseExpression(clang::Parser::TypeCastState) (/tmp/_update_lc/t/bin/clang+0x4d51ac9)
#28 0x0000000004d78368 clang::Parser::ParseExprStatement(clang::Parser::ParsedStmtContext) (/tmp/_update_lc/t/bin/clang+0x4d78368)
#29 0x0000000004d76ba0 clang::Parser::ParseStatementOrDeclarationAfterAttributes(llvm::SmallVector<clang::Stmt*, 32u>&, clang::Parser::ParsedStmtContext, clang::SourceLocation*, clang::Parser::ParsedAttributesWithRange&) (/tmp/_update_lc/t/bin/clang+0x4d76ba0)
#30 0x0000000004d76614 clang::Parser::ParseStatementOrDeclaration(llvm::SmallVector<clang::Stmt*, 32u>&, clang::Parser::ParsedStmtContext, clang::SourceLocation*) (/tmp/_update_lc/t/bin/clang+0x4d76614)
#31 0x0000000004d7ecd2 clang::Parser::ParseCompoundStatementBody(bool) (/tmp/_update_lc/t/bin/clang+0x4d7ecd2)
#32 0x0000000004d7fcd0 clang::Parser::ParseFunctionStatementBody(clang::Decl*, clang::Parser::ParseScope&) (/tmp/_update_lc/t/bin/clang+0x4d7fcd0)
#33 0x0000000004cfacc0 clang::Parser::ParseFunctionDefinition(clang::ParsingDeclarator&, clang::Parser::ParsedTemplateInfo const&, clang::Parser::LateParsedAttrList*) (/tmp/_update_lc/t/bin/clang+0x4cfacc0)
#34 0x0000000004d28f2d clang::Parser::ParseDeclGroup(clang::ParsingDeclSpec&, clang::DeclaratorContext, clang::SourceLocation*, clang::Parser::ForRangeInit*) (/tmp/_update_lc/t/bin/clang+0x4d28f2d)
#35 0x0000000004cf9f32 clang::Parser::ParseDeclOrFunctionDefInternal(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec&, clang::AccessSpecifier) (/tmp/_update_lc/t/bin/clang+0x4cf9f32)
#36 0x0000000004cf9938 clang::Parser::ParseDeclarationOrFunctionDefinition(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec*, clang::AccessSpecifier) (/tmp/_update_lc/t/bin/clang+0x4cf9938)
#37 0x0000000004cf86fc clang::Parser::ParseExternalDeclaration(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec*) (/tmp/_update_lc/t/bin/clang+0x4cf86fc)
#38 0x0000000004cf6858 clang::Parser::ParseTopLevelDecl(clang::OpaquePtr<clang::DeclGroupRef>&, bool) (/tmp/_update_lc/t/bin/clang+0x4cf6858)
#39 0x0000000004cf16ed clang::ParseAST(clang::Sema&, bool, bool) (/tmp/_update_lc/t/bin/clang+0x4cf16ed)
#40 0x0000000003e3eb21 clang::FrontendAction::Execute() (/tmp/_update_lc/t/bin/clang+0x3e3eb21)
#41 0x0000000003dba0e3 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/tmp/_update_lc/t/bin/clang+0x3dba0e3)
#42 0x0000000003ee796b clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/tmp/_update_lc/t/bin/clang+0x3ee796b)
#43 0x0000000002244636 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/tmp/_update_lc/t/bin/clang+0x2244636)
#44 0x000000000224297d ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/tmp/_update_lc/t/bin/clang+0x224297d)
#45 0x0000000002242619 main (/tmp/_update_lc/t/bin/clang+0x2242619)
#46 0x00007ffff7b28042 __libc_start_main (/lib64/libc.so.6+0x27042)
#47 0x000000000223f8ce _start (/tmp/_update_lc/t/bin/clang+0x223f8ce)
/tmp/_update_lc/t/tools/clang/test/CXX/class/class.compare/class.eq/Output/p2.cpp.script: line 1: 4146047 Aborted                 /tmp/_update_lc/t/bin/clang -cc1 -internal-isystem /tmp/_update_lc/t/lib/clang/11.0.0/include -nostdsysteminc -std=c++2a -verify /home/dave/s/lp/clang/test/CXX/class/class.compare/class.eq/p2.cpp

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
********************
Failed Tests (2):
  Clang :: CXX/class/class.compare/class.eq/p2.cpp
  Clang :: CXX/class/class.compare/class.spaceship/p1.cpp


Testing Time: 117.51s
  Unsupported      : 12906
  Passed           : 51214
  Expectedly Failed:   100
  Failed           :     2
FAILED: CMakeFiles/check-all
cd /tmp/_update_lc/t && /usr/bin/python3.8 /tmp/_update_lc/t/./bin/llvm-lit -sv --param USE_Z3_SOLVER=0 /tmp/_update_lc/t/tools/clang/test /tmp/_update_lc/t/tools/lld/test /tmp/_update_lc/t/tools/lldb/test /tmp/_update_lc/t/utils/lit /tmp/_update_lc/t/test
ninja: build stopped: subcommand failed.
+ do_error 'FAILURE -- STAGE TWO BUILD of LLVM' 12
+ echo FAILURE -- STAGE TWO BUILD of LLVM
FAILURE -- STAGE TWO BUILD of LLVM
+ exit 12