/**
 * 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.stack.isea;

import avrora.core.*;
import avrora.core.ControlFlowGraph.Block;
import cck.text.*;
import cck.util.Util;
import java.util.*;

/**
 * The <code>ISEAnalyzer</code> class is a static analyzer for machine code. This class
 * implements intra-procedural side-effect analysis. This determines the set of registers
 * read and modified by this procedure locally; this information can be used to reduce
 * the amount of work that other static analyzers must do when they analyze code, because
 * they can use the results of this analysis to know which registers' values are used, and
 * which registers are unmodified by a procedure.
 *
 * @author Ben L. Titzer
 */
public class ISEAnalyzer implements ISEInterpreter.SummaryCache {

    protected final Program program;
    protected final SourceMapping smap;
    protected final ControlFlowGraph cfg;
    protected final ProcedureMap pmap;
    protected final HashMap<Block, ISEState> procedureSummaries;
    protected final HashMap<Integer, ISEState> returnSummaries;
    protected final Stack<Block> stack;

    protected final Verbose.Printer printer = Verbose.getVerbosePrinter("analysis.isea");

    public ISEAnalyzer(Program p) {
        program = p;
        smap = p.getSourceMapping();
        cfg = program.getCFG();
        pmap = cfg.getProcedureMap();
        procedureSummaries = new HashMap<Block, ISEState>();
        returnSummaries = new HashMap<Integer, ISEState>();
        stack = new Stack<Block>();
    }

    class Item {
        ControlFlowGraph.Block block;
        Item next;

        Item(ControlFlowGraph.Block b) {
            block = b;
        }
    }

    public ISEState getProcedureSummary(int start) {
        ControlFlowGraph.Block block = cfg.getBlockStartingAt(start);
        if ( block == null ) {
            throw Util.failure("cannot get procedure summary for address: "+StringUtil.addrToString(start));
        }
        analyzeProcedure(block);
        return (ISEState)procedureSummaries.get(block);
    }

    public void recordReturnSummary(int retaddr, ISEState rs) {
        ISEState ors = getReturnSummary(retaddr);
        if ( ors == null ) {
            ors = rs.dup();
            returnSummaries.put(new Integer(retaddr), ors);
        } else {
            ors.merge(rs);
        }
    }

    public ISEState getReturnSummary(int retaddr) {
        return (ISEState)returnSummaries.get(new Integer(retaddr));
    }

    public void analyze() {
        HashSet<Block> seen = new HashSet<Block>();
        Item head;
        Item tail = head = new Item(cfg.getBlockStartingAt(0x0000));

        while ( head != null ) {
            ControlFlowGraph.Block block = head.block;
            if ( printer.enabled ) {
                Terminal.println("looking at block "+getBlockName(block));
            }
            seen.add(block);
            if ( pmap.getProcedureEntrypoints().contains(block) ) {
                // this is a procedure entrypoint
                analyzeProcedure(block);
            } else {
                // otherwise, look for successor blocks
                Iterator<ControlFlowGraph.Edge> i = block.getEdgeIterator();
                while ( i.hasNext() ) {
                    ControlFlowGraph.Edge e = i.next();
                    ControlFlowGraph.Block target = e.getTarget();
                    tail = addToWorkList(seen, target, tail);
                }

                // are there any indirect edges that we should know about?
                int lastAddr = block.getLastAddress();
                List<Integer> list = program.getIndirectEdges(lastAddr);
                if ( list != null ) {
                    for (Integer taddr : list) {
                        // add the indirect target to the work list
                        tail = addToWorkList(seen, cfg.getBlockStartingAt(taddr), tail);
                    }
                }
            }

            head = head.next;
        }
    }

    private Item addToWorkList(HashSet<Block> seen, ControlFlowGraph.Block target, Item tail) {
        if ( target == null ) return tail;
        if ( !seen.contains(target) ) {
            // if we haven't seen this block before, add to worklist
            tail.next = new Item(target);
            tail = tail.next;
        }
        return tail;
    }

    public void analyzeProcedure(ControlFlowGraph.Block start) {
        // first check the procedure summary cache
        if ( procedureSummaries.containsKey(start) ) return;
        if ( printer.enabled ) {
            printStart(start);
        }
        if ( stack.contains(start) ) {
            throw Util.failure("program contains recursion");
        }
        stack.push(start);
        ISEState rs = new ISEInterpreter(program, this).analyze(start.getAddress());
        procedureSummaries.put(start, rs);
        stack.pop();
    }

    private void printStart(ControlFlowGraph.Block start) {
        int size = stack.size();
        String indent = StringUtil.dup('=', 4*size+3);
        Terminal.print(Terminal.COLOR_MAGENTA, indent+">");
        Terminal.print(Terminal.COLOR_PURPLE, " ISE: Analyzing procedure ");
        Terminal.printBrightCyan(getBlockName(start));
        Terminal.nextln();
    }

    private String getBlockName(ControlFlowGraph.Block start) {
        int address = start.getAddress();
        return "("+smap.getName(address)+": "+ StringUtil.addrToString(address)+")";
    }

    public void analyze(int loc) {
        ISEState s = new ISEInterpreter(program, this).analyze(loc);
        TermUtil.printSeparator();
        if ( s != null ) {
            Terminal.printRed("RETURN STATE");
            Terminal.nextln();
            s.print(loc);
        } else {
            Terminal.printRed("PROCEDURE DOES NOT RETURN");
            Terminal.nextln();
        }
    }
}
