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.instrsched;
014
015 import java.util.Enumeration;
016
017 import org.jikesrvm.compilers.opt.OptOptions;
018 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
019 import org.jikesrvm.compilers.opt.depgraph.DepGraph;
020 import org.jikesrvm.compilers.opt.depgraph.DepGraphNode;
021 import org.jikesrvm.compilers.opt.ir.BasicBlock;
022 import org.jikesrvm.compilers.opt.ir.IR;
023 import org.jikesrvm.compilers.opt.ir.Instruction;
024 import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
025 import org.jikesrvm.compilers.opt.util.GraphNode;
026
027 /**
028 * This a simple list-based instruction scheduler.
029 * <p>
030 * TODO:
031 * <ul>
032 * <li>Add more priority lists
033 * <li>When scheduling an instruction, verify that its predecessors have
034 * already been scheduled.
035 * <li>Change forward propagation of earliest time to computing it from the
036 * scheduling time of predecessors + latencies.
037 * <li>Change bubble sort to insertion sort.
038 * </ul>
039 */
040
041 final class Scheduler {
042 /**
043 * Debugging level.
044 */
045 private static final int VERBOSE = 0;
046
047 /**
048 * Should we print the length of the critical path for each basic block?
049 */
050 private static final boolean PRINT_CRITICAL_PATH_LENGTH = false;
051
052 /**
053 * A constant signifying pre-pass scheduling phase.
054 */
055 public static final int PREPASS = 1;
056
057 /**
058 * A constant signifying post-pass scheduling phase.
059 * <p>
060 * WARNING: POSTPASS INSTRUCTION SCHEDULING (AFTER REGISTER ALLOCATION)
061 * Cannot be done safely due to failure to update GCMapping information.
062 */
063 public static final int POSTPASS = 2;
064
065 /**
066 * Names of various scheduling phases.
067 */
068 public static final String[] PhaseName = new String[]{"Invalid Phase!!!!!!!!", "pre-pass", "post-pass"};
069
070 /**
071 * Current phase (prepass/postpass).
072 */
073 private final int phase;
074
075 /**
076 * Current IR.
077 */
078 private IR ir;
079
080 /**
081 * Current basic block.
082 */
083 private BasicBlock bb;
084
085 /**
086 * Dependence graph for current basic block.
087 */
088 private DepGraph dg;
089
090 /**
091 * Mapping from Instruction to DepGraphNode.
092 */
093 private DepGraphNode[] i2gn;
094
095 /**
096 * Should we print the dependence graph?
097 * @param options the options object
098 * @return true if we should print depgraph, false otherwise
099 */
100 private boolean printDepgraph(OptOptions options) {
101 return (phase == PREPASS && options.PRINT_DG_SCHED_PRE) || (phase == POSTPASS && options.PRINT_DG_SCHED_POST);
102 }
103
104 /**
105 * For each basic block, build the dependence graph and
106 * perform instruction scheduling.
107 * This is an MIR to MIR transformation.
108 *
109 * @param _ir the IR in question
110 */
111 void perform(IR _ir) {
112 // Remember the ir to schedule
113 ir = _ir;
114 if (VERBOSE >= 1) {
115 debug("Scheduling " +
116 ir.method.getDeclaringClass() +
117 ' ' +
118 ir.method.getName() +
119 ' ' +
120 ir.method.getDescriptor());
121 }
122
123 // Performing live analysis may reduce dependences between PEIs and stores
124 if (ir.options.L2M_HANDLER_LIVENESS) {
125 new LiveAnalysis(false, false, true).perform(ir);
126 }
127
128 // Create mapping for dependence graph
129 i2gn = new DepGraphNode[ir.numberInstructions()];
130 // Create scheduling info for each instruction
131 for (Enumeration<Instruction> instr = ir.forwardInstrEnumerator(); instr.hasMoreElements();) {
132 SchedulingInfo.createInfo(instr.nextElement());
133 }
134 // iterate over each basic block
135 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
136 bb = e.nextElement();
137 if (bb.isEmpty()) {
138 continue;
139 }
140 // HACK: temporarily disable scheduling of unsafe basic blocks.
141 // TODO: remove when UNINT_BEGIN/END are working properly.
142 if (bb.isUnsafeToSchedule()) {
143 continue;
144 }
145 // Build Dependence graph
146 dg = new DepGraph(ir, bb.firstInstruction(), bb.lastRealInstruction(), bb);
147 if (printDepgraph(ir.options)) {
148 // print dependence graph.
149 System.out.println("**** START OF " + PhaseName[phase].toUpperCase() + " DEPENDENCE GRAPH ****");
150 dg.printDepGraph();
151 System.out.println("**** END OF " + PhaseName[phase].toUpperCase() + " DEPENDENCE GRAPH ****");
152 }
153 scheduleBasicBlock();
154 }
155
156 // Remove scheduling info for each instruction
157 for (Enumeration<Instruction> instr = ir.forwardInstrEnumerator(); instr.hasMoreElements();) {
158 SchedulingInfo.removeInfo(instr.nextElement());
159 }
160 // Remove mapping for dependence graph
161 i2gn = null;
162 // Clear the ir to schedule
163 bb = null;
164 dg = null;
165 ir = null;
166 }
167
168 /**
169 * Initialize scheduler for a given phase.
170 *
171 * @param phase the scheduling phase
172 */
173 Scheduler(int phase) {
174 this.phase = phase;
175 }
176
177 /**
178 * Output debugging information.
179 * @param s string to print
180 */
181 private static void debug(String s) {
182 System.err.println(s);
183 }
184
185 /**
186 * Output debugging information with indentation.
187 * @param depth level of indenting
188 * @param s string to print
189 */
190 private static void debug(int depth, String s) {
191 String format = String.format("%% %ds", depth*2);
192 debug(String.format(format, s));
193 }
194
195 /**
196 * Set corresponding graph node for instruction.
197 * @param i given instruction
198 * @param n dependence graph node for instruction
199 */
200 private void setGraphNode(Instruction i, DepGraphNode n) {
201 i2gn[i.scratch] = n;
202 }
203
204 /**
205 * Return corresponding graph node for instruction.
206 * @param i given instruction
207 */
208 private DepGraphNode getGraphNode(Instruction i) {
209 return i2gn[i.scratch];
210 }
211
212 /**
213 * Perform DFS to compute critical path for all instructions.
214 * @param n start node
215 * @param depth current DFS depth
216 */
217 private void computeCriticalPath(DepGraphNode n, int depth) {
218 if (VERBOSE >= 5) {
219 debug(depth, "Visiting " + n);
220 }
221 Instruction i = n.instruction();
222 if (SchedulingInfo.getCriticalPath(i) != -1) {
223 return;
224 }
225 int cp = 0;
226 for (Enumeration<GraphNode> succ = n.outNodes(); succ.hasMoreElements();) {
227 DepGraphNode np = (DepGraphNode) succ.nextElement();
228 Instruction j = np.instruction();
229 computeCriticalPath(np, depth + 1);
230 int d = SchedulingInfo.getCriticalPath(j);
231 if (d + 1 > cp) {
232 cp = d + 1;
233 }
234 }
235 SchedulingInfo.setCriticalPath(i, cp);
236 }
237
238 /**
239 * Compute earliest scheduling time for an instruction.
240 * @param i given instruction
241 */
242 private int computeEarliestTime(Instruction i) {
243 if (VERBOSE >= 5) {
244 debug("Computing earliest time for " + i);
245 }
246 DepGraphNode n = getGraphNode(i);
247 int etime = SchedulingInfo.getEarliestTime(i);
248 if (etime == -1) {
249 etime = 0;
250 }
251 OperatorClass opc = i.operator().getOpClass();
252 if (VERBOSE >= 7) {
253 debug("opc=" + opc);
254 }
255 if (opc == null) {
256 throw new OptimizingCompilerException("Missing operator class " + i.operator());
257 }
258 for (Enumeration<GraphNode> pred = n.inNodes(); pred.hasMoreElements();) {
259 DepGraphNode np = (DepGraphNode) pred.nextElement();
260 Instruction j = np.instruction();
261 int time = SchedulingInfo.getTime(j);
262 if (VERBOSE >= 6) {
263 debug("Predecessor " + j + " scheduled at " + time);
264 }
265 if (time == -1) {
266 throw new OptimizingCompilerException("Instructions not in topological order: " + i + "; " + j);
267 }
268 if (VERBOSE >= 6) {
269 debug("Retrieving latency from " + j);
270 }
271 OperatorClass joc = j.operator().getOpClass();
272 if (VERBOSE >= 7) {
273 debug("j's class=" + joc);
274 }
275 if (joc == null) {
276 throw new OptimizingCompilerException("Missing operator class " + j.operator());
277 }
278 int lat = joc.latency(opc);
279 if (time + lat > etime) {
280 etime = time + lat;
281 }
282 }
283 if (VERBOSE >= 5) {
284 debug("Updating time of " + i + " to " + etime);
285 }
286 SchedulingInfo.setEarliestTime(i, etime);
287 return etime;
288 }
289
290 /**
291 * A class representing sorted list of instructions.
292 * The instructions are sorted by their position on the critical path.
293 */
294 private static final class InstructionBucket {
295 /**
296 * The instruction in the current slot.
297 */
298 public Instruction instruction;
299 /**
300 * Next pointer.
301 */
302 public InstructionBucket next;
303
304 /**
305 * Create a list element containing the instruction.
306 * @param i given instruction
307 */
308 private InstructionBucket(Instruction i) {
309 instruction = i;
310 }
311
312 /**
313 * Insert the instruction into a given slot (based on its scheduling time).
314 * @param pool the bucket pool
315 * @param i given instruction
316 */
317 public static void insert(InstructionBucket[] pool, Instruction i) {
318 InstructionBucket ib = new InstructionBucket(i);
319 int time = SchedulingInfo.getTime(i);
320 if (pool[time] == null) {
321 pool[time] = ib;
322 return;
323 }
324 int cp = SchedulingInfo.getCriticalPath(i);
325 Instruction j = pool[time].instruction;
326 if (SchedulingInfo.getCriticalPath(j) < cp) {
327 ib.next = pool[time];
328 pool[time] = ib;
329 return;
330 }
331 InstructionBucket p = pool[time];
332 InstructionBucket t = p.next;
333 while (t != null) {
334 j = t.instruction;
335 if (SchedulingInfo.getCriticalPath(j) < cp) {
336 break;
337 }
338 p = t;
339 t = t.next;
340 }
341 ib.next = t;
342 p.next = ib;
343 }
344 }
345
346 /**
347 * Sort basic block by Scheduled Time.
348 * Uses bucket sort on time, with equal times ordered by critical path.
349 * @param maxtime the maximum scheduled time
350 */
351 private boolean sortBasicBlock(int maxtime) {
352 boolean changed = false;
353 InstructionBucket[] pool = new InstructionBucket[maxtime + 1];
354 int num = bb.firstInstruction().scratch;
355 Instruction ins;
356 while ((ins = bb.firstRealInstruction()) != null) {
357 InstructionBucket.insert(pool, ins);
358 ins.remove();
359 }
360 for (int i = 0; i <= maxtime; i++) {
361 for (InstructionBucket t = pool[i]; t != null; t = t.next) {
362 bb.appendInstruction(t.instruction);
363 changed = changed || num > t.instruction.scratch;
364 num = t.instruction.scratch;
365 }
366 }
367 return changed;
368 }
369
370 /**
371 * Schedule a basic block.
372 */
373 private void scheduleBasicBlock() {
374 if (VERBOSE >= 2) {
375 debug("Scheduling " + bb);
376 }
377 if (VERBOSE >= 4) {
378 debug("**** START OF CURRENT BB BEFORE SCHEDULING ****");
379 for (Enumeration<Instruction> bi = bb.forwardInstrEnumerator(); bi.hasMoreElements();) {
380 debug(bi.nextElement().toString());
381 }
382 debug("**** END OF CURRENT BB BEFORE SCHEDULING ****");
383 }
384 // Build mapping from instructions to graph nodes
385 for (DepGraphNode dgn = (DepGraphNode) dg.firstNode(); dgn != null; dgn = (DepGraphNode) dgn.getNext())
386 {
387 setGraphNode(dgn.instruction(), dgn);
388 if (VERBOSE >= 4) {
389 debug("Added node for " + dgn.instruction());
390 }
391 }
392 ResourceMap rmap = new ResourceMap();
393 int bl = 0;
394 Instruction fi = bb.firstInstruction();
395 if (VERBOSE >= 5) {
396 debug("Computing critical path for " + fi);
397 }
398 computeCriticalPath(getGraphNode(fi), 0);
399 int cp = SchedulingInfo.getCriticalPath(fi);
400 for (Enumeration<Instruction> ie = bb.forwardRealInstrEnumerator(); ie.hasMoreElements();) {
401 Instruction i = ie.nextElement();
402 if (VERBOSE >= 5) {
403 debug("Computing critical path for " + i);
404 }
405 computeCriticalPath(getGraphNode(i), 0);
406 int d = SchedulingInfo.getCriticalPath(i);
407 if (d > cp) {
408 cp = d;
409 }
410 bl++;
411 }
412 cp++;
413 if (PRINT_CRITICAL_PATH_LENGTH) {
414 System.err.println("::: BL=" + bl + " CP=" + cp + " LOC=" + ir.method + ":" + bb);
415 }
416 Priority ilist = new DefaultPriority(bb);
417 int maxtime = 0;
418 for (ilist.reset(); ilist.hasMoreElements();) {
419 Instruction i = ilist.nextElement();
420 if (VERBOSE >= 3) {
421 debug("Scheduling " + i + "[" + SchedulingInfo.getInfo(i) + "]");
422 }
423 int time = computeEarliestTime(i);
424 while (!rmap.schedule(i, time)) {
425 time++;
426 }
427 if (VERBOSE >= 5) {
428 debug("Scheduled " + i + " at time " + time);
429 }
430 if (time > maxtime) {
431 maxtime = time;
432 }
433 }
434 if (VERBOSE >= 2) {
435 debug("Done scheduling " + bb);
436 }
437 if (VERBOSE >= 3) {
438 debug(rmap.toString());
439 }
440 boolean changed = sortBasicBlock(maxtime);
441 if (changed && VERBOSE >= 2) {
442 debug("Basic block " + bb + " changed");
443 }
444 if (VERBOSE >= 4) {
445 debug("**** START OF CURRENT BB AFTER SCHEDULING ****");
446 for (Enumeration<Instruction> bi = bb.forwardInstrEnumerator(); bi.hasMoreElements();) {
447 debug(bi.nextElement().toString());
448 }
449 debug("**** END OF CURRENT BB AFTER SCHEDULING ****");
450 }
451 }
452 }
453