[hcoop/debian/mlton.git] / doc / guide / localhost / Redundant

<!DOCTYPE html>\r
<html lang="en">\r
<head>\r
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
<meta name="generator" content="AsciiDoc 8.6.9">\r
<title>Redundant</title>\r
<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
<link rel="stylesheet" href="./pygments.css" type="text/css">\r
\r
\r
<script type="text/javascript" src="./asciidoc.js"></script>\r
<script type="text/javascript">\r
/*<![CDATA[*/\r
asciidoc.install();\r
/*]]>*/\r
</script>\r
<link rel="stylesheet" href="./mlton.css" type="text/css">\r
</head>\r
<body class="article">\r
<div id="banner">\r
<div id="banner-home">\r
<a href="./Home">MLton 20180207</a>\r
</div>\r
</div>\r
<div id="header">\r
<h1>Redundant</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p><a href="Redundant">Redundant</a> is an optimization pass for the <a href="SSA">SSA</a>\r
<a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="SSASimplify">SSASimplify</a>.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_description">Description</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>The redundant SSA optimization eliminates redundant function and label\r
arguments; an argument of a function or label is redundant if it is\r
always the same as another argument of the same function or label.\r
The analysis finds an equivalence relation on the arguments of a\r
function or label, such that all arguments in an equivalence class are\r
redundant with respect to the other arguments in the equivalence\r
class; the transformation selects one representative of each\r
equivalence class and drops the binding occurrence of\r
non-representative variables and renames use occurrences of the\r
non-representative variables to the representative variable.  The\r
analysis finds the equivalence classes via a fixed-point analysis.\r
Each vector of arguments to a function or label is initialized to\r
equivalence classes that equate all arguments of the same type; one\r
could start with an equivalence class that equates all arguments, but\r
arguments of different type cannot be redundant.  Variables bound in\r
statements are initialized to singleton equivalence classes.  The\r
fixed-point analysis repeatedly refines these equivalence classes on\r
the formals by the equivalence classes of the actuals.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_implementation">Implementation</h2>\r
<div class="sectionbody">\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/redundant.fun"><span class="monospaced">redundant.fun</span></a>\r
</p>\r
</li>\r
</ul></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_details_and_notes">Details and Notes</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>The reason <a href="Redundant">Redundant</a> got put in was due to some output of the\r
<a href="ClosureConvert">ClosureConvert</a> pass converter where the environment record, or\r
components of it, were passed around in several places.  That may have\r
been more relevant with polyvariant analyses (which are long gone).\r
But it still seems possibly relevant, especially with more aggressive\r
flattening, which should reveal some fields in nested closure records\r
that are redundant.</p></div>\r
</div>\r
</div>\r
</div>\r
<div id="footnotes"><hr></div>\r
<div id="footer">\r
<div id="footer-text">\r
</div>\r
<div id="footer-badges">\r
</div>\r
</div>\r
</body>\r
</html>\r
Commit	Line	Data
7f918cf1 CE	1	<!DOCTYPE html>\r
	2	<html lang="en">\r
	3	<head>\r
	4	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
	5	<meta name="generator" content="AsciiDoc 8.6.9">\r
	6	<title>Redundant</title>\r
	7	<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
	8	<link rel="stylesheet" href="./pygments.css" type="text/css">\r
	9	\r
	10	\r
	11	<script type="text/javascript" src="./asciidoc.js"></script>\r
	12	<script type="text/javascript">\r
	13	/<![CDATA[/\r
	14	asciidoc.install();\r
	15	/]]>/\r
	16	</script>\r
	17	<link rel="stylesheet" href="./mlton.css" type="text/css">\r
	18	</head>\r
	19	<body class="article">\r
	20	<div id="banner">\r
	21	<div id="banner-home">\r
	22	<a href="./Home">MLton 20180207</a>\r
	23	</div>\r
	24	</div>\r
	25	<div id="header">\r
	26	<h1>Redundant</h1>\r
	27	</div>\r
	28	<div id="content">\r
	29	<div id="preamble">\r
	30	<div class="sectionbody">\r
	31	<div class="paragraph"><p><a href="Redundant">Redundant</a> is an optimization pass for the <a href="SSA">SSA</a>\r
	32	<a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="SSASimplify">SSASimplify</a>.</p></div>\r
	33	</div>\r
	34	</div>\r
	35	<div class="sect1">\r
	36	<h2 id="_description">Description</h2>\r
	37	<div class="sectionbody">\r
	38	<div class="paragraph"><p>The redundant SSA optimization eliminates redundant function and label\r
	39	arguments; an argument of a function or label is redundant if it is\r
	40	always the same as another argument of the same function or label.\r
	41	The analysis finds an equivalence relation on the arguments of a\r
	42	function or label, such that all arguments in an equivalence class are\r
	43	redundant with respect to the other arguments in the equivalence\r
	44	class; the transformation selects one representative of each\r
	45	equivalence class and drops the binding occurrence of\r
	46	non-representative variables and renames use occurrences of the\r
	47	non-representative variables to the representative variable. The\r
	48	analysis finds the equivalence classes via a fixed-point analysis.\r
	49	Each vector of arguments to a function or label is initialized to\r
	50	equivalence classes that equate all arguments of the same type; one\r
	51	could start with an equivalence class that equates all arguments, but\r
	52	arguments of different type cannot be redundant. Variables bound in\r
	53	statements are initialized to singleton equivalence classes. The\r
	54	fixed-point analysis repeatedly refines these equivalence classes on\r
	55	the formals by the equivalence classes of the actuals.</p></div>\r
	56	</div>\r
	57	</div>\r
	58	<div class="sect1">\r
	59	<h2 id="_implementation">Implementation</h2>\r
	60	<div class="sectionbody">\r
	61	<div class="ulist"><ul>\r
	62	<li>\r
	63	<p>\r
	64	<a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/redundant.fun"><span class="monospaced">redundant.fun</span></a>\r
65	</p>\r
66	</li>\r
67	</ul></div>\r
68	</div>\r
69	</div>\r
70	<div class="sect1">\r
71	<h2 id="_details_and_notes">Details and Notes</h2>\r
72	<div class="sectionbody">\r
73	<div class="paragraph"><p>The reason <a href="Redundant">Redundant</a> got put in was due to some output of the\r
74	<a href="ClosureConvert">ClosureConvert</a> pass converter where the environment record, or\r
75	components of it, were passed around in several places. That may have\r
76	been more relevant with polyvariant analyses (which are long gone).\r
77	But it still seems possibly relevant, especially with more aggressive\r
78	flattening, which should reveal some fields in nested closure records\r
79	that are redundant.</p></div>\r
80	</div>\r
81	</div>\r
82	</div>\r
83	<div id="footnotes"><hr></div>\r
84	<div id="footer">\r
85	<div id="footer-text">\r
86	</div>\r
87	<div id="footer-badges">\r
88	</div>\r
89	</div>\r
90	</body>\r
91	</html>\r