Interaction Faults (in order of presentation)

GCC Bug 41643

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: The optimization pass for eliminating tail recursion (an optional feature implemented in tree-tailcall.c) contains the function tree_optimize_tail_calls_1, which as its first step must ensure that the first basic block in the function being optimized contains a lone predecessor and no phi nodes. Before the fix, it would check the first block for predecessor blocks; if it found more than one, it would split to function's entry edge into two edges: one from the entry vertex to a new empty basic block, and one from the new block to the block that was formerly first. Thus, it would guarantee that the new first basic block has only one predecessor. However, as the check was written this is not enough to guarantee the absence of phi nodes, because the earlier passes could still create degenerate phi nodes (phi nodes that stand for only one definition) without giving the first basic block multiple predecessors. Under normal circumstances, the dead code elimination (DCE) pass (another optional feature) would clean up degenerate phi nodes, but tree_optimize_tail_calls_1 should have been prepared to handle them in the case where DCE was disabled. The fix works by checking not only for multiple predecessors, but also for phi nodes, and splitting the entry edge on either condition.

Summary: An optional feature depended on another optional feature to ensure its preconditions.

GCC Bug 39794

Links: Bug Report, Fix Comment, Fix Commit, Major Code Changes 1 and 2, Minor Code Changes 1, 2, 3, and 4, and Test Case

Explanation: Before the fix, the global dead store elimination (DSE) pass, an optional feature, was checking for conflicts by comparing register transfer language expressions, but without consideration for changes to register values between the points where the expressions appeared. Thus, two expressions might appear to be non-conflicting when in fact the differences in their offsets are made up for by intervening stores, or conflicting when the only difference is one introduced by an intervening store. DSE could protect irrelevant instructions (which is harmless except for missed optimization opportunities), or eliminate stores that are not really dead. The fix added code to properly canonicalize the addresses' representations before they were compared, thereby eliminating the assumption of unchanging register contents.

Summary: Under certain feature combinations an optional feature needed to read information produced in earlier passes (the information for canonicalizing the addresses), but it did not.

GCC Bug 40087

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: According to the C standard, certain operations like pointer arithmetic and arithmetic on signed integers are undefined if they would overflow; a compiler may assume that these operations do not overflow and optimize accordingly. Before the fix, loops like the one in the test case could be infinite only in the case of overflow, so an optional GCC feature would set a flag indicating that the loop was finite. But later, in another optional feature, that flag was being taken to mean that the conditional exit introduced by the do, the while, or the for is the one taken, when in fact the program might exit the loop through a break or exceptional control flow. The fix eliminates the conflation, except of course when the loop is know to have only one exit.

Summary: The information produced by one feature was interpreted with different semantics in another, meaning that the latter's assumptions could be violated.

Non-Interaction Faults (in numerical order)

GCC Bug 40321

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Cases 1 and 2

Explanation: Before the fix, GCC's data flow analysis to compute anticipated expressions (part of partial redundancy elimination, an optional feature) was not including phi nodes in its maximal set. Consequently, when a phi was anticipated, so were its arguments, which could in turn be other phi nodes, etc., possibly even forming a cycle. In such cases GCC would loop forever. The fix added phi nodes to the maximal set so that the analysis could realize that a phi node had already been detected as anticipated, rather than retranslating it.

Summary: The fault was confined to an optional feature.

GCC Bug 40389

Links: Bug Report, Fix Comments 1 and 2, Fix Commits 1 and 2, Code Changes 1, 2, 3, and 4, and Test Case

Explanation: The test case involved a doubly linked-list where one structure is used for vertices, and another list structure pairs the head and tail pointers. The vertices, besides keeping previous and next pointers also maintained pointers to their owning list structure. Additionally there was a function to create and return a new vertex, adding it to a list by passing that list's pointer to the vertex constructor. Before the fix, GCC was returning values from this function (the callee) by invisible reference, but then the following happened:

  1. The caller allocated space for the return value because the return was by invisible reference.
  2. The callee called the vertex constructor to construct the return value.
  3. The vertex's this pointer escaped from the constructor when it was stored in the list's head and tail pointers.
  4. The callee returned; the return value was still live because it still needed to be copied.
  5. The return value was copied by invoking the vertex class's assignment operator (at this point some fields of the return value were cached in registers because of an optional optimization, scalar replacement of aggregates [SRA]).
  6. The copy operation caused the vertex being copied to to be inserted in the linked list, thus changing the return value's next pointer.
  7. The return value was destroyed, triggering an inlined call to remove the return value from the linked list.
  8. But the call, being inlined, used the cached values: the list's head pointer should have been copied from the updated next pointer. Instead, it was null.

The SRA pass was correct given the information it was receiving. The fix informed it of cases where an object returned by invisible reference could have its address escape.

Summary: The fault was confined to an optional feature.

GCC Bug 41016

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Summary: The fault was confined to an optional feature.

GCC Bug 41094

Links: Bug Report, Fix Comment, Fix Commit, Code Change, Test Case, and Test Case Corrections 1, and 2

Explanation: Before the fix GCC was changing (xy)z to x(yz) as part of its optional fast math optimization. But for expressions with a negative base, like ((-4)2)1/4, this gives (-4)1/2, a NaN, rather than 161/4, two. The fix introduced a sign check into the fast math feature.

Summary: The fault was confined to an optional feature.

GCC Bug 41183

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: In interprocedural constant propagation, an optional feature, GCC would clone functions to specialize them for the propagated constants. The cloning functions did not copy all of the function annotations: in particular, source-language-specific fields were not copied. Later, when a function created by template instantiation needed its name to be mangled late in the compilation process, the mangler assumed the availability of these structures because it is usually invoked from the front-end. The fix chosen was to check for a null pointer before the dereference, though copying the source-language-specific fields was also a proposed alternative.

Summary: Common code was assuming data not provided by an optional feature.

GCC Bug 41403

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Cases and 2

Explanation: A legality check for an outdated Fortran construct depended on distinct code labels having distinct addresses. Any optimization that collapsed two labels into each other would break this assumption and the check would hang. Rather than fixing the invalid assumption, the developers simply deleted the offending legality check.

Summary: a common feature was built with preconditions many optional features could not reasonably fulfill.

GCC Bug 41843

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: The structure reorganization optimization, an optional feature, would mistakenly consider two structures to be equivalent if for every field in one it could find a matching field in the other. It should have tested both for extra fields in the second structure, as well as agreement on the fields' ordering.

Summary: The fault was confined to an optional feature.

GCC Bug 41917

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: For the phases where a program is represented in register transfer language (RTL), GCC maintains information to the side about each RTL expression: which bits are known to be zero, and how many high-order bits are known to be the same as the sign bit, among other things. These annotations are used to ensure the correctness of RTL rewrites. Before the fix, GCC would determine the number of sign bit copies in the result of an unsigned mod operation based on the intuition that the number of high-order zeros is at least the number of high-order zeros in the modulus. But if the modulus has a nonzero sign bit, the number of zeros says nothing about the number of sign bit copies. The fix added checks for the possibility of the modulus sign bit being set.

Summary: The fault involved an optional feature and common code.

GCC Bug 42049

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: GCC can specially compile some common utility functions, called built-ins, rather than using an actual function call. After constant propagation, the built-in strcpy was sometimes rendered as the evaluation of a compound expression (an expression made up of subexpressions separated by C's comma operator), which before the fix was not considered as a possibility. Therefore GCC crashed when it tried to continue expanding the compound expression monolithically. The fix expanded each of the subexpressions separately and used only the last as strcpy's result.

Summary: The fault was confined to an optional feature.

GCC Bug 42231

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: GCC's interprocedural constant propagation looks for arguments that always have the same value, regardless of call site. It works in three phases: identifying how arguments are passed at each call site, seeing which arguments are always a particular constant, and cloning the functions taking these arguments, substituting the constants. But when the arguments are function pointers invoked in the callee, the cloning process can infer a edge in the call graphs that it could not before, and it does not redo the analysis to see if the newly known call also passes the constant(s) identified in the second phase. Thus, before the fix, it could rewrite the call through the function pointer to point to a wrongly specialized clone. The fix tagged new call graph edges and prevented them from calling the clones generated by the constant propagation.

Summary: The fault was confined to an optional feature.

GCC Bug 42542

Links: Bug Report, Fix Comments 1, 2, and 3, Fix Commits 1, 2, and 3, Code Changes 1, 2, 3, 4, and 5, and Test Cases 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12

Explanation: When vectorizing for some architectures with only the signed version of a vector greater-than operation, GCC was emitting the same operation code for both signed and unsigned comparisons. The fix added a conditional on signedness and the code to emulate an unsigned comparison with the signed operator.

Summary: The fault was confined to an optional feature.

GCC Bug 42614

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Summary: The fault was confined to an optional feature.

GCC Bug 42667

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: The GCC built-in strlen contained a hard-coded return type, size_t. But it is legal for the input source to override the return type by giving a prototype of its own. Before the fix the return type from the prototype was not being propagated to the code for constant folding with built-ins, so a constant string reaching a wrongly prototyped strlen would result in invalid Gimple. An optional feature, partial redundancy elimination, detected the type mismatch in an assertion.

Summary: The fault was in common code, but manifested as a failure in an optional feature.

GCC Bug 43024

Links: Bug Report, Fix Comment, Fix Commit, Code Change, and Test Case

Explanation: This is essentially the same as 41183, except that the binding contour was the field not copied.

Summary: Common code was assuming data not provided by an optional feature.