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