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.ssa;
014
015import java.util.HashSet;
016import java.util.Iterator;
017
018
019/**
020 * This class represents a congruence class for
021 * global value numbering.
022 */
023final class GVCongruenceClass implements Iterable<ValueGraphVertex> {
024  /**
025   * A label representing a property of this congruence class.
026   */
027  private final Object label;
028  /**
029   * A value number representing this congruence class.
030   */
031  private final int valueNumber;
032  /**
033   * How many vertices in this congruence class represent parameters?
034   */
035  private int nParameter;
036  /**
037   * The set of vertices in this congruence class
038   */
039  private final HashSet<ValueGraphVertex> vertices;
040
041  /**
042   * A representative of the congruence class
043   *   - saves having to find one
044   */
045  private ValueGraphVertex representativeV;
046
047  /**
048   * Create a congruence class with a given representative value number
049   * and label.
050   * @param     valueNumber the value number of the class
051   * @param     label the label of the class
052   */
053  GVCongruenceClass(int valueNumber, Object label) {
054    this.valueNumber = valueNumber;
055    this.label = label;
056    vertices = new HashSet<ValueGraphVertex>(1);
057  }
058
059  public Object getLabel() {
060    return label;
061  }
062
063  public int getValueNumber() {
064    return valueNumber;
065  }
066
067  /**
068   * Do any of the vertices in this set represent a parameter?
069   * <p> TODO: for efficiency, keep this information incrementally
070   * @return true or false
071   */
072  public boolean containsParameter() {
073    return (nParameter > 0);
074  }
075
076  /**
077   * Add a vertex to this congruence class.
078   * @param v the vertex to add
079   */
080  public void addVertex(ValueGraphVertex v) {
081    if (vertices.add(v)) {
082      if (v.representsParameter()) {
083        nParameter++;
084      }
085      if (representativeV == null) {
086        representativeV = v;
087      }
088    }
089  }
090
091  /**
092   * Remove a vertex from this congruence class.
093   * @param v the vertex to remove
094   */
095  public void removeVertex(ValueGraphVertex v) {
096    if (vertices.remove(v)) {
097      if (v.representsParameter()) {
098        nParameter--;
099      }
100      if (representativeV == v) {
101        // Try to find an alternate representative
102        representativeV = vertices.iterator().next();
103      }
104    }
105  }
106
107  /**
108   * Return a representative vertex for this congruence class.
109   * @return a representative vertex for this congruence class.
110   */
111  public ValueGraphVertex getRepresentative() {
112    return representativeV;
113  }
114
115  /**
116   * Return an iterator over the vertices in this congruence class
117   * @return an iterator over the vertices in this congruence class
118   */
119  @Override
120  public Iterator<ValueGraphVertex> iterator() {
121    return vertices.iterator();
122  }
123
124  /**
125   * Return the number of vertices in this class
126   * @return the number of vertices in this class
127   */
128  public int size() {
129    return vertices.size();
130  }
131}