Pointers Are Complicated II, or: We need better language specs

That is not what any compiler writer I know would say, for all compilers I'm aware of assume that casting a pointer to an integer causes the pointer to escape and every integer-to-pointer conversion creates a pointer that may alias any external pointer (including the aforementioned escaping pointers). The problem that's been identified is that this is not sufficient.

If you were to describe the semantics operationally, you'd observe that pointers carry information in them that are more than just the integer address of its location, and this extra information is not saved upon conversion to integer in a naïve semantics. Converting an integer back into a pointer must generate some information for the pointer. A naïve semantics would imply that a pointer-to-integer-to-pointer roundtrip is equivalent to doing nothing at all (on the basis of it all being nops at hardware level), but careful exploration of operational semantics suggests that it is equivalent to clearing that extra information fields, and it is not a valid refinement to fill in that information with a subset of everything.

With LLVM, there is another wrinkle, in that memory is untyped, so effectively every load or store instruction is converting its type to an integer. So LLVM is permitted (and used to until recently, albeit very controversially!) to turn a store (load i8*) into store (load i64), which will introduce inttoptr/ptrtoint into code where the user previously only pointers. (And yes, this has caused optimization problems--I've been bitten by this "bug"). Take the implicit inttoptr literally, and literally every pointer variable in your program escapes because of the presence of the memory inttoptr; ignore the implicit inttoptr entirely and you probably introduce a soundness hole by folding a user inttoptr into the implicit memory one and miss that you actually need one.

Semantics are difficult, even for the people who know what they're doing. A lot of potential pitfalls with semantics aren't apparent until you can find examples of where things go wrong or try to write the optimizations that you intend to write. C++'s experience with relaxed atomics is an example of where something seemingly simple turned out to be more complex than expected, and the issues LLVM has with inttoptr and undefined values are a long-running exercise in "vague, obvious semantics don't work, and most compiler authors aren't prepared to reason about these in a more correct semantic model" (it doesn't help that the LLVM community isn't particularly welcoming towards formalizing their semantic model).

4 Likes

That is not what any compiler writer I know would say, for all compilers I'm aware of assume that casting a pointer to an integer causes the pointer to escape and every integer-to-pointer conversion creates a pointer that may alias any external pointer (including the aforementioned escaping pointers). The problem that's been identified is that this is not sufficient .

It doesn't sound to me like clang is treats pointer-to-int conversions as having release semantics with regard to later int-to-pointe conversions, since if the conversions really were being processed with such semantics, any pointer produced by an integer-to-pointer conversion would be recognized as potentially aliasing every pointer that has leaked.

With LLVM, there is another wrinkle, in that memory is untyped, so effectively every load or store instruction is converting its type to an integer.

So, LLVM needs to include acquire/release notations when the conversions occur as a result of source-code constructs and, until tools that generate LLVM can properly generate such notations, a "force soundness" mode that would sacrifice optimizations for the benefit of people who would prefer a compiler that generates code that's reliably correct, even if it's sub-optimal, to one which generates more "efficient" code that will "probably" work.

(it doesn't help that the LLVM community isn't particularly welcoming towards formalizing their semantic model).

I don't think it would be possible to formalize anything resembling the LLVM semantic model without making some fundamental changes to it first. Such changes would include the abandonment of the idea that optimization must never observably affect the behavior of correct programs, and its replacement with specifications describing when transformations may be generally performed, and what constructs would block them. A program whose behavior might be affected by such transformations could be a correct program if it would meet all its application requirements with any allowable combination of transforms applied.

Consider, for example, the following two language rules: 1. If program would enter a loop whose exit point is statically reachable, but the loop would never terminate, an implementation may behave in arbitrary fashion; 2. If no individual operation within a loop would be observably ordered before any later operation that is statically reachable from it, the execution of the loop or any portion thereof may be reordered with respect to that later operation, or omitted entirely if it is not observably ordered before any observable operation.

If one allows that an implementation may impose a limit on a program's execution time, and raise a signal if it determines that the limit either has been exceeded, or would inevitably be exceeded in the absence of the signal, that would give an implementation license to trap if it happens to detect that it will never escape a particular loop. I can easily imagine situations where it may be useful to have an implementation trap on endless loops that it happens to detect, or where it would be useful to postpone or omit the execution of a loop which would be unable to affect program behavior under any circumstance where it would terminate. Note that if a compiler were given something like:

int test(long long x, int mode)
{
  do 
    { x = no_side_effects(x); }
  while(x & 15);
  if (!mode) return 0;
  return x & 1;
}

Under the latter rules, a compiler would be allowed to generate code that skips the execution of the loop in cases where mode is zero, or that performs the loop unconditionally and then returns zero without bothering to look at the value of mode. If mode is non-zero, however, the read of x within the return statement would be sequenced after its computation within the loop. If a compiler observes that x & 15 is zero, it would be entitled to assume that x & 1 would likewise be zero, but a compiler that postpones the evaluation of x & 15 that would have occurred within the loop would not be entitled to use computations it hasn't performed to justify assumptions about the value of x & 1

The discussions about formalization itself has been moved onto a separate thread, because discussing pointers in the specific and compiler IR and optimization in general in the same topic was getting to be a bit of a tangled read.

6 Likes

Doesn't seem like that powerful of a point to me. Of course if you derive pointers via some invalid means it will potentially have downstream negative effects on the optimizer. This goes for any invalid pointer nonsense:

int n = 5;
int* p = (int*)rand(); // by an impossible coincidence, p now points to n
*p = 2; // now n == 2
printf("%d\n", n); // OPTIMIZATIONS BROKEN!!

@jamesblacklock your example program has UB. The way UB interacts with non-determinism, if any non-deterministic choice leads to UB, then the compiler can assume that this program point is already unreachable. (It needs to make sure that it is consistent about it, which can be tricky, but it can be done.)

Since the program has UB, the optimization doesn't break the program -- it already was broken before.

1 Like

@RalfJung That's my point; the program is broken because of wonky pointer misuse, not because of optimizations. If you decide to do wonky invalid things with pointers, whether that be generating random numbers or reaching past the end of an array, then stuff (including optimizations) is going to break. I could be wrong, but I don't think the C standard even guarantees the layout of variables on the stack. Even if it does, it's a really bad idea to leverage that.

Unless an implementation specifies the behavior of rand() and how it will place n, a program execution where rand() happened to yield the address of n but optimization failed to accommodate that would be indistinguishable from one where rand() had simply yielded some other address. If, however, the program had been something more like:

int n = 5;
int main(void)
{
  uintptr_t pn = 3*(uintptr_t)&n;
  uintptr_t r = rand();
  uintptr_t rn = r*15;
  if (pn == rn)
    (int*)(r*5) = 9;
  printf("%llX %llX %d\n", pn, rn, n);
}

an implementation which doesn't document both how rand() is computed and how static objects are placed would be free to arrange things in such a way that pn and rn could never be equal, in which case it would not have to allow for the possibility that the assignment to (int*)(r*5) would affect n. On the other hand, I don't think an implementation should define uintptr_t (which is an optional type) unless it would treat conversion of a pointer to uintptr_t that may be observed in ways whose consequences the compiler can't fully understood as a potential leak, and a pointer formed by a casting a uintptr_t as a potential alias for any object whose address had leaked. If e.g. r happened to be 0x1110 and the address of n happened to be 0x5550, then whether or not the compiler could see any way by which a programmer might know that the (int*)(r*5) would yield the address of n, it should allow for the possibility that such a thing might occur. I would have no problem with implementations that were incapable of upholding such a guarantee, if they would refrain from defining uintptr_t and intptr_t.

Note that in terms of what the Standard would actually mandates, it requires nothing beyond the fact that if a pointer is round-tripped through uintptr_t and back to its original type, the resulting pointer must compare equal to the original. The Standard specifies nothing about whether an implementation must process any other actions involving the pointer in meaningful fashion, instead leaving that as a Quality of Implementation issue. Some compiler writers interpret the Standard's failure to forbid wacky treatment of a construct as an endorsement of such treatment, but in reality the Standard makes no effort to prevent the creation of "conforming" implementations that are of such garbage quality as to be totally useless, indeed allowing for the possibility that an implementation could be conformign without having to meaningly process any programs that aren't contrived and useless.

Your program is broken because if "wonky pointer misuse". But the first program in my blog post is not, it is only doing things that are explicitly supported in the standard: casting a pointer to an integer, and then casting the very same integer back to a pointer. Nothing wonky happening here.

2 Likes

Looks real wonky to me. Casting an out-of-bounds pointer to an integer. There is no real program where you should ever do this. It is a bug. If this were in a code review, it would be rejected. Is it interesting that it manifests itself in this particular way? Absolutely! But that certainly doesn't make the optimizer broken. It makes your program broken.

Whether or not a program is broken is defined by the specification, not by "do real programs do this". The specification has no objections with this program.

Also, real programs use one-past-the-end ptrs all the time (for iteration loops). I would not be surprised at all if some of them cast those to an integer as well. So I don't buy your assertion that no real program would do this. But it doesn't even matter, since the compiler has to be correct for all programs, not just for those you consider realistic.

4 Likes

Whether or not a program is broken is defined by the specification, not by "do real programs do this". The specification has no objections with this program.

Nothing an implementation does in response to an attempt to dereference a round-tripped pointer could render it non-conforming. An cases where two equal pointers could exist which would be usable only to access disjoint sets of objects, a capricious but conforming implementation could make any conversion of a round-tripped pointer yield a pointer which would compare equal to the original, but would not be usable to access any of the same objects. So in that sense, almost all programs that make use of integer-to-pointer conversions would be "broken" unless they are only intended for use on implementations that uphold guarantees stronger than what the Standard requires.

That having been said, if the example were changed slightly:

#include <stdint.h>
char x[1], y[1] = {0};
int test(unsigned char *p)
{
    uintptr_t ip = (uintptr_t)p;
    uintptr_t iq = (uintptr_t)(x+1);
    y[0] = 123;
    if (iq == ip) {
      *p = 45;
    }
    return y[0];
}

Here the code never dereferences the round-tripped pointer, but clang still processes the code nonsensically.

What's going on is similar to the way clang and gcc treat some goofy corner cases in the Standard involving restrict-qualified pointers, which would cause the C Standard would define the behavior of a construct of the form (someFlag && a || b) && doSomething) when a is 0 (meaning someFlag would be evaluated but doSomething would be unconditionally skipped) or when b is 1 (meaning someFlag would be evaluated but doSomething would be unconditionally executed), and yet not define program behavior in cases where execution of doSomething is conditioned on someFlag. I can't think of any reasonable abstraction model in which the reason for a compiler to decide to execute or skip a piece of code would play any role in determining whether its behavior is defined, but that's how the Standard specifies the behavior of restrict, and clang and LLVM are simply applying the same logic elsewhere.

C or C++? It seems C standard indeed says roundtripping is implementation-defined.

But the C++ standard (of which a draft is available) says:

It looks like the C++ standard does make round-tripping pointers through integers via reinterpret_cast a valid operation. It also does seem that a compiled application formatting the HDD in response to dereferencing a round-tripped pointer would in fact render a C++ compiler which produced such a compilation non-conformant.

What is your point though? My concern is that this topic ongoing may be putting too high a demand on Ralf's time..

In fact I think when a is 0 but b is 1 doSomething should get evaluated.

2 Likes

C or C++? It seems C standard indeed says roundtripping is implementation-defined.

Implementations may at their leisure define round-tripping in useful or useless fashion. The only behavioral requirement given in the Standard is that a round-tripped pointer must compare equal to the original. Is there anything in the Standard that would forbid an implementation from specifying that casting 42 to a char const* will yield a pointer to the string "WHAT DO YOU GET WHEN YOU MULTIPLY SIX BY NINE", but casting any other integer value will yield a pointer value which, even if it would compare equal to other pointers in some cases (including all where the Standard would mandate such behavior), cannot be dereferenced to access anything?

In fact I think when a is 0 but b is 1 doSomething should get evaluated.

Sorry, I should have said when both a and b are zero, but my point is that while one would expect that an the behavior of any particular execution of x && y would always be equivalent to either "execute x and then execute y" or "execute x and don't execute y", the way clang and gcc interpret the Standard means that such an expression could behave in ways which don't match either of the above. If one wants to allow such behavior, it could be be accommodated by an abstraction model which allows transformations based upon program structure, but I don't see any way to accommodate such behavior in an abstraction model that's based purely upon sequential program execution.

I think there is in C++ standard. LLVM being used to compile both C and C++ apparently needs to support a "union" of both standards.

I don't these these details of the C/C++ standard really matter here. The blog post is about the semantics of LLVM IR, and this is a Rust forum, so the rather vague wording of C/C++ around ptr-int-roundtrips is essentially irrelevant except as a way to maybe better understand the semantics of LLVM IR.

It is quite clear that a semantics where round-tripping the pointer doesn't work is useless. So I really have no idea what the point of the discussion here is currently. Is it just that the C/C++ standard is imprecise and vague? I agree, but... so what? None of the posts seem to even discuss the issue that the blog post brings up, so this all seems very far off-topic.

If you want to continue the discussion, please start with a clear problem statement.

I do not have the faintest idea what you are talking about here. If you have a concrete example in mind, please spell it out. There is no restrict-qualified pointer anywhere in the short bits of code you wrote here, so I do not see the connection.

5 Likes

"Also, real programs use one-past-the-end ptrs all the time (for iteration loops)."

AFAICT, this would require runtime evaluation of pointer equality so it wouldn't affect the static optimization being discussed here.

I do understand that while your initial example is contrived, useful code could theoretically have a similar effect. However, I can't imagine what that useful code would actually look like. I could certainly be persuaded that this is a real problem if you were to present a plausible example of this issue in useful code. So far I can't see it, but I'll allow for the possibility of that being my ignorance.

The optimizations just showcase certain features of the underlying operational semantics / Abstract Machine. So just because usually the ptr equality needs to be runtime-evaluated, doesn't make it any easier to solve this problem.

What would solve the problem is to disallow casting one-past-the-end ptrs to integers. But in Rust that's not an option as ptr-to-int casts are a safe operation.

The ability to convert between integers and pointers would be useless if they couldn't be round-tripped meaningfully in ways that would support at least the common use cases. It may be sometimes be useful for an implementation to support round-tripping of pointers in some cases even if would be some situations where such round-tripping wouldn't work as expected. I think the intention of the C Standard was that implementations would process the conversions meaningfully when practical, but they didn't want to brand as non-conforming implementations where some weird contrived corner cases might fail. I wouldn't be surprised if at least one of the Committee members responsible for the C Standard's failure to specify that round-tripped pointers should actually be useful, wanted to avoid characterizing optimizations like the one in your original post "incorrect". If the original program invoked UB, the question of which stage of optimization introduced UB would be moot.

I do not have the faintest idea what you are talking about here. If you have a concrete example in mind, please spell it out. There is no restrict -qualified pointer anywhere in the short bits of code you wrote here, so I do not see the connection.

The basic issue is whether it makes sense to have a language standard forbid any actions within a piece of code which is only executed if certain pointers are in some sense "equal", that would be allowed if the same code were executed unconditionally. The C Standard's definition of restrict, or at least the interpretation shared by clang and gcc, creates such corner cases, and I think that even though your doesn't use restrict, I think the compiler is attempting to broadly apply logic that assumes that if P can't alias some restrict-qualified pointer Q, and within a block of code some pointer R is known to be equal to P, then R can't alias Q either even if it's formed directly from Q, but it isn't limiting such logic to situations where Q is restrict-qualified (in your example it obviously isn't).

Uh, no. The mechanism the third optimization uses is some variation of memory dependence, which is ultimately based on a function called mayAlias, and, in this case, getUnderlyingObject. Because of the incorrect prior optimizations [1], mayAlias(p + 1, q) returns false because the underlying allocations of both pointers are firmly described, and they are different. So the optimizer concludes that p[1] cannot effect the result returned by q[0]. restrict isn't involved in the slightest.

[1] I believe the current majority opinion in the LLVM community is that it's the second optimization that is wrong, i.e., intoptr(ptrtoint(x)) => x is not a valid transformation. Note that, as RalfJung discusses, there are other potential answers to which transformation was incorrect.

3 Likes

This is a theoretical problem only, AFAICT. Is there any real world problem that could arise from this? I can't imagine one. Maybe if there was loop unwinding involved plus iterators checking one past the end? I still don't think this would trigger the issue, because if you were statically unwinding, you wouldn't need to check one past the end. It seems like intentionally deriving an out of bounds pointer is the only way to trigger this, so I remain unconvinced.