4 ms·

Question is when do you stop? At what point does adding runtime checks become too expensive? I doubt you want to end up with gazillion checks for non-overlap.

Question is when do you stop? At what point does adding runtime checks become too expensive? I doubt you want to end up with gazillion checks for non-overlap. C and C++ both seem to lack user-specified type aliasing relations. You have to work with standard base types. I want to be able to declare my own type that is unique on its own and aliasing relations with other types.

DannyBee 10y ago
Sure, and that's a reasonable thing, i'm just saying "the world where nothing aliased and users specify all possible aliasing" didn't turn out to be a fun one either. Honestly, while it seems a good idea, most languages that allow you to specify complex aliasing relationships tend not to be translatable into usable metadata by anything but very high level compilers in a lot of cases. Either they have to evaluate the language-level aliasing rules in the compiler (which requires a high enough level IR for them to still be correct on the IR, and means your compiler is language specific), try to translate them into something more generic (which almost always loses info), or fall back to (n^2)/2 space pair aliasing (IE for each n pointer, specify which n pointers it aliases or no aliases with). They also have to be queryable in essentially constant time for a pointer pair or a memory location and a pointer to have a reasonable speed compiler. This means, for example, if your rule says "they don't alias if every field of every subobject is in blah relationship", that ain't gonna work well unless the answer to that is precomputed and doesn't take up a lot space to represent for the objects. Most choose the middle ground to make all this happen (or have a high level ir, optimize some at high cost, then choose the middle ground). So the problem is not usually coming up with cool things you can say at a high level, it's making them usable to the compiler. I believe, in fact, rust has had precisely this problem with various features, and added a higher level IR to attempt to ameliorate this. The downside is if you don't find a way to transfer it to the lower levels, you miss optimization at the high level due to not-exposed operations (IE things that are lowered), and then the lower level doesn't have the info the higher level did, so you still miss some optimizations So you can have the nicest, most complete aliasing specification in the world, and making it help an optimizer may just not work at all. The late 80's are littered with languages where this was true. Then the early 90's to mid 90's did the same thing with parallelization. see, e.g, https://en.wikipedia.org/wiki/High_Performance_Fortran https://en.wikipedia.org/wiki/High_Performance_Fortran The paper ken kennedy wrote on it before he passed away is a great read, and led to later compilers, etc, being much better about this sort of thing. (Rust should pay attention to the "different optimizations", etc parts and hope there is never a second compiler for rust that gains traction :P)
- flamedoge 10y ago
  > tend not to be translatable into usable metadata LLVM tbaa honestly seems so straight-forward and not language-specific... actually you're the one who taught me this! I mean how many ways can you describe one-to-many aliasing relations?
  - DannyBee 10y ago
    >> tend not to be translatable into usable metadata >LLVM tbaa honestly seems so straight-forward and not language-specific" It also represents a very non-complex aliasing relationship :) IE type dags. I could also point out it's horrendously broken and about to be redesigned (but to be fair, this was just 'unions were a hack in tbaa, nobody realized how much of a hack until they started really digging') https://bugs.llvm.org/show_bug.cgi?id=32056 https://bugs.llvm.org/show_bug.cgi?id=32056 The result will just look like gcc's. But this is also subject to fairly simple rules, and those rules fail to let you optimize in a lot of cases. IE the language itself says what the rules are. I can't use the type system to say "circle types never alias square types" if it's not in the language rules instead, if i do this: struct circle { int radius; int x; int y; }; struct square { int size; int x; int y; } There is actually no way in C, translated to llvm, to say pointers to these things these do not alias (i don't remember all the versions of the common initial sequence rules off the top of my head to know whether it's possible at all. Assume for our purposes it's not) in fact, in llvm, it's worse. It has a "type system" that is useless (literally), and in that type system, you can't even distinguish or prove that a given access is to a different field (because it allows negative offsets). We have no metadata that specifies it (remember the struct tbaa info is about types of fields, not access paths in generals) So TBAA will not help with that. Thus, in the above case, a pointer to any field will may-alias every other field. (This is what llvm will do, other compilers are much better) The best you get in C is restrict, which is pretty weak. This is the use case a type system helps, where you want to be able to assert things that you can't easily express. But then you have to translate that assertion, again, into something the compiler understands. Compiler type systems and language type systems are pretty much never identical. This is also info that requires translation from high level to low level :(
ori_b 10y ago
> At what point does adding runtime checks become too expensive? That's what profile guided optimization is for!
- kibwen 10y ago
  I love PGO and think it's basically magic, but I'd be very surprised if PGO alone would let you ever elide runtime aliasing checks!
  - gpderetta 10y ago
    In fact PGO will probably help you find out where to add those aliasing checks! Whole program optimization could help though.
  - flamedoge 10y ago
    You are right that even with PGO you are still speculating if you remove runtime checks.
  - ori_b 10y ago
    It lets you decide when there's more overhead in versioning your loop versus not versioning it.

DannyBee 10y ago

Sure, and that's a reasonable thing, i'm just saying "the world where nothing aliased and users specify all possible aliasing" didn't turn out to be a fun one either. Honestly, while it seems a good idea, most languages that allow you to specify complex aliasing relationships tend not to be translatable into usable metadata by anything but very high level compilers in a lot of cases. Either they have to evaluate the language-level aliasing rules in the compiler (which requires a high enough level IR for them to still be correct on the IR, and means your compiler is language specific), try to translate them into something more generic (which almost always loses info), or fall back to (n^2)/2 space pair aliasing (IE for each n pointer, specify which n pointers it aliases or no aliases with). They also have to be queryable in essentially constant time for a pointer pair or a memory location and a pointer to have a reasonable speed compiler. This means, for example, if your rule says "they don't alias if every field of every subobject is in blah relationship", that ain't gonna work well unless the answer to that is precomputed and doesn't take up a lot space to represent for the objects. Most choose the middle ground to make all this happen (or have a high level ir, optimize some at high cost, then choose the middle ground). So the problem is not usually coming up with cool things you can say at a high level, it's making them usable to the compiler. I believe, in fact, rust has had precisely this problem with various features, and added a higher level IR to attempt to ameliorate this. The downside is if you don't find a way to transfer it to the lower levels, you miss optimization at the high level due to not-exposed operations (IE things that are lowered), and then the lower level doesn't have the info the higher level did, so you still miss some optimizations So you can have the nicest, most complete aliasing specification in the world, and making it help an optimizer may just not work at all. The late 80's are littered with languages where this was true. Then the early 90's to mid 90's did the same thing with parallelization. see, e.g, https://en.wikipedia.org/wiki/High_Performance_Fortran https://en.wikipedia.org/wiki/High_Performance_Fortran The paper ken kennedy wrote on it before he passed away is a great read, and led to later compilers, etc, being much better about this sort of thing. (Rust should pay attention to the "different optimizations", etc parts and hope there is never a second compiler for rust that gains traction :P)

flamedoge 10y ago
> tend not to be translatable into usable metadata LLVM tbaa honestly seems so straight-forward and not language-specific... actually you're the one who taught me this! I mean how many ways can you describe one-to-many aliasing relations?
- DannyBee 10y ago
  >> tend not to be translatable into usable metadata >LLVM tbaa honestly seems so straight-forward and not language-specific" It also represents a very non-complex aliasing relationship :) IE type dags. I could also point out it's horrendously broken and about to be redesigned (but to be fair, this was just 'unions were a hack in tbaa, nobody realized how much of a hack until they started really digging') https://bugs.llvm.org/show_bug.cgi?id=32056 https://bugs.llvm.org/show_bug.cgi?id=32056 The result will just look like gcc's. But this is also subject to fairly simple rules, and those rules fail to let you optimize in a lot of cases. IE the language itself says what the rules are. I can't use the type system to say "circle types never alias square types" if it's not in the language rules instead, if i do this: struct circle { int radius; int x; int y; }; struct square { int size; int x; int y; } There is actually no way in C, translated to llvm, to say pointers to these things these do not alias (i don't remember all the versions of the common initial sequence rules off the top of my head to know whether it's possible at all. Assume for our purposes it's not) in fact, in llvm, it's worse. It has a "type system" that is useless (literally), and in that type system, you can't even distinguish or prove that a given access is to a different field (because it allows negative offsets). We have no metadata that specifies it (remember the struct tbaa info is about types of fields, not access paths in generals) So TBAA will not help with that. Thus, in the above case, a pointer to any field will may-alias every other field. (This is what llvm will do, other compilers are much better) The best you get in C is restrict, which is pretty weak. This is the use case a type system helps, where you want to be able to assert things that you can't easily express. But then you have to translate that assertion, again, into something the compiler understands. Compiler type systems and language type systems are pretty much never identical. This is also info that requires translation from high level to low level :(

ori_b 10y ago

> At what point does adding runtime checks become too expensive? That's what profile guided optimization is for!

kibwen 10y ago
I love PGO and think it's basically magic, but I'd be very surprised if PGO alone would let you ever elide runtime aliasing checks!
- gpderetta 10y ago
  In fact PGO will probably help you find out where to add those aliasing checks! Whole program optimization could help though.
- flamedoge 10y ago
  You are right that even with PGO you are still speculating if you remove runtime checks.
- ori_b 10y ago
  It lets you decide when there's more overhead in versioning your loop versus not versioning it.