Differential D75285
Mark restrict pointer or reference to const as invariant Authored by yaxunl on Feb 27 2020, 11:41 AM.
Details We saw users intend to use const int* restrict to indicate the memory pointed to by the pointer is invariant. This makes sense since restrict means the memory is not aliased by any other pointers whereas const Mark such pointer or reference as invariant allows more optimization opportunities. This gives users a way to mark something as invariant.
Diff Detail Event TimelineComment Actions Unfortunately, we cannot do this kind of thing just because it seems to make sense. The language semantics must be exactly satisfied by the IR-level semantics. I certainly agree that it would make sense for users to be able to mark invariant loads, but this mechanism simply might not be the right one. One problem here is that, with something like: char test2(X *x) {
const char* __restrict p = &(x->b);
return *p;
}what happens when the function is inlined? Does the "invariantness" only still apply to accesses within the scope of the local restrict pointer? I believe that it would not, and that would be a problem because later code might legally modify the relevant data. Comment Actions Unfortunately, const also doesn't mean that the memory doesn't change. It does mean it can't be changed through this pointer, but restrict allows you to derive more pointers from it within the restrict scope, and those pointers can remove the const qualifier. Comment Actions If this is not the right way to tell the compiler a memory pointed to by a pointer is invariant, what is the recommended way? Can we introduce clang builtins for llvm.invariant.start and llvm.invariant.end to allow user to specify that? Thanks. Comment Actions Are you sure restrict alone isn't good enough? It doesn't directly tell you that the memory is invariant, but it's usually simple to prove that the memory isn't modified within the restrict scope, which might be sufficient. Comment Actions If users derive a non-const pointer from the const pointer and modify it, doesn't that result in UB? Thanks. Comment Actions I don't think that 'restrict' is a good match for this behavior. For c++, the alias_set proposal (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4150.pdf) would be a better match. struct X {
int a;
char [[alias_set(MyOwnUniverseForX_b)]] b;
};Unfortunatly, there is no implementation yet. Imho, adding a 'attribute((invariant))' or something similar (immutable ? const_invariant ?) would be a better approach. (hmm, I like 'immutable') char test2(X *x) {
const char __attribute__((immutable)) *p = (const char __attribute__((immutable))*)&(x->b);
// for all i: p[i] will never be modified.
return *p;
}Extra precautions are probably needed to ensure that the initialization of x->b is separated from the usage of it. Comment Actions No. Modifying a const object is UB, so e.g. we can segv if it's in .rodata, but a const pointer is not necessarily a pointer to a const object. If it's a const pointer to a non-const object then one can cast it directly to a non-const pointer and mutate at will. This unfortunately makes 'const int*' of rather less use than it would otherwise be. Comment Actions Right. Note that this UB extends to all const objects, even locals, which is something that I don't think we currently have a good way to take advantage of in LLVM. Unfortunately, this probably doesn't help Yaxun's use case. Comment Actions Oh yes. Thanks for the reminder. We have only 18 months left if we want something like that in C++23... Comment Actions Agree. An attribute like __attribute__((immutable)) should be useful. It can be used on a pointer or reference and tells the compiler that Comment Actions Do you mean to prove in analysis passes? Should we emit some sort of hints from the frontend to indicate what to look for? Comment Actions Not sure what you mean with 'hints from the frontend', but D68484 (and later) contain a significant improvement to clang's handling of restrict. That could make the restrict path feasible (if that would support the actual use case). Comment Actions I think there are cases that noalias is not sufficient to prove invariance. For example, a global variable, even if we mark it as restrict and we do not modify it in a function, the compiler is still not sure it is invariant in that function, since it may be modified by another thread. In this case, if a user knows that it is invariant in that function, he would just want to mark it as __invariant__ or __immutable__. Comment Actions That is not true for two reasons: first, restrict guarantees that the variable is not accessed through any non-derived l-value within its scope, and that would certainly include from other threads; and second, it is undefined behavior for two threads to access the same object without synchronizing anyway (unless they're both just reading from it). Comment Actions How about the cases where users cannot use restrict but they still want to mark a pointer as invariant? Or even though restrict is used but it is too complicated for alias analysis to deduce invariance? Comment Actions I'm not sure what cases those would be; I'm pretty sure that if memory is invariant then you can always use restrict.
I asked before if there was a specific optimization problem you were trying to solve, and I still have that question. It kindof feels like somebody's already decided that they don't want to use alias analysis for something, so now you're looking for ways to do it without alias analysis, even though alias analysis might be a satisfactory way of solving the problem. restrict gives us a *lot* of informatiion; I'm sure there are places where we don't preserve it well enough to do some optimization, but that can be improved without needing a whole new language feature. Comment Actions If we can reuse existing attributes it is better than adding new ones so my preference would be to make restrict work unless it's absolutely impossible for the use case you consider. |