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.ssa;
014    
015    import java.util.HashSet;
016    import java.util.Iterator;
017    
018    
019    /**
020     * This class represents a congruence class for
021     * global value numbering.
022     */
023    final 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    }