Page MenuHomePhabricator

Mark restrict pointer or reference to const as invariant
AbandonedPublic

Authored by yaxunl on Feb 27 2020, 11:41 AM.

Details

Summary

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
means the memory does not change.

Mark such pointer or reference as invariant allows more optimization opportunities.

This gives users a way to mark something as invariant.

Diff Detail

Event Timeline

yaxunl created this revision.Feb 27 2020, 11:41 AM
hfinkel requested changes to this revision.Feb 27 2020, 12:00 PM

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.

This revision now requires changes to proceed.Feb 27 2020, 12:00 PM

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.

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.

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.

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.

How about inserting llvm.invariant.end at the end of scope of the variable?

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.

If users derive a non-const pointer from the const pointer and modify it, doesn't that result in UB? Thanks.

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.
You would put the read access of *p in its own universe; or even better, something like

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.

If users derive a non-const pointer from the const pointer and modify it, doesn't that result in UB? Thanks.

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.

If users derive a non-const pointer from the const pointer and modify it, doesn't that result in UB? Thanks.

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.

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.

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.

Oh yes. Thanks for the reminder. We have only 18 months left if we want something like that in C++23...

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.
You would put the read access of *p in its own universe; or even better, something like

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.

Agree. An attribute like __attribute__((immutable)) should be useful. It can be used on a pointer or reference and tells the compiler that
the content of the pointer or reference is invariant in the scope of that variable.

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.

Do you mean to prove in analysis passes? Should we emit some sort of hints from the frontend to indicate what to look for?

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.

Do you mean to prove in analysis passes? Should we emit some sort of hints from the frontend to indicate what to look for?

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).

yaxunl added a comment.Mar 3 2020, 8:57 AM

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.

Do you mean to prove in analysis passes? Should we emit some sort of hints from the frontend to indicate what to look for?

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).

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__.

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.

Do you mean to prove in analysis passes? Should we emit some sort of hints from the frontend to indicate what to look for?

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).

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__.

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).

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).

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?

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).

How about the cases where users cannot use restrict but they still want to mark a pointer as invariant?

I'm not sure what cases those would be; I'm pretty sure that if memory is invariant then you can always use restrict.

Or even though restrict is used but it is too complicated for alias analysis to deduce invariance?

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.

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).

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?

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.

yaxunl abandoned this revision.Mar 30 2020, 8:58 AM