code: /**
   * Copyright (c) 2004-2005, Regents of the University of California
   * All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * Redistributions of source code must retain the above copyright notice,
   * this list of conditions and the following disclaimer.
   *
   * Redistributions in binary form must reproduce the above copyright
   * notice, this list of conditions and the following disclaimer in the
   * documentation and/or other materials provided with the distribution.
   *
   * Neither the name of the University of California, Los Angeles nor the
   * names of its contributors may be used to endorse or promote products
   * derived from this software without specific prior written permission.
   *
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   */
  
  package avrora.core;
  
  import avrora.arch.legacy.LegacyInstr;
  import cck.util.Util;
  import java.util.*;
  
  /**
   * The <code>ControlFlowGraph</code> represents a control flow graph for an entire program, including all
   * basic blocks and all procedures.
   *
   * @author Ben L. Titzer
   * @see Program
   * @see ProcedureMap
   */
  public class ControlFlowGraph {
  
      /**
       * The <code>Edge</code> represents an edge leaving a basic block and (optionally) arriving at another,
       * known basic block. When the target is not know, for example in the case of an indirect call or branch,
       * then the accessor methods to this field return <code>null</code>. Each edge has a type that is
       * represented as a string.
       */
      public class Edge {
          private final String type;
          private final Block source;
          private final Block target;
  
          /**
           * The constructor for the <code>Edge</code> class creates a new edge with the specified type
           * with the specified source block and specified destination block.
           * @param t the type of the edge
           * @param s the source block of the edge
           * @param b the destination block of the edge
           */
          Edge(String t, Block s, Block b) {
              type = t;
              source = s;
              target = b;
          }
  
          /**
           * The <code>getType()</code> method returns the string name of the type of this edge. This type
           * denotes whether it is a call, return, or regular edge.
           *
           * @return the string name of the type of the edge
           */
          public String getType() {
              return type;
          }
  
          /**
           * The <code>getSource()</code> method returns the basic block that is the source of this edge. The
           * edge is always from the last instruction in the basic block.
           *
           * @return the basic block that is the source of this edge
           */
          public Block getSource() {
              return source;
          }
  
          /**
           * The <code>getTarget()</code> method returns the known target of this control flow graph edge, if it
           * is known. In the case of indirect calls, branches, or a return, the target block is not known--in
           * that case, this method returns <code>null</code>.
           *
           * @return the basic block that is the target of this edge if it is known; null otherwise
           */
          public Block getTarget() {
              return target;
          }
      }
  
      /**
       * The <code>Block</code> class represents a basic block of code within the program. A basic block
       * contains a straight-line piece of code that ends with a control instruction (e.g. a skip, a jump, a
       * branch, or a call) or an implicit fall-through to the next basic block. It contains at most two
       * references to successor basic blocks.
       * <p/>
       * For <b>fallthroughs</b> (no ending control instruction), the <code>next</code> field refers to the
       * block immediately following this block, and the <code>other</code> field is null.
       * <p/>
       * For <b>jumps</b>, the <code>other</code> field refers to the block that is the target of the jump, and
       * the <code>next</code> field is null.
       * <p/>
       * For <b>skips</b>, <b>branches</b>, and <b>calls</b>, the <code>next</code> field refers to the block
       * immediately following this block (i.e. not-taken for branches, the return address for calls). The
       * <code>other</code> field refers to the target address of the branch if it is taken or the address to be
       * called.
       * <p/>
       * For <b>indirect jumps</b> both the <code>next</code> and <code>other</code> fields are null.
       * <p/>
       * For <b>indirect calls</b> the <code>next</code> field refers to the block immediately following this
       * block (i.e. the return address). The <code>other</code> field is null because the target of the call
       * cannot be known.
       */
      public class Block {
  
          private final int address;
          private int last_address;
          private int size;
          private int length;
  
          private final List<LegacyInstr> instructions;
          private final List<Edge> edges;
  
          Block(int addr) {
              address = addr;
              last_address = address;
              instructions = new LinkedList<LegacyInstr>();
              edges = new LinkedList<Edge>();
          }
  
  
          /**
           * The <code>addInstr()</code> method adds an instruction to the end of this basic block. It is not
           * recommended for general use: it is generally used by the <code>CFGBuilder</code> class. No
           * enforcement of invariants is made: this method does not check whether the instruction being added
           * changes the control flow or branches to another block, etc.
           *
           * @param i the instruction to add to this basic block
           */
          public void addInstr(LegacyInstr i) {
              instructions.add(i);
  
              last_address = address + size;
              size += i.getSize();
              length++;
          }
  
          /**
           * The <code>hashCode()</code> method computes the hash code of this block. In the initial
           * implementation, the hash code is simply the byte address of the block
           *
           * @return an integer value that is the hash code of this object
           */
          public int hashCode() {
              return address;
          }
  
          /**
           * The <code>equals()</code> method computes object equality for basic blocks. It simply compares the
           * addresses of the basic blocks and returns true if they match.
           *
           * @param o the other object to compare to
           * @return true if these two basic blocks are equivalent; false otherwise
           */
          public boolean equals(Object o) {
              if (this == o) return true;
              if (!(o instanceof Block)) return false;
              return ((Block)o).address == this.address;
          }
  
          /**
           * The <code>getAddress()</code> method gets the starting byte address of this basic block.
           *
           * @return the starting address of this basic block
           */
          public int getAddress() {
              return address;
          }
  
          /**
           * The <code>getLastAddress()</code> gets the last address that this block covers.
           * @return the last address that this block covers
           */
          public int getLastAddress() {
              return last_address;
          }
  
          /**
           * The <code>getSize()</code> method returns the size of the basic block in bytes.
           *
           * @return the number of bytes in this basic block
           */
          public int getSize() {
              return size;
          }
  
          /**
           * The <code>getLength()</code> returns the length of this basic block in terms of the number of
           * instructions
           *
           * @return the number of instructions in this basic block
           */
          public int getLength() {
              return length;
          }
  
          /**
           * The <code>getInstrIterator()</code> method returns an iterator over the instructions in this basic
           * block. The resulting iterator can be used to iterate over the instructions in the basic block in
           * order.
           *
           * @return an iterator over the instructions in this block.
           */
          public Iterator<LegacyInstr> getInstrIterator() {
              return instructions.iterator();
          }
  
          public Iterator<Edge> getEdgeIterator() {
              return edges.iterator();
          }
      }
  
      private static class BlockComparator implements Comparator<Block> {
          public int compare(Block b1, Block b2) {
              return b1.address - b2.address;
          }
      }
  
      /**
       * The <code>blocks</code> field contains a reference to a map from <code>Integer</code> to
       * <code>Block</code> this map is used to lookup the basic block that starts at a particular address.
       */
      protected final HashMap<Integer, Block> blocks;
  
      /**
       * The <code>edges</code> field contains a reference to the list of edges (instances of class
       * <code>Edge</code>) within this control flow graph.
       */
      protected final List<Edge> allEdges;
  
      /**
       * The <code>program</code> field stores a reference to the program to which this control flow graph
       * corresponds.
       */
      protected final Program program;
  
      /**
       * The <code>COMPARATOR</code> field stores a comparator that is used in sorting basic blocks by program
       * order.
       */
      public static final Comparator<Block> COMPARATOR = new BlockComparator();
  
  
      /**
       * The constructor for the <code>ControlFlowGraph</code> initializes this control flow graph with the
       * given program. It does not build the actual control flow graph-- a <code>CFGBuilder</code> instance
       * does that.
       *
       * @param p the program to create the control flow graph for
       */
      ControlFlowGraph(Program p) {
          program = p;
          blocks = new HashMap<Integer, Block>();
          allEdges = new LinkedList<Edge>();
      }
  
      /**
       * The <code>newBlock()</code> method creates a new block within the control flow graph, starting at the
       * specified address. No checking is done by this method as to whether the address overlaps with another
       * block. This is primarily intended for use within the <code>CFGBuilder</code> class.
       *
       * @param address the byte address at which this block begins
       * @return an instance of <code>Block</code> representing the new block
       */
      public Block newBlock(int address) {
          Block b = new Block(address);
          blocks.put(new Integer(address), b);
          return b;
      }
  
      /**
       * The <code>addEdge()</code> method adds an edge between two blocks with a given type. If the destination
       * block is null, then the edge has an unknown target.
       *
       * @param s    the source block of the edge
       * @param t    the target block of the edge
       * @param type the string name of the type of the edge, e.g. CALL or RETURN
       */
      public void addEdge(Block s, Block t, String type) {
          Edge edge = new Edge(type, s, t);
          s.edges.add(edge);
          allEdges.add(edge);
      }
  
      /**
       * The <code>addEdge()</code> method adds an edge between two blocks. If the destination block is null,
       * then the edge has an unknown target.
       *
       * @param s the source block of the edge
       * @param t the target block of the edge
       */
      public void addEdge(Block s, Block t) {
          Edge edge = new Edge("", s, t);
          s.edges.add(edge);
          allEdges.add(edge);
      }
  
      /**
       * The <code>getBlockStartingAt()</code> method looks up a basic block based on its starting address. If a
       * basic block contains the address, but does not begin at that address, that basic block is ignored.
       *
       * @param address the byte address at which the block begins
       * @return a reference to the <code>Block</code> instance that starts at the address specified, if such a
       *         block exists; null otherwise
       */
      public Block getBlockStartingAt(int address) {
          return blocks.get(new Integer(address));
      }
  
      /**
       * The <code>getBlockContaining()</code> method looks up the basic block that contains the address
       * specified. The basic blocks are assumed to not overlap.
       *
       * @return a reference to the <code>Block</code> instance that contains the address specified, if such a
       *         block exists; null otherwise
       */
      public Block getBlockContaining(int address) {
          throw Util.unimplemented();
      }
  
      /**
       * The <code>getBlockIterator()</code> method constructs an interator over all of the blocks in the
       * control flow graph, regardless of connectivity. No order is guaranteed.
       *
       * @return an instance of <code>Iterator</code> that can be used to iterate over all blocks in the control
       *         flow graph
       */
      public Iterator<Block> getBlockIterator() {
          return blocks.values().iterator();
      }
  
      /**
       * The <code>getBlockIterator()</code> method constructs an interator over all of the blocks in the
       * control flow graph, regardless of connectivity. The order is guaranteed to be in ascending order.
       *
       * @return an instance of <code>Iterator</code> that can be used to iterate over all blocks in the control
       *         flow graph in ascending order
       */
      public Iterator<Block> getSortedBlockIterator() {
          List<Block> l = Collections.list(Collections.enumeration(blocks.values()));
          Collections.sort(l, COMPARATOR);
          return l.iterator();
      }
  
      /**
       * The <code>getEdgeIterator()</code> method returns an interator over all edges between all blocks within
       * this control flow graph.
       *
       * @return an instance of <code>Iterator</code> that iterates over the edges of this control flow graph.
       */
      public Iterator<Edge> getEdgeIterator() {
          return allEdges.iterator();
      }
  
      private ProcedureMap pmap;
  
      /**
       * The <code>getProcedureMap()</code> method returns a reference to a <code>ProcedureMap</code> instance
       * that maps basic blocks to the procedures in which they are contained
       *
       * @return a reference to a <code>ProcedureMap</code> instance for this control flow graph
       */
      public synchronized ProcedureMap getProcedureMap() {
          if (pmap == null) {
              pmap = new ProcedureMapBuilder(program).buildMap();
          }
          return pmap;
      }
  }
  