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.runtimesupport;
014
015import java.util.Enumeration;
016import org.jikesrvm.VM;
017import org.jikesrvm.compilers.opt.inlining.CallSiteTree;
018import org.jikesrvm.compilers.opt.inlining.CallSiteTreeNode;
019import org.jikesrvm.compilers.opt.util.TreeNode;
020import org.vmmagic.pragma.Interruptible;
021import 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
039public 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}