|
Copy Propagation
In compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x. From the following code: y = x z = 3 + y Copy propagation would yield: z = 3 + x Copy propagation often makes use of reaching definitions, use-def chains and def-use chains when computing which occurrences of the target may be safely replaced. If all upwards exposed uses of the target may be safely modified, the assignment operation may be eliminated. Copy propagation is a useful "clean up" optimization frequently used after other compiler passes have already been run. Some optimizations—such as classical implementations of elimination of common sub expressions—''require'' that copy propagation be run afterwards in order to achieve an increase in efficiency. See also * Copy elision In C++ computer programming, copy elision refers to a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Compiler Theory
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a low-level programming language (e.g. assembly language, object code, or machine code) to create an executable program. Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman - Second Edition, 2007 There are many different types of compilers which produce output in different useful forms. A ''cross-compiler'' produces code for a different CPU or operating system than the one on which the cross-compiler itself runs. A ''bootstrap compiler'' is often a temporary compiler, used for compiling a more permanent or better optimised compiler for a language. Related software include, a program that translates from a low-level language to a h ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reaching Definitions
In compiler theory, a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment. For example, in the following code: d1 : y := 3 d2 : x := y d1 is a reaching definition for d2. In the following, example, however: d1 : y := 3 d2 : y := 4 d3 : x := y d1 is no longer a reaching definition for d3, because d2 kills its reach: the value defined in d1 is no longer available and cannot reach d3. As analysis The similarly named reaching definitions is a data-flow analysis which statically determines which definitions may reach a given point in the code. Because of its simplicity, it is often used as the canonical example of a data-flow analysis in textbooks. The data-flow confluence operator used is set union, and the analysis is forward flow. Reaching definitions are used to compute use-def chains. The data-flow equations used for a given basic block S in reaching defin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Use-def Chains
Within computer science, a Use-Definition Chain (''UD Chain'') is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain generally means the assignment of some value to a variable. A counterpart of a ''UD Chain'' is a Definition-Use Chain (''DU Chain''), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions. Both UD and DU chains are created by using a form of static code analysis known as data flow analysis. Knowing the use-def and def-use chains for a program or subprogram is a prerequisite for many compiler optimizations, including constant propagation and common subexpression elimination. Purpose Making the use-define or define-use chains is a step in liveness analysis, so that logical representations of all the variables can be identified and tracked through t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Def-use Chains
Within computer science, a Use-Definition Chain (''UD Chain'') is a data structure that consists of a use, U, of a Variable (programming), variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain generally means the Assignment (computer science), assignment of some value to a variable. A counterpart of a ''UD Chain'' is a Definition-Use Chain (''DU Chain''), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions. Both UD and DU chains are created by using a form of static code analysis known as data flow analysis. Knowing the use-def and def-use chains for a program or subprogram is a prerequisite for many compiler optimizations, including constant propagation and common subexpression elimination. Purpose Making the use-define or define-use chains is a step in liveness analysis, so that logical representations of all th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Upwards Exposed Uses
Upwards exposed uses or reachable uses, is a concept in compiler theory which occurs in the copy propagation stage of compilation. Uses During the copy propagation stage of program compilation, instances of a target are replaced with assignments to their values. During this process, it is necessary for the compiler to understand which instances of a target are being accessed so that appropriate substitution may occur, related to the concept of reaching definition in reaching analysis. This is done with the purpose of simplifying code before execution: if the number of upwards exposed uses of an assignment is zero, it does not contribute to the end result of the code and can be safely removed. This is also useful for improving code security during the compilation stages. Example Consider the following pseudocode: x = 1 y = z if False: x = 0 else: x = y + 2 It is safe to assume that line 5 will never occur, as demonstrated by the number of upwards exposed uses for this ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Elimination Of Common Sub Expressions
In compiler theory, common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value. Example In the following code: a = b * c + g; d = b * c * e; it may be worth transforming the code to: tmp = b * c; a = tmp + g; d = tmp * e; if the cost of storing and retrieving tmp is less than the cost of calculating b * c an extra time. Principle The possibility to perform CSE is based on available expression analysis (a data flow analysis). An expression b*c is available at a point ''p'' in a program if: * every path from the initial node to p evaluates b*c before reaching ''p'', * and there are no assignments to b or c after the evaluation but before ''p''. The cost/benefit analysis performed by an optimizer will calculate whether the cost of the store to tmp is less than the c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Copy Elision
In C++ computer programming, copy elision refers to a compiler optimization technique that eliminates unnecessary copying of objects. The C++ language standard generally allows implementations to perform any optimization, provided the resulting program's observable behavior is the same '' as if'', i.e. pretending, the program were executed exactly as mandated by the standard. Beyond that, the standard also describes a few situations where copying can be eliminated even if this would alter the program's behavior, the most common being the return value optimization (see below). Another widely implemented optimization, described in the C++ standard, is when a temporary object of class type is copied to an object of the same type.ISO/IEC (2003). '' ISO/IEC 14882:2003(E): Programming Languages - C++ §12.8 Copying class objects lass.copy' para. 15 As a result, ''copy-initialization'' is usually equivalent to ''direct-initialization'' in terms of performance, but not in semantics; ''co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
