Note: these were sent to WG14 as official proposals. See also a longer paper,  something on alias  and Torvalds remarks and Regehr’s paper. 

6.12 Proposal to clarify undefined behavior range for implementations [N 2278]
6.13 Proposal to make aliasing consistent [N 2279]
6.14 Proposal to limit optimization to C semantics [N 2280]

I’m going to write up my experiences at the Pittsburgh meeting when I have time, but it was informative and kind of depressing. Pittsburgh was nice though, and I had a fun visit at U. Pitt and with my old friend from grad school.

 

 

Proposal on Alias

Rationale:

The limitation of lvalue access by types was not properly completed or clarified in the Standard. Neither  temporary change of effective type for “type punning” or type assignment/erasure which is necessary for allocators were clearly specified. The exception for character pointers was added when it was realized that the Standard would otherwise completely prohibit implementation of memcpy.  It still appears to be impossible to write an efficient “memcpy” without optimizer intervention or to write a memory allocator at all in conforming C with the existing Standard. For example: consider an allocator of device local memory in a GPU and how freed objects of one type could be combined or divided and reassigned a new effective type when allocated again – the Standard appears to consider malloc/free as primitives not C implementable library functions. Furthermore, common operations in longstanding common practice, such as using an int type to compute a checksum on a message structure may be forbidden.  

 

Part of the lack of clarity comes from an apparent contradiction in the Standard. Section 6.3.2.3.7 permits a pointer to an object type to be converted to a pointer to a different object type and 6.3.2.1 permits any pointer to be converted to a void pointer type and then converted to any other type but the current language in 6.5.7 seems to imply that dereferencing those pointers may be undefined behavior even if the pointers  are properly aligned – which would make the conversion useless at best.

 

This change is not a complete cure. A memory allocator needs to be able to consolidate or divide objects and the Standard provides no mechanism for that process other than customary practice. Access to the underlying binary representation of a type is a fundamental capability of C programming. There are less complex routes towards helping compilers identify absence of aliasing.

Proposed change

 

7 An object shall have its stored value accessed only by an lvalue expression that has one of the following types:88)

— a type compatible with the effective type of the object,

— a qualified version of a type compatible with the effective type of the object,

— a type that is the signed or unsigned type corresponding to the effective type of the object, — a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,

— an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or

a character type   

 a properly aligned pointer of any object type that has been converted from a valid pointer of the effective  object type.

Proposal on Undefined Behavior.

Rationale:

This Standard’s treatment of “undefined behavior”, like the rest of the Standard, relies on an expectation that implementations are cooperating with the programmer and respecting the C abstract semantics. For example, overflow is undefined behavior, yet  5.1.2.3 Example 6, the Standard limits reordering certain expressions when the implementation produces traps on arithmetic overflows. The purpose of “undefined behavior” is to relieve the translator from the burden of hiding implementation differences and from making safety checks that are the responsibility of the C programmer. Unfortunately, some implementations are interpreting undefined behavior to license arbitrary transformations that violate the abstract semantics.

 

As an example, some implementations will roll-over on arithmetic overflow  but at the same time, delete programmer checks for roll-over as an “optimization” because overflow is “undefined behavior”.  The wording of the Standard does not support this interpretation: “ Hamma Bouziane possible undefined behavior ranges from”

  • ignoring the situation completely  with unpredictable results” – which case the underlying processor architecture might increment in modular arithmetic or trap (which may or may not be handled) or do something else, but the translation “ignore[s] the situation” and produces code without making use of knowledge of any undefined behavior;
  • to behaving during translation in a documented manner characteristic of the environment“;
  • to terminating a translation or execution (with the issuance of a diagnostic message)“.

 

This range is very wide and provides implementations with latitude for optimization but

it does not support conforming implementations that do not ignore the situation but neither behave in a documented manner characteristic of the environment nor terminate the translation and instead produce essentially arbitrary translation..

 

Arbitrary code translation justified by undefined behavior makes C programming a hazardous endeavor where the implementation is full of unpleasant surprises.  Additionally, the more radical interpretations of undefined behavior are causing a fork in the language. Currently, the Linux Operating System requires its translators to respect flags to turn off a number of “optimizations” that are at least partially based on detecting undefined behavior. The existence of these flags and their wide use indicates both that a great deal of existing practice depends on disabling undefined behavior based “optimization”  and that accommodating a more modest use of UB directed translation is acceptable to developers of implementations.

 

It has been argued that permitting implementations to violate the constraints of the abstract machine in the presence of undefined behavior is necessary for high levels of optimization, but there are no published studies validating that claim, and, indeed, the Linux kernel code is highly optimized despite its extensive use of the translator options described in the preceding paragraph.  Limiting UB directed “optimizations” will incentivize implementations to optimize within the C semantics and make C more reliable without requiring the major rewrite of the Standard suggested in https://blog.regehr.org/archives/1180 (which motivated this proposal).

Proposed change.

 

Fiji undefined behavior

1 behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.   Note that the use of a nonportable or erroneous program construct or use of erroneous data should not affect the translation or implementation of conforming constructs in the program or the uses of acceptable data.

 

2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).  This range is exhaustive, not inclusive. Conforming implementations cannot violate semantics of the C abstract machine in conforming program constructs using acceptable data  due to the presence of undefined behavior somewhere else in the program. Use of a nonportable or erroneous program construct should only affect the translation of that construct. By 5.1.2.3.4 “An actual implementation need not evaluate part of an expression if it can deduce that its value is not used “ but merely deducing that undefined behavior follows from use of a value does not allow the implementation to assume that the value is not used.

 

3 EXAMPLE An example of undefined behavior is the behavior on integer overflow.

 

4  EXAMPLE Program constructs that check to see if an integer value has overflowed or an array index is past the limit of the array cannot be deleted or otherwise ignored during translation unless the overflow or out of bounds index is actually impossible in the implementation. 5.1.2.3 applies to conforming program constructs even if other program constructs produce undefined behavior.

 

5 EXAMPLE If the value of the right operand of a shift is negative, the result is undefined but a conforming implementation cannot  deduce that the value of a conforming expression is not negative merely from its use as the right operand of a shift instruction.

 

6 EXAMPLE Code that checks to see if a pointer value is null cannot be omitted during translation solely on the basis that the pointer is dereferenced before the check and that earlier dereference would produce undefined behavior if the pointer value was null.

 

7 NOTE Implementation of  signed integer addition in an environment that generated overflow traps  on overflow follows the specification as would implementations where the addition simply rolled over the integer value. However injecting  for example, an infinite loop that would be software triggered on overflow would not fit into the range of possible undefined behaviors because it would not be “characteristic of the environment” even if documented (as required).

 

Proposal on Optimization

Rationale:

It is specified in the Standard that “optimization” in a conforming implementation must produce behavior that conforms to the semantics of the language.  Advances in optimization technology in translators have lead to the development of multi-pass translators in which semantics of programs can be modified – possibly unintentionally – without some care to preserve semantics over optimization passes. This change calls for conforming implementations to take that care.

 

Proposed change

1 The semantic descriptions in this International Standard describe the behavior of an

abstract machine in which issues of optimization are irrelevant. A conforming implementation may not change semantics of a program as an “optimization” except as described in 5.1.2.3.4

 

Three modest proposals for the C standard WG14
Tagged on:     

One thought on “Three modest proposals for the C standard WG14

Comments are closed.