jdk

1
/*
2
 * Copyright (c) 1997, 2023, 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 "compiler/compileLog.hpp"
27
#include "gc/shared/barrierSet.hpp"
28
#include "gc/shared/c2/barrierSetC2.hpp"
29
#include "memory/allocation.inline.hpp"
30
#include "opto/addnode.hpp"
31
#include "opto/callnode.hpp"
32
#include "opto/cfgnode.hpp"
33
#include "opto/loopnode.hpp"
34
#include "opto/matcher.hpp"
35
#include "opto/movenode.hpp"
36
#include "opto/mulnode.hpp"
37
#include "opto/opaquenode.hpp"
38
#include "opto/opcodes.hpp"
39
#include "opto/phaseX.hpp"
40
#include "opto/subnode.hpp"
41
#include "runtime/sharedRuntime.hpp"
42
#include "utilities/reverse_bits.hpp"
43

44
// Portions of code courtesy of Clifford Click
45

46
// Optimization - Graph Style
47

48
#include "math.h"
49

50
//=============================================================================
51
//------------------------------Identity---------------------------------------
52
// If right input is a constant 0, return the left input.
53
Node* SubNode::Identity(PhaseGVN* phase) {
54
  assert(in(1) != this, "Must already have called Value");
55
  assert(in(2) != this, "Must already have called Value");
56

57
  // Remove double negation
58
  const Type *zero = add_id();
59
  if( phase->type( in(1) )->higher_equal( zero ) &&
60
      in(2)->Opcode() == Opcode() &&
61
      phase->type( in(2)->in(1) )->higher_equal( zero ) ) {
62
    return in(2)->in(2);
63
  }
64

65
  // Convert "(X+Y) - Y" into X and "(X+Y) - X" into Y
66
  if (in(1)->Opcode() == Op_AddI || in(1)->Opcode() == Op_AddL) {
67
    if (in(1)->in(2) == in(2)) {
68
      return in(1)->in(1);
69
    }
70
    if (in(1)->in(1) == in(2)) {
71
      return in(1)->in(2);
72
    }
73
  }
74

75
  return ( phase->type( in(2) )->higher_equal( zero ) ) ? in(1) : this;
76
}
77

78
//------------------------------Value------------------------------------------
79
// A subtract node differences it's two inputs.
80
const Type* SubNode::Value_common(PhaseValues* phase) const {
81
  const Node* in1 = in(1);
82
  const Node* in2 = in(2);
83
  // Either input is TOP ==> the result is TOP
84
  const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);
85
  if( t1 == Type::TOP ) return Type::TOP;
86
  const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);
87
  if( t2 == Type::TOP ) return Type::TOP;
88

89
  // Not correct for SubFnode and AddFNode (must check for infinity)
90
  // Equal?  Subtract is zero
91
  if (in1->eqv_uncast(in2))  return add_id();
92

93
  // Either input is BOTTOM ==> the result is the local BOTTOM
94
  if( t1 == Type::BOTTOM || t2 == Type::BOTTOM )
95
    return bottom_type();
96

97
  return nullptr;
98
}
99

100
const Type* SubNode::Value(PhaseGVN* phase) const {
101
  const Type* t = Value_common(phase);
102
  if (t != nullptr) {
103
    return t;
104
  }
105
  const Type* t1 = phase->type(in(1));
106
  const Type* t2 = phase->type(in(2));
107
  return sub(t1,t2);            // Local flavor of type subtraction
108

109
}
110

111
SubNode* SubNode::make(Node* in1, Node* in2, BasicType bt) {
112
  switch (bt) {
113
    case T_INT:
114
      return new SubINode(in1, in2);
115
    case T_LONG:
116
      return new SubLNode(in1, in2);
117
    default:
118
      fatal("Not implemented for %s", type2name(bt));
119
  }
120
  return nullptr;
121
}
122

123
//=============================================================================
124
//------------------------------Helper function--------------------------------
125

126
static bool is_cloop_increment(Node* inc) {
127
  precond(inc->Opcode() == Op_AddI || inc->Opcode() == Op_AddL);
128

129
  if (!inc->in(1)->is_Phi()) {
130
    return false;
131
  }
132
  const PhiNode* phi = inc->in(1)->as_Phi();
133

134
  if (!phi->region()->is_CountedLoop()) {
135
    return false;
136
  }
137

138
  return inc == phi->region()->as_CountedLoop()->incr();
139
}
140

141
// Given the expression '(x + C) - v', or
142
//                      'v - (x + C)', we examine nodes '+' and 'v':
143
//
144
//  1. Do not convert if '+' is a counted-loop increment, because the '-' is
145
//     loop invariant and converting extends the live-range of 'x' to overlap
146
//     with the '+', forcing another register to be used in the loop.
147
//
148
//  2. Do not convert if 'v' is a counted-loop induction variable, because
149
//     'x' might be invariant.
150
//
151
static bool ok_to_convert(Node* inc, Node* var) {
152
  return !(is_cloop_increment(inc) || var->is_cloop_ind_var());
153
}
154

155
static bool is_cloop_condition(BoolNode* bol) {
156
  for (DUIterator_Fast imax, i = bol->fast_outs(imax); i < imax; i++) {
157
    Node* out = bol->fast_out(i);
158
    if (out->is_BaseCountedLoopEnd()) {
159
      return true;
160
    }
161
  }
162
  return false;
163
}
164

165
//------------------------------Ideal------------------------------------------
166
Node *SubINode::Ideal(PhaseGVN *phase, bool can_reshape){
167
  Node *in1 = in(1);
168
  Node *in2 = in(2);
169
  uint op1 = in1->Opcode();
170
  uint op2 = in2->Opcode();
171

172
#ifdef ASSERT
173
  // Check for dead loop
174
  if ((in1 == this) || (in2 == this) ||
175
      ((op1 == Op_AddI || op1 == Op_SubI) &&
176
       ((in1->in(1) == this) || (in1->in(2) == this) ||
177
        (in1->in(1) == in1)  || (in1->in(2) == in1)))) {
178
    assert(false, "dead loop in SubINode::Ideal");
179
  }
180
#endif
181

182
  const Type *t2 = phase->type( in2 );
183
  if( t2 == Type::TOP ) return nullptr;
184
  // Convert "x-c0" into "x+ -c0".
185
  if( t2->base() == Type::Int ){        // Might be bottom or top...
186
    const TypeInt *i = t2->is_int();
187
    if( i->is_con() )
188
      return new AddINode(in1, phase->intcon(java_negate(i->get_con())));
189
  }
190

191
  // Convert "(x+c0) - y" into (x-y) + c0"
192
  // Do not collapse (x+c0)-y if "+" is a loop increment or
193
  // if "y" is a loop induction variable.
194
  if( op1 == Op_AddI && ok_to_convert(in1, in2) ) {
195
    const Type *tadd = phase->type( in1->in(2) );
196
    if( tadd->singleton() && tadd != Type::TOP ) {
197
      Node *sub2 = phase->transform( new SubINode( in1->in(1), in2 ));
198
      return new AddINode( sub2, in1->in(2) );
199
    }
200
  }
201

202
  // Convert "x - (y+c0)" into "(x-y) - c0" AND
203
  // Convert "c1 - (y+c0)" into "(c1-c0) - y"
204
  // Need the same check as in above optimization but reversed.
205
  if (op2 == Op_AddI
206
      && ok_to_convert(in2, in1)
207
      && in2->in(2)->Opcode() == Op_ConI) {
208
    jint c0 = phase->type(in2->in(2))->isa_int()->get_con();
209
    Node* in21 = in2->in(1);
210
    if (in1->Opcode() == Op_ConI) {
211
      // Match c1
212
      jint c1 = phase->type(in1)->isa_int()->get_con();
213
      Node* sub2 = phase->intcon(java_subtract(c1, c0));
214
      return new SubINode(sub2, in21);
215
    } else {
216
      // Match x
217
      Node* sub2 = phase->transform(new SubINode(in1, in21));
218
      Node* neg_c0 = phase->intcon(java_negate(c0));
219
      return new AddINode(sub2, neg_c0);
220
    }
221
  }
222

223
  const Type *t1 = phase->type( in1 );
224
  if( t1 == Type::TOP ) return nullptr;
225

226
#ifdef ASSERT
227
  // Check for dead loop
228
  if ((op2 == Op_AddI || op2 == Op_SubI) &&
229
      ((in2->in(1) == this) || (in2->in(2) == this) ||
230
       (in2->in(1) == in2)  || (in2->in(2) == in2))) {
231
    assert(false, "dead loop in SubINode::Ideal");
232
  }
233
#endif
234

235
  // Convert "x - (x+y)" into "-y"
236
  if (op2 == Op_AddI && in1 == in2->in(1)) {
237
    return new SubINode(phase->intcon(0), in2->in(2));
238
  }
239
  // Convert "(x-y) - x" into "-y"
240
  if (op1 == Op_SubI && in1->in(1) == in2) {
241
    return new SubINode(phase->intcon(0), in1->in(2));
242
  }
243
  // Convert "x - (y+x)" into "-y"
244
  if (op2 == Op_AddI && in1 == in2->in(2)) {
245
    return new SubINode(phase->intcon(0), in2->in(1));
246
  }
247

248
  // Convert "0 - (x-y)" into "y-x", leave the double negation "-(-y)" to SubNode::Identity().
249
  if (t1 == TypeInt::ZERO && op2 == Op_SubI && phase->type(in2->in(1)) != TypeInt::ZERO) {
250
    return new SubINode(in2->in(2), in2->in(1));
251
  }
252

253
  // Convert "0 - (x+con)" into "-con-x"
254
  jint con;
255
  if( t1 == TypeInt::ZERO && op2 == Op_AddI &&
256
      (con = in2->in(2)->find_int_con(0)) != 0 )
257
    return new SubINode( phase->intcon(-con), in2->in(1) );
258

259
  // Convert "(X+A) - (X+B)" into "A - B"
260
  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(1) == in2->in(1) )
261
    return new SubINode( in1->in(2), in2->in(2) );
262

263
  // Convert "(A+X) - (B+X)" into "A - B"
264
  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(2) == in2->in(2) )
265
    return new SubINode( in1->in(1), in2->in(1) );
266

267
  // Convert "(A+X) - (X+B)" into "A - B"
268
  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(2) == in2->in(1) )
269
    return new SubINode( in1->in(1), in2->in(2) );
270

271
  // Convert "(X+A) - (B+X)" into "A - B"
272
  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(1) == in2->in(2) )
273
    return new SubINode( in1->in(2), in2->in(1) );
274

275
  // Convert "A-(B-C)" into (A+C)-B", since add is commutative and generally
276
  // nicer to optimize than subtract.
277
  if( op2 == Op_SubI && in2->outcnt() == 1) {
278
    Node *add1 = phase->transform( new AddINode( in1, in2->in(2) ) );
279
    return new SubINode( add1, in2->in(1) );
280
  }
281

282
  // Associative
283
  if (op1 == Op_MulI && op2 == Op_MulI) {
284
    Node* sub_in1 = nullptr;
285
    Node* sub_in2 = nullptr;
286
    Node* mul_in = nullptr;
287

288
    if (in1->in(1) == in2->in(1)) {
289
      // Convert "a*b-a*c into a*(b-c)
290
      sub_in1 = in1->in(2);
291
      sub_in2 = in2->in(2);
292
      mul_in = in1->in(1);
293
    } else if (in1->in(2) == in2->in(1)) {
294
      // Convert a*b-b*c into b*(a-c)
295
      sub_in1 = in1->in(1);
296
      sub_in2 = in2->in(2);
297
      mul_in = in1->in(2);
298
    } else if (in1->in(2) == in2->in(2)) {
299
      // Convert a*c-b*c into (a-b)*c
300
      sub_in1 = in1->in(1);
301
      sub_in2 = in2->in(1);
302
      mul_in = in1->in(2);
303
    } else if (in1->in(1) == in2->in(2)) {
304
      // Convert a*b-c*a into a*(b-c)
305
      sub_in1 = in1->in(2);
306
      sub_in2 = in2->in(1);
307
      mul_in = in1->in(1);
308
    }
309

310
    if (mul_in != nullptr) {
311
      Node* sub = phase->transform(new SubINode(sub_in1, sub_in2));
312
      return new MulINode(mul_in, sub);
313
    }
314
  }
315

316
  // Convert "0-(A>>31)" into "(A>>>31)"
317
  if ( op2 == Op_RShiftI ) {
318
    Node *in21 = in2->in(1);
319
    Node *in22 = in2->in(2);
320
    const TypeInt *zero = phase->type(in1)->isa_int();
321
    const TypeInt *t21 = phase->type(in21)->isa_int();
322
    const TypeInt *t22 = phase->type(in22)->isa_int();
323
    if ( t21 && t22 && zero == TypeInt::ZERO && t22->is_con(31) ) {
324
      return new URShiftINode(in21, in22);
325
    }
326
  }
327

328
  return nullptr;
329
}
330

331
//------------------------------sub--------------------------------------------
332
// A subtract node differences it's two inputs.
333
const Type *SubINode::sub( const Type *t1, const Type *t2 ) const {
334
  const TypeInt *r0 = t1->is_int(); // Handy access
335
  const TypeInt *r1 = t2->is_int();
336
  int32_t lo = java_subtract(r0->_lo, r1->_hi);
337
  int32_t hi = java_subtract(r0->_hi, r1->_lo);
338

339
  // We next check for 32-bit overflow.
340
  // If that happens, we just assume all integers are possible.
341
  if( (((r0->_lo ^ r1->_hi) >= 0) ||    // lo ends have same signs OR
342
       ((r0->_lo ^      lo) >= 0)) &&   // lo results have same signs AND
343
      (((r0->_hi ^ r1->_lo) >= 0) ||    // hi ends have same signs OR
344
       ((r0->_hi ^      hi) >= 0)) )    // hi results have same signs
345
    return TypeInt::make(lo,hi,MAX2(r0->_widen,r1->_widen));
346
  else                          // Overflow; assume all integers
347
    return TypeInt::INT;
348
}
349

350
//=============================================================================
351
//------------------------------Ideal------------------------------------------
352
Node *SubLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
353
  Node *in1 = in(1);
354
  Node *in2 = in(2);
355
  uint op1 = in1->Opcode();
356
  uint op2 = in2->Opcode();
357

358
#ifdef ASSERT
359
  // Check for dead loop
360
  if ((in1 == this) || (in2 == this) ||
361
      ((op1 == Op_AddL || op1 == Op_SubL) &&
362
       ((in1->in(1) == this) || (in1->in(2) == this) ||
363
        (in1->in(1) == in1)  || (in1->in(2) == in1)))) {
364
    assert(false, "dead loop in SubLNode::Ideal");
365
  }
366
#endif
367

368
  if( phase->type( in2 ) == Type::TOP ) return nullptr;
369
  const TypeLong *i = phase->type( in2 )->isa_long();
370
  // Convert "x-c0" into "x+ -c0".
371
  if( i &&                      // Might be bottom or top...
372
      i->is_con() )
373
    return new AddLNode(in1, phase->longcon(java_negate(i->get_con())));
374

375
  // Convert "(x+c0) - y" into (x-y) + c0"
376
  // Do not collapse (x+c0)-y if "+" is a loop increment or
377
  // if "y" is a loop induction variable.
378
  if( op1 == Op_AddL && ok_to_convert(in1, in2) ) {
379
    Node *in11 = in1->in(1);
380
    const Type *tadd = phase->type( in1->in(2) );
381
    if( tadd->singleton() && tadd != Type::TOP ) {
382
      Node *sub2 = phase->transform( new SubLNode( in11, in2 ));
383
      return new AddLNode( sub2, in1->in(2) );
384
    }
385
  }
386

387
  // Convert "x - (y+c0)" into "(x-y) - c0" AND
388
  // Convert "c1 - (y+c0)" into "(c1-c0) - y"
389
  // Need the same check as in above optimization but reversed.
390
  if (op2 == Op_AddL
391
      && ok_to_convert(in2, in1)
392
      && in2->in(2)->Opcode() == Op_ConL) {
393
    jlong c0 = phase->type(in2->in(2))->isa_long()->get_con();
394
    Node* in21 = in2->in(1);
395
    if (in1->Opcode() == Op_ConL) {
396
      // Match c1
397
      jlong c1 = phase->type(in1)->isa_long()->get_con();
398
      Node* sub2 = phase->longcon(java_subtract(c1, c0));
399
      return new SubLNode(sub2, in21);
400
    } else {
401
      Node* sub2 = phase->transform(new SubLNode(in1, in21));
402
      Node* neg_c0 = phase->longcon(-c0);
403
      return new AddLNode(sub2, neg_c0);
404
    }
405
  }
406

407
  const Type *t1 = phase->type( in1 );
408
  if( t1 == Type::TOP ) return nullptr;
409

410
#ifdef ASSERT
411
  // Check for dead loop
412
  if ((op2 == Op_AddL || op2 == Op_SubL) &&
413
      ((in2->in(1) == this) || (in2->in(2) == this) ||
414
       (in2->in(1) == in2)  || (in2->in(2) == in2))) {
415
    assert(false, "dead loop in SubLNode::Ideal");
416
  }
417
#endif
418

419
  // Convert "x - (x+y)" into "-y"
420
  if (op2 == Op_AddL && in1 == in2->in(1)) {
421
    return new SubLNode(phase->makecon(TypeLong::ZERO), in2->in(2));
422
  }
423
  // Convert "(x-y) - x" into "-y"
424
  if (op1 == Op_SubL && in1->in(1) == in2) {
425
    return new SubLNode(phase->makecon(TypeLong::ZERO), in1->in(2));
426
  }
427
  // Convert "x - (y+x)" into "-y"
428
  if (op2 == Op_AddL && in1 == in2->in(2)) {
429
    return new SubLNode(phase->makecon(TypeLong::ZERO), in2->in(1));
430
  }
431

432
  // Convert "0 - (x-y)" into "y-x", leave the double negation "-(-y)" to SubNode::Identity.
433
  if (t1 == TypeLong::ZERO && op2 == Op_SubL && phase->type(in2->in(1)) != TypeLong::ZERO) {
434
    return new SubLNode(in2->in(2), in2->in(1));
435
  }
436

437
  // Convert "(X+A) - (X+B)" into "A - B"
438
  if( op1 == Op_AddL && op2 == Op_AddL && in1->in(1) == in2->in(1) )
439
    return new SubLNode( in1->in(2), in2->in(2) );
440

441
  // Convert "(A+X) - (B+X)" into "A - B"
442
  if( op1 == Op_AddL && op2 == Op_AddL && in1->in(2) == in2->in(2) )
443
    return new SubLNode( in1->in(1), in2->in(1) );
444

445
  // Convert "(A+X) - (X+B)" into "A - B"
446
  if( op1 == Op_AddL && op2 == Op_AddL && in1->in(2) == in2->in(1) )
447
    return new SubLNode( in1->in(1), in2->in(2) );
448

449
  // Convert "(X+A) - (B+X)" into "A - B"
450
  if( op1 == Op_AddL && op2 == Op_AddL && in1->in(1) == in2->in(2) )
451
    return new SubLNode( in1->in(2), in2->in(1) );
452

453
  // Convert "A-(B-C)" into (A+C)-B"
454
  if( op2 == Op_SubL && in2->outcnt() == 1) {
455
    Node *add1 = phase->transform( new AddLNode( in1, in2->in(2) ) );
456
    return new SubLNode( add1, in2->in(1) );
457
  }
458

459
  // Associative
460
  if (op1 == Op_MulL && op2 == Op_MulL) {
461
    Node* sub_in1 = nullptr;
462
    Node* sub_in2 = nullptr;
463
    Node* mul_in = nullptr;
464

465
    if (in1->in(1) == in2->in(1)) {
466
      // Convert "a*b-a*c into a*(b+c)
467
      sub_in1 = in1->in(2);
468
      sub_in2 = in2->in(2);
469
      mul_in = in1->in(1);
470
    } else if (in1->in(2) == in2->in(1)) {
471
      // Convert a*b-b*c into b*(a-c)
472
      sub_in1 = in1->in(1);
473
      sub_in2 = in2->in(2);
474
      mul_in = in1->in(2);
475
    } else if (in1->in(2) == in2->in(2)) {
476
      // Convert a*c-b*c into (a-b)*c
477
      sub_in1 = in1->in(1);
478
      sub_in2 = in2->in(1);
479
      mul_in = in1->in(2);
480
    } else if (in1->in(1) == in2->in(2)) {
481
      // Convert a*b-c*a into a*(b-c)
482
      sub_in1 = in1->in(2);
483
      sub_in2 = in2->in(1);
484
      mul_in = in1->in(1);
485
    }
486

487
    if (mul_in != nullptr) {
488
      Node* sub = phase->transform(new SubLNode(sub_in1, sub_in2));
489
      return new MulLNode(mul_in, sub);
490
    }
491
  }
492

493
  // Convert "0L-(A>>63)" into "(A>>>63)"
494
  if ( op2 == Op_RShiftL ) {
495
    Node *in21 = in2->in(1);
496
    Node *in22 = in2->in(2);
497
    const TypeLong *zero = phase->type(in1)->isa_long();
498
    const TypeLong *t21 = phase->type(in21)->isa_long();
499
    const TypeInt *t22 = phase->type(in22)->isa_int();
500
    if ( t21 && t22 && zero == TypeLong::ZERO && t22->is_con(63) ) {
501
      return new URShiftLNode(in21, in22);
502
    }
503
  }
504

505
  return nullptr;
506
}
507

508
//------------------------------sub--------------------------------------------
509
// A subtract node differences it's two inputs.
510
const Type *SubLNode::sub( const Type *t1, const Type *t2 ) const {
511
  const TypeLong *r0 = t1->is_long(); // Handy access
512
  const TypeLong *r1 = t2->is_long();
513
  jlong lo = java_subtract(r0->_lo, r1->_hi);
514
  jlong hi = java_subtract(r0->_hi, r1->_lo);
515

516
  // We next check for 32-bit overflow.
517
  // If that happens, we just assume all integers are possible.
518
  if( (((r0->_lo ^ r1->_hi) >= 0) ||    // lo ends have same signs OR
519
       ((r0->_lo ^      lo) >= 0)) &&   // lo results have same signs AND
520
      (((r0->_hi ^ r1->_lo) >= 0) ||    // hi ends have same signs OR
521
       ((r0->_hi ^      hi) >= 0)) )    // hi results have same signs
522
    return TypeLong::make(lo,hi,MAX2(r0->_widen,r1->_widen));
523
  else                          // Overflow; assume all integers
524
    return TypeLong::LONG;
525
}
526

527
//=============================================================================
528
//------------------------------Value------------------------------------------
529
// A subtract node differences its two inputs.
530
const Type* SubFPNode::Value(PhaseGVN* phase) const {
531
  const Node* in1 = in(1);
532
  const Node* in2 = in(2);
533
  // Either input is TOP ==> the result is TOP
534
  const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);
535
  if( t1 == Type::TOP ) return Type::TOP;
536
  const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);
537
  if( t2 == Type::TOP ) return Type::TOP;
538

539
  // if both operands are infinity of same sign, the result is NaN; do
540
  // not replace with zero
541
  if (t1->is_finite() && t2->is_finite() && in1 == in2) {
542
    return add_id();
543
  }
544

545
  // Either input is BOTTOM ==> the result is the local BOTTOM
546
  const Type *bot = bottom_type();
547
  if( (t1 == bot) || (t2 == bot) ||
548
      (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
549
    return bot;
550

551
  return sub(t1,t2);            // Local flavor of type subtraction
552
}
553

554

555
//=============================================================================
556
//------------------------------Ideal------------------------------------------
557
Node *SubFNode::Ideal(PhaseGVN *phase, bool can_reshape) {
558
  const Type *t2 = phase->type( in(2) );
559
  // Convert "x-c0" into "x+ -c0".
560
  if( t2->base() == Type::FloatCon ) {  // Might be bottom or top...
561
    // return new (phase->C, 3) AddFNode(in(1), phase->makecon( TypeF::make(-t2->getf()) ) );
562
  }
563

564
  // Cannot replace 0.0-X with -X because a 'fsub' bytecode computes
565
  // 0.0-0.0 as +0.0, while a 'fneg' bytecode computes -0.0.
566
  //if( phase->type(in(1)) == TypeF::ZERO )
567
  //return new (phase->C, 2) NegFNode(in(2));
568

569
  return nullptr;
570
}
571

572
//------------------------------sub--------------------------------------------
573
// A subtract node differences its two inputs.
574
const Type *SubFNode::sub( const Type *t1, const Type *t2 ) const {
575
  // no folding if one of operands is infinity or NaN, do not do constant folding
576
  if( g_isfinite(t1->getf()) && g_isfinite(t2->getf()) ) {
577
    return TypeF::make( t1->getf() - t2->getf() );
578
  }
579
  else if( g_isnan(t1->getf()) ) {
580
    return t1;
581
  }
582
  else if( g_isnan(t2->getf()) ) {
583
    return t2;
584
  }
585
  else {
586
    return Type::FLOAT;
587
  }
588
}
589

590
//=============================================================================
591
//------------------------------Ideal------------------------------------------
592
Node *SubDNode::Ideal(PhaseGVN *phase, bool can_reshape){
593
  const Type *t2 = phase->type( in(2) );
594
  // Convert "x-c0" into "x+ -c0".
595
  if( t2->base() == Type::DoubleCon ) { // Might be bottom or top...
596
    // return new (phase->C, 3) AddDNode(in(1), phase->makecon( TypeD::make(-t2->getd()) ) );
597
  }
598

599
  // Cannot replace 0.0-X with -X because a 'dsub' bytecode computes
600
  // 0.0-0.0 as +0.0, while a 'dneg' bytecode computes -0.0.
601
  //if( phase->type(in(1)) == TypeD::ZERO )
602
  //return new (phase->C, 2) NegDNode(in(2));
603

604
  return nullptr;
605
}
606

607
//------------------------------sub--------------------------------------------
608
// A subtract node differences its two inputs.
609
const Type *SubDNode::sub( const Type *t1, const Type *t2 ) const {
610
  // no folding if one of operands is infinity or NaN, do not do constant folding
611
  if( g_isfinite(t1->getd()) && g_isfinite(t2->getd()) ) {
612
    return TypeD::make( t1->getd() - t2->getd() );
613
  }
614
  else if( g_isnan(t1->getd()) ) {
615
    return t1;
616
  }
617
  else if( g_isnan(t2->getd()) ) {
618
    return t2;
619
  }
620
  else {
621
    return Type::DOUBLE;
622
  }
623
}
624

625
//=============================================================================
626
//------------------------------Idealize---------------------------------------
627
// Unlike SubNodes, compare must still flatten return value to the
628
// range -1, 0, 1.
629
// And optimizations like those for (X + Y) - X fail if overflow happens.
630
Node* CmpNode::Identity(PhaseGVN* phase) {
631
  return this;
632
}
633

634
CmpNode *CmpNode::make(Node *in1, Node *in2, BasicType bt, bool unsigned_comp) {
635
  switch (bt) {
636
    case T_INT:
637
      if (unsigned_comp) {
638
        return new CmpUNode(in1, in2);
639
      }
640
      return new CmpINode(in1, in2);
641
    case T_LONG:
642
      if (unsigned_comp) {
643
        return new CmpULNode(in1, in2);
644
      }
645
      return new CmpLNode(in1, in2);
646
    case T_OBJECT:
647
    case T_ARRAY:
648
    case T_ADDRESS:
649
    case T_METADATA:
650
      return new CmpPNode(in1, in2);
651
    case T_NARROWOOP:
652
    case T_NARROWKLASS:
653
      return new CmpNNode(in1, in2);
654
    default:
655
      fatal("Not implemented for %s", type2name(bt));
656
  }
657
  return nullptr;
658
}
659

660
//=============================================================================
661
//------------------------------cmp--------------------------------------------
662
// Simplify a CmpI (compare 2 integers) node, based on local information.
663
// If both inputs are constants, compare them.
664
const Type *CmpINode::sub( const Type *t1, const Type *t2 ) const {
665
  const TypeInt *r0 = t1->is_int(); // Handy access
666
  const TypeInt *r1 = t2->is_int();
667

668
  if( r0->_hi < r1->_lo )       // Range is always low?
669
    return TypeInt::CC_LT;
670
  else if( r0->_lo > r1->_hi )  // Range is always high?
671
    return TypeInt::CC_GT;
672

673
  else if( r0->is_con() && r1->is_con() ) { // comparing constants?
674
    assert(r0->get_con() == r1->get_con(), "must be equal");
675
    return TypeInt::CC_EQ;      // Equal results.
676
  } else if( r0->_hi == r1->_lo ) // Range is never high?
677
    return TypeInt::CC_LE;
678
  else if( r0->_lo == r1->_hi ) // Range is never low?
679
    return TypeInt::CC_GE;
680
  return TypeInt::CC;           // else use worst case results
681
}
682

683
const Type* CmpINode::Value(PhaseGVN* phase) const {
684
  Node* in1 = in(1);
685
  Node* in2 = in(2);
686
  // If this test is the zero trip guard for a main or post loop, check whether, with the opaque node removed, the test
687
  // would constant fold so the loop is never entered. If so return the type of the test without the opaque node removed:
688
  // make the loop unreachable.
689
  // The reason for this is that the iv phi captures the bounds of the loop and if the loop becomes unreachable, it can
690
  // become top. In that case, the loop must be removed.
691
  // This is safe because:
692
  // - as optimizations proceed, the range of iterations executed by the main loop narrows. If no iterations remain, then
693
  // we're done with optimizations for that loop.
694
  // - the post loop is initially not reachable but as long as there's a main loop, the zero trip guard for the post
695
  // loop takes a phi that merges the pre and main loop's iv and can't constant fold the zero trip guard. Once, the main
696
  // loop is removed, there's no need to preserve the zero trip guard for the post loop anymore.
697
  if (in1 != nullptr && in2 != nullptr) {
698
    uint input = 0;
699
    Node* cmp = nullptr;
700
    BoolTest::mask test;
701
    if (in1->Opcode() == Op_OpaqueZeroTripGuard && phase->type(in1) != Type::TOP) {
702
      cmp = new CmpINode(in1->in(1), in2);
703
      test = ((OpaqueZeroTripGuardNode*)in1)->_loop_entered_mask;
704
    }
705
    if (in2->Opcode() == Op_OpaqueZeroTripGuard && phase->type(in2) != Type::TOP) {
706
      assert(cmp == nullptr, "A cmp with 2 OpaqueZeroTripGuard inputs");
707
      cmp = new CmpINode(in1, in2->in(1));
708
      test = ((OpaqueZeroTripGuardNode*)in2)->_loop_entered_mask;
709
    }
710
    if (cmp != nullptr) {
711
      const Type* cmp_t = cmp->Value(phase);
712
      const Type* t = BoolTest(test).cc2logical(cmp_t);
713
      cmp->destruct(phase);
714
      if (t == TypeInt::ZERO) {
715
        return cmp_t;
716
      }
717
    }
718
  }
719

720
  return SubNode::Value(phase);
721
}
722

723

724
// Simplify a CmpU (compare 2 integers) node, based on local information.
725
// If both inputs are constants, compare them.
726
const Type *CmpUNode::sub( const Type *t1, const Type *t2 ) const {
727
  assert(!t1->isa_ptr(), "obsolete usage of CmpU");
728

729
  // comparing two unsigned ints
730
  const TypeInt *r0 = t1->is_int();   // Handy access
731
  const TypeInt *r1 = t2->is_int();
732

733
  // Current installed version
734
  // Compare ranges for non-overlap
735
  juint lo0 = r0->_lo;
736
  juint hi0 = r0->_hi;
737
  juint lo1 = r1->_lo;
738
  juint hi1 = r1->_hi;
739

740
  // If either one has both negative and positive values,
741
  // it therefore contains both 0 and -1, and since [0..-1] is the
742
  // full unsigned range, the type must act as an unsigned bottom.
743
  bool bot0 = ((jint)(lo0 ^ hi0) < 0);
744
  bool bot1 = ((jint)(lo1 ^ hi1) < 0);
745

746
  if (bot0 || bot1) {
747
    // All unsigned values are LE -1 and GE 0.
748
    if (lo0 == 0 && hi0 == 0) {
749
      return TypeInt::CC_LE;            //   0 <= bot
750
    } else if ((jint)lo0 == -1 && (jint)hi0 == -1) {
751
      return TypeInt::CC_GE;            // -1 >= bot
752
    } else if (lo1 == 0 && hi1 == 0) {
753
      return TypeInt::CC_GE;            // bot >= 0
754
    } else if ((jint)lo1 == -1 && (jint)hi1 == -1) {
755
      return TypeInt::CC_LE;            // bot <= -1
756
    }
757
  } else {
758
    // We can use ranges of the form [lo..hi] if signs are the same.
759
    assert(lo0 <= hi0 && lo1 <= hi1, "unsigned ranges are valid");
760
    // results are reversed, '-' > '+' for unsigned compare
761
    if (hi0 < lo1) {
762
      return TypeInt::CC_LT;            // smaller
763
    } else if (lo0 > hi1) {
764
      return TypeInt::CC_GT;            // greater
765
    } else if (hi0 == lo1 && lo0 == hi1) {
766
      return TypeInt::CC_EQ;            // Equal results
767
    } else if (lo0 >= hi1) {
768
      return TypeInt::CC_GE;
769
    } else if (hi0 <= lo1) {
770
      // Check for special case in Hashtable::get.  (See below.)
771
      if ((jint)lo0 >= 0 && (jint)lo1 >= 0 && is_index_range_check())
772
        return TypeInt::CC_LT;
773
      return TypeInt::CC_LE;
774
    }
775
  }
776
  // Check for special case in Hashtable::get - the hash index is
777
  // mod'ed to the table size so the following range check is useless.
778
  // Check for: (X Mod Y) CmpU Y, where the mod result and Y both have
779
  // to be positive.
780
  // (This is a gross hack, since the sub method never
781
  // looks at the structure of the node in any other case.)
782
  if ((jint)lo0 >= 0 && (jint)lo1 >= 0 && is_index_range_check())
783
    return TypeInt::CC_LT;
784
  return TypeInt::CC;                   // else use worst case results
785
}
786

787
const Type* CmpUNode::Value(PhaseGVN* phase) const {
788
  const Type* t = SubNode::Value_common(phase);
789
  if (t != nullptr) {
790
    return t;
791
  }
792
  const Node* in1 = in(1);
793
  const Node* in2 = in(2);
794
  const Type* t1 = phase->type(in1);
795
  const Type* t2 = phase->type(in2);
796
  assert(t1->isa_int(), "CmpU has only Int type inputs");
797
  if (t2 == TypeInt::INT) { // Compare to bottom?
798
    return bottom_type();
799
  }
800

801
  const Type* t_sub = sub(t1, t2); // compare based on immediate inputs
802

803
  uint in1_op = in1->Opcode();
804
  if (in1_op == Op_AddI || in1_op == Op_SubI) {
805
    // The problem rise when result of AddI(SubI) may overflow
806
    // signed integer value. Let say the input type is
807
    // [256, maxint] then +128 will create 2 ranges due to
808
    // overflow: [minint, minint+127] and [384, maxint].
809
    // But C2 type system keep only 1 type range and as result
810
    // it use general [minint, maxint] for this case which we
811
    // can't optimize.
812
    //
813
    // Make 2 separate type ranges based on types of AddI(SubI) inputs
814
    // and compare results of their compare. If results are the same
815
    // CmpU node can be optimized.
816
    const Node* in11 = in1->in(1);
817
    const Node* in12 = in1->in(2);
818
    const Type* t11 = (in11 == in1) ? Type::TOP : phase->type(in11);
819
    const Type* t12 = (in12 == in1) ? Type::TOP : phase->type(in12);
820
    // Skip cases when input types are top or bottom.
821
    if ((t11 != Type::TOP) && (t11 != TypeInt::INT) &&
822
        (t12 != Type::TOP) && (t12 != TypeInt::INT)) {
823
      const TypeInt *r0 = t11->is_int();
824
      const TypeInt *r1 = t12->is_int();
825
      jlong lo_r0 = r0->_lo;
826
      jlong hi_r0 = r0->_hi;
827
      jlong lo_r1 = r1->_lo;
828
      jlong hi_r1 = r1->_hi;
829
      if (in1_op == Op_SubI) {
830
        jlong tmp = hi_r1;
831
        hi_r1 = -lo_r1;
832
        lo_r1 = -tmp;
833
        // Note, for substructing [minint,x] type range
834
        // long arithmetic provides correct overflow answer.
835
        // The confusion come from the fact that in 32-bit
836
        // -minint == minint but in 64-bit -minint == maxint+1.
837
      }
838
      jlong lo_long = lo_r0 + lo_r1;
839
      jlong hi_long = hi_r0 + hi_r1;
840
      int lo_tr1 = min_jint;
841
      int hi_tr1 = (int)hi_long;
842
      int lo_tr2 = (int)lo_long;
843
      int hi_tr2 = max_jint;
844
      bool underflow = lo_long != (jlong)lo_tr2;
845
      bool overflow  = hi_long != (jlong)hi_tr1;
846
      // Use sub(t1, t2) when there is no overflow (one type range)
847
      // or when both overflow and underflow (too complex).
848
      if ((underflow != overflow) && (hi_tr1 < lo_tr2)) {
849
        // Overflow only on one boundary, compare 2 separate type ranges.
850
        int w = MAX2(r0->_widen, r1->_widen); // _widen does not matter here
851
        const TypeInt* tr1 = TypeInt::make(lo_tr1, hi_tr1, w);
852
        const TypeInt* tr2 = TypeInt::make(lo_tr2, hi_tr2, w);
853
        const TypeInt* cmp1 = sub(tr1, t2)->is_int();
854
        const TypeInt* cmp2 = sub(tr2, t2)->is_int();
855
        // Compute union, so that cmp handles all possible results from the two cases
856
        const Type* t_cmp = cmp1->meet(cmp2);
857
        // Pick narrowest type, based on overflow computation and on immediate inputs
858
        return t_sub->filter(t_cmp);
859
      }
860
    }
861
  }
862

863
  return t_sub;
864
}
865

866
bool CmpUNode::is_index_range_check() const {
867
  // Check for the "(X ModI Y) CmpU Y" shape
868
  return (in(1)->Opcode() == Op_ModI &&
869
          in(1)->in(2)->eqv_uncast(in(2)));
870
}
871

872
//------------------------------Idealize---------------------------------------
873
Node *CmpINode::Ideal( PhaseGVN *phase, bool can_reshape ) {
874
  if (phase->type(in(2))->higher_equal(TypeInt::ZERO)) {
875
    switch (in(1)->Opcode()) {
876
    case Op_CmpU3:              // Collapse a CmpU3/CmpI into a CmpU
877
      return new CmpUNode(in(1)->in(1),in(1)->in(2));
878
    case Op_CmpL3:              // Collapse a CmpL3/CmpI into a CmpL
879
      return new CmpLNode(in(1)->in(1),in(1)->in(2));
880
    case Op_CmpUL3:             // Collapse a CmpUL3/CmpI into a CmpUL
881
      return new CmpULNode(in(1)->in(1),in(1)->in(2));
882
    case Op_CmpF3:              // Collapse a CmpF3/CmpI into a CmpF
883
      return new CmpFNode(in(1)->in(1),in(1)->in(2));
884
    case Op_CmpD3:              // Collapse a CmpD3/CmpI into a CmpD
885
      return new CmpDNode(in(1)->in(1),in(1)->in(2));
886
    //case Op_SubI:
887
      // If (x - y) cannot overflow, then ((x - y) <?> 0)
888
      // can be turned into (x <?> y).
889
      // This is handled (with more general cases) by Ideal_sub_algebra.
890
    }
891
  }
892
  return nullptr;                  // No change
893
}
894

895
Node *CmpLNode::Ideal( PhaseGVN *phase, bool can_reshape ) {
896
  const TypeLong *t2 = phase->type(in(2))->isa_long();
897
  if (Opcode() == Op_CmpL && in(1)->Opcode() == Op_ConvI2L && t2 && t2->is_con()) {
898
    const jlong con = t2->get_con();
899
    if (con >= min_jint && con <= max_jint) {
900
      return new CmpINode(in(1)->in(1), phase->intcon((jint)con));
901
    }
902
  }
903
  return nullptr;
904
}
905

906
//=============================================================================
907
// Simplify a CmpL (compare 2 longs ) node, based on local information.
908
// If both inputs are constants, compare them.
909
const Type *CmpLNode::sub( const Type *t1, const Type *t2 ) const {
910
  const TypeLong *r0 = t1->is_long(); // Handy access
911
  const TypeLong *r1 = t2->is_long();
912

913
  if( r0->_hi < r1->_lo )       // Range is always low?
914
    return TypeInt::CC_LT;
915
  else if( r0->_lo > r1->_hi )  // Range is always high?
916
    return TypeInt::CC_GT;
917

918
  else if( r0->is_con() && r1->is_con() ) { // comparing constants?
919
    assert(r0->get_con() == r1->get_con(), "must be equal");
920
    return TypeInt::CC_EQ;      // Equal results.
921
  } else if( r0->_hi == r1->_lo ) // Range is never high?
922
    return TypeInt::CC_LE;
923
  else if( r0->_lo == r1->_hi ) // Range is never low?
924
    return TypeInt::CC_GE;
925
  return TypeInt::CC;           // else use worst case results
926
}
927

928

929
// Simplify a CmpUL (compare 2 unsigned longs) node, based on local information.
930
// If both inputs are constants, compare them.
931
const Type* CmpULNode::sub(const Type* t1, const Type* t2) const {
932
  assert(!t1->isa_ptr(), "obsolete usage of CmpUL");
933

934
  // comparing two unsigned longs
935
  const TypeLong* r0 = t1->is_long();   // Handy access
936
  const TypeLong* r1 = t2->is_long();
937

938
  // Current installed version
939
  // Compare ranges for non-overlap
940
  julong lo0 = r0->_lo;
941
  julong hi0 = r0->_hi;
942
  julong lo1 = r1->_lo;
943
  julong hi1 = r1->_hi;
944

945
  // If either one has both negative and positive values,
946
  // it therefore contains both 0 and -1, and since [0..-1] is the
947
  // full unsigned range, the type must act as an unsigned bottom.
948
  bool bot0 = ((jlong)(lo0 ^ hi0) < 0);
949
  bool bot1 = ((jlong)(lo1 ^ hi1) < 0);
950

951
  if (bot0 || bot1) {
952
    // All unsigned values are LE -1 and GE 0.
953
    if (lo0 == 0 && hi0 == 0) {
954
      return TypeInt::CC_LE;            //   0 <= bot
955
    } else if ((jlong)lo0 == -1 && (jlong)hi0 == -1) {
956
      return TypeInt::CC_GE;            // -1 >= bot
957
    } else if (lo1 == 0 && hi1 == 0) {
958
      return TypeInt::CC_GE;            // bot >= 0
959
    } else if ((jlong)lo1 == -1 && (jlong)hi1 == -1) {
960
      return TypeInt::CC_LE;            // bot <= -1
961
    }
962
  } else {
963
    // We can use ranges of the form [lo..hi] if signs are the same.
964
    assert(lo0 <= hi0 && lo1 <= hi1, "unsigned ranges are valid");
965
    // results are reversed, '-' > '+' for unsigned compare
966
    if (hi0 < lo1) {
967
      return TypeInt::CC_LT;            // smaller
968
    } else if (lo0 > hi1) {
969
      return TypeInt::CC_GT;            // greater
970
    } else if (hi0 == lo1 && lo0 == hi1) {
971
      return TypeInt::CC_EQ;            // Equal results
972
    } else if (lo0 >= hi1) {
973
      return TypeInt::CC_GE;
974
    } else if (hi0 <= lo1) {
975
      return TypeInt::CC_LE;
976
    }
977
  }
978

979
  return TypeInt::CC;                   // else use worst case results
980
}
981

982
//=============================================================================
983
//------------------------------sub--------------------------------------------
984
// Simplify an CmpP (compare 2 pointers) node, based on local information.
985
// If both inputs are constants, compare them.
986
const Type *CmpPNode::sub( const Type *t1, const Type *t2 ) const {
987
  const TypePtr *r0 = t1->is_ptr(); // Handy access
988
  const TypePtr *r1 = t2->is_ptr();
989

990
  // Undefined inputs makes for an undefined result
991
  if( TypePtr::above_centerline(r0->_ptr) ||
992
      TypePtr::above_centerline(r1->_ptr) )
993
    return Type::TOP;
994

995
  if (r0 == r1 && r0->singleton()) {
996
    // Equal pointer constants (klasses, nulls, etc.)
997
    return TypeInt::CC_EQ;
998
  }
999

1000
  // See if it is 2 unrelated classes.
1001
  const TypeOopPtr* p0 = r0->isa_oopptr();
1002
  const TypeOopPtr* p1 = r1->isa_oopptr();
1003
  const TypeKlassPtr* k0 = r0->isa_klassptr();
1004
  const TypeKlassPtr* k1 = r1->isa_klassptr();
1005
  if ((p0 && p1) || (k0 && k1)) {
1006
    if (p0 && p1) {
1007
      Node* in1 = in(1)->uncast();
1008
      Node* in2 = in(2)->uncast();
1009
      AllocateNode* alloc1 = AllocateNode::Ideal_allocation(in1);
1010
      AllocateNode* alloc2 = AllocateNode::Ideal_allocation(in2);
1011
      if (MemNode::detect_ptr_independence(in1, alloc1, in2, alloc2, nullptr)) {
1012
        return TypeInt::CC_GT;  // different pointers
1013
      }
1014
    }
1015
    bool    xklass0 = p0 ? p0->klass_is_exact() : k0->klass_is_exact();
1016
    bool    xklass1 = p1 ? p1->klass_is_exact() : k1->klass_is_exact();
1017
    bool unrelated_classes = false;
1018

1019
    if ((p0 && p0->is_same_java_type_as(p1)) ||
1020
        (k0 && k0->is_same_java_type_as(k1))) {
1021
    } else if ((p0 && !p1->maybe_java_subtype_of(p0) && !p0->maybe_java_subtype_of(p1)) ||
1022
               (k0 && !k1->maybe_java_subtype_of(k0) && !k0->maybe_java_subtype_of(k1))) {
1023
      unrelated_classes = true;
1024
    } else if ((p0 && !p1->maybe_java_subtype_of(p0)) ||
1025
               (k0 && !k1->maybe_java_subtype_of(k0))) {
1026
      unrelated_classes = xklass1;
1027
    } else if ((p0 && !p0->maybe_java_subtype_of(p1)) ||
1028
               (k0 && !k0->maybe_java_subtype_of(k1))) {
1029
      unrelated_classes = xklass0;
1030
    }
1031

1032
    if (unrelated_classes) {
1033
      // The oops classes are known to be unrelated. If the joined PTRs of
1034
      // two oops is not Null and not Bottom, then we are sure that one
1035
      // of the two oops is non-null, and the comparison will always fail.
1036
      TypePtr::PTR jp = r0->join_ptr(r1->_ptr);
1037
      if (jp != TypePtr::Null && jp != TypePtr::BotPTR) {
1038
        return TypeInt::CC_GT;
1039
      }
1040
    }
1041
  }
1042

1043
  // Known constants can be compared exactly
1044
  // Null can be distinguished from any NotNull pointers
1045
  // Unknown inputs makes an unknown result
1046
  if( r0->singleton() ) {
1047
    intptr_t bits0 = r0->get_con();
1048
    if( r1->singleton() )
1049
      return bits0 == r1->get_con() ? TypeInt::CC_EQ : TypeInt::CC_GT;
1050
    return ( r1->_ptr == TypePtr::NotNull && bits0==0 ) ? TypeInt::CC_GT : TypeInt::CC;
1051
  } else if( r1->singleton() ) {
1052
    intptr_t bits1 = r1->get_con();
1053
    return ( r0->_ptr == TypePtr::NotNull && bits1==0 ) ? TypeInt::CC_GT : TypeInt::CC;
1054
  } else
1055
    return TypeInt::CC;
1056
}
1057

1058
static inline Node* isa_java_mirror_load(PhaseGVN* phase, Node* n) {
1059
  // Return the klass node for (indirect load from OopHandle)
1060
  //   LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
1061
  //   or null if not matching.
1062
  BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
1063
    n = bs->step_over_gc_barrier(n);
1064

1065
  if (n->Opcode() != Op_LoadP) return nullptr;
1066

1067
  const TypeInstPtr* tp = phase->type(n)->isa_instptr();
1068
  if (!tp || tp->instance_klass() != phase->C->env()->Class_klass()) return nullptr;
1069

1070
  Node* adr = n->in(MemNode::Address);
1071
  // First load from OopHandle: ((OopHandle)mirror)->resolve(); may need barrier.
1072
  if (adr->Opcode() != Op_LoadP || !phase->type(adr)->isa_rawptr()) return nullptr;
1073
  adr = adr->in(MemNode::Address);
1074

1075
  intptr_t off = 0;
1076
  Node* k = AddPNode::Ideal_base_and_offset(adr, phase, off);
1077
  if (k == nullptr)  return nullptr;
1078
  const TypeKlassPtr* tkp = phase->type(k)->isa_klassptr();
1079
  if (!tkp || off != in_bytes(Klass::java_mirror_offset())) return nullptr;
1080

1081
  // We've found the klass node of a Java mirror load.
1082
  return k;
1083
}
1084

1085
static inline Node* isa_const_java_mirror(PhaseGVN* phase, Node* n) {
1086
  // for ConP(Foo.class) return ConP(Foo.klass)
1087
  // otherwise return null
1088
  if (!n->is_Con()) return nullptr;
1089

1090
  const TypeInstPtr* tp = phase->type(n)->isa_instptr();
1091
  if (!tp) return nullptr;
1092

1093
  ciType* mirror_type = tp->java_mirror_type();
1094
  // TypeInstPtr::java_mirror_type() returns non-null for compile-
1095
  // time Class constants only.
1096
  if (!mirror_type) return nullptr;
1097

1098
  // x.getClass() == int.class can never be true (for all primitive types)
1099
  // Return a ConP(null) node for this case.
1100
  if (mirror_type->is_classless()) {
1101
    return phase->makecon(TypePtr::NULL_PTR);
1102
  }
1103

1104
  // return the ConP(Foo.klass)
1105
  assert(mirror_type->is_klass(), "mirror_type should represent a Klass*");
1106
  return phase->makecon(TypeKlassPtr::make(mirror_type->as_klass(), Type::trust_interfaces));
1107
}
1108

1109
//------------------------------Ideal------------------------------------------
1110
// Normalize comparisons between Java mirror loads to compare the klass instead.
1111
//
1112
// Also check for the case of comparing an unknown klass loaded from the primary
1113
// super-type array vs a known klass with no subtypes.  This amounts to
1114
// checking to see an unknown klass subtypes a known klass with no subtypes;
1115
// this only happens on an exact match.  We can shorten this test by 1 load.
1116
Node *CmpPNode::Ideal( PhaseGVN *phase, bool can_reshape ) {
1117
  // Normalize comparisons between Java mirrors into comparisons of the low-
1118
  // level klass, where a dependent load could be shortened.
1119
  //
1120
  // The new pattern has a nice effect of matching the same pattern used in the
1121
  // fast path of instanceof/checkcast/Class.isInstance(), which allows
1122
  // redundant exact type check be optimized away by GVN.
1123
  // For example, in
1124
  //   if (x.getClass() == Foo.class) {
1125
  //     Foo foo = (Foo) x;
1126
  //     // ... use a ...
1127
  //   }
1128
  // a CmpPNode could be shared between if_acmpne and checkcast
1129
  {
1130
    Node* k1 = isa_java_mirror_load(phase, in(1));
1131
    Node* k2 = isa_java_mirror_load(phase, in(2));
1132
    Node* conk2 = isa_const_java_mirror(phase, in(2));
1133

1134
    if (k1 && (k2 || conk2)) {
1135
      Node* lhs = k1;
1136
      Node* rhs = (k2 != nullptr) ? k2 : conk2;
1137
      set_req_X(1, lhs, phase);
1138
      set_req_X(2, rhs, phase);
1139
      return this;
1140
    }
1141
  }
1142

1143
  // Constant pointer on right?
1144
  const TypeKlassPtr* t2 = phase->type(in(2))->isa_klassptr();
1145
  if (t2 == nullptr || !t2->klass_is_exact())
1146
    return nullptr;
1147
  // Get the constant klass we are comparing to.
1148
  ciKlass* superklass = t2->exact_klass();
1149

1150
  // Now check for LoadKlass on left.
1151
  Node* ldk1 = in(1);
1152
  if (ldk1->is_DecodeNKlass()) {
1153
    ldk1 = ldk1->in(1);
1154
    if (ldk1->Opcode() != Op_LoadNKlass )
1155
      return nullptr;
1156
  } else if (ldk1->Opcode() != Op_LoadKlass )
1157
    return nullptr;
1158
  // Take apart the address of the LoadKlass:
1159
  Node* adr1 = ldk1->in(MemNode::Address);
1160
  intptr_t con2 = 0;
1161
  Node* ldk2 = AddPNode::Ideal_base_and_offset(adr1, phase, con2);
1162
  if (ldk2 == nullptr)
1163
    return nullptr;
1164
  if (con2 == oopDesc::klass_offset_in_bytes()) {
1165
    // We are inspecting an object's concrete class.
1166
    // Short-circuit the check if the query is abstract.
1167
    if (superklass->is_interface() ||
1168
        superklass->is_abstract()) {
1169
      // Make it come out always false:
1170
      this->set_req(2, phase->makecon(TypePtr::NULL_PTR));
1171
      return this;
1172
    }
1173
  }
1174

1175
  // Check for a LoadKlass from primary supertype array.
1176
  // Any nested loadklass from loadklass+con must be from the p.s. array.
1177
  if (ldk2->is_DecodeNKlass()) {
1178
    // Keep ldk2 as DecodeN since it could be used in CmpP below.
1179
    if (ldk2->in(1)->Opcode() != Op_LoadNKlass )
1180
      return nullptr;
1181
  } else if (ldk2->Opcode() != Op_LoadKlass)
1182
    return nullptr;
1183

1184
  // Verify that we understand the situation
1185
  if (con2 != (intptr_t) superklass->super_check_offset())
1186
    return nullptr;                // Might be element-klass loading from array klass
1187

1188
  // If 'superklass' has no subklasses and is not an interface, then we are
1189
  // assured that the only input which will pass the type check is
1190
  // 'superklass' itself.
1191
  //
1192
  // We could be more liberal here, and allow the optimization on interfaces
1193
  // which have a single implementor.  This would require us to increase the
1194
  // expressiveness of the add_dependency() mechanism.
1195
  // %%% Do this after we fix TypeOopPtr:  Deps are expressive enough now.
1196

1197
  // Object arrays must have their base element have no subtypes
1198
  while (superklass->is_obj_array_klass()) {
1199
    ciType* elem = superklass->as_obj_array_klass()->element_type();
1200
    superklass = elem->as_klass();
1201
  }
1202
  if (superklass->is_instance_klass()) {
1203
    ciInstanceKlass* ik = superklass->as_instance_klass();
1204
    if (ik->has_subklass() || ik->is_interface())  return nullptr;
1205
    // Add a dependency if there is a chance that a subclass will be added later.
1206
    if (!ik->is_final()) {
1207
      phase->C->dependencies()->assert_leaf_type(ik);
1208
    }
1209
  }
1210

1211
  // Bypass the dependent load, and compare directly
1212
  this->set_req_X(1, ldk2, phase);
1213

1214
  return this;
1215
}
1216

1217
//=============================================================================
1218
//------------------------------sub--------------------------------------------
1219
// Simplify an CmpN (compare 2 pointers) node, based on local information.
1220
// If both inputs are constants, compare them.
1221
const Type *CmpNNode::sub( const Type *t1, const Type *t2 ) const {
1222
  ShouldNotReachHere();
1223
  return bottom_type();
1224
}
1225

1226
//------------------------------Ideal------------------------------------------
1227
Node *CmpNNode::Ideal( PhaseGVN *phase, bool can_reshape ) {
1228
  return nullptr;
1229
}
1230

1231
//=============================================================================
1232
//------------------------------Value------------------------------------------
1233
// Simplify an CmpF (compare 2 floats ) node, based on local information.
1234
// If both inputs are constants, compare them.
1235
const Type* CmpFNode::Value(PhaseGVN* phase) const {
1236
  const Node* in1 = in(1);
1237
  const Node* in2 = in(2);
1238
  // Either input is TOP ==> the result is TOP
1239
  const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);
1240
  if( t1 == Type::TOP ) return Type::TOP;
1241
  const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);
1242
  if( t2 == Type::TOP ) return Type::TOP;
1243

1244
  // Not constants?  Don't know squat - even if they are the same
1245
  // value!  If they are NaN's they compare to LT instead of EQ.
1246
  const TypeF *tf1 = t1->isa_float_constant();
1247
  const TypeF *tf2 = t2->isa_float_constant();
1248
  if( !tf1 || !tf2 ) return TypeInt::CC;
1249

1250
  // This implements the Java bytecode fcmpl, so unordered returns -1.
1251
  if( tf1->is_nan() || tf2->is_nan() )
1252
    return TypeInt::CC_LT;
1253

1254
  if( tf1->_f < tf2->_f ) return TypeInt::CC_LT;
1255
  if( tf1->_f > tf2->_f ) return TypeInt::CC_GT;
1256
  assert( tf1->_f == tf2->_f, "do not understand FP behavior" );
1257
  return TypeInt::CC_EQ;
1258
}
1259

1260

1261
//=============================================================================
1262
//------------------------------Value------------------------------------------
1263
// Simplify an CmpD (compare 2 doubles ) node, based on local information.
1264
// If both inputs are constants, compare them.
1265
const Type* CmpDNode::Value(PhaseGVN* phase) const {
1266
  const Node* in1 = in(1);
1267
  const Node* in2 = in(2);
1268
  // Either input is TOP ==> the result is TOP
1269
  const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);
1270
  if( t1 == Type::TOP ) return Type::TOP;
1271
  const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);
1272
  if( t2 == Type::TOP ) return Type::TOP;
1273

1274
  // Not constants?  Don't know squat - even if they are the same
1275
  // value!  If they are NaN's they compare to LT instead of EQ.
1276
  const TypeD *td1 = t1->isa_double_constant();
1277
  const TypeD *td2 = t2->isa_double_constant();
1278
  if( !td1 || !td2 ) return TypeInt::CC;
1279

1280
  // This implements the Java bytecode dcmpl, so unordered returns -1.
1281
  if( td1->is_nan() || td2->is_nan() )
1282
    return TypeInt::CC_LT;
1283

1284
  if( td1->_d < td2->_d ) return TypeInt::CC_LT;
1285
  if( td1->_d > td2->_d ) return TypeInt::CC_GT;
1286
  assert( td1->_d == td2->_d, "do not understand FP behavior" );
1287
  return TypeInt::CC_EQ;
1288
}
1289

1290
//------------------------------Ideal------------------------------------------
1291
Node *CmpDNode::Ideal(PhaseGVN *phase, bool can_reshape){
1292
  // Check if we can change this to a CmpF and remove a ConvD2F operation.
1293
  // Change  (CMPD (F2D (float)) (ConD value))
1294
  // To      (CMPF      (float)  (ConF value))
1295
  // Valid when 'value' does not lose precision as a float.
1296
  // Benefits: eliminates conversion, does not require 24-bit mode
1297

1298
  // NaNs prevent commuting operands.  This transform works regardless of the
1299
  // order of ConD and ConvF2D inputs by preserving the original order.
1300
  int idx_f2d = 1;              // ConvF2D on left side?
1301
  if( in(idx_f2d)->Opcode() != Op_ConvF2D )
1302
    idx_f2d = 2;                // No, swap to check for reversed args
1303
  int idx_con = 3-idx_f2d;      // Check for the constant on other input
1304

1305
  if( ConvertCmpD2CmpF &&
1306
      in(idx_f2d)->Opcode() == Op_ConvF2D &&
1307
      in(idx_con)->Opcode() == Op_ConD ) {
1308
    const TypeD *t2 = in(idx_con)->bottom_type()->is_double_constant();
1309
    double t2_value_as_double = t2->_d;
1310
    float  t2_value_as_float  = (float)t2_value_as_double;
1311
    if( t2_value_as_double == (double)t2_value_as_float ) {
1312
      // Test value can be represented as a float
1313
      // Eliminate the conversion to double and create new comparison
1314
      Node *new_in1 = in(idx_f2d)->in(1);
1315
      Node *new_in2 = phase->makecon( TypeF::make(t2_value_as_float) );
1316
      if( idx_f2d != 1 ) {      // Must flip args to match original order
1317
        Node *tmp = new_in1;
1318
        new_in1 = new_in2;
1319
        new_in2 = tmp;
1320
      }
1321
      CmpFNode *new_cmp = (Opcode() == Op_CmpD3)
1322
        ? new CmpF3Node( new_in1, new_in2 )
1323
        : new CmpFNode ( new_in1, new_in2 ) ;
1324
      return new_cmp;           // Changed to CmpFNode
1325
    }
1326
    // Testing value required the precision of a double
1327
  }
1328
  return nullptr;                  // No change
1329
}
1330

1331

1332
//=============================================================================
1333
//------------------------------cc2logical-------------------------------------
1334
// Convert a condition code type to a logical type
1335
const Type *BoolTest::cc2logical( const Type *CC ) const {
1336
  if( CC == Type::TOP ) return Type::TOP;
1337
  if( CC->base() != Type::Int ) return TypeInt::BOOL; // Bottom or worse
1338
  const TypeInt *ti = CC->is_int();
1339
  if( ti->is_con() ) {          // Only 1 kind of condition codes set?
1340
    // Match low order 2 bits
1341
    int tmp = ((ti->get_con()&3) == (_test&3)) ? 1 : 0;
1342
    if( _test & 4 ) tmp = 1-tmp;     // Optionally complement result
1343
    return TypeInt::make(tmp);       // Boolean result
1344
  }
1345

1346
  if( CC == TypeInt::CC_GE ) {
1347
    if( _test == ge ) return TypeInt::ONE;
1348
    if( _test == lt ) return TypeInt::ZERO;
1349
  }
1350
  if( CC == TypeInt::CC_LE ) {
1351
    if( _test == le ) return TypeInt::ONE;
1352
    if( _test == gt ) return TypeInt::ZERO;
1353
  }
1354

1355
  return TypeInt::BOOL;
1356
}
1357

1358
//------------------------------dump_spec-------------------------------------
1359
// Print special per-node info
1360
void BoolTest::dump_on(outputStream *st) const {
1361
  const char *msg[] = {"eq","gt","of","lt","ne","le","nof","ge"};
1362
  st->print("%s", msg[_test]);
1363
}
1364

1365
// Returns the logical AND of two tests (or 'never' if both tests can never be true).
1366
// For example, a test for 'le' followed by a test for 'lt' is equivalent with 'lt'.
1367
BoolTest::mask BoolTest::merge(BoolTest other) const {
1368
  const mask res[illegal+1][illegal+1] = {
1369
    // eq,      gt,      of,      lt,      ne,      le,      nof,     ge,      never,   illegal
1370
      {eq,      never,   illegal, never,   never,   eq,      illegal, eq,      never,   illegal},  // eq
1371
      {never,   gt,      illegal, never,   gt,      never,   illegal, gt,      never,   illegal},  // gt
1372
      {illegal, illegal, illegal, illegal, illegal, illegal, illegal, illegal, never,   illegal},  // of
1373
      {never,   never,   illegal, lt,      lt,      lt,      illegal, never,   never,   illegal},  // lt
1374
      {never,   gt,      illegal, lt,      ne,      lt,      illegal, gt,      never,   illegal},  // ne
1375
      {eq,      never,   illegal, lt,      lt,      le,      illegal, eq,      never,   illegal},  // le
1376
      {illegal, illegal, illegal, illegal, illegal, illegal, illegal, illegal, never,   illegal},  // nof
1377
      {eq,      gt,      illegal, never,   gt,      eq,      illegal, ge,      never,   illegal},  // ge
1378
      {never,   never,   never,   never,   never,   never,   never,   never,   never,   illegal},  // never
1379
      {illegal, illegal, illegal, illegal, illegal, illegal, illegal, illegal, illegal, illegal}}; // illegal
1380
  return res[_test][other._test];
1381
}
1382

1383
//=============================================================================
1384
uint BoolNode::hash() const { return (Node::hash() << 3)|(_test._test+1); }
1385
uint BoolNode::size_of() const { return sizeof(BoolNode); }
1386

1387
//------------------------------operator==-------------------------------------
1388
bool BoolNode::cmp( const Node &n ) const {
1389
  const BoolNode *b = (const BoolNode *)&n; // Cast up
1390
  return (_test._test == b->_test._test);
1391
}
1392

1393
//-------------------------------make_predicate--------------------------------
1394
Node* BoolNode::make_predicate(Node* test_value, PhaseGVN* phase) {
1395
  if (test_value->is_Con())   return test_value;
1396
  if (test_value->is_Bool())  return test_value;
1397
  if (test_value->is_CMove() &&
1398
      test_value->in(CMoveNode::Condition)->is_Bool()) {
1399
    BoolNode*   bol   = test_value->in(CMoveNode::Condition)->as_Bool();
1400
    const Type* ftype = phase->type(test_value->in(CMoveNode::IfFalse));
1401
    const Type* ttype = phase->type(test_value->in(CMoveNode::IfTrue));
1402
    if (ftype == TypeInt::ZERO && !TypeInt::ZERO->higher_equal(ttype)) {
1403
      return bol;
1404
    } else if (ttype == TypeInt::ZERO && !TypeInt::ZERO->higher_equal(ftype)) {
1405
      return phase->transform( bol->negate(phase) );
1406
    }
1407
    // Else fall through.  The CMove gets in the way of the test.
1408
    // It should be the case that make_predicate(bol->as_int_value()) == bol.
1409
  }
1410
  Node* cmp = new CmpINode(test_value, phase->intcon(0));
1411
  cmp = phase->transform(cmp);
1412
  Node* bol = new BoolNode(cmp, BoolTest::ne);
1413
  return phase->transform(bol);
1414
}
1415

1416
//--------------------------------as_int_value---------------------------------
1417
Node* BoolNode::as_int_value(PhaseGVN* phase) {
1418
  // Inverse to make_predicate.  The CMove probably boils down to a Conv2B.
1419
  Node* cmov = CMoveNode::make(nullptr, this,
1420
                               phase->intcon(0), phase->intcon(1),
1421
                               TypeInt::BOOL);
1422
  return phase->transform(cmov);
1423
}
1424

1425
//----------------------------------negate-------------------------------------
1426
BoolNode* BoolNode::negate(PhaseGVN* phase) {
1427
  return new BoolNode(in(1), _test.negate());
1428
}
1429

1430
// Change "bool eq/ne (cmp (add/sub A B) C)" into false/true if add/sub
1431
// overflows and we can prove that C is not in the two resulting ranges.
1432
// This optimization is similar to the one performed by CmpUNode::Value().
1433
Node* BoolNode::fold_cmpI(PhaseGVN* phase, SubNode* cmp, Node* cmp1, int cmp_op,
1434
                          int cmp1_op, const TypeInt* cmp2_type) {
1435
  // Only optimize eq/ne integer comparison of add/sub
1436
  if((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1437
     (cmp_op == Op_CmpI) && (cmp1_op == Op_AddI || cmp1_op == Op_SubI)) {
1438
    // Skip cases were inputs of add/sub are not integers or of bottom type
1439
    const TypeInt* r0 = phase->type(cmp1->in(1))->isa_int();
1440
    const TypeInt* r1 = phase->type(cmp1->in(2))->isa_int();
1441
    if ((r0 != nullptr) && (r0 != TypeInt::INT) &&
1442
        (r1 != nullptr) && (r1 != TypeInt::INT) &&
1443
        (cmp2_type != TypeInt::INT)) {
1444
      // Compute exact (long) type range of add/sub result
1445
      jlong lo_long = r0->_lo;
1446
      jlong hi_long = r0->_hi;
1447
      if (cmp1_op == Op_AddI) {
1448
        lo_long += r1->_lo;
1449
        hi_long += r1->_hi;
1450
      } else {
1451
        lo_long -= r1->_hi;
1452
        hi_long -= r1->_lo;
1453
      }
1454
      // Check for over-/underflow by casting to integer
1455
      int lo_int = (int)lo_long;
1456
      int hi_int = (int)hi_long;
1457
      bool underflow = lo_long != (jlong)lo_int;
1458
      bool overflow  = hi_long != (jlong)hi_int;
1459
      if ((underflow != overflow) && (hi_int < lo_int)) {
1460
        // Overflow on one boundary, compute resulting type ranges:
1461
        // tr1 [MIN_INT, hi_int] and tr2 [lo_int, MAX_INT]
1462
        int w = MAX2(r0->_widen, r1->_widen); // _widen does not matter here
1463
        const TypeInt* tr1 = TypeInt::make(min_jint, hi_int, w);
1464
        const TypeInt* tr2 = TypeInt::make(lo_int, max_jint, w);
1465
        // Compare second input of cmp to both type ranges
1466
        const Type* sub_tr1 = cmp->sub(tr1, cmp2_type);
1467
        const Type* sub_tr2 = cmp->sub(tr2, cmp2_type);
1468
        if (sub_tr1 == TypeInt::CC_LT && sub_tr2 == TypeInt::CC_GT) {
1469
          // The result of the add/sub will never equal cmp2. Replace BoolNode
1470
          // by false (0) if it tests for equality and by true (1) otherwise.
1471
          return ConINode::make((_test._test == BoolTest::eq) ? 0 : 1);
1472
        }
1473
      }
1474
    }
1475
  }
1476
  return nullptr;
1477
}
1478

1479
static bool is_counted_loop_cmp(Node *cmp) {
1480
  Node *n = cmp->in(1)->in(1);
1481
  return n != nullptr &&
1482
         n->is_Phi() &&
1483
         n->in(0) != nullptr &&
1484
         n->in(0)->is_CountedLoop() &&
1485
         n->in(0)->as_CountedLoop()->phi() == n;
1486
}
1487

1488
//------------------------------Ideal------------------------------------------
1489
Node *BoolNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1490
  // Change "bool tst (cmp con x)" into "bool ~tst (cmp x con)".
1491
  // This moves the constant to the right.  Helps value-numbering.
1492
  Node *cmp = in(1);
1493
  if( !cmp->is_Sub() ) return nullptr;
1494
  int cop = cmp->Opcode();
1495
  if( cop == Op_FastLock || cop == Op_FastUnlock ||
1496
      cmp->is_SubTypeCheck() || cop == Op_VectorTest ) {
1497
    return nullptr;
1498
  }
1499
  Node *cmp1 = cmp->in(1);
1500
  Node *cmp2 = cmp->in(2);
1501
  if( !cmp1 ) return nullptr;
1502

1503
  if (_test._test == BoolTest::overflow || _test._test == BoolTest::no_overflow) {
1504
    return nullptr;
1505
  }
1506

1507
  const int cmp1_op = cmp1->Opcode();
1508
  const int cmp2_op = cmp2->Opcode();
1509

1510
  // Constant on left?
1511
  Node *con = cmp1;
1512
  // Move constants to the right of compare's to canonicalize.
1513
  // Do not muck with Opaque1 nodes, as this indicates a loop
1514
  // guard that cannot change shape.
1515
  if (con->is_Con() && !cmp2->is_Con() && cmp2_op != Op_OpaqueZeroTripGuard &&
1516
      // Because of NaN's, CmpD and CmpF are not commutative
1517
      cop != Op_CmpD && cop != Op_CmpF &&
1518
      // Protect against swapping inputs to a compare when it is used by a
1519
      // counted loop exit, which requires maintaining the loop-limit as in(2)
1520
      !is_counted_loop_exit_test() ) {
1521
    // Ok, commute the constant to the right of the cmp node.
1522
    // Clone the Node, getting a new Node of the same class
1523
    cmp = cmp->clone();
1524
    // Swap inputs to the clone
1525
    cmp->swap_edges(1, 2);
1526
    cmp = phase->transform( cmp );
1527
    return new BoolNode( cmp, _test.commute() );
1528
  }
1529

1530
  // Change "bool eq/ne (cmp (cmove (bool tst (cmp2)) 1 0) 0)" into "bool tst/~tst (cmp2)"
1531
  if (cop == Op_CmpI &&
1532
      (_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1533
      cmp1_op == Op_CMoveI && cmp2->find_int_con(1) == 0) {
1534
    // 0 should be on the true branch
1535
    if (cmp1->in(CMoveNode::Condition)->is_Bool() &&
1536
        cmp1->in(CMoveNode::IfTrue)->find_int_con(1) == 0 &&
1537
        cmp1->in(CMoveNode::IfFalse)->find_int_con(0) != 0) {
1538
      BoolNode* target = cmp1->in(CMoveNode::Condition)->as_Bool();
1539
      return new BoolNode(target->in(1),
1540
                          (_test._test == BoolTest::eq) ? target->_test._test :
1541
                                                          target->_test.negate());
1542
    }
1543
  }
1544

1545
  // Change "bool eq/ne (cmp (and X 16) 16)" into "bool ne/eq (cmp (and X 16) 0)".
1546
  if (cop == Op_CmpI &&
1547
      (_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1548
      cmp1_op == Op_AndI && cmp2_op == Op_ConI &&
1549
      cmp1->in(2)->Opcode() == Op_ConI) {
1550
    const TypeInt *t12 = phase->type(cmp2)->isa_int();
1551
    const TypeInt *t112 = phase->type(cmp1->in(2))->isa_int();
1552
    if (t12 && t12->is_con() && t112 && t112->is_con() &&
1553
        t12->get_con() == t112->get_con() && is_power_of_2(t12->get_con())) {
1554
      Node *ncmp = phase->transform(new CmpINode(cmp1, phase->intcon(0)));
1555
      return new BoolNode(ncmp, _test.negate());
1556
    }
1557
  }
1558

1559
  // Same for long type: change "bool eq/ne (cmp (and X 16) 16)" into "bool ne/eq (cmp (and X 16) 0)".
1560
  if (cop == Op_CmpL &&
1561
      (_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1562
      cmp1_op == Op_AndL && cmp2_op == Op_ConL &&
1563
      cmp1->in(2)->Opcode() == Op_ConL) {
1564
    const TypeLong *t12 = phase->type(cmp2)->isa_long();
1565
    const TypeLong *t112 = phase->type(cmp1->in(2))->isa_long();
1566
    if (t12 && t12->is_con() && t112 && t112->is_con() &&
1567
        t12->get_con() == t112->get_con() && is_power_of_2(t12->get_con())) {
1568
      Node *ncmp = phase->transform(new CmpLNode(cmp1, phase->longcon(0)));
1569
      return new BoolNode(ncmp, _test.negate());
1570
    }
1571
  }
1572

1573
  // Change "cmp (add X min_jint) (add Y min_jint)" into "cmpu X Y"
1574
  // and    "cmp (add X min_jint) c" into "cmpu X (c + min_jint)"
1575
  if (cop == Op_CmpI &&
1576
      cmp1_op == Op_AddI &&
1577
      phase->type(cmp1->in(2)) == TypeInt::MIN &&
1578
      !is_cloop_condition(this)) {
1579
    if (cmp2_op == Op_ConI) {
1580
      Node* ncmp2 = phase->intcon(java_add(cmp2->get_int(), min_jint));
1581
      Node* ncmp = phase->transform(new CmpUNode(cmp1->in(1), ncmp2));
1582
      return new BoolNode(ncmp, _test._test);
1583
    } else if (cmp2_op == Op_AddI &&
1584
               phase->type(cmp2->in(2)) == TypeInt::MIN &&
1585
               !is_cloop_condition(this)) {
1586
      Node* ncmp = phase->transform(new CmpUNode(cmp1->in(1), cmp2->in(1)));
1587
      return new BoolNode(ncmp, _test._test);
1588
    }
1589
  }
1590

1591
  // Change "cmp (add X min_jlong) (add Y min_jlong)" into "cmpu X Y"
1592
  // and    "cmp (add X min_jlong) c" into "cmpu X (c + min_jlong)"
1593
  if (cop == Op_CmpL &&
1594
      cmp1_op == Op_AddL &&
1595
      phase->type(cmp1->in(2)) == TypeLong::MIN &&
1596
      !is_cloop_condition(this)) {
1597
    if (cmp2_op == Op_ConL) {
1598
      Node* ncmp2 = phase->longcon(java_add(cmp2->get_long(), min_jlong));
1599
      Node* ncmp = phase->transform(new CmpULNode(cmp1->in(1), ncmp2));
1600
      return new BoolNode(ncmp, _test._test);
1601
    } else if (cmp2_op == Op_AddL &&
1602
               phase->type(cmp2->in(2)) == TypeLong::MIN &&
1603
               !is_cloop_condition(this)) {
1604
      Node* ncmp = phase->transform(new CmpULNode(cmp1->in(1), cmp2->in(1)));
1605
      return new BoolNode(ncmp, _test._test);
1606
    }
1607
  }
1608

1609
  // Change "bool eq/ne (cmp (xor X 1) 0)" into "bool ne/eq (cmp X 0)".
1610
  // The XOR-1 is an idiom used to flip the sense of a bool.  We flip the
1611
  // test instead.
1612
  const TypeInt* cmp2_type = phase->type(cmp2)->isa_int();
1613
  if (cmp2_type == nullptr)  return nullptr;
1614
  Node* j_xor = cmp1;
1615
  if( cmp2_type == TypeInt::ZERO &&
1616
      cmp1_op == Op_XorI &&
1617
      j_xor->in(1) != j_xor &&          // An xor of itself is dead
1618
      phase->type( j_xor->in(1) ) == TypeInt::BOOL &&
1619
      phase->type( j_xor->in(2) ) == TypeInt::ONE &&
1620
      (_test._test == BoolTest::eq ||
1621
       _test._test == BoolTest::ne) ) {
1622
    Node *ncmp = phase->transform(new CmpINode(j_xor->in(1),cmp2));
1623
    return new BoolNode( ncmp, _test.negate() );
1624
  }
1625

1626
  // Change ((x & m) u<= m) or ((m & x) u<= m) to always true
1627
  // Same with ((x & m) u< m+1) and ((m & x) u< m+1)
1628
  if (cop == Op_CmpU &&
1629
      cmp1_op == Op_AndI) {
1630
    Node* bound = nullptr;
1631
    if (_test._test == BoolTest::le) {
1632
      bound = cmp2;
1633
    } else if (_test._test == BoolTest::lt &&
1634
               cmp2->Opcode() == Op_AddI &&
1635
               cmp2->in(2)->find_int_con(0) == 1) {
1636
      bound = cmp2->in(1);
1637
    }
1638
    if (cmp1->in(2) == bound || cmp1->in(1) == bound) {
1639
      return ConINode::make(1);
1640
    }
1641
  }
1642

1643
  // Change ((x & (m - 1)) u< m) into (m > 0)
1644
  // This is the off-by-one variant of the above
1645
  if (cop == Op_CmpU &&
1646
      _test._test == BoolTest::lt &&
1647
      cmp1_op == Op_AndI) {
1648
    Node* l = cmp1->in(1);
1649
    Node* r = cmp1->in(2);
1650
    for (int repeat = 0; repeat < 2; repeat++) {
1651
      bool match = r->Opcode() == Op_AddI && r->in(2)->find_int_con(0) == -1 &&
1652
                   r->in(1) == cmp2;
1653
      if (match) {
1654
        // arraylength known to be non-negative, so a (arraylength != 0) is sufficient,
1655
        // but to be compatible with the array range check pattern, use (arraylength u> 0)
1656
        Node* ncmp = cmp2->Opcode() == Op_LoadRange
1657
                     ? phase->transform(new CmpUNode(cmp2, phase->intcon(0)))
1658
                     : phase->transform(new CmpINode(cmp2, phase->intcon(0)));
1659
        return new BoolNode(ncmp, BoolTest::gt);
1660
      } else {
1661
        // commute and try again
1662
        l = cmp1->in(2);
1663
        r = cmp1->in(1);
1664
      }
1665
    }
1666
  }
1667

1668
  // Change x u< 1 or x u<= 0 to x == 0
1669
  // and    x u> 0 or u>= 1   to x != 0
1670
  if (cop == Op_CmpU &&
1671
      cmp1_op != Op_LoadRange &&
1672
      (((_test._test == BoolTest::lt || _test._test == BoolTest::ge) &&
1673
        cmp2->find_int_con(-1) == 1) ||
1674
       ((_test._test == BoolTest::le || _test._test == BoolTest::gt) &&
1675
        cmp2->find_int_con(-1) == 0))) {
1676
    Node* ncmp = phase->transform(new CmpINode(cmp1, phase->intcon(0)));
1677
    return new BoolNode(ncmp, _test.is_less() ? BoolTest::eq : BoolTest::ne);
1678
  }
1679

1680
  // Change (arraylength <= 0) or (arraylength == 0)
1681
  //   into (arraylength u<= 0)
1682
  // Also change (arraylength != 0) into (arraylength u> 0)
1683
  // The latter version matches the code pattern generated for
1684
  // array range checks, which will more likely be optimized later.
1685
  if (cop == Op_CmpI &&
1686
      cmp1_op == Op_LoadRange &&
1687
      cmp2->find_int_con(-1) == 0) {
1688
    if (_test._test == BoolTest::le || _test._test == BoolTest::eq) {
1689
      Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
1690
      return new BoolNode(ncmp, BoolTest::le);
1691
    } else if (_test._test == BoolTest::ne) {
1692
      Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
1693
      return new BoolNode(ncmp, BoolTest::gt);
1694
    }
1695
  }
1696

1697
  // Change "bool eq/ne (cmp (Conv2B X) 0)" into "bool eq/ne (cmp X 0)".
1698
  // This is a standard idiom for branching on a boolean value.
1699
  Node *c2b = cmp1;
1700
  if( cmp2_type == TypeInt::ZERO &&
1701
      cmp1_op == Op_Conv2B &&
1702
      (_test._test == BoolTest::eq ||
1703
       _test._test == BoolTest::ne) ) {
1704
    Node *ncmp = phase->transform(phase->type(c2b->in(1))->isa_int()
1705
       ? (Node*)new CmpINode(c2b->in(1),cmp2)
1706
       : (Node*)new CmpPNode(c2b->in(1),phase->makecon(TypePtr::NULL_PTR))
1707
    );
1708
    return new BoolNode( ncmp, _test._test );
1709
  }
1710

1711
  // Comparing a SubI against a zero is equal to comparing the SubI
1712
  // arguments directly.  This only works for eq and ne comparisons
1713
  // due to possible integer overflow.
1714
  if ((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1715
        (cop == Op_CmpI) &&
1716
        (cmp1_op == Op_SubI) &&
1717
        ( cmp2_type == TypeInt::ZERO ) ) {
1718
    Node *ncmp = phase->transform( new CmpINode(cmp1->in(1),cmp1->in(2)));
1719
    return new BoolNode( ncmp, _test._test );
1720
  }
1721

1722
  // Same as above but with and AddI of a constant
1723
  if ((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1724
      cop == Op_CmpI &&
1725
      cmp1_op == Op_AddI &&
1726
      cmp1->in(2) != nullptr &&
1727
      phase->type(cmp1->in(2))->isa_int() &&
1728
      phase->type(cmp1->in(2))->is_int()->is_con() &&
1729
      cmp2_type == TypeInt::ZERO &&
1730
      !is_counted_loop_cmp(cmp) // modifying the exit test of a counted loop messes the counted loop shape
1731
      ) {
1732
    const TypeInt* cmp1_in2 = phase->type(cmp1->in(2))->is_int();
1733
    Node *ncmp = phase->transform( new CmpINode(cmp1->in(1),phase->intcon(-cmp1_in2->_hi)));
1734
    return new BoolNode( ncmp, _test._test );
1735
  }
1736

1737
  // Change "bool eq/ne (cmp (phi (X -X) 0))" into "bool eq/ne (cmp X 0)"
1738
  // since zero check of conditional negation of an integer is equal to
1739
  // zero check of the integer directly.
1740
  if ((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1741
      (cop == Op_CmpI) &&
1742
      (cmp2_type == TypeInt::ZERO) &&
1743
      (cmp1_op == Op_Phi)) {
1744
    // There should be a diamond phi with true path at index 1 or 2
1745
    PhiNode *phi = cmp1->as_Phi();
1746
    int idx_true = phi->is_diamond_phi();
1747
    if (idx_true != 0) {
1748
      // True input is in(idx_true) while false input is in(3 - idx_true)
1749
      Node *tin = phi->in(idx_true);
1750
      Node *fin = phi->in(3 - idx_true);
1751
      if ((tin->Opcode() == Op_SubI) &&
1752
          (phase->type(tin->in(1)) == TypeInt::ZERO) &&
1753
          (tin->in(2) == fin)) {
1754
        // Found conditional negation at true path, create a new CmpINode without that
1755
        Node *ncmp = phase->transform(new CmpINode(fin, cmp2));
1756
        return new BoolNode(ncmp, _test._test);
1757
      }
1758
      if ((fin->Opcode() == Op_SubI) &&
1759
          (phase->type(fin->in(1)) == TypeInt::ZERO) &&
1760
          (fin->in(2) == tin)) {
1761
        // Found conditional negation at false path, create a new CmpINode without that
1762
        Node *ncmp = phase->transform(new CmpINode(tin, cmp2));
1763
        return new BoolNode(ncmp, _test._test);
1764
      }
1765
    }
1766
  }
1767

1768
  // Change (-A vs 0) into (A vs 0) by commuting the test.  Disallow in the
1769
  // most general case because negating 0x80000000 does nothing.  Needed for
1770
  // the CmpF3/SubI/CmpI idiom.
1771
  if( cop == Op_CmpI &&
1772
      cmp1_op == Op_SubI &&
1773
      cmp2_type == TypeInt::ZERO &&
1774
      phase->type( cmp1->in(1) ) == TypeInt::ZERO &&
1775
      phase->type( cmp1->in(2) )->higher_equal(TypeInt::SYMINT) ) {
1776
    Node *ncmp = phase->transform( new CmpINode(cmp1->in(2),cmp2));
1777
    return new BoolNode( ncmp, _test.commute() );
1778
  }
1779

1780
  // Try to optimize signed integer comparison
1781
  return fold_cmpI(phase, cmp->as_Sub(), cmp1, cop, cmp1_op, cmp2_type);
1782

1783
  //  The transformation below is not valid for either signed or unsigned
1784
  //  comparisons due to wraparound concerns at MAX_VALUE and MIN_VALUE.
1785
  //  This transformation can be resurrected when we are able to
1786
  //  make inferences about the range of values being subtracted from
1787
  //  (or added to) relative to the wraparound point.
1788
  //
1789
  //    // Remove +/-1's if possible.
1790
  //    // "X <= Y-1" becomes "X <  Y"
1791
  //    // "X+1 <= Y" becomes "X <  Y"
1792
  //    // "X <  Y+1" becomes "X <= Y"
1793
  //    // "X-1 <  Y" becomes "X <= Y"
1794
  //    // Do not this to compares off of the counted-loop-end.  These guys are
1795
  //    // checking the trip counter and they want to use the post-incremented
1796
  //    // counter.  If they use the PRE-incremented counter, then the counter has
1797
  //    // to be incremented in a private block on a loop backedge.
1798
  //    if( du && du->cnt(this) && du->out(this)[0]->Opcode() == Op_CountedLoopEnd )
1799
  //      return nullptr;
1800
  //  #ifndef PRODUCT
1801
  //    // Do not do this in a wash GVN pass during verification.
1802
  //    // Gets triggered by too many simple optimizations to be bothered with
1803
  //    // re-trying it again and again.
1804
  //    if( !phase->allow_progress() ) return nullptr;
1805
  //  #endif
1806
  //    // Not valid for unsigned compare because of corner cases in involving zero.
1807
  //    // For example, replacing "X-1 <u Y" with "X <=u Y" fails to throw an
1808
  //    // exception in case X is 0 (because 0-1 turns into 4billion unsigned but
1809
  //    // "0 <=u Y" is always true).
1810
  //    if( cmp->Opcode() == Op_CmpU ) return nullptr;
1811
  //    int cmp2_op = cmp2->Opcode();
1812
  //    if( _test._test == BoolTest::le ) {
1813
  //      if( cmp1_op == Op_AddI &&
1814
  //          phase->type( cmp1->in(2) ) == TypeInt::ONE )
1815
  //        return clone_cmp( cmp, cmp1->in(1), cmp2, phase, BoolTest::lt );
1816
  //      else if( cmp2_op == Op_AddI &&
1817
  //         phase->type( cmp2->in(2) ) == TypeInt::MINUS_1 )
1818
  //        return clone_cmp( cmp, cmp1, cmp2->in(1), phase, BoolTest::lt );
1819
  //    } else if( _test._test == BoolTest::lt ) {
1820
  //      if( cmp1_op == Op_AddI &&
1821
  //          phase->type( cmp1->in(2) ) == TypeInt::MINUS_1 )
1822
  //        return clone_cmp( cmp, cmp1->in(1), cmp2, phase, BoolTest::le );
1823
  //      else if( cmp2_op == Op_AddI &&
1824
  //         phase->type( cmp2->in(2) ) == TypeInt::ONE )
1825
  //        return clone_cmp( cmp, cmp1, cmp2->in(1), phase, BoolTest::le );
1826
  //    }
1827
}
1828

1829
//------------------------------Value------------------------------------------
1830
// Simplify a Bool (convert condition codes to boolean (1 or 0)) node,
1831
// based on local information.   If the input is constant, do it.
1832
const Type* BoolNode::Value(PhaseGVN* phase) const {
1833
  return _test.cc2logical( phase->type( in(1) ) );
1834
}
1835

1836
#ifndef PRODUCT
1837
//------------------------------dump_spec--------------------------------------
1838
// Dump special per-node info
1839
void BoolNode::dump_spec(outputStream *st) const {
1840
  st->print("[");
1841
  _test.dump_on(st);
1842
  st->print("]");
1843
}
1844
#endif
1845

1846
//----------------------is_counted_loop_exit_test------------------------------
1847
// Returns true if node is used by a counted loop node.
1848
bool BoolNode::is_counted_loop_exit_test() {
1849
  for( DUIterator_Fast imax, i = fast_outs(imax); i < imax; i++ ) {
1850
    Node* use = fast_out(i);
1851
    if (use->is_CountedLoopEnd()) {
1852
      return true;
1853
    }
1854
  }
1855
  return false;
1856
}
1857

1858
//=============================================================================
1859
//------------------------------Value------------------------------------------
1860
const Type* AbsNode::Value(PhaseGVN* phase) const {
1861
  const Type* t1 = phase->type(in(1));
1862
  if (t1 == Type::TOP) return Type::TOP;
1863

1864
  switch (t1->base()) {
1865
  case Type::Int: {
1866
    const TypeInt* ti = t1->is_int();
1867
    if (ti->is_con()) {
1868
      return TypeInt::make(uabs(ti->get_con()));
1869
    }
1870
    break;
1871
  }
1872
  case Type::Long: {
1873
    const TypeLong* tl = t1->is_long();
1874
    if (tl->is_con()) {
1875
      return TypeLong::make(uabs(tl->get_con()));
1876
    }
1877
    break;
1878
  }
1879
  case Type::FloatCon:
1880
    return TypeF::make(abs(t1->getf()));
1881
  case Type::DoubleCon:
1882
    return TypeD::make(abs(t1->getd()));
1883
  default:
1884
    break;
1885
  }
1886

1887
  return bottom_type();
1888
}
1889

1890
//------------------------------Identity----------------------------------------
1891
Node* AbsNode::Identity(PhaseGVN* phase) {
1892
  Node* in1 = in(1);
1893
  // No need to do abs for non-negative values
1894
  if (phase->type(in1)->higher_equal(TypeInt::POS) ||
1895
      phase->type(in1)->higher_equal(TypeLong::POS)) {
1896
    return in1;
1897
  }
1898
  // Convert "abs(abs(x))" into "abs(x)"
1899
  if (in1->Opcode() == Opcode()) {
1900
    return in1;
1901
  }
1902
  return this;
1903
}
1904

1905
//------------------------------Ideal------------------------------------------
1906
Node* AbsNode::Ideal(PhaseGVN* phase, bool can_reshape) {
1907
  Node* in1 = in(1);
1908
  // Convert "abs(0-x)" into "abs(x)"
1909
  if (in1->is_Sub() && phase->type(in1->in(1))->is_zero_type()) {
1910
    set_req_X(1, in1->in(2), phase);
1911
    return this;
1912
  }
1913
  return nullptr;
1914
}
1915

1916
//=============================================================================
1917
//------------------------------Value------------------------------------------
1918
// Compute sqrt
1919
const Type* SqrtDNode::Value(PhaseGVN* phase) const {
1920
  const Type *t1 = phase->type( in(1) );
1921
  if( t1 == Type::TOP ) return Type::TOP;
1922
  if( t1->base() != Type::DoubleCon ) return Type::DOUBLE;
1923
  double d = t1->getd();
1924
  if( d < 0.0 ) return Type::DOUBLE;
1925
  return TypeD::make( sqrt( d ) );
1926
}
1927

1928
const Type* SqrtFNode::Value(PhaseGVN* phase) const {
1929
  const Type *t1 = phase->type( in(1) );
1930
  if( t1 == Type::TOP ) return Type::TOP;
1931
  if( t1->base() != Type::FloatCon ) return Type::FLOAT;
1932
  float f = t1->getf();
1933
  if( f < 0.0f ) return Type::FLOAT;
1934
  return TypeF::make( (float)sqrt( (double)f ) );
1935
}
1936

1937
const Type* ReverseINode::Value(PhaseGVN* phase) const {
1938
  const Type *t1 = phase->type( in(1) );
1939
  if (t1 == Type::TOP) {
1940
    return Type::TOP;
1941
  }
1942
  const TypeInt* t1int = t1->isa_int();
1943
  if (t1int && t1int->is_con()) {
1944
    jint res = reverse_bits(t1int->get_con());
1945
    return TypeInt::make(res);
1946
  }
1947
  return bottom_type();
1948
}
1949

1950
const Type* ReverseLNode::Value(PhaseGVN* phase) const {
1951
  const Type *t1 = phase->type( in(1) );
1952
  if (t1 == Type::TOP) {
1953
    return Type::TOP;
1954
  }
1955
  const TypeLong* t1long = t1->isa_long();
1956
  if (t1long && t1long->is_con()) {
1957
    jlong res = reverse_bits(t1long->get_con());
1958
    return TypeLong::make(res);
1959
  }
1960
  return bottom_type();
1961
}
1962

1963
Node* ReverseINode::Identity(PhaseGVN* phase) {
1964
  if (in(1)->Opcode() == Op_ReverseI) {
1965
    return in(1)->in(1);
1966
  }
1967
  return this;
1968
}
1969

1970
Node* ReverseLNode::Identity(PhaseGVN* phase) {
1971
  if (in(1)->Opcode() == Op_ReverseL) {
1972
    return in(1)->in(1);
1973
  }
1974
  return this;
1975
}
1976