1 /*
2 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
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
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "opto/addnode.hpp"
28 #include "opto/cfgnode.hpp"
29 #include "opto/machnode.hpp"
30 #include "opto/matcher.hpp"
31 #include "opto/mathexactnode.hpp"
32 #include "opto/subnode.hpp"
33
34 MathExactNode::MathExactNode(Node* ctrl, Node* n1, Node* n2) : MultiNode(3) {
35 init_req(0, ctrl);
36 init_req(1, n1);
37 init_req(2, n2);
38 }
39
40 BoolNode* MathExactNode::bool_node() const {
41 Node* flags = flags_node();
42 BoolNode* boolnode = flags->unique_out()->as_Bool();
43 assert(boolnode != NULL, "must have BoolNode");
44 return boolnode;
45 }
46
47 IfNode* MathExactNode::if_node() const {
48 BoolNode* boolnode = bool_node();
49 IfNode* ifnode = boolnode->unique_out()->as_If();
50 assert(ifnode != NULL, "must have IfNode");
51 return ifnode;
52 }
53
54 Node* MathExactNode::control_node() const {
55 IfNode* ifnode = if_node();
56 return ifnode->in(0);
57 }
58
59 Node* MathExactNode::non_throwing_branch() const {
60 IfNode* ifnode = if_node();
61 if (bool_node()->_test._test == BoolTest::overflow) {
62 return ifnode->proj_out(0);
63 }
64 return ifnode->proj_out(1);
65 }
66
67 MathExactNode::MathExactNode(Node* ctrl, Node* n1) : MultiNode(2) {
68 init_req(0, ctrl);
69 init_req(1, n1);
70 }
71
72 // If the MathExactNode won't overflow we have to replace the
73 // FlagsProjNode and ProjNode that is generated by the MathExactNode
74 Node* MathExactNode::no_overflow(PhaseGVN* phase, Node* new_result) {
75 PhaseIterGVN* igvn = phase->is_IterGVN();
76 if (igvn) {
77 ProjNode* result = result_node();
78 ProjNode* flags = flags_node();
79
80 if (result != NULL) {
81 igvn->replace_node(result, new_result);
82 }
83
84 if (flags != NULL) {
85 BoolNode* boolnode = bool_node();
86 switch (boolnode->_test._test) {
87 case BoolTest::overflow:
88 // if the check is for overflow - never taken
89 igvn->replace_node(boolnode, phase->intcon(0));
90 break;
91 case BoolTest::no_overflow:
92 // if the check is for no overflow - always taken
93 igvn->replace_node(boolnode, phase->intcon(1));
94 break;
95 default:
96 fatal("Unexpected value of BoolTest");
97 break;
98 }
99 flags->del_req(0);
100 }
101 }
102 return new_result;
103 }
104
105 bool MathExactNode::is_MathExactOpcode(int opcode) {
106 switch (opcode) {
107 case Op_AddExactI:
108 case Op_AddExactL:
109 case Op_SubExactI:
110 case Op_SubExactL:
111 case Op_MulExactI:
112 case Op_MulExactL:
113 case Op_NegExactI:
114 case Op_NegExactL:
115 return true;
116 default:
117 return false;
118 }
119 }
120
121 Node* MathExactINode::match(const ProjNode* proj, const Matcher* m) {
122 uint ideal_reg = proj->ideal_reg();
123 RegMask rm;
124 if (proj->_con == result_proj_node) {
125 rm = m->mathExactI_result_proj_mask();
126 } else {
127 assert(proj->_con == flags_proj_node, "must be result or flags");
128 assert(ideal_reg == Op_RegFlags, "sanity");
129 rm = m->mathExactI_flags_proj_mask();
130 }
131 return new (m->C) MachProjNode(this, proj->_con, rm, ideal_reg);
132 }
133
134 Node* MathExactLNode::match(const ProjNode* proj, const Matcher* m) {
135 uint ideal_reg = proj->ideal_reg();
136 RegMask rm;
137 if (proj->_con == result_proj_node) {
138 rm = m->mathExactL_result_proj_mask();
139 } else {
140 assert(proj->_con == flags_proj_node, "must be result or flags");
141 assert(ideal_reg == Op_RegFlags, "sanity");
142 rm = m->mathExactI_flags_proj_mask();
143 }
144 return new (m->C) MachProjNode(this, proj->_con, rm, ideal_reg);
145 }
146
147 Node* AddExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
148 Node* arg1 = in(1);
149 Node* arg2 = in(2);
150
151 const Type* type1 = phase->type(arg1);
152 const Type* type2 = phase->type(arg2);
153
154 if (type1 != Type::TOP && type1->singleton() &&
155 type2 != Type::TOP && type2->singleton()) {
156 jint val1 = arg1->get_int();
157 jint val2 = arg2->get_int();
158 jint result = val1 + val2;
159 // Hacker's Delight 2-12 Overflow if both arguments have the opposite sign of the result
160 if ( (((val1 ^ result) & (val2 ^ result)) >= 0)) {
161 Node* con_result = ConINode::make(phase->C, result);
162 return no_overflow(phase, con_result);
163 }
164 return NULL;
165 }
166
167 if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) { // (Add 0 x) == x
168 Node* add_result = new (phase->C) AddINode(arg1, arg2);
169 return no_overflow(phase, add_result);
170 }
171
172 if (type2->singleton()) {
173 return NULL; // no change - keep constant on the right
174 }
175
176 if (type1->singleton()) {
177 // Make it x + Constant - move constant to the right
178 swap_edges(1, 2);
179 return this;
180 }
181
182 if (arg2->is_Load()) {
183 return NULL; // no change - keep load on the right
184 }
185
186 if (arg1->is_Load()) {
187 // Make it x + Load - move load to the right
188 swap_edges(1, 2);
189 return this;
190 }
191
192 if (arg1->_idx > arg2->_idx) {
193 // Sort the edges
194 swap_edges(1, 2);
195 return this;
196 }
197
198 return NULL;
199 }
200
201 Node* AddExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
202 Node* arg1 = in(1);
203 Node* arg2 = in(2);
204
205 const Type* type1 = phase->type(arg1);
206 const Type* type2 = phase->type(arg2);
207
208 if (type1 != Type::TOP && type1->singleton() &&
209 type2 != Type::TOP && type2->singleton()) {
210 jlong val1 = arg1->get_long();
211 jlong val2 = arg2->get_long();
212 jlong result = val1 + val2;
213 // Hacker's Delight 2-12 Overflow if both arguments have the opposite sign of the result
214 if ( (((val1 ^ result) & (val2 ^ result)) >= 0)) {
215 Node* con_result = ConLNode::make(phase->C, result);
216 return no_overflow(phase, con_result);
217 }
218 return NULL;
219 }
220
221 if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) { // (Add 0 x) == x
222 Node* add_result = new (phase->C) AddLNode(arg1, arg2);
223 return no_overflow(phase, add_result);
224 }
225
226 if (type2->singleton()) {
227 return NULL; // no change - keep constant on the right
228 }
229
230 if (type1->singleton()) {
231 // Make it x + Constant - move constant to the right
232 swap_edges(1, 2);
233 return this;
234 }
235
236 if (arg2->is_Load()) {
237 return NULL; // no change - keep load on the right
238 }
239
240 if (arg1->is_Load()) {
241 // Make it x + Load - move load to the right
242 swap_edges(1, 2);
243 return this;
244 }
245
246 if (arg1->_idx > arg2->_idx) {
247 // Sort the edges
248 swap_edges(1, 2);
249 return this;
250 }
251
252 return NULL;
253 }
254
255 Node* SubExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
256 Node* arg1 = in(1);
257 Node* arg2 = in(2);
258
259 const Type* type1 = phase->type(arg1);
260 const Type* type2 = phase->type(arg2);
261
262 if (type1 != Type::TOP && type1->singleton() &&
263 type2 != Type::TOP && type2->singleton()) {
264 jint val1 = arg1->get_int();
265 jint val2 = arg2->get_int();
266 jint result = val1 - val2;
267
268 // Hacker's Delight 2-12 Overflow iff the arguments have different signs and
269 // the sign of the result is different than the sign of arg1
270 if (((val1 ^ val2) & (val1 ^ result)) >= 0) {
271 Node* con_result = ConINode::make(phase->C, result);
272 return no_overflow(phase, con_result);
273 }
274 return NULL;
275 }
276
277 if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) {
278 // Sub with zero is the same as add with zero
279 Node* add_result = new (phase->C) AddINode(arg1, arg2);
280 return no_overflow(phase, add_result);
281 }
282
283 return NULL;
284 }
285
286 Node* SubExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
287 Node* arg1 = in(1);
288 Node* arg2 = in(2);
289
290 const Type* type1 = phase->type(arg1);
291 const Type* type2 = phase->type(arg2);
292
293 if (type1 != Type::TOP && type1->singleton() &&
294 type2 != Type::TOP && type2->singleton()) {
295 jlong val1 = arg1->get_long();
296 jlong val2 = arg2->get_long();
297 jlong result = val1 - val2;
298
299 // Hacker's Delight 2-12 Overflow iff the arguments have different signs and
300 // the sign of the result is different than the sign of arg1
301 if (((val1 ^ val2) & (val1 ^ result)) >= 0) {
302 Node* con_result = ConLNode::make(phase->C, result);
303 return no_overflow(phase, con_result);
304 }
305 return NULL;
306 }
307
308 if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) {
309 // Sub with zero is the same as add with zero
310 Node* add_result = new (phase->C) AddLNode(arg1, arg2);
311 return no_overflow(phase, add_result);
312 }
313
314 return NULL;
315 }
316
317 Node* NegExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
318 Node *arg = in(1);
319
320 const Type* type = phase->type(arg);
321 if (type != Type::TOP && type->singleton()) {
322 jint value = arg->get_int();
323 if (value != min_jint) {
324 Node* neg_result = ConINode::make(phase->C, -value);
325 return no_overflow(phase, neg_result);
326 }
327 }
328 return NULL;
329 }
330
331 Node* NegExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
332 Node *arg = in(1);
333
334 const Type* type = phase->type(arg);
335 if (type != Type::TOP && type->singleton()) {
336 jlong value = arg->get_long();
337 if (value != min_jlong) {
338 Node* neg_result = ConLNode::make(phase->C, -value);
339 return no_overflow(phase, neg_result);
340 }
341 }
342 return NULL;
343 }
344
345 Node* MulExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
346 Node* arg1 = in(1);
347 Node* arg2 = in(2);
348
349 const Type* type1 = phase->type(arg1);
350 const Type* type2 = phase->type(arg2);
351
352 if (type1 != Type::TOP && type1->singleton() &&
353 type2 != Type::TOP && type2->singleton()) {
354 jint val1 = arg1->get_int();
355 jint val2 = arg2->get_int();
356 jlong result = (jlong) val1 * (jlong) val2;
357 if ((jint) result == result) {
358 // no overflow
359 Node* mul_result = ConINode::make(phase->C, result);
360 return no_overflow(phase, mul_result);
361 }
362 }
363
364 if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) {
365 return no_overflow(phase, ConINode::make(phase->C, 0));
366 }
367
368 if (type1 == TypeInt::ONE) {
369 Node* mul_result = new (phase->C) AddINode(arg2, phase->intcon(0));
370 return no_overflow(phase, mul_result);
371 }
372 if (type2 == TypeInt::ONE) {
373 Node* mul_result = new (phase->C) AddINode(arg1, phase->intcon(0));
374 return no_overflow(phase, mul_result);
375 }
376
377 if (type1 == TypeInt::MINUS_1) {
378 return new (phase->C) NegExactINode(NULL, arg2);
379 }
380
381 if (type2 == TypeInt::MINUS_1) {
382 return new (phase->C) NegExactINode(NULL, arg1);
383 }
384
385 return NULL;
386 }
387
388 Node* MulExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
389 Node* arg1 = in(1);
390 Node* arg2 = in(2);
391
392 const Type* type1 = phase->type(arg1);
393 const Type* type2 = phase->type(arg2);
394
395 if (type1 != Type::TOP && type1->singleton() &&
396 type2 != Type::TOP && type2->singleton()) {
397 jlong val1 = arg1->get_long();
398 jlong val2 = arg2->get_long();
399
400 jlong result = val1 * val2;
401 jlong ax = (val1 < 0 ? -val1 : val1);
402 jlong ay = (val2 < 0 ? -val2 : val2);
403
404 bool overflow = false;
405 if ((ax | ay) & CONST64(0xFFFFFFFF00000000)) {
406 // potential overflow if any bit in upper 32 bits are set
407 if ((val1 == min_jlong && val2 == -1) || (val2 == min_jlong && val1 == -1)) {
408 // -1 * Long.MIN_VALUE will overflow
409 overflow = true;
410 } else if (val2 != 0 && (result / val2 != val1)) {
411 overflow = true;
412 }
413 }
414
415 if (!overflow) {
416 Node* mul_result = ConLNode::make(phase->C, result);
417 return no_overflow(phase, mul_result);
418 }
419 }
420
421 if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) {
422 return no_overflow(phase, ConLNode::make(phase->C, 0));
423 }
424
425 if (type1 == TypeLong::ONE) {
426 Node* mul_result = new (phase->C) AddLNode(arg2, phase->longcon(0));
427 return no_overflow(phase, mul_result);
428 }
429 if (type2 == TypeLong::ONE) {
430 Node* mul_result = new (phase->C) AddLNode(arg1, phase->longcon(0));
431 return no_overflow(phase, mul_result);
432 }
433
434 if (type1 == TypeLong::MINUS_1) {
435 return new (phase->C) NegExactLNode(NULL, arg2);
436 }
437
438 if (type2 == TypeLong::MINUS_1) {
439 return new (phase->C) NegExactLNode(NULL, arg1);
440 }
441
442 return NULL;
443 }
444