6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 package org.graalvm.compiler.core.amd64; 25 26 import jdk.vm.ci.meta.JavaConstant; 27 28 import org.graalvm.compiler.core.common.NumUtil; 29 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale; 30 import org.graalvm.compiler.core.common.type.IntegerStamp; 31 import org.graalvm.compiler.debug.DebugContext; 32 import org.graalvm.compiler.nodes.ValueNode; 33 import org.graalvm.compiler.nodes.calc.AddNode; 34 import org.graalvm.compiler.nodes.calc.LeftShiftNode; 35 import org.graalvm.compiler.nodes.calc.ZeroExtendNode; 36 import org.graalvm.compiler.nodes.memory.address.AddressNode; 37 import org.graalvm.compiler.phases.common.AddressLoweringPhase.AddressLowering; 38 39 public class AMD64AddressLowering extends AddressLowering { 40 41 @Override 42 public AddressNode lower(ValueNode address) { 43 return lower(address, null); 44 } 45 46 @Override 47 public AddressNode lower(ValueNode base, ValueNode offset) { 48 AMD64AddressNode ret = new AMD64AddressNode(base, offset); 49 boolean changed; 50 do { 51 changed = improve(base.getDebug(), ret); 52 } while (changed); 53 return base.graph().unique(ret); 54 } 55 56 /** 57 * @param debug 58 */ 59 protected boolean improve(DebugContext debug, AMD64AddressNode ret) { 60 ValueNode newBase = improveInput(ret, ret.getBase(), 0); 61 if (newBase != ret.getBase()) { 62 ret.setBase(newBase); 63 return true; 64 } 65 66 ValueNode newIdx = improveInput(ret, ret.getIndex(), ret.getScale().log2); 67 if (newIdx != ret.getIndex()) { 68 ret.setIndex(newIdx); 69 return true; 70 } 71 72 if (ret.getIndex() instanceof LeftShiftNode) { 73 LeftShiftNode shift = (LeftShiftNode) ret.getIndex(); 74 if (shift.getY().isConstant()) { 75 int amount = ret.getScale().log2 + shift.getY().asJavaConstant().asInt(); 76 Scale scale = Scale.fromShift(amount); 77 if (scale != null) { 78 ret.setIndex(shift.getX()); 79 ret.setScale(scale); 80 return true; 81 } 82 } 83 } 84 85 if (ret.getScale() == Scale.Times1) { 86 if (ret.getBase() == null || ret.getIndex() == null) { 87 if (ret.getBase() instanceof AddNode) { 88 AddNode add = (AddNode) ret.getBase(); 89 ret.setBase(add.getX()); 90 ret.setIndex(add.getY()); 91 return true; 92 } else if (ret.getIndex() instanceof AddNode) { 93 AddNode add = (AddNode) ret.getIndex(); 94 ret.setBase(add.getX()); 95 ret.setIndex(add.getY()); 96 return true; 97 } 98 } 99 100 if (ret.getBase() instanceof LeftShiftNode && !(ret.getIndex() instanceof LeftShiftNode)) { 101 ValueNode tmp = ret.getBase(); 102 ret.setBase(ret.getIndex()); 103 ret.setIndex(tmp); 104 return true; 105 } 106 } 107 108 return false; 109 } 110 111 private static ValueNode improveInput(AMD64AddressNode address, ValueNode node, int shift) { 112 if (node == null) { 113 return null; 114 } 115 116 JavaConstant c = node.asJavaConstant(); 117 if (c != null) { 118 return improveConstDisp(address, node, c, null, shift); 119 } else { 120 if (node.stamp() instanceof IntegerStamp && ((IntegerStamp) node.stamp()).getBits() == 64) { 121 if (node instanceof ZeroExtendNode) { 122 if (((ZeroExtendNode) node).getInputBits() == 32) { 123 /* 124 * We can just swallow a zero-extend from 32 bit to 64 bit because the upper 125 * half of the register will always be zero. 126 */ 127 return ((ZeroExtendNode) node).getValue(); 128 } 129 } else if (node instanceof AddNode) { 130 AddNode add = (AddNode) node; 131 if (add.getX().isConstant()) { 132 return improveConstDisp(address, node, add.getX().asJavaConstant(), add.getY(), shift); 133 } else if (add.getY().isConstant()) { 134 return improveConstDisp(address, node, add.getY().asJavaConstant(), add.getX(), shift); 135 } 136 } 137 } 138 } 139 140 return node; 141 } 142 143 private static ValueNode improveConstDisp(AMD64AddressNode address, ValueNode original, JavaConstant c, ValueNode other, int shift) { 144 if (c.getJavaKind().isNumericInteger()) { 145 long disp = address.getDisplacement(); 146 disp += c.asLong() << shift; 147 if (NumUtil.isInt(disp)) { 148 address.setDisplacement((int) disp); 149 return other; 150 } 151 } 152 return original; 153 } 154 } | 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 package org.graalvm.compiler.core.amd64; 25 26 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale; 27 import org.graalvm.compiler.core.common.NumUtil; 28 import org.graalvm.compiler.core.common.type.IntegerStamp; 29 import org.graalvm.compiler.debug.DebugContext; 30 import org.graalvm.compiler.nodes.StructuredGraph; 31 import org.graalvm.compiler.nodes.ValueNode; 32 import org.graalvm.compiler.nodes.calc.AddNode; 33 import org.graalvm.compiler.nodes.calc.LeftShiftNode; 34 import org.graalvm.compiler.nodes.calc.NegateNode; 35 import org.graalvm.compiler.nodes.calc.ZeroExtendNode; 36 import org.graalvm.compiler.nodes.memory.address.AddressNode; 37 import org.graalvm.compiler.phases.common.AddressLoweringPhase.AddressLowering; 38 39 import jdk.vm.ci.meta.JavaConstant; 40 41 public class AMD64AddressLowering extends AddressLowering { 42 @Override 43 public AddressNode lower(ValueNode address) { 44 return lower(address, null); 45 } 46 47 @Override 48 public AddressNode lower(ValueNode base, ValueNode offset) { 49 AMD64AddressNode ret = new AMD64AddressNode(base, offset); 50 StructuredGraph graph = base.graph(); 51 52 boolean changed; 53 do { 54 changed = improve(graph, base.getDebug(), ret, false, false); 55 } while (changed); 56 57 return graph.unique(ret); 58 } 59 60 /** 61 * Tries to optimize addresses so that they match the AMD64-specific addressing mode better 62 * (base + index * scale + displacement). 63 * 64 * @param graph the current graph 65 * @param debug the current debug context 66 * @param ret the address that should be optimized 67 * @param isBaseNegated determines if the address base is negated. if so, all values that are 68 * extracted from the base will be negated as well 69 * @param isIndexNegated determines if the index is negated. if so, all values that are 70 * extracted from the index will be negated as well 71 * @return true if the address was modified 72 */ 73 protected boolean improve(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean isBaseNegated, boolean isIndexNegated) { 74 ValueNode newBase = improveInput(ret, ret.getBase(), 0, isBaseNegated); 75 if (newBase != ret.getBase()) { 76 ret.setBase(newBase); 77 return true; 78 } 79 80 ValueNode newIdx = improveInput(ret, ret.getIndex(), ret.getScale().log2, isIndexNegated); 81 if (newIdx != ret.getIndex()) { 82 ret.setIndex(newIdx); 83 return true; 84 } 85 86 if (ret.getIndex() instanceof LeftShiftNode) { 87 LeftShiftNode shift = (LeftShiftNode) ret.getIndex(); 88 if (shift.getY().isConstant()) { 89 int amount = ret.getScale().log2 + shift.getY().asJavaConstant().asInt(); 90 Scale scale = Scale.fromShift(amount); 91 if (scale != null) { 92 ret.setIndex(shift.getX()); 93 ret.setScale(scale); 94 return true; 95 } 96 } 97 } 98 99 if (ret.getScale() == Scale.Times1) { 100 if (ret.getIndex() == null && ret.getBase() instanceof AddNode) { 101 AddNode add = (AddNode) ret.getBase(); 102 ret.setBase(add.getX()); 103 ret.setIndex(considerNegation(graph, add.getY(), isBaseNegated)); 104 return true; 105 } else if (ret.getBase() == null && ret.getIndex() instanceof AddNode) { 106 AddNode add = (AddNode) ret.getIndex(); 107 ret.setBase(considerNegation(graph, add.getX(), isIndexNegated)); 108 ret.setIndex(add.getY()); 109 return true; 110 } 111 112 if (ret.getBase() instanceof LeftShiftNode && !(ret.getIndex() instanceof LeftShiftNode)) { 113 ValueNode tmp = ret.getBase(); 114 ret.setBase(considerNegation(graph, ret.getIndex(), isIndexNegated != isBaseNegated)); 115 ret.setIndex(considerNegation(graph, tmp, isIndexNegated != isBaseNegated)); 116 return true; 117 } 118 } 119 120 return improveNegation(graph, debug, ret, isBaseNegated, isIndexNegated); 121 } 122 123 private boolean improveNegation(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean originalBaseNegated, boolean originalIndexNegated) { 124 boolean baseNegated = originalBaseNegated; 125 boolean indexNegated = originalIndexNegated; 126 127 ValueNode originalBase = ret.getBase(); 128 ValueNode originalIndex = ret.getIndex(); 129 130 if (ret.getBase() instanceof NegateNode) { 131 NegateNode negate = (NegateNode) ret.getBase(); 132 ret.setBase(negate.getValue()); 133 baseNegated = !baseNegated; 134 } 135 136 if (ret.getIndex() instanceof NegateNode) { 137 NegateNode negate = (NegateNode) ret.getIndex(); 138 ret.setIndex(negate.getValue()); 139 indexNegated = !indexNegated; 140 } 141 142 if (baseNegated != originalBaseNegated || indexNegated != originalIndexNegated) { 143 ValueNode base = ret.getBase(); 144 ValueNode index = ret.getIndex(); 145 146 boolean improved = improve(graph, debug, ret, baseNegated, indexNegated); 147 if (baseNegated != originalBaseNegated) { 148 if (base == ret.getBase()) { 149 ret.setBase(originalBase); 150 } else if (ret.getBase() != null) { 151 ret.setBase(graph.maybeAddOrUnique(NegateNode.create(ret.getBase()))); 152 } 153 } 154 155 if (indexNegated != originalIndexNegated) { 156 if (index == ret.getIndex()) { 157 ret.setIndex(originalIndex); 158 } else if (ret.getIndex() != null) { 159 ret.setIndex(graph.maybeAddOrUnique(NegateNode.create(ret.getIndex()))); 160 } 161 } 162 return improved; 163 } else { 164 assert ret.getBase() == originalBase && ret.getIndex() == originalIndex; 165 } 166 return false; 167 } 168 169 private static ValueNode considerNegation(StructuredGraph graph, ValueNode value, boolean negate) { 170 if (negate && value != null) { 171 return graph.maybeAddOrUnique(NegateNode.create(value)); 172 } 173 return value; 174 } 175 176 private ValueNode improveInput(AMD64AddressNode address, ValueNode node, int shift, boolean negateExtractedDisplacement) { 177 if (node == null) { 178 return null; 179 } 180 181 JavaConstant c = node.asJavaConstant(); 182 if (c != null) { 183 return improveConstDisp(address, node, c, null, shift, negateExtractedDisplacement); 184 } else { 185 if (node.stamp() instanceof IntegerStamp) { 186 if (node instanceof ZeroExtendNode && (((ZeroExtendNode) node).getInputBits() == 32)) { 187 /* 188 * we can't just swallow all zero-extends as we might encounter something like 189 * the following: ZeroExtend(Add(negativeValue, positiveValue)). 190 * 191 * if we swallow the zero-extend in this case and subsequently optimize the add, 192 * we might end up with a negative value that has less than 64 bits in base or 193 * index. such a value would require sign extension instead of zero-extension 194 * but the backend can only do zero-extension. if we ever want to optimize that 195 * further, we would also need to be careful about over-/underflows. 196 * 197 * furthermore, we also can't swallow zero-extends with less than 32 bits as 198 * most of these values are immediately sign-extended to 32 bit by the backend 199 * (therefore, the subsequent implicit zero-extension to 64 bit won't do what we 200 * expect). 201 */ 202 ValueNode value = ((ZeroExtendNode) node).getValue(); 203 if (!mightBeOptimized(value)) { 204 // if the value is not optimized further by the address lowering, then we 205 // can safely rely on the backend doing the implicitly zero-extension. 206 return value; 207 } 208 } 209 210 if (node instanceof AddNode) { 211 AddNode add = (AddNode) node; 212 if (add.getX().isConstant()) { 213 return improveConstDisp(address, node, add.getX().asJavaConstant(), add.getY(), shift, negateExtractedDisplacement); 214 } else if (add.getY().isConstant()) { 215 return improveConstDisp(address, node, add.getY().asJavaConstant(), add.getX(), shift, negateExtractedDisplacement); 216 } 217 } 218 } 219 } 220 221 return node; 222 } 223 224 /** 225 * This method returns true for all nodes that might be optimized by the address lowering. 226 */ 227 protected boolean mightBeOptimized(ValueNode value) { 228 return value instanceof AddNode || value instanceof LeftShiftNode || value instanceof NegateNode || value instanceof ZeroExtendNode; 229 } 230 231 private static ValueNode improveConstDisp(AMD64AddressNode address, ValueNode original, JavaConstant c, ValueNode other, int shift, boolean negateExtractedDisplacement) { 232 if (c.getJavaKind().isNumericInteger()) { 233 long delta = c.asLong() << shift; 234 if (updateDisplacement(address, delta, negateExtractedDisplacement)) { 235 return other; 236 } 237 } 238 return original; 239 } 240 241 protected static boolean updateDisplacement(AMD64AddressNode address, long displacementDelta, boolean negateDelta) { 242 long sign = negateDelta ? -1 : 1; 243 long disp = address.getDisplacement() + displacementDelta * sign; 244 if (NumUtil.isInt(disp)) { 245 address.setDisplacement((int) disp); 246 return true; 247 } 248 return false; 249 } 250 } |