Sphinxify the lexicon doc.

[oota-llvm.git] / docs / Lexicon.rst

diff --git a/docs/Lexicon.rst b/docs/Lexicon.rst
new file mode 100644 (file)
index 0000000..6ebe614
--- /dev/null
+++ b/docs/Lexicon.rst
@@ -0,0 +1,194 @@
+.. _lexicon:
+
+================
+The LLVM Lexicon
+================
+
+.. note::
+
+    This document is a work in progress!
+
+Definitions
+===========
+
+A
+-
+
+**ADCE**
+    Aggressive Dead Code Elimination
+
+B
+-
+
+**BURS**
+
+    Bottom Up Rewriting System --- A method of instruction selection for code
+    generation.  An example is the `BURG
+    <http://www.program-transformation.org/Transform/BURG>`_ tool.
+
+C
+-
+
+**CSE**
+    Common Subexpression Elimination. An optimization that removes common
+    subexpression compuation. For example ``(a+b)*(a+b)`` has two subexpressions
+    that are the same: ``(a+b)``. This optimization would perform the addition
+    only once and then perform the multiply (but only if it's compulationally
+    correct/safe).
+
+D
+-
+
+**DAG**
+    Directed Acyclic Graph
+
+.. _derived pointer:
+.. _derived pointers:
+
+**Derived Pointer**
+    A pointer to the interior of an object, such that a garbage collector is
+    unable to use the pointer for reachability analysis. While a derived pointer
+    is live, the corresponding object pointer must be kept in a root, otherwise
+    the collector might free the referenced object. With copying collectors,
+    derived pointers pose an additional hazard that they may be invalidated at
+    any `safe point`_. This term is used in opposition to `object pointer`_.
+
+**DSA**
+    Data Structure Analysis
+
+**DSE**
+    Dead Store Elimination
+
+F
+-
+
+**FCA**
+    First Class Aggregate
+
+G
+-
+
+**GC**
+    Garbage Collection. The practice of using reachability analysis instead of
+    explicit memory management to reclaim unused memory.
+
+H
+-
+
+.. _heap:
+
+**Heap**
+    In garbage collection, the region of memory which is managed using
+    reachability analysis.
+
+I
+-
+
+**IPA**
+    Inter-Procedural Analysis. Refers to any variety of code analysis that
+    occurs between procedures, functions or compilation units (modules).
+
+**IPO**
+    Inter-Procedural Optimization. Refers to any variety of code optimization
+    that occurs between procedures, functions or compilation units (modules).
+
+**ISel**
+    Instruction Selection
+
+L
+-
+
+**LCSSA**
+    Loop-Closed Static Single Assignment Form
+
+**LICM**
+    Loop Invariant Code Motion
+
+**Load-VN**
+    Load Value Numbering
+
+**LTO**
+    Link-Time Optimization
+
+M
+-
+
+**MC**
+    Machine Code
+
+O
+-
+.. _object pointer:
+.. _object pointers:
+
+**Object Pointer**
+    A pointer to an object such that the garbage collector is able to trace
+    references contained within the object. This term is used in opposition to
+    `derived pointer`_.
+
+P
+-
+
+**PRE**
+    Partial Redundancy Elimination
+
+R
+-
+
+**RAUW**
+
+    Replace All Uses With. The functions ``User::replaceUsesOfWith()``,
+    ``Value::replaceAllUsesWith()``, and
+    ``Constant::replaceUsesOfWithOnConstant()`` implement the replacement of one
+    Value with another by iterating over its def/use chain and fixing up all of
+    the pointers to point to the new value.  See
+    also `def/use chains <ProgrammersManual.html#iterate_chains>`_.
+
+**Reassociation**
+    Rearranging associative expressions to promote better redundancy elimination
+    and other optimization.  For example, changing ``(A+B-A)`` into ``(B+A-A)``,
+    permitting it to be optimized into ``(B+0)`` then ``(B)``.
+
+.. _roots:
+.. _stack roots:
+
+**Root**
+    In garbage collection, a pointer variable lying outside of the `heap`_ from
+    which the collector begins its reachability analysis. In the context of code
+    generation, "root" almost always refers to a "stack root" --- a local or
+    temporary variable within an executing function.</dd>
+
+**RPO**
+    Reverse postorder
+
+S
+-
+
+.. _safe point:
+
+**Safe Point**
+    In garbage collection, it is necessary to identify `stack roots`_ so that
+    reachability analysis may proceed. It may be infeasible to provide this
+    information for every instruction, so instead the information may is
+    calculated only at designated safe points. With a copying collector,
+    `derived pointers`_ must not be retained across safe points and `object
+    pointers`_ must be reloaded from stack roots.
+
+**SDISel**
+    Selection DAG Instruction Selection.
+
+**SCC**
+    Strongly Connected Component
+
+**SCCP**
+    Sparse Conditional Constant Propagation
+
+**SRoA**
+    Scalar Replacement of Aggregates
+
+**SSA**
+    Static Single Assignment
+
+**Stack Map**
+    In garbage collection, metadata emitted by the code generator which
+    identifies `roots`_ within the stack frame of an executing function.