Authors
Theodoros TheodoridisZhendong Su
Topics
Parallel Computing and Optimization TechniquesLogic, programming, and type systemsAdvanced Malware Detection TechniquesAuthor(s): Theodoridis, Theodoros; Su, ZhendongPermanent link: https://doi.org/10.3929/ethz-b-000680791Rights / license: Creative Commons Attribution 4.0 InternationalOriginally published in: Proceedings of the ACM on Programming Languages 8(PLDI), https://doi.org/10.1145/3656404This page was generated automatically upon download from the ETH Zurich Research Collection. For more information, please consult the Terms of use.THEODOROS THEODORIDIS, ETH Zurich, Switzerland ZHENDONG SU, ETH Zurich, Switzerland To optimize a program, a compiler needs precise information about it. Significant effort is dedicated to improving the ability of compilers to analyze programs, with the expectation that more information results in better optimization. But this assumption does not always hold: due to unexpected interactions between compiler components and phase ordering issues, sometimes more information leads to worse optimization. This can lead to wasted research and engineering effort whenever compilers cannot efficiently leverage additional information. In this work, we systematically examine the extent to which additional information can be detrimental to compilers. We consider two types of information: dead code, i.e., whether a program location is unreachable, and value ranges, i.e., the possible values a variable can take at a specific program location. Given a seed program, we refine it with additional information and check whether this degrades the output. Based on this approach, we develop a fully automated and effective testing method for identifying such issues, and through an extensive evaluation and analysis, we quantify their existence and prevalence in widely used compilers. In particular, we have reported 59 cases in GCC and LLVM, of which 55 have been confirmed or fixed so far, highlighting the practical relevance and value of our findings. This work’s fresh perspective opens up a new direction in understanding and improving compilers. CCS Concepts: • Software and its engineering → Compilers. Additional Key Words and Phrases: Missed Compiler Optimizations, Automated Compiler Testing ACM Reference Format: Theodoros Theodoridis and Zhendong Su. 2024. Refined Input, Degraded Output: The Counterintuitive World of Compiler Behavior. Proc. ACM Program. Lang. 8, PLDI, Article 174 (June 2024), 21 pages. https: //doi.org/10.1145/3656404 1 INTRODUCTION Compilers are complex systems with hundreds of “moving parts”. An optimizing compiler must simultaneously understand the semantics of an input program using many different analyses [9, 14, 15, 21], and transform it into an equivalent program that is more efficient to execute. This process requires hundreds or even thousands of interdependent transformation steps [1, 2, 25]. Naturally, a compiler may fail to properly optimize a program, e.g., due to phase ordering issues [33], unexpected interactions between its components [7], or missing analyses and optimizations [3, 6]. However, as users of a compiler, we expect it to behave consistently. If, for example, it can optimize a code snippet well in one program, we expect similar results if the same snippet occurs in another program. Similarly, a newer compiler version should optimize a given program at least as well as an older version of the same compiler. Furthermore, we expect that a compiler does better given additional program information, similarly to Listing 1 where GCC generates better code by leveraging the given hint.Authors’ addresses: Theodoros Theodoridis, ETH Zurich, Zurich, Switzerland, theodoros.theodoridis@inf.ethz.ch; Zhendong Su, ETH Zurich, Zurich, Switzerland, zhendong.su@inf.ethz.ch.© 2024 Copyright held by the owner/author(s). ACM 2475-1421/2024/6-ART174 https://doi.org/10.1145/3656404This work is licensed under a Creative Commons Attribution 4.0 International License.int foo ( int x , int y ) { if ( x == y ) return 0; if ( x > y ) return 1; else return -1;} int bar ( int x , int y ) { return foo (x , y ) ; (a) Original code bar : xorl %eax , % eax cmpl %esi , % edi je .L6 # x == y setg %al # x > y movzbl %al , % eax leal -1(% rax ,% rax ) ,% eax .L6 : ret (b) Generated ASM int bar ( int x , int y ) { // We know that // x > = y and // make it obvious // to the compiler if (!(x >= y)) __builtin_unreachable(); return foo (x , y ) ;}(c) Refined code bar : xorl %eax , %eax cmpl %esi , %edi setne %al # x < y ret (d) Refined ASMListing 1. Consistent behavior example: GCC 13 -O3 generates simpler code given the additional information. In the original assembly code (Listing 1b) two conditional instructions are used to determine the return value je .L6 and setg .L7: (1) je .L6 implements the x == y check by jumping to the return statement if the previous comparison result (cmpl %esi, %edi) is “equal”, the return value is 0 (which set by initially xor-ing %eax with itself), (2) setg .L7 implements the x > y check by se ing the return value to 1 if the previous comparison result is “greater”. In the refined assembly (Listing 1d) there is only one conditional: setne %al which sets the return value to 1 if the previous comparison result is “not equal”.Compilers, however, often defy our expectations—their behavior can be inconsistent. For example, a loop’s source code “form” can drastically affect the generated code [13, 20] and, counterintuitively, auto-vectorizers sometimes generate better code given less information [27]. Even seemingly insignificant changes such as swapping the order of independent statements can lead to unexpected differences in the generated code. Moreover, compilers are frequently unable to use additional information hints provided by programmers [10], and improving the strength of analyses has sometimes little impact on optimizations [22]. The inconsistent and unpredictable behavior of compilers can be a major obstacle in compiler research and development. Compiler developers are aware of these issues and rely on bug reports or continuous benchmarking to identify them, but the scope of these efforts is limited. Previous work has focused on automatically identifying missed optimizations [3, 18, 29, 31]. None, however, has systematically studied this inconsistent behavior of compilers, i.e., the phenomenon where more information about a program’s semantics causes a compiler to generate worse code. Techniques and tools are necessary for finding such optimization inconsistencies, both to help with understanding the unexpected interactions between compiler components, but also to identify these issues and fix the missed optimizations, analysis weaknesses, and unexpected interactions that cause them. To this end, this work develops a general approach for finding optimization inconsistencies in compilers. Our core idea is to (1) refine an input program by adding additional information about its semantics without affecting its runtime behavior, and (2) check whether the compiler generates worse code for the refined program. For example, in Listing 1c we explicitly “tell” the compiler that x >= y: GCC is consistent in this case, it generates better code for the refined version (Listing 1d). Another example of adding information would be to annotate pointers with the restrict keyword, making it obvious that they do not alias. In general, we expect that a compiler should be able to optimize a refined program at least as well as the original one; otherwise, we have identified an optimization inconsistency. Note that our work is orthogonal to finding missed optimizations such as the aforementioned efforts [3, 29–31]. Detection oracles like DCE Markers [31], optdiff checkers [3], or identifyingredundant memory operations [29] aim at reliably finding missed compiler optimizations. Incontrast, our work investigates the novel issue of how additional information about a program’sbehavior can negatively impact a compiler, leading to inferior code generation. Furthermore, asdemonstrated in our evaluation (Section 4.8), our approach can uncover such issues much moreeffectively than merely using a missed optimization detection oracle.We refine programs with two kinds of information: (1) dead code information, i.e., by explicitlyannotating dead locations as unreachable, and (2) value ranges, i.e., by making the bounds ofvariable values on specific program locations explicit. Deriving this information is generallynontrivial, but we focus on closed (i.e., taking no input) and deterministic programs where this task isstraightforward (Section 3.2); such programs are often used in automated compiler testing [4, 23, 34].Our approach, however, is general and extendable to other kinds of information (Section 4.9).We determine if the compiler is consistent between an original and refined program by using anoracle. Such an oracle, given a compiler𝐶, an original program 𝑃, and the refined one 𝑃 ′, determinesif the compilation result on the latter is degraded. Note that the oracle is not limited to the compiler’soutput, but it can also consider other information such as the compiler’s internal representation,diagnostics, or the compiled program’s runtime behavior. Our approach can be instantiated witha number of different oracles. In this work, we use three: (1) the size of the generated code, i.e.,whether refining a program leads to a significant binary size increase, (2) the number of Dead CodeElimination (DCE) markers [31], i.e., whether refining a program leads to less eliminated dead code,and (3) the precision of value range analysis, i.e., whether refining a program leads to less precisevalue range results. Our approach is described in detail in Section 3.Our empirical analysis demonstrates the usefulness and applicability of our approach in uncovering a wide range of optimization inconsistencies (Section 4). We reported 40 GCC and 19 LLVMcases, out of which 39 and 16 respectively have been confirmed/fixed. We also analyzed 89 GCC and69 LLVM unique regressions, i.e., cases where a previous compiler version was consistent. Theseregressions were caused by changes in 18 GCC and 16 LLVM components, including, among others,alias analysis, control flow graph transformations, constant propagation, global value number,jump threading, loop transformations, peephole optimizations, value range analysis, etc.. Overall,this demonstrates that our technique is highly effective in finding a wide range of optimizationinconsistencies, unexpected interactions between compiler components, and missed optimizationsin state-of-the-art compilers. Our key contributions are:• Formulating the optimization inconsistency problem in compilers and an automated approach for finding them;• An implementation of our approach which we used to find and report a wide range of issues to compiler developers; and• A systematic and quantitative study of optimization inconsistencies in GCC and LLVM.2 AN OPTIMIZATION INCONSISTENCY EXAMPLEWe start with an example demonstrating an optimization inconsistency (Listing 2). When compilingthe original program in Listing 2a with the current development version of GCC 1 at -Os, thecompiler is able to optimize away all control flow and simplify the code, as shown in Listing 2b.To uncover the optimization inconsistency in this example, we must refine the program withadditional information; the refinement is done in a semantics preserving way, i.e., the refinedprogram must have the same behavior as the original one. In this work, we refine programs byexplicitly annotating dead code as unreachable and by making the ranges of variable values atspecific program locations explicit.1Revision r14-5021-g94c0b26f454In this particular example, the inconsistency is triggered by refining function h: h is called 13 times in main’s outer loop and the values of its parameter, j, range from 1 to 65535. We “inject” this information via a conditional call to __builtin_unreachable() [24], as shown in Listing 2c.This annotation informs the compiler that j’s values can never be outside the range [1, 65535]. The compiler’s output on the refined program, shown in Listing 2d, is significantly longer and more complex than the original one. The compiler’s behavior is unexpected: it can fully optimize the original program, but it fails with the refined one, even though the only difference between the two is the constrained range of j’s values. This is an example of optimization inconsistency where refining a program with additional information leads to an unexpected degradation in the generated static struct { int a ; int b ; } c ; static int d , e , g ; static short f , i ; static void h ( unsigned short j ) { c . a = i ; main : movl $ -7 , d (% rip ) xorl %eax , %eax movl %eax , c (% rip) xorl %eax , %eax ret (b) Original ASM } int main () { d = 6; for (; d != -7; d - -) { h ( d ^ d < (0 <= 6) ) ; if ( d >= 12) if ( e ) { for (; f ; ++ f ) g = c . b ; if ( g ) e = 0;} // The rest of the code is unchanged static void h ( unsigned short j ) { c . a = i ; if (!((j >= 1) && (j <= 65535))) } }__builtin_unreachable();}| | | | | | | (a) | Original | | code | | | | | | | | | | (c) Refined | code | | | | || --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- || | | main | | : | | | | | | .L4 | | : | | | | | .L32 | : | | | | | .L12 | : | | | || | | | movl | | e (% | ) rip | , % | ecx | | | testb | | | , %dil | | %dil | testl | | | %esi | , %esi | | testb | | | , %r9b %r9b | || | | | movl | | $6 | , % eax | | | | | je | | | .L5 | | | je | | | .L6 | | | je | | | .L20 | || | | | xorl | | %edi | , %edi | | | | | movl | | | , %ecx | e (% ) | rip | movb | | | $1 | , %dil | | movw | | | , f (% %dx rip | ) || | | | xorl | | %r8d | , %r8d | | | | .L5 | | : | | | | | xorl | | | %ecx | , %ecx | | movl | | | , g (% %esi | ) rip || | | | movl | | c +4(% | rip) | ,% | r10d | | | xorl | | | , %ecx | | %ecx | .L6 | : | | | | | jmp | | | .L20 | || | | | movl | | g (% | ) rip | , %esi | | | | movw | | | , f %dx | (% rip) | | decl | | | % eax | | | .L10 | : | | | || | | | xorl | | %r9d | , %r9d | | | | | movl | | | , %ecx | c (% ) | rip | movb | | | $1 | , %r8b | | testb | | | , %dil %dil | || | | | movl | | $6 | , d (% | rip) | | | | movl | | | , %esi | g (% ) | rip | jmp | | | .L1 | | | je | | | .L12 | || | | | movw | | f (% | ) rip | , %dx | | | .L3 | | : | | | | | .L31 | : | | | | | movl | | | , e (% %ecx | ) rip || | | .L2 | : | | | | | | | | cmpl | | | $11 , % eax | | | testb | | | %r8b | , %r8b | | jmp | | | .L12 | || | | | cmpl | | $ -7 | , %eax | | | | | jle | | | .L6 | | | je | | | .L10 | | | .L20 | : | | | || | | | je | | .L31 | | | | | | testl | | | , %ecx | | %ecx | movl | | | $ -7 | , d (% rip) | | xorl | | | , % %eax eax | || | | | xorl | | %r11d | , | % r11d | | | | je | | | .L6 | | | testb | | | %dil | , %dil | | ret | | | | || | | | testl | | %eax | , % | eax | | | .L7 | | : | | | | | je | | | .L11 | | | | | | | || | | | setle | | % r11b | | | | | | testw | | | , %dx %dx | | | movl | | | %ecx | , e (% rip | ) | | | | | || | | | cmpw | | %ax | , % r11w | | | | | je | | | .L32 | | | .L11 | : | | | | | | | | | || | | | jne | | .L3 | | | | | | incl | | | %edx | | | xorl | | | %eax | , %eax | | | | | | || | | | testb | | %r8b | , % | r8b | | | | movl | | | , %r10d | % | esi | movl | | | %eax | , c (% rip | ) | | | | | || | | | je | | .L4 | | | | | | movb | | | $1 , % r9b | | | | | | | | | | | | || | | | movl | | %eax | , d | (% rip) | | | | jmp | | | .L7 | | | | | | | | | | | | |(d) Refined ASMListing 2. Optimization inconsistency example: the current upstream version of GCC -Os optimizes away all control flow in the original program. Refining the program with additional information, leads to an unexpected behavior: the compiler fails to optimize the refined program and generates significantly more complex code. Adapted from bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112545Refined Input, Degraded Output: The Counterintuitive World of Compiler Behavior 174:5 code. Note that existing (differential) testing based approaches [3, 29, 31] cannot detect this issue, as it only manifests in the refined program and not the original one. Given the standardization of the ability to “inject” information similarly to Listing 2 [11], optimization inconsistencies will likely become an even more prevalent issue in the future.Inconsistency DetectedProgram Generator Input ProgramDerived InformationRefineOracleRefined ProgramCompileRepeatFig.
About
PublishedJun 20, 2024
TypeArticle
Citations12
References31