1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.ssa;
18
19/**
20 * <h1>An introduction to SSA Form</h1>
21 *
22 * This package contains classes associated with dx's {@code SSA}
23 * intermediate form. This form is a static-single-assignment representation of
24 * Rop-form a method with Rop-form-like instructions (with the addition of a
25 * {@link PhiInsn phi instriction}. This form is intended to make it easy to
26 * implement basic optimization steps and register allocation so that a
27 * reasonably efficient register machine representation can be produced from a
28 * stack machine source bytecode.<p>
29 *
30 * <h2>Key Classes</h2>
31 *
32 * <h3>Classes related to conversion and lifetime</h3>
33 * <ul>
34 * <li> {@link Optimizer} is a singleton class containing methods for
35 * converting, optimizing, and then back-converting Rop-form methods. It's the
36 * typical gateway into the rest of the package.
37 * <li> {@link SsaConverter} converts a Rop-form method to SSA form.
38 * <li> {@link SsaToRop} converts an SSA-form method back to Rop form.
39 * </ul>
40 *
41 * <h3>Classes related to method representation</h3>
42 * <ul>
43 * <li> A {@link SsaMethod} instance represents a method.
44 * <li> A {@link SsaBasicBlock} instance represents a basic block, whose
45 * semantics are quite similar to basic blocks in
46 * {@link com.android.dx.rop Rop form}.
47 * <li> {@link PhiInsn} instances represent "phi" operators defined in SSA
48 * literature. They must be the first N instructions in a basic block.
49 * <li> {@link NormalSsaInsn} instances represent instructions that directly
50 * correspond to {@code Rop} form.
51 * </ul>
52 *
53 * <h3>Classes related to optimization steps</h3>
54 * <ul>
55 * <li> {@link MoveParamCombiner} is a simple step that ensures each method
56 * parameter is represented by at most one SSA register.
57 * <li> {@link SCCP} is a (partially implemented) sparse-conditional
58 * constant propogator.
59 * <li> {@link LiteralOpUpgrader} is a step that attempts to use constant
60 * information to convert math and comparison instructions into
61 * constant-bearing "literal ops" in cases where they can be represented in the
62 * output form (see {@link TranslationAdvice#hasConstantOperation}).
63 * <li> {@link ConstCollector} is a step that attempts to trade (modest)
64 * increased register space for decreased instruction count in cases where
65 * the same constant value is used repeatedly in a single method.
66 * <li> {@link DeadCodeRemover} is a dead code remover. This phase must
67 * always be run to remove unused phi instructions.
68 * </ul>
69 *
70 * <h2>SSA Lifetime</h2>
71 * The representation of a method in SSA form obeys slightly different
72 * constraints depending upon whether it is in the process of being converted
73 * into or out of SSA form.
74 *
75 * <h3>Conversion into SSA Form</h3>
76 *
77 * {@link SsaConverter#convertToSsaMethod} takes a {@code RopMethod} and
78 * returns a fully-converted {@code SsaMethod}. The conversion process
79 * is roughly as follows:
80 *
81 * <ol>
82 * <li> The Rop-form method, its blocks and their instructions are directly
83 * wrapped in {@code SsaMethod}, {@code SsaBasicBlock} and
84 * {@code SsaInsn} instances. Nothing else changes.
85 * <li> Critical control-flow graph edges are {@link SsaConverter#edgeSplit
86 * split} and new basic blocks inserted as required to meet the constraints
87 * necessary for the ultimate SSA representation.
88 * <li> A {@link LocalVariableExtractor} is run to produce a table of
89 * Rop registers to local variables necessary during phi placement. This
90 * step could also be done in Rop form and then updated through the preceding
91 * steps.
92 * <li> {@code Phi} instructions are {link SsaConverter#placePhiFunctions}
93 * placed in a semi-pruned fashion, which requires computation of {@link
94 * Dominators dominance graph} and each node's {@link DomFront
95 * dominance-frontier set}.
96 * <li> Finally, source and result registers for all instructions are {@link
97 * SsaRenamer renamed} such that each assignment is given a unique register
98 * number (register categories or widths, significant in Rop form, do not
99 * exist in SSA). Move instructions are eliminated except where necessary
100 * to preserve local variable assignments.
101 * </ol>
102 *
103 */
104