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.inlining;
014
015import org.jikesrvm.compilers.opt.util.Tree;
016
017/**
018 *  This class represents the set of inlined method calls that are
019 * contained within a single method code body.  The tree is consists
020 * of nodes each of which contains an InlineSequence object
021 * representing an inlined method call.  The tree is rooted at the
022 * inline sequence object representing the top level method, and the
023 * inlined calls appear as children of that root, and so on
024 * recursively.  These trees are used to construct the persistent
025 * encoding of inlining information, stored in the
026 * OptMachineCodeMap.
027 *
028 *
029 * @see InlineSequence
030 * @see CallSiteTreeNode
031 * @see org.jikesrvm.compilers.opt.runtimesupport.OptEncodedCallSiteTree
032 * @see org.jikesrvm.compilers.opt.runtimesupport.OptMachineCodeMap
033 */
034public class CallSiteTree extends Tree {
035
036  /**
037   * Given an existing call site tree representing a method, add a new
038   * inlined call to it.
039   * @param seq a call to add to the call site tree
040   * @return the call site tree node corresponding to the new call site
041   */
042  public CallSiteTreeNode addLocation(InlineSequence seq) {
043    if (seq.caller == null) {
044      CallSiteTreeNode x = (CallSiteTreeNode) getRoot();
045      if (x == null) {
046        x = new CallSiteTreeNode(seq);
047        setRoot(x);
048      }
049      return x;
050    } else {
051      CallSiteTreeNode node = addLocation(seq.caller);
052      CallSiteTreeNode x = (CallSiteTreeNode) node.getLeftChild();
053      while (x != null) {
054        if (x.callSite == seq) {
055          return x;
056        }
057        x = (CallSiteTreeNode) x.getRightSibling();
058      }
059      CallSiteTreeNode xx = new CallSiteTreeNode(seq);
060      node.addChild(xx);
061      return xx;
062    }
063  }
064
065  /**
066   * Given an inline sequence representing an inlined call site, find
067   * the corresponding call site tree node.
068   * @param seq an inlined call site
069   * @return the corresponding call site tree node
070   */
071  public CallSiteTreeNode find(InlineSequence seq) {
072    if (seq.caller == null) {
073      return (CallSiteTreeNode) getRoot();
074    } else {
075      CallSiteTreeNode parent = find(seq.caller);
076      CallSiteTreeNode x = (CallSiteTreeNode) parent.getLeftChild();
077      while (x != null) {
078        if (x.callSite == seq) {
079          return x;
080        }
081        x = (CallSiteTreeNode) x.getRightSibling();
082      }
083      return null;
084    }
085  }
086}