Tricks to avoid pointer aliasing in generic code

I found a hacky way to do this. I realized that I can use the __restrict keyword in member (pointer) variables.

So, basically, if I "reimplement" vector iterator with a restrict pointer then I can get away with this, in principle.

In practice this only helps on GCC, and not in clang.

template<class Iterator>
struct restricted_vector_iterator {
    explicit restricted_vector_iterator(Iterator it) : p_{&*it} {}

    decltype(auto) operator*() const {return *p_;}

    decltype(auto) operator++(int) {++p_; return *this;}

 private:
    typename Iterator::pointer __restrict p_;
};


...
    foo(restricted_vector_iterator{v1.begin()}, restricted_vector_iterator{v2.begin()});

https://godbolt.org/z/oE1f1vnPr

This looks like casting the iterator to pointer but in generic code a restrict class could work differently for different iterator types. Also I am not modifying "library" code, only user code. (The user knows that the ranges do not overlap.)

Of course this is not ideal.

First, It doesn't scale well, because every critical iterator will have to be wrapped/reimplemented (__restrict cannot be applied to the iterator class, only to the contained pointer). This would be much simpler if __restrict worked recursively for the pointer member inside a class (specifically an iterator.)

Second, it sounds kind of dangerous that one can keep a restricted pointer alive in the wild, maybe I can make this wrapper iterator non-copyable or at least "hard to copy".

Third, it is not clear to me how pointer arithmetic will work (are pointers calculated from other restricted pointers, also restricted?, are restricted among them?)

Fourth, it is not portable, both because __restrict is an extension, and because at the end it only does the optimization on GCC it seems.

If you have any comments let me know.

Finally, if I had control over the container, I could have a different method like v1.RESTRICT_begin() for example.

The general way to convince the compiler of an arbitrary boolean predicate is to __builtin_assume it, something like this:

#include <version>
#if defined(__clang__)
 #define ASSUME(x) __builtin_assume(x)
#elif defined(_MSC_VER)
 #define ASSUME(x) __assume(x)
#elif __has_builtin(__builtin_unreachable)
 #define ASSUME(x) do { if (!(x)) __builtin_unreachable(); } while (0)
#elif defined(__cpp_lib_unreachable)
 #include <utility>
 #define ASSUME(x) do { if (!(x)) std::unreachable(); } while (0)
#endif

(GCC supports __builtin_unreachable but not __builtin_assume. MSVC supports it but only as __assume, not __builtin_assume.)

Unfortunately, no existing compiler seems to understand the following sequence (Godbolt):

int misunderstood(int *p, int *q) {
  ASSUME(p != q);
  *p = 1;
  *q = 2;
  return *p;  // should return "1", surely
}

OTOH, both GCC 10+ and Clang 11+ understand this sequence just fine:

bool understood(int *p, int *q) {
  ASSUME(p != q);
  *p = 1;
  *q = 2;
  return (p == q);  // returns "false"
}

so you'd think there's no actual reason they couldn't go on to understand that, if two pointers point different places, then modifying one place can't possibly modify the other. And vice versa, it's ironic that neither GCC nor Clang understand that two independently __restrict'ed pointers can't be equal. It's almost as if both compilers have an internal idea of "aliasing" which is somehow orthogonal to "equaling."