Stream: t-compiler/wg-llvm

Topic: Forward-progress guarantee


Nikita Popov (Aug 04 2019 at 08:26, on Zulip):

It looks like I misunderstood the direction in which forward-progress guarantees in LLVM are headed. Apparently the current stance is that forward-progress is required and llvm.sideeffect is the final solution to this issue, not just a temporary workaround.

RalfJ (Aug 04 2019 at 09:13, on Zulip):

Wow :(

RalfJ (Aug 04 2019 at 09:13, on Zulip):

do they plan to fix clang? (currently LLVM, to my knowledge, violates the C standard by requiring forward progress even for loops where the conditional is a constant)

nagisa (Aug 04 2019 at 14:07, on Zulip):

Any context? I did not get any pings on relevant bugs.

Nikita Popov (Aug 04 2019 at 14:12, on Zulip):

Direct context is https://reviews.llvm.org/D59978, though more relevant is http://lists.llvm.org/pipermail/llvm-dev/2015-July/088095.html.

RalfJ (Aug 04 2019 at 19:47, on Zulip):

@Nikita Popov seems worth asking how they plan to implement the "unless loop conditional is a constant" part of the C spec. Also I dont think C makes a forward progress assumption for recursive functions; the quoted part of the standard is specifically about loops.

RalfJ (Aug 04 2019 at 19:49, on Zulip):

or maybe I can read what they say in there as them saying that stack overflow is UB, which would be... really, really bad news for guard pages as they become useless. well not practically useless but from a principled perspective.

Nikita Popov (Aug 04 2019 at 19:54, on Zulip):

I've opened https://reviews.llvm.org/D65718 to document this ... but based on the initial comments maybe the comments on that thread do not actually represent the current consensus.

Nikita Popov (Aug 04 2019 at 19:54, on Zulip):

Someone recently started a thread on llvm-dev to clarify stack overflow behavior, no responses yet though.

rkruppe (Aug 04 2019 at 19:55, on Zulip):

Tangentially related, I've been baited into finally implementing the -Z flag I proposed here https://github.com/rust-lang/rust/issues/28728#issuecomment-426247247 to see how bad the impact really is

RalfJ (Aug 04 2019 at 19:56, on Zulip):

@Nikita Popov thanks for pointing us to the llvm-dev thread(s), I hope to chime in there as well (after catching up)

Nikita Popov (Aug 04 2019 at 19:58, on Zulip):

@rkruppe Did you see https://github.com/rust-lang/rust/pull/59546?

RalfJ (Aug 04 2019 at 19:59, on Zulip):

@rkruppe do you know if there is any basis in C for removing infinite recursion with no side-effects?

rkruppe (Aug 04 2019 at 19:59, on Zulip):

@Nikita Popov Oh dear. I did not.

Nikita Popov (Aug 04 2019 at 19:59, on Zulip):

That has some indication about just how bad it is. Though I think that it's somewhat overly pessimistic, because it places sideeffect intrinsics on every call instead of on every function entry.

RalfJ (Aug 04 2019 at 20:01, on Zulip):

@Nikita Popov is "current" discussion happening on the list or that review you linked? What would likely be the better place to respond?

RalfJ (Aug 04 2019 at 20:01, on Zulip):

(asking because I am not very familiar with the ways of LLVM. still takes me several minutes, once I wrote a patch, to submit it for review there. I had no idea that non-PR-based workflows are so bad until I was subject to this one. I mean I worked on KDE which also used/uses a reviewboard, but there at least I could just git push "into the reviewboard", so things were much easier. manually picking reviewers as a dont-know-anything new contributor still sucked though.)

rkruppe (Aug 04 2019 at 20:03, on Zulip):

That has some indication about just how bad it is. Though I think that it's somewhat overly pessimistic, because it places sideeffect intrinsics on every call instead of on every function entry.

I only see perf results, which measure compile time as much as optimization impact. It seems nobody has provided lolbench results (or other measurements) so far. Is that correct?

Nikita Popov (Aug 04 2019 at 20:04, on Zulip):

@RalfJ For stack overflows I'd respond to http://lists.llvm.org/pipermail/llvm-dev/2019-August/134317.html. For forward-progress in general probably best on https://reviews.llvm.org/D65718, I don't think there has been a recent mailing list discussion on this.

RalfJ (Aug 04 2019 at 20:05, on Zulip):

@Nikita Popov thanks

Nikita Popov (Aug 04 2019 at 20:06, on Zulip):

@rkruppe Yeah, those are only compile time results (though check build regressions should be pure run-time regressions). Compile-time is a big concern as well though, because llvm.sideeffect really blows up the IR without some kind of coalescing.

rkruppe (Aug 04 2019 at 20:09, on Zulip):

Sure, the compile time regression sucks, but it's much less important than missed optimizations IMO (and apparently also in the eyes of the compiler team)

nagisa (Aug 04 2019 at 20:13, on Zulip):

I think for that PR we ideally want to do codegen analysis pass (we have some for e.g. SSA-ization of our MIR values. something similar to that)

nagisa (Aug 04 2019 at 20:13, on Zulip):

and then just stick a sideeffect in the entry point of that function which should not be optimised out.

nagisa (Aug 04 2019 at 20:14, on Zulip):

at least currently LLVM is not smart enough to remove the loops themselves, rather it is only removing calls to functions that contain such infinite loops.

nagisa (Aug 04 2019 at 20:15, on Zulip):

but for perf evaluation I think whatever approach works.

rkruppe (Aug 04 2019 at 20:15, on Zulip):

What sort of analysis are you thinking of? Finding loops?

Nikita Popov (Aug 04 2019 at 20:17, on Zulip):

@nagisa It's not so much that LLVM isn't smart enough, but that it currently has explicit checks to not remove potentially infinite loops.

nagisa (Aug 04 2019 at 20:18, on Zulip):

What sort of analysis are you thinking of? Finding loops?

Analysis which figures out whether we need to smack a sideeffect into the function. It can be as simple as "if there is a loop" or as complicated "this particular pattern makes semantics currently not match".

nagisa (Aug 04 2019 at 20:18, on Zulip):

nagisa It's not so much that LLVM isn't smart enough, but that it currently has explicit checks to not remove potentially infinite loops.

Okay, "smart enough to not remove".

rkruppe (Aug 04 2019 at 20:19, on Zulip):

Because of recursion, "there's a loop" is not enough.

RalfJ (Aug 04 2019 at 20:20, on Zulip):

lol... searching for "C is stack overflow undefined behavior" is not as helpful as one might think because a certain site decided to pick a particular name...

nagisa (Aug 04 2019 at 20:21, on Zulip):

Stack overflow is a buffer overrun, so they are equivalent.

RalfJ (Aug 04 2019 at 20:21, on Zulip):

I dont think the C standard specifies the stack as a buffer

nagisa (Aug 04 2019 at 20:21, on Zulip):

C standard will not specify anything much about stack at all, because that’s a concern for an ABI document.

nagisa (Aug 04 2019 at 20:22, on Zulip):

At least that’s my intuition, I haven’t C standard in my head.

RalfJ (Aug 04 2019 at 20:22, on Zulip):

I hope nobody does, they could go right to the asylum...

nagisa (Aug 04 2019 at 20:22, on Zulip):

but I do know that ABI documents usually take the responsibility of specifying stack.

RalfJ (Aug 04 2019 at 20:22, on Zulip):

the other tricky bit is that the compiler is certainly allowed to turn stack overflows into working code, e.g. by removing unused local variables

rkruppe (Aug 04 2019 at 20:23, on Zulip):

ABI documents aren't (shouldn't) be in the business of settling whether something is UB or not, though

RalfJ (Aug 04 2019 at 20:23, on Zulip):

that could be specified very precisely by saying "on the Abstract Machine, any time a function is called, execution might halt due a stack overflow"

RalfJ (Aug 04 2019 at 20:23, on Zulip):

but of course such precision is not achieved by the C spec

nagisa (Aug 04 2019 at 20:24, on Zulip):

@rkruppe ABI document does not set what UB is or isn’t, but it does (and should) specify what stack is.

nagisa (Aug 04 2019 at 20:24, on Zulip):

Which usually is a buffer that "grows downwards".

RalfJ (Aug 04 2019 at 20:24, on Zulip):

@nagisa but in no way does that make it a buffer in any C sense

nagisa (Aug 04 2019 at 20:25, on Zulip):

/me shrugs

RalfJ (Aug 04 2019 at 20:25, on Zulip):

like, ABIs also define frame pointers and return pointers and stuff

RalfJ (Aug 04 2019 at 20:25, on Zulip):

and still it is UB to observe those from C

RalfJ (Aug 04 2019 at 20:26, on Zulip):

ABIs are basically mostly hardware-level documents. they don't really say anything about what the C Abstract Machine does, AFAIK.

RalfJ (Aug 04 2019 at 20:26, on Zulip):

some aspects of ABI feed back, such as sizes of types

RalfJ (Aug 04 2019 at 20:26, on Zulip):

but those are explicitly accounted for in a precise Abstract Machine spec: "each type has an implementation-defined size, ..."

nagisa (Aug 04 2019 at 20:29, on Zulip):

I guess there is one example (SPARC) where stack is not a buffer at all.

nagisa (Aug 04 2019 at 20:30, on Zulip):

(well, it is in a sense that it is still a few pages of memory), but the actual hardware requires it to be used in a very specific manner which disallows to treat it that way

Last update: Nov 15 2019 at 11:00UTC