public class Log {
	
    public static Log logger;
    
    public static Log getLogger() {
        return logger;
    }
    
    private int state = INFO;
    
    /**
     * @return Returns the state.
     */
    public int getState() {
        return state;
    }

    /**
     * @param state The state to set.
     */
    public void setState(int state) {
        this.state = state;
    }

    public static final int DEBUG = 3;
    public static final int INFO = 2;
    public static final int WARN = 1;
    public static final int ERROR = 0;
    
    public void debug(CharSequence arg0, Throwable arg1) {
        if (isDebugEnabled()) {
            System.out.println("[DEBUG] " + arg0);
            arg1.printStackTrace();
        }
    }

    public void debug(CharSequence arg0) {
        if (isDebugEnabled()) {
            System.out.println("[DEBUG] " + arg0);
        }
    }

    public void debug(Throwable arg0) {
        if (isDebugEnabled()) {
            arg0.printStackTrace();
        }
    }

    public void error(CharSequence arg0, Throwable arg1) {
        if (isErrorEnabled()) {
            System.out.println("[ERROR] " + arg0);
            arg1.printStackTrace();
        }
    }

    public void error(CharSequence arg0) {
        if (isErrorEnabled()) {
            System.out.println("[ERROR] " + arg0);
        }
    }

    public void error(Throwable arg0) {
        if (isErrorEnabled()) {
            arg0.printStackTrace();
        }
    }

    public void info(CharSequence arg0, Throwable arg1) {
        if (isInfoEnabled()) {
            System.out.println("[INFO] " + arg0);
            arg1.printStackTrace();
        }
    }

    public void info(CharSequence arg0) {
        if (isInfoEnabled()) {
            System.out.println("[INFO] " + arg0);
        }
    }

    public void info(Throwable arg0) {
        if (isInfoEnabled()) {
            arg0.printStackTrace();
        }
    }

    public boolean isDebugEnabled() {
        return state >= DEBUG;
    }

    public boolean isErrorEnabled() {
        return state >= ERROR;
    }

    public boolean isInfoEnabled() {
        return state >= INFO;
    }

    public boolean isWarnEnabled() {
        return state >= WARN;
    }

    public void warn(CharSequence arg0, Throwable arg1) {
        if (isWarnEnabled()) {
            System.out.println("[WARNING] " + arg0);
            arg1.printStackTrace();
        }
    }

    public void warn(CharSequence arg0) {
        if (isWarnEnabled()) {
            System.out.println("[WARNING] " + arg0);
        }
    }

    public void warn(Throwable arg0) {
        if (isWarnEnabled()) {
            arg0.printStackTrace();
        }
    }
    
} public class Optimizer {
    
    private MethodDeclaration methodDecl;
    private List tempDecls;
    
    public Optimizer(MethodDeclaration theMethodDecl, List theTempDecls) {
        methodDecl = theMethodDecl;
        tempDecls = theTempDecls;
    }
    
    public static Expression negate(Expression expr) {
        PrefixExpression pe = new PrefixExpression();
        pe.setOperator(PrefixExpression.NOT);
        pe.setOperand(expr);
        return pe;
    }
    
    /**
     * Simplifies the (possibly negated) expression.
     */
    public static Expression simplifyBooleanExpression(Expression expr, boolean negate) {
        if (expr instanceof PrefixExpression) {
            PrefixExpression pe = (PrefixExpression) expr;
            if (pe.getOperator() != PrefixExpression.NOT) return expr;
            return simplifyBooleanExpression((Expression) pe.getOperand(), !negate);
        }
        
        if (expr instanceof InfixExpression && expr.getTypeBinding() == Type.BOOLEAN) {
            InfixExpression in = (InfixExpression) expr;
            InfixExpression.Operator op = in.getOperator();
            if (negate) {
                op = op.getComplement();
                if (op != InfixExpression.Operator.CONDITIONAL_AND && op != InfixExpression.Operator.CONDITIONAL_OR)
                    negate = false;
            }
            InfixExpression out = new InfixExpression(op);
            out.widen(in);
            out.setOperands(simplifyBooleanExpression(in.getLeftOperand(), negate), simplifyBooleanExpression(in.getRightOperand(), negate));
            return out;
        }
        
        if (negate) {
            PrefixExpression pe = new PrefixExpression();
            pe.setOperator(PrefixExpression.NOT);
            pe.setOperand(expr);
            return pe;
        }
        
        return expr;
    }
    
    private boolean representSameAssignables(Assignable a, Assignable b) {
        if (!(a instanceof FieldAccess && b instanceof FieldAccess)) return false;
        FieldAccess faa = (FieldAccess) a;
        FieldAccess fab = (FieldAccess) b;
        if (!faa.getName().equals(fab.getName())) return false;
        if (faa.getExpression() instanceof VariableBinding && fab.getExpression() instanceof VariableBinding ) {
            VariableBinding vba = (VariableBinding) faa.getExpression();
            VariableBinding vbb = (VariableBinding) fab.getExpression();
            return vba.getVariableDeclaration() == vbb.getVariableDeclaration();
        }
        return false;
    }
    
    /**
     * Reduces occurences of
     *      temp = x;
     *      y = temp;
     * to
     *      y = x;
     */
//    private ASTNode bar1(ASTNode child, ASTNode next) {
//        if (child instanceof Assignment && next instanceof Assignment) {
//            Assignment a1 = (Assignment) child;
//            Assignment a2 = (Assignment) next;
//            if (a1.getLeftHandSide().equals(a2.getRightHandSide())) {
//                a2.setRightHandSide(a1.getRightHandSide());
//                child.getParentBlock().removeChild(child);
//                return next;
//            }
//        }
//        return child;
//    }
    
    private VariableBinding fetchVariableBinding(Expression expr, VariableDeclaration decl) {
        ASTNode child = expr.getFirstChild();
        while (child != null) {
            if (child instanceof VariableBinding && ((VariableBinding) child).getVariableDeclaration() == decl)
                return (VariableBinding) child;
            VariableBinding vb = fetchVariableBinding((Expression) child, decl);
            if (vb != null) return vb;
            child = child.getNextSibling();
        }
        return null;
    }
    
    /**
     * If the specified expression corresponds to
     *      xy + 1 or xy - (-1),
     * returns the INCREMENT operator. If the specified expression corresponds to
     *      xy - 1 or xy + (-1),
     * returns the DECREMENT operator. Otherwise, null is returned.
     * @param expr
     * @return
     */
    private PStarExpression.Operator getOp(InfixExpression expr) {
        NumberLiteral nl;
        if (expr.getRightOperand() instanceof NumberLiteral) {
            nl = (NumberLiteral) expr.getRightOperand();
        } else return null;
        
        PStarExpression.Operator op;
        if (expr.getOperator() == InfixExpression.Operator.PLUS) {
            op = PStarExpression.INCREMENT;
        } else if (expr.getOperator() == InfixExpression.Operator.MINUS) {
            op = PStarExpression.DECREMENT;
        }  else {
            return null;
        }
        
        if (NumberLiteral.isOne(nl)) {
            // We are ok.
        } else if (NumberLiteral.isMinusOne(nl)) {
            op = op.complement();
        } else {
            return null;
        }
        return op;
    }    
    
    /**
     * Reduces
     *      vb = x.y;      (1)
     *      x.y = vb + 1;  (2)
     *      ...
     *      expr(vb);
     * to incremental form
     *       expr(x.y++);
     * Likewise decrement.
     */
    private boolean reduceXCrement(VariableDeclaration decl) {
        Assignment a1 = null;
        Assignment a2 = null;
        VariableBinding vb1 = null;
        VariableBinding vb2 = null;
        
        Assignable fa1 = null;
        Assignable fa2 = null;
        
        InfixExpression sum = null;
        
        
        Iterator iter = decl.vbs.iterator();

        while (iter.hasNext()) {
            VariableBinding vb = (VariableBinding) iter.next();
            
            if (vb.getParentNode() instanceof Assignment) {
                Assignment a = (Assignment) vb.getParentNode();
                if (a.getLeftHandSide() == vb && a.getRightHandSide() instanceof Assignable) {
                    vb1 = vb;
                    a1 = a;
                    fa1 = (Assignable) a.getRightHandSide();
                    continue;
                }
            }

            if (vb.getParentNode() instanceof InfixExpression) {
                InfixExpression infix = (InfixExpression) vb.getParentNode();
                if (infix.getParentNode() instanceof Assignment) {
                    Assignment a = (Assignment) infix.getParentNode();
                    if (a.getLeftHandSide() instanceof Assignable) {
                        vb2 = vb;
                        fa2 = (Assignable) a.getLeftHandSide();
                        a2 = a;
                        sum = infix;
                        continue;
                    }
                }
            }
        }

        if (a1 == null || a2 == null) return false;
        if (!fa1.isSame(fa2)) return false;

        PStarExpression.Operator operator = getOp(sum);
        if (operator == null) return false;
        
        PStarExpression p = new PostfixExpression();
        p.setOperand((Expression) fa1);
        p.setOperator(operator);

        decl.vbs.remove(vb1);
        decl.vbs.remove(vb2);
        VariableBinding vb = decl.vbs.get(0);
        vb.getParentBlock().replaceChild(p, vb);

        Block b = a1.getParentBlock();
        b.removeChild(a1);
        b.removeChild(a2);
        return true;
    }
    
    /**
     * Reduces
     *      vb = x.y op z;  (3)
     *      x.y = vb;       (4)
     *      ...
     *      expr(vb);
     * to incremental form
     *      expr(x.y op= z) or expr(++x.y);
     * Likewise decrement.
     */
    private boolean reduceYCrement(VariableDeclaration decl) {
        Assignment a1 = null;
        Assignment a2 = null;
        VariableBinding vb1 = null;
        VariableBinding vb2 = null;
        
        Assignable fa1 = null;
        Assignable fa2 = null;
        
        InfixExpression infixExpr = null;
        
        Iterator iter = decl.vbs.iterator();

        while (iter.hasNext()) {
            VariableBinding vb = (VariableBinding) iter.next();
            
            if (!(vb.getParentNode() instanceof Assignment)) continue;
        
            Assignment a = (Assignment) vb.getParentNode();
            if (a.getRightHandSide() == vb && a.getLeftHandSide() instanceof Assignable) {
                vb2 = vb;
                a2 = a;
                fa2 = (Assignable) a.getLeftHandSide();
                continue;
            }
            
            if (a.getLeftHandSide() == vb && a.getRightHandSide() instanceof InfixExpression) {
                InfixExpression infix = (InfixExpression) a.getRightHandSide();
                if (!(infix.getLeftOperand() instanceof Assignable)) continue;
                vb1 = vb;
                a1 = a;
                fa1 = (Assignable) infix.getLeftOperand();
                infixExpr = infix;
                continue;
            }
        }

        if (a1 == null || a2 == null) return false;
        if (!fa1.isSame(fa2)) return false;

        decl.vbs.remove(vb1);
        decl.vbs.remove(vb2);
        VariableBinding vb = decl.vbs.get(0);
        Expression replacement = null;
        
        PStarExpression.Operator operator = getOp(infixExpr);
        if (operator != null) {
            PrefixExpression   p = new PrefixExpression();
            p.setOperand((Expression) fa1);
            p.setOperator(operator);
            replacement = p;
        } else {
            InfixExpression.Operator op = infixExpr.getOperator();
            Assignment.Operator opp = Assignment.Operator.lookup(op.toString() + '=');
            Assignment a = new Assignment(opp);
            a.setLeftHandSide((Expression) fa2);
            a.setRightHandSide(infixExpr.getRightOperand());
            replacement = a;
        }
        
        vb.getParentBlock().replaceChild(replacement, vb);
        
        Block b = a1.getParentBlock();
        b.removeChild(a1);
        b.removeChild(a2);
        return true;
    }
    
    public void optimize() {
        if (false) return;
        // Review this code. For example j2js.fa(obj, name)++ is illegal!
        
        Iterator iter = tempDecls.iterator();
        while (iter.hasNext()) {
            VariableDeclaration decl = (VariableDeclaration) iter.next();
            int count = decl.vbs.size();
            if (count == 3) {
                if (reduceXCrement(decl)) {
                    iter.remove();
                    methodDecl.removeLocalVariable(decl.getName());
                } else if (reduceYCrement(decl)) {
                    iter.remove();
                    methodDecl.removeLocalVariable(decl.getName());
                }
            }
        }
    }

} public class ConditionalEdge extends Edge {
    
    private BooleanExpression expression;
    private boolean negate = false;
    
    ConditionalEdge(Graph graph, Node theSource, Node theTarget) {
        super(graph, theSource, theTarget);
    }
    
    public BooleanExpression getBooleanExpression() {
        return expression;
    }
    
    public void setBooleanExpression(BooleanExpression expr) {
        expression = expr;
    }

    public boolean isNegate() {
        return negate;
    }

    public void setNegate(boolean theNegate) {
        negate = theNegate;
    }
} public class ControlFlowGraph extends Graph {

    // Ordering is only used by method getNodeAt().
    private SortedMap<Integer, Node> nodesByPc = new TreeMap<Integer, Node>();
    
    // The single entry point of control.
    private Node sourceNode;
    
    private List tryStatements;
    
    public ControlFlowGraph(List theTryStatements) {
        tryStatements = theTryStatements;
    }

    /**
     * Returns the try statement which contains the specified node.
     */
    private TryStatement selectTryStatement(Node node) {
        int pc = node.getInitialPc();
        for (int i=0; i<tryStatements.size(); i++) {
            TryStatement tryStmt = (TryStatement) tryStatements.get(i);
            Block block = tryStmt.getTryBlock();
            if (pc >= block.getBeginIndex() && pc <= block.getEndIndex()) return tryStmt;
        }
        return null;
    }
    

    public Node createNode(int pc) {
        return createNode(pc, Node.class);
    }
    
    public Node getOrCreateNode(int pc) {
        Node node = getNode(pc);
        if (node == null) {
            node = createNode(pc, Node.class);
        }
        return node;
    }

    public Node createNode(int pc, Class nodeClass) {
        if (pc < 0) throw new RuntimeException("Program counter may not be negative");
        
        Node node = super.createNode(nodeClass);
        node.setInitialPc(pc);
        if (nodesByPc.put(node.getInitialPc(), node) != null) {
            throw new RuntimeException("Node already exists: " + node);
        }
        
        if (pc == 0) sourceNode = node;

        return node;
    }
    
    /**
     * Returns the largest (w.r. to its initial pc) node closest to the specified pc.
     */
    public Node getNodeAt(int pc) {
        int minPcDelta = Integer.MAX_VALUE;
        Node node = null;
        for (Node n : getNodes()) {
            if (n.getInitialPc() <= pc && pc-n.getInitialPc() < minPcDelta) {
                minPcDelta = pc-n.getInitialPc();
                node = n;
                if (minPcDelta == 0) return node;
            }
        }
        
        if (node == null) {
            throw new RuntimeException("No node at pc " + pc);
        }
        
        return node;
    }
    
    /**
     * Splits a node at the given pc value into two nodes nodeA and nodeB.
     * nodeB will start at pc and will have the outbound edges of the original node, and an
     * extra edge is added from nodeA to nodeB.
     */
    public Node split(Node node, int pc) {
        if (node.block.getBeginIndex() >= pc) throw new RuntimeException("Block must contain program counter");
        
        Node nodeB = createNode(pc);
        
        // Reroot all outbound edges at nodeB.
        for (Edge edge : new ArrayList<Edge>(node.getOutEdges())) {
            edge.reroot(nodeB);
        }

        addEdge(node, nodeB);
        
        // Transfer code starting at pc to nodeB.
        ASTNode astNode = node.block.getFirstChild();
        while (astNode != null) {
            if (astNode.getBeginIndex() >= pc) {
                node.setCurrentPc(astNode.getBeginIndex()-1);
                nodeB.block.appendChildren(astNode, node.block.getLastChild());
                break;
            }
            astNode = astNode.getNextSibling();
        }

        // Transfer stack to nodeB.
        nodeB.stack = node.stack;
        node.stack = new ASTNodeStack();
        
        return nodeB;
    }
    
    public Node[] getOrSplitNodeAt(Node currentNode, int pc) {
        Node targetNode = getNodeAt(pc);
        if (targetNode.getInitialPc() != pc) {
            // No node starts at target pc. We have to split the node.
            Node nodeB = split(targetNode, pc);
            if (targetNode == currentNode) {
                currentNode = nodeB;
            }
            targetNode = nodeB;
        }
        return new Node[]{currentNode, targetNode};
    }
    
    /**
     * Redirect all incoming edges for try bodys to its try header.
     */
    private void processTrys() { 
        for (int i=0; i<tryStatements.size(); i++) {
            TryStatement stmt = (TryStatement) tryStatements.get(i);
            TryHeaderNode header = stmt.header;
            Node tryNode = header.getTryBody();
            
            if (tryNode == sourceNode) sourceNode = header;

            for (Edge edge : new ArrayList<Edge>(tryNode.getInEdges())) {
                int pc = edge.source.getInitialPc();
                if (pc >= stmt.getBeginIndex() && pc <= stmt.getEndIndex()) continue;
                if (edge.source == header) continue;
                edge.redirect(header);
            }
        }
    }
    
    /**
     * Reroots all local edges exiting a try body at the corresponding try header.
     */
    private void processTrys2() {
        for (Node node: nodesByPc.values()) {
            TryStatement sourceTry = selectTryStatement(node);
            if (sourceTry == null) continue;
        
            for (Edge edge : node.getOutEdges()) {
                if (edge.target.getInEdges().size() != 1) {
                    continue;
                }
                TryStatement targetTry = selectTryStatement(edge.target);
                if (targetTry == null || targetTry != sourceTry) {
                    edge.reroot(sourceTry.header);
                }
            }
        }
    }
    
    /**
     * Reroot the fall through successor directly at the try header.
     */
    private void processTrys1() {     
        for (int i=0; i<tryStatements.size(); i++) {
            TryStatement stmt = (TryStatement) tryStatements.get(i);
            TryHeaderNode header = stmt.header;
            Node finallyNode = header.getFinallyNode();
            if (finallyNode == null) continue;
            
            Iterator iter = finallyNode.jsrCallers.iterator();
            while (iter.hasNext()) {
                Node node = (Node) iter.next();
                // TODO: Be independant of pc!
                if (node.getInitialPc() > finallyNode.getInitialPc()) {
                    removeInEdges(node);
                    addEdge(header, node);
                    node.setDomParent(header);
                }
            }    
        }
    }
    
    public Node getSource() {
        return sourceNode;
    }
    
    public Node getNode(int pc) {
        return nodesByPc.get(pc);
    }
    
    /**
     * Finds the set of all successors of the specified predecessor which are not dominated by it.
     * Each node in this set is then marked as a global target of the predecessor.
     * If the predecessor is a branch, then a newly created node will function as the referer. 
     */
    private void markGlobalTargets(Node predecessor) {
        for (Edge edge : predecessor.getOutEdges()) {
            Node target = edge.target;
            if (target.getDomParent() == predecessor)
                continue;

            if (predecessor.isBranch()) {
                Node node = createNode(Node.class);
                edge.redirect(node);
                node.setDomParent(predecessor);
                edge = addEdge(node, target);
            }
        }
    }
    
    /**
     * For each node in tree, mark global targets.
     */
    void visitToMark(Node node) {
        // Be concurrent safe.
        for (Node child : new ArrayList<Node>(node.getDomChildren())) {
            visitToMark(child);
        }

        markGlobalTargets(node);
    }
    
    /**
     * Recursively (depth first) traverses the dominator tree rooted at the specified node and post-processes
     * all possible reductions.
     */
    void visit(Node node) {

        // Be concurrent safe.
        for (Node child : new ArrayList<Node>(node.getDomChildren())) {
            visit(child);
        }
    
        do {
            Transformation t = Transformation.select(this, node);
            if (t == null) break;
            node = t.apply();
            dump("After transformation");
        } while (true);
        
        if (node.getDomChildren().size() > 0) {
            throw new RuntimeException("Could not reduce graph at " + node);
        }
    }
    
    public void replaceNode(Node node, Node newNode) {
        
        super.replaceNode(node, newNode);
        
        if (newNode != null) {
            nodesByPc.put(node.getInitialPc(), newNode);
        } else {
            nodesByPc.remove(node.getInitialPc());
        }

        if (node == sourceNode) {
            if (newNode == null) {
                throw new RuntimeException("Cannot remove source node " + sourceNode);
            }
            sourceNode = newNode;
        }
    }
    
    public Block reduce() {  
        processTrys();
        processTrys2();

        dump("Before Shortcuts");
        processShortcuts();
        
        DominatorTree builder = new DominatorTree(this);
        builder.build();
        
        processTrys1();
        
        visitToMark(getSource());
        dump("Begin reduce");
        
        visit(getSource());

        if (size() != 1) {
            throw new RuntimeException("Could not reduce graph");
        }

        Block block = new Block();

        rollOut(getSource(), block);
        
        return block;
    }
    
    /**
     * Performs an OR or AND shortcut on two branches A and B by replacing them with new node A&B or A|B.
     */
     boolean performAndOrShortcut(Node a, Node b) {
         if (b.getInEdges().size() != 1) return false;
         if (b.block.getChildCount() > 0) {
             // Node b is not a mere conditional.
             return false;
         }

         
         ConditionalEdge aToC;
         ConditionalEdge bToC;
         boolean isOR = true;
         
         while(true) {
             aToC = a.getConditionalEdge(isOR);
             bToC = b.getConditionalEdge(isOR);
             if (bToC.target == aToC.target) break;
             if (!isOR) return false;
             isOR = false;
         }
         
         if (aToC.target.getInEdges().size() != 2) return false;

         ConditionalEdge bToD = b.getConditionalEdge(!isOR);
         ConditionalEdge aToB = a.getConditionalEdge(!isOR);
         
         aToB.redirect(bToD.target);
         removeEdge(bToC);
         removeEdge(bToD);
         removeNode(b);
         
         InfixExpression infix = new InfixExpression(
                 isOR?InfixExpression.Operator.CONDITIONAL_OR:InfixExpression.Operator.CONDITIONAL_AND);
         // Note that the order aToC, then bToC is important.
         infix.setOperands(
                 aToC.getBooleanExpression().getExpression(), 
                 bToC.getBooleanExpression().getExpression());
         
         BooleanExpression be = new BooleanExpression(infix);
         aToC.setBooleanExpression(be);
         aToB.setBooleanExpression(be);
         
         logger.debug("Created shortcut and removed " + b);
         
         return true;
     }
     
     public void processShortcuts() {
         Collection<Node> branches = new HashSet<Node>();
         for (Node node : getNodes()) {
             if (node.isBranch()) branches.add(node);
         }
         
         L: while (true) {
             Iterator<Node> iter = branches.iterator();
             while (iter.hasNext()) {
                 Node branch = iter.next();
                 for (Node node: branch.succs()) {
                     if (node.isBranch() && performAndOrShortcut(branch, node)) {
                         branches.remove(node);
                         continue L;
                     }
                 }
             }
             break L;
         }
         
     }
} public class Edge {
    
    private Graph graph;
    public Node source;
    public Node target;
    public EdgeType type;
    private Node orgSource;
    
    Edge(Graph theGraph, Node theSource, Node theTarget) {
        graph = theGraph;
        source = theSource;
        target = theTarget;
    }
    
    public boolean equals(Object other) {
        if (other == null || !(other instanceof Edge)) return false;
        Edge otherEdge = (Edge) other;
        return source.getId().equals(otherEdge.source.getId()) && target.getId().equals(otherEdge.target.getId());
    }
    
    /**
     * Replace the target of this edge.
     */
    public void reroot(Node newSource) {
        source.outEdges.remove(this);
        newSource.outEdges.add(this);
        source = newSource;
    }
    
    /**
     * Replace the target of this edge.
     */
    public void redirect(Node newTarget) {
        target.inEdges.remove(this);
        newTarget.inEdges.add(this);
        target = newTarget;
    }

    /**
     * Returns true if this edge is a backward (i.e. loop) edge.
     */
    public boolean isBackEdge() {
        return target.isDomAncestor(source);
    }
    
    public boolean isGlobal() {
        return orgSource != null;
    }
    
    public String toString() {
        String s = getClass().getName();
        // Extract unqualified class name.
        s = s.substring(s.lastIndexOf('.')+1);
        return s + " " + source.getId() + " -> " + target.getId();
    }

    public Node getOrgSource() {
        if (orgSource == null) {
            return source;
        }
        return orgSource;
    }

    public void setOrgSource(Node theOrgSource) {
        orgSource = theOrgSource;
    }

   
} public abstract class Graph {

    private Map<String, Node> nodes = new HashMap<String, Node>();
    
    int nodeIdSequence = 0;
    
    Log logger = Log.getLogger();
    
    public Graph() {
    }

    public Node getNodeById(String id) {
        return nodes.get(id);
    }
    
    public Node createNode(Class nodeClass) {
        return createNode(nodeClass, Integer.toString(nodeIdSequence++, 26));
    }
    
    public Node createNode(Class nodeClass, String id) {
        Node node;
        try {
            Constructor constructor = nodeClass.getConstructor(new Class[]{Graph.class});
            node = (Node) constructor.newInstance(new Object[] {this});
        } catch (InstantiationException e) {
            throw new RuntimeException(e);
        } catch (IllegalAccessException e) {
            throw new RuntimeException(e);
        } catch (NoSuchMethodException e) {
            throw new RuntimeException(e);
        } catch (InvocationTargetException e) {
            throw new RuntimeException(e);
        }
        node.id = id;
        nodes.put(id, node);
        return node;
    }
    
    /**
     * Returns true if node set A is contained in node set B.
     */
    public boolean isContained(Set nodesA, Node[] nodesB) {
        Set<Node> foo = new HashSet<Node>(Arrays.asList(nodesB));
        return foo.containsAll(nodesA);
    }
    
    /**
     * Redirects all inbound edges of a node to another node.
     */
    public void replaceAsTarget(Node oldTarget, Node newTarget) {
        for (Edge edge : new ArrayList<Edge>(oldTarget.getInEdges())) {
            edge.redirect(newTarget);
        }
    }

    public Edge removeEdge(Node source, Node target) {
        Edge edge = getEdge(source, target);
        return removeEdge(edge);
    }
    
    public Edge removeEdge(Edge edge) {
        edge.source.getOutEdges().remove(edge);
        edge.target.getInEdges().remove(edge);
        return edge;
    } 
    
//    public void replaceNodes(Node header, List nodes, Node newNode) {
//        replaceNodes(header, (Node[]) nodes.toArray(new Node[nodes.size()]), newNode);
//    }
    
    public String getEdgeId(Node source, Node target) {
        return source.getId() + "->" + target.getId();
    }
    
    public void addIfElseEdge(Node source, Node ifTarget, Node elseTarget, BooleanExpression be) {
        ConditionalEdge ifEdge = (ConditionalEdge) addEdge(source, ifTarget, ConditionalEdge.class);
        ifEdge.setBooleanExpression(be);
        ConditionalEdge elseEdge = (ConditionalEdge) addEdge(source, elseTarget, ConditionalEdge.class);
        elseEdge.setBooleanExpression(be);
        elseEdge.setNegate(true);
    }
    
    public Edge addEdge(Node source, Node target) {
        return addEdge(source, target, Edge.class);
    }
    
    public Edge addEdge(Node source, Node target, Class clazz) {
        Edge edge = getEdge(source, target);
        if (edge != null) {
            // TODO: Why not allow adding multiple edges? This is possible
            // anyway through reroot or redirect!
            throw new RuntimeException("Edge already exists");
        }
        if (clazz.equals(Edge.class)) {
            edge = new Edge(this, source, target);
        } else if (clazz.equals(SwitchEdge.class)) {
            edge = new SwitchEdge(this, source, target);
        } else if (clazz.equals(ConditionalEdge.class)) {
            edge = new ConditionalEdge(this, source, target);
        } else {
            throw new RuntimeException("Illegal edge class " + clazz);
        }
        source.addEdge(edge);
        if (source != target) {
            target.addEdge(edge);
        }
        return edge;
    }
    
    public Edge getEdge(Node source, Node target) {
        for (Edge edge : source.getOutEdges()) {
            if (edge.target == target) return edge;
        }
        return null;
    }
    	
    public void removeNode(Node node) {
        replaceNode(node, null);
    }
    
    public Set<Edge> removeOutEdges(Node node) {
        Set<Edge> outEdges = new HashSet<Edge>(node.outEdges);
        Iterator iter = outEdges.iterator();
        while (iter.hasNext()) {
            Edge edge = (Edge) iter.next();
            removeEdge(edge);
        }
        
        return outEdges;
    }
    
    /**
     * Removes all in-edges to the specified node.
     *
     * @return the set of removed in-edges
     */
    public Set removeInEdges(Node node) {
        Set<Edge> inEdges = new HashSet<Edge>(node.inEdges);
        Iterator<Edge> iter = inEdges.iterator();
        while (iter.hasNext()) {
            Edge edge = iter.next();
            removeEdge(edge);
        }
        
        return inEdges;
    }
    
    public Set removeSelfEdges(Node node) {
        Set<Edge> selfEdges = new HashSet<Edge>();
        
        for (Edge edge: new HashSet<Edge>(node.outEdges)) {
            if (edge.target != node) continue;
            removeEdge(edge);
            selfEdges.add(edge);
        }
        
        return selfEdges;
    }
    
    public void rerootGlobalOutEdges(Node node, Node newSource) {
        Edge[] edges  = node.getOutEdgesArray();
        for (int i=0; i<edges.length; i++) {
            Edge edge = edges[i];
            if (edge.isGlobal()) {
                edge.reroot(newSource);
            }
        }
    }
    
    public void rerootOutEdges(Node node, Node newSource, boolean localToGlobal) {
        Edge[] edges  = node.getOutEdgesArray();
        for (int i=0; i<edges.length; i++) {
            Edge edge = edges[i];
            edge.reroot(newSource);
            if (localToGlobal && !edge.isGlobal()) {
                edge.setOrgSource(node);
            }
        }
    }
    
    public void replaceNode(Node oldNode, Node newNode) {
        nodes.remove(oldNode.getId());
        
        if (newNode != null) {
            // Redirect all in-edges for oldNode to newNode.
            replaceAsTarget(oldNode, newNode);
            
            // Reroot all out-edges from oldNode at newNode, making local edges global.
            rerootOutEdges(oldNode, newNode, true);
            
            newNode.setDomParent(oldNode.getDomParent());
            for (Node child : new ArrayList<Node>(oldNode.getDomChildren())) {
                child.setDomParent(newNode);
            }
        }
        
        if (oldNode.inEdges.size() > 0 || oldNode.outEdges.size() > 0)
            throw new RuntimeException("Cannot replace node with edges");

        oldNode.setDomParent(null);
    }
	
    public Collection<Node> getNodes() {
        return nodes.values();
    }
    
	public int size() {
		return getNodes().size();
	}

    public Block reduceDumb() {
        Block block = new Block();
        
        for (Node node : getNodes()) {
            block.appendChild(node.block);
            
            if (node.isBranch()) {
                IfStatement ifStmt = new IfStatement();
                ConditionalEdge cEdge = node.getConditionalEdge(true);
                ifStmt.setExpression(cEdge.getBooleanExpression().getExpression());
                ifStmt.setIfBlock(new Block());
                Block targetBlock = cEdge.target.block;
                ifStmt.getIfBlock().appendChild(new BreakStatement(targetBlock));
                ifStmt.setElseBlock(new Block());
                targetBlock = node.getConditionalEdge(false).target.block;
                ifStmt.getElseBlock().appendChild(new BreakStatement(targetBlock));
                block.appendChild(ifStmt);
            } else {
                for (Edge e : node.getOutEdges()) {
                    BreakStatement bStmt = new BreakStatement(e.target.block);
                    node.block.appendChild(bStmt);
                }
            }
        }
        return block;
    }

    boolean isTarget(Node n, Set edgeSet) {
        Iterator iter = edgeSet.iterator();
        while (iter.hasNext()) {
            Edge e = (Edge) iter.next();
            if (n == e.target) return true;
        }
        return false;
    }
    
    public void rollOut(Node node, Block targetBlock) {
        if (node.trans != null) {
            node.trans.rollOut(targetBlock);
        } else {
            targetBlock.appendChildren(node.block);
        }
    }
    
    public void dump(String msg) {
        StringBuffer sb = new StringBuffer();
        sb.append(msg + " ...\n");
        for (Node node : getNodes()) {
            sb.append(node.describe() + "\n");
            //dump(node.block, "Block");
        }
        sb.append("... " + msg);
        logger.debug(sb.toString());
    }
} public class Node {
    
    public class Reference {
        public Node source;
        public boolean isBackward = false;
    }
    
    public static int NON_HEADER = 0;
    public static int REDUCIBLE = 1;
    public static int IRREDUCIBLE = 2;
    
    String id;
    
    Set<Edge> inEdges = new LinkedHashSet<Edge>();
    Set<Edge> outEdges = new LinkedHashSet<Edge>();
    Graph graph;
    private int currentPc = -1;
    private int initialPc = -1;
    public ASTNodeStack stack = new ASTNodeStack();
    public Block block = new Block();
    public boolean closed = false;
    
    protected int preOrderIndex = -1;
    
    private Node domParent;                         // Block that (immediately) dominates this Block
    private Set<Node> domChildren = new HashSet<Node>();        // Blocks that this Block dominates
    
    IfStatement ifStmt;
    public Expression switchExpression;
    
    public Transformation trans;
    public Collection<Node> jsrCallers = new HashSet<Node>();
    
    public boolean isSwitchHeader = false;
       
    public Node(Graph theGraph, int pc) {
        this(theGraph);
        setInitialPc(pc);
    }
    
    public Node(Graph theGraph) {
        graph = theGraph;
    }
     
    public int getComplexity() {
        Node node = this;
        int complexity = 0;
        while (node.trans != null) {
            complexity++;
            node = node.trans.header;
        }
        return complexity;
    }
    
    /**
     * @return Returns the pc.
     */
    public int getCurrentPc() {
        return currentPc;
    }
    /**
     * @param pc The pc to set.
     */
    public void setCurrentPc(int pc) {
        currentPc = pc;
    }
    
    public void close() {
        closed = true;
    }
    
    public void addEdge(Edge e) {
        if (e.source == this) {
            if (!outEdges.add(e)) {
                throw new RuntimeException("\n" + this + "\nalready bound to " + e);
            }
        }
        
        if (e.target == this) {
            if (!inEdges.add(e)) {
                throw new RuntimeException("" + this + " already bound to " + e);
            }
        }
    }
    
    public String toString() {
        String s = getClass().getName();
        // Same as getClass().getSimpleName() in JDK 5.0.
        s = s.replaceFirst(".*\\.", "");

        s += " " + id + "[" + initialPc + ", " + currentPc + "]";
        //if (preOrderIndex >= 0) s += " preIndex=" + preOrderIndex;
        if (domParent != null) s += " dominated by " + domParent.id;
        if (isLoopHeader()) s += " LH";
        return s;
    }
    
    public String describe() {
        String s = toString();
        Iterator iter = outEdges.iterator();
        while (iter.hasNext()) {
            Edge e = (Edge) iter.next();
            s += "\n\t" + e;
        }
        return s;
    }
    
    
    /**
     * @return Returns the inEdges.
     */
    public Set<Edge> getInEdges() {
        return inEdges;
    }
    
    public Edge getSelfEdge() {
        Iterator iterator = inEdges.iterator();
        while (iterator.hasNext()) {
            Edge edge = (Edge) iterator.next();
            if (edge.source == this) return edge;
        }
        return null;
    }
    
//    public Set getGlobalInEdges() {
//        HashSet set = new HashSet();
//        Iterator iterator = inEdges.iterator();
//        while (iterator.hasNext()) {
//            Edge edge = (Edge) iterator.next();
//            if (edge.global) set.add(edge);
//        }
//        return set;
//    }
    
//    public Set getForewardOutEdges() {
//        HashSet set = new HashSet();
//        Iterator iterator = outEdges.iterator();
//        while (iterator.hasNext()) {
//            Edge edge = (Edge) iterator.next();
//            if (!edge.isBackEdge()) set.add(edge);
//        }
//        return set;
//    }
    
    /**
     * @return Returns the outEdges.
     */
    public Set<Edge> getOutEdges() {
        return outEdges;
    }
    
    public Edge[] getOutEdgesArray() {
        return outEdges.toArray(new Edge[outEdges.size()]);
    }
    
    public Edge[] getInEdgesArray() {
        return inEdges.toArray(new Edge[inEdges.size()]);
    }
    
    public int getPreOrderIndex() {
        return preOrderIndex;
    }

    public void setPreOrderIndex(int thePreOrderIndex) {
        preOrderIndex = thePreOrderIndex;
    }
    
    public Set<Node> succs() {
        Set<Node> list = new LinkedHashSet<Node>();
        Edge[] edges = getOutEdgesArray();
        for (int i=edges.length-1; i>=0; i--) {
            list.add(edges[i].target);
        }
        return list;
    }
    
    public Set<Node> preds() {
        Set<Node> list = new LinkedHashSet<Node>();
        Iterator iter = inEdges.iterator();
        while (iter.hasNext()) {
            Edge e = (Edge) iter.next();
            list.add(e.source);
        }
        return list;
    }
    
    public Node getPred() {
        int count = inEdges.size();
        if (count != 1) throw new RuntimeException("Requested unique predecessor, found " + count);
        return inEdges.iterator().next().source;
    }
    
    public Node getSucc() {
        return getOutEdge().target;
    }
    
    public Edge getLocalOutEdgeOrNull() {
        Edge outEdge = null;
        Iterator iter = outEdges.iterator();
        while (iter.hasNext()) {
            Edge edge = (Edge) iter.next();
            if (outEdge != null) new RuntimeException("Found multiple local out-edges");
            outEdge = edge;
        }
        return outEdge;
    }
    
    public Edge getOutEdge() {
        int count = outEdges.size();
        if (count != 1) throw new RuntimeException("Requested unique successor, found " + count);
        return outEdges.iterator().next();
    }

    /**
     * Return true if this node is equal to or dominates the specified node.
     */
    public boolean isDomAncestor(Node node) {
        do {
            if (node == null) return false;
            if (node == this) return true;
            node = node.getDomParent();
        } while (true);
    }
    
    public Set<Node> getDomChildren() {
        return domChildren;
    }
    
    public Node getDomChild() {
        if (domChildren.size() != 1) throw new RuntimeException("Node must have single child");
        return getDomChildren().iterator().next();
    }

    public Node getDomParent() {
        return domParent;
    }

    public void setDomParent(Node newDomParent) {
        // If this Block already had a dominator specified, remove
        // it from its dominator's children.
        if (domParent != null) {
            domParent.domChildren.remove(this);
        }

        domParent = newDomParent;

        // Add this Block to its new dominator's children.
        if (domParent != null) {
            domParent.domChildren.add(this);
        }
    }

    public boolean isBranch() {
        Edge[] edges = getOutEdgesArray();
        if (edges.length != 2) return false;
        if (edges[0] instanceof ConditionalEdge && edges[1] instanceof ConditionalEdge) return true;
        if ((edges[0] instanceof ConditionalEdge) || (edges[1] instanceof ConditionalEdge))
            throw new RuntimeException("Node must not have mixed edges");
        return false;
    }

    /**
     * Returns either the true or false edge.
     */
    public ConditionalEdge getConditionalEdge(boolean trueFalse) {
        if (!isBranch()) throw new RuntimeException("Node must be a branch");
        Iterator<Edge> iter = outEdges.iterator();
        Edge edge = iter.next();
        if (!trueFalse) edge = iter.next();
        return (ConditionalEdge) edge;
    }

    public String getId() {
        return id;
    }

    public int getInitialPc() {
        return initialPc;
    }

    public Graph getGraph() {
        return graph;
    }

    public void setInitialPc(int theInitialPc) {
        initialPc = theInitialPc;
        currentPc = theInitialPc;
    }

    public boolean isLoopHeader() {
        Iterator iter = inEdges.iterator();
        while (iter.hasNext()) {
            Edge edge = (Edge) iter.next();
            if (edge.isBackEdge()) return true;
        }
        return false;
    }
    
    public boolean hasSelfEdges() {
        Iterator iter = outEdges.iterator();
        while (iter.hasNext()) {
            Edge edge = (Edge) iter.next();
            if (edge.target == this) return true;
        }
        return false;
    }
    
//    public void replaceEdge(Edge oldEdge, Edge newEdge) {
//        source.outEdges.remove(this);
//        newSource.outEdges.add(this);
//        source = newSource;
//    }
} public class Block extends ASTNode {
    
	public static int TAG = 0;
	
    private String label;
    
    private ASTNode firstChild = null;
    private ASTNode lastChild = null;
    private int childCount = 0;
    
    public Block() {
    	super();
    }
    
    public Block(int theBeginIndex) {
        setBeginIndex(theBeginIndex);
     }
    
    public Block(int theBeginIndex, int theEndIndex) {
        this(theBeginIndex);
        setRange(theBeginIndex, theEndIndex);
    }
    
//    public Block getFooBlock() {
//        Block block = this;
//        while (block!=null) {
//            if (!block.getClass().equals(Block.class)) {
//                return block;
//            }
//            block = block.getParentBlock();
//        }
//        return this;
//    }
    
    public int getTargetPc() {
        if (lastChild instanceof Jump) {
            return ((Jump) lastChild).getTargetIndex();
        }
        return Integer.MAX_VALUE;
    }
    
    public int getTargetIndex() {
        return beginIndex;
    }

    public void setBeginIndex(int theBeginIndex) {
        super.setBeginIndex(theBeginIndex);
    }
    
    public void visit(AbstractVisitor visitor) {
	    visitor.visit(this);
    }

    public void appendChildren(ASTNode begin, ASTNode end) {
    	if (begin == null || end == null) {
        	throw new RuntimeException("Illegal null parameters");
        }
        if (begin.getParentBlock() != null)
            (begin.getParentBlock()).removeChildren(begin, end);

        if (firstChild == null) {
            setFirstChildInternal(begin);
        } else {
            ASTNode prev = getLastChild();
            prev.setNextSibling(begin);
            begin.setPreviousSibling(prev);
        }
        setLastChildInternal(end);

        ASTNode node = begin;
        while (node != null) {
            node.setParentNode(this);
            childCount++;
            if (node == end) break;
            node = node.getNextSibling();
        }    
    }
    
    /**
     * Appends all children of the specified block to this block.
     * @param sourceBlock
     */
    public void appendChildren(Block sourceBlock) {
        if (sourceBlock.getChildCount() > 0) {
            appendChildren(sourceBlock.getFirstChild(), sourceBlock.getLastChild());
        }
    }
    
    /**
     * Sets the specified node at the index. Returns the replaced node, or null if the index
     * was equal to the cild count.
     */
    public ASTNode setChildAt(int index, ASTNode newChild) {
        if (index == childCount) {
            appendChild(newChild);
            return null; 
        } else if (index < 0 || index > childCount) {
            throw new RuntimeException("Index " + index + " out of range [0, " + childCount + "]");
        }
        
        return replaceChild(newChild, getChildAt(index));
    }
    
    public ASTNode getChildAt(int index) {
        if (childCount == 0) {
            throw new RuntimeException("Requested child at index " + index + ", but block has no children");
        }
        if (index < 0 || index >= childCount) {
            throw new RuntimeException("Index " + index + " out of range [0, " + (childCount-1) + "]");
        }
        
        if (index == childCount-1) {
            return getLastChild();
        }
        
        ASTNode node = getFirstChild();
        int i = 0;
        while (i < index) {
            i++;
            node = node.getNextSibling();
        }
        
        return node;
    }
    
    public ASTNode appendChild(ASTNode newChild) {
    	Log.getLogger().debug("Appending " + newChild + " to " + this);
    	
    	unlink(newChild);
        
        if (firstChild == null) {
            newChild.setPreviousSibling(null);
            setFirstChildInternal(newChild);
        } else {
            ASTNode prev = getLastChild();
            prev.setNextSibling(newChild);
            newChild.setPreviousSibling(prev);
        }
        setLastChildInternal(newChild);
        newChild.setParentNode(this);
        childCount++;

    	return newChild;
    }
    
    public ASTNode replaceChild(ASTNode newChild, ASTNode oldChild) {
    	Log.getLogger().debug("Replacing " + oldChild + " by " + newChild + " in " + this);
        if (oldChild.getParentNode() != this) {
            throw new DOMException(DOMException.NOT_FOUND_ERR, "Node " + oldChild + " is not a child of " + this);
        }
        unlink(newChild);
        if (oldChild.getPreviousSibling() != null) {
            oldChild.getPreviousSibling().setNextSibling(newChild);
        }
        if (oldChild.getNextSibling() != null) {
            oldChild.getNextSibling().setPreviousSibling(newChild);
        }
        newChild.setPreviousSibling(oldChild.getPreviousSibling());
	    newChild.setNextSibling(oldChild.getNextSibling());
	    newChild.setParentNode(this);
	    if (getFirstChild() == oldChild) {
	        setFirstChildInternal(newChild);
	    }
	    if (getLastChild() == oldChild) {
	        setLastChildInternal(newChild);
	    }
        oldChild.setPreviousSibling(null);
	    oldChild.setNextSibling(null);
	    oldChild.setParentNode(null);
	    return oldChild;
	}
    
    public ASTNode removeChild(ASTNode oldChild) {
    	Log.getLogger().debug("Removing " + oldChild + " from " + this);
        removeChildren(oldChild, oldChild);
        
	    oldChild.setPreviousSibling(null);
	    oldChild.setNextSibling(null);
        return oldChild;
    }
        
    /**
     * Removes all children from begin to end inclusively.
     */
    private void removeChildren(ASTNode begin, ASTNode end) {
        if (begin == null || end == null) throw new RuntimeException("Illegal null parameters");
    	ASTNode node = begin;
        while (node!= null) {
            if (node.getParentNode() != this) {
                throw new DOMException(DOMException.NOT_FOUND_ERR, "Node " + node + " is not a child of " + this);
            }
            node.setParentNode(null);
            childCount--;
            if (node == end) break;
            node = node.getNextSibling();
        }
        
        
        if (node != end) {
        	throw new RuntimeException("Node " + end + " is not a right-sibling of " + begin);
        }

        if (begin.getPreviousSibling() != null) {
            begin.getPreviousSibling().setNextSibling(end.getNextSibling());
        }
        if (end.getNextSibling() != null) {
            end.getNextSibling().setPreviousSibling(begin.getPreviousSibling());
        }
        if (getFirstChild() == begin) {
	        setFirstChildInternal(end.getNextSibling());
	    }
	    if (getLastChild() == end) {
	        setLastChildInternal(begin.getPreviousSibling());
	    }
    }
    
    public void removeChildren() {
    	if (getFirstChild() != null) {
    		removeChildren(getFirstChild(), getLastChild());
    	}
    }
    
    public int getChildCount() {
        return childCount;
    }
    
    /**
     * Inserts the node newChild after the existing child node refChild.
     * If refChild is null, insert newChild at the beginning of the list of children.  
     * 
     * @param newChild The node to insert
     * @param refChild The reference node, i.e., the node before which the new node must be inserted
     * @return
     */
//    public ASTNode insertAfter(ASTNode newChild, ASTNode refChild) {
//        if (refChild == null) {
//            refChild = getFirstChild();
//        } else {
//            refChild = refChild.getNextSibling();
//        }
//        return insertBefore(newChild, refChild);
//    }

    /**
     * Inserts the node newChild before the existing child node refChild.
     * If refChild is null, insert newChild at the end of the list of children.  
     * 
     * @param newChild The node to insert
     * @param refChild The reference node, i.e., the node before which the new node must be inserted
     * @return
     */
    public ASTNode insertBefore(ASTNode newChild, ASTNode refChild) {
		if (refChild == null) {
            return appendChild(newChild);
        }

    	Log.getLogger().debug("Inserting " + newChild + " before " + refChild + " in " + this);
    	
    	if (refChild.getParentNode() != this) {
            throw new DOMException(DOMException.NOT_FOUND_ERR, "Reference " + refChild + " is not a child of " + this);
        }
        
        unlink(newChild);

        if (refChild.getPreviousSibling() != null) {
            refChild.getPreviousSibling().setNextSibling(newChild);
        }
        newChild.setPreviousSibling(refChild.getPreviousSibling());
        newChild.setNextSibling(refChild);
	    newChild.setParentNode(this);
	    childCount++;
        
        refChild.setPreviousSibling(newChild);
        
	    if (getFirstChild() == refChild) {
	        setFirstChildInternal(newChild);
	    }
	    
        return newChild;
    }
    
    public void addStatements(java.util.List statements) {
        for (int i=0; i<statements.size(); i++) {
            appendChild((ASTNode)statements.get(i));
        }
    }
    
    
    public ASTNode getFirstChild() {
        return firstChild;
    }
    
    public ASTNode getLastChild() {
        return lastChild;
    }
    
    /**
     * @param firstChild The firstChild to set.
     */
    private void setFirstChildInternal(ASTNode newFirstChild) {
        firstChild = newFirstChild;
        if (firstChild != null) {
            firstChild.setPreviousSibling(null);
            beginIndex = Math.min(beginIndex, firstChild.getBeginIndex());
        }
    }

    /**
     * @param lastChild The lastChild to set.
     */
    private void setLastChildInternal(ASTNode newLastChild) {
        lastChild = newLastChild;
        if (lastChild != null) {
            lastChild.setNextSibling(null);
            endIndex = Math.max(endIndex, lastChild.getEndIndex());
        }
    }
    
    /**
     * If the specified node is contained in a tree, remove it.
     */
    private void unlink(ASTNode node) {
        if (node.getParentBlock() != null) {
            node.getParentBlock().removeChild(node);
        }
    }
    
    public String getLabel() {
    	if (label == null) throw new RuntimeException("Statement is not labeled");
        return label;
    }
    
    public void setLabel(String theLabel) {
        label = theLabel;
    }
    
    public boolean isLabeled() {
        return label != null;
    }

    public String setLabeled() {
        if (label == null) label = "L" + (++TAG);
        return label;
    }
} public class BooleanExpression implements Cloneable {
    private Expression expression;
    
    public BooleanExpression(Expression newExpression) {
        expression = newExpression;
    }

    public Expression getExpression() {
        return expression;
    }


} public class BreakStatement extends LabeledJump {
    
    public BreakStatement(String theLabel) {
        super(theLabel);
    }
    
    public BreakStatement(Block block) {
        super(block);
    }
    
    public void visit(AbstractVisitor visitor) {
	    visitor.visit(this);
    }
    
} public class ContinueStatement extends LabeledJump {
    
	public ContinueStatement(Block block) {
        super(block);
    }
	
    public void visit(AbstractVisitor visitor) {
	    visitor.visit(this);
    }
    
} public class Expression extends Block implements Cloneable {
    
    Type type = Type.UNKNOWN;
    
    public Expression() {
        super();
    }
    
    public Expression(int theBeginIndex, int theEndIndex) {
        super(theBeginIndex, theEndIndex);
    }
    
    public Object clone() {
        if (getChildCount() > 0) throw new RuntimeException("Cannot clone expression with children");
        ASTNode node;
        try {
            node = (ASTNode) super.clone();
        } catch (CloneNotSupportedException e) {
            return null;
        }
        node.setParentNode(null);
        node.setPreviousSibling(null);
        node.setNextSibling(null);
        return node;
    }
    
    public Type getTypeBinding() {
        return type;
    }
    
    public void setTypeBinding(Type theType) {
        type = theType;
    }
    
    public int getCategory() {
        if (getTypeBinding().getType() == Type.LONG.getType()) return Form.CATEGORY2;
        if (getTypeBinding().getType() == Type.DOUBLE.getType()) return Form.CATEGORY2;
        return Form.CATEGORY1;
        //return getTypeBinding().getType() == Type.LONG.getType() || getTypeBinding().getType() == Type.DOUBLE.getType()?Form.CATEGORY2:Form.CATEGORY1;
    }

} public class IfStatement extends Block {
    
    public IfStatement() {
    	super();
    }
    
    public Expression getExpression() {
        return (Expression) getChildAt(0);
    }
    
    public void setExpression(Expression expression) {
        widen(expression);
        setChildAt(0, expression);
    }
    
    public Block getIfBlock() {
        return (Block) getChildAt(1);
    }
    
    public void setIfBlock(Block block) {
        widen(block);
        setChildAt(1, block);
    }
    
    public Block getElseBlock() {
        if (getChildCount() < 3) return null;
        return (Block) getChildAt(2);
    }
    
    public void setElseBlock(Block block) {
        widen(block);
        setChildAt(2, block);
    }
    
    public void visit(AbstractVisitor visitor) {
	    visitor.visit(this);
    }

}
import com.j2js.Log;
import com.j2js.Optimizer;
import com.j2js.cfg.ConditionalEdge;
import com.j2js.cfg.ControlFlowGraph;
import com.j2js.cfg.Edge;
import com.j2js.cfg.Graph;
import com.j2js.cfg.Node;
import com.j2js.dom.Block;
import com.j2js.dom.BooleanExpression;
import com.j2js.dom.BreakStatement;
import com.j2js.dom.ContinueStatement;
import com.j2js.dom.Expression;
import com.j2js.dom.IfStatement;
package com.j2js.cfg.transformation;


public abstract class Transformation {
    
    static Class[] transformations = new Class[] {
        Switch.class,
        Try.class,
        //If.class,
        //IfElse.class,
        Loop.class,
        // Merge must be applied after Loop.
        Merge.class
    };

    public static Transformation select(Graph graph, Node node) {
        
        for (int i=0; i<transformations.length; i++) {
            Transformation t = fetch(i);
            if (t.applies(node)) {
                return t;
            }
        }
    
        return null;
    }

    static Transformation fetch(int index) {
        Transformation t = null;
        try {
            t = (Transformation) transformations[index].newInstance();
        } catch (InstantiationException e) {
            throw new RuntimeException(e);
        } catch (IllegalAccessException e) {
            throw new RuntimeException(e);
        }
    
        return t;
    }
    
    ControlFlowGraph graph;
    public Node header;
    Node newNode;
    
    public Transformation() {
    }
    
    public Node apply() {
        newNode = graph.createNode(Node.class);
        newNode.setInitialPc(header.getInitialPc());
        newNode.trans = this;
        apply_();
        
        // Remove Header.
        graph.replaceNode(header, newNode);
        
        Log.getLogger().debug(toString() + " -> " + newNode);
        return newNode;
    }
    
    public boolean applies(Node node) {
        graph = (ControlFlowGraph) node.getGraph();
        header = node;
        return applies_();
    }
    
    abstract boolean applies_();
    abstract void apply_();
    abstract void rollOut_(Block block);
    
    public void rollOut(Block block) {
        rollOut_(block);
        block.appendChildren(newNode.block);
    }
    
    void produceJump(Edge edge, Block labeledBlock) {
        Node referer = edge.getOrgSource();
        Block breakBlock;
        if (edge instanceof ConditionalEdge) {
            ConditionalEdge condEdge = (ConditionalEdge) edge;
            BooleanExpression condExpr = condEdge.getBooleanExpression();
            Expression expr = Optimizer.simplifyBooleanExpression(condExpr.getExpression(), condEdge.isNegate());
            IfStatement ifStmt = new IfStatement();
            ifStmt.setExpression(expr);
            referer.block.appendChild(ifStmt);
            Block ifBlock = new Block();
            ifStmt.setIfBlock(ifBlock);
            breakBlock = ifBlock;
        } else {
            breakBlock = referer.block;
        }
        
        if (edge.isBackEdge()) {
            breakBlock.appendChild(new ContinueStatement(labeledBlock));
        } else {
            breakBlock.appendChild(new BreakStatement(labeledBlock));