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.lir2mir;
014
015import java.util.Enumeration;
016
017import org.jikesrvm.VM;
018import org.jikesrvm.compilers.opt.depgraph.DepGraphNode;
019import org.jikesrvm.compilers.opt.ir.BasicBlock;
020import org.jikesrvm.compilers.opt.ir.Instruction;
021import org.jikesrvm.compilers.opt.ir.IR;
022import static org.jikesrvm.compilers.opt.ir.Operators.CALL_opcode;
023import static org.jikesrvm.compilers.opt.ir.Operators.OTHER_OPERAND_opcode;
024import static org.jikesrvm.compilers.opt.ir.Operators.RETURN_opcode;
025import static org.jikesrvm.compilers.opt.ir.Operators.SYSCALL_opcode;
026import static org.jikesrvm.compilers.opt.ir.Operators.YIELDPOINT_OSR_opcode;
027import org.jikesrvm.compilers.opt.ir.operand.AddressConstantOperand;
028import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
029import org.jikesrvm.compilers.opt.ir.operand.InlinedOsrTypeInfoOperand;
030import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
031import org.jikesrvm.compilers.opt.ir.operand.LongConstantOperand;
032import org.jikesrvm.compilers.opt.ir.operand.Operand;
033import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
034
035/**
036 * This class contains code for quick and dirty instruction selection
037 * by forcing each instruction to be a tree and generating the trees in
038 * the same input as the input LIR instructions.
039 * This results in poor code quality, but can be done very quickly.
040 * The intended purpose is to reduce compile time by doing quick and
041 * dirty instruction selection for infrequently executed basic blocks.
042 *
043 * @see BURS_StateCoder
044 * @see AbstractBURS_TreeNode
045 */
046final class MinimalBURS extends BURS {
047
048  /**
049   * Create a BURS object for the given IR.
050   *
051   * @param ir the IR to translate from LIR to MIR.
052   */
053  MinimalBURS(IR ir) {
054    super(ir);
055  }
056
057  /**
058   * Build BURS trees for the basic block <code>bb</code>, label the trees, and
059   * then generate MIR instructions based on the labeling.
060   *
061   * @param bb the basic block to process
062   */
063  public void invoke(BasicBlock bb) {
064    BURS_StateCoder burs = makeCoder();
065    for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
066      Instruction s = e.nextElement();
067      AbstractBURS_TreeNode tn = buildTree(s);
068      label(tn);
069      mark(tn, /* goalnt */(byte) 1);
070      generateTree(tn, burs);
071    }
072  }
073
074  ////////////////////////////////
075  // Implementation
076  ////////////////////////////////
077
078  /**
079   * Build a BURS Tree for each Instruction.
080   * Complete BURS trees by adding leaf nodes as needed, and
081   * creating tree edges by calling insertChild1() or insertChild2()
082   * This step is also where we introduce intermediate tree nodes for
083   * any LIR instruction that has &gt; 2 "real" operands e.g., a CALL.
084   *
085   * @param s The instruction for which a tree must be built
086   * @return the root of the newly constructed tree
087   */
088  private AbstractBURS_TreeNode buildTree(Instruction s) {
089    AbstractBURS_TreeNode root = AbstractBURS_TreeNode.create(new DepGraphNode(s));
090    AbstractBURS_TreeNode cur = root;
091    for (Enumeration<Operand> uses = s.getUses(); uses.hasMoreElements();) {
092      Operand op = uses.nextElement();
093      if (op == null) continue;
094
095      // Set child = AbstractBURS_TreeNode for operand op
096      AbstractBURS_TreeNode child;
097      if (op instanceof RegisterOperand) {
098        if (op.asRegister().getRegister().isValidation()) continue;
099        child = Register;
100      } else if (op instanceof IntConstantOperand) {
101        child = new BURS_IntConstantTreeNode(((IntConstantOperand) op).value);
102      } else if (op instanceof LongConstantOperand) {
103        child = LongConstant;
104      } else if (op instanceof AddressConstantOperand) {
105        child = AddressConstant;
106      } else if (op instanceof BranchOperand && s.isCall()) {
107        child = BranchTarget;
108      } else if (op instanceof InlinedOsrTypeInfoOperand && s.isYieldPoint()) {
109        child = NullTreeNode;
110      } else {
111        continue;
112      }
113
114      // Attach child as child of cur_parent in correct position
115      if (cur.child1 == null) {
116        cur.child1 = child;
117      } else if (cur.child2 == null) {
118        cur.child2 = child;
119      } else {
120        // Create auxiliary node so as to represent
121        // a instruction with arity > 2 in a binary tree.
122        AbstractBURS_TreeNode child1 = cur.child2;
123        AbstractBURS_TreeNode aux = AbstractBURS_TreeNode.create(OTHER_OPERAND_opcode);
124        cur.child2 = aux;
125        cur = aux;
126        cur.child1 = child1;
127        cur.child2 = child;
128      }
129    }
130
131    // patch for calls & return
132    switch (s.getOpcode()) {
133      case CALL_opcode:
134      case SYSCALL_opcode:
135      case YIELDPOINT_OSR_opcode:
136        if (cur.child2 == null) {
137          cur.child2 = NullTreeNode;
138        }
139        // fall through
140      case RETURN_opcode:
141        if (cur.child1 == null) {
142          cur.child1 = NullTreeNode;
143        }
144    }
145    return root;
146  }
147
148
149
150  /**
151   * Generates code for a single tree root.
152   * @param k the root to start generation at
153   * @param burs the current BURS state
154   */
155  private void generateTree(AbstractBURS_TreeNode k, BURS_StateCoder burs) {
156    AbstractBURS_TreeNode child1 = k.child1;
157    AbstractBURS_TreeNode child2 = k.child2;
158    if (child1 != null) {
159      if (child2 != null) {
160        // k has two children; use register labeling to
161        // determine order that minimizes register pressure
162        if (k.isSuperNodeRoot()) {
163          byte act = action(k.rule(k.getNonTerminal()));
164          if ((act & BURS_StateCoder.RIGHT_CHILD_FIRST) != 0) {
165            // rule selected forces order of evaluation
166            generateTree(child2, burs);
167            generateTree(child1, burs);
168          } else {
169            generateTree(child1, burs);
170            generateTree(child2, burs);
171          }
172        } else {
173          generateTree(child1, burs);
174          generateTree(child2, burs);
175        }
176      } else {
177        generateTree(child1, burs);
178      }
179    } else if (child2 != null) {
180      generateTree(child2, burs);
181    }
182
183    if (k.isSuperNodeRoot()) {
184      int nonterminal = k.getNonTerminal();
185      int rule = k.rule(nonterminal);
186      burs.code(k, nonterminal, rule);
187      if (DEBUG) VM.sysWrite(k + " " + debug(rule) + "\n");
188    }
189  }
190}