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 */
013 package org.jikesrvm.compilers.opt.depgraph;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK;
016
017 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
018 import org.jikesrvm.compilers.opt.ir.BasicBlock;
019 import org.jikesrvm.compilers.opt.ir.IR;
020 import org.jikesrvm.compilers.opt.ir.Instruction;
021 import 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 */
030 public 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 * Return an estimate of the number of cycles for a given instruction.
120 * Currently, this estimate is comically simple.
121 * @param instr the instruction
122 */
123 int estimateExecutionTime(Instruction instr) {
124 if (instr.operator() == NULL_CHECK) {
125 return 0;
126 } else {
127 return 1;
128 }
129 }
130 }