flatfinger · HackerTrans

flatfinger

no profile record

comments

6 năm trướcdiscuss

In many cases, the semantics programmers would require are much looser than anything provided for by the Standard. For example, if a programmer requires an expression that computes (x \* y / z) when there is no overflow, and computes an arbitrary value with no side effects when there is an overflow, a programmer could write the expression with unsigned and signed casting operators, but that would force a compiler generate machine code to actually perform the multiplication and division even in cases where it knows that y will always be twice z. Under "yield any value with no side effects" semantics, a compiler could replace the expression with (x \* 2), which would be much faster to compute.

6 năm trướcdiscuss

There are many cases where accommodating weird corner cases would be expensive, and would only be useful for some kinds of program. Requiring that all implementations intended for all kinds of task handle corner cases that won't be relevant for most kinds of tasks would needlessly degrade efficiency. The problem is that there's no way for programs to specify which corner cases they do or don't need.

6 năm trướcdiscuss

> Yes, clearly.

Unfortunately, the C Standard doesn't specify an abstraction model that is amenable to the optimization of usable programs.

> In that case, I'm not sure what we're even arguing about; the language standard might or might not standardize a way of specifying said waiver, but as long as it's not lumped in with -On or -std=blah that are necessary to get a proper compiler, it has no bearing on real-world programmers that're just trying get working code. Hell, I'd welcome a -Ounsafe or whatever, just to see what sort of horrible mess it makes, as long -Ono-unsafe exists and is the default.

The only reason for contention between compiler writers and programmers is a desire to allow compilers to optimized based upon the assumption that a program won't do certain things. The solution to that contention would be to have a means of inviting optimizations in cases where they would be safe and useful, analogous to what `restrict` would be if the definition of "based upon" wasn't so heinously broken.

6 năm trướcdiscuss

> With, I presume, a eye toward further producing: x.a[dat[i]] = i; y.a[dat[i]] = i;

Bingo.

> I assume you mean zero-extending; otherwise `x=255` would result in `result=-1`, which is clearly wrong.

Naturally.

> None of this involves that the compiler infering objective (and frequently false) properties of the input program (such as "this loop will terminate" or "p != NULL"), though.

Thus the need to use an abstraction model which allows optimizations to alter observable aspects of a program whose behavior is, generally, defined. I wouldn't describe such things as "behavior characteristic of the environment", though the environment would affect the ways in which the effects of optimizations might be likely to manifest themselves.

Note that programs intended for different tasks on different platforms will benefit from slightly--but critically--different abstraction models, and there needs to be a way for programs to specify when deviations from the "load/store machine model" which would normally be acceptable, aren't. For example, there should be a way of indicating that a program requires that automatic objects always behave as though initialized with Unspecified rather than Indeterminate Value.

A good general-purpose abstraction model, however, should allow a compiler to make certain assumptions about the behaviors of constructs, or substitute alternative constructs whose behaviors would be allowed to differ, but would not allow a compiler to make assumptions about the behaviors of constructs it has changed to violate them.

Consider, for example:

    typedef void proc(int);  // Ever seen this shorthand for prototypes?
    proc do_something1, do_something2, do_something3;

    void test2(int z)
    {
      if (z < 60000) do_something3(z);
    }

    int q;
    void test1(int x)
    {
      q = x*60000/60000;
      if (q < 60000) do_something1(q);
      int y = x*60000/60000;
      if (y < 60000) do_something2(y);
      test2(y);
    }

Under a good general-purpose model, a compiler could generate code that could never set q to a value greater than INT_MAX/60000, and a 32-bit compiler that did so could assume that q's value would always be in range and thus omit the comparison. A compiler could also generate code that would simply set q to x, but would forfeit the right to assume that it couldn't be greater than INT_MAX/60000.

There could be optimization value in allowing a compiler to treat automatic objects "symbolically", allowing the second assignment/test combination to become:

      if (x*60000/60000 < 60000) 
        do_something2(x*60000/60000);

even though the effect of the substituted expression might not be consistent. I wouldn't favor allowing inconsistent substitutions by default, but would favor having a means of waiving normal behavioral guarantees against them for local automatic objects whose address is not taken. On the other hand, there would need to be an operator which, when given an operand with a non-determinisitic value, would choose in Unspecified fashion from among the possibilities; to minimize security risks that could be posed by such values, I would say that function arguments should by default behave as though passed through that operator.

The guiding principle I would use in deciding that the value substitution would be reasonable when applied to y but not q or z would be that a programmer would be able to see how y's value is assigned, and see that it could produce something whose behavior would be "unusual", but a programmer looking at test2() would have no reason to believe such a thing about z.

6 năm trướcdiscuss

Replying to the code [discussed deeper in this sub-thread]:

    struct blob { uint16_t a[100]; } x,y,z;
  
    void test2(void)
    {
      int indices[] = {1,0};
      {
        int* dat = indices;
        int n = 2;
        {
          struct blob temp;
          for(int i=0; i<n; i++) 
            temp.a[dat[i]] = i; // This is what I'd meant
          x=temp;
          y=temp;
        }
        z=x;
      }

The rewrite sequence I would envision would be:

    struct blob { uint16_t a[100]; } x,y,z;
  
    void test2(void)
    {
      int indices[] = {1,0};
      {
        int* dat = indices;
        int n = 2;
        {
          struct blob temp1 = x; // Allowed initial value
          struct blob temp2 = y; // Allowed initial value
          for(int i=0; i<n; i++)
          {
            temp1.a[dat[i]] = i;
            temp2.a[dat[i]] = i;
          }
          x=temp1;
          y=temp2;
        }
        z=x;
      }

Compilers may replace an automatic object whose address is not observable with two objects, provided that anything that is written to one will be written to the other before the latter is examined (if it ever is). Such a possibility is the reason why automatic objects which are written between "setjmp" and "longjmp" must be declared "volatile".

If one allows a compiler to split "temp" into two objects without having to pre-initialize the parts that hold Indeterminate Value, that may allow more efficient code generation than would be possible if either "temp" was regarded as holding Unspecified Value, or if copying a partially-initialized object as classified as "modern-style Undefined Behavior", making it necessary for programmers to manually initialize entire structures, including parts whose values would otherwise not observably affect program execution.

The optimization benefits of attaching loose semantics to objects of automatic duration whose address is not observable are generally greater than the marginal benefits of attaching those semantics to all objects. The risks, however, are relatively small since everything that could affect the objects would be confined to a single function (it an object's address is passed into another function, its address would be observable during the execution of that function).

BTW, automatic objects whose address isn't taken have behaved somewhat more loosely than static objects even in compilers that didn't optimized aggressively. Consider, for example:

    volatile unsigned char x,y;
    int test(int dummy, int mode)
    {
      register unsigned char result;
      if (mode & 1) result = x;
      if (mode & 2) result = y;
      return result;
    }

On many machines, if an attempt to read an uninitialized automatic object whose address isn't taken is allowed to behave weirdly, the most efficient possible code for this function would allocate an "int"-sized register for "result", even though it's only an 8-bit type, do a sign-extending load from `x` and/or `y` if needed, and return whatever happens to be in that register. That would not be a complicated optimization; in fact, it's a simple enough optimization that even a single-shot compiler might be able to do it. It would, however, have the weird effect of allowing the uninitialized "result" object of type "unsigned char" to hold a value outside the result 0..255.

Should a compiler be required to initialize "result" in that situation, or should programmers be required to allow for the possibility that if they don't initialize an automatic object it might behave somewhat strangely?

6 năm trướcdiscuss

The indent is getting rather crazy on this thread; I'll reply further up-thread so as to make the indent less crazy.

6 năm trướcdiscuss

Yeah, I meant `slow_function_no_side_effects(x)`. My point is that there's a huge difference between saying that a compiler need not treat a loop as sequenced with regard to outside code if none of the operations therein are likewise sequenced, versus saying that if a loop without side effects fails to terminate, compiler writers should regard all imaginable actions the program could perform as equally acceptable.

In a broader sense, I think the problem is that the authors of the Standard have latched onto the idea that optimizations must not be observable unless a program invokes Undefined Behavior, and consequently any action that would make the effects of an optimization visible must be characterized as UB.

I think it would be far more useful to recognize that optimizations may, on an opt-in or opt-out basis, be allowed to do various things whose effects would be observable, and correct programs that would allow such optimizations must work correctly for any possible combination of effects. Consider the function:

    struct blob { uint16_t a[100]; } x,y,z;

    void test1(int *dat, int n)
    {
      struct blob temp;
      for (int i=0; i<n; i++)
        temp.a[i] = i;
      x=temp;
      y=temp;

    }
    void test2(void)
    {
      int indices[] = {1,0};
      test1(indices, 2);
      z=x;
    }

Should the behavior of test2() be defined despite the fact that `temp` is not fully written before it is copied to `x` and `y`? What if anything should be guaranteed about the values of `x.a[2..99]`, `y.a[2..99]`, and `z.a[2..99]`?

While I would allow programmer to include directives mandating more precise behavior or allowing less precise behavior, I think the most useful set of behavioral guarantees would allow those elements of `x` and `y` to hold arbitrarily different values, but that `x` and `z` would match. My rationale would be that a programmer who sees `x` and `y` assigned from `temp` would be able to see where `temp` was created, and would be able to see that some parts of it might not have been written. If the programmer cared about ensuring that the parts of `x` and `y` corresponding to the unwritten parts matched, there would be many ways of doing that. If the programmer fails to do any of those things, it's likely because the programmer doesn't care about those values.

The programmer of function `test2()`, however, would generally have no way of knowing whether any part of `x` might hold something that won't behave as some possibly-meaningless number. Further, there's no practical way that the author of `test2` could ensure anything about the parts of `x` corresponding to parts of `temp` that don't be written. Thus, a compiler should not make any assumptions about whether a programmer cares about whether `z.a[2..99]` match `x.a[2..99]`.

A compiler's decision to optimize out assignments to `x[2..99]` and `y[2..99]` may be observable, but if code would not, in fact, care about whether `x[2..99]` and `y[2..99]` match, the fact that the optimization may cause the arrays to hold different Unspecified values should not affect any other aspect of program execution.

6 năm trướcdiscuss

What should be relevant is not programmer "intent", but rather whether the behavior would likely match the that of an implementation which give that describe behavior of actions priority over parts of the Standard that would characterize them as "Undefined Behavior".

6 năm trướcdiscuss

Has there ever been any consensus as to what that "...or is copied as an array of character type..." text is supposed to mean, or what sort of hoops must be jumped through for a strictly conforming program to generate an object whose bit pattern matches another without copying the effective type thereof?

6 năm trướcdiscuss

The ability to use pointers to structures with a Common initial Sequence goes back at least to 1974--before unions were invented. When C89 was written, it would have been plausible that an implementation could uphold the Common Initial Sequence guarantees for pointers without upholding them for unions, but rather less plausible that implementations could do the reverse. Thus, the Standard explicitly specified that the guarantee is usable for unions, but saw no need to redundantly specify that it also worked for pointers.

If compilers would recognize that operation involving a pointer/lvalue that is freshly visibly based on another is an action that at least potentially involves the latter, that would be sufficient to make code that relies upon the CIS work. Unfortunately, some compilers are willfully blind to such things.

6 năm trướcdiscuss

How about allowing `return` to be used as a qualifier within a function or prototype's argument which, if present, would adjust the qualifiers of the function's return value to match those of the argument, e.g. adding "const" or removing "volatile" as appropriate?

This, if one did:

    char *strchr2(char return *restrict src, char target)
    {
      while(*src)
      {
        if (*src == target) return src;
        src++;
      }
    }

then one version of the function could support both const and non-const usage. BTW, I'd also like to see "register" and "return register" be usable as a qualifiers for pointer-type function parameters which would promise that the passed in pointer wouldn't "escape", or else that it could only escape through the return value (so a compiler that could see everything done with the return value wouldn't have to worry about the argument escaping).

6 năm trướcdiscuss

Functions like malloc are only required for hosted implementations. Many operating systems are built using freestanding implementations.

Further, on many platforms, one should avoid using malloc() unless portability is more important than performance or safety. Some operating systems support useful features like the ability to allocate objects with different expected lifetimes in different heaps, so as to help avoid fragmentation, or arrange to have allocations a program can survive without fail while there is still enough memory to handle critical allocations. Any library that insists upon using "malloc()" will be less than ideal for use with any such operating system.

6 năm trướcdiscuss

> This won't work because defective implementations will just claim that their intended purpose is to do [whatever emergent behaviour that implementation produces], or to generate the fastest code possible regardless of whether that code bears any relation to what the programmer asked for.

I would have no qualm with the way clang and gcc process various constructs if they were to explicitly state that its maintainers make no effort to make their optimizer suitable for any tasks involving the receipt of untrustworthy input. Instead, however, they claim that their optimizers are suitable for general-purpose use, despite the fact that their behavior isn't reliably suitable for many common purposes.

> This is actually completely unneeded, even for optimisation.

Consider the following function:

    unsigned long long test(unsigned long long x, int mode)
    {
      do
        x = slow_function_no_side_effects();
      while(x > 1);
      if (mode)
        return 1;
      else
        return x;
    }

Suppose the function is passed a value of "x" which would get caught in a cycle that never hits zero or one, but "mode" is 1. If the code is processed by performing every individual step in order, the function would never return. The rule in C11 is designed to avoid requiring that generated code compute the value of x when its only possible effect on the program's execution would be to prevent the execution of code that doesn't depend on its value.

Suppose the most important requirement that function test() must meet is that it must never return 1 unless mode is 1, or the iteration on x would yield 1 before it yields zero; returning 1 in any other cases would cause the computer's speaker to start playing Barney's "I love you" song, and while looping endlessly would be irksome, it would be less bad than Barney's singing. If a compiler determines that slow_function_no_side_effects() will never return an even number, should it be entitled to generate code that will return 1 when mode is zero, without regard for whether the loop actually completes?

I would think it reasonable for a compiler to defer/skip the computation of x in cases where mode is 1, or for a compiler that can tell that "x" will never be an even number to generate code that, after ensuring that the loop will actually terminate, would unconditionally return 1. Requiring that the programmer write extra code to ensure that the function not return 1 in cases where mode is zero but the loop doesn't terminate would defeat the purpose of "optimization".

6 năm trướcdiscuss

> If I understand correctly, that would actually be "implementation-defined", not "undefined".

That is an extremely common myth. From the point of view of the Standard, the difference between Implementation Defined behavior and Undefined Behavior is that implementations are supposed to document some kind of behavioral guarantee with regard to the former, even in cases where it would be impractical for a particular implementation to guarantee anything at all, and nothing that implementation could guarantee in those cases would be useful.

The published Rationale makes explicit an intention that Undefined Behavior, among other things, "identifies areas of conforming language extension".

> There are size-specific integer types specified in the C99 standard (e.g. `uint32_t`). I use those, except in the most trivial cases (e.g. `int main()`), and limit myself to those size-specific integer types that are "guaranteed" by the standard.

A major problem with the fixed-sized types is that their semantics are required to vary among implementations. For example, given

    int test(uint16_t a, uint16_t b, uint16_t c) { return a-b > c }

some implementations would be required to process test(1,2,3); so as to return 1, and some would be required to process it so as to return 0.

Further, if one has a piece of code which is written for a machine with particular integer types, and a compiler which targets a newer architecture but can be configured to support the old set of types, all one would need to do to port the code to the new platform would be to add a directive specifying the required integer types, with no need to rework the code to use the "fixed-sized" types whose semantics vary among implementations anyway.

6 năm trướcdiscuss

See post above. There is no good way for compilers to handle that case, but gcc gets "creative" even in cases where the authors of C89 made their intentions clear.

6 năm trướcdiscuss

I can't really blame gcc for that one, since the most straightforward way of using signed integer arithmetic would yield a negative value if the result is bigger than INT_MAX, but it would be very weird that programs would expect and rely upon that behavior.

On the other hand, even the function "unsigned mul_mod_65536(unsigned short x, unsigned short y) { return (x * y) & 0xFFFF; }" which the authors of the Standard would have expected commonplace implementations to process in consistent fashion for all possible values of "x" and "y" [the Rationale describes their expectations] will sometimes cause gcc to jump the rails if the arithmetical value of the product exceeds INT_MAX, despite the fact that the sign bit of the computation is ignored. If, for example, the product would exceed INT_MAX on the second iteration of a loop that should run a variable number of iterations, gcc will replace the loop for code that just handles the first iteration.

6 năm trướcdiscuss

It's too bad Unicode wasn't designed around the concept of easily-recognizable grapheme clusters and "write-only" [non-round-trip] forms that are normalized in various ways. A text layout engine shouldn't have to have detailed knowledge of rules that are constantly subject to change, but if there were a standard representation for a Unicode string where all grapheme clusters are marked and everything is listed in left-to-right order, and an OS function was available to convert a Unicode string into such a form, a text-layout using that OS routine would be able to accommodate future additions to the character set and and glyph-joining rules without having to know anything about them.

6 năm trướcdiscuss

A conforming implementation could extend the language with an 8-bit type __nonaliasingbyte which has no special aliasing privileges, and define uint8_t as being synonymous with that type.

On the other hand, the Standard should never have given character types special aliasing rules to begin with. Such rules would have been unnecessary if the Standard had noted that an access to an lvalue which is freshly visibly derived from another is an access to the lvalue from which it is derived. The question of whether a compiler recognizes a particular lvalue as "freshly visibly derived" from another is a Quality of Implementation issue outside the Standard's jurisdiction.

6 năm trướcdiscuss

If the Standard were to make recursion an optional feature, many programs' stack usage could be statically verified. Indeed, there are some not-quite-conforming compilers which can statically verify stack usage--a feature which for many purposes would be far more useful than support for recursion.

6 năm trướcdiscuss

If a compiler decides that it's going to process:

    unsigned mul(unsigned short x, unsigned short y)
    { return x*y; }

in a way that causes calling code to behave in meaningless fashion if x would exceed INT_MAX/y [something gcc will sometimes actually do, by the way, with that exact function!], the hardware isn't going to have any say in that.