| /* |
| * Copyright (C) 2008 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.dx.ssa; |
| |
| /** |
| * <h1>An introduction to SSA Form</h1> |
| * |
| * This package contains classes associated with dx's {@code SSA} |
| * intermediate form. This form is a static-single-assignment representation of |
| * Rop-form a method with Rop-form-like instructions (with the addition of a |
| * {@link PhiInsn phi instriction}. This form is intended to make it easy to |
| * implement basic optimization steps and register allocation so that a |
| * reasonably efficient register machine representation can be produced from a |
| * stack machine source bytecode.<p> |
| * |
| * <h2>Key Classes</h2> |
| * |
| * <h3>Classes related to conversion and lifetime</h3> |
| * <ul> |
| * <li> {@link Optimizer} is a singleton class containing methods for |
| * converting, optimizing, and then back-converting Rop-form methods. It's the |
| * typical gateway into the rest of the package. |
| * <li> {@link SsaConverter} converts a Rop-form method to SSA form. |
| * <li> {@link SsaToRop} converts an SSA-form method back to Rop form. |
| * </ul> |
| * |
| * <h3>Classes related to method representation</h3> |
| * <ul> |
| * <li> A {@link SsaMethod} instance represents a method. |
| * <li> A {@link SsaBasicBlock} instance represents a basic block, whose |
| * semantics are quite similar to basic blocks in |
| * {@link com.android.dx.rop Rop form}. |
| * <li> {@link PhiInsn} instances represent "phi" operators defined in SSA |
| * literature. They must be the first N instructions in a basic block. |
| * <li> {@link NormalSsaInsn} instances represent instructions that directly |
| * correspond to {@code Rop} form. |
| * </ul> |
| * |
| * <h3>Classes related to optimization steps</h3> |
| * <ul> |
| * <li> {@link MoveParamCombiner} is a simple step that ensures each method |
| * parameter is represented by at most one SSA register. |
| * <li> {@link SCCP} is a (partially implemented) sparse-conditional |
| * constant propogator. |
| * <li> {@link LiteralOpUpgrader} is a step that attempts to use constant |
| * information to convert math and comparison instructions into |
| * constant-bearing "literal ops" in cases where they can be represented in the |
| * output form (see {@link TranslationAdvice#hasConstantOperation}). |
| * <li> {@link ConstCollector} is a step that attempts to trade (modest) |
| * increased register space for decreased instruction count in cases where |
| * the same constant value is used repeatedly in a single method. |
| * <li> {@link DeadCodeRemover} is a dead code remover. This phase must |
| * always be run to remove unused phi instructions. |
| * </ul> |
| * |
| * <h2>SSA Lifetime</h2> |
| * The representation of a method in SSA form obeys slightly different |
| * constraints depending upon whether it is in the process of being converted |
| * into or out of SSA form. |
| * |
| * <h3>Conversion into SSA Form</h3> |
| * |
| * {@link SsaConverter#convertToSsaMethod} takes a {@code RopMethod} and |
| * returns a fully-converted {@code SsaMethod}. The conversion process |
| * is roughly as follows: |
| * |
| * <ol> |
| * <li> The Rop-form method, its blocks and their instructions are directly |
| * wrapped in {@code SsaMethod}, {@code SsaBasicBlock} and |
| * {@code SsaInsn} instances. Nothing else changes. |
| * <li> Critical control-flow graph edges are {@link SsaConverter#edgeSplit |
| * split} and new basic blocks inserted as required to meet the constraints |
| * necessary for the ultimate SSA representation. |
| * <li> A {@link LocalVariableExtractor} is run to produce a table of |
| * Rop registers to local variables necessary during phi placement. This |
| * step could also be done in Rop form and then updated through the preceding |
| * steps. |
| * <li> {@code Phi} instructions are {link SsaConverter#placePhiFunctions} |
| * placed in a semi-pruned fashion, which requires computation of {@link |
| * Dominators dominance graph} and each node's {@link DomFront |
| * dominance-frontier set}. |
| * <li> Finally, source and result registers for all instructions are {@link |
| * SsaRenamer renamed} such that each assignment is given a unique register |
| * number (register categories or widths, significant in Rop form, do not |
| * exist in SSA). Move instructions are eliminated except where necessary |
| * to preserve local variable assignments. |
| * </ol> |
| * |
| */ |
