jdk

1
/*
2
 * Copyright (c) 2006, 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 "memory/allocation.inline.hpp"
27
#include "opto/castnode.hpp"
28
#include "opto/cfgnode.hpp"
29
#include "opto/connode.hpp"
30
#include "opto/convertnode.hpp"
31
#include "opto/loopnode.hpp"
32
#include "opto/opaquenode.hpp"
33
#include "opto/predicates.hpp"
34
#include "opto/rootnode.hpp"
35

36
// Loop Unswitching is a loop optimization to move an invariant, non-loop-exiting test in the loop body before the loop.
37
// Such a test is either always true or always false in all loop iterations and could therefore only be executed once.
38
// To achieve that, we duplicate the loop and change the original and cloned loop as follows:
39
// - Original loop -> true-path-loop:
40
//        The true-path of the invariant, non-loop-exiting test in the original loop
41
//        is kept while the false-path is killed. We call this unswitched loop version
42
//        the true-path-loop.
43
// - Cloned loop -> false-path-loop:
44
//        The false-path of the invariant, non-loop-exiting test in the cloned loop
45
//        is kept while the true-path is killed. We call this unswitched loop version
46
//        the false-path loop.
47
//
48
// The invariant, non-loop-exiting test can now be moved before both loops (to only execute it once) and turned into a
49
// loop selector If node to select at runtime which unswitched loop version should be executed.
50
// - Loop selector true?  Execute the true-path-loop.
51
// - Loop selector false? Execute the false-path-loop.
52
//
53
// Note that even though an invariant test that exits the loop could also be optimized with Loop Unswitching, it is more
54
// efficient to simply peel the loop which achieves the same result in a simpler manner (also see policy_peeling()).
55
//
56
// The following graphs summarizes the Loop Unswitching optimization.
57
// We start with the original loop:
58
//
59
//                       [Predicates]
60
//                            |
61
//                       Original Loop
62
//                         stmt1
63
//                         if (invariant-test)
64
//                           if-path
65
//                         else
66
//                           else-path
67
//                         stmt2
68
//                       Endloop
69
//
70
//
71
// which is unswitched into a true-path-loop and a false-path-loop together with a loop selector:
72
//
73
//
74
//            [Initialized Assertion Predicates]
75
//                            |
76
//                 loop selector If (invariant-test)
77
//                    /                   \
78
//                true?                  false?
79
//                /                         \
80
//    [Cloned Parse Predicates]         [Cloned Parse Predicates]
81
//    [Cloned Template                  [Cloned Template
82
//     Assertion Predicates]             Assertion Predicates]
83
//          |                                  |
84
//    True-Path-Loop                    False-Path-Loop
85
//      cloned stmt1                      cloned stmt1
86
//      cloned if-path                    cloned else-path
87
//      cloned stmt2                      cloned stmt2
88
//    Endloop                           Endloop
89

90

91
// Return true if the loop should be unswitched or false otherwise.
92
bool IdealLoopTree::policy_unswitching(PhaseIdealLoop* phase) const {
93
  if (!LoopUnswitching) {
94
    return false;
95
  }
96
  if (!_head->is_Loop()) {
97
    return false;
98
  }
99

100
  // If nodes are depleted, some transform has miscalculated its needs.
101
  assert(!phase->exceeding_node_budget(), "sanity");
102

103
  // check for vectorized loops, any unswitching was already applied
104
  if (_head->is_CountedLoop() && _head->as_CountedLoop()->is_unroll_only()) {
105
    return false;
106
  }
107

108
  LoopNode* head = _head->as_Loop();
109
  if (head->unswitch_count() + 1 > head->unswitch_max()) {
110
    return false;
111
  }
112
  if (phase->find_unswitch_candidate(this) == nullptr) {
113
    return false;
114
  }
115

116
  // Too speculative if running low on nodes.
117
  return phase->may_require_nodes(est_loop_clone_sz(2));
118
}
119

120
// Find an invariant test in the loop body that does not exit the loop. If multiple tests are found, we pick the first
121
// one in the loop body. Return the "unswitch candidate" If to apply Loop Unswitching on.
122
IfNode* PhaseIdealLoop::find_unswitch_candidate(const IdealLoopTree* loop) const {
123
  LoopNode* head = loop->_head->as_Loop();
124
  IfNode* unswitch_candidate = nullptr;
125
  Node* n = head->in(LoopNode::LoopBackControl);
126
  while (n != head) {
127
    Node* n_dom = idom(n);
128
    if (n->is_Region()) {
129
      if (n_dom->is_If()) {
130
        IfNode* iff = n_dom->as_If();
131
        if (iff->in(1)->is_Bool()) {
132
          BoolNode* bol = iff->in(1)->as_Bool();
133
          if (bol->in(1)->is_Cmp()) {
134
            // If condition is invariant and not a loop exit,
135
            // then found reason to unswitch.
136
            if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) {
137
              assert(iff->Opcode() == Op_If || iff->is_RangeCheck() || iff->is_BaseCountedLoopEnd(), "valid ifs");
138
              unswitch_candidate = iff;
139
            }
140
          }
141
        }
142
      }
143
    }
144
    n = n_dom;
145
  }
146
  return unswitch_candidate;
147
}
148

149
// This class creates an If node (i.e. loop selector) that selects if the true-path-loop or the false-path-loop should be
150
// executed at runtime. This is done by finding an invariant and non-loop-exiting unswitch candidate If node (guaranteed
151
// to exist at this point) to perform Loop Unswitching on.
152
class UnswitchedLoopSelector : public StackObj {
153
  PhaseIdealLoop* const _phase;
154
  IdealLoopTree* const _outer_loop;
155
  Node* const _original_loop_entry;
156
  IfNode* const _unswitch_candidate;
157
  IfNode* const _selector;
158
  IfTrueNode* const _true_path_loop_proj;
159
  IfFalseNode* const _false_path_loop_proj;
160

161
  enum PathToLoop { TRUE_PATH, FALSE_PATH };
162

163
 public:
164
  UnswitchedLoopSelector(IdealLoopTree* loop)
165
      : _phase(loop->_phase),
166
        _outer_loop(loop->skip_strip_mined()->_parent),
167
        _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
168
        _unswitch_candidate(find_unswitch_candidate(loop)),
169
        _selector(create_selector_if()),
170
        _true_path_loop_proj(create_proj_to_loop(TRUE_PATH)->as_IfTrue()),
171
        _false_path_loop_proj(create_proj_to_loop(FALSE_PATH)->as_IfFalse()) {
172
  }
173
  NONCOPYABLE(UnswitchedLoopSelector);
174

175
 private:
176
  IfNode* find_unswitch_candidate(IdealLoopTree* loop) {
177
    IfNode* unswitch_candidate = _phase->find_unswitch_candidate(loop);
178
    assert(unswitch_candidate != nullptr, "guaranteed to exist by policy_unswitching");
179
    assert(_phase->is_member(loop, unswitch_candidate), "must be inside original loop");
180
    return unswitch_candidate;
181
  }
182

183
  IfNode* create_selector_if() const {
184
    const uint dom_depth = _phase->dom_depth(_original_loop_entry);
185
    _phase->igvn().rehash_node_delayed(_original_loop_entry);
186
    BoolNode* unswitch_candidate_bool = _unswitch_candidate->in(1)->as_Bool();
187
    IfNode* selector_if = IfNode::make_with_same_profile(_unswitch_candidate, _original_loop_entry,
188
                                                         unswitch_candidate_bool);
189
    _phase->register_node(selector_if, _outer_loop, _original_loop_entry, dom_depth);
190
    return selector_if;
191
  }
192

193
  IfProjNode* create_proj_to_loop(const PathToLoop path_to_loop) {
194
    const uint dom_depth = _phase->dom_depth(_original_loop_entry);
195
    IfProjNode* proj_to_loop;
196
    if (path_to_loop == TRUE_PATH) {
197
      proj_to_loop = new IfTrueNode(_selector);
198
    } else {
199
      proj_to_loop = new IfFalseNode(_selector);
200
    }
201
    _phase->register_node(proj_to_loop, _outer_loop, _selector, dom_depth);
202
    return proj_to_loop;
203
  }
204

205
 public:
206
  IfNode* unswitch_candidate() const {
207
    return _unswitch_candidate;
208
  }
209

210
  IfNode* selector() const {
211
    return _selector;
212
  }
213

214
  IfTrueNode* true_path_loop_proj() const {
215
    return _true_path_loop_proj;
216
  }
217

218
  IfFalseNode* false_path_loop_proj() const {
219
    return _false_path_loop_proj;
220
  }
221
};
222

223
// Class to unswitch the original loop and create Predicates at the new unswitched loop versions. The newly cloned loop
224
// becomes the false-path-loop while original loop becomes the true-path-loop.
225
class OriginalLoop : public StackObj {
226
  LoopNode* const _loop_head; // OuterStripMinedLoopNode if loop strip mined, else just the loop head.
227
  IdealLoopTree* const _loop;
228
  Node_List& _old_new;
229
  PhaseIdealLoop* const _phase;
230

231
 public:
232
  OriginalLoop(IdealLoopTree* loop, Node_List& old_new)
233
      : _loop_head(loop->_head->as_Loop()->skip_strip_mined()),
234
        _loop(loop),
235
        _old_new(old_new),
236
        _phase(loop->_phase) {}
237
  NONCOPYABLE(OriginalLoop);
238

239
 private:
240
  void fix_loop_entries(IfProjNode* true_path_loop_entry, IfProjNode* false_path_loop_entry) {
241
    _phase->replace_loop_entry(_loop_head, true_path_loop_entry);
242
    LoopNode* false_path_loop_strip_mined_head = old_to_new(_loop_head)->as_Loop();
243
    _phase->replace_loop_entry(false_path_loop_strip_mined_head, false_path_loop_entry);
244
  }
245

246
  Node* old_to_new(const Node* old) const {
247
    return _old_new[old->_idx];
248
  }
249

250
#ifdef ASSERT
251
  void verify_unswitched_loop_versions(LoopNode* true_path_loop_head,
252
                                       const UnswitchedLoopSelector& unswitched_loop_selector) const {
253
    verify_unswitched_loop_version(true_path_loop_head, unswitched_loop_selector.true_path_loop_proj());
254
    verify_unswitched_loop_version(old_to_new(true_path_loop_head)->as_Loop(),
255
                                   unswitched_loop_selector.false_path_loop_proj());
256
  }
257

258
  static void verify_unswitched_loop_version(LoopNode* loop_head, IfProjNode* loop_selector_if_proj) {
259
    Node* entry = loop_head->skip_strip_mined()->in(LoopNode::EntryControl);
260
    const Predicates predicates(entry);
261
    // When skipping all predicates, we should end up at 'loop_selector_if_proj'.
262
    assert(loop_selector_if_proj == predicates.entry(), "should end up at loop selector If");
263
  }
264
#endif // ASSERT
265

266
  // Remove the unswitch candidate If nodes in both unswitched loop versions which are now dominated by the loop selector
267
  // If node. Keep the true-path-path in the true-path-loop and the false-path-path in the false-path-loop by setting
268
  // the bool input accordingly. The unswitch candidate If nodes are folded in the next IGVN round.
269
  void remove_unswitch_candidate_from_loops(const UnswitchedLoopSelector& unswitched_loop_selector) {
270
    IfNode* unswitching_candidate = unswitched_loop_selector.unswitch_candidate();
271
    _phase->igvn().rehash_node_delayed(unswitching_candidate);
272
    _phase->dominated_by(unswitched_loop_selector.true_path_loop_proj(), unswitching_candidate);
273

274
    IfNode* unswitching_candidate_clone = _old_new[unswitching_candidate->_idx]->as_If();
275
    _phase->igvn().rehash_node_delayed(unswitching_candidate_clone);
276
    _phase->dominated_by(unswitched_loop_selector.false_path_loop_proj(), unswitching_candidate_clone);
277
  }
278

279
 public:
280
  // Unswitch the original loop on the invariant loop selector by creating a true-path-loop and a false-path-loop.
281
  // Remove the unswitch candidate If from both unswitched loop versions which are now covered by the loop selector If.
282
  void unswitch(const UnswitchedLoopSelector& unswitched_loop_selector) {
283
    _phase->clone_loop(_loop, _old_new, _phase->dom_depth(_loop_head),
284
                       PhaseIdealLoop::CloneIncludesStripMined, unswitched_loop_selector.selector());
285

286
    // At this point, the selector If projections are the corresponding loop entries.
287
    // clone_parse_and_assertion_predicates_to_unswitched_loop() could clone additional predicates after the selector
288
    // If projections. The loop entries are updated accordingly.
289
    IfProjNode* true_path_loop_entry = unswitched_loop_selector.true_path_loop_proj();
290
    IfProjNode* false_path_loop_entry = unswitched_loop_selector.false_path_loop_proj();
291
    _phase->clone_parse_and_assertion_predicates_to_unswitched_loop(_loop, _old_new,
292
                                                                    true_path_loop_entry, false_path_loop_entry);
293

294
    fix_loop_entries(true_path_loop_entry, false_path_loop_entry);
295

296
    DEBUG_ONLY(verify_unswitched_loop_versions(_loop->_head->as_Loop(), unswitched_loop_selector);)
297

298
    _phase->recompute_dom_depth();
299
    remove_unswitch_candidate_from_loops(unswitched_loop_selector);
300
  }
301
};
302

303
// See comments below file header for more information about Loop Unswitching.
304
void PhaseIdealLoop::do_unswitching(IdealLoopTree* loop, Node_List& old_new) {
305
  assert(LoopUnswitching, "LoopUnswitching must be enabled");
306

307
  LoopNode* original_head = loop->_head->as_Loop();
308
  if (has_control_dependencies_from_predicates(original_head)) {
309
    NOT_PRODUCT(trace_loop_unswitching_impossible(original_head);)
310
    return;
311
  }
312

313
  NOT_PRODUCT(trace_loop_unswitching_count(loop, original_head);)
314
  C->print_method(PHASE_BEFORE_LOOP_UNSWITCHING, 4, original_head);
315

316
  revert_to_normal_loop(original_head);
317

318
  const UnswitchedLoopSelector unswitched_loop_selector(loop);
319
  OriginalLoop original_loop(loop, old_new);
320
  original_loop.unswitch(unswitched_loop_selector);
321

322
  hoist_invariant_check_casts(loop, old_new, unswitched_loop_selector);
323
  add_unswitched_loop_version_bodies_to_igvn(loop, old_new);
324

325
  LoopNode* new_head = old_new[original_head->_idx]->as_Loop();
326
  increment_unswitch_counts(original_head, new_head);
327

328
  NOT_PRODUCT(trace_loop_unswitching_result(unswitched_loop_selector, original_head, new_head);)
329
  C->print_method(PHASE_AFTER_LOOP_UNSWITCHING, 4, new_head);
330
  C->set_major_progress();
331
}
332

333
bool PhaseIdealLoop::has_control_dependencies_from_predicates(LoopNode* head) {
334
  Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
335
  const Predicates predicates(entry);
336
  if (predicates.has_any()) {
337
    assert(entry->is_IfProj(), "sanity - must be ifProj since there is at least one predicate");
338
    if (entry->outcnt() > 1) {
339
      // Bailout if there are predicates from which there are additional control dependencies (i.e. from loop
340
      // entry 'entry') to previously partially peeled statements since this case is not handled and can lead
341
      // to a wrong execution. Remove this bailout, once this is fixed.
342
      return true;
343
    }
344
  }
345
  return false;
346
}
347

348
#ifndef PRODUCT
349
void PhaseIdealLoop::trace_loop_unswitching_impossible(const LoopNode* original_head) {
350
  if (TraceLoopUnswitching) {
351
    tty->print_cr("Loop Unswitching \"%d %s\" not possible due to control dependencies",
352
                  original_head->_idx, original_head->Name());
353
  }
354
}
355

356
void PhaseIdealLoop::trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head) {
357
  if (TraceLoopOpts) {
358
    tty->print("Unswitch   %d ", original_head->unswitch_count() + 1);
359
    loop->dump_head();
360
  }
361
}
362

363
void PhaseIdealLoop::trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,
364
                                                   const LoopNode* original_head, const LoopNode* new_head) {
365
  if (TraceLoopUnswitching) {
366
    IfNode* unswitch_candidate = unswitched_loop_selector.unswitch_candidate();
367
    IfNode* loop_selector = unswitched_loop_selector.selector();
368
    tty->print_cr("Loop Unswitching:");
369
    tty->print_cr("- Unswitch-Candidate-If: %d %s", unswitch_candidate->_idx, unswitch_candidate->Name());
370
    tty->print_cr("- Loop-Selector-If: %d %s", loop_selector->_idx, loop_selector->Name());
371
    tty->print_cr("- True-Path-Loop (=Orig): %d %s", original_head->_idx, original_head->Name());
372
    tty->print_cr("- False-Path-Loop (=Clone): %d %s", new_head->_idx, new_head->Name());
373
  }
374
}
375
#endif
376

377
// When unswitching a counted loop, we need to convert it back to a normal loop since it's not a proper pre, main or,
378
// post loop anymore after loop unswitching.
379
void PhaseIdealLoop::revert_to_normal_loop(const LoopNode* loop_head) {
380
  CountedLoopNode* cl = loop_head->isa_CountedLoop();
381
  if (cl != nullptr && !cl->is_normal_loop()) {
382
    cl->set_normal_loop();
383
  }
384
}
385

386
// Hoist invariant CheckCastPPNodes out of each unswitched loop version to the appropriate loop selector If projection.
387
void PhaseIdealLoop::hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
388
                                                 const UnswitchedLoopSelector& unswitched_loop_selector) {
389
  IfNode* unswitch_candidate = unswitched_loop_selector.unswitch_candidate();
390
  IfNode* loop_selector = unswitched_loop_selector.selector();
391
  ResourceMark rm;
392
  GrowableArray<CheckCastPPNode*> loop_invariant_check_casts;
393
  for (DUIterator_Fast imax, i = unswitch_candidate->fast_outs(imax); i < imax; i++) {
394
    IfProjNode* proj = unswitch_candidate->fast_out(i)->as_IfProj();
395
    // Copy to a worklist for easier manipulation
396
    for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
397
      CheckCastPPNode* check_cast = proj->fast_out(j)->isa_CheckCastPP();
398
      if (check_cast != nullptr && loop->is_invariant(check_cast->in(1))) {
399
        loop_invariant_check_casts.push(check_cast);
400
      }
401
    }
402
    IfProjNode* loop_selector_if_proj = loop_selector->proj_out(proj->_con)->as_IfProj();
403
    while (loop_invariant_check_casts.length() > 0) {
404
      CheckCastPPNode* cast = loop_invariant_check_casts.pop();
405
      Node* cast_clone = cast->clone();
406
      cast_clone->set_req(0, loop_selector_if_proj);
407
      _igvn.replace_input_of(cast, 1, cast_clone);
408
      register_new_node(cast_clone, loop_selector_if_proj);
409
      // Same for the clone
410
      Node* use_clone = old_new[cast->_idx];
411
      _igvn.replace_input_of(use_clone, 1, cast_clone);
412
    }
413
  }
414
}
415

416
// Enable more optimizations possibilities in the next IGVN round.
417
void PhaseIdealLoop::add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new) {
418
  loop->record_for_igvn();
419
  for(int i = loop->_body.size() - 1; i >= 0 ; i--) {
420
    Node* n = loop->_body[i];
421
    Node* n_clone = old_new[n->_idx];
422
    _igvn._worklist.push(n_clone);
423
  }
424
}
425

426
void PhaseIdealLoop::increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head) {
427
  const int unswitch_count = original_head->unswitch_count() + 1;
428
  original_head->set_unswitch_count(unswitch_count);
429
  new_head->set_unswitch_count(unswitch_count);
430
}
431

432