Mercurial > hg > truffle

comparison src/share/vm/opto/mathexactnode.cpp @ 17726:085b304a1cc5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
8027754: Enable loop optimizations for loops with MathExact inside Reviewed-by: kvn, iveresov
author rbackman
date Thu, 23 Jan 2014 12:08:28 +0100
parents 59e8ad757e19
children 4ca6dc0799b6
comparison
equal deleted inserted replaced
17725:b4ce4e9eb97d 17726:085b304a1cc5
29 #include "opto/machnode.hpp" 29 #include "opto/machnode.hpp"
30 #include "opto/matcher.hpp" 30 #include "opto/matcher.hpp"
31 #include "opto/mathexactnode.hpp" 31 #include "opto/mathexactnode.hpp"
32 #include "opto/subnode.hpp" 32 #include "opto/subnode.hpp"
33 33
34 MathExactNode::MathExactNode(Node* ctrl, Node* in1) : MultiNode(2) { 34 template <typename OverflowOp>
35 init_class_id(Class_MathExact); 35 class AddHelper {
36 init_req(0, ctrl); 36 public:
37 init_req(1, in1); 37 typedef typename OverflowOp::TypeClass TypeClass;
38 } 38 typedef typename TypeClass::NativeType NativeType;
39 39
40 MathExactNode::MathExactNode(Node* ctrl, Node* in1, Node* in2) : MultiNode(3) { 40 static bool will_overflow(NativeType value1, NativeType value2) {
41 init_class_id(Class_MathExact); 41 NativeType result = value1 + value2;
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 42 // Hacker's Delight 2-12 Overflow if both arguments have the opposite sign of the result
146 if ( (((val1 ^ result) & (val2 ^ result)) >= 0)) { 43 if (((value1 ^ result) & (value2 ^ result)) >= 0) {
147 Node* con_result = ConINode::make(phase->C, result); 44 return false;
148 return no_overflow(phase, con_result); 45 }
149 } 46 return true;
150 return NULL; 47 }
151 } 48
152 49 static bool can_overflow(const Type* type1, const Type* type2) {
153 if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) { // (Add 0 x) == x 50 if (type1 == TypeClass::ZERO || type2 == TypeClass::ZERO) {
154 Node* add_result = new (phase->C) AddINode(arg1, arg2); 51 return false;
155 return no_overflow(phase, add_result); 52 }
156 } 53 return true;
157 54 }
158 if (type2->singleton()) { 55 };
159 return NULL; // no change - keep constant on the right 56
160 } 57 template <typename OverflowOp>
161 58 class SubHelper {
162 if (type1->singleton()) { 59 public:
163 // Make it x + Constant - move constant to the right 60 typedef typename OverflowOp::TypeClass TypeClass;
164 swap_edges(1, 2); 61 typedef typename TypeClass::NativeType NativeType;
165 return this; 62
166 } 63 static bool will_overflow(NativeType value1, NativeType value2) {
167 64 NativeType result = value1 - value2;
168 if (arg2->is_Load()) { 65 // hacker's delight 2-12 overflow iff the arguments have different signs and
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 66 // the sign of the result is different than the sign of arg1
256 if (((val1 ^ val2) & (val1 ^ result)) >= 0) { 67 if (((value1 ^ value2) & (value1 ^ result)) >= 0) {
257 Node* con_result = ConINode::make(phase->C, result); 68 return false;
258 return no_overflow(phase, con_result); 69 }
259 } 70 return true;
260 return NULL; 71 }
261 } 72
262 73 static bool can_overflow(const Type* type1, const Type* type2) {
263 if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) { 74 if (type2 == TypeClass::ZERO) {
264 // Sub with zero is the same as add with zero 75 return false;
265 Node* add_result = new (phase->C) AddINode(arg1, arg2); 76 }
266 return no_overflow(phase, add_result); 77 return true;
267 } 78 }
268 79 };
269 return NULL; 80
270 } 81 template <typename OverflowOp>
271 82 class MulHelper {
272 Node* SubExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) { 83 public:
273 Node* arg1 = in(1); 84 typedef typename OverflowOp::TypeClass TypeClass;
274 Node* arg2 = in(2); 85
275 86 static bool can_overflow(const Type* type1, const Type* type2) {
276 const Type* type1 = phase->type(arg1); 87 if (type1 == TypeClass::ZERO || type2 == TypeClass::ZERO) {
277 const Type* type2 = phase->type(arg2); 88 return false;
278 89 } else if (type1 == TypeClass::ONE || type2 == TypeClass::ONE) {
279 if (type1 != Type::TOP && type1->singleton() && 90 return false;
280 type2 != Type::TOP && type2->singleton()) { 91 }
281 jlong val1 = arg1->get_long(); 92 return true;
282 jlong val2 = arg2->get_long(); 93 }
283 jlong result = val1 - val2; 94 };
284 95
285 // Hacker's Delight 2-12 Overflow iff the arguments have different signs and 96 bool OverflowAddINode::will_overflow(jint v1, jint v2) const {
286 // the sign of the result is different than the sign of arg1 97 return AddHelper<OverflowAddINode>::will_overflow(v1, v2);
287 if (((val1 ^ val2) & (val1 ^ result)) >= 0) { 98 }
288 Node* con_result = ConLNode::make(phase->C, result); 99
289 return no_overflow(phase, con_result); 100 bool OverflowSubINode::will_overflow(jint v1, jint v2) const {
290 } 101 return SubHelper<OverflowSubINode>::will_overflow(v1, v2);
291 return NULL; 102 }
292 } 103
293 104 bool OverflowMulINode::will_overflow(jint v1, jint v2) const {
294 if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) { 105 jlong result = (jlong) v1 * (jlong) v2;
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) { 106 if ((jint) result == result) {
344 // no overflow 107 return false;
345 Node* mul_result = ConINode::make(phase->C, result); 108 }
346 return no_overflow(phase, mul_result); 109 return true;
347 } 110 }
348 } 111
349 112 bool OverflowAddLNode::will_overflow(jlong v1, jlong v2) const {
350 if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) { 113 return AddHelper<OverflowAddLNode>::will_overflow(v1, v2);
351 return no_overflow(phase, ConINode::make(phase->C, 0)); 114 }
352 } 115
353 116 bool OverflowSubLNode::will_overflow(jlong v1, jlong v2) const {
354 if (type1 == TypeInt::ONE) { 117 return SubHelper<OverflowSubLNode>::will_overflow(v1, v2);
355 Node* mul_result = new (phase->C) AddINode(arg2, phase->intcon(0)); 118 }
356 return no_overflow(phase, mul_result); 119
357 } 120 bool OverflowMulLNode::will_overflow(jlong val1, jlong val2) const {
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; 121 jlong result = val1 * val2;
387 jlong ax = (val1 < 0 ? -val1 : val1); 122 jlong ax = (val1 < 0 ? -val1 : val1);
388 jlong ay = (val2 < 0 ? -val2 : val2); 123 jlong ay = (val2 < 0 ? -val2 : val2);
389 124
390 bool overflow = false; 125 bool overflow = false;
396 } else if (val2 != 0 && (result / val2 != val1)) { 131 } else if (val2 != 0 && (result / val2 != val1)) {
397 overflow = true; 132 overflow = true;
398 } 133 }
399 } 134 }
400 135
401 if (!overflow) { 136 return overflow;
402 Node* mul_result = ConLNode::make(phase->C, result); 137 }
403 return no_overflow(phase, mul_result); 138
404 } 139 bool OverflowAddINode::can_overflow(const Type* t1, const Type* t2) const {
405 } 140 return AddHelper<OverflowAddINode>::can_overflow(t1, t2);
406 141 }
407 if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) { 142
408 return no_overflow(phase, ConLNode::make(phase->C, 0)); 143 bool OverflowSubINode::can_overflow(const Type* t1, const Type* t2) const {
409 } 144 if (in(1) == in(2)) {
410 145 return false;
411 if (type1 == TypeLong::ONE) { 146 }
412 Node* mul_result = new (phase->C) AddLNode(arg2, phase->longcon(0)); 147 return SubHelper<OverflowSubINode>::can_overflow(t1, t2);
413 return no_overflow(phase, mul_result); 148 }
414 } 149
415 if (type2 == TypeLong::ONE) { 150 bool OverflowMulINode::can_overflow(const Type* t1, const Type* t2) const {
416 Node* mul_result = new (phase->C) AddLNode(arg1, phase->longcon(0)); 151 return MulHelper<OverflowMulINode>::can_overflow(t1, t2);
417 return no_overflow(phase, mul_result); 152 }
418 } 153
419 154 bool OverflowAddLNode::can_overflow(const Type* t1, const Type* t2) const {
420 if (type1 == TypeLong::MINUS_1) { 155 return AddHelper<OverflowAddLNode>::can_overflow(t1, t2);
421 return new (phase->C) NegExactLNode(NULL, arg2); 156 }
422 } 157
423 158 bool OverflowSubLNode::can_overflow(const Type* t1, const Type* t2) const {
424 if (type2 == TypeLong::MINUS_1) { 159 if (in(1) == in(2)) {
425 return new (phase->C) NegExactLNode(NULL, arg1); 160 return false;
426 } 161 }
427 162 return SubHelper<OverflowSubLNode>::can_overflow(t1, t2);
428 return NULL; 163 }
429 } 164
430 165 bool OverflowMulLNode::can_overflow(const Type* t1, const Type* t2) const {
166 return MulHelper<OverflowMulLNode>::can_overflow(t1, t2);
167 }
168
169 const Type* OverflowNode::sub(const Type* t1, const Type* t2) const {
170 fatal(err_msg_res("sub() should not be called for '%s'", NodeClassNames[this->Opcode()]));
171 return TypeInt::CC;
172 }
173
174 template <typename OverflowOp>
175 struct IdealHelper {
176 typedef typename OverflowOp::TypeClass TypeClass; // TypeInt, TypeLong
177 typedef typename TypeClass::NativeType NativeType;
178
179 static Node* Ideal(const OverflowOp* node, PhaseGVN* phase, bool can_reshape) {
180 Node* arg1 = node->in(1);
181 Node* arg2 = node->in(2);
182 const Type* type1 = phase->type(arg1);
183 const Type* type2 = phase->type(arg2);
184
185 if (type1 == NULL || type2 == NULL) {
186 return NULL;
187 }
188
189 if (type1 != Type::TOP && type1->singleton() &&
190 type2 != Type::TOP && type2->singleton()) {
191 NativeType val1 = TypeClass::as_self(type1)->get_con();
192 NativeType val2 = TypeClass::as_self(type2)->get_con();
193 if (node->will_overflow(val1, val2) == false) {
194 Node* con_result = ConINode::make(phase->C, 0);
195 return con_result;
196 }
197 return NULL;
198 }
199 return NULL;
200 }
201
202 static const Type* Value(const OverflowOp* node, PhaseTransform* phase) {
203 const Type *t1 = phase->type( node->in(1) );
204 const Type *t2 = phase->type( node->in(2) );
205 if( t1 == Type::TOP ) return Type::TOP;
206 if( t2 == Type::TOP ) return Type::TOP;
207
208 const TypeClass* i1 = TypeClass::as_self(t1);
209 const TypeClass* i2 = TypeClass::as_self(t2);
210
211 if (i1 == NULL || i2 == NULL) {
212 return TypeInt::CC;
213 }
214
215 if (t1->singleton() && t2->singleton()) {
216 NativeType val1 = i1->get_con();
217 NativeType val2 = i2->get_con();
218 if (node->will_overflow(val1, val2)) {
219 return TypeInt::CC;
220 }
221 return TypeInt::ZERO;
222 } else if (i1 != TypeClass::TYPE_DOMAIN && i2 != TypeClass::TYPE_DOMAIN) {
223 if (node->will_overflow(i1->_lo, i2->_lo)) {
224 return TypeInt::CC;
225 } else if (node->will_overflow(i1->_lo, i2->_hi)) {
226 return TypeInt::CC;
227 } else if (node->will_overflow(i1->_hi, i2->_lo)) {
228 return TypeInt::CC;
229 } else if (node->will_overflow(i1->_hi, i2->_hi)) {
230 return TypeInt::CC;
231 }
232 return TypeInt::ZERO;
233 }
234
235 if (!node->can_overflow(t1, t2)) {
236 return TypeInt::ZERO;
237 }
238 return TypeInt::CC;
239 }
240 };
241
242 Node* OverflowINode::Ideal(PhaseGVN* phase, bool can_reshape) {
243 return IdealHelper<OverflowINode>::Ideal(this, phase, can_reshape);
244 }
245
246 Node* OverflowLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
247 return IdealHelper<OverflowLNode>::Ideal(this, phase, can_reshape);
248 }
249
250 const Type* OverflowINode::Value(PhaseTransform* phase) const {
251 return IdealHelper<OverflowINode>::Value(this, phase);
252 }
253
254 const Type* OverflowLNode::Value(PhaseTransform* phase) const {
255 return IdealHelper<OverflowLNode>::Value(this, phase);
256 }
257