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 */
013package org.jikesrvm.compilers.opt.regalloc;
014
015import java.util.Enumeration;
016import java.util.HashMap;
017import java.util.Iterator;
018import java.util.Map;
019
020import org.jikesrvm.VM;
021import org.jikesrvm.compilers.opt.OptimizingCompilerException;
022import org.jikesrvm.compilers.opt.ir.GenericPhysicalRegisterSet;
023import org.jikesrvm.compilers.opt.ir.IR;
024import org.jikesrvm.compilers.opt.ir.Instruction;
025import org.jikesrvm.compilers.opt.ir.Register;
026import org.jikesrvm.compilers.opt.util.GraphEdge;
027import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
028
029/**
030 * "Active set" for linear scan register allocation.
031 * This version is maintained sorted in order of increasing
032 * live interval end point.
033 */
034final class ActiveSet extends IncreasingEndMappedIntervalSet {
035  /** Support for Set serialization */
036  static final long serialVersionUID = 2570397490575294294L;
037  /**
038   * Governing ir
039   */
040  private final IR ir;
041
042  private final RegisterAllocatorState regAllocState;
043
044  /**
045   * Manager of spill locations;
046   */
047  private final SpillLocationManager spillManager;
048
049  /**
050   * An object to help estimate spill costs
051   */
052  private final transient SpillCostEstimator spillCost;
053
054  /**
055   * Have we spilled anything?
056   */
057  private boolean spilled;
058
059  ActiveSet(IR ir, SpillLocationManager sm, SpillCostEstimator cost) {
060    super();
061    spilled = false;
062    this.ir = ir;
063    this.regAllocState = ir.MIRInfo.regAllocState;
064    this.spillManager = sm;
065    this.spillCost = cost;
066  }
067
068  boolean spilledSomething() {
069    return spilled;
070  }
071
072  /**
073   *  For each new basic interval, we scan the list of active basic
074   *  intervals in order of increasing end point.  We remove any "expired"
075   *  intervals - those
076   *  intervals that no longer overlap the new interval because their
077   *  end point precedes the new interval's start point - and makes the
078   *  corresponding register available for allocation
079   *
080   *  @param newInterval the new interval
081   */
082  void expireOldIntervals(BasicInterval newInterval) {
083
084    for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
085      MappedBasicInterval bi = (MappedBasicInterval) e.next();
086
087      // break out of the loop when we reach an interval that is still
088      // alive
089      int newStart = newInterval.getBegin();
090      if (bi.endsAfter(newStart)) break;
091
092      if (LinearScan.VERBOSE_DEBUG) System.out.println("Expire " + bi);
093
094      // note that the bi interval no longer is live
095      freeInterval(bi);
096
097      // remove bi from the active set
098      e.remove();
099
100    }
101  }
102
103  void freeInterval(MappedBasicInterval bi) {
104    CompoundInterval container = bi.container;
105    Register r = container.getRegister();
106
107    if (r.isPhysical()) {
108      r.deallocateRegister();
109      return;
110    }
111
112    if (container.isSpilled(regAllocState)) {
113      // free the spill location iff this is the last interval in the
114      // compound interval.
115      BasicInterval last = container.last();
116      if (last.sameRange(bi)) {
117        spillManager.freeInterval(container.getSpillInterval());
118      }
119    } else {
120      // free the assigned register
121      if (VM.VerifyAssertions) VM._assert(container.getAssignment(regAllocState).isAllocated());
122      container.getAssignment(regAllocState).deallocateRegister();
123    }
124
125  }
126
127  void allocate(BasicInterval newInterval, CompoundInterval container) {
128
129    if (LinearScan.DEBUG) {
130      System.out.println("Allocate " + newInterval + " " + container.getRegister());
131    }
132
133    Register r = container.getRegister();
134
135    if (container.isSpilled(regAllocState)) {
136      // We previously decided to spill the compound interval.  No further
137      // action is needed.
138      if (LinearScan.VERBOSE_DEBUG) System.out.println("Previously spilled " + container);
139    } else {
140      if (container.isAssigned(regAllocState)) {
141        // The compound interval was previously assigned to a physical
142        // register.
143        Register phys = container.getAssignment(regAllocState);
144        if (!currentlyActive(phys)) {
145          // The assignment of newInterval to phys is still OK.
146          // Update the live ranges of phys to include the new basic
147          // interval
148          if (LinearScan.VERBOSE_DEBUG) {
149            System.out.println("Previously assigned to " +
150                               phys +
151                               " " +
152                               container +
153                               " phys interval " +
154                               regAllocState.getInterval(phys));
155          }
156          updatePhysicalInterval(phys, newInterval);
157          if (LinearScan.VERBOSE_DEBUG) {
158            System.out.println(" now phys interval " + regAllocState.getInterval(phys));
159          }
160          // Mark the physical register as currently allocated
161          phys.allocateRegister();
162        } else {
163          // The previous assignment is not OK, since the physical
164          // register is now in use elsewhere.
165          if (LinearScan.DEBUG) {
166            System.out.println("Previously assigned, " + phys + " " + container);
167          }
168          // first look and see if there's another free register for
169          // container.
170          if (LinearScan.VERBOSE_DEBUG) System.out.println("Looking for free register");
171          Register freeR = findAvailableRegister(container);
172          if (LinearScan.VERBOSE_DEBUG) System.out.println("Free register? " + freeR);
173
174          if (freeR == null) {
175            // Did not find a free register to assign.  So, spill one of
176            // the two intervals concurrently allocated to phys.
177
178            CompoundInterval currentAssignment = getCurrentInterval(phys);
179            // choose which of the two intervals to spill
180            double costA = spillCost.getCost(container.getRegister());
181            double costB = spillCost.getCost(currentAssignment.getRegister());
182            if (LinearScan.VERBOSE_DEBUG) {
183              System.out.println("Current assignment " + currentAssignment + " cost " + costB);
184            }
185            if (LinearScan.VERBOSE_DEBUG) {
186              System.out.println("Cost of spilling" + container + " cost " + costA);
187            }
188            CompoundInterval toSpill = (costA < costB) ? container : currentAssignment;
189            // spill it.
190            Register p = toSpill.getAssignment(regAllocState);
191            toSpill.spill(spillManager, regAllocState);
192            spilled = true;
193            if (LinearScan.VERBOSE_DEBUG) {
194              System.out.println("Spilled " + toSpill + " from " + p);
195            }
196            CompoundInterval physInterval = regAllocState.getInterval(p);
197            physInterval.removeAll(toSpill);
198            if (LinearScan.VERBOSE_DEBUG) System.out.println("  after spill phys" + regAllocState.getInterval(p));
199            if (toSpill != container) updatePhysicalInterval(p, newInterval);
200            if (LinearScan.VERBOSE_DEBUG) {
201              System.out.println(" now phys interval " + regAllocState.getInterval(p));
202            }
203          } else {
204            // found a free register for container! use it!
205            if (LinearScan.DEBUG) {
206              System.out.println("Switch container " + container + "from " + phys + " to " + freeR);
207            }
208            CompoundInterval physInterval = regAllocState.getInterval(phys);
209            if (LinearScan.DEBUG) {
210              System.out.println("Before switch phys interval" + physInterval);
211            }
212            physInterval.removeAll(container);
213            if (LinearScan.DEBUG) {
214              System.out.println("Intervals of " + phys + " now " + physInterval);
215            }
216
217            container.assign(freeR);
218            updatePhysicalInterval(freeR, container, newInterval);
219            if (LinearScan.VERBOSE_DEBUG) {
220              System.out.println("Intervals of " + freeR + " now " + regAllocState.getInterval(freeR));
221            }
222            // mark the free register found as currently allocated.
223            freeR.allocateRegister();
224          }
225        }
226      } else {
227        // This is the first attempt to allocate the compound interval.
228        // Attempt to find a free physical register for this interval.
229        Register phys = findAvailableRegister(r);
230        if (phys != null) {
231          // Found a free register.  Perform the register assignment.
232          container.assign(phys);
233          if (LinearScan.DEBUG) {
234            System.out.println("First allocation " + phys + " " + container);
235          }
236          updatePhysicalInterval(phys, newInterval);
237          if (LinearScan.VERBOSE_DEBUG) System.out.println("  now phys" + regAllocState.getInterval(phys));
238          // Mark the physical register as currently allocated.
239          phys.allocateRegister();
240        } else {
241          // Could not find a free physical register.  Some member of the
242          // active set must be spilled.  Choose a spill candidate.
243          CompoundInterval spillCandidate = getSpillCandidate(container);
244          if (VM.VerifyAssertions) {
245            VM._assert(!spillCandidate.isSpilled(regAllocState));
246            VM._assert((spillCandidate.getRegister().getType() == r.getType()) ||
247                       (spillCandidate.getRegister().isNatural() && r.isNatural()));
248            VM._assert(!ir.stackManager.getRestrictions().mustNotSpill(spillCandidate.getRegister()));
249            if (spillCandidate.getAssignment(regAllocState) != null) {
250              VM._assert(!ir.stackManager.getRestrictions().
251                  isForbidden(r, spillCandidate.getAssignment(regAllocState)));
252            }
253          }
254          if (spillCandidate != container) {
255            // spill a previously allocated interval.
256            phys = spillCandidate.getAssignment(regAllocState);
257            spillCandidate.spill(spillManager, regAllocState);
258            spilled = true;
259            if (LinearScan.VERBOSE_DEBUG) {
260              System.out.println("Spilled " + spillCandidate + " from " + phys);
261            }
262            CompoundInterval physInterval = regAllocState.getInterval(phys);
263            if (LinearScan.VERBOSE_DEBUG) {
264              System.out.println(" assigned " + phys + " to " + container);
265            }
266            physInterval.removeAll(spillCandidate);
267            if (LinearScan.VERBOSE_DEBUG) System.out.println("  after spill phys" + regAllocState.getInterval(phys));
268            updatePhysicalInterval(phys, newInterval);
269            if (LinearScan.VERBOSE_DEBUG) {
270              System.out.println(" now phys interval " + regAllocState.getInterval(phys));
271            }
272            container.assign(phys);
273          } else {
274            // spill the new interval.
275            if (LinearScan.VERBOSE_DEBUG) System.out.println("spilled " + container);
276            container.spill(spillManager, regAllocState);
277            spilled = true;
278          }
279        }
280      }
281    }
282  }
283
284  /**
285   * Updates the interval representing the allocations of a physical
286   * register p to include a new interval i.
287   *
288   * @param p a physical register
289   * @param i the new interval
290   */
291  private void updatePhysicalInterval(Register p, BasicInterval i) {
292    // Get a representation of the intervals already assigned to p.
293    CompoundInterval physInterval = regAllocState.getInterval(p);
294    if (physInterval == null) {
295      // no interval yet.  create one.
296      regAllocState.setInterval(p, new CompoundInterval(i, p));
297    } else {
298      // incorporate i into the set of intervals assigned to p
299      CompoundInterval ci = new CompoundInterval(i, p);
300      if (VM.VerifyAssertions) VM._assert(!ci.intersects(physInterval));
301      physInterval.addAll(ci);
302    }
303  }
304
305  /**
306   * Update the interval representing the allocations of a physical
307   * register p to include a new compound interval c.  Include only
308   * those basic intervals in c up to and including basic interval stop.
309   *
310   * @param p a physical register
311   * @param c the new interval
312   * @param stop the last interval to be included
313   */
314  private void updatePhysicalInterval(Register p, CompoundInterval c, BasicInterval stop) {
315    // Get a representation of the intervals already assigned to p.
316    CompoundInterval physInterval = regAllocState.getInterval(p);
317    if (physInterval == null) {
318      // no interval yet.  create one.
319      regAllocState.setInterval(p, c.copy(p, stop));
320    } else {
321      // incorporate c into the set of intervals assigned to p
322      if (VM.VerifyAssertions) VM._assert(!c.intersects(physInterval));
323      // copy to a new BasicInterval so "equals" will work as expected,
324      // since "stop" may be a MappedBasicInterval.
325      stop = new BasicInterval(stop.getBegin(), stop.getEnd());
326      physInterval.addNonIntersectingInterval(c, stop);
327    }
328  }
329
330  /**
331   * @param r a physical register
332   * @return whether the particular physical register is currently allocated to an
333   * interval in the active set
334   */
335  boolean currentlyActive(Register r) {
336    for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
337      MappedBasicInterval i = (MappedBasicInterval) e.next();
338      CompoundInterval container = i.container;
339      if (regAllocState.getMapping(container.getRegister()) == r) {
340        return true;
341      }
342    }
343    return false;
344  }
345
346  /**
347   * @param r a physical register
348   * @return the interval that the physical register is allocated to
349   * @throws OptimizingCompilerException if the register is not currently
350   *  allocated to any interval
351   */
352  CompoundInterval getCurrentInterval(Register r) {
353    for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
354      MappedBasicInterval i = (MappedBasicInterval) e.next();
355      CompoundInterval container = i.container;
356      if (regAllocState.getMapping(container.getRegister()) == r) {
357        return container;
358      }
359    }
360    OptimizingCompilerException.UNREACHABLE("getCurrentInterval", "Not Currently Active ", r.toString());
361    return null;
362  }
363
364  /**
365   * @param ci interval to allocate
366   * @return a free physical register to allocate to the compound
367   * interval, {@code null} if no free physical register is found
368   */
369  Register findAvailableRegister(CompoundInterval ci) {
370
371    if (ir.options.FREQ_FOCUS_EFFORT && ci.isInfrequent()) {
372      // don't bother trying to find an available register
373      return null;
374    }
375
376    Register r = ci.getRegister();
377    GenericRegisterRestrictions restrict = ir.stackManager.getRestrictions();
378
379    // first attempt to allocate to the preferred register
380    if (ir.options.REGALLOC_COALESCE_MOVES) {
381      Register p = getPhysicalPreference(ci);
382      if (p != null) {
383        if (LinearScan.DEBUG_COALESCE) {
384          System.out.println("REGISTER PREFERENCE " + ci + " " + p);
385        }
386        return p;
387      }
388    }
389
390    GenericPhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
391    int type = GenericPhysicalRegisterSet.getPhysicalRegisterType(r);
392
393    // next attempt to allocate to a volatile
394    if (!restrict.allVolatilesForbidden(r)) {
395      for (Enumeration<Register> e = phys.enumerateVolatiles(type); e.hasMoreElements();) {
396        Register p = e.nextElement();
397        if (allocateToPhysical(ci, p)) {
398          return p;
399        }
400      }
401    }
402
403    // next attempt to allocate to a Nonvolatile.  we allocate the
404    // novolatiles backwards.
405    for (Enumeration<Register> e = phys.enumerateNonvolatilesBackwards(type); e.hasMoreElements();) {
406      Register p = e.nextElement();
407      if (allocateToPhysical(ci, p)) {
408        return p;
409      }
410    }
411
412    // no allocation succeeded.
413    return null;
414  }
415
416  /**
417   * @param symb symbolic register to allocate
418   * @return a free physical register to allocate to the symbolic
419   * register, {@code null} if no free physical register is found
420   */
421  Register findAvailableRegister(Register symb) {
422
423    GenericRegisterRestrictions restrict = ir.stackManager.getRestrictions();
424
425    // first attempt to allocate to the preferred register
426    if (ir.options.REGALLOC_COALESCE_MOVES) {
427      Register p = getPhysicalPreference(symb);
428      if (p != null) {
429        if (LinearScan.DEBUG_COALESCE) {
430          System.out.println("REGISTER PREFERENCE " + symb + " " + p);
431        }
432        return p;
433      }
434    }
435
436    GenericPhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
437    int type = GenericPhysicalRegisterSet.getPhysicalRegisterType(symb);
438
439    // next attempt to allocate to a volatile
440    if (!restrict.allVolatilesForbidden(symb)) {
441      for (Enumeration<Register> e = phys.enumerateVolatiles(type); e.hasMoreElements();) {
442        Register p = e.nextElement();
443        if (allocateNewSymbolicToPhysical(symb, p)) {
444          return p;
445        }
446      }
447    }
448
449    // next attempt to allocate to a Nonvolatile.  we allocate the
450    // novolatiles backwards.
451    for (Enumeration<Register> e = phys.enumerateNonvolatilesBackwards(type); e.hasMoreElements();) {
452      Register p = e.nextElement();
453      if (allocateNewSymbolicToPhysical(symb, p)) {
454        return p;
455      }
456    }
457
458    // no allocation succeeded.
459    return null;
460  }
461
462  /**
463   * Given the current state of the register allocator, compute the
464   * available physical register to which a symbolic register has the
465   * highest preference.
466   *
467   * @param r the symbolic register in question.
468   * @return the preferred register, {@code null} if no preference found.
469   */
470  private Register getPhysicalPreference(Register r) {
471    // a mapping from Register to Integer
472    // (physical register to weight);
473    HashMap<Register, Integer> map = new HashMap<Register, Integer>();
474
475    CoalesceGraph graph = ir.stackManager.getPreferences().getGraph();
476    SpaceEffGraphNode node = graph.findNode(r);
477
478    // Return null if no affinities.
479    if (node == null) return null;
480
481    // walk through all in edges of the node, searching for affinity
482    for (Enumeration<GraphEdge> in = node.inEdges(); in.hasMoreElements();) {
483      CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
484      CoalesceGraph.Node src = (CoalesceGraph.Node) edge.from();
485      Register neighbor = src.getRegister();
486      if (neighbor.isSymbolic()) {
487        // if r is assigned to a physical register r2, treat the
488        // affinity as an affinity for r2
489        Register r2 = regAllocState.getMapping(r);
490        if (r2 != null && r2.isPhysical()) {
491          neighbor = r2;
492        }
493      }
494      if (neighbor.isPhysical()) {
495        // if this is a candidate interval, update its weight
496        if (allocateNewSymbolicToPhysical(r, neighbor)) {
497          int w = edge.getWeight();
498          Integer oldW = map.get(neighbor);
499          if (oldW == null) {
500            map.put(neighbor, w);
501          } else {
502            map.put(neighbor, oldW + w);
503          }
504          break;
505        }
506      }
507    }
508    // walk through all out edges of the node, searching for affinity
509    for (Enumeration<GraphEdge> in = node.outEdges(); in.hasMoreElements();) {
510      CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
511      CoalesceGraph.Node dest = (CoalesceGraph.Node) edge.to();
512      Register neighbor = dest.getRegister();
513      if (neighbor.isSymbolic()) {
514        // if r is assigned to a physical register r2, treat the
515        // affinity as an affinity for r2
516        Register r2 = regAllocState.getMapping(r);
517        if (r2 != null && r2.isPhysical()) {
518          neighbor = r2;
519        }
520      }
521      if (neighbor.isPhysical()) {
522        // if this is a candidate interval, update its weight
523        if (allocateNewSymbolicToPhysical(r, neighbor)) {
524          int w = edge.getWeight();
525          Integer oldW = map.get(neighbor);
526          if (oldW == null) {
527            map.put(neighbor, w);
528          } else {
529            map.put(neighbor, oldW + w);
530          }
531          break;
532        }
533      }
534    }
535    // OK, now find the highest preference.
536    Register result = null;
537    int weight = -1;
538    for (Map.Entry<Register, Integer> entry : map.entrySet()) {
539      int w = entry.getValue();
540      if (w > weight) {
541        weight = w;
542        result = entry.getKey();
543      }
544    }
545    return result;
546  }
547
548  /**
549   * Given the current state of the register allocator, compute the
550   * available physical register to which an interval has the highest
551   * preference.
552   *
553   * @param ci the interval in question
554   * @return the preferred register, {@code null} if no preference found
555   */
556  private Register getPhysicalPreference(CompoundInterval ci) {
557    // a mapping from Register to Integer
558    // (physical register to weight);
559    HashMap<Register, Integer> map = new HashMap<Register, Integer>();
560    Register r = ci.getRegister();
561
562    CoalesceGraph graph = ir.stackManager.getPreferences().getGraph();
563    SpaceEffGraphNode node = graph.findNode(r);
564
565    // Return null if no affinities.
566    if (node == null) return null;
567
568    // walk through all in edges of the node, searching for affinity
569    for (Enumeration<GraphEdge> in = node.inEdges(); in.hasMoreElements();) {
570      CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
571      CoalesceGraph.Node src = (CoalesceGraph.Node) edge.from();
572      Register neighbor = src.getRegister();
573      if (neighbor.isSymbolic()) {
574        // if r is assigned to a physical register r2, treat the
575        // affinity as an affinity for r2
576        Register r2 = regAllocState.getMapping(r);
577        if (r2 != null && r2.isPhysical()) {
578          neighbor = r2;
579        }
580      }
581      if (neighbor.isPhysical()) {
582        // if this is a candidate interval, update its weight
583        if (allocateToPhysical(ci, neighbor)) {
584          int w = edge.getWeight();
585          Integer oldW = map.get(neighbor);
586          if (oldW == null) {
587            map.put(neighbor, w);
588          } else {
589            map.put(neighbor, oldW + w);
590          }
591          break;
592        }
593      }
594    }
595    // walk through all out edges of the node, searching for affinity
596    for (Enumeration<GraphEdge> in = node.outEdges(); in.hasMoreElements();) {
597      CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
598      CoalesceGraph.Node dest = (CoalesceGraph.Node) edge.to();
599      Register neighbor = dest.getRegister();
600      if (neighbor.isSymbolic()) {
601        // if r is assigned to a physical register r2, treat the
602        // affinity as an affinity for r2
603        Register r2 = regAllocState.getMapping(r);
604        if (r2 != null && r2.isPhysical()) {
605          neighbor = r2;
606        }
607      }
608      if (neighbor.isPhysical()) {
609        // if this is a candidate interval, update its weight
610        if (allocateToPhysical(ci, neighbor)) {
611          int w = edge.getWeight();
612          Integer oldW = map.get(neighbor);
613          if (oldW == null) {
614            map.put(neighbor, w);
615          } else {
616            map.put(neighbor, oldW + w);
617          }
618          break;
619        }
620      }
621    }
622    // OK, now find the highest preference.
623    Register result = null;
624    int weight = -1;
625    for (Map.Entry<Register, Integer> entry : map.entrySet()) {
626      int w = entry.getValue();
627      if (w > weight) {
628        weight = w;
629        result = entry.getKey();
630      }
631    }
632    return result;
633  }
634
635  /**
636   * Checks whether it's ok to allocate an interval to a physical
637   * register.
638   *
639   * @param i the interval to allocate
640   * @param p the physical register
641   * @return {@code true} if it's ok to allocate the interval to the
642   *  given physical register, {@code false} otherwise
643   */
644  private boolean allocateToPhysical(CompoundInterval i, Register p) {
645    GenericRegisterRestrictions restrict = ir.stackManager.getRestrictions();
646    Register r = i.getRegister();
647    GenericPhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
648    if (p != null && !phys.isAllocatable(p)) return false;
649
650    if (LinearScan.VERBOSE_DEBUG && p != null) {
651      if (!p.isAvailable()) System.out.println("unavailable " + i + p);
652      if (restrict.isForbidden(r, p)) System.out.println("forbidden" + i + p);
653    }
654
655    if ((p != null) && p.isAvailable() && !restrict.isForbidden(r, p)) {
656      CompoundInterval pInterval = regAllocState.getInterval(p);
657      if (pInterval == null) {
658        // no assignment to p yet
659        return true;
660      } else {
661        if (!i.intersects(pInterval)) {
662          return true;
663        }
664      }
665    }
666    return false;
667  }
668
669  /**
670   * NOTE: This routine assumes we're processing the first interval of
671   * register symb; so p.isAvailable() is the key information needed.
672   *
673   * @param symb the symbolic register
674   * @param p the physical register
675   * @return whether it's ok to allocate the symbolic register to the physical
676   * register
677   */
678  private boolean allocateNewSymbolicToPhysical(Register symb, Register p) {
679    GenericRegisterRestrictions restrict = ir.stackManager.getRestrictions();
680    GenericPhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
681    if (p != null && !phys.isAllocatable(p)) return false;
682
683    if (LinearScan.VERBOSE_DEBUG && p != null) {
684      if (!p.isAvailable()) System.out.println("unavailable " + symb + p);
685      if (restrict.isForbidden(symb, p)) System.out.println("forbidden" + symb + p);
686    }
687
688    return (p != null) && p.isAvailable() && !restrict.isForbidden(symb, p);
689  }
690
691  /**
692   * @param newInterval a new interval
693   * @return an interval that can be spilled. This may be chosen from the
694   * existing candidates and the new interval
695   */
696  private CompoundInterval getSpillCandidate(CompoundInterval newInterval) {
697    if (LinearScan.VERBOSE_DEBUG) System.out.println("GetSpillCandidate from " + this);
698
699    if (ir.options.FREQ_FOCUS_EFFORT && newInterval.isInfrequent()) {
700      // if it's legal to spill this infrequent interval, then just do so!
701      // don't spend any more effort.
702      GenericRegisterRestrictions restrict = ir.stackManager.getRestrictions();
703      if (!restrict.mustNotSpill(newInterval.getRegister())) {
704        return newInterval;
705      }
706    }
707
708    return spillMinUnitCost(newInterval);
709  }
710
711  /**
712   * Chooses the interval with the minimal unit cost (defined as the number
713   * of defs and uses).
714   *
715   * @param newInterval a new interval
716   * @return the interval with the minimal number of defs and uses
717   */
718  private CompoundInterval spillMinUnitCost(CompoundInterval newInterval) {
719    if (LinearScan.VERBOSE_DEBUG) {
720      System.out.println(" interval caused a spill: " + newInterval);
721    }
722    GenericRegisterRestrictions restrict = ir.stackManager.getRestrictions();
723    Register r = newInterval.getRegister();
724    double minCost = spillCost.getCost(r);
725    if (LinearScan.VERBOSE_DEBUG) {
726      System.out.println(" spill cost: " + r + " " + minCost);
727    }
728    CompoundInterval result = newInterval;
729    if (restrict.mustNotSpill(result.getRegister())) {
730      if (LinearScan.VERBOSE_DEBUG) {
731        System.out.println(" must not spill: " + result.getRegister());
732      }
733      result = null;
734      minCost = Double.MAX_VALUE;
735    }
736    for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
737      MappedBasicInterval b = (MappedBasicInterval) e.next();
738      CompoundInterval i = b.container;
739      Register newR = i.getRegister();
740      if (LinearScan.VERBOSE_DEBUG) {
741        if (i.isSpilled(regAllocState)) {
742          System.out.println(" not candidate, already spilled: " + newR);
743        }
744        if ((r.getType() != newR.getType()) || (r.isNatural() && newR.isNatural())) {
745          System.out.println(" not candidate, type mismatch : " + r.getType() + " " + newR + " " + newR.getType());
746        }
747        if (restrict.mustNotSpill(newR)) {
748          System.out.println(" not candidate, must not spill: " + newR);
749        }
750      }
751      if (!newR.isPhysical() &&
752          !i.isSpilled(regAllocState) &&
753          (r.getType() == newR.getType() || (r.isNatural() && newR.isNatural())) &&
754          !restrict.mustNotSpill(newR)) {
755        // Found a potential spill interval. Check if the assignment
756        // works if we spill this interval.
757        if (checkAssignmentIfSpilled(newInterval, i)) {
758          double iCost = spillCost.getCost(newR);
759          if (LinearScan.VERBOSE_DEBUG) {
760            System.out.println(" potential candidate " + i + " cost " + iCost);
761          }
762          if (iCost < minCost) {
763            if (LinearScan.VERBOSE_DEBUG) System.out.println(" best candidate so far" + i);
764            minCost = iCost;
765            result = i;
766          }
767        } else {
768          if (LinearScan.VERBOSE_DEBUG) {
769            System.out.println(" not a candidate, insufficient range: " + i);
770          }
771        }
772      }
773    }
774    if (VM.VerifyAssertions) {
775      VM._assert(result != null);
776    }
777    return result;
778  }
779
780  /**
781   * Checks if it would be possible to assign an interval to the physical
782   * register of another interval if that other interval were spilled.
783   *
784   * @param spill the interval that's a candidate for spilling
785   * @param i the interval that we want to assign to the register of the spill interval
786   * @return {@code true} if the allocation would fit,  {@code false} otherwise
787   */
788  private boolean checkAssignmentIfSpilled(CompoundInterval i, CompoundInterval spill) {
789    Register r = spill.getAssignment(regAllocState);
790
791    GenericRegisterRestrictions restrict = ir.stackManager.getRestrictions();
792    if (restrict.isForbidden(i.getRegister(), r)) return false;
793
794    // 1. Speculatively simulate the spill.
795    CompoundInterval rI = regAllocState.getInterval(r);
796    CompoundInterval cache = rI.removeIntervalsAndCache(spill);
797
798    // 2. Check the fit.
799    boolean result = !rI.intersects(i);
800
801    // 3. Undo the simulated spill.
802    rI.addAll(cache);
803
804    return result;
805  }
806
807  /**
808   * Finds a basic interval for a register so that the interval contains
809   * the instruction.
810   *
811   * @param r the register whose interval is desired
812   * @param s the reference instruction
813   * @return {@code null} if there is no basic interval for the given register
814   *  that contains the instruction, the interval otherwise. If there are
815   *  multiple intervals, the first one will be returned.
816   */
817  BasicInterval getBasicInterval(Register r, Instruction s) {
818    CompoundInterval c = regAllocState.getInterval(r);
819    if (c == null) return null;
820    return c.getBasicInterval(regAllocState, s);
821  }
822
823}