You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@flex.apache.org by cd...@apache.org on 2014/07/22 15:36:07 UTC
[41/51] [partial] - Migrated the directory structure to a more Maven
style structure. - Started migrating the Parser from Antlr2+3 and JFlex to
Antlr4.
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();
+ }
+}