Compiler Design - revision history

Dank: /* See Also */ fix syntax

2012-05-12T20:22:56Z

Dank: /* Control Flow Analysis */ don't leave pluralization outside of formatting tag it looks stupid

2011-09-06T21:09:50Z

Control Flow Analysis: don't leave pluralization outside of formatting tag it looks stupid

← Older revision		Revision as of 21:09, 6 September 2011
Line 13:		Line 13:
	Dataflow analysis is most usefully performed into and out of ''regions'', subsets of the nodes such that a ''header'' exists which dominates all nodes in the region, and all edges between nodes in the region are themselves in the region. A loop is a region which is strongly connected, where all back-edges to the header are themselves within the region '''FIXME -- unclear'''.		Dataflow analysis is most usefully performed into and out of ''regions'', subsets of the nodes such that a ''header'' exists which dominates all nodes in the region, and all edges between nodes in the region are themselves in the region. A loop is a region which is strongly connected, where all back-edges to the header are themselves within the region '''FIXME -- unclear'''.

	Loops can be discovered via domination analysis (it is important to note that this refers to loops in the generated code, not loop constructs of the source language, and furthermore that all possible loops will be found (ie, unstructured loops constructed from C <tt>~~goto~~</tt>s)). Discover all strongly-connected subgraphs (SCCs) of the CFG (subgraphs where, for each vertex, a path ('''not''' necessarily an edge) exists from that vertex to all other nodes of the subgraph); if a subgraph contains a node dominating all that subgraph's nodes, the subgraph is a loop. The trivial case is, of course, a statement which jumps to itself, ala the BASIC program <tt>10 GOTO 10</tt>. Implementation via [[Kosaraju's Algorithm]] is simple, with O(\|V\|+\|E\|) time complexity using graph encoding and O(N<sup>2</sup>) time complexity using adjacency matrices:		Loops can be discovered via domination analysis (it is important to note that this refers to loops in the generated code, not loop constructs of the source language, and furthermore that all possible loops will be found (ie, unstructured loops constructed from C <tt>gotos</tt>)). Discover all strongly-connected subgraphs (SCCs) of the CFG (subgraphs where, for each vertex, a path ('''not''' necessarily an edge) exists from that vertex to all other nodes of the subgraph); if a subgraph contains a node dominating all that subgraph's nodes, the subgraph is a loop. The trivial case is, of course, a statement which jumps to itself, ala the BASIC program <tt>10 GOTO 10</tt>. Implementation via [[Kosaraju's Algorithm]] is simple, with O(\|V\|+\|E\|) time complexity using graph encoding and O(N<sup>2</sup>) time complexity using adjacency matrices:
	* Perform a recursive depth-first traversal of the graph starting from s. Each time you return, add that node onto an auxiliary vector. Upon the traversal's completion, this vector sorts the nodes topologically.		* Perform a recursive depth-first traversal of the graph starting from s. Each time you return, add that node onto an auxiliary vector. Upon the traversal's completion, this vector sorts the nodes topologically.
	* Until the the vector is empty, use the last node of the vector to begin traversing the transpose graph. Remove the path from the vector; these paths partition the graph into SCCs.		* Until the the vector is empty, use the last node of the vector to begin traversing the transpose graph. Remove the path from the vector; these paths partition the graph into SCCs.

Dank: /* Control Flow Analysis */

2010-03-17T21:44:46Z

Control Flow Analysis

← Older revision		Revision as of 21:44, 17 March 2010
Line 3:		Line 3:
	* either b immediately follows a, and a does not end in an unconditional branch,		* either b immediately follows a, and a does not end in an unconditional branch,
	* or a ends in a branch, of which b is a potential target.		* or a ends in a branch, of which b is a potential target.
	Note that an indirect branch, without context information, trivializes all blocks (every instruction becomes a leader) and flows to them all from at least that point (an arborescence is ~~formed~~)!		Note that an indirect branch, without context information, trivializes all blocks (every instruction becomes a leader) and flows to them all from at least that point (an arborescence is induced)!

	The directed multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.		The directed multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.

Dank: /* See Also */

2009-10-27T11:53:01Z

Dank: /* See Also */

2009-10-27T11:50:23Z

Dank: /* See Also */

2009-10-27T11:50:11Z

Dank at 11:49, 27 October 2009

2009-10-27T11:49:37Z

← Older revision		Revision as of 11:49, 27 October 2009
Line 91:		Line 91:
	** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the Banerjee test.		** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the Banerjee test.
	* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].		* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
			* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code

Dank: /* Dead code elimination */

2009-04-29T10:57:09Z

Dead code elimination

← Older revision		Revision as of 10:57, 29 April 2009
Line 20:		Line 20:

	===Dead code elimination===		===Dead code elimination===
	Control flow analysis by itself is sufficient to remove some unreachable code.		Control flow analysis by itself is sufficient to remove some ''unreachable code'' (viz ''dead code'', below).

	==Dataflow/Dependency Analysis==		==Dataflow/Dependency Analysis==

Dank: /* Dataflow/Dependency Analysis */

2009-04-29T10:56:43Z

Dataflow/Dependency Analysis

← Older revision		Revision as of 10:56, 29 April 2009
Line 31:		Line 31:
	** Def-Use chain -- a definition D of a variable, and all uses of that variable it can reach (those reached from D)		** Def-Use chain -- a definition D of a variable, and all uses of that variable it can reach (those reached from D)
	** Common subexpression elimination lexically matches subexpressions, and can preserve them in registers		** Common subexpression elimination lexically matches subexpressions, and can preserve them in registers
			** Liveness analysis can detect some instances of ''dead code'' (code whose result is never used, viz ''unreachable code'' above)

	===Intermediate Representations===		===Intermediate Representations===

Dank: /* Control Flow Analysis */

2009-04-29T10:55:33Z

Control Flow Analysis

← Older revision		Revision as of 10:55, 29 April 2009
Line 18:		Line 18:
	Kosaraju's algorithm is improved upon by [[Tarjan's Algorithm]] and [[Gabow's Algorithm]].		Kosaraju's algorithm is improved upon by [[Tarjan's Algorithm]] and [[Gabow's Algorithm]].
	''Natural loop'' identification proceeds via identification of ''back edges'' (edges from a node b to a node a, where a dominates b). A loop is associated with every such back edge; if a backedge exists from b to a, the associated loop is entered at a, and consists additionally of all nodes which can reach b without going through a. Similarly, a loop is associated with the target of every back edge, this being the union of all such backedges' associated natural loops.		''Natural loop'' identification proceeds via identification of ''back edges'' (edges from a node b to a node a, where a dominates b). A loop is associated with every such back edge; if a backedge exists from b to a, the associated loop is entered at a, and consists additionally of all nodes which can reach b without going through a. Similarly, a loop is associated with the target of every back edge, this being the union of all such backedges' associated natural loops.

			===Dead code elimination===
			Control flow analysis by itself is sufficient to remove some unreachable code.

	==Dataflow/Dependency Analysis==		==Dataflow/Dependency Analysis==

← Older revision		Revision as of 11:53, 27 October 2009
Line 88:		Line 88:
	* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page		* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page
	* "[http://www.cs.lth.se/home/Jonas_Skeppstedt/kongstad.pdf An Implementation of Global Value Numbering in the GNU Compiler Collection, with Performance Measurements]" (Kongstad 2004)		* "[http://www.cs.lth.se/home/Jonas_Skeppstedt/kongstad.pdf An Implementation of Global Value Numbering in the GNU Compiler Collection, with Performance Measurements]" (Kongstad 2004)
	* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and [[Banerjee ~~inequality~~\|Banerjee ~~Inequalities~~]], explaining the crappiness of the former and general robustness of the latter.		* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and [[Banerjee Inequality\|Banerjee inequalities]], explaining the crappiness of the former and general robustness of the latter.
	** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality\|Banerjee test]].		** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality\|Banerjee test]].
	* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].		* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
	* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code		* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code
			* "[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.5532 Combining Register Allocation and Instruction Scheduling]", a seminal 1995 paper by Motwani et al, explores the complexity of scheduling

← Older revision		Revision as of 11:50, 27 October 2009
Line 88:		Line 88:
	* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page		* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page
	* "[http://www.cs.lth.se/home/Jonas_Skeppstedt/kongstad.pdf An Implementation of Global Value Numbering in the GNU Compiler Collection, with Performance Measurements]" (Kongstad 2004)		* "[http://www.cs.lth.se/home/Jonas_Skeppstedt/kongstad.pdf An Implementation of Global Value Numbering in the GNU Compiler Collection, with Performance Measurements]" (Kongstad 2004)
	* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and [[Banerjee inequality\|Banerjee ~~inequalities~~]], explaining the crappiness of the former and general robustness of the latter.		* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and [[Banerjee inequality\|Banerjee Inequalities]], explaining the crappiness of the former and general robustness of the latter.
	** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality\|Banerjee test]].		** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality\|Banerjee test]].
	* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].		* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
	* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code		* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code

← Older revision		Revision as of 11:50, 27 October 2009
Line 88:		Line 88:
	* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page		* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page
	* "[http://www.cs.lth.se/home/Jonas_Skeppstedt/kongstad.pdf An Implementation of Global Value Numbering in the GNU Compiler Collection, with Performance Measurements]" (Kongstad 2004)		* "[http://www.cs.lth.se/home/Jonas_Skeppstedt/kongstad.pdf An Implementation of Global Value Numbering in the GNU Compiler Collection, with Performance Measurements]" (Kongstad 2004)
	* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and Banerjee inequalities, explaining the crappiness of the former and general robustness of the latter.		* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and [[Banerjee inequality\|Banerjee inequalities]], explaining the crappiness of the former and general robustness of the latter.
	** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the Banerjee test.		** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality\|Banerjee test]].
	* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].		* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
	* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code		* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code

← Older revision		Revision as of 20:22, 12 May 2012
Line 91:		Line 91:
	** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality\|Banerjee test]].		** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality\|Banerjee test]].
	* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].		* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
	* "[http://coyotegulch.com/products/acovea/ Acovea]: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code		* "[http://coyotegulch.com/products/acovea/ Acovea: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code
	* "[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.5532 Combining Register Allocation and Instruction Scheduling]", a seminal 1995 paper by Motwani et al, explores the complexity of scheduling		* "[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.5532 Combining Register Allocation and Instruction Scheduling]", a seminal 1995 paper by Motwani et al, explores the complexity of scheduling