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.runtimesupport;
014    
015    import java.util.Enumeration;
016    import org.jikesrvm.VM;
017    import org.jikesrvm.compilers.opt.inlining.CallSiteTree;
018    import org.jikesrvm.compilers.opt.inlining.CallSiteTreeNode;
019    import org.jikesrvm.compilers.opt.util.TreeNode;
020    import org.vmmagic.pragma.Interruptible;
021    import org.vmmagic.pragma.Uninterruptible;
022    
023    /**
024     * Suppose the following inlining actions have been taken
025     * <pre>
026     * (&lt;callerMID, bcIndex, calleeMID&gt;):
027     *
028     * &lt;A, 12, B&gt;, &lt;A,14,C&gt;, &lt;A,16,D&gt;, &lt; B,3,E&gt;, &lt; B,5,F &gt;, &lt;C,10,G&gt;, &lt;G,20,H&gt;,
029     * &lt;H,30,I&gt;
030     * </pre>
031     *
032     * Then the <code>OptEncodedCallSiteTree </code> would be:
033     *
034     * <pre>
035     * -1, A, -2, 12, B, 14, C, 16, D, -6, 3, E, 5, F, -9, 10, G, -2, 20 H -2 30 I
036     * </pre>
037     */
038    @Uninterruptible
039    public abstract class OptEncodedCallSiteTree {
040    
041      public static int getMethodID(int entryOffset, int[] encoding) {
042        return encoding[entryOffset + 1];
043      }
044    
045      static void setMethodID(int entryOffset, int[] encoding, int methodID) {
046        encoding[entryOffset + 1] = methodID;
047      }
048    
049      public static int getByteCodeOffset(int entryOffset, int[] encoding) {
050        return encoding[entryOffset];
051      }
052    
053      @Interruptible
054      public static int[] getEncoding(CallSiteTree tree) {
055        int size = 0;
056        if (tree.isEmpty()) {
057          return null;
058        } else {
059          Enumeration<TreeNode> e = tree.elements();
060          while (e.hasMoreElements()) {
061            TreeNode x = e.nextElement();
062            if (x.getLeftChild() == null) {
063              size += 2;
064            } else {
065              size += 3;
066            }
067          }
068          int[] encoding = new int[size];
069          getEncoding((CallSiteTreeNode) tree.getRoot(), 0, -1, encoding);
070          return encoding;
071        }
072      }
073    
074      @Interruptible
075      static int getEncoding(CallSiteTreeNode current, int offset, int parent, int[] encoding) {
076        int i = offset;
077        if (parent != -1) {
078          encoding[i++] = parent - offset;
079        }
080        CallSiteTreeNode x = current;
081        int j = i;
082        while (x != null) {
083          x.encodedOffset = j;
084          int byteCodeIndex = x.callSite.bcIndex;
085          encoding[j++] = (byteCodeIndex >= 0) ? byteCodeIndex : -1;
086          encoding[j++] = x.callSite.getMethod().getId();
087          x = (CallSiteTreeNode) x.getRightSibling();
088        }
089        x = current;
090        int thisParent = i;
091        while (x != null) {
092          if (x.getLeftChild() != null) {
093            j = getEncoding((CallSiteTreeNode) x.getLeftChild(), j, thisParent, encoding);
094          }
095          thisParent += 2;
096          x = (CallSiteTreeNode) x.getRightSibling();
097        }
098        return j;
099      }
100    
101      public static int getParent(int index, int[] encodedTree) {
102        while (index >= 0 && encodedTree[index] >= -1) {
103          index--;
104        }
105        if (index < 0) {
106          return -1;
107        } else {
108          return index + encodedTree[index];
109        }
110      }
111    
112      public static boolean edgePresent(int desiredCaller, int desiredBCIndex, int desiredCallee, int[] encoding) {
113        if (encoding.length < 3) return false; // Why are we creating an encoding with no real data???
114        if (VM.VerifyAssertions) {
115          VM._assert(encoding[0] == -1);
116          VM._assert(encoding[2] == -2);
117        }
118        int idx = 3;
119        int parent = encoding[1];
120        while (idx < encoding.length) {
121          if (encoding[idx] < 0) {
122            parent = idx + encoding[idx];
123            idx++;
124          }
125          if (parent == desiredCaller) {
126            if (encoding[idx] == desiredBCIndex && encoding[idx + 1] == desiredCallee) {
127              return true;
128            }
129          }
130          idx += 2;
131        }
132        return false;
133      }
134    }
135    
136    
137