Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 0304b2bc2bc3acaa4c6ff71816b69cc7c4b49997 / . / docs / Passes.html
blob: 469576900889917f0feb01b77b54dc3f7f572548 [file] [log] [blame]
Reid Spencerd9aac122007-03-26 09:32:31 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
5 <title>LLVM's Analysis and Transform Passes</title>
6 <link rel="stylesheet" href="llvm.css" type="text/css">
7</head>
8<body>
9
10<div class="doc_title">LLVM's Analysis and Transform Passes</div>
11
12<ol>
13 <li><a href="#intro">Introduction</a></li>
14 <li><a href="#analyses">Analysis Passes</a>
15 <li><a href="#transforms">Transform Passes</a></li>
16 <li><a href="#utilities">Utility Passes</a></li>
17</ol>
18
19<div class="doc_author">
20 <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p>
21</div>
22
23<!-- ======================================================================= -->
24<div class="doc_section"> <a name="intro">Introduction</a> </div>
25<div class="doc_text">
26 <p>This document serves as a high level summary of the optimization features
27 that LLVM provides. Optimizations are implemented as Passes that traverse some
28 portion of a program to either collect information or transform the program.
29 THe table below divides the passes that LLVM provides into three categories.
30 Analysis passes compute information that other passes can use or for debugging
31 or program visualization purposes. Transform passes can use (or invalidate)
32 the analysis passes. Transform passes all mutate the program in some way.
33 Utility passes provides ome utility but don't otherwise fit categorization.
34 For example passes to extract functions to bytecode or write a module to
35 bytecode are neither analysis nor transform passes.
36 <p>The table below provides a quick summary of each pass and links to the more
37 complete pass description later in the document.</p>
38</div>
39<div class="doc_text" >
40<table>
41<tr><th colspan="3"><b>ANALYSIS PASSES</b></th></tr>
42<tr><th>Option</th><th>Name</th><th>Directory</th></tr>
43<tr><td><a href="#aa-eval">-aa-eval</a></td><td>Exhaustive Alias Analysis Precision Evaluator</td></tr>
44<tr><td><a href="#anders-aa">-anders-aa</a></td><td>Andersen's Interprocedural Alias Analysis</td></tr>
45<tr><td><a href="#basicaa">-basicaa</a></td><td>Basic Alias Analysis (default AA impl)</td></tr>
46<tr><td><a href="#basiccg">-basiccg</a></td><td>Basic CallGraph Construction</td></tr>
47<tr><td><a href="#basicvn">-basicvn</a></td><td>Basic Value Numbering (default GVN impl)</td></tr>
48<tr><td><a href="#callgraph">-callgraph</a></td><td>Print a call graph</td></tr>
49<tr><td><a href="#callscc">-callscc</a></td><td>Print SCCs of the Call Graph</td></tr>
50<tr><td><a href="#cfgscc">-cfgscc</a></td><td>Print SCCs of each function CFG</td></tr>
51<tr><td><a href="#count-aa">-count-aa</a></td><td>Count Alias Analysis Query Responses</td></tr>
52<tr><td><a href="#debug-aa">-debug-aa</a></td><td>AA use debugger</td></tr>
53<tr><td><a href="#domfrontier">-domfrontier</a></td><td>Dominance Frontier Construction</td></tr>
54<tr><td><a href="#domset">-domset</a></td><td>Dominator Set Construction</td></tr>
55<tr><td><a href="#domtree">-domtree</a></td><td>Dominator Tree Construction</td></tr>
56<tr><td><a href="#etforest">-etforest</a></td><td>ET Forest Construction</td></tr>
57<tr><td><a href="#externalfnconstants">-externalfnconstants</a></td><td>Print external fn callsites passed constants</td></tr>
58<tr><td><a href="#globalsmodref-aa">-globalsmodref-aa</a></td><td>Simple mod/ref analysis for globals</td></tr>
59<tr><td><a href="#idom">-idom</a></td><td>Immediate Dominators Construction</td></tr>
60<tr><td><a href="#instcount">-instcount</a></td><td>Counts the various types of Instructions</td></tr>
61<tr><td><a href="#intervals">-intervals</a></td><td>Interval Partition Construction</td></tr>
62<tr><td><a href="#load-vn">-load-vn</a></td><td>Load Value Numbering</td></tr>
63<tr><td><a href="#loops">-loops</a></td><td>Natural Loop Construction</td></tr>
64<tr><td><a href="#no-aa">-no-aa</a></td><td>No Alias Analysis (always returns 'may' alias)</td></tr>
65<tr><td><a href="#no-profile">-no-profile</a></td><td>No Profile Information</td></tr>
66<tr><td><a href="#postdomfrontier">-postdomfrontier</a></td><td>Post-Dominance Frontier Construction</td></tr>
67<tr><td><a href="#postdomset">-postdomset</a></td><td>Post-Dominator Set Construction</td></tr>
68<tr><td><a href="#postdomtree">-postdomtree</a></td><td>Post-Dominator Tree Construction</td></tr>
69<tr><td><a href="#postetforest">-postetforest</a></td><td>Post-ET-Forest Construction</td></tr>
70<tr><td><a href="#postidom">-postidom</a></td><td>Immediate Post-Dominators Construction</td></tr>
71<tr><td><a href="#print">-print</a></td><td>Print function to stderr</td></tr>
72<tr><td><a href="#print-alias-sets">-print-alias-sets</a></td><td>Alias Set Printer</td></tr>
73<tr><td><a href="#print-callgraph">-print-callgraph</a></td><td>Print Call Graph to 'dot' file</td></tr>
74<tr><td><a href="#print-cfg">-print-cfg</a></td><td>Print CFG of function to 'dot' file</td></tr>
75<tr><td><a href="#print-cfg-only">-print-cfg-only</a></td><td>Print CFG of function to 'dot' file (with no function bodies)</td></tr>
76<tr><td><a href="#printm">-printm</a></td><td>Print module to stderr</td></tr>
77<tr><td><a href="#printusedtypes">-printusedtypes</a></td><td>Find Used Types</td></tr>
78<tr><td><a href="#profile-loader">-profile-loader</a></td><td>Load profile information from llvmprof.out</td></tr>
79<tr><td><a href="#scalar-evolution">-scalar-evolution</a></td><td>Scalar Evolution Analysis</td></tr>
80<tr><td><a href="#targetdata">-targetdata</a></td><td>Target Data Layout</td></tr>
81
82
83<tr><th colspan="3"><b>TRANSFORM PASSES</b></th></tr>
84<tr><th>Option</th><th>Name</th><th>Directory</th></tr>
85<tr><td><a href="#adce">-adce</a></td><td>Aggressive Dead Code Elimination</td></tr>
86<tr><td><a href="#argpromotion">-argpromotion</a></td><td>Promote 'by reference' arguments to scalars</td></tr>
87<tr><td><a href="#block-placement">-block-placement</a></td><td>Profile Guided Basic Block Placement</td></tr>
88<tr><td><a href="#break-crit-edges">-break-crit-edges</a></td><td>Break Critical Edges in CFG</td></tr>
89<tr><td><a href="#cee">-cee</a></td><td>Correlated Expression Elimination</td></tr>
90<tr><td><a href="#condprop">-condprop</a></td><td>Conditional Propagation</td></tr>
91<tr><td><a href="#constmerge">-constmerge</a></td><td>Merge Duplicate Global Constants</td></tr>
92<tr><td><a href="#constprop">-constprop</a></td><td>Simple constant propagation</td></tr>
93<tr><td><a href="#dce">-dce</a></td><td>Dead Code Elimination</td></tr>
94<tr><td><a href="#deadargelim">-deadargelim</a></td><td>Dead Argument Elimination</td></tr>
95<tr><td><a href="#deadtypeelim">-deadtypeelim</a></td><td>Dead Type Elimination</td></tr>
96<tr><td><a href="#die">-die</a></td><td>Dead Instruction Elimination</td></tr>
97<tr><td><a href="#dse">-dse</a></td><td>Dead Store Elimination</td></tr>
98<tr><td><a href="#gcse">-gcse</a></td><td>Global Common Subexpression Elimination</td></tr>
99<tr><td><a href="#globaldce">-globaldce</a></td><td>Dead Global Elimination</td></tr>
100<tr><td><a href="#globalopt">-globalopt</a></td><td>Global Variable Optimizer</td></tr>
101<tr><td><a href="#indmemrem">-indmemrem</a></td><td>Indirect Malloc and Free Removal</td></tr>
102<tr><td><a href="#indvars">-indvars</a></td><td>Canonicalize Induction Variables</td></tr>
103<tr><td><a href="#inline">-inline</a></td><td>Function Integration/Inlining</td></tr>
104<tr><td><a href="#insert-block-profiling">-insert-block-profiling</a></td><td>Insert instrumentation for block profiling</td></tr>
105<tr><td><a href="#insert-edge-profiling">-insert-edge-profiling</a></td><td>Insert instrumentation for edge profiling</td></tr>
106<tr><td><a href="#insert-function-profiling">-insert-function-profiling</a></td><td>Insert instrumentation for function profiling</td></tr>
107<tr><td><a href="#insert-null-profiling-rs">-insert-null-profiling-rs</a></td><td>Measure profiling framework overhead</td></tr>
108<tr><td><a href="#insert-rs-profiling-framework">-insert-rs-profiling-framework</a></td><td>Insert random sampling instrumentation framework</td></tr>
109<tr><td><a href="#instcombine">-instcombine</a></td><td>Combine redundant instructions</td></tr>
110<tr><td><a href="#internalize">-internalize</a></td><td>Internalize Global Symbols</td></tr>
111<tr><td><a href="#ipconstprop">-ipconstprop</a></td><td>Interprocedural constant propagation</td></tr>
112<tr><td><a href="#ipsccp">-ipsccp</a></td><td>Interprocedural Sparse Conditional Constant Propagation</td></tr>
113<tr><td><a href="#lcssa">-lcssa</a></td><td>Loop-Closed SSA Form Pass</td></tr>
114<tr><td><a href="#licm">-licm</a></td><td>Loop Invariant Code Motion</td></tr>
115<tr><td><a href="#loop-extract">-loop-extract</a></td><td>Extract loops into new functions</td></tr>
116<tr><td><a href="#loop-extract-single">-loop-extract-single</a></td><td>Extract at most one loop into a new function</td></tr>
117<tr><td><a href="#loop-reduce">-loop-reduce</a></td><td>Loop Strength Reduction</td></tr>
118<tr><td><a href="#loop-unroll">-loop-unroll</a></td><td>Unroll Loops</td></tr>
119<tr><td><a href="#loop-unswitch">-loop-unswitch</a></td><td>Unswitch Loops</td></tr>
120<tr><td><a href="#loopsimplify">-loopsimplify</a></td><td>Canonicalize Natural Loops</td></tr>
121<tr><td><a href="#lower-packed">-lower-packed</a></td><td>Lower Packed Operations</td></tr>
122<tr><td><a href="#lowerallocs">-lowerallocs</a></td><td>Lower allocations from instructions to calls</td></tr>
123<tr><td><a href="#lowergc">-lowergc</a></td><td>Lower GC intrinsics, for GCless code generators</td></tr>
124<tr><td><a href="#lowerinvoke">-lowerinvoke</a></td><td>Lower Invoke and Unwind</td></tr>
125<tr><td><a href="#lowerselect">-lowerselect</a></td><td>Lower Selects To Branches</td></tr>
126<tr><td><a href="#lowersetjmp">-lowersetjmp</a></td><td>Lower Set Jump</td></tr>
127<tr><td><a href="#lowerswitch">-lowerswitch</a></td><td>Lower SwitchInst's to branches</td></tr>
128<tr><td><a href="#mem2reg">-mem2reg</a></td><td>Promote Memory to Register</td></tr>
129<tr><td><a href="#mergereturn">-mergereturn</a></td><td>Unify Function Exit Nodes</td></tr>
130<tr><td><a href="#predsimplify">-predsimplify</a></td><td>Predicate Simplifier</td></tr>
131<tr><td><a href="#prune-eh">-prune-eh</a></td><td>Remove unused exception handling info</td></tr>
132<tr><td><a href="#raiseallocs">-raiseallocs</a></td><td>Raise allocations from calls to instructions</td></tr>
133<tr><td><a href="#reassociate">-reassociate</a></td><td>Reassociate Expressions</td></tr>
134<tr><td><a href="#reg2mem">-reg2mem</a></td><td>Demote Values to Memory</td></tr>
135<tr><td><a href="#scalarrepl">-scalarrepl</a></td><td>Scalar Replacement of Aggregates</td></tr>
136<tr><td><a href="#sccp">-sccp</a></td><td>Sparse Conditional Constant Propagation</td></tr>
137<tr><td><a href="#simplify-libcalls">-simplify-libcalls</a></td><td>Simplify well-known library calls</td></tr>
138<tr><td><a href="#simplifycfg">-simplifycfg</a></td><td>Simplify the CFG</td></tr>
139<tr><td><a href="#strip">-strip</a></td><td>Strip all symbols from a module</td></tr>
140<tr><td><a href="#tailcallelim">-tailcallelim</a></td><td>Tail Call Elimination</td></tr>
141<tr><td><a href="#tailduplicate">-tailduplicate</a></td><td>Tail Duplication</td></tr>
142<tr><th colspan="3"><b>UTILITY PASSES</b></th></tr>
143<tr><th>Option</th><th>Name</th><th>Directory</th></tr>
144<tr><td><a href="#deadarghaX0r">-deadarghaX0r</a></td><td>Dead Argument Hacking (BUGPOINT ONLY)</td></tr>
145<tr><td><a href="#extract-blocks">-extract-blocks</a></td><td>Extract Basic Blocks From Module (BUGPOINT ONLY)</td></tr>
146<tr><td><a href="#emitbytecode">-emitbytecode</a></td><td>Bytecode Writer</td></tr>
147<tr><td><a href="#verify">-verify</a></td><td>Module Verifier</td></tr>
148</table>
149</div>
150
151<!-- ======================================================================= -->
152<div class="doc_section"> <a name="example">Analysis Passes</a></div>
153<div class="doc_text">
154 <p>This section describes the LLVM Analysis Passes.</p>
155</div>
156
157<!-------------------------------------------------------------------------- -->
158<div class="doc_subsection">
159 <a name="aa-eval">Exhaustive Alias Analysis Precision Evaluator</a>
160</div>
161<div class="doc_text">
162 <p>Yet to be written.</p>
163</div>
164
165<!-------------------------------------------------------------------------- -->
166<div class="doc_subsection">
167 <a name="anders-aa">Andersen's Interprocedural Alias Analysis</a>
168</div>
169<div class="doc_text">
170 <p>Yet to be written.</p>
171</div>
172
173<!-------------------------------------------------------------------------- -->
174<div class="doc_subsection">
175 <a name="basicaa">Basic Alias Analysis</a>
176</div>
177<div class="doc_text">
178 <p>Yet to be written.</p>
179</div>
180
181<!-------------------------------------------------------------------------- -->
182<div class="doc_subsection">
183 <a name="basiccg">Basic Call Graph Construction</a>
184</div>
185<div class="doc_text">
186 <p>Yet to be written.</p>
187</div>
188
189<!-------------------------------------------------------------------------- -->
190<div class="doc_subsection">
191 <a name="basicvn">Basic Value Numbering</a>
192</div>
193<div class="doc_text">
194 <p>Yet to be written.</p>
195</div>
196
197<!-------------------------------------------------------------------------- -->
198<div class="doc_subsection">
199 <a name="callgraph">Print Call Graph</a>
200</div>
201<div class="doc_text">
202 <p>Yet to be written.</p>
203</div>
204
205<!-------------------------------------------------------------------------- -->
206<div class="doc_subsection">
207 <a name="callscc">Print SCCs of the Call Graph</a>
208</div>
209<div class="doc_text">
210 <p>Yet to be written.</p>
211</div>
212
213<!-------------------------------------------------------------------------- -->
214<div class="doc_subsection">
215 <a name="cfgscc">Print SCCs of each Function Control Flow Graph</a>
216</div>
217<div class="doc_text">
218 <p>Yet to be written.</p>
219</div>
220
221<!-------------------------------------------------------------------------- -->
222<div class="doc_subsection">
223 <a name="count-aa">Count Alias Analysis Query Responses</a>
224</div>
225<div class="doc_text">
226 <p>Yet to be written.</p>
227</div>
228
229<!-------------------------------------------------------------------------- -->
230<div class="doc_subsection">
231 <a name="debug-aa">Alias Analysis Usage Debugger</a>
232</div>
233<div class="doc_text">
234 <p>Yet to be written.</p>
235</div>
236
237<!-------------------------------------------------------------------------- -->
238<div class="doc_subsection">
239 <a name="domfrontier">Dominance Frontier Construction</a>
240</div>
241<div class="doc_text">
242 <p>Yet to be written.</p>
243</div>
244
245<!-------------------------------------------------------------------------- -->
246<div class="doc_subsection">
247 <a name="domset">Dominator Set Construction</a>
248</div>
249<div class="doc_text">
250 <p>Yet to be written.</p>
251</div>
252
253<!-------------------------------------------------------------------------- -->
254<div class="doc_subsection">
255 <a name="domtree">Dominator Tree Construction</a>
256</div>
257<div class="doc_text">
258 <p>Yet to be written.</p>
259</div>
260
261<!-------------------------------------------------------------------------- -->
262<div class="doc_subsection">
263 <a name="etforest">ET Forest Construction</a>
264</div>
265<div class="doc_text">
266 <p>Yet to be written.</p>
267</div>
268
269<!-------------------------------------------------------------------------- -->
270<div class="doc_subsection">
271 <a name="basicvn">Basic Value Numbering</a>
272</div>
273<div class="doc_text">
274 <p>Yet to be written.</p>
275</div>
276
277<!-------------------------------------------------------------------------- -->
278<div class="doc_subsection">
279 <a name="externalfnconstants">Print external fn callsites passed constants</a>
280</div>
281<div class="doc_text">
282 <p>Yet to be written.</p>
283</div>
284
285<!-------------------------------------------------------------------------- -->
286<div class="doc_subsection">
287 <a name="globalsmodref-aa">Simple mod/ref analysis for globals</a>
288</div>
289<div class="doc_text">
290 <p>Yet to be written.</p>
291</div>
292
293<!-------------------------------------------------------------------------- -->
294<div class="doc_subsection">
295 <a name="idom">Immediate Dominators Construction</a>
296</div>
297<div class="doc_text">
298 <p>Yet to be written.</p>
299</div>
300
301<!-------------------------------------------------------------------------- -->
302<div class="doc_subsection">
303 <a name="instcount">Counts the various types of Instructions</a>
304</div>
305<div class="doc_text">
306 <p>Yet to be written.</p>
307</div>
308
309<!-------------------------------------------------------------------------- -->
310<div class="doc_subsection">
311 <a name="intervals">Interval Partition Construction</a>
312</div>
313<div class="doc_text">
314 <p>Yet to be written.</p>
315</div>
316
317<!-------------------------------------------------------------------------- -->
318<div class="doc_subsection">
319 <a name="load-vn">Load Value Numbering</a>
320</div>
321<div class="doc_text">
322 <p>Yet to be written.</p>
323</div>
324
325<!-------------------------------------------------------------------------- -->
326<div class="doc_subsection">
327 <a name="loops">Natural Loop Construction</a>
328</div>
329<div class="doc_text">
330 <p>Yet to be written.</p>
331</div>
332
333<!-------------------------------------------------------------------------- -->
334<div class="doc_subsection">
335 <a name="no-aa">No Alias Analysis (always returns 'may' alias)</a>
336</div>
337<div class="doc_text">
338 <p>Yet to be written.</p>
339</div>
340
341<!-------------------------------------------------------------------------- -->
342<div class="doc_subsection">
343 <a name="no-profile">No Profile Information</a>
344</div>
345<div class="doc_text">
346 <p>Yet to be written.</p>
347</div>
348
349<!-------------------------------------------------------------------------- -->
350<div class="doc_subsection">
351 <a name="postdomfrontier">Post-Dominance Frontier Construction</a>
352</div>
353<div class="doc_text">
354 <p>Yet to be written.</p>
355</div>
356
357<!-------------------------------------------------------------------------- -->
358<div class="doc_subsection">
359 <a name="postdomset">Post-Dominator Set Construction</a>
360</div>
361<div class="doc_text">
362 <p>Yet to be written.</p>
363</div>
364
365<!-------------------------------------------------------------------------- -->
366<div class="doc_subsection">
367 <a name="postdomtree">Post-Dominator Tree Construction</a>
368</div>
369<div class="doc_text">
370 <p>Yet to be written.</p>
371</div>
372
373<!-------------------------------------------------------------------------- -->
374<div class="doc_subsection">
375 <a name="postetforest">Post-ET-Forest Construction</a>
376</div>
377<div class="doc_text">
378 <p>Yet to be written.</p>
379</div>
380
381<!-------------------------------------------------------------------------- -->
382<div class="doc_subsection">
383 <a name="postidom">Immediate Post-Dominators Construction</a>
384</div>
385<div class="doc_text">
386 <p>Yet to be written.</p>
387</div>
388
389<!-------------------------------------------------------------------------- -->
390<div class="doc_subsection">
391 <a name="print">Print function to stderr</a>
392</div>
393<div class="doc_text">
394 <p>Yet to be written.</p>
395</div>
396
397<!-------------------------------------------------------------------------- -->
398<div class="doc_subsection">
399 <a name="print-alias-sets">Alias Set Printer</a>
400</div>
401<div class="doc_text">
402 <p>Yet to be written.</p>
403</div>
404
405<!-------------------------------------------------------------------------- -->
406<div class="doc_subsection">
407 <a name="print-callgraph">Print Call Graph to 'dot' file</a>
408</div>
409<div class="doc_text">
410 <p>Yet to be written.</p>
411</div>
412
413<!-------------------------------------------------------------------------- -->
414<div class="doc_subsection">
415 <a name="print-cfg">Print CFG of function to 'dot' file</a>
416</div>
417<div class="doc_text">
418 <p>Yet to be written.</p>
419</div>
420
421<!-------------------------------------------------------------------------- -->
422<div class="doc_subsection">
423 <a name="print-cfg-only">Print CFG of function to 'dot' file (with no function bodies)</a>
424</div>
425<div class="doc_text">
426 <p>Yet to be written.</p>
427</div>
428
429<!-------------------------------------------------------------------------- -->
430<div class="doc_subsection">
431 <a name="printm">Print module to stderr</a>
432</div>
433<div class="doc_text">
434 <p>Yet to be written.</p>
435</div>
436
437<!-------------------------------------------------------------------------- -->
438<div class="doc_subsection">
439 <a name="printusedtypes">Find Used Types</a>
440</div>
441<div class="doc_text">
442 <p>Yet to be written.</p>
443</div>
444
445<!-------------------------------------------------------------------------- -->
446<div class="doc_subsection">
447 <a name="profile-loader">Load profile information from llvmprof.out</a>
448</div>
449<div class="doc_text">
450 <p>Yet to be written.</p>
451</div>
452
453<!-------------------------------------------------------------------------- -->
454<div class="doc_subsection">
455 <a name="scalar-evolution">Scalar Evolution Analysis</a>
456</div>
457<div class="doc_text">
458 <p>Yet to be written.</p>
459</div>
460
461<!-------------------------------------------------------------------------- -->
462<div class="doc_subsection">
463 <a name="targetdata">Target Data Layout</a>
464</div>
465<div class="doc_text">
466 <p>Yet to be written.</p>
467</div>
468
469<!-- ======================================================================= -->
470<div class="doc_section"> <a name="transform">Transform Passes</a></div>
471<div class="doc_text">
472 <p>This section describes the LLVM Transform Passes.</p>
473</div>
474
475<!-------------------------------------------------------------------------- -->
476<div class="doc_subsection">
477 <a name="adce">Aggressive Dead Code Elimination</a>
478</div>
479<div class="doc_text">
Reid Spenceraf4af3a2007-03-27 02:49:31 +0000[diff] [blame]480 <p>ADCE aggressively tries to eliminate code. This pass is similar to
481 <a href="#dce">DCE</a> but it assumes that values are dead until proven
482 otherwise. This is similar to <a href="#sccp">SCCP</a>, except applied to
483 the liveness of values.</p>
Reid Spencerd9aac122007-03-26 09:32:31 +0000[diff] [blame]484</div>
485
486<!-------------------------------------------------------------------------- -->
487<div class="doc_subsection">
488 <a name="argpromotion">Promote 'by reference' arguments to scalars</a>
489</div>
490<div class="doc_text">
491 <p>Yet to be written.</p>
492</div>
493
494<!-------------------------------------------------------------------------- -->
495<div class="doc_subsection">
496 <a name="block-placement">Profile Guided Basic Block Placement</a>
497</div>
498<div class="doc_text">
Reid Spenceraf4af3a2007-03-27 02:49:31 +0000[diff] [blame]499 <p>This pass implements a very simple profile guided basic block placement
500 algorithm. The idea is to put frequently executed blocks together at the
501 start of the function, and hopefully increase the number of fall-through
502 conditional branches. If there is no profile information for a particular
503 function, this pass basically orders blocks in depth-first order.</p>
504 <p>The algorithm implemented here is basically "Algo1" from "Profile Guided
505 Code Positioning" by Pettis and Hansen, except that it uses basic block
506 counts instead of edge counts. This could be improved in many ways, but is
507 very simple for now.</p>
508 <p>Basically we "place" the entry block, then loop over all successors in a
509 DFO, placing the most frequently executed successor until we run out of
510 blocks. Did we mention that this was <b>extremely</b> simplistic? This is
511 also much slower than it could be. When it becomes important, this pass
512 will be rewritten to use a better algorithm, and then we can worry about
513 efficiency.</p>
Reid Spencerd9aac122007-03-26 09:32:31 +0000[diff] [blame]514</div>
515
516<!-------------------------------------------------------------------------- -->
517<div class="doc_subsection">
518 <a name="break-crit-edges">Break Critical Edges in CFG</a>
519</div>
520<div class="doc_text">
521 <p>Yet to be written.</p>
522</div>
523
524<!-------------------------------------------------------------------------- -->
525<div class="doc_subsection">
526 <a name="cee">Correlated Expression Elimination</a>
527</div>
528<div class="doc_text">
Reid Spenceraf4af3a2007-03-27 02:49:31 +0000[diff] [blame]529 <p>Correlated Expression Elimination propagates information from conditional
530 branches to blocks dominated by destinations of the branch. It propagates
531 information from the condition check itself into the body of the branch,
532 allowing transformations like these for example:
533 <pre>
534 if (i == 7)
535 ... 4*i; // constant propagation
536
537 M = i+1; N = j+1;
538 if (i == j)
539 X = M-N; // = M-M == 0;
540 </pre></p>
541
542 <p>This is called Correlated Expression Elimination because we eliminate or
543 simplify expressions that are correlated with the direction of a branch. In
544 this way we use static information to give us some information about the
545 dynamic value of a variable.</p>
Reid Spencerd9aac122007-03-26 09:32:31 +0000[diff] [blame]546</div>
547
548<!-------------------------------------------------------------------------- -->
549<div class="doc_subsection">
550 <a name="condprop">Conditional Propagation</a>
551</div>
552<div class="doc_text">
Reid Spenceraf4af3a2007-03-27 02:49:31 +0000[diff] [blame]553 <p>This pass propagates information about conditional expressions through the
554 program, allowing it to eliminate conditional branches in some cases.</p>
Reid Spencerd9aac122007-03-26 09:32:31 +0000[diff] [blame]555</div>
556
557<!-------------------------------------------------------------------------- -->
558<div class="doc_subsection">
559 <a name="constmerge">Merge Duplicate Global Constants</a>
560</div>
561<div class="doc_text">
562 <p>Yet to be written.</p>
563</div>
564
565<!-------------------------------------------------------------------------- -->
566<div class="doc_subsection">
Reid Spenceraf4af3a2007-03-27 02:49:31 +0000[diff] [blame]567 <a name="constprop">Constant Propagation</a>
Reid Spencerd9aac122007-03-26 09:32:31 +0000[diff] [blame]568</div>
569<div class="doc_text">
Reid Spenceraf4af3a2007-03-27 02:49:31 +0000[diff] [blame]570 <p>This file implements constant propagation and merging. It looks for
571 instructions involving only constant operands and replaces them with a
572 constant value instead of an instruction. For example:
573 <pre>add i32 1, 2</pre><br/>
574 becomes
575 <pre>i32 3</pre></p>
576 <p>NOTE: this pass has a habit of making definitions be dead. It is a good
577 idea to to run a <a href="#die">DIE</a> (Dead Instruction Elimination) pass
578 sometime after running this pass.</p>
Reid Spencerd9aac122007-03-26 09:32:31 +0000[diff] [blame]579</div>
580
581<!-------------------------------------------------------------------------- -->
582<div class="doc_subsection">
583 <a name="dce">Dead Code Elimination</a>
584</div>
585<div class="doc_text">
586 <p>Yet to be written.</p>
587</div>
588
589<!-------------------------------------------------------------------------- -->
590<div class="doc_subsection">
591 <a name="deadargelim">Dead Argument Elimination</a>
592</div>
593<div class="doc_text">
594 <p>Yet to be written.</p>
595</div>
596
597<!-------------------------------------------------------------------------- -->
598<div class="doc_subsection">
599 <a name="deadtypeelim">Dead Type Elimination</a>
600</div>
601<div class="doc_text">
602 <p>Yet to be written.</p>
603</div>
604
605<!-------------------------------------------------------------------------- -->
606<div class="doc_subsection">
607 <a name="die">Dead Instruction Elimination</a>
608</div>
609<div class="doc_text">
610 <p>Yet to be written.</p>
611</div>
612
613<!-------------------------------------------------------------------------- -->
614<div class="doc_subsection">
615 <a name="dse">Dead Store Elimination</a>
616</div>
617<div class="doc_text">
618 <p>Yet to be written.</p>
619</div>
620
621<!-------------------------------------------------------------------------- -->
622<div class="doc_subsection">
623 <a name="gcse">Global Common Subexpression Elimination</a>
624</div>
625<div class="doc_text">
626 <p>Yet to be written.</p>
627</div>
628
629<!-------------------------------------------------------------------------- -->
630<div class="doc_subsection">
631 <a name="globaldce">Dead Global Elimination</a>
632</div>
633<div class="doc_text">
634 <p>Yet to be written.</p>
635</div>
636
637<!-------------------------------------------------------------------------- -->
638<div class="doc_subsection">
639 <a name="globalopt">Global Variable Optimizer</a>
640</div>
641<div class="doc_text">
642 <p>Yet to be written.</p>
643</div>
644
645<!-------------------------------------------------------------------------- -->
646<div class="doc_subsection">
647 <a name="indmemrem">Indirect Malloc and Free Removal</a>
648</div>
649<div class="doc_text">
650 <p>Yet to be written.</p>
651</div>
652
653<!-------------------------------------------------------------------------- -->
654<div class="doc_subsection">
655 <a name="indvars">Canonicalize Induction Variables</a>
656</div>
657<div class="doc_text">
658 <p>Yet to be written.</p>
659</div>
660
661<!-------------------------------------------------------------------------- -->
662<div class="doc_subsection">
663 <a name="inline">Function Integration/Inlining</a>
664</div>
665<div class="doc_text">
666 <p>Yet to be written.</p>
667</div>
668
669<!-------------------------------------------------------------------------- -->
670<div class="doc_subsection">
671 <a name="insert-block-profiling">Insert instrumentation for block profiling</a>
672</div>
673<div class="doc_text">
674 <p>Yet to be written.</p>
675</div>
676
677<!-------------------------------------------------------------------------- -->
678<div class="doc_subsection">
679 <a name="insert-edge-profiling">Insert instrumentation for edge profiling</a>
680</div>
681<div class="doc_text">
682 <p>Yet to be written.</p>
683</div>
684
685<!-------------------------------------------------------------------------- -->
686<div class="doc_subsection">
687 <a name="insert-function-profiling">Insert instrumentation for function profiling</a>
688</div>
689<div class="doc_text">
690 <p>Yet to be written.</p>
691</div>
692
693<!-------------------------------------------------------------------------- -->
694<div class="doc_subsection">
695 <a name="insert-null-profiling-rs">Measure profiling framework overhead</a>
696</div>
697<div class="doc_text">
698 <p>Yet to be written.</p>
699</div>
700
701<!-------------------------------------------------------------------------- -->
702<div class="doc_subsection">
703 <a name="insert-rs-profiling-framework">Insert random sampling instrumentation framework</a>
704</div>
705<div class="doc_text">
706 <p>Yet to be written.</p>
707</div>
708
709<!-------------------------------------------------------------------------- -->
710<div class="doc_subsection">
711 <a name="instcombine">Combine redundant instructions</a>
712</div>
713<div class="doc_text">
714 <p>Yet to be written.</p>
715</div>
716
717<!-------------------------------------------------------------------------- -->
718<div class="doc_subsection">
719 <a name="internalize">Internalize Global Symbols</a>
720</div>
721<div class="doc_text">
722 <p>Yet to be written.</p>
723</div>
724
725<!-------------------------------------------------------------------------- -->
726<div class="doc_subsection">
727 <a name="ipconstprop">Interprocedural constant propagation</a>
728</div>
729<div class="doc_text">
730 <p>Yet to be written.</p>
731</div>
732
733<!-------------------------------------------------------------------------- -->
734<div class="doc_subsection">
735 <a name="ipsccp">Interprocedural Sparse Conditional Constant Propagation</a>
736</div>
737<div class="doc_text">
738 <p>Yet to be written.</p>
739</div>
740
741<!-------------------------------------------------------------------------- -->
742<div class="doc_subsection">
743 <a name="lcssa">Loop-Closed SSA Form Pass</a>
744</div>
745<div class="doc_text">
746 <p>Yet to be written.</p>
747</div>
748
749<!-------------------------------------------------------------------------- -->
750<div class="doc_subsection">
751 <a name="licm">Loop Invariant Code Motion</a>
752</div>
753<div class="doc_text">
754 <p>Yet to be written.</p>
755</div>
756
757<!-------------------------------------------------------------------------- -->
758<div class="doc_subsection">
759 <a name="loop-extract">Extract loops into new functions</a>
760</div>
761<div class="doc_text">
762 <p>Yet to be written.</p>
763</div>
764
765<!-------------------------------------------------------------------------- -->
766<div class="doc_subsection">
767 <a name="loop-extract-single">Extract at most one loop into a new function</a>
768</div>
769<div class="doc_text">
770 <p>Yet to be written.</p>
771</div>
772
773<!-------------------------------------------------------------------------- -->
774<div class="doc_subsection">
775 <a name="loop-reduce">Loop Strength Reduction</a>
776</div>
777<div class="doc_text">
778 <p>Yet to be written.</p>
779</div>
780
781<!-------------------------------------------------------------------------- -->
782<div class="doc_subsection">
783 <a name="loop-unroll">Unroll Loops</a>
784</div>
785<div class="doc_text">
786 <p>Yet to be written.</p>
787</div>
788
789<!-------------------------------------------------------------------------- -->
790<div class="doc_subsection">
791 <a name="loop-unswitch">Unswitch Loops</a>
792</div>
793<div class="doc_text">
794 <p>Yet to be written.</p>
795</div>
796
797<!-------------------------------------------------------------------------- -->
798<div class="doc_subsection">
799 <a name="loopsimplify">Canonicalize Natural Loops</a>
800</div>
801<div class="doc_text">
802 <p>Yet to be written.</p>
803</div>
804
805<!-------------------------------------------------------------------------- -->
806<div class="doc_subsection">
807 <a name="lower-packed">Lower Packed Operations</a>
808</div>
809<div class="doc_text">
810 <p>Yet to be written.</p>
811</div>
812
813<!-------------------------------------------------------------------------- -->
814<div class="doc_subsection">
815 <a name="lowerallocs">Lower allocations from instructions to calls</a>
816</div>
817<div class="doc_text">
818 <p>Yet to be written.</p>
819</div>
820
821<!-------------------------------------------------------------------------- -->
822<div class="doc_subsection">
823 <a name="lowergc">Lower GC intrinsics, for GCless code generators</a>
824</div>
825<div class="doc_text">
826 <p>Yet to be written.</p>
827</div>
828
829<!-------------------------------------------------------------------------- -->
830<div class="doc_subsection">
831 <a name="lowerinvoke">Lower Invoke and Unwind</a>
832</div>
833<div class="doc_text">
834 <p>Yet to be written.</p>
835</div>
836
837<!-------------------------------------------------------------------------- -->
838<div class="doc_subsection">
839 <a name="lowerselect">Lower Selects To Branches</a>
840</div>
841<div class="doc_text">
842 <p>Yet to be written.</p>
843</div>
844
845<!-------------------------------------------------------------------------- -->
846<div class="doc_subsection">
847 <a name="lowersetjmp">Lower Set Jump</a>
848</div>
849<div class="doc_text">
850 <p>Yet to be written.</p>
851</div>
852
853<!-------------------------------------------------------------------------- -->
854<div class="doc_subsection">
855 <a name="lowerswitch">Lower SwitchInst's to branches</a>
856</div>
857<div class="doc_text">
858 <p>Yet to be written.</p>
859</div>
860
861<!-------------------------------------------------------------------------- -->
862<div class="doc_subsection">
863 <a name="mem2reg">Promote Memory to Register</a>
864</div>
865<div class="doc_text">
866 <p>Yet to be written.</p>
867</div>
868
869<!-------------------------------------------------------------------------- -->
870<div class="doc_subsection">
871 <a name="mergereturn">Unify Function Exit Nodes</a>
872</div>
873<div class="doc_text">
874 <p>Yet to be written.</p>
875</div>
876
877<!-------------------------------------------------------------------------- -->
878<div class="doc_subsection">
879 <a name="predsimplify">Predicate Simplifier</a>
880</div>
881<div class="doc_text">
882 <p>Yet to be written.</p>
883</div>
884
885<!-------------------------------------------------------------------------- -->
886<div class="doc_subsection">
887 <a name="prune-eh">Remove unused exception handling info</a>
888</div>
889<div class="doc_text">
890 <p>Yet to be written.</p>
891</div>
892
893<!-------------------------------------------------------------------------- -->
894<div class="doc_subsection">
895 <a name="raiseallocs">Raise allocations from calls to instructions</a>
896</div>
897<div class="doc_text">
898 <p>Yet to be written.</p>
899</div>
900
901<!-------------------------------------------------------------------------- -->
902<div class="doc_subsection">
903 <a name="reassociate">Reassociate Expressions</a>
904</div>
905<div class="doc_text">
906 <p>Yet to be written.</p>
907</div>
908
909<!-------------------------------------------------------------------------- -->
910<div class="doc_subsection">
911 <a name="reg2mem">Demote Values to Memory</a>
912</div>
913<div class="doc_text">
914 <p>Yet to be written.</p>
915</div>
916
917<!-------------------------------------------------------------------------- -->
918<div class="doc_subsection">
919 <a name="scalarrepl">Scalar Replacement of Aggregates</a>
920</div>
921<div class="doc_text">
922 <p>Yet to be written.</p>
923</div>
924
925<!-------------------------------------------------------------------------- -->
926<div class="doc_subsection">
927 <a name="sccp">Sparse Conditional Constant Propagation</a>
928</div>
929<div class="doc_text">
930 <p>Yet to be written.</p>
931</div>
932
933<!-------------------------------------------------------------------------- -->
934<div class="doc_subsection">
935 <a name="simplify-libcalls">Simplify well-known library calls</a>
936</div>
937<div class="doc_text">
938 <p>Yet to be written.</p>
939</div>
940
941<!-------------------------------------------------------------------------- -->
942<div class="doc_subsection">
943 <a name="simplifycfg">Simplify the CFG</a>
944</div>
945<div class="doc_text">
946 <p>Yet to be written.</p>
947</div>
948
949<!-------------------------------------------------------------------------- -->
950<div class="doc_subsection">
951 <a name="strip">Strip all symbols from a module</a>
952</div>
953<div class="doc_text">
954 <p>Yet to be written.</p>
955</div>
956
957<!-------------------------------------------------------------------------- -->
958<div class="doc_subsection">
959 <a name="tailcallelim">Tail Call Elimination</a>
960</div>
961<div class="doc_text">
962 <p>Yet to be written.</p>
963</div>
964
965<!-------------------------------------------------------------------------- -->
966<div class="doc_subsection">
967 <a name="tailduplicate">Tail Duplication</a>
968</div>
969<div class="doc_text">
970 <p>Yet to be written.</p>
971</div>
972
973<!-- ======================================================================= -->
974<div class="doc_section"> <a name="transform">Utility Passes</a></div>
975<div class="doc_text">
976 <p>This section describes the LLVM Utility Passes.</p>
977</div>
978
979<!-------------------------------------------------------------------------- -->
980<div class="doc_subsection">
981 <a name="deadarghaX0r">Dead Argument Hacking (BUGPOINT ONLY)</a>
982</div>
983<div class="doc_text">
984 <p>Yet to be written.</p>
985</div>
986
987<!-------------------------------------------------------------------------- -->
988<div class="doc_subsection">
989 <a name="extract-blocks">Extract Basic Blocks From Module (BUGPOINT ONLY)</a>
990</div>
991<div class="doc_text">
992 <p>Yet to be written.</p>
993</div>
994
995<!-------------------------------------------------------------------------- -->
996<div class="doc_subsection">
997 <a name="emitbytecode">Bytecode Writer</a>
998</div>
999<div class="doc_text">
1000 <p>Yet to be written.</p>
1001</div>
1002
1003<!-------------------------------------------------------------------------- -->
1004<div class="doc_subsection">
1005 <a name="verify">Module Verifier</a>
1006</div>
1007<div class="doc_text">
1008 <p>Yet to be written.</p>
1009</div>
1010
1011<!-- *********************************************************************** -->
1012
1013<hr>
1014<address>
1015 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1016 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1017 <a href="http://validator.w3.org/check/referer"><img
1018 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1019
1020 <a href="mailto:rspencer@x10sys.com">Reid Spencer</a><br>
1021 <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
1022 Last modified: $Date$
1023</address>
1024
1025</body>
1026</html>