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.regalloc;
014
015 import java.util.HashMap;
016
017 import org.jikesrvm.compilers.opt.ir.Register;
018 import org.jikesrvm.compilers.opt.util.GraphEdge;
019 import org.jikesrvm.compilers.opt.util.SpaceEffGraph;
020 import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
021 import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
022 import 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 */
037 class CoalesceGraph extends SpaceEffGraph {
038
039 /**
040 * Mapping register -> Node
041 */
042 final HashMap<Register, Node> nodeMap = new HashMap<Register, Node>();
043
044 /**
045 * find or create a node in the graph corresponding to a register.
046 */
047 private Node findOrCreateNode(Register r) {
048 Node n = nodeMap.get(r);
049 if (n == null) {
050 n = new Node(r);
051 nodeMap.put(r, n);
052 addGraphNode(n);
053 }
054 return n;
055 }
056
057 /**
058 * Find the node corresponding to a regsiter.
059 */
060 Node findNode(Register r) {
061 return nodeMap.get(r);
062 }
063
064 /**
065 * find or create an edge in the graph
066 */
067 private Edge findOrCreateEdge(Node src, Node dest) {
068 Edge edge = null;
069 for (GraphEdgeEnumeration<GraphEdge> e = src.outEdges(); e.hasMoreElements();) {
070 Edge candidate = (Edge)e.next();
071 if (candidate.toNode() == dest) {
072 edge = candidate;
073 break;
074 }
075 }
076 if (edge == null) {
077 edge = new Edge(src, dest);
078 addGraphEdge(edge);
079 }
080 return edge;
081 }
082
083 /**
084 * Add an affinity of weight w between registers r1 and r2
085 */
086 void addAffinity(int w, Register r1, Register r2) {
087 Node src;
088 Node dest;
089 if (r1.getNumber() == r2.getNumber()) return;
090
091 // the register with the smaller number is the source of the edge.
092 if (r1.getNumber() < r2.getNumber()) {
093 src = findOrCreateNode(r1);
094 dest = findOrCreateNode(r2);
095 } else {
096 src = findOrCreateNode(r2);
097 dest = findOrCreateNode(r1);
098 }
099
100 Edge edge = findOrCreateEdge(src, dest);
101
102 edge.addWeight(w);
103 }
104
105 static class Node extends SpaceEffGraphNode {
106 final Register r;
107
108 Node(Register r) {
109 this.r = r;
110 }
111
112 Register getRegister() {
113 return r;
114 }
115 }
116
117 static class Edge extends SpaceEffGraphEdge {
118 private int w;
119
120 Edge(Node src, Node dest) {
121 super(src, dest);
122 }
123
124 void addWeight(int x) {
125 w += x;
126 }
127
128 int getWeight() {
129 return w;
130 }
131 }
132 }