http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/59f6373b/compiler/src/main/java/org/apache/flex/abc/models/TreeModelEncoder.java ---------------------------------------------------------------------- diff --git a/compiler/src/main/java/org/apache/flex/abc/models/TreeModelEncoder.java b/compiler/src/main/java/org/apache/flex/abc/models/TreeModelEncoder.java new file mode 100644 index 0000000..7146c22 --- /dev/null +++ b/compiler/src/main/java/org/apache/flex/abc/models/TreeModelEncoder.java @@ -0,0 +1,1101 @@ +/* + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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 org.apache.flex.abc.models; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; + +import org.apache.flex.abc.semantics.ExceptionInfo; +import org.apache.flex.abc.semantics.Instruction; +import org.apache.flex.abc.semantics.MethodBodyInfo; +import org.apache.flex.abc.visitors.IDiagnosticsVisitor; +import org.apache.flex.abc.visitors.NilDiagnosticsVisitor; +import org.apache.flex.abc.graph.IFlowgraph; +import org.apache.flex.abc.graph.IBasicBlock; +import org.apache.flex.abc.graph.algorithms.DominatorTree.Multimap; + +/** + * The TreeModelEncoder translates the stack-oriented semantics + * of ABC bytecode into a tree-oriented model. + */ +public class TreeModelEncoder<T> +{ + /** + * Construct a new TreeModelEncoder. + * @param mbi - the method body of interest. + * @param visitor - the TreeModelVisitor that's interested. + * @param diagnosticsVisitor - a handler for any diagnostics generated. + */ + public TreeModelEncoder( MethodBodyInfo mbi, TreeModelVisitor<T> visitor, IDiagnosticsVisitor diagnosticsVisitor) + { + this.mbi = mbi; + this.visitor = visitor; + this.diagnosticsVisitor = diagnosticsVisitor; + + this.visitor.visit(this); + + setUpFrames(); + placePhiNodes(); + visitFrames(); + + this.visitor.visitEnd(); + } + + /** + * The Method of interest. + */ + private final MethodBodyInfo mbi; + + /** + * The model visitor we're driving. + */ + private final TreeModelVisitor<T> visitor; + + /** + * Receiver of any diagnostic output. + */ + private final IDiagnosticsVisitor diagnosticsVisitor; + + /** + * The Block currently under examination. + */ + IBasicBlock currentBlock; + + /** + * The FrameModelEncoder that's driving this TreeModelEncoder. + */ + private FrameModelEncoder encoder; + + /** + * The symbolic representations of this method's locals. + */ + ArrayList<Object> localSymbolicReferences = new ArrayList<Object>(); + + /** + * The symbolic representations of this method's value stack slots. + * Note: There is only one symbol for each element of the stack itself, + * not a symbol for each value the stack will hold over its lifetime. + */ + ArrayList<Object> valueSymbolicReferences = new ArrayList<Object>(); + + /** + * The symbolic representations of this method's scope stack slots. + * Note: There is only one symbol for each element of the stack itself, + * not a symbol for each scope the stack will hold over its lifetime. + */ + ArrayList<Object> scopeSymbolicReferences = new ArrayList<Object>(); + + /** + * Blocks modifying frame elements, keyed by + * the symbolic representation of the frame element. + */ + private Map<Object,Set<IBasicBlock>> a = new HashMap<Object,Set<IBasicBlock>>(); + + /** + * Get the MethodBodyInfo of the method being analyzed. + * @return the MethodBodyInfo being analyzed. + */ + public MethodBodyInfo getMethodBodyInfo() + { + return this.mbi; + } + + /** + * Get the method's flowgraph. + * @return the IFlowGraph of the method being analyzed. + */ + public IFlowgraph getCfg() + { + return this.mbi.getCfg(); + } + + /** + * Get the block currently being analyzed. + * @return the block currently being analyzed. + */ + public IBasicBlock getCurrentBlock() + { + return this.currentBlock; + } + + /** + * Get the index of the instruction currently being analyzed. + * @return the intra-Block index of the instruction currently being analyzed. + */ + public int getInstructionIndex() + { + return this.encoder.getInstructionIndex(); + } + + /** + * Do a preliminary pass over the method to set up + * the frames' extents and live-out sets. + */ + private void setUpFrames() + { + mbi.getCfg().traverseGraph( + new FrameModelEncoder( + this.mbi, + new FrameSetupVisitor(), + new NilDiagnosticsVisitor() + ) + ); + } + + /** + * Place phi-nodes at blocks' dominance frontiers + * to model dataflow merges in frame state. + */ + private void placePhiNodes() + { + int iterCount = 0; + + Multimap<IBasicBlock> df = getCfg().getDominatorTree().getDominanceFrontiers(); + + Map<IBasicBlock, Integer> hasAlready = new HashMap<IBasicBlock,Integer>(); + Map<IBasicBlock, Integer> work = new HashMap<IBasicBlock, Integer>(); + + for ( Object local: localSymbolicReferences ) + iterCount = placePhiNodes(iterCount, local, df, a, hasAlready, work); + for ( Object scope: scopeSymbolicReferences ) + iterCount = placePhiNodes(iterCount, scope, df, a, hasAlready, work); + for ( Object value: valueSymbolicReferences ) + iterCount = placePhiNodes(iterCount, value, df, a, hasAlready, work); + } + + /** + * Place phi-nodes for one particular element of the frame. + * @param initialIteration - the initial value of the iteration counter. + * @param v - the frame element being analyzed. + * @param df - the method's dominance frontiers. + * @param a - the map of Blocks that assign to various frame elements. + * @param hasAlready - a map of Block-to-iteration-count values, used + * to note a Block that already has a phi node for the element. + * @param work - a map of Block-to-iteration-count values, used + * to find Blocks that need further analysis. + */ + private int placePhiNodes( + final int initialIteration, + final Object v, + Multimap<IBasicBlock> df, + Map<Object,Set<IBasicBlock>> a, + Map<IBasicBlock,Integer> hasAlready, + Map<IBasicBlock,Integer> work + ) + { + if ( ! a.containsKey(v) ) + return initialIteration; + + int iterCount = initialIteration + 1; + + HashSet<IBasicBlock> w = new HashSet<IBasicBlock>(); + + for ( IBasicBlock x: a.get(v) ) + { + work.put(x, iterCount); + w.add(x); + } + + while ( ! w.isEmpty() ) + { + Iterator<IBasicBlock> it = w.iterator(); + IBasicBlock x = it.next(); + it.remove(); + + for ( IBasicBlock y: df.get(x) ) + { + if ( !hasAlready.containsKey(y) || hasAlready.get(y).intValue() < iterCount ) + { + placePhiNode(y,v); + hasAlready.put(y, iterCount); + + if ( !work.containsKey(y) || work.get(y).intValue() < iterCount ) + { + work.put(y, iterCount); + w.add(y); + } + } + } + } + + return iterCount; + } + + /** + * Place a phi-node for a particular (Block,frame element) tuple. + * @param target - the Block. + * @param frameKey - the variable. + */ + void placePhiNode(IBasicBlock target, Object frameKey) + { + Frame targetFrame = getFrame(target); + + // Figure out which value this is. + + int idx = this.localSymbolicReferences.indexOf(frameKey); + + if ( idx != -1 ) + { + if ( needsInitializer(targetFrame.locals, idx) ) + setFrameElement(targetFrame.locals, idx, visitor.addMergePoint(currentBlock)); + } + else + { + idx = this.valueSymbolicReferences.indexOf(frameKey); + + if ( idx != -1 ) + { + if ( needsInitializer(targetFrame.values, idx) ) + setFrameElement(targetFrame.values, idx, visitor.addMergePoint(currentBlock)); + } + else + { + idx = scopeSymbolicReferences.indexOf(frameKey); + assert idx != -1; + if ( needsInitializer(targetFrame.scopes, idx) ) + setFrameElement(targetFrame.scopes, idx, visitor.addMergePoint(currentBlock)); + } + } + } + + /** + * Determine if a particular frame element needs an initializer. + * @param elements - the frame elements (locals, scope stack, or value stack). + * @param idx - the index of the frame element of interest. + * @return true if the given index has no initializer object. + */ + private boolean needsInitializer(ArrayList<? extends Object> elements, int idx) + { + return ( elements.size() <= idx || elements.get(idx) == null ); + } + + /** + * Initialize a frame element with an anonymous marker object if necessary. + * @param elements - the frame elements (locals, scope stack, or value stack). + * @param idx - the index of the frame element of interest. + */ + private void touchFrameElement(ArrayList<Object> elements, int idx) + { + if ( needsInitializer(elements, idx) ) + setFrameElement(elements, idx, new Object()); + } + + /** + * Set a frame element. + * @param elements - the frame elements (locals, scope stack, or value stack). + * @param idx - the index of the frame element of interest. + * @param value - the value to set. + */ + private <E> void setFrameElement(ArrayList<E> elements, int idx, final E value) + { + while ( elements.size() <= idx ) + elements.add(null); + elements.set(idx, value); + } + + /** + * Modify a frame element; touch it and add the modifying Block to its + * set of assigning blocks. + * @param elements - the frame elements (locals, scope stack, or value stack). + * @param idx - the index of the frame element of interest. + * @param b - the Block that modifies the element. + */ + private void modifyFrameElement(ArrayList<Object> elements, int idx, IBasicBlock b) + { + touchFrameElement(elements,idx); + + if ( ! a.containsKey(elements.get(idx)) ) + a.put(elements.get(idx), new HashSet<IBasicBlock>()); + a.get(elements.get(idx)).add(b); + } + + /** + * Visit each block, its associated Frame, and the + * instructions in each block, showing each in turn + * to the TreeModelVisitor and recording its results + * in the Frame. + */ + private void visitFrames() + { + ArrayList<T> parameters = new ArrayList<T>(); + + // Load the initial frame's locals with parameter information. + for ( int i = 0; i < this.mbi.getMethodInfo().getParamCount(); i++ ) + parameters.add(visitor.translateParameter(i)); + + Frame startFrame = getFrame(this.mbi.getCfg().getStartBlock()); + startFrame.locals.addAll(parameters); + + // Initialize exception-handling targets with the exception variable, + // and set up a dataflow merge node for each local that may be read + // in the block. + // TODO: This encoder makes pessimistic assumptions about dataflow + // into the locals, i.e., it assumes every exception handler is + // globally reachable. + for ( ExceptionInfo ex: this.mbi.getExceptions() ) + { + IBasicBlock catchTarget = this.mbi.getCfg().getBlock(ex.getTarget()); + Frame catchFrame = getFrame(catchTarget); + + setFrameElement(catchFrame.values, 0, visitor.translateExceptionVariable(ex.getCatchVar(), ex.getExceptionType())); + + for ( int i = 0; i < parameters.size(); i++ ) + { + catchFrame.locals.add(visitor.addMergePoint(catchTarget)); + @SuppressWarnings("unchecked") + TreeModelVisitor.IMergePoint<T> mergeNode = (TreeModelVisitor.IMergePoint<T>)catchFrame.locals.get(i); + mergeNode.addValue(parameters.get(i)); + } + + // Initialize the other locals' merge nodes, which are initially empty. + for ( int i = parameters.size(); i < localSymbolicReferences.size(); i++ ) + { + catchFrame.locals.add(visitor.addMergePoint(catchTarget)); + } + } + + this.encoder = new FrameModelEncoder( this.mbi, new ModelDrivingVisitor(this.visitor), this.diagnosticsVisitor ); + this.mbi.getCfg().traverseGraph( this.encoder ); + } + + /** + * A representation of an AVM "frame," the local variables, scope stack slots, + * and value stack slots used in a particular Block of the method's flowgraph. + */ + public class Frame + { + /** + * The local variables used in the Block. + */ + public final ArrayList<T> locals = new ArrayList<T>(); + + /** + * The scope stack slots used in the Block. + */ + public final ArrayList<T> scopes = new ArrayList<T>(); + + /** + * The value stack slots used in the Block. + */ + public final ArrayList<T> values = new ArrayList<T>(); + + /** + * @return the value on top of the value stack. + */ + public T tos() + { + return this.values.get(valueStackDepth()); + } + + /** + * Remove a value from the value stack. + * Visitors must modify the Frame, but should + * maintain their own modifiable view of it. + */ + private T popValue() + { + return popElement(this.values); + } + + /** + * Push a value onto the value stack. + * Visitors must modify the Frame, but should + * maintain their own modifiable view of it. + */ + private T pushValue(T value) + { + this.values.add(value); + return value; + } + + /** + * Push a value onto the scope stack. + * Visitors must modify the Frame, but should + * maintain their own modifiable view of it. + */ + private T pushScope(T scope) + { + this.scopes.add(scope); + return scope; + } + + /** + * Pop a value off the scope stack. + * Visitors must modify the Frame, but should + * maintain their own modifiable view of it. + */ + private T popScope() + { + return popElement(this.scopes); + } + + /** + * Get a local variable. + * Visitors must modify the Frame, but should + * maintain their own modifiable view of it. + */ + private T getlocal(int idx) + { + adjustSize(this.locals, idx+1); + return this.locals.get(idx); + } + + /** + * Set a local variable. + * Visitors must modify the Frame, but should + * maintain their own modifiable view of it. + */ + private T setlocal(int idx, T value) + { + adjustSize(this.locals, idx+1); + this.locals.set(idx, value); + propagateLocalToCatchBlocks(idx,value); + + return value; + } + + /** + * Get a scope object. + * Visitors must modify the Frame, but should + * maintain their own modifiable view of it. + */ + private T getscopeobject(int idx) + { + adjustSize(this.scopes, idx+1); + return this.scopes.get(idx); + } + + /** + * Verify that the value stack contains + * at least the required number of live values. + * @param required - the numbe of values required. + * @return true if the value stack has the required number of values. + */ + private boolean verifyStackDepth(int required) + { + return this.values.size() >= required; + } + + /** + * @return the number of live values on the value stack. + */ + private int valueStackDepth() + { + return this.values.size() - 1; + } + + /** + * Verify that the scope stack contains + * at least the required number of live values. + * @param required - the numbe of values required. + * @return true if the scope stack has the required number of values. + */ + private boolean verifyScopeDepth(int required) + { + return this.scopes.size() >= required; + } + + /** + * @return the number of live values on the scope stack. + */ + @SuppressWarnings("unused") + private int scopeStackDepth() + { + return this.scopes.size() - 1; + } + } + + /** + * Propagate a local variable's value to all catch blocks. + * TODO: this should only propagate to catch blocks reachable + * from the current block; this code errs on the side of pessimism. + * @param idx the index of the local. + * @param value the value to propagate. + */ + void propagateLocalToCatchBlocks(int idx, T value) + { + for ( ExceptionInfo ex: mbi.getExceptions() ) + { + IBasicBlock catchTarget = mbi.getCfg().getBlock(ex.getTarget()); + Frame catchFrame = getFrame(catchTarget); + + if ( catchFrame.locals.get(idx) instanceof TreeModelVisitor.IMergePoint ) + { + @SuppressWarnings("unchecked") + TreeModelVisitor.IMergePoint<T> mergeNode = (TreeModelVisitor.IMergePoint<T>)catchFrame.locals.get(idx); + mergeNode.addValue(value); + } + // else it's an exception variable. + } + } + + /** + * Active Frames, keyed by their generating Block. + */ + private Map<IBasicBlock,Frame> framesByBlock = new HashMap<IBasicBlock,Frame>(); + + /** + * Get the Frame that corresponds to a Block. + * @param b - the Block of interest. + * @return the Frame mapped to the Block. + */ + public Frame getFrame(IBasicBlock b) + { + if ( ! this.framesByBlock.containsKey(b) ) + this.framesByBlock.put(b, new Frame()); + return this.framesByBlock.get(b); + } + + /** + * The FrameSetupVisitor creates Frame objects for the Blocks, + * and drives the modifyFrameElement calls that initialize + * the map of Blocks that assign values to specific frame elements. + */ + private class FrameSetupVisitor implements FrameModelVisitor<T> + { + IBasicBlock currentBlock = null; + BlockState blockState = null; + + public void visit(FrameModelEncoder encoder) + { + } + + public void visitEnd() + { + } + + public T noFrameEffect(Instruction i) + { + return null; + } + + public T consumeValue(Instruction i, int count) + { + // The model driving visitor detects stack underflow. + blockState.stackDepth = Math.max(blockState.stackDepth - count, 0); + return null; + } + + /** + * Handle an instruction that pushes a value onto the stack. + * @param i - the Instruction. + */ + public T produceValue(Instruction i) + { + modifyFrameElement(valueSymbolicReferences, blockState.stackDepth, currentBlock); + blockState.stackDepth++; + return null; + } + + public T consumeAndProduceValue(Instruction i, int consumeCount) + { + consumeValue(null, consumeCount); + produceValue(null); + return null; + } + + public T branch(Instruction i, IBasicBlock target) + { + return null; + } + + public T multiwayBranch(Instruction i, Collection<IBasicBlock> targets) + { + return null; + } + + public T getlocal(Instruction i, int idx) + { + touchFrameElement(localSymbolicReferences, idx); + return null; + } + + public T setlocal(Instruction i, int idx) + { + modifyFrameElement(localSymbolicReferences, idx, currentBlock); + return null; + } + + public void modifyLocal(Instruction i, int idx) + { + modifyFrameElement(localSymbolicReferences, idx, currentBlock); + } + + public T moveValueToScopeStack(Instruction i) + { + consumeValue(null, 1); + modifyFrameElement(scopeSymbolicReferences, blockState.scopeDepth, currentBlock); + blockState.scopeDepth++; + return null; + } + + public T popscope(Instruction i) + { + blockState.scopeDepth = Math.max(blockState.scopeDepth - 1, 0); + return null; + } + + public T getScopeobject(Instruction i, int idx) + { + touchFrameElement(scopeSymbolicReferences, idx); + return null; + } + + public T hasnext2(Instruction i) + { + modifyFrameElement(localSymbolicReferences, (Integer)i.getOperand(0), currentBlock); + modifyFrameElement(localSymbolicReferences, (Integer)i.getOperand(1), currentBlock); + return null; + } + + public T dup(Instruction i) + { + produceValue(null); + return null; + } + + public T swap(Instruction i) + { + // No effect on the frame setup. + return null; + } + + public boolean visitBlock(IBasicBlock b) + { + if ( visited.add(b) ) + { + assert this.currentBlock == null; + this.currentBlock = b; + this.blockState = getBlockState(b); + return true; + } + else + { + return false; + } + } + + /** + * Blocks visisted so far. + */ + private Set<IBasicBlock> visited = new HashSet<IBasicBlock>(); + + /** + * End the visit to a block; ensure that all its + * frame elements are in place. + */ + public void visitEndBlock(IBasicBlock b) + { + for ( int i = 0; i < this.blockState.stackDepth; i++ ) + touchFrameElement(valueSymbolicReferences, i); + + for ( int i = 0; i < this.blockState.scopeDepth; i++ ) + touchFrameElement(scopeSymbolicReferences, i); + + this.currentBlock = null; + this.blockState = null; + } + + /** + * Propagate value/scope stack depth information + * from one Block to its target block. + */ + public void visitEdge(IBasicBlock from, IBasicBlock target) + { + assert(from == this.currentBlock); + BlockState targetState = getBlockState(target); + + targetState.stackDepth = blockState.stackDepth; + targetState.scopeDepth = blockState.scopeDepth; + } + + + /** + * Get the scope/value stack depth tracker for a Block. + * @param b - the Block of interest. + * @return the BlockState tracker mapped to it. + */ + private BlockState getBlockState(IBasicBlock b) + { + if ( ! this.statesByBlock.containsKey(b) ) + this.statesByBlock.put(b, new BlockState()); + return this.statesByBlock.get(b); + } + + private Map<IBasicBlock, BlockState> statesByBlock = new HashMap<IBasicBlock,BlockState>(); + } + + private static class BlockState + { + int stackDepth = 0; + int scopeDepth = 0; + } + + /** + * The ModelDrivingVisitor makes a second pass over the method's + * control flow graph, after the Frames have been initialized and + * dataflow merge points placed, and drives the visitor's traversal + * of the method. + */ + private class ModelDrivingVisitor implements FrameModelVisitor<T> + { + ModelDrivingVisitor(TreeModelVisitor<T> visitor) + { + this.visitor = visitor; + } + + final TreeModelVisitor<T> visitor; + + public void visit(FrameModelEncoder encoder) + { + assert(encoder == TreeModelEncoder.this.encoder); + } + + public void visitEnd() + { + TreeModelEncoder.this.encoder = null; + } + + /** + * The Frame that corresponds to the block being visited. + */ + Frame currentFrame = null; + + @Override + public T noFrameEffect(Instruction i) + { + return visitor.translate(i, noOperands()); + } + + /** + * Handle an instruction that consumes value stack elements. + * @param i - the Instruction. + * @param count - the number of value stack elements consumed. + */ + public T consumeValue(Instruction i, int count) + { + if ( this.currentFrame.verifyStackDepth(count) ) + { + ArrayList<T> operands = new ArrayList<T>(count); + for ( int j = 0; j < count; j++ ) + operands.add(this.currentFrame.popValue()); + return visitor.translate(i, operands); + } + else + { + return visitor.valueStackUnderflow(i, count); + } + } + + /** + * Handle an instruction that pushes a value onto the stack. + * @param i - the Instruction. + */ + public T produceValue(Instruction i) + { + return this.currentFrame.pushValue(visitor.translate(i, noOperands())); + } + + /** + * Handle an instruction that consumes value stack elements, + * and then pushes a new value onto the stack. + * @param i - the Instruction. + * @param consumeCount - the number of value stack elements consumed. + */ + public T consumeAndProduceValue(Instruction i, int consumeCount) + { + if ( this.currentFrame.verifyStackDepth(consumeCount) ) + { + ArrayList<T> operands = new ArrayList<T>(consumeCount); + for ( int j = 0; j < consumeCount; j++ ) + operands.add(this.currentFrame.popValue()); + return this.currentFrame.pushValue(visitor.translate(i, operands)); + } + else + { + return visitor.valueStackUnderflow(i, consumeCount); + } + } + + /** + * Handle a branch instruction. + * @param i - the Instruction. + * @param target - the Instruction's target. Instructions with + * fall-through semantics also implicitly target the next Block. + */ + public T branch(Instruction i, IBasicBlock target) + { + return visitor.translateBranch(i, singleOperand(target)); + } + + /** + * Handle a multibranch instruction. + * @param i - the Instruction. + * @param targets - the Instruction's targets. + */ + public T multiwayBranch(Instruction i, Collection<IBasicBlock> targets) + { + return visitor.translateBranch(i, targets); + } + + /** + * Get a local variable, leaving its value on the stack. + * @param i - the Instruction. + * @param idx - the variable's index. + */ + public T getlocal(Instruction i, int idx) + { + adjustSize(currentFrame.locals, idx + 1); + T result = visitor.translate(i, singleOperand(this.currentFrame.getlocal(idx))); + this.currentFrame.pushValue(result); + return result; + } + + /** + * Set a local variable, comsuming a value from the stack. + * @param i - the Instruction. + * @param idx - the variable's index. + */ + public T setlocal(Instruction i, int idx) + { + adjustSize(currentFrame.locals, idx + 1); + if ( this.currentFrame.verifyStackDepth(1) ) + { + T result = visitor.translate(i, singleOperand(this.currentFrame.popValue())); + return this.currentFrame.setlocal(idx, result); + } + else + { + return this.currentFrame.setlocal(idx, visitor.valueStackUnderflow(i, 1)); + } + } + + /** + * Modify a local variable. + * @param i - the Instruction. + * @param idx - the variable's index. + */ + public void modifyLocal(Instruction i, int idx) + { + visitor.translate(i, noOperands()); + } + + /** + * Pop a value off the value stack and push it on the scope stack. + * @param i - the Instruction (an OP_pushscope). + */ + public T moveValueToScopeStack(Instruction i) + { + if ( this.currentFrame.verifyStackDepth(1) ) + return this.currentFrame.pushScope(visitor.translate(i, singleOperand(this.currentFrame.popValue()))); + else + return visitor.valueStackUnderflow(i, 1); + } + + /** + * Pop a value off the scope stack. + * @param i - the Instruction (an OP_popscope). + */ + public T popscope(Instruction i) + { + if ( this.currentFrame.verifyScopeDepth(1) ) + return visitor.translate(i, singleOperand(this.currentFrame.popScope())); + else + return visitor.scopeStackUnderflow(i, 1); + + } + + /** + * Get a particular scope stack element. + * @param i - the Instruction. + * @param idx - the index of the scope element. + */ + public T getScopeobject(Instruction i, int idx) + { + if ( this.currentFrame.verifyScopeDepth(idx+1) ) + return this.currentFrame.pushValue(visitor.translate(i, singleOperand(this.currentFrame.scopes.get(idx)))); + else + return visitor.scopeStackUnderflow(i, 1); + } + + /** + * Handle the special-case hasnext2 instruction. + * @param i - the Instruction. + */ + public T hasnext2(Instruction i) + { + return null; + } + + /** + * Handle the stack-maintenance dup instruction. + * @param i - the Instruction. + */ + public T dup(Instruction i) + { + if ( this.currentFrame.verifyStackDepth(1) ) + { + return this.currentFrame.pushValue(visitor.translate(i, singleOperand(this.currentFrame.tos()))); + } + else + { + return visitor.valueStackUnderflow(i, 1); + } + + } + + /** + * Handle the stack-maintenance swap instruction. + * @param i - the Instruction. + */ + public T swap(Instruction i) + { + if ( this.currentFrame.verifyStackDepth(2) ) + { + int stackDepth = this.currentFrame.valueStackDepth(); + T temp = visitor.translate(i, singleOperand(this.currentFrame.tos())); + this.currentFrame.values.set( stackDepth, this.currentFrame.values.get(stackDepth-1) ); + this.currentFrame.values.set( stackDepth - 1, temp); + return this.currentFrame.tos(); + } + else + { + return visitor.valueStackUnderflow(i, 2); + } + } + + @Override + public boolean visitBlock(IBasicBlock b) + { + Frame frame = getFrame(b); + currentBlock = b; + this.currentFrame = frame; + + if ( visitor.visitBlock(b) ) + { + return true; + } + else + { + // Tear down. + this.currentFrame = null; + currentBlock = null; + return false; + } + + } + + @Override + public void visitEndBlock(IBasicBlock b) + { + visitor.visitEnd(b); + this.currentFrame = null; + currentBlock = null; + } + + @Override + public void visitEdge(IBasicBlock from, IBasicBlock target) + { + assert getFrame(from) == this.currentFrame; + + Frame targetFrame = getFrame(target); + + for ( int i = 0; i < this.currentFrame.locals.size(); i++ ) + addInitializer(i, targetFrame.locals, this.currentFrame.getlocal(i)); + for ( int i = 0; i < this.currentFrame.values.size(); i++ ) + addInitializer(i, targetFrame.values, this.currentFrame.values.get(i)); + for ( int i = 0; i < this.currentFrame.scopes.size(); i++ ) + addInitializer(i, targetFrame.scopes, this.currentFrame.getscopeobject(i)); + } + + + private void addInitializer(final int i, ArrayList<T> target, T value) + { + if ( target.size() <= i ) + { + adjustSize(target, i); + target.add(value); + } + else if ( target.get(i) instanceof TreeModelVisitor.IMergePoint<?> ) + { + @SuppressWarnings("unchecked") + TreeModelVisitor.IMergePoint<T> phi = (TreeModelVisitor.IMergePoint<T>) target.get(i); + phi.addValue(value); + } + else if ( target.get(i) == null ) + { + target.set(i, value); + } + else + { + // TODO: Verify that the existing value and the current value are the same. + } + } + + /** + * Build an operands Collection from a single operand. + * @param operand - the operand. + * @return the operand, wrapped in a Collection. + */ + private <X> Collection<X> singleOperand(X operand) + { + ArrayList<X> result = new ArrayList<X>(1); + result.add(operand); + return result; + } + + /** + * @return an empty list, approprately cast. + */ + private Collection<T> noOperands() + { + return Collections.emptyList(); + } + } + + /** + * Adjust the size of a collection of frame elements. + * @param frameElements - the frame elements of interest. + * @param idx - the minimum size of the frame element. + */ + private static <X> void adjustSize(ArrayList<X> frameElements, int idx) + { + while(frameElements.size() < idx ) + frameElements.add(null); + } + + /** + * Pop a value off a collection of frame elements. + * @param frameElements - the frame elements of interest. + * @return the last element in the collection, which + * has been removed from the collection. + */ + static <X> X popElement(ArrayList<X> frameElements) + { + int lastIdx = frameElements.size() - 1; + return frameElements.remove(lastIdx); + } +}
http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/59f6373b/compiler/src/main/java/org/apache/flex/abc/models/TreeModelVisitor.java ---------------------------------------------------------------------- diff --git a/compiler/src/main/java/org/apache/flex/abc/models/TreeModelVisitor.java b/compiler/src/main/java/org/apache/flex/abc/models/TreeModelVisitor.java new file mode 100644 index 0000000..a11b0e6 --- /dev/null +++ b/compiler/src/main/java/org/apache/flex/abc/models/TreeModelVisitor.java @@ -0,0 +1,149 @@ +/* + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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 org.apache.flex.abc.models; + +import java.util.Collection; + +import org.apache.flex.abc.graph.IBasicBlock; +import org.apache.flex.abc.semantics.Instruction; +import org.apache.flex.abc.semantics.Name; + +/** + * A TreeModelVisitor translates stack-oriented + * operations into a operation/operands view of + * an ABC method body. + */ +public interface TreeModelVisitor<T> +{ + /** + * Begin visiting a method's frames. + * @param model - the TreeModelEncoder that's + * driving the visitor. + */ + public void visit(TreeModelEncoder<T> model); + + /** + * Finish visiting a method and its frames. + */ + public void visitEnd(); + + /** + * Begin a visit to a block. + * @param b the IBasicBlock to be visited. + * @return true if the encoder should continue visiting the block. + */ + public boolean visitBlock(IBasicBlock b); + + /** + * Finish visiting a block. + * @param b the last IBasicBlock to be confirmed to-be-visited by visitBlock(). + */ + public void visitEnd(IBasicBlock b); + + /** + * Translate an Instruction and its operands into + * an intermediate form. + * @param insn - the Instruction that encoded this operation. + * @param operands - the Instruction's operands, usually from + * the ABC value stack. + * @return an equivalent representation of the + * operation denoted by the instruction/operands tuple. + */ + public T translate(Instruction insn, Collection<T> operands); + + /** + * Translate a branch Instruction and its targets into + * an intermediate form. + * @param insn - the Instruction that encoded this operation. + * @param targets - the Instruction's targets. + * @return an equivalent representation of the + * operation denoted by the instruction/targets tuple. + */ + public T translateBranch(Instruction insn, Collection<IBasicBlock> targets); + + /** + * Recover from a value stack underflow condition. + * @param insn - the Instruction that attempted to encode + * this operation. + * @param count - the number of stack values required. + * @return a representation of the recovery action; + * returning some type of "bottom value" is recommended. + */ + public T valueStackUnderflow(Instruction insn, int count); + + /** + * Recover from a scope stack underflow condition. + * @param insn - the Instruction that attempted to encode + * this operation. + * @param count - the number of scope stack values required. + * @return a representation of the recovery action; + * returning some type of "bottom value" is recommended. + */ + public T scopeStackUnderflow(Instruction insn, int count); + + /** + * Get a representation of a function actual parameter. + * @param paramNumber - the parameter number. + * @return a representation of the parameter as an + * initializing value. + */ + public T translateParameter(int paramNumber); + + /** + * Get a representation of an exception variable. + * @param varName the exception variable's name. + * @param varType the exception variable's type. + * @return a representation of the exception + * variable as an initializing value. + */ + public T translateExceptionVariable(Name varName, Name varType); + + /** + * Add a merge node, where values from several blocks + * combine in the dataflow graph. + * @param toInit - the Block where these values combine. + * @return a representation of the merge point; this + * object must implement @code{IMergePoint<T>}. + */ + public T /* must implement IMergePoint<T> */ addMergePoint(IBasicBlock toInit); + + /** + * IMergePoint models a point where several predecessors' + * values combine in the dataflow graph. + */ + public interface IMergePoint<T> + { + /** + * Add a predecessor's value to the collection + * of predecessor values. The implementation + * is allowed to merge equal values, but may + * also choose not to do so. + * @param value - the new precedecessor value. + */ + public void addValue(T value); + + /** + * Get the values that predecessor blocks contributed + * to this dataflow merge point. + * @return the collection of predecessor values. + */ + public Collection<T> getValues(); + } +} http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/59f6373b/compiler/src/main/java/org/apache/flex/abc/models/package.html ---------------------------------------------------------------------- diff --git a/compiler/src/main/java/org/apache/flex/abc/models/package.html b/compiler/src/main/java/org/apache/flex/abc/models/package.html new file mode 100644 index 0000000..8f97e93 --- /dev/null +++ b/compiler/src/main/java/org/apache/flex/abc/models/package.html @@ -0,0 +1,29 @@ +<!-- + + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You 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. + +--> + +<html> +<body> + +This package contains higher-level models of a method body +and encoders to translate from the basic ABC model +into these higher-level models. + +</body> +</html> + http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/59f6373b/compiler/src/main/java/org/apache/flex/abc/optimize/DeadCodeFilter.java ---------------------------------------------------------------------- diff --git a/compiler/src/main/java/org/apache/flex/abc/optimize/DeadCodeFilter.java b/compiler/src/main/java/org/apache/flex/abc/optimize/DeadCodeFilter.java new file mode 100644 index 0000000..0c2e74c --- /dev/null +++ b/compiler/src/main/java/org/apache/flex/abc/optimize/DeadCodeFilter.java @@ -0,0 +1,156 @@ +/* + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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 org.apache.flex.abc.optimize; + +import java.util.Iterator; +import java.util.List; + +import org.apache.flex.abc.ABCConstants; +import org.apache.flex.abc.graph.IBasicBlock; +import org.apache.flex.abc.graph.IFlowgraph; +import org.apache.flex.abc.semantics.ExceptionInfo; +import org.apache.flex.abc.semantics.Instruction; +import org.apache.flex.abc.semantics.InstructionFactory; +import org.apache.flex.abc.semantics.MethodBodyInfo; +import org.apache.flex.abc.visitors.DelegatingMethodBodyVisitor; +import org.apache.flex.abc.visitors.IDiagnosticsVisitor; +import org.apache.flex.abc.visitors.IMethodBodyVisitor; + +/** + * DeadCodeFilter rebuilds the method's result InstructionList by walking the + * control flow graph at visitEnd() time, and resets its delegate's instructions + * to the pruned InstructionList. + */ +public class DeadCodeFilter extends DelegatingMethodBodyVisitor +{ + /** + * Constructor. + * + * @param mbi - the MethodBodyInfo to be analyzed. + * @param delegate - the next IMethodBodyVisitor in the chain. + */ + public DeadCodeFilter(MethodBodyInfo mbi, IMethodBodyVisitor delegate, IDiagnosticsVisitor diagnostics) + { + super(delegate); + this.mbi = mbi; + this.diagnostics = diagnostics; + } + + /** + * The MethodBodyInfo under analysis. + */ + protected final MethodBodyInfo mbi; + + /** + */ + protected final IDiagnosticsVisitor diagnostics; + + /** + * Walk the control flow graph and remove unreachable blocks. + */ + @Override + public void visitEnd() + { + IFlowgraph cfg = this.mbi.getCfg(); + List<IBasicBlock> blocks = cfg.getBlocksInEntryOrder(); + boolean lastBlockWasReachable = true; + + int blockIdx = 0; + while ( blockIdx < blocks.size() ) + { + IBasicBlock b = blocks.get(blockIdx); + boolean isReachable = cfg.isReachable(b); + + // Only advance the block index if the current + // block is removed. + int previousBlockCount = blocks.size(); + + if ( ! isReachable ) + { + // Don't remove unreachable blocks that are the final block in an exception handler, + // unless they're also the first block in the exception handler. The AVM depends on + // these blocks under some circumstances. However, the block's instructions can be + // coalesced to a single OP_nop. + boolean safeToRemove = true; + + for ( ExceptionInfo ex: this.mbi.getExceptions() ) + { + IBasicBlock toBlock = this.mbi.getCfg().getBlock(ex.getTo()); + if ( b.equals(toBlock) ) + { + IBasicBlock fromBlock = this.mbi.getCfg().getBlock(ex.getFrom()); + + int tryFrom = blocks.indexOf(fromBlock); + int tryTo = blocks.indexOf(toBlock); + assert tryFrom >= 0 && tryTo >= tryFrom; + + for ( int j = tryTo - 1; safeToRemove && j >= tryFrom; j-- ) + safeToRemove = !cfg.isReachable(blocks.get(j)); + + if ( !safeToRemove ) + { + // Can't remove it, but compact it: remove executable + // instructions, then write a single OP_nop as necessary. + + Iterator<Instruction> it = b.getInstructions().iterator(); + + while ( it.hasNext() ) + { + Instruction insn = it.next(); + + if ( insn.isExecutable() ) + it.remove(); + } + + b.getInstructions().add(InstructionFactory.getInstruction(ABCConstants.OP_nop)); + break; + } + } + } + + if ( safeToRemove ) + { + // Only remove the Block if it contains executable and non-NOP instructions. + for ( int j = 0; j < b.size(); j++ ) + { + Instruction insn = b.get(j); + if ( insn.isExecutable() && insn.getOpcode() != ABCConstants.OP_nop ) + { + // Only emit a diagnostic if b is the first unreachable block + // encountered in this sequence. + if ( lastBlockWasReachable ) + this.diagnostics.unreachableBlock(this.mbi, this.mbi.getCfg(), b); + cfg.removeUnreachableBlock(b); + break; + } + } + } + } + + if ( previousBlockCount == blocks.size() ) + blockIdx++; + + // Remember the state of the last-visited block. + lastBlockWasReachable = isReachable; + } + + super.visitEnd(); + } +}
