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