139 Node *x1 = add1->in(1);
140 Node *x2 = phase->makecon( add1->as_Add()->add_ring( t2, t12 ));
141 PhaseIterGVN *igvn = phase->is_IterGVN();
142 if( igvn ) {
143 set_req_X(2,x2,igvn);
144 set_req_X(1,x1,igvn);
145 } else {
146 set_req(2,x2);
147 set_req(1,x1);
148 }
149 progress = this; // Made progress
150 add1 = in(1);
151 add1_op = add1->Opcode();
152 }
153 }
154
155 // Convert "(x+1)+y" into "(x+y)+1". Push constants down the expression tree.
156 if( add1_op == this_op && !con_right ) {
157 Node *a12 = add1->in(2);
158 const Type *t12 = phase->type( a12 );
159 if( t12->singleton() && t12 != Type::TOP && (add1 != add1->in(1)) ) {
160 assert(add1->in(1) != this, "dead loop in AddNode::Ideal");
161 add2 = add1->clone();
162 add2->set_req(2, in(2));
163 add2 = phase->transform(add2);
164 set_req(1, add2);
165 set_req(2, a12);
166 progress = this;
167 add2 = a12;
168 }
169 }
170
171 // Convert "x+(y+1)" into "(x+y)+1". Push constants down the expression tree.
172 int add2_op = add2->Opcode();
173 if( add2_op == this_op && !con_left ) {
174 Node *a22 = add2->in(2);
175 const Type *t22 = phase->type( a22 );
176 if( t22->singleton() && t22 != Type::TOP && (add2 != add2->in(1)) ) {
177 assert(add2->in(1) != this, "dead loop in AddNode::Ideal");
178 Node *addx = add2->clone();
179 addx->set_req(1, in(1));
180 addx->set_req(2, add2->in(1));
181 addx = phase->transform(addx);
182 set_req(1, addx);
183 set_req(2, a22);
184 progress = this;
185 }
186 }
187
188 return progress;
189 }
190
191 //------------------------------Value-----------------------------------------
192 // An add node sums it's two _in. If one input is an RSD, we must mixin
193 // the other input's symbols.
194 const Type *AddNode::Value( PhaseTransform *phase ) const {
195 // Either input is TOP ==> the result is TOP
196 const Type *t1 = phase->type( in(1) );
208 const Type *tadd = add_of_identity( t1, t2 );
209 if( tadd ) return tadd;
210
211 return add_ring(t1,t2); // Local flavor of type addition
212 }
213
214 //------------------------------add_identity-----------------------------------
215 // Check for addition of the identity
216 const Type *AddNode::add_of_identity( const Type *t1, const Type *t2 ) const {
217 const Type *zero = add_id(); // The additive identity
218 if( t1->higher_equal( zero ) ) return t2;
219 if( t2->higher_equal( zero ) ) return t1;
220
221 return NULL;
222 }
223
224
225 //=============================================================================
226 //------------------------------Idealize---------------------------------------
227 Node *AddINode::Ideal(PhaseGVN *phase, bool can_reshape) {
228 int op1 = in(1)->Opcode();
229 int op2 = in(2)->Opcode();
230 // Fold (con1-x)+con2 into (con1+con2)-x
231 if( op1 == Op_SubI ) {
232 const Type *t_sub1 = phase->type( in(1)->in(1) );
233 const Type *t_2 = phase->type( in(2) );
234 if( t_sub1->singleton() && t_2->singleton() && t_sub1 != Type::TOP && t_2 != Type::TOP )
235 return new (phase->C, 3) SubINode(phase->makecon( add_ring( t_sub1, t_2 ) ),
236 in(1)->in(2) );
237 // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)"
238 if( op2 == Op_SubI ) {
239 // Check for dead cycle: d = (a-b)+(c-d)
240 assert( in(1)->in(2) != this && in(2)->in(2) != this,
241 "dead loop in AddINode::Ideal" );
242 Node *sub = new (phase->C, 3) SubINode(NULL, NULL);
243 sub->init_req(1, phase->transform(new (phase->C, 3) AddINode(in(1)->in(1), in(2)->in(1) ) ));
244 sub->init_req(2, phase->transform(new (phase->C, 3) AddINode(in(1)->in(2), in(2)->in(2) ) ));
245 return sub;
246 }
247 }
248
249 // Convert "x+(0-y)" into "(x-y)"
250 if( op2 == Op_SubI && phase->type(in(2)->in(1)) == TypeInt::ZERO )
251 return new (phase->C, 3) SubINode(in(1), in(2)->in(2) );
252
253 // Convert "(0-y)+x" into "(x-y)"
254 if( op1 == Op_SubI && phase->type(in(1)->in(1)) == TypeInt::ZERO )
255 return new (phase->C, 3) SubINode( in(2), in(1)->in(2) );
256
257 // Convert (x>>>z)+y into (x+(y<<z))>>>z for small constant z and y.
258 // Helps with array allocation math constant folding
259 // See 4790063:
260 // Unrestricted transformation is unsafe for some runtime values of 'x'
261 // ( x == 0, z == 1, y == -1 ) fails
262 // ( x == -5, z == 1, y == 1 ) fails
263 // Transform works for small z and small negative y when the addition
264 // (x + (y << z)) does not cross zero.
265 // Implement support for negative y and (x >= -(y << z))
266 // Have not observed cases where type information exists to support
267 // positive y and (x <= -(y << z))
268 if( op1 == Op_URShiftI && op2 == Op_ConI &&
269 in(1)->in(2)->Opcode() == Op_ConI ) {
270 jint z = phase->type( in(1)->in(2) )->is_int()->get_con() & 0x1f; // only least significant 5 bits matter
271 jint y = phase->type( in(2) )->is_int()->get_con();
272
273 if( z < 5 && -5 < y && y < 0 ) {
274 const Type *t_in11 = phase->type(in(1)->in(1));
275 if( t_in11 != Type::TOP && (t_in11->is_int()->_lo >= -(y << z)) ) {
276 Node *a = phase->transform( new (phase->C, 3) AddINode( in(1)->in(1), phase->intcon(y<<z) ) );
277 return new (phase->C, 3) URShiftINode( a, in(1)->in(2) );
278 }
279 }
280 }
281
282 return AddNode::Ideal(phase, can_reshape);
283 }
284
285
286 //------------------------------Identity---------------------------------------
287 // Fold (x-y)+y OR y+(x-y) into x
288 Node *AddINode::Identity( PhaseTransform *phase ) {
289 if( in(1)->Opcode() == Op_SubI && phase->eqv(in(1)->in(2),in(2)) ) {
290 return in(1)->in(1);
291 }
292 else if( in(2)->Opcode() == Op_SubI && phase->eqv(in(2)->in(2),in(1)) ) {
293 return in(2)->in(1);
294 }
295 return AddNode::Identity(phase);
296 }
297
311 lo = min_jint; hi = max_jint; // Underflow on the low side
312 }
313 if( (~(r0->_hi | r1->_hi)) < 0 && hi < 0 ) {
314 lo = min_jint; hi = max_jint; // Overflow on the high side
315 }
316 if( lo > hi ) { // Handle overflow
317 lo = min_jint; hi = max_jint;
318 }
319 } else {
320 // both constants, compute precise result using 'lo' and 'hi'
321 // Semantics define overflow and underflow for integer addition
322 // as expected. In particular: 0x80000000 + 0x80000000 --> 0x0
323 }
324 return TypeInt::make( lo, hi, MAX2(r0->_widen,r1->_widen) );
325 }
326
327
328 //=============================================================================
329 //------------------------------Idealize---------------------------------------
330 Node *AddLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
331 int op1 = in(1)->Opcode();
332 int op2 = in(2)->Opcode();
333 // Fold (con1-x)+con2 into (con1+con2)-x
334 if( op1 == Op_SubL ) {
335 const Type *t_sub1 = phase->type( in(1)->in(1) );
336 const Type *t_2 = phase->type( in(2) );
337 if( t_sub1->singleton() && t_2->singleton() && t_sub1 != Type::TOP && t_2 != Type::TOP )
338 return new (phase->C, 3) SubLNode(phase->makecon( add_ring( t_sub1, t_2 ) ),
339 in(1)->in(2) );
340 // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)"
341 if( op2 == Op_SubL ) {
342 // Check for dead cycle: d = (a-b)+(c-d)
343 assert( in(1)->in(2) != this && in(2)->in(2) != this,
344 "dead loop in AddLNode::Ideal" );
345 Node *sub = new (phase->C, 3) SubLNode(NULL, NULL);
346 sub->init_req(1, phase->transform(new (phase->C, 3) AddLNode(in(1)->in(1), in(2)->in(1) ) ));
347 sub->init_req(2, phase->transform(new (phase->C, 3) AddLNode(in(1)->in(2), in(2)->in(2) ) ));
348 return sub;
349 }
350 }
351
352 // Convert "x+(0-y)" into "(x-y)"
353 if( op2 == Op_SubL && phase->type(in(2)->in(1)) == TypeLong::ZERO )
354 return new (phase->C, 3) SubLNode(in(1), in(2)->in(2) );
355
356 // Convert "X+X+X+X+X...+X+Y" into "k*X+Y" or really convert "X+(X+Y)"
357 // into "(X<<1)+Y" and let shift-folding happen.
358 if( op2 == Op_AddL &&
359 in(2)->in(1) == in(1) &&
360 op1 != Op_ConL &&
361 0 ) {
362 Node *shift = phase->transform(new (phase->C, 3) LShiftLNode(in(1),phase->intcon(1)));
363 return new (phase->C, 3) AddLNode(shift,in(2)->in(2));
364 }
365
366 return AddNode::Ideal(phase, can_reshape);
367 }
368
369
370 //------------------------------Identity---------------------------------------
371 // Fold (x-y)+y OR y+(x-y) into x
372 Node *AddLNode::Identity( PhaseTransform *phase ) {
373 if( in(1)->Opcode() == Op_SubL && phase->eqv(in(1)->in(2),in(2)) ) {
374 return in(1)->in(1);
375 }
376 else if( in(2)->Opcode() == Op_SubL && phase->eqv(in(2)->in(2),in(1)) ) {
377 return in(2)->in(1);
378 }
379 return AddNode::Identity(phase);
380 }
381
382
383 //------------------------------add_ring---------------------------------------
|
139 Node *x1 = add1->in(1);
140 Node *x2 = phase->makecon( add1->as_Add()->add_ring( t2, t12 ));
141 PhaseIterGVN *igvn = phase->is_IterGVN();
142 if( igvn ) {
143 set_req_X(2,x2,igvn);
144 set_req_X(1,x1,igvn);
145 } else {
146 set_req(2,x2);
147 set_req(1,x1);
148 }
149 progress = this; // Made progress
150 add1 = in(1);
151 add1_op = add1->Opcode();
152 }
153 }
154
155 // Convert "(x+1)+y" into "(x+y)+1". Push constants down the expression tree.
156 if( add1_op == this_op && !con_right ) {
157 Node *a12 = add1->in(2);
158 const Type *t12 = phase->type( a12 );
159 if( t12->singleton() && t12 != Type::TOP && (add1 != add1->in(1)) &&
160 !(add1->in(1)->is_Phi() && add1->in(1)->as_Phi()->is_tripcount()) ) {
161 assert(add1->in(1) != this, "dead loop in AddNode::Ideal");
162 add2 = add1->clone();
163 add2->set_req(2, in(2));
164 add2 = phase->transform(add2);
165 set_req(1, add2);
166 set_req(2, a12);
167 progress = this;
168 add2 = a12;
169 }
170 }
171
172 // Convert "x+(y+1)" into "(x+y)+1". Push constants down the expression tree.
173 int add2_op = add2->Opcode();
174 if( add2_op == this_op && !con_left ) {
175 Node *a22 = add2->in(2);
176 const Type *t22 = phase->type( a22 );
177 if( t22->singleton() && t22 != Type::TOP && (add2 != add2->in(1)) &&
178 !(add2->in(1)->is_Phi() && add2->in(1)->as_Phi()->is_tripcount()) ) {
179 assert(add2->in(1) != this, "dead loop in AddNode::Ideal");
180 Node *addx = add2->clone();
181 addx->set_req(1, in(1));
182 addx->set_req(2, add2->in(1));
183 addx = phase->transform(addx);
184 set_req(1, addx);
185 set_req(2, a22);
186 progress = this;
187 }
188 }
189
190 return progress;
191 }
192
193 //------------------------------Value-----------------------------------------
194 // An add node sums it's two _in. If one input is an RSD, we must mixin
195 // the other input's symbols.
196 const Type *AddNode::Value( PhaseTransform *phase ) const {
197 // Either input is TOP ==> the result is TOP
198 const Type *t1 = phase->type( in(1) );
210 const Type *tadd = add_of_identity( t1, t2 );
211 if( tadd ) return tadd;
212
213 return add_ring(t1,t2); // Local flavor of type addition
214 }
215
216 //------------------------------add_identity-----------------------------------
217 // Check for addition of the identity
218 const Type *AddNode::add_of_identity( const Type *t1, const Type *t2 ) const {
219 const Type *zero = add_id(); // The additive identity
220 if( t1->higher_equal( zero ) ) return t2;
221 if( t2->higher_equal( zero ) ) return t1;
222
223 return NULL;
224 }
225
226
227 //=============================================================================
228 //------------------------------Idealize---------------------------------------
229 Node *AddINode::Ideal(PhaseGVN *phase, bool can_reshape) {
230 Node* in1 = in(1);
231 Node* in2 = in(2);
232 int op1 = in1->Opcode();
233 int op2 = in2->Opcode();
234 // Fold (con1-x)+con2 into (con1+con2)-x
235 if ( op1 == Op_AddI && op2 == Op_SubI ) {
236 // Swap edges to try optimizations below
237 in1 = in2;
238 in2 = in(1);
239 op1 = op2;
240 op2 = in2->Opcode();
241 }
242 if( op1 == Op_SubI ) {
243 const Type *t_sub1 = phase->type( in1->in(1) );
244 const Type *t_2 = phase->type( in2 );
245 if( t_sub1->singleton() && t_2->singleton() && t_sub1 != Type::TOP && t_2 != Type::TOP )
246 return new (phase->C, 3) SubINode(phase->makecon( add_ring( t_sub1, t_2 ) ),
247 in1->in(2) );
248 // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)"
249 if( op2 == Op_SubI ) {
250 // Check for dead cycle: d = (a-b)+(c-d)
251 assert( in1->in(2) != this && in2->in(2) != this,
252 "dead loop in AddINode::Ideal" );
253 Node *sub = new (phase->C, 3) SubINode(NULL, NULL);
254 sub->init_req(1, phase->transform(new (phase->C, 3) AddINode(in1->in(1), in2->in(1) ) ));
255 sub->init_req(2, phase->transform(new (phase->C, 3) AddINode(in1->in(2), in2->in(2) ) ));
256 return sub;
257 }
258 // Convert "(a-b)+(b+c)" into "(a+c)"
259 if( op2 == Op_AddI && in1->in(2) == in2->in(1) ) {
260 assert(in1->in(1) != this && in2->in(2) != this,"dead loop in AddINode::Ideal");
261 return new (phase->C, 3) AddINode(in1->in(1), in2->in(2));
262 }
263 // Convert "(a-b)+(c+b)" into "(a+c)"
264 if( op2 == Op_AddI && in1->in(2) == in2->in(2) ) {
265 assert(in1->in(1) != this && in2->in(1) != this,"dead loop in AddINode::Ideal");
266 return new (phase->C, 3) AddINode(in1->in(1), in2->in(1));
267 }
268 // Convert "(a-b)+(b-c)" into "(a-c)"
269 if( op2 == Op_SubI && in1->in(2) == in2->in(1) ) {
270 assert(in1->in(1) != this && in2->in(2) != this,"dead loop in AddINode::Ideal");
271 return new (phase->C, 3) SubINode(in1->in(1), in2->in(2));
272 }
273 // Convert "(a-b)+(c-a)" into "(c-b)"
274 if( op2 == Op_SubI && in1->in(1) == in2->in(2) ) {
275 assert(in1->in(2) != this && in2->in(1) != this,"dead loop in AddINode::Ideal");
276 return new (phase->C, 3) SubINode(in2->in(1), in1->in(2));
277 }
278 }
279
280 // Convert "x+(0-y)" into "(x-y)"
281 if( op2 == Op_SubI && phase->type(in2->in(1)) == TypeInt::ZERO )
282 return new (phase->C, 3) SubINode(in1, in2->in(2) );
283
284 // Convert "(0-y)+x" into "(x-y)"
285 if( op1 == Op_SubI && phase->type(in1->in(1)) == TypeInt::ZERO )
286 return new (phase->C, 3) SubINode( in2, in1->in(2) );
287
288 // Convert (x>>>z)+y into (x+(y<<z))>>>z for small constant z and y.
289 // Helps with array allocation math constant folding
290 // See 4790063:
291 // Unrestricted transformation is unsafe for some runtime values of 'x'
292 // ( x == 0, z == 1, y == -1 ) fails
293 // ( x == -5, z == 1, y == 1 ) fails
294 // Transform works for small z and small negative y when the addition
295 // (x + (y << z)) does not cross zero.
296 // Implement support for negative y and (x >= -(y << z))
297 // Have not observed cases where type information exists to support
298 // positive y and (x <= -(y << z))
299 if( op1 == Op_URShiftI && op2 == Op_ConI &&
300 in1->in(2)->Opcode() == Op_ConI ) {
301 jint z = phase->type( in1->in(2) )->is_int()->get_con() & 0x1f; // only least significant 5 bits matter
302 jint y = phase->type( in2 )->is_int()->get_con();
303
304 if( z < 5 && -5 < y && y < 0 ) {
305 const Type *t_in11 = phase->type(in1->in(1));
306 if( t_in11 != Type::TOP && (t_in11->is_int()->_lo >= -(y << z)) ) {
307 Node *a = phase->transform( new (phase->C, 3) AddINode( in1->in(1), phase->intcon(y<<z) ) );
308 return new (phase->C, 3) URShiftINode( a, in1->in(2) );
309 }
310 }
311 }
312
313 return AddNode::Ideal(phase, can_reshape);
314 }
315
316
317 //------------------------------Identity---------------------------------------
318 // Fold (x-y)+y OR y+(x-y) into x
319 Node *AddINode::Identity( PhaseTransform *phase ) {
320 if( in(1)->Opcode() == Op_SubI && phase->eqv(in(1)->in(2),in(2)) ) {
321 return in(1)->in(1);
322 }
323 else if( in(2)->Opcode() == Op_SubI && phase->eqv(in(2)->in(2),in(1)) ) {
324 return in(2)->in(1);
325 }
326 return AddNode::Identity(phase);
327 }
328
342 lo = min_jint; hi = max_jint; // Underflow on the low side
343 }
344 if( (~(r0->_hi | r1->_hi)) < 0 && hi < 0 ) {
345 lo = min_jint; hi = max_jint; // Overflow on the high side
346 }
347 if( lo > hi ) { // Handle overflow
348 lo = min_jint; hi = max_jint;
349 }
350 } else {
351 // both constants, compute precise result using 'lo' and 'hi'
352 // Semantics define overflow and underflow for integer addition
353 // as expected. In particular: 0x80000000 + 0x80000000 --> 0x0
354 }
355 return TypeInt::make( lo, hi, MAX2(r0->_widen,r1->_widen) );
356 }
357
358
359 //=============================================================================
360 //------------------------------Idealize---------------------------------------
361 Node *AddLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
362 Node* in1 = in(1);
363 Node* in2 = in(2);
364 int op1 = in1->Opcode();
365 int op2 = in2->Opcode();
366 // Fold (con1-x)+con2 into (con1+con2)-x
367 if ( op1 == Op_AddL && op2 == Op_SubL ) {
368 // Swap edges to try optimizations below
369 in1 = in2;
370 in2 = in(1);
371 op1 = op2;
372 op2 = in2->Opcode();
373 }
374 // Fold (con1-x)+con2 into (con1+con2)-x
375 if( op1 == Op_SubL ) {
376 const Type *t_sub1 = phase->type( in1->in(1) );
377 const Type *t_2 = phase->type( in2 );
378 if( t_sub1->singleton() && t_2->singleton() && t_sub1 != Type::TOP && t_2 != Type::TOP )
379 return new (phase->C, 3) SubLNode(phase->makecon( add_ring( t_sub1, t_2 ) ),
380 in1->in(2) );
381 // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)"
382 if( op2 == Op_SubL ) {
383 // Check for dead cycle: d = (a-b)+(c-d)
384 assert( in1->in(2) != this && in2->in(2) != this,
385 "dead loop in AddLNode::Ideal" );
386 Node *sub = new (phase->C, 3) SubLNode(NULL, NULL);
387 sub->init_req(1, phase->transform(new (phase->C, 3) AddLNode(in1->in(1), in2->in(1) ) ));
388 sub->init_req(2, phase->transform(new (phase->C, 3) AddLNode(in1->in(2), in2->in(2) ) ));
389 return sub;
390 }
391 // Convert "(a-b)+(b+c)" into "(a+c)"
392 if( op2 == Op_AddL && in1->in(2) == in2->in(1) ) {
393 assert(in1->in(1) != this && in2->in(2) != this,"dead loop in AddLNode::Ideal");
394 return new (phase->C, 3) AddLNode(in1->in(1), in2->in(2));
395 }
396 // Convert "(a-b)+(c+b)" into "(a+c)"
397 if( op2 == Op_AddL && in1->in(2) == in2->in(2) ) {
398 assert(in1->in(1) != this && in2->in(1) != this,"dead loop in AddLNode::Ideal");
399 return new (phase->C, 3) AddLNode(in1->in(1), in2->in(1));
400 }
401 // Convert "(a-b)+(b-c)" into "(a-c)"
402 if( op2 == Op_SubL && in1->in(2) == in2->in(1) ) {
403 assert(in1->in(1) != this && in2->in(2) != this,"dead loop in AddLNode::Ideal");
404 return new (phase->C, 3) SubLNode(in1->in(1), in2->in(2));
405 }
406 // Convert "(a-b)+(c-a)" into "(c-b)"
407 if( op2 == Op_SubL && in1->in(1) == in1->in(2) ) {
408 assert(in1->in(2) != this && in2->in(1) != this,"dead loop in AddLNode::Ideal");
409 return new (phase->C, 3) SubLNode(in2->in(1), in1->in(2));
410 }
411 }
412
413 // Convert "x+(0-y)" into "(x-y)"
414 if( op2 == Op_SubL && phase->type(in2->in(1)) == TypeLong::ZERO )
415 return new (phase->C, 3) SubLNode( in1, in2->in(2) );
416
417 // Convert "(0-y)+x" into "(x-y)"
418 if( op1 == Op_SubL && phase->type(in1->in(1)) == TypeInt::ZERO )
419 return new (phase->C, 3) SubLNode( in2, in1->in(2) );
420
421 // Convert "X+X+X+X+X...+X+Y" into "k*X+Y" or really convert "X+(X+Y)"
422 // into "(X<<1)+Y" and let shift-folding happen.
423 if( op2 == Op_AddL &&
424 in2->in(1) == in1 &&
425 op1 != Op_ConL &&
426 0 ) {
427 Node *shift = phase->transform(new (phase->C, 3) LShiftLNode(in1,phase->intcon(1)));
428 return new (phase->C, 3) AddLNode(shift,in2->in(2));
429 }
430
431 return AddNode::Ideal(phase, can_reshape);
432 }
433
434
435 //------------------------------Identity---------------------------------------
436 // Fold (x-y)+y OR y+(x-y) into x
437 Node *AddLNode::Identity( PhaseTransform *phase ) {
438 if( in(1)->Opcode() == Op_SubL && phase->eqv(in(1)->in(2),in(2)) ) {
439 return in(1)->in(1);
440 }
441 else if( in(2)->Opcode() == Op_SubL && phase->eqv(in(2)->in(2),in(1)) ) {
442 return in(2)->in(1);
443 }
444 return AddNode::Identity(phase);
445 }
446
447
448 //------------------------------add_ring---------------------------------------
|