jdk

1
/*
2
 * Copyright (c) 2000, 2024, 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 "libadt/vectset.hpp"
27
#include "memory/allocation.inline.hpp"
28
#include "memory/resourceArea.inline.hpp"
29
#include "opto/addnode.hpp"
30
#include "opto/c2compiler.hpp"
31
#include "opto/callnode.hpp"
32
#include "opto/cfgnode.hpp"
33
#include "opto/chaitin.hpp"
34
#include "opto/loopnode.hpp"
35
#include "opto/machnode.hpp"
36

37
//------------------------------Split--------------------------------------
38
// Walk the graph in RPO and for each lrg which spills, propagate reaching
39
// definitions.  During propagation, split the live range around regions of
40
// High Register Pressure (HRP).  If a Def is in a region of Low Register
41
// Pressure (LRP), it will not get spilled until we encounter a region of
42
// HRP between it and one of its uses.  We will spill at the transition
43
// point between LRP and HRP.  Uses in the HRP region will use the spilled
44
// Def.  The first Use outside the HRP region will generate a SpillCopy to
45
// hoist the live range back up into a register, and all subsequent uses
46
// will use that new Def until another HRP region is encountered.  Defs in
47
// HRP regions will get trailing SpillCopies to push the LRG down into the
48
// stack immediately.
49
//
50
// As a side effect, unlink from (hence make dead) coalesced copies.
51
//
52

53
static const char out_of_nodes[] = "out of nodes during split";
54

55
//------------------------------get_spillcopy_wide-----------------------------
56
// Get a SpillCopy node with wide-enough masks.  Use the 'wide-mask', the
57
// wide ideal-register spill-mask if possible.  If the 'wide-mask' does
58
// not cover the input (or output), use the input (or output) mask instead.
59
Node *PhaseChaitin::get_spillcopy_wide(MachSpillCopyNode::SpillType spill_type, Node *def, Node *use, uint uidx) {
60
  // If ideal reg doesn't exist we've got a bad schedule happening
61
  // that is forcing us to spill something that isn't spillable.
62
  // Bail rather than abort
63
  uint ireg = def->ideal_reg();
64
  if (ireg == 0 || ireg == Op_RegFlags) {
65
    assert(false, "attempted to spill a non-spillable item: %d: %s <- %d: %s, ireg = %u, spill_type: %s",
66
           def->_idx, def->Name(), use->_idx, use->Name(), ireg,
67
           MachSpillCopyNode::spill_type(spill_type));
68
    C->record_method_not_compilable("attempted to spill a non-spillable item");
69
    return nullptr;
70
  }
71
  if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {
72
    return nullptr;
73
  }
74
  const RegMask *i_mask = &def->out_RegMask();
75
  const RegMask *w_mask = C->matcher()->idealreg2spillmask[ireg];
76
  const RegMask *o_mask = use ? &use->in_RegMask(uidx) : w_mask;
77
  const RegMask *w_i_mask = w_mask->overlap( *i_mask ) ? w_mask : i_mask;
78
  const RegMask *w_o_mask;
79

80
  int num_regs = RegMask::num_registers(ireg);
81
  bool is_vect = RegMask::is_vector(ireg);
82
  if( w_mask->overlap( *o_mask ) && // Overlap AND
83
      (num_regs == 1  // Single use or aligned
84
        || is_vect    // or vector
85
        || (!is_vect && o_mask->is_aligned_pairs())) ) {
86
    assert(!is_vect || o_mask->is_aligned_sets(num_regs), "vectors are aligned");
87
    // Don't come here for mis-aligned doubles
88
    w_o_mask = w_mask;
89
  } else {                      // wide ideal mask does not overlap with o_mask
90
    // Mis-aligned doubles come here and XMM->FPR moves on x86.
91
    w_o_mask = o_mask;          // Must target desired registers
92
    // Does the ideal-reg-mask overlap with o_mask?  I.e., can I use
93
    // a reg-reg move or do I need a trip across register classes
94
    // (and thus through memory)?
95
    if( !C->matcher()->idealreg2regmask[ireg]->overlap( *o_mask) && o_mask->is_UP() )
96
      // Here we assume a trip through memory is required.
97
      w_i_mask = &C->FIRST_STACK_mask();
98
  }
99
  return new MachSpillCopyNode(spill_type, def, *w_i_mask, *w_o_mask );
100
}
101

102
//------------------------------insert_proj------------------------------------
103
// Insert the spill at chosen location.  Skip over any intervening Proj's or
104
// Phis.  Skip over a CatchNode and projs, inserting in the fall-through block
105
// instead.  Update high-pressure indices.  Create a new live range.
106
void PhaseChaitin::insert_proj( Block *b, uint i, Node *spill, uint maxlrg ) {
107
  // Skip intervening ProjNodes.  Do not insert between a ProjNode and
108
  // its definer.
109
  while( i < b->number_of_nodes() &&
110
         (b->get_node(i)->is_Proj() ||
111
          b->get_node(i)->is_Phi() ) )
112
    i++;
113

114
  // Do not insert between a call and his Catch
115
  if( b->get_node(i)->is_Catch() ) {
116
    // Put the instruction at the top of the fall-thru block.
117
    // This assumes that the instruction is not used in the other exception
118
    // blocks. Global code motion is responsible for maintaining this invariant.
119
    // Find the fall-thru projection
120
    while( 1 ) {
121
      const CatchProjNode *cp = b->get_node(++i)->as_CatchProj();
122
      if( cp->_con == CatchProjNode::fall_through_index )
123
        break;
124
    }
125
    int sidx = i - b->end_idx()-1;
126
    b = b->_succs[sidx];        // Switch to successor block
127
    i = 1;                      // Right at start of block
128
  }
129

130
  b->insert_node(spill, i);    // Insert node in block
131
  _cfg.map_node_to_block(spill,  b); // Update node->block mapping to reflect
132
  // Adjust the point where we go hi-pressure
133
  if( i <= b->_ihrp_index ) b->_ihrp_index++;
134
  if( i <= b->_fhrp_index ) b->_fhrp_index++;
135

136
  // Assign a new Live Range Number to the SpillCopy and grow
137
  // the node->live range mapping.
138
  new_lrg(spill,maxlrg);
139
}
140

141
//------------------------------split_DEF--------------------------------------
142
// There are four categories of Split; UP/DOWN x DEF/USE
143
// Only three of these really occur as DOWN/USE will always color
144
// Any Split with a DEF cannot CISC-Spill now.  Thus we need
145
// two helper routines, one for Split DEFS (insert after instruction),
146
// one for Split USES (insert before instruction).  DEF insertion
147
// happens inside Split, where the Leaveblock array is updated.
148
uint PhaseChaitin::split_DEF( Node *def, Block *b, int loc, uint maxlrg, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ) {
149
#ifdef ASSERT
150
  // Increment the counter for this lrg
151
  splits.at_put(slidx, splits.at(slidx)+1);
152
#endif
153
  // If we are spilling the memory op for an implicit null check, at the
154
  // null check location (ie - null check is in HRP block) we need to do
155
  // the null-check first, then spill-down in the following block.
156
  // (The implicit_null_check function ensures the use is also dominated
157
  // by the branch-not-taken block.)
158
  Node *be = b->end();
159
  if( be->is_MachNullCheck() && be->in(1) == def && def == b->get_node(loc)) {
160
    // Spill goes in the branch-not-taken block
161
    b = b->_succs[b->get_node(b->end_idx()+1)->Opcode() == Op_IfTrue];
162
    loc = 0;                    // Just past the Region
163
  }
164
  assert( loc >= 0, "must insert past block head" );
165

166
  // Get a def-side SpillCopy
167
  Node *spill = get_spillcopy_wide(MachSpillCopyNode::Definition, def, nullptr, 0);
168
  // Did we fail to split?, then bail
169
  if (!spill) {
170
    return 0;
171
  }
172

173
  // Insert the spill at chosen location
174
  insert_proj( b, loc+1, spill, maxlrg++);
175

176
  // Insert new node into Reaches array
177
  Reachblock[slidx] = spill;
178
  // Update debug list of reaching down definitions by adding this one
179
  debug_defs[slidx] = spill;
180

181
  // return updated count of live ranges
182
  return maxlrg;
183
}
184

185
//------------------------------split_USE--------------------------------------
186
// Splits at uses can involve redeffing the LRG, so no CISC Spilling there.
187
// Debug uses want to know if def is already stack enabled.
188
// Return value
189
//   -1 : bailout, 0: no spillcopy created, 1: create a new spillcopy
190
int PhaseChaitin::split_USE(MachSpillCopyNode::SpillType spill_type, Node *def, Block *b, Node *use, uint useidx, uint maxlrg, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ) {
191
#ifdef ASSERT
192
  // Increment the counter for this lrg
193
  splits.at_put(slidx, splits.at(slidx)+1);
194
#endif
195

196
  // Some setup stuff for handling debug node uses
197
  JVMState* jvms = use->jvms();
198
  uint debug_start = jvms ? jvms->debug_start() : 999999;
199
  uint debug_end   = jvms ? jvms->debug_end()   : 999999;
200

201
  //-------------------------------------------
202
  // Check for use of debug info
203
  if (useidx >= debug_start && useidx < debug_end) {
204
    // Actually it's perfectly legal for constant debug info to appear
205
    // just unlikely.  In this case the optimizer left a ConI of a 4
206
    // as both inputs to a Phi with only a debug use.  It's a single-def
207
    // live range of a rematerializable value.  The live range spills,
208
    // rematerializes and now the ConI directly feeds into the debug info.
209
    // assert(!def->is_Con(), "constant debug info already constructed directly");
210

211
    // Special split handling for Debug Info
212
    // If DEF is DOWN, just hook the edge and return
213
    // If DEF is UP, Split it DOWN for this USE.
214
    if( def->is_Mach() ) {
215
      if( def_down ) {
216
        // DEF is DOWN, so connect USE directly to the DEF
217
        use->set_req(useidx, def);
218
        return 0;
219
      } else {
220
        // Block and index where the use occurs.
221
        Block *b = _cfg.get_block_for_node(use);
222
        // Put the clone just prior to use
223
        int bindex = b->find_node(use);
224
        // DEF is UP, so must copy it DOWN and hook in USE
225
        // Insert SpillCopy before the USE, which uses DEF as its input,
226
        // and defs a new live range, which is used by this node.
227
        Node *spill = get_spillcopy_wide(spill_type, def,use,useidx);
228
        // did we fail to split?
229
        if (!spill) {
230
          // Bail
231
          return -1;
232
        }
233
        // insert into basic block
234
        insert_proj( b, bindex, spill, maxlrg );
235
        // Use the new split
236
        use->set_req(useidx,spill);
237
        return 1;
238
      }
239
      // No further split handling needed for this use
240
    }  // End special splitting for debug info live range
241
  }  // If debug info
242

243
  // CISC-SPILLING
244
  // Finally, check to see if USE is CISC-Spillable, and if so,
245
  // gather_lrg_masks will add the flags bit to its mask, and
246
  // no use side copy is needed.  This frees up the live range
247
  // register choices without causing copy coalescing, etc.
248
  if( UseCISCSpill && cisc_sp ) {
249
    int inp = use->cisc_operand();
250
    if( inp != AdlcVMDeps::Not_cisc_spillable )
251
      // Convert operand number to edge index number
252
      inp = use->as_Mach()->operand_index(inp);
253
    if( inp == (int)useidx ) {
254
      use->set_req(useidx, def);
255
#ifndef PRODUCT
256
      if( TraceCISCSpill ) {
257
        tty->print("  set_split: ");
258
        use->dump();
259
      }
260
#endif
261
      return 0;
262
    }
263
  }
264

265
  //-------------------------------------------
266
  // Insert a Copy before the use
267

268
  // Block and index where the use occurs.
269
  int bindex;
270
  // Phi input spill-copys belong at the end of the prior block
271
  if( use->is_Phi() ) {
272
    b = _cfg.get_block_for_node(b->pred(useidx));
273
    bindex = b->end_idx();
274
  } else {
275
    // Put the clone just prior to use
276
    bindex = b->find_node(use);
277
  }
278

279
  Node *spill = get_spillcopy_wide(spill_type, def, use, useidx );
280
  if( !spill ) return -1;        // Bailed out
281
  // Insert SpillCopy before the USE, which uses the reaching DEF as
282
  // its input, and defs a new live range, which is used by this node.
283
  insert_proj( b, bindex, spill, maxlrg );
284
  // Use the spill/clone
285
  use->set_req(useidx,spill);
286

287
  return 1;
288
}
289

290
//------------------------------clone_node----------------------------
291
// Clone node with anti dependence check.
292
static Node* clone_node(Node* def, Block *b, Compile* C) {
293
  if (def->needs_anti_dependence_check()) {
294
#ifdef ASSERT
295
    if (PrintOpto && WizardMode) {
296
      tty->print_cr("RA attempts to clone node with anti_dependence:");
297
      def->dump(-1); tty->cr();
298
      tty->print_cr("into block:");
299
      b->dump();
300
    }
301
#endif
302
    if (C->subsume_loads() == true && !C->failing()) {
303
      // Retry with subsume_loads == false
304
      // If this is the first failure, the sentinel string will "stick"
305
      // to the Compile object, and the C2Compiler will see it and retry.
306
      C->record_failure(C2Compiler::retry_no_subsuming_loads());
307
    } else {
308
      // Bailout without retry
309
      assert(false, "RA Split failed: attempt to clone node with anti_dependence");
310
      C->record_method_not_compilable("RA Split failed: attempt to clone node with anti_dependence");
311
    }
312
    return nullptr;
313
  }
314
  return def->clone();
315
}
316

317
//------------------------------split_Rematerialize----------------------------
318
// Clone a local copy of the def.
319
Node *PhaseChaitin::split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg,
320
                                        GrowableArray<uint> splits, int slidx, uint *lrg2reach,
321
                                        Node **Reachblock, bool walkThru) {
322
  // The input live ranges will be stretched to the site of the new
323
  // instruction.  They might be stretched past a def and will thus
324
  // have the old and new values of the same live range alive at the
325
  // same time - a definite no-no.  Split out private copies of
326
  // the inputs.
327
  if (def->req() > 1) {
328
    for (uint i = 1; i < def->req(); i++) {
329
      Node *in = def->in(i);
330
      uint lidx = _lrg_map.live_range_id(in);
331
      // We do not need this for live ranges that are only defined once.
332
      // However, this is not true for spill copies that are added in this
333
      // Split() pass, since they might get coalesced later on in this pass.
334
      if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).is_singledef()) {
335
        continue;
336
      }
337

338
      Block *b_def = _cfg.get_block_for_node(def);
339
      int idx_def = b_def->find_node(def);
340
      // Cannot spill Op_RegFlags.
341
      Node *in_spill;
342
      if (in->ideal_reg() != Op_RegFlags) {
343
        in_spill = get_spillcopy_wide(MachSpillCopyNode::InputToRematerialization, in, def, i);
344
        if (!in_spill) { return nullptr; } // Bailed out
345
        insert_proj(b_def, idx_def, in_spill, maxlrg++);
346
        if (b_def == b) {
347
          insidx++;
348
        }
349
        def->set_req(i, in_spill);
350
      } else {
351
        // The 'in' defines a flag register. Flag registers can not be spilled.
352
        // Register allocation handles live ranges with flag registers
353
        // by rematerializing the def (in this case 'in'). Thus, this is not
354
        // critical if the input can be rematerialized, too.
355
        if (!in->rematerialize()) {
356
          assert(false, "Can not rematerialize %d: %s. Prolongs RegFlags live"
357
                 " range and defining node %d: %s may not be rematerialized.",
358
                 def->_idx, def->Name(), in->_idx, in->Name());
359
          C->record_method_not_compilable("attempted to spill a non-spillable item with RegFlags input");
360
          return nullptr; // Bailed out
361
        }
362
      }
363
    }
364
  }
365

366
  Node *spill = clone_node(def, b, C);
367
  if (spill == nullptr || C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {
368
    // Check when generating nodes
369
    return nullptr;
370
  }
371

372
  // See if any inputs are currently being spilled, and take the
373
  // latest copy of spilled inputs.
374
  if( spill->req() > 1 ) {
375
    for( uint i = 1; i < spill->req(); i++ ) {
376
      Node *in = spill->in(i);
377
      uint lidx = _lrg_map.find_id(in);
378

379
      // Walk backwards thru spill copy node intermediates
380
      if (walkThru) {
381
        while (in->is_SpillCopy() && lidx >= _lrg_map.max_lrg_id()) {
382
          in = in->in(1);
383
          lidx = _lrg_map.find_id(in);
384
        }
385

386
        if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).is_multidef()) {
387
          // walkThru found a multidef LRG, which is unsafe to use, so
388
          // just keep the original def used in the clone.
389
          in = spill->in(i);
390
          lidx = _lrg_map.find_id(in);
391
        }
392
      }
393

394
      if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).reg() >= LRG::SPILL_REG) {
395
        Node *rdef = Reachblock[lrg2reach[lidx]];
396
        if (rdef) {
397
          spill->set_req(i, rdef);
398
        }
399
      }
400
    }
401
  }
402

403

404
  assert( spill->out_RegMask().is_UP(), "rematerialize to a reg" );
405
  // Rematerialized op is def->spilled+1
406
  set_was_spilled(spill);
407
  if( _spilled_once.test(def->_idx) )
408
    set_was_spilled(spill);
409

410
  insert_proj( b, insidx, spill, maxlrg++ );
411
#ifdef ASSERT
412
  // Increment the counter for this lrg
413
  splits.at_put(slidx, splits.at(slidx)+1);
414
#endif
415
  // See if the cloned def kills any flags, and copy those kills as well
416
  uint i = insidx+1;
417
  int found_projs = clone_projs( b, i, def, spill, maxlrg);
418
  if (found_projs > 0) {
419
    // Adjust the point where we go hi-pressure
420
    if (i <= b->_ihrp_index) {
421
      b->_ihrp_index += found_projs;
422
    }
423
    if (i <= b->_fhrp_index) {
424
      b->_fhrp_index += found_projs;
425
    }
426
  }
427

428
  return spill;
429
}
430

431
//------------------------------is_high_pressure-------------------------------
432
// Function to compute whether or not this live range is "high pressure"
433
// in this block - whether it spills eagerly or not.
434
bool PhaseChaitin::is_high_pressure( Block *b, LRG *lrg, uint insidx ) {
435
  if( lrg->_was_spilled1 ) return true;
436
  // Forced spilling due to conflict?  Then split only at binding uses
437
  // or defs, not for supposed capacity problems.
438
  // CNC - Turned off 7/8/99, causes too much spilling
439
  // if( lrg->_is_bound ) return false;
440

441
  // Use float pressure numbers for vectors.
442
  bool is_float_or_vector = lrg->_is_float || lrg->_is_vector;
443
  // Not yet reached the high-pressure cutoff point, so low pressure
444
  uint hrp_idx = is_float_or_vector ? b->_fhrp_index : b->_ihrp_index;
445
  if( insidx < hrp_idx ) return false;
446
  // Register pressure for the block as a whole depends on reg class
447
  int block_pres = is_float_or_vector ? b->_freg_pressure : b->_reg_pressure;
448
  // Bound live ranges will split at the binding points first;
449
  // Intermediate splits should assume the live range's register set
450
  // got "freed up" and that num_regs will become INT_PRESSURE.
451
  int bound_pres = is_float_or_vector ? Matcher::float_pressure_limit() : Matcher::int_pressure_limit();
452
  // Effective register pressure limit.
453
  int lrg_pres = (lrg->get_invalid_mask_size() > lrg->num_regs())
454
    ? (lrg->get_invalid_mask_size() >> (lrg->num_regs()-1)) : bound_pres;
455
  // High pressure if block pressure requires more register freedom
456
  // than live range has.
457
  return block_pres >= lrg_pres;
458
}
459

460

461
//------------------------------prompt_use---------------------------------
462
// True if lidx is used before any real register is def'd in the block
463
bool PhaseChaitin::prompt_use( Block *b, uint lidx ) {
464
  if (lrgs(lidx)._was_spilled2) {
465
    return false;
466
  }
467

468
  // Scan block for 1st use.
469
  for( uint i = 1; i <= b->end_idx(); i++ ) {
470
    Node *n = b->get_node(i);
471
    // Ignore PHI use, these can be up or down
472
    if (n->is_Phi()) {
473
      continue;
474
    }
475
    for (uint j = 1; j < n->req(); j++) {
476
      if (_lrg_map.find_id(n->in(j)) == lidx) {
477
        return true;          // Found 1st use!
478
      }
479
    }
480
    if (n->out_RegMask().is_NotEmpty()) {
481
      return false;
482
    }
483
  }
484
  return false;
485
}
486

487
//------------------------------Split--------------------------------------
488
//----------Split Routine----------
489
// ***** NEW SPLITTING HEURISTIC *****
490
// DEFS: If the DEF is in a High Register Pressure(HRP) Block, split there.
491
//        Else, no split unless there is a HRP block between a DEF and
492
//        one of its uses, and then split at the HRP block.
493
//
494
// USES: If USE is in HRP, split at use to leave main LRG on stack.
495
//       Else, hoist LRG back up to register only (ie - split is also DEF)
496
// We will compute a new maxlrg as we go
497
uint PhaseChaitin::Split(uint maxlrg, ResourceArea* split_arena) {
498
  Compile::TracePhase tp("regAllocSplit", &timers[_t_regAllocSplit]);
499

500
  // Free thread local resources used by this method on exit.
501
  ResourceMark rm(split_arena);
502

503
  uint                 bidx, pidx, slidx, insidx, inpidx, twoidx;
504
  uint                 non_phi = 1, spill_cnt = 0;
505
  Node                *n1, *n2, *n3;
506
  bool                *UPblock;
507
  bool                 u1, u2, u3;
508
  Block               *b, *pred;
509
  PhiNode             *phi;
510
  GrowableArray<uint>  lidxs(split_arena, maxlrg, 0, 0);
511

512
  // Array of counters to count splits per live range
513
  GrowableArray<uint>  splits(split_arena, maxlrg, 0, 0);
514

515
#define NEW_SPLIT_ARRAY(type, size)\
516
  (type*) split_arena->allocate_bytes((size) * sizeof(type))
517

518
  //----------Setup Code----------
519
  // Create a convenient mapping from lrg numbers to reaches/leaves indices
520
  uint *lrg2reach = NEW_SPLIT_ARRAY(uint, maxlrg);
521
  // Gather info on which LRG's are spilling, and build maps
522
  for (bidx = 1; bidx < maxlrg; bidx++) {
523
    if (lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG) {
524
      assert(!lrgs(bidx).mask().is_AllStack(),"AllStack should color");
525
      lrg2reach[bidx] = spill_cnt;
526
      spill_cnt++;
527
      lidxs.append(bidx);
528
#ifdef ASSERT
529
      // Initialize the split counts to zero
530
      splits.append(0);
531
#endif
532
      if (PrintOpto && WizardMode && lrgs(bidx)._was_spilled1) {
533
        tty->print_cr("Warning, 2nd spill of L%d",bidx);
534
      }
535
    }
536
  }
537

538
  // Create side arrays for propagating reaching defs info.
539
  // Each block needs a node pointer for each spilling live range for the
540
  // Def which is live into the block.  Phi nodes handle multiple input
541
  // Defs by querying the output of their predecessor blocks and resolving
542
  // them to a single Def at the phi.  The pointer is updated for each
543
  // Def in the block, and then becomes the output for the block when
544
  // processing of the block is complete.  We also need to track whether
545
  // a Def is UP or DOWN.  UP means that it should get a register (ie -
546
  // it is always in LRP regions), and DOWN means that it is probably
547
  // on the stack (ie - it crosses HRP regions).
548
  Node ***Reaches     = NEW_SPLIT_ARRAY( Node**, _cfg.number_of_blocks() + 1);
549
  bool  **UP          = NEW_SPLIT_ARRAY( bool*, _cfg.number_of_blocks() + 1);
550
  Node  **debug_defs  = NEW_SPLIT_ARRAY( Node*, spill_cnt );
551
  VectorSet **UP_entry= NEW_SPLIT_ARRAY( VectorSet*, spill_cnt );
552

553
  // Initialize Reaches & UP
554
  for (bidx = 0; bidx < _cfg.number_of_blocks() + 1; bidx++) {
555
    Reaches[bidx]     = NEW_SPLIT_ARRAY( Node*, spill_cnt );
556
    UP[bidx]          = NEW_SPLIT_ARRAY( bool, spill_cnt );
557
    Node **Reachblock = Reaches[bidx];
558
    bool *UPblock     = UP[bidx];
559
    for( slidx = 0; slidx < spill_cnt; slidx++ ) {
560
      UPblock[slidx] = true;     // Assume they start in registers
561
      Reachblock[slidx] = nullptr;  // Assume that no def is present
562
    }
563
  }
564

565
#undef NEW_SPLIT_ARRAY
566

567
  // Initialize to array of empty vectorsets
568
  // Each containing at most spill_cnt * _cfg.number_of_blocks() entries.
569
  for (slidx = 0; slidx < spill_cnt; slidx++) {
570
    UP_entry[slidx] = new(split_arena) VectorSet(split_arena);
571
  }
572

573
  // Keep track of DEFS & Phis for later passes
574
  Node_List defs(split_arena, 8);
575
  Node_List phis(split_arena, 16);
576

577
  //----------PASS 1----------
578
  //----------Propagation & Node Insertion Code----------
579
  // Walk the Blocks in RPO for DEF & USE info
580
  for( bidx = 0; bidx < _cfg.number_of_blocks(); bidx++ ) {
581

582
    if (C->check_node_count(spill_cnt, out_of_nodes)) {
583
      return 0;
584
    }
585

586
    b  = _cfg.get_block(bidx);
587
    // Reaches & UP arrays for this block
588
    Node** Reachblock = Reaches[b->_pre_order];
589
    UPblock    = UP[b->_pre_order];
590
    // Reset counter of start of non-Phi nodes in block
591
    non_phi = 1;
592
    //----------Block Entry Handling----------
593
    // Check for need to insert a new phi
594
    // Cycle through this block's predecessors, collecting Reaches
595
    // info for each spilled LRG.  If they are identical, no phi is
596
    // needed.  If they differ, check for a phi, and insert if missing,
597
    // or update edges if present.  Set current block's Reaches set to
598
    // be either the phi's or the reaching def, as appropriate.
599
    // If no Phi is needed, check if the LRG needs to spill on entry
600
    // to the block due to HRP.
601
    for( slidx = 0; slidx < spill_cnt; slidx++ ) {
602
      // Grab the live range number
603
      uint lidx = lidxs.at(slidx);
604
      // Do not bother splitting or putting in Phis for single-def
605
      // rematerialized live ranges.  This happens a lot to constants
606
      // with long live ranges.
607
      if( lrgs(lidx).is_singledef() &&
608
          lrgs(lidx)._def->rematerialize() ) {
609
        // reset the Reaches & UP entries
610
        Reachblock[slidx] = lrgs(lidx)._def;
611
        UPblock[slidx] = true;
612
        // Record following instruction in case 'n' rematerializes and
613
        // kills flags
614
        Block *pred1 = _cfg.get_block_for_node(b->pred(1));
615
        continue;
616
      }
617

618
      // Initialize needs_phi and needs_split
619
      bool needs_phi = false;
620
      bool needs_split = false;
621
      bool has_phi = false;
622
      // Walk the predecessor blocks to check inputs for that live range
623
      // Grab predecessor block header
624
      n1 = b->pred(1);
625
      // Grab the appropriate reaching def info for inpidx
626
      pred = _cfg.get_block_for_node(n1);
627
      pidx = pred->_pre_order;
628
      Node **Ltmp = Reaches[pidx];
629
      bool  *Utmp = UP[pidx];
630
      n1 = Ltmp[slidx];
631
      u1 = Utmp[slidx];
632
      // Initialize node for saving type info
633
      n3 = n1;
634
      u3 = u1;
635

636
      // Compare inputs to see if a Phi is needed
637
      for( inpidx = 2; inpidx < b->num_preds(); inpidx++ ) {
638
        // Grab predecessor block headers
639
        n2 = b->pred(inpidx);
640
        // Grab the appropriate reaching def info for inpidx
641
        pred = _cfg.get_block_for_node(n2);
642
        pidx = pred->_pre_order;
643
        Ltmp = Reaches[pidx];
644
        Utmp = UP[pidx];
645
        n2 = Ltmp[slidx];
646
        u2 = Utmp[slidx];
647
        // For each LRG, decide if a phi is necessary
648
        if( n1 != n2 ) {
649
          needs_phi = true;
650
        }
651
        // See if the phi has mismatched inputs, UP vs. DOWN
652
        if( n1 && n2 && (u1 != u2) ) {
653
          needs_split = true;
654
        }
655
        // Move n2/u2 to n1/u1 for next iteration
656
        n1 = n2;
657
        u1 = u2;
658
        // Preserve a non-null predecessor for later type referencing
659
        if( (n3 == nullptr) && (n2 != nullptr) ){
660
          n3 = n2;
661
          u3 = u2;
662
        }
663
      }  // End for all potential Phi inputs
664

665
      // check block for appropriate phinode & update edges
666
      for( insidx = 1; insidx <= b->end_idx(); insidx++ ) {
667
        n1 = b->get_node(insidx);
668
        // bail if this is not a phi
669
        phi = n1->is_Phi() ? n1->as_Phi() : nullptr;
670
        if( phi == nullptr ) {
671
          // Keep track of index of first non-PhiNode instruction in block
672
          non_phi = insidx;
673
          // break out of the for loop as we have handled all phi nodes
674
          break;
675
        }
676
        // must be looking at a phi
677
        if (_lrg_map.find_id(n1) == lidxs.at(slidx)) {
678
          // found the necessary phi
679
          needs_phi = false;
680
          has_phi = true;
681
          // initialize the Reaches entry for this LRG
682
          Reachblock[slidx] = phi;
683
          break;
684
        }  // end if found correct phi
685
      }  // end for all phi's
686

687
      // If a phi is needed or exist, check for it
688
      if( needs_phi || has_phi ) {
689
        // add new phinode if one not already found
690
        if( needs_phi ) {
691
          // create a new phi node and insert it into the block
692
          // type is taken from left over pointer to a predecessor
693
          guarantee(n3, "No non-null reaching DEF for a Phi");
694
          phi = new PhiNode(b->head(), n3->bottom_type());
695
          // initialize the Reaches entry for this LRG
696
          Reachblock[slidx] = phi;
697

698
          // add node to block & node_to_block mapping
699
          insert_proj(b, insidx++, phi, maxlrg++);
700
          non_phi++;
701
          // Reset new phi's mapping to be the spilling live range
702
          _lrg_map.map(phi->_idx, lidx);
703
          assert(_lrg_map.find_id(phi) == lidx, "Bad update on Union-Find mapping");
704
        }  // end if not found correct phi
705
        // Here you have either found or created the Phi, so record it
706
        assert(phi != nullptr,"Must have a Phi Node here");
707
        phis.push(phi);
708
        // PhiNodes should either force the LRG UP or DOWN depending
709
        // on its inputs and the register pressure in the Phi's block.
710
        UPblock[slidx] = true;  // Assume new DEF is UP
711
        // If entering a high-pressure area with no immediate use,
712
        // assume Phi is DOWN
713
        if( is_high_pressure( b, &lrgs(lidx), b->end_idx()) && !prompt_use(b,lidx) )
714
          UPblock[slidx] = false;
715
        // If we are not split up/down and all inputs are down, then we
716
        // are down
717
        if( !needs_split && !u3 )
718
          UPblock[slidx] = false;
719
      }  // end if phi is needed
720

721
      // Do not need a phi, so grab the reaching DEF
722
      else {
723
        // Grab predecessor block header
724
        n1 = b->pred(1);
725
        // Grab the appropriate reaching def info for k
726
        pred = _cfg.get_block_for_node(n1);
727
        pidx = pred->_pre_order;
728
        Node **Ltmp = Reaches[pidx];
729
        bool  *Utmp = UP[pidx];
730
        // reset the Reaches & UP entries
731
        Reachblock[slidx] = Ltmp[slidx];
732
        UPblock[slidx] = Utmp[slidx];
733
      }  // end else no Phi is needed
734
    }  // end for all spilling live ranges
735
    // DEBUG
736
#ifndef PRODUCT
737
    if(trace_spilling()) {
738
      tty->print("/`\nBlock %d: ", b->_pre_order);
739
      tty->print("Reaching Definitions after Phi handling\n");
740
      for( uint x = 0; x < spill_cnt; x++ ) {
741
        tty->print("Spill Idx %d: UP %d: Node\n",x,UPblock[x]);
742
        if( Reachblock[x] )
743
          Reachblock[x]->dump();
744
        else
745
          tty->print("Undefined\n");
746
      }
747
    }
748
#endif
749

750
    //----------Non-Phi Node Splitting----------
751
    // Since phi-nodes have now been handled, the Reachblock array for this
752
    // block is initialized with the correct starting value for the defs which
753
    // reach non-phi instructions in this block.  Thus, process non-phi
754
    // instructions normally, inserting SpillCopy nodes for all spill
755
    // locations.
756

757
    // Memoize any DOWN reaching definitions for use as DEBUG info
758
    for( insidx = 0; insidx < spill_cnt; insidx++ ) {
759
      debug_defs[insidx] = (UPblock[insidx]) ? nullptr : Reachblock[insidx];
760
      if( UPblock[insidx] )     // Memoize UP decision at block start
761
        UP_entry[insidx]->set( b->_pre_order );
762
    }
763

764
    //----------Walk Instructions in the Block and Split----------
765
    // For all non-phi instructions in the block
766
    for( insidx = 1; insidx <= b->end_idx(); insidx++ ) {
767
      Node *n = b->get_node(insidx);
768
      // Find the defining Node's live range index
769
      uint defidx = _lrg_map.find_id(n);
770
      uint cnt = n->req();
771

772
      if (n->is_Phi()) {
773
        // Skip phi nodes after removing dead copies.
774
        if (defidx < _lrg_map.max_lrg_id()) {
775
          // Check for useless Phis.  These appear if we spill, then
776
          // coalesce away copies.  Dont touch Phis in spilling live
777
          // ranges; they are busy getting modified in this pass.
778
          if( lrgs(defidx).reg() < LRG::SPILL_REG ) {
779
            uint i;
780
            Node *u = nullptr;
781
            // Look for the Phi merging 2 unique inputs
782
            for( i = 1; i < cnt; i++ ) {
783
              // Ignore repeats and self
784
              if( n->in(i) != u && n->in(i) != n ) {
785
                // Found a unique input
786
                if( u != nullptr ) // If it's the 2nd, bail out
787
                  break;
788
                u = n->in(i);   // Else record it
789
              }
790
            }
791
            assert( u, "at least 1 valid input expected" );
792
            if (i >= cnt) {    // Found one unique input
793
              assert(_lrg_map.find_id(n) == _lrg_map.find_id(u), "should be the same lrg");
794
              n->replace_by(u); // Then replace with unique input
795
              n->disconnect_inputs(C);
796
              b->remove_node(insidx);
797
              insidx--;
798
              b->_ihrp_index--;
799
              b->_fhrp_index--;
800
            }
801
          }
802
        }
803
        continue;
804
      }
805
      assert( insidx > b->_ihrp_index ||
806
              (b->_reg_pressure < Matcher::int_pressure_limit()) ||
807
              b->_ihrp_index > 4000000 ||
808
              b->_ihrp_index >= b->end_idx() ||
809
              !b->get_node(b->_ihrp_index)->is_Proj(), "" );
810
      assert( insidx > b->_fhrp_index ||
811
              (b->_freg_pressure < Matcher::float_pressure_limit()) ||
812
              b->_fhrp_index > 4000000 ||
813
              b->_fhrp_index >= b->end_idx() ||
814
              !b->get_node(b->_fhrp_index)->is_Proj(), "" );
815

816
      // ********** Handle Crossing HRP Boundary **********
817
      if( (insidx == b->_ihrp_index) || (insidx == b->_fhrp_index) ) {
818
        for( slidx = 0; slidx < spill_cnt; slidx++ ) {
819
          // Check for need to split at HRP boundary - split if UP
820
          n1 = Reachblock[slidx];
821
          // bail out if no reaching DEF
822
          if( n1 == nullptr ) continue;
823
          // bail out if live range is 'isolated' around inner loop
824
          uint lidx = lidxs.at(slidx);
825
          // If live range is currently UP
826
          if( UPblock[slidx] ) {
827
            // set location to insert spills at
828
            // SPLIT DOWN HERE - NO CISC SPILL
829
            if( is_high_pressure( b, &lrgs(lidx), insidx ) &&
830
                !n1->rematerialize() ) {
831
              // If there is already a valid stack definition available, use it
832
              if( debug_defs[slidx] != nullptr ) {
833
                Reachblock[slidx] = debug_defs[slidx];
834
              }
835
              else {
836
                // Insert point is just past last use or def in the block
837
                int insert_point = insidx-1;
838
                while( insert_point > 0 ) {
839
                  Node *n = b->get_node(insert_point);
840
                  // Hit top of block?  Quit going backwards
841
                  if (n->is_Phi()) {
842
                    break;
843
                  }
844
                  // Found a def?  Better split after it.
845
                  if (_lrg_map.live_range_id(n) == lidx) {
846
                    break;
847
                  }
848
                  // Look for a use
849
                  uint i;
850
                  for( i = 1; i < n->req(); i++ ) {
851
                    if (_lrg_map.live_range_id(n->in(i)) == lidx) {
852
                      break;
853
                    }
854
                  }
855
                  // Found a use?  Better split after it.
856
                  if (i < n->req()) {
857
                    break;
858
                  }
859
                  insert_point--;
860
                }
861
                uint orig_eidx = b->end_idx();
862
                maxlrg = split_DEF( n1, b, insert_point, maxlrg, Reachblock, debug_defs, splits, slidx);
863
                // If it wasn't split bail
864
                if (!maxlrg) {
865
                  return 0;
866
                }
867
                // Spill of null check mem op goes into the following block.
868
                if (b->end_idx() > orig_eidx) {
869
                  insidx++;
870
                }
871
              }
872
              // This is a new DEF, so update UP
873
              UPblock[slidx] = false;
874
#ifndef PRODUCT
875
              // DEBUG
876
              if( trace_spilling() ) {
877
                tty->print("\nNew Split DOWN DEF of Spill Idx ");
878
                tty->print("%d, UP %d:\n",slidx,false);
879
                n1->dump();
880
              }
881
#endif
882
            }
883
          }  // end if LRG is UP
884
        }  // end for all spilling live ranges
885
        assert( b->get_node(insidx) == n, "got insidx set incorrectly" );
886
      }  // end if crossing HRP Boundary
887

888
      // If the LRG index is oob, then this is a new spillcopy, skip it.
889
      if (defidx >= _lrg_map.max_lrg_id()) {
890
        continue;
891
      }
892
      LRG &deflrg = lrgs(defidx);
893
      uint copyidx = n->is_Copy();
894
      // Remove coalesced copy from CFG
895
      if (copyidx && defidx == _lrg_map.live_range_id(n->in(copyidx))) {
896
        n->replace_by( n->in(copyidx) );
897
        n->set_req( copyidx, nullptr );
898
        b->remove_node(insidx--);
899
        b->_ihrp_index--; // Adjust the point where we go hi-pressure
900
        b->_fhrp_index--;
901
        continue;
902
      }
903

904
#define DERIVED 0
905

906
      // ********** Handle USES **********
907
      bool nullcheck = false;
908
      // Implicit null checks never use the spilled value
909
      if( n->is_MachNullCheck() )
910
        nullcheck = true;
911
      if( !nullcheck ) {
912
        // Search all inputs for a Spill-USE
913
        JVMState* jvms = n->jvms();
914
        uint oopoff = jvms ? jvms->oopoff() : cnt;
915
        uint old_last = cnt - 1;
916
        for( inpidx = 1; inpidx < cnt; inpidx++ ) {
917
          // Derived/base pairs may be added to our inputs during this loop.
918
          // If inpidx > old_last, then one of these new inputs is being
919
          // handled. Skip the derived part of the pair, but process
920
          // the base like any other input.
921
          if (inpidx > old_last && ((inpidx - oopoff) & 1) == DERIVED) {
922
            continue;  // skip derived_debug added below
923
          }
924
          // Get lidx of input
925
          uint useidx = _lrg_map.find_id(n->in(inpidx));
926
          // Not a brand-new split, and it is a spill use
927
          if (useidx < _lrg_map.max_lrg_id() && lrgs(useidx).reg() >= LRG::SPILL_REG) {
928
            // Check for valid reaching DEF
929
            slidx = lrg2reach[useidx];
930
            Node *def = Reachblock[slidx];
931
            assert( def != nullptr, "Using Undefined Value in Split()\n");
932

933
            // (+++) %%%% remove this in favor of pre-pass in matcher.cpp
934
            // monitor references do not care where they live, so just hook
935
            if ( jvms && jvms->is_monitor_use(inpidx) ) {
936
              // The effect of this clone is to drop the node out of the block,
937
              // so that the allocator does not see it anymore, and therefore
938
              // does not attempt to assign it a register.
939
              def = clone_node(def, b, C);
940
              if (def == nullptr || C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {
941
                return 0;
942
              }
943
              _lrg_map.extend(def->_idx, 0);
944
              _cfg.map_node_to_block(def, b);
945
              n->set_req(inpidx, def);
946
              continue;
947
            }
948

949
            // Rematerializable?  Then clone def at use site instead
950
            // of store/load
951
            if( def->rematerialize() ) {
952
              int old_size = b->number_of_nodes();
953
              def = split_Rematerialize( def, b, insidx, maxlrg, splits, slidx, lrg2reach, Reachblock, true );
954
              if( !def ) return 0; // Bail out
955
              insidx += b->number_of_nodes()-old_size;
956
            }
957

958
            MachNode *mach = n->is_Mach() ? n->as_Mach() : nullptr;
959
            // Base pointers and oopmap references do not care where they live.
960
            if ((inpidx >= oopoff) ||
961
                (mach && mach->ideal_Opcode() == Op_AddP && inpidx == AddPNode::Base)) {
962
              if (def->rematerialize() && lrgs(useidx)._was_spilled2) {
963
                // This def has been rematerialized a couple of times without
964
                // progress. It doesn't care if it lives UP or DOWN, so
965
                // spill it down now.
966
                int delta = split_USE(MachSpillCopyNode::BasePointerToMem, def,b,n,inpidx,maxlrg,false,false,splits,slidx);
967
                // If it wasn't split bail
968
                if (delta < 0) {
969
                  return 0;
970
                }
971
                maxlrg += delta;
972
                insidx += delta;  // Reset iterator to skip USE side split
973
              } else {
974
                // Just hook the def edge
975
                n->set_req(inpidx, def);
976
              }
977

978
              if (inpidx >= oopoff) {
979
                // After oopoff, we have derived/base pairs.  We must mention all
980
                // derived pointers here as derived/base pairs for GC.  If the
981
                // derived value is spilling and we have a copy both in Reachblock
982
                // (called here 'def') and debug_defs[slidx] we need to mention
983
                // both in derived/base pairs or kill one.
984
                Node *derived_debug = debug_defs[slidx];
985
                if( ((inpidx - oopoff) & 1) == DERIVED && // derived vs base?
986
                    mach && mach->ideal_Opcode() != Op_Halt &&
987
                    derived_debug != nullptr &&
988
                    derived_debug != def ) { // Actual 2nd value appears
989
                  // We have already set 'def' as a derived value.
990
                  // Also set debug_defs[slidx] as a derived value.
991
                  uint k;
992
                  for( k = oopoff; k < cnt; k += 2 )
993
                    if( n->in(k) == derived_debug )
994
                      break;      // Found an instance of debug derived
995
                  if( k == cnt ) {// No instance of debug_defs[slidx]
996
                    // Add a derived/base pair to cover the debug info.
997
                    // We have to process the added base later since it is not
998
                    // handled yet at this point but skip derived part.
999
                    assert(((n->req() - oopoff) & 1) == DERIVED,
1000
                           "must match skip condition above");
1001
                    n->add_req( derived_debug );   // this will be skipped above
1002
                    n->add_req( n->in(inpidx+1) ); // this will be processed
1003
                    // Increment cnt to handle added input edges on
1004
                    // subsequent iterations.
1005
                    cnt += 2;
1006
                  }
1007
                }
1008
              }
1009
              continue;
1010
            }
1011
            // Special logic for DEBUG info
1012
            if( jvms && b->_freq > BLOCK_FREQUENCY(0.5) ) {
1013
              uint debug_start = jvms->debug_start();
1014
              // If this is debug info use & there is a reaching DOWN def
1015
              if ((debug_start <= inpidx) && (debug_defs[slidx] != nullptr)) {
1016
                assert(inpidx < oopoff, "handle only debug info here");
1017
                // Just hook it in & move on
1018
                n->set_req(inpidx, debug_defs[slidx]);
1019
                // (Note that this can make two sides of a split live at the
1020
                // same time: The debug def on stack, and another def in a
1021
                // register.  The GC needs to know about both of them, but any
1022
                // derived pointers after oopoff will refer to only one of the
1023
                // two defs and the GC would therefore miss the other.  Thus
1024
                // this hack is only allowed for debug info which is Java state
1025
                // and therefore never a derived pointer.)
1026
                continue;
1027
              }
1028
            }
1029
            // Grab register mask info
1030
            const RegMask &dmask = def->out_RegMask();
1031
            const RegMask &umask = n->in_RegMask(inpidx);
1032
            bool is_vect = RegMask::is_vector(def->ideal_reg());
1033
            assert(inpidx < oopoff, "cannot use-split oop map info");
1034

1035
            bool dup = UPblock[slidx];
1036
            bool uup = umask.is_UP();
1037

1038
            // Need special logic to handle bound USES. Insert a split at this
1039
            // bound use if we can't rematerialize the def, or if we need the
1040
            // split to form a misaligned pair.
1041
            if( !umask.is_AllStack() &&
1042
                (int)umask.Size() <= lrgs(useidx).num_regs() &&
1043
                (!def->rematerialize() ||
1044
                 (!is_vect && umask.is_misaligned_pair()))) {
1045
              // These need a Split regardless of overlap or pressure
1046
              // SPLIT - NO DEF - NO CISC SPILL
1047
              int delta = split_USE(MachSpillCopyNode::Bound, def,b,n,inpidx,maxlrg,dup,false, splits,slidx);
1048
              // If it wasn't split bail
1049
              if (delta < 0) {
1050
                return 0;
1051
              }
1052
              maxlrg += delta;
1053
              insidx += delta;  // Reset iterator to skip USE side split
1054
              continue;
1055
            }
1056

1057
            if (UseFPUForSpilling && n->is_MachCall() && !uup && !dup ) {
1058
              // The use at the call can force the def down so insert
1059
              // a split before the use to allow the def more freedom.
1060
              int delta = split_USE(MachSpillCopyNode::CallUse, def,b,n,inpidx,maxlrg,dup,false, splits,slidx);
1061
              // If it wasn't split bail
1062
              if (delta < 0) {
1063
                return 0;
1064
              }
1065
              maxlrg += delta;
1066
              insidx += delta;  // Reset iterator to skip USE side split
1067
              continue;
1068
            }
1069

1070
            // Here is the logic chart which describes USE Splitting:
1071
            // 0 = false or DOWN, 1 = true or UP
1072
            //
1073
            // Overlap | DEF | USE | Action
1074
            //-------------------------------------------------------
1075
            //    0    |  0  |  0  | Copy - mem -> mem
1076
            //    0    |  0  |  1  | Split-UP - Check HRP
1077
            //    0    |  1  |  0  | Split-DOWN - Debug Info?
1078
            //    0    |  1  |  1  | Copy - reg -> reg
1079
            //    1    |  0  |  0  | Reset Input Edge (no Split)
1080
            //    1    |  0  |  1  | Split-UP - Check HRP
1081
            //    1    |  1  |  0  | Split-DOWN - Debug Info?
1082
            //    1    |  1  |  1  | Reset Input Edge (no Split)
1083
            //
1084
            // So, if (dup == uup), then overlap test determines action,
1085
            // with true being no split, and false being copy. Else,
1086
            // if DEF is DOWN, Split-UP, and check HRP to decide on
1087
            // resetting DEF. Finally if DEF is UP, Split-DOWN, with
1088
            // special handling for Debug Info.
1089
            if( dup == uup ) {
1090
              if( dmask.overlap(umask) ) {
1091
                // Both are either up or down, and there is overlap, No Split
1092
                n->set_req(inpidx, def);
1093
              }
1094
              else {  // Both are either up or down, and there is no overlap
1095
                if( dup ) {  // If UP, reg->reg copy
1096
                  // COPY ACROSS HERE - NO DEF - NO CISC SPILL
1097
                  int delta = split_USE(MachSpillCopyNode::RegToReg, def,b,n,inpidx,maxlrg,false,false, splits,slidx);
1098
                  // If it wasn't split bail
1099
                  if (delta < 0) {
1100
                    return 0;
1101
                  }
1102
                  maxlrg += delta;
1103
                  insidx += delta;  // Reset iterator to skip USE side split
1104
                }
1105
                else {       // DOWN, mem->mem copy
1106
                  // COPY UP & DOWN HERE - NO DEF - NO CISC SPILL
1107
                  // First Split-UP to move value into Register
1108
                  uint def_ideal = def->ideal_reg();
1109
                  const RegMask* tmp_rm = Matcher::idealreg2regmask[def_ideal];
1110
                  Node *spill = new MachSpillCopyNode(MachSpillCopyNode::MemToReg, def, dmask, *tmp_rm);
1111
                  insert_proj( b, insidx, spill, maxlrg );
1112
                  maxlrg++; insidx++;
1113
                  // Then Split-DOWN as if previous Split was DEF
1114
                  int delta = split_USE(MachSpillCopyNode::RegToMem, spill,b,n,inpidx,maxlrg,false,false, splits,slidx);
1115
                  // If it wasn't split bail
1116
                  if (delta < 0) {
1117
                    return 0;
1118
                  }
1119
                  maxlrg += delta;
1120
                  insidx += delta;  // Reset iterator to skip USE side splits
1121
                }
1122
              }  // End else no overlap
1123
            }  // End if dup == uup
1124
            // dup != uup, so check dup for direction of Split
1125
            else {
1126
              if( dup ) {  // If UP, Split-DOWN and check Debug Info
1127
                // If this node is already a SpillCopy, just patch the edge
1128
                // except the case of spilling to stack.
1129
                if( n->is_SpillCopy() ) {
1130
                  RegMask tmp_rm(umask);
1131
                  tmp_rm.SUBTRACT(Matcher::STACK_ONLY_mask);
1132
                  if( dmask.overlap(tmp_rm) ) {
1133
                    if( def != n->in(inpidx) ) {
1134
                      n->set_req(inpidx, def);
1135
                    }
1136
                    continue;
1137
                  }
1138
                }
1139
                // COPY DOWN HERE - NO DEF - NO CISC SPILL
1140
                int delta = split_USE(MachSpillCopyNode::RegToMem, def,b,n,inpidx,maxlrg,false,false, splits,slidx);
1141
                // If it wasn't split bail
1142
                if (delta < 0) {
1143
                  return 0;
1144
                }
1145
                maxlrg += delta;
1146
                insidx += delta;  // Reset iterator to skip USE side split
1147
                // Check for debug-info split.  Capture it for later
1148
                // debug splits of the same value
1149
                if (jvms && jvms->debug_start() <= inpidx && inpidx < oopoff)
1150
                  debug_defs[slidx] = n->in(inpidx);
1151

1152
              }
1153
              else {       // DOWN, Split-UP and check register pressure
1154
                if( is_high_pressure( b, &lrgs(useidx), insidx ) ) {
1155
                  // COPY UP HERE - NO DEF - CISC SPILL
1156
                  int delta = split_USE(MachSpillCopyNode::MemToReg, def,b,n,inpidx,maxlrg,true,true, splits,slidx);
1157
                  // If it wasn't split bail
1158
                  if (delta < 0) {
1159
                    return 0;
1160
                  }
1161
                  maxlrg += delta;
1162
                  insidx += delta;  // Reset iterator to skip USE side split
1163
                } else {                          // LRP
1164
                  // COPY UP HERE - WITH DEF - NO CISC SPILL
1165
                  int delta = split_USE(MachSpillCopyNode::MemToReg, def,b,n,inpidx,maxlrg,true,false, splits,slidx);
1166
                  // If it wasn't split bail
1167
                  if (delta < 0) {
1168
                    return 0;
1169
                  }
1170
                  // Flag this lift-up in a low-pressure block as
1171
                  // already-spilled, so if it spills again it will
1172
                  // spill hard (instead of not spilling hard and
1173
                  // coalescing away).
1174
                  set_was_spilled(n->in(inpidx));
1175
                  // Since this is a new DEF, update Reachblock & UP
1176
                  Reachblock[slidx] = n->in(inpidx);
1177
                  UPblock[slidx] = true;
1178
                  maxlrg += delta;
1179
                  insidx += delta;  // Reset iterator to skip USE side split
1180
                }
1181
              }  // End else DOWN
1182
            }  // End dup != uup
1183
          }  // End if Spill USE
1184
        }  // End For All Inputs
1185
      }  // End If not nullcheck
1186

1187
      // ********** Handle DEFS **********
1188
      // DEFS either Split DOWN in HRP regions or when the LRG is bound, or
1189
      // just reset the Reaches info in LRP regions.  DEFS must always update
1190
      // UP info.
1191
      if( deflrg.reg() >= LRG::SPILL_REG ) {    // Spilled?
1192
        uint slidx = lrg2reach[defidx];
1193
        // Add to defs list for later assignment of new live range number
1194
        defs.push(n);
1195
        // Set a flag on the Node indicating it has already spilled.
1196
        // Only do it for capacity spills not conflict spills.
1197
        if( !deflrg._direct_conflict )
1198
          set_was_spilled(n);
1199
        assert(!n->is_Phi(),"Cannot insert Phi into DEFS list");
1200
        // Grab UP info for DEF
1201
        const RegMask &dmask = n->out_RegMask();
1202
        bool defup = dmask.is_UP();
1203
        uint ireg = n->ideal_reg();
1204
        bool is_vect = RegMask::is_vector(ireg);
1205
        // Only split at Def if this is a HRP block or bound (and spilled once)
1206
        if( !n->rematerialize() &&
1207
            (((dmask.is_bound(ireg) || (!is_vect && dmask.is_misaligned_pair())) &&
1208
              (deflrg._direct_conflict || deflrg._must_spill)) ||
1209
             // Check for LRG being up in a register and we are inside a high
1210
             // pressure area.  Spill it down immediately.
1211
             (defup && is_high_pressure(b,&deflrg,insidx) && !n->is_SpillCopy())) ) {
1212
          assert( !n->rematerialize(), "" );
1213
          // Do a split at the def site.
1214
          maxlrg = split_DEF( n, b, insidx, maxlrg, Reachblock, debug_defs, splits, slidx );
1215
          // If it wasn't split bail
1216
          if (!maxlrg) {
1217
            return 0;
1218
          }
1219
          // Split DEF's Down
1220
          UPblock[slidx] = 0;
1221
#ifndef PRODUCT
1222
          // DEBUG
1223
          if( trace_spilling() ) {
1224
            tty->print("\nNew Split DOWN DEF of Spill Idx ");
1225
            tty->print("%d, UP %d:\n",slidx,false);
1226
            n->dump();
1227
          }
1228
#endif
1229
        }
1230
        else {                  // Neither bound nor HRP, must be LRP
1231
          // otherwise, just record the def
1232
          Reachblock[slidx] = n;
1233
          // UP should come from the outRegmask() of the DEF
1234
          UPblock[slidx] = defup;
1235
          // Update debug list of reaching down definitions, kill if DEF is UP
1236
          debug_defs[slidx] = defup ? nullptr : n;
1237
#ifndef PRODUCT
1238
          // DEBUG
1239
          if( trace_spilling() ) {
1240
            tty->print("\nNew DEF of Spill Idx ");
1241
            tty->print("%d, UP %d:\n",slidx,defup);
1242
            n->dump();
1243
          }
1244
#endif
1245
        }  // End else LRP
1246
      }  // End if spill def
1247

1248
      // ********** Split Left Over Mem-Mem Moves **********
1249
      // Check for mem-mem copies and split them now.  Do not do this
1250
      // to copies about to be spilled; they will be Split shortly.
1251
      if (copyidx) {
1252
        Node *use = n->in(copyidx);
1253
        uint useidx = _lrg_map.find_id(use);
1254
        if (useidx < _lrg_map.max_lrg_id() &&       // This is not a new split
1255
            OptoReg::is_stack(deflrg.reg()) &&
1256
            deflrg.reg() < LRG::SPILL_REG ) { // And DEF is from stack
1257
          LRG &uselrg = lrgs(useidx);
1258
          if( OptoReg::is_stack(uselrg.reg()) &&
1259
              uselrg.reg() < LRG::SPILL_REG && // USE is from stack
1260
              deflrg.reg() != uselrg.reg() ) { // Not trivially removed
1261
            uint def_ideal_reg = n->bottom_type()->ideal_reg();
1262
            const RegMask &def_rm = *Matcher::idealreg2regmask[def_ideal_reg];
1263
            const RegMask &use_rm = n->in_RegMask(copyidx);
1264
            if( def_rm.overlap(use_rm) && n->is_SpillCopy() ) {  // Bug 4707800, 'n' may be a storeSSL
1265
              if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {  // Check when generating nodes
1266
                return 0;
1267
              }
1268
              Node *spill = new MachSpillCopyNode(MachSpillCopyNode::MemToReg, use,use_rm,def_rm);
1269
              n->set_req(copyidx,spill);
1270
              n->as_MachSpillCopy()->set_in_RegMask(def_rm);
1271
              // Put the spill just before the copy
1272
              insert_proj( b, insidx++, spill, maxlrg++ );
1273
            }
1274
          }
1275
        }
1276
      }
1277
    }  // End For All Instructions in Block - Non-PHI Pass
1278

1279
    // Check if each LRG is live out of this block so as not to propagate
1280
    // beyond the last use of a LRG.
1281
    for( slidx = 0; slidx < spill_cnt; slidx++ ) {
1282
      uint defidx = lidxs.at(slidx);
1283
      IndexSet *liveout = _live->live(b);
1284
      if( !liveout->member(defidx) ) {
1285
#ifdef ASSERT
1286
        if (VerifyRegisterAllocator) {
1287
          // The index defidx is not live.  Check the liveout array to ensure that
1288
          // it contains no members which compress to defidx.  Finding such an
1289
          // instance may be a case to add liveout adjustment in compress_uf_map().
1290
          // See 5063219.
1291
          if (!liveout->is_empty()) {
1292
            uint member;
1293
            IndexSetIterator isi(liveout);
1294
            while ((member = isi.next()) != 0) {
1295
              assert(defidx != _lrg_map.find_const(member), "Live out member has not been compressed");
1296
            }
1297
          }
1298
        }
1299
#endif
1300
        Reachblock[slidx] = nullptr;
1301
      } else {
1302
        assert(Reachblock[slidx] != nullptr,"No reaching definition for liveout value");
1303
      }
1304
    }
1305
#ifndef PRODUCT
1306
    if( trace_spilling() )
1307
      b->dump();
1308
#endif
1309
  }  // End For All Blocks
1310

1311
  //----------PASS 2----------
1312
  // Reset all DEF live range numbers here
1313
  for( insidx = 0; insidx < defs.size(); insidx++ ) {
1314
    // Grab the def
1315
    n1 = defs.at(insidx);
1316
    // Set new lidx for DEF
1317
    new_lrg(n1, maxlrg++);
1318
  }
1319
  //----------Phi Node Splitting----------
1320
  // Clean up a phi here, and assign a new live range number
1321
  // Cycle through this block's predecessors, collecting Reaches
1322
  // info for each spilled LRG and update edges.
1323
  // Walk the phis list to patch inputs, split phis, and name phis
1324
  uint lrgs_before_phi_split = maxlrg;
1325
  for( insidx = 0; insidx < phis.size(); insidx++ ) {
1326
    Node *phi = phis.at(insidx);
1327
    assert(phi->is_Phi(),"This list must only contain Phi Nodes");
1328
    Block *b = _cfg.get_block_for_node(phi);
1329
    // Grab the live range number
1330
    uint lidx = _lrg_map.find_id(phi);
1331
    uint slidx = lrg2reach[lidx];
1332
    // Update node to lidx map
1333
    new_lrg(phi, maxlrg++);
1334
    // Get PASS1's up/down decision for the block.
1335
    int phi_up = !!UP_entry[slidx]->test(b->_pre_order);
1336

1337
    // Force down if double-spilling live range
1338
    if( lrgs(lidx)._was_spilled1 )
1339
      phi_up = false;
1340

1341
    // When splitting a Phi we an split it normal or "inverted".
1342
    // An inverted split makes the splits target the Phi's UP/DOWN
1343
    // sense inverted; then the Phi is followed by a final def-side
1344
    // split to invert back.  It changes which blocks the spill code
1345
    // goes in.
1346

1347
    // Walk the predecessor blocks and assign the reaching def to the Phi.
1348
    // Split Phi nodes by placing USE side splits wherever the reaching
1349
    // DEF has the wrong UP/DOWN value.
1350
    for( uint i = 1; i < b->num_preds(); i++ ) {
1351
      // Get predecessor block pre-order number
1352
      Block *pred = _cfg.get_block_for_node(b->pred(i));
1353
      pidx = pred->_pre_order;
1354
      // Grab reaching def
1355
      Node *def = Reaches[pidx][slidx];
1356
      Node** Reachblock = Reaches[pidx];
1357
      assert( def, "must have reaching def" );
1358
      // If input up/down sense and reg-pressure DISagree
1359
      if (def->rematerialize()) {
1360
        // Place the rematerialized node above any MSCs created during
1361
        // phi node splitting.  end_idx points at the insertion point
1362
        // so look at the node before it.
1363
        int insert = pred->end_idx();
1364
        while (insert >= 1 &&
1365
               pred->get_node(insert - 1)->is_SpillCopy() &&
1366
               _lrg_map.find(pred->get_node(insert - 1)) >= lrgs_before_phi_split) {
1367
          insert--;
1368
        }
1369
        def = split_Rematerialize(def, pred, insert, maxlrg, splits, slidx, lrg2reach, Reachblock, false);
1370
        if (!def) {
1371
          return 0;    // Bail out
1372
        }
1373
      }
1374
      // Update the Phi's input edge array
1375
      phi->set_req(i,def);
1376
      // Grab the UP/DOWN sense for the input
1377
      u1 = UP[pidx][slidx];
1378
      if( u1 != (phi_up != 0)) {
1379
        int delta = split_USE(MachSpillCopyNode::PhiLocationDifferToInputLocation, def, b, phi, i, maxlrg, !u1, false, splits,slidx);
1380
        // If it wasn't split bail
1381
        if (delta < 0) {
1382
          return 0;
1383
        }
1384
        maxlrg += delta;
1385
      }
1386
    }  // End for all inputs to the Phi
1387
  }  // End for all Phi Nodes
1388
  // Update _maxlrg to save Union asserts
1389
  _lrg_map.set_max_lrg_id(maxlrg);
1390

1391

1392
  //----------PASS 3----------
1393
  // Pass over all Phi's to union the live ranges
1394
  for( insidx = 0; insidx < phis.size(); insidx++ ) {
1395
    Node *phi = phis.at(insidx);
1396
    assert(phi->is_Phi(),"This list must only contain Phi Nodes");
1397
    // Walk all inputs to Phi and Union input live range with Phi live range
1398
    for( uint i = 1; i < phi->req(); i++ ) {
1399
      // Grab the input node
1400
      Node *n = phi->in(i);
1401
      assert(n, "node should exist");
1402
      uint lidx = _lrg_map.find(n);
1403
      uint pidx = _lrg_map.find(phi);
1404
      if (lidx < pidx) {
1405
        Union(n, phi);
1406
      }
1407
      else if(lidx > pidx) {
1408
        Union(phi, n);
1409
      }
1410
    }  // End for all inputs to the Phi Node
1411
  }  // End for all Phi Nodes
1412
  // Now union all two address instructions
1413
  for (insidx = 0; insidx < defs.size(); insidx++) {
1414
    // Grab the def
1415
    n1 = defs.at(insidx);
1416
    // Set new lidx for DEF & handle 2-addr instructions
1417
    if (n1->is_Mach() && ((twoidx = n1->as_Mach()->two_adr()) != 0)) {
1418
      assert(_lrg_map.find(n1->in(twoidx)) < maxlrg,"Assigning bad live range index");
1419
      // Union the input and output live ranges
1420
      uint lr1 = _lrg_map.find(n1);
1421
      uint lr2 = _lrg_map.find(n1->in(twoidx));
1422
      if (lr1 < lr2) {
1423
        Union(n1, n1->in(twoidx));
1424
      }
1425
      else if (lr1 > lr2) {
1426
        Union(n1->in(twoidx), n1);
1427
      }
1428
    }  // End if two address
1429
  }  // End for all defs
1430
  // DEBUG
1431
#ifdef ASSERT
1432
  // Validate all live range index assignments
1433
  for (bidx = 0; bidx < _cfg.number_of_blocks(); bidx++) {
1434
    b  = _cfg.get_block(bidx);
1435
    for (insidx = 0; insidx <= b->end_idx(); insidx++) {
1436
      Node *n = b->get_node(insidx);
1437
      uint defidx = _lrg_map.find(n);
1438
      assert(defidx < _lrg_map.max_lrg_id(), "Bad live range index in Split");
1439
      assert(defidx < maxlrg,"Bad live range index in Split");
1440
    }
1441
  }
1442
  // Issue a warning if splitting made no progress
1443
  int noprogress = 0;
1444
  for (slidx = 0; slidx < spill_cnt; slidx++) {
1445
    if (PrintOpto && WizardMode && splits.at(slidx) == 0) {
1446
      tty->print_cr("Failed to split live range %d", lidxs.at(slidx));
1447
      //BREAKPOINT;
1448
    }
1449
    else {
1450
      noprogress++;
1451
    }
1452
  }
1453
  if(!noprogress) {
1454
    tty->print_cr("Failed to make progress in Split");
1455
    //BREAKPOINT;
1456
  }
1457
#endif
1458
  // Return updated count of live ranges
1459
  return maxlrg;
1460
}
1461