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.ssa;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.SPLIT;
016
017 import java.util.Enumeration;
018 import java.util.HashMap;
019 import java.util.HashSet;
020 import java.util.Map;
021
022 import org.jikesrvm.classloader.TypeReference;
023 import org.jikesrvm.compilers.opt.DefUse;
024 import org.jikesrvm.compilers.opt.OptOptions;
025 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
026 import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
027 import org.jikesrvm.compilers.opt.controlflow.DominanceFrontier;
028 import org.jikesrvm.compilers.opt.controlflow.DominatorsPhase;
029 import org.jikesrvm.compilers.opt.controlflow.LSTGraph;
030 import org.jikesrvm.compilers.opt.controlflow.LSTNode;
031 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
032 import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
033 import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
034 import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
035 import org.jikesrvm.compilers.opt.ir.BasicBlock;
036 import org.jikesrvm.compilers.opt.ir.IR;
037 import org.jikesrvm.compilers.opt.ir.IRTools;
038 import org.jikesrvm.compilers.opt.ir.Instruction;
039 import org.jikesrvm.compilers.opt.ir.Register;
040 import org.jikesrvm.compilers.opt.ir.RegisterOperandEnumeration;
041 import org.jikesrvm.compilers.opt.ir.Unary;
042 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
043 import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
044 import org.jikesrvm.compilers.opt.regalloc.CoalesceMoves;
045 import org.jikesrvm.compilers.opt.util.GraphNode;
046 import org.jikesrvm.util.BitVector;
047
048
049 /**
050 * Perform live-range splitting.
051 *
052 * <p>This pass splits live ranges where they enter and exit loop bodies
053 * by normal (unexceptional) control flow.
054 * It splits a live range for register r by inserting the instruction
055 * <code> r = SPLIT r </code>. Then, SSA renaming will introduce a new
056 * name for r. The SPLIT operator is later turned into a MOVE during
057 * BURS.
058 *
059 * <p>This pass also splits live ranges on edges to and from infrequent code.
060 *
061 * <p> This composite phase should be performed at the end of SSA in LIR.
062 */
063 public class LiveRangeSplitting extends OptimizationPlanCompositeElement {
064
065 public final boolean shouldPerform(OptOptions options) {
066 return options.SSA_LIVE_RANGE_SPLITTING;
067 }
068
069 /**
070 * Build this phase as a composite of others.
071 */
072 public LiveRangeSplitting() {
073 super("LIR SSA Live Range Splitting", new OptimizationPlanElement[]{
074 // 0. Clean up the IR
075 new OptimizationPlanAtomicElement(new BranchOptimizations(2, true, true)),
076 new OptimizationPlanAtomicElement(new CoalesceMoves()),
077 // 1. Insert the split operations.
078 new OptimizationPlanAtomicElement(new LiveRangeSplittingPhase()),
079 new OptimizationPlanAtomicElement(new BranchOptimizations(2, true, true)),
080 // 2. Use SSA to rename
081 new OptimizationPlanAtomicElement(new DominatorsPhase(true)),
082 new OptimizationPlanAtomicElement(new DominanceFrontier()),
083 new OptimizationPlanAtomicElement(new RenamePreparation()),
084 new OptimizationPlanAtomicElement(new EnterSSA()),
085 new OptimizationPlanAtomicElement(new LeaveSSA())});
086 }
087
088 private static class LiveRangeSplittingPhase extends CompilerPhase {
089
090 /**
091 * Return this instance of this phase. This phase contains no
092 * per-compilation instance fields.
093 * @param ir not used
094 * @return this
095 */
096 public CompilerPhase newExecution(IR ir) {
097 return this;
098 }
099
100 public final boolean shouldPerform(OptOptions options) {
101 return options.SSA_LIVE_RANGE_SPLITTING;
102 }
103
104 public final String getName() {
105 return "Live Range Splitting";
106 }
107
108 /**
109 * The main entrypoint for this pass.
110 */
111 public final void perform(IR ir) {
112 // 1. Compute an up-to-date loop structure tree.
113 DominatorsPhase dom = new DominatorsPhase(true);
114 dom.perform(ir);
115 LSTGraph lst = ir.HIRInfo.loopStructureTree;
116 if (lst == null) {
117 throw new OptimizingCompilerException("null loop structure tree");
118 }
119
120 // 2. Compute liveness.
121 // YUCK: We will later retrieve the live analysis info, relying on the
122 // scratchObject field of the Basic Blocks. Thus, liveness must be
123 // computed AFTER the dominators, since the dominator phase also uses
124 // the scratchObject field.
125 LiveAnalysis live = new LiveAnalysis(false, // don't create GC maps
126 false, // don't skip (final) local
127 // propagation step of live analysis
128 false, // don't store information at handlers
129 true); // skip guards
130 live.perform(ir);
131
132 // 3. Perform the analysis
133 DefUse.computeDU(ir);
134 HashMap<BasicBlockPair, HashSet<Register>> result = findSplitPoints(ir, live, lst);
135
136 // 4. Perform the transformation.
137 transform(ir, result);
138
139 // 5. Record that we've destroyed SSA
140 if (ir.actualSSAOptions != null) {
141 ir.actualSSAOptions.setScalarValid(false);
142 ir.actualSSAOptions.setHeapValid(false);
143 }
144 }
145
146 /**
147 * Find the points the IR where live ranges should be split.
148 *
149 * @param ir the governing IR
150 * @param live valid liveness information
151 * @param lst a valid loop structure tree
152 * @return the result as a mapping from BasicBlockPair to a set of registers
153 */
154 private static HashMap<BasicBlockPair, HashSet<Register>> findSplitPoints(IR ir, LiveAnalysis live,
155 LSTGraph lst) {
156
157 HashMap<BasicBlockPair, HashSet<Register>> result = new HashMap<BasicBlockPair, HashSet<Register>>(10);
158 for (Enumeration<GraphNode> e = lst.enumerateNodes(); e.hasMoreElements();) {
159 LSTNode node = (LSTNode) e.nextElement();
160 BasicBlock header = node.getHeader();
161 BitVector loop = node.getLoop();
162 if (loop == null) continue;
163
164 // First split live ranges on edges coming into the loop header.
165 for (Enumeration<BasicBlock> in = header.getIn(); in.hasMoreElements();) {
166 BasicBlock bb = in.nextElement();
167 if (loop.get(bb.getNumber())) continue;
168 HashSet<Register> liveRegisters = live.getLiveRegistersOnEdge(bb, header);
169 for (Register r : liveRegisters) {
170 if (r.isSymbolic()) {
171 HashSet<Register> s = findOrCreateSplitSet(result, bb, header);
172 s.add(r);
173 }
174 }
175 }
176
177 // Next split live ranges on every normal exit from the loop.
178 for (int i = 0; i < loop.length(); i++) {
179 if (loop.get(i)) {
180 BasicBlock bb = ir.getBasicBlock(i);
181 for (Enumeration<BasicBlock> out = bb.getNormalOut(); out.hasMoreElements();) {
182 BasicBlock dest = out.nextElement();
183 if (loop.get(dest.getNumber())) continue;
184 HashSet<Register> liveRegisters = live.getLiveRegistersOnEdge(bb, dest);
185 for (Register r : liveRegisters) {
186 if (r.isSymbolic()) {
187 HashSet<Register> s = findOrCreateSplitSet(result, bb, dest);
188 s.add(r);
189 }
190 }
191 }
192 }
193 }
194 }
195
196 addEntriesForInfrequentBlocks(ir, live, result);
197
198 return result;
199 }
200
201 /**
202 * Split live ranges on entry and exit to infrequent regions.
203 * Add this information to 'result', a mapping from BasicBlockPair to a set of
204 * registers to split.
205 *
206 * @param ir the governing IR
207 * @param live valid liveness information
208 * @param result mapping from BasicBlockPair to a set of registers
209 */
210 private static void addEntriesForInfrequentBlocks(IR ir, LiveAnalysis live,
211 HashMap<BasicBlockPair, HashSet<Register>> result) {
212 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
213 BasicBlock bb = e.nextElement();
214 boolean bbInfrequent = bb.getInfrequent();
215 for (Enumeration<BasicBlock> out = bb.getNormalOut(); out.hasMoreElements();) {
216 BasicBlock dest = out.nextElement();
217 boolean destInfrequent = dest.getInfrequent();
218 if (bbInfrequent ^ destInfrequent) {
219 HashSet<Register> liveRegisters = live.getLiveRegistersOnEdge(bb, dest);
220 for (Register r : liveRegisters) {
221 if (r.isSymbolic()) {
222 HashSet<Register> s = findOrCreateSplitSet(result, bb, dest);
223 s.add(r);
224 }
225 }
226 }
227 }
228 }
229 }
230
231 /**
232 * Given a mapping from BasicBlockPair -> HashSet, find or create the hash
233 * set corresponding to a given basic block pair
234 *
235 * @param map the mapping to search
236 * @param b1 the first basic block in the pair
237 * @param b2 the second basic block in the pair
238 */
239 private static HashSet<Register> findOrCreateSplitSet(HashMap<BasicBlockPair, HashSet<Register>> map,
240 BasicBlock b1, BasicBlock b2) {
241 BasicBlockPair pair = new BasicBlockPair(b1, b2);
242 HashSet<Register> set = map.get(pair);
243 if (set == null) {
244 set = new HashSet<Register>(5);
245 map.put(pair, set);
246 }
247 return set;
248 }
249
250 /**
251 * Perform the transformation
252 *
253 * @param ir the governing IR
254 * @param xform a mapping from BasicBlockPair to the set of registers
255 * to split
256 */
257 private static void transform(IR ir, HashMap<BasicBlockPair, HashSet<Register>> xform) {
258 for (Map.Entry<BasicBlockPair, HashSet<Register>> entry : xform.entrySet()) {
259 BasicBlockPair bbp = entry.getKey();
260 HashSet<Register> toSplit = entry.getValue();
261
262 // we go ahead and split all edges, instead of just critical ones.
263 // we'll clean up the mess later after SSA.
264 BasicBlock target = IRTools.makeBlockOnEdge(bbp.src, bbp.dest, ir);
265 SSA.replaceBlockInPhis(bbp.dest, bbp.src, target);
266
267 for (Register r : toSplit) {
268 if (r.defList == null) continue;
269 Instruction s = null;
270 switch (r.getType()) {
271 case Register.ADDRESS_TYPE:
272 RegisterOperand lhs2 = IRTools.A(r);
273 RegisterOperand rhs2 = IRTools.A(r);
274 s = Unary.create(SPLIT, lhs2, rhs2);
275 // fix up types: only split live ranges when the type is
276 // consistent at all defs
277 TypeReference t2 = null;
278 RegisterOperandEnumeration e2 = DefUse.defs(r);
279 if (!e2.hasMoreElements()) {
280 s = null;
281 } else {
282 RegisterOperand rop2 = e2.next();
283 t2 = rop2.getType();
284 while (e2.hasMoreElements()) {
285 RegisterOperand nextOp2 = e2.next();
286 if (nextOp2.getType() != t2) {
287 s = null;
288 }
289 }
290 }
291 if (s != null) {
292 lhs2.setType(t2);
293 rhs2.setType(t2);
294 }
295 break;
296 case Register.INTEGER_TYPE:
297 RegisterOperand lhs = IRTools.I(r);
298 RegisterOperand rhs = IRTools.I(r);
299 s = Unary.create(SPLIT, lhs, rhs);
300 // fix up types: only split live ranges when the type is
301 // consistent at all defs
302 TypeReference t = null;
303 RegisterOperandEnumeration e = DefUse.defs(r);
304 if (!e.hasMoreElements()) {
305 s = null;
306 } else {
307 RegisterOperand rop = e.next();
308 t = rop.getType();
309 while (e.hasMoreElements()) {
310 RegisterOperand nextOp = e.next();
311 if (nextOp.getType() != t) {
312 s = null;
313 }
314 }
315 }
316 if (s != null) {
317 lhs.setType(t);
318 rhs.setType(t);
319 }
320 break;
321 case Register.FLOAT_TYPE:
322 s = Unary.create(SPLIT, IRTools.F(r), IRTools.F(r));
323 break;
324 case Register.DOUBLE_TYPE:
325 s = Unary.create(SPLIT, IRTools.D(r), IRTools.D(r));
326 break;
327 case Register.LONG_TYPE:
328 s = Unary.create(SPLIT, IRTools.L(r), IRTools.L(r));
329 break;
330 default:
331 // we won't split live ranges for other types.
332 s = null;
333 break;
334 }
335 if (s != null) {
336 target.prependInstruction(s);
337 }
338 }
339 }
340 }
341
342 /**
343 * A utility class to represent an edge in the CFG.
344 */
345 private static class BasicBlockPair {
346 /**
347 * The source of a control-flow edge
348 */
349 final BasicBlock src;
350
351 /**
352 * The sink of a control-flow edge
353 */
354 final BasicBlock dest;
355
356 BasicBlockPair(BasicBlock src, BasicBlock dest) {
357 this.src = src;
358 this.dest = dest;
359 }
360
361 static int nextHash = 0;
362 int myHash = ++nextHash;
363
364 public int hashCode() {
365 return myHash;
366 }
367
368 public boolean equals(Object o) {
369 if (!(o instanceof BasicBlockPair)) return false;
370 BasicBlockPair p = (BasicBlockPair) o;
371 return (src.equals(p.src) && dest.equals(p.dest));
372 }
373
374 public String toString() {
375 return "<" + src + "," + dest + ">";
376 }
377 }
378 }
379
380 /**
381 * This class sets up the IR state prior to entering SSA.
382 */
383 private static class RenamePreparation extends CompilerPhase {
384
385 /**
386 * Return this instance of this phase. This phase contains no
387 * per-compilation instance fields.
388 * @param ir not used
389 * @return this
390 */
391 public CompilerPhase newExecution(IR ir) {
392 return this;
393 }
394
395 public final boolean shouldPerform(OptOptions options) {
396 return options.SSA_LIVE_RANGE_SPLITTING;
397 }
398
399 public final String getName() {
400 return "Rename Preparation";
401 }
402
403 /**
404 * register in the IR the SSA properties we need for simple scalar
405 * renaming
406 */
407 public final void perform(IR ir) {
408 ir.desiredSSAOptions = new SSAOptions();
409 ir.desiredSSAOptions.setScalarsOnly(true);
410 ir.desiredSSAOptions.setBackwards(false);
411 ir.desiredSSAOptions.setInsertUsePhis(false);
412 }
413 }
414 }