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 17 package 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
