001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.opt.depgraph;
014
015import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK;
016
017import org.jikesrvm.compilers.opt.OptimizingCompilerException;
018import org.jikesrvm.compilers.opt.ir.BasicBlock;
019import org.jikesrvm.compilers.opt.ir.IR;
020import org.jikesrvm.compilers.opt.ir.Instruction;
021import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
022
023/**
024 * This module provides dependence graph statistics. It will only
025 * be used for for experimental measurements, so compile-time overhead
026 * is less of a concern.
027 *
028 * @see DepGraph
029 */
030public class DepGraphStats {
031  /**
032   * Create a statistical summary of a dependence graph for a given basic
033   * block.
034   *
035   * @param   dg        the dependence graph
036   * @param   bbName    name of the basic block
037   */
038  DepGraphStats(DepGraph dg, String bbName) {
039    // First pass -- compute numNodes
040    int _numNodes = 0;
041    boolean containsLoadOrStore = false;
042    for (DepGraphNode n = (DepGraphNode) dg.firstNode(); n != null; n = (DepGraphNode) n.getNext()) {
043      _numNodes++;
044      Instruction instr = n.instruction();
045      if (instr.isImplicitStore() || instr.isImplicitLoad()) {
046        containsLoadOrStore = true;
047      }
048    }
049    DepGraphNode[] nodes = new DepGraphNode[_numNodes];
050    int[] ECT = new int[_numNodes];              // Earliest Completion Times
051    int _totalTime = 0;
052    int _critPathLength = 0;
053    // Second pass -- compute times
054    int i = 0;
055    for (DepGraphNode n = (DepGraphNode) dg.firstNode(); n != null; n = (DepGraphNode) n.getNext()) {
056      nodes[i] = n;
057      ECT[i] = 0;
058      for (DepGraphEdge e = (DepGraphEdge) n.firstInEdge(); e != null; e = (DepGraphEdge) e.getNextIn()) {
059        DepGraphNode pred = (DepGraphNode) e.fromNode();
060        // Look for pred in nodes[]
061        int j;
062        for (j = 0; j < i; j++) {
063          if (nodes[j] == pred) {
064            break;
065          }
066        }
067        if (j == i) {
068          // Not found
069          throw new OptimizingCompilerException("DepGraphStats: dep graph is not topologically sorted ???");
070          // NOTE: I could not use SortedGraphIterator
071          // for top sort because DepGraphNode
072          // is not a subclass of SortedGraphNode
073        }
074        // TODO: add edge latency also??
075        ECT[i] = Math.max(ECT[i], ECT[j]);
076      }         // for ( e = ... )
077      Instruction instr = n.instruction();
078      int curTime = estimateExecutionTime(instr);
079      _totalTime += curTime;
080      ECT[i] += curTime;
081      _critPathLength = Math.max(_critPathLength, ECT[i]);
082      i++;
083    }           // for ( n = ... )
084    System.out.println("@@@@ BB " +
085                       bbName +
086                       "; totalTime = " +
087                       _totalTime +
088                       "; containsLoadOrStore = " +
089                       containsLoadOrStore +
090                       "; critPathLength = " +
091                       _critPathLength);
092  }
093
094  /**
095   * Print the dependence graph stats for all basic blocks in an IR.
096   * @param ir the IR
097   */
098  public static void printBasicBlockStatistics(IR ir) {
099    final boolean DEBUG = false;
100    System.out.println();
101    System.out.println("**** START OF printBasicBlockStatistics() for method " + ir.method + " ****");
102    if (DEBUG) {
103      ir.printInstructions();
104    }
105
106    // Performing live analysis may reduce dependences between PEIs and stores
107    if (ir.options.L2M_HANDLER_LIVENESS) {
108      new LiveAnalysis(false, false, true).perform(ir);
109    }
110
111    for (BasicBlock bb = ir.firstBasicBlockInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
112      //DepGraph dg =
113      new DepGraph(ir, bb.firstRealInstruction(), bb.lastRealInstruction(), bb);
114    }
115    System.out.println("**** END OF printBasicBlockStatistics() ****");
116  }
117
118  /**
119   * Returns an estimate of the number of cycles for a given instruction.
120   * Currently, this estimate is comically simple (see below).
121   *
122   * @param instr the instruction
123   * @return {@code 0} or {@code 1}
124   */
125  int estimateExecutionTime(Instruction instr) {
126    if (instr.operator() == NULL_CHECK) {
127      return 0;
128    } else {
129      return 1;
130    }
131  }
132}