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