Indeterminate Values

It appears from http://www.cl.cam.ac.uk/~pes20/cerberus/notes30.pdf that
future standards may endeavor to say something more useful about Indeterminate
Value than saying that the Standard imposes no requirements about any code
which attempts to use one.  This is certainly a welcome change, since there are
many situations where a piece of code may need to "pass along" information
that may or may not be meaningful to a recipient that may or may not use it(*),
or where code would expect to read a value that may or may not be defined and
then check its validity(**).  Requiring that in such situations a programmer
must include extra code--which an optimizer would in many cases not be able
to filter out--to ensure that only defined values are used would not be an
efficient use of programmer time nor CPU resources.

(*) The calling mode may, for example, be issuing a request through a wrapper
    layer; the calling code would knows which requests are expected to return
    useful information, but the wrapper layer may have no reason to know or
    care about such things.

(**) If the worst-case number of items that will be stored in a hash table
     is bounded but likely to be small, and resizing the table once
     constructed would be undesirable, having each read of an uninitialized
     table entry safely yield an arbitrary number would reduce the time
     required to construct an N-item table from O(N) to O(1).

Although C does not distinguish between kinds of Indeterminate Value, there
are in many implementations two kinds, with different characteristics.  The
indicated draft document recognizes that, but I think it falls short of
fully considering the consequences.

1. If a value is held in a register that is never written before its
   content is used, the value read from that register may not be a value
   of the register's type.  This behavior is not limited to Itanium's NAT
   values, but has in fact been commonplace on many architectures for
   decades.  Consider:

   uint16_t empty(uint32_t x) { }

   Invoking such a function will have will-defined behavior if the caller
   discards the return value.  On many platforms, however, the effect of
   the function would be to return x, even if it's larger than 65535, but
   since calling code won't expect possibility it may skip masking steps
   that would have been necessary if empty were declared as returning
   uint32_t.


    uint32_t wowzers(void)
    {
     uint16_t t = empty(123456);
     uint32_t u = t;
    }

   it would not be uncommon for "u" to end up receiving the value 123456
   even though there is no way that t should have been able to hold a
   a number that large.

   Making the attempted use of empty's return value UB is one way to solve
   the problem, but it can make it difficult to write wrapper functions
   which should have no reason to know or care about whether the called
   function is going to return something meaningful.

   I would suggest that it would be more helpful to recognize the concept
   of a value with contagious indeterminate upper bits, which would mean
   that given something like:

   uint16_t (*proc)(uint32 x);
   uint16_t invoke_if_set(uint32_t x)
   {
     if (!proc) exit(-1);
     return proc(x);
   }

   a compiler should not be required to make the above function return a
   value in the range 0-65535 in cases where proc() fails to do so, but
   if code that calls invoke_if_set ignores its return value, behavior
   should be fully defined whether or not proc() returns a value.


2. The main situations where Indeterminate Value (rather than Unspecified)
   is relevant for values stored in memory occurs when part of storage is
   accessed by reads and writes which the compiler regards as unsequenced.
   In cases where storage is written as one type and read as another, and
   where the semantics of the read would suggest that it would yield
   Indeterminate Value, an optimizer might reorder code so that the write
   is actually executed after the read.  As a consequence, a subsequent
   reads may yield a value different from the first.

   While such optimizations are often useful, and while there are reasons
   for indeterminate values produced thereby to be somewhat "contagious",
   I would suggest that the proposed semantics are looser than would be
   necessary to enable useful optimizations.  What I would suggest instead
   would be to say that certain operations are guaranteed to always yield
   a concrete value, while others may, at the compiler's leisure, act as
   lazy evaluators.  Thus, given

      uint32_t *p1 = malloc(4); uint16_t v1=(*p1)>>8;
      uint32_t *p2 = malloc(4); uint16_t v2=(*p2)>>8;
      uint32_t v1v2a = v1+v2;
      uint32_t v1v2b = v1v2a;
      uint32_t c1 = v1v2b > 0x01FFFFFD;
      uint32_t c2 = v1v2b > 0x01FFFFFE;

   a compiler would be allowed to treat v1 as holding (INDETERMINATE)>>8,
   and likewise v2, v1v2a as ((INDETERMINATE)>>8)+((INDETERMINATE)>>8),
   and v1v2b likewise.  Since v1v2b could be as large as 0x1FFFFFE, the
   first conditional could arbitrarily yield 0 or 1 at the compiler's
   leisure, but since it could not be larger than 0x1FFFFFFE, the second
   conditional must return false.

Another point I failed to see mentioned is that while the draft suggests
that it would be possible to write a function which would convert
Indeterminate Value to Unspecified Value while leaving other values
unaffected, e.g.

    uint32_t sanitize_uint32(uint32_t x)
    {
      uint32_t result = 0;
      if (x & 0x00000001) result |= 0x00000001;
      if (x & 0x00000002) result |= 0x00000002;
      ...
      if (x & 0x40000000) result |= 0x80000000;
      if (x & 0x80000000) result |= 0x80000000;
      return result;
    }

and such a function would clearly yield a concrete output no matter how
many times "x" might change during its evaluation, it would clearly not
be reasonable to require that a programmer use such a function any time
it needs to copy a possibly-Indeterminate Value to a variable and be able
to treat that variable as holding a deterministic number, especially given
that such a conversion should often require zero instructions and should
very seldom cost more than two [the typical worst-case scenario would
entail making a copy of what a storage location held at a particular
moment in time, and using the copied at multiple points later in the
program rather than having the places in the program that use the value
later fetch the original].

In a good programming language, useful operations that can be done cheaply
machine code should be achievable cheaply within the language.  Being
able to convert possibly-Indeterminate values into values that are, at worst,
Unspecified, should certainly qualify.