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