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