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.HashMap;
016
017import org.jikesrvm.compilers.opt.ir.Register;
018import org.jikesrvm.compilers.opt.util.GraphEdge;
019import org.jikesrvm.compilers.opt.util.SpaceEffGraph;
020import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
021import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
022import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode.GraphEdgeEnumeration;
023
024/**
025 * This class represents a graph, where
026 * <ul>
027 *   <li> the nodes are registers
028 *   <li> the edge weights represent affinities between registers.
029 * </ul>
030 * <p>
031 * This graph is used to drive coalescing during register allocation.
032 * <p>
033 * Implementation: this is meant to be an undirected graph.  By
034 * convention, we enforce that the register with the lower number is the
035 * source of an edge.
036 */
037class CoalesceGraph extends SpaceEffGraph {
038
039  /**
040   * Mapping register -&gt; Node
041   */
042  final HashMap<Register, Node> nodeMap = new HashMap<Register, Node>();
043
044  private Node findOrCreateNode(Register r) {
045    Node n = nodeMap.get(r);
046    if (n == null) {
047      n = new Node(r);
048      nodeMap.put(r, n);
049      addGraphNode(n);
050    }
051    return n;
052  }
053
054  Node findNode(Register r) {
055    return nodeMap.get(r);
056  }
057
058  private Edge findOrCreateEdge(Node src, Node dest) {
059    Edge edge = null;
060    for (GraphEdgeEnumeration<GraphEdge> e = src.outEdges(); e.hasMoreElements();) {
061       Edge candidate = (Edge)e.next();
062      if (candidate.toNode() == dest) {
063        edge = candidate;
064        break;
065      }
066    }
067    if (edge == null) {
068      edge = new Edge(src, dest);
069      addGraphEdge(edge);
070    }
071    return edge;
072  }
073
074  void addAffinity(int w, Register r1, Register r2) {
075    Node src;
076    Node dest;
077    if (r1.getNumber() == r2.getNumber()) return;
078
079    // the register with the smaller number is the source of the edge.
080    if (r1.getNumber() < r2.getNumber()) {
081      src = findOrCreateNode(r1);
082      dest = findOrCreateNode(r2);
083    } else {
084      src = findOrCreateNode(r2);
085      dest = findOrCreateNode(r1);
086    }
087
088    Edge edge = findOrCreateEdge(src, dest);
089
090    edge.addWeight(w);
091  }
092
093  static class Node extends SpaceEffGraphNode {
094    final Register r;
095
096    Node(Register r) {
097      this.r = r;
098    }
099
100    Register getRegister() {
101      return r;
102    }
103  }
104
105  static class Edge extends SpaceEffGraphEdge {
106    private int w;
107
108    Edge(Node src, Node dest) {
109      super(src, dest);
110    }
111
112    void addWeight(int x) {
113      w += x;
114    }
115
116    int getWeight() {
117      return w;
118    }
119  }
120}