Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C - is an indeterminate value indeterminable?

According to this post an indeterminate value is:

3.17.2
1 indeterminate value
either an unspecified value or a trap representation

According to google, the definition of indeterminate is:

  • Not certain, known, or established
  • Left doubtful; vague.

According to thefreedictionary, determinable is:

  • capable of being determined

According to merriam-webster, to determine (in the particular context) is:

  • to find out or come to a decision about by investigation, reasoning, or calculation

So, common sense dictates that even though an indeterminate value is unknown during compile time, it is perfectly determinable during runtime, e.g. you can always read whatever happens to occupy that memory location.

Or am I wrong? If so, why?

EDIT: To clarify, I post this in relation to what became a heated argument with a user who attempted to convince me that an indeterminate value is indeterminable, which I very much doubt.

EDIT 2: To clarify, by "determinable" I don't mean a stable or usable value, even if it is a garbage value for uninitialized memory the value of that garbage can still be determined. I mean that trying to determine that value will still yield in some value rather than ... no action. So this value must come from some memory, allocated as storage for the still indeterminate value, I highly doubt a compiler will actually use say a random number generator just for the sake of coming up with some arbitrary value.

like image 952
dtech Avatar asked Jun 30 '13 21:06

dtech


2 Answers

The fact that it is indeterminate not only means that it is unpredictable at the first read, it also means that it is not guaranteed to be stable. This means that reading the same uninitialized variable twice is not guaranteed to produce the same value. For this reason you cannot really "determine" that value by reading it. (See DR#260 for the initial discussion on the subject from 2004 and DR#451 reaffirming that position in 2014.)

For example, a variable a might be assigned to occupy a CPU register R1 withing a certain timeframe (instead of memory location). In order to establish the optimal variable-to-register assignment schedule the language-level concept of "object lifetime" is not sufficiently precise. The CPU registers are managed by an optimizing compiler based on a much more precise concept of "value lifetime". Value lifetime begins when a variable gets assigned a determinate value. Value lifetime ends when the previously assigned determinate value is read for the last time. Value lifetime determines the timeframe during which a variable is associated with a specific CPU register. Outside of that assigned timeframe the same register R1 might be associated with a completely different variable b. Trying to read an uninitialized variable a outside its value lifetime might actually result in reading variable b, which might be actively changing.

In this code sample

{
  int i, j;

  for (i = 0; i < 10; ++i)
    printf("%d\n", j);

  for (j = 0; j < 10; ++j)
    printf("%d\n", 42);
}

the compiler can easily determine that even though object lifetimes of i and j overlap, the value lifetimes do not overlap at all, meaning that both i and j can get assigned to the same CPU register. If something like that happens, you might easily discover that the first cycle prints the constantly changing value of i on each iteration. This is perfectly consistent with the idea of value of j being indeterminate.

Note that this optimization does not necessarily require CPU registers. For another example, a smart optimizing compiler concerned with preserving valuable stack space might analyze the value lifetimes in the above code sample and transform it into

{
  int i;

  for (i = 0; i < 10; ++i)
    printf("%d\n", <future location of j>);
}

{
  int j;

  for (j = 0; j < 10; ++j)
    printf("%d\n", 42);
}

with variables i and j occupying the same location in memory at different times. In this case the first cycle might again end up printing the value of i on each iteration.

like image 166
AnT Avatar answered Oct 18 '22 07:10

AnT


Two successive reads of an indeterminate value can give two different values. Moreover reading an indeterminate value invokes undefined behavior in case of a trap representation.

In a DR#260, C Committee wrote:

An indeterminate value may be represented by any bit pattern. The C Standard lays down no requirement that two inspections of the bits representing a given value will observe the same bit-pattern only that the observed pattern on each occasion will be a valid representation of the value.

[...] In reaching our response we noted that requiring immutable bit patterns for indeterminate values would reduce optimization opportunities. For example, it would require tracking of the actual bit-patterns of indeterminate values if the memory containing them were paged out. That seems an unnecessary constraint on optimizers with no compensatory benefit to programmers.

like image 11
ouah Avatar answered Oct 18 '22 08:10

ouah