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.inlining;
014    
015    import 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     */
034    public 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    }