jdk

1
/*
2
 * Copyright (c) 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 "opto/callnode.hpp"
27
#include "opto/loopnode.hpp"
28
#include "opto/node.hpp"
29
#include "opto/predicates.hpp"
30

31
// Walk over all Initialized Assertion Predicates and return the entry into the first Initialized Assertion Predicate
32
// (i.e. not belonging to an Initialized Assertion Predicate anymore)
33
Node* AssertionPredicatesWithHalt::find_entry(Node* start_proj) {
34
  Node* entry = start_proj;
35
  while (AssertionPredicateWithHalt::is_predicate(entry)) {
36
    entry = entry->in(0)->in(0);
37
  }
38
  return entry;
39
}
40

41
bool AssertionPredicateWithHalt::is_predicate(const Node* maybe_success_proj) {
42
  if (maybe_success_proj == nullptr || !maybe_success_proj->is_IfProj() || !maybe_success_proj->in(0)->is_If()) {
43
    return false;
44
  }
45
  return has_assertion_predicate_opaque(maybe_success_proj) && has_halt(maybe_success_proj);
46
}
47

48
// Check if the If node of `predicate_proj` has an Opaque4 (Template Assertion Predicate) or an
49
// OpaqueInitializedAssertionPredicate (Initialized Assertion Predicate) node as input.
50
bool AssertionPredicateWithHalt::has_assertion_predicate_opaque(const Node* predicate_proj) {
51
  IfNode* iff = predicate_proj->in(0)->as_If();
52
  Node* bol = iff->in(1);
53
  return bol->is_Opaque4() || bol->is_OpaqueInitializedAssertionPredicate();
54
}
55

56
// Check if the other projection (UCT projection) of `success_proj` has a Halt node as output.
57
bool AssertionPredicateWithHalt::has_halt(const Node* success_proj) {
58
  ProjNode* other_proj = success_proj->as_IfProj()->other_if_proj();
59
  return other_proj->outcnt() == 1 && other_proj->unique_out()->Opcode() == Op_Halt;
60
}
61

62
// Returns the Parse Predicate node if the provided node is a Parse Predicate success proj. Otherwise, return null.
63
ParsePredicateNode* ParsePredicate::init_parse_predicate(Node* parse_predicate_proj,
64
                                                         Deoptimization::DeoptReason deopt_reason) {
65
  assert(parse_predicate_proj != nullptr, "must not be null");
66
  if (parse_predicate_proj->is_IfTrue() && parse_predicate_proj->in(0)->is_ParsePredicate()) {
67
    ParsePredicateNode* parse_predicate_node = parse_predicate_proj->in(0)->as_ParsePredicate();
68
    if (parse_predicate_node->deopt_reason() == deopt_reason) {
69
      return parse_predicate_node;
70
    }
71
  }
72
  return nullptr;
73
}
74

75
bool ParsePredicate::is_predicate(Node* maybe_success_proj) {
76
  if (!maybe_success_proj->is_IfProj()) {
77
    return false;
78
  }
79
  IfNode* if_node = maybe_success_proj->in(0)->as_If();
80
  return if_node->is_ParsePredicate();
81
}
82

83
Deoptimization::DeoptReason RegularPredicateWithUCT::uncommon_trap_reason(IfProjNode* if_proj) {
84
    CallStaticJavaNode* uct_call = if_proj->is_uncommon_trap_if_pattern();
85
    if (uct_call == nullptr) {
86
      return Deoptimization::Reason_none;
87
    }
88
    return Deoptimization::trap_request_reason(uct_call->uncommon_trap_request());
89
}
90

91
bool RegularPredicateWithUCT::is_predicate(Node* maybe_success_proj) {
92
  if (may_be_predicate_if(maybe_success_proj)) {
93
    IfProjNode* success_proj = maybe_success_proj->as_IfProj();
94
    const Deoptimization::DeoptReason deopt_reason = uncommon_trap_reason(success_proj);
95
    return (deopt_reason == Deoptimization::Reason_loop_limit_check ||
96
            deopt_reason == Deoptimization::Reason_predicate ||
97
            deopt_reason == Deoptimization::Reason_profile_predicate);
98
  } else {
99
    return false;
100
  }
101
}
102

103
bool RegularPredicateWithUCT::is_predicate(Node* node, Deoptimization::DeoptReason deopt_reason) {
104
  if (may_be_predicate_if(node)) {
105
    return deopt_reason == uncommon_trap_reason(node->as_IfProj());
106
  } else {
107
    return false;
108
  }
109
}
110

111
// A Runtime Predicate must have an If or a RangeCheck node, while the If should not be a zero trip guard check.
112
bool RegularPredicateWithUCT::may_be_predicate_if(Node* node) {
113
  if (node->is_IfProj()) {
114
    const IfNode* if_node = node->in(0)->as_If();
115
    const int opcode_if = if_node->Opcode();
116
    if ((opcode_if == Op_If && !if_node->is_zero_trip_guard())
117
        || opcode_if == Op_RangeCheck) {
118
      return true;
119
    }
120
  }
121
  return false;
122
}
123

124
bool RuntimePredicate::is_success_proj(Node* node, Deoptimization::DeoptReason deopt_reason) {
125
  return RegularPredicateWithUCT::is_predicate(node, deopt_reason);
126
}
127

128
ParsePredicateIterator::ParsePredicateIterator(const Predicates& predicates) : _current_index(0) {
129
  const PredicateBlock* loop_limit_check_predicate_block = predicates.loop_limit_check_predicate_block();
130
  if (loop_limit_check_predicate_block->has_parse_predicate()) {
131
    _parse_predicates.push(loop_limit_check_predicate_block->parse_predicate());
132
  }
133
  if (UseProfiledLoopPredicate) {
134
    const PredicateBlock* profiled_loop_predicate_block = predicates.profiled_loop_predicate_block();
135
    if (profiled_loop_predicate_block->has_parse_predicate()) {
136
      _parse_predicates.push(profiled_loop_predicate_block->parse_predicate());
137
    }
138
  }
139
  if (UseLoopPredicate) {
140
    const PredicateBlock* loop_predicate_block = predicates.loop_predicate_block();
141
    if (loop_predicate_block->has_parse_predicate()) {
142
      _parse_predicates.push(loop_predicate_block->parse_predicate());
143
    }
144
  }
145
}
146

147
ParsePredicateNode* ParsePredicateIterator::next() {
148
  assert(has_next(), "always check has_next() first");
149
  return _parse_predicates.at(_current_index++);
150
}
151

152
#ifdef ASSERT
153
// Check that the block has at most one Parse Predicate and that we only find Regular Predicate nodes (i.e. IfProj,
154
// If, or RangeCheck nodes).
155
void PredicateBlock::verify_block() {
156
  Node* next = _parse_predicate.entry(); // Skip unique Parse Predicate of this block if present
157
  while (next != _entry) {
158
    assert(!next->is_ParsePredicate(), "can only have one Parse Predicate in a block");
159
    const int opcode = next->Opcode();
160
    assert(next->is_IfProj() || opcode == Op_If || opcode == Op_RangeCheck,
161
           "Regular Predicates consist of an IfProj and an If or RangeCheck node");
162
    assert(opcode != Op_If || !next->as_If()->is_zero_trip_guard(), "should not be zero trip guard");
163
    next = next->in(0);
164
  }
165
}
166
#endif // ASSERT
167

168
// Walk over all Regular Predicates of this block (if any) and return the first node not belonging to the block
169
// anymore (i.e. entry to the first Regular Predicate in this block if any or `regular_predicate_proj` otherwise).
170
Node* PredicateBlock::skip_regular_predicates(Node* regular_predicate_proj, Deoptimization::DeoptReason deopt_reason) {
171
  Node* entry = regular_predicate_proj;
172
  while (RuntimePredicate::is_success_proj(entry, deopt_reason)) {
173
    assert(entry->in(0)->as_If(), "must be If node");
174
    entry = entry->in(0)->in(0);
175
  }
176
  return entry;
177
}
178

179
// This strategy clones the OpaqueLoopInit and OpaqueLoopStride nodes.
180
class CloneStrategy : public TransformStrategyForOpaqueLoopNodes {
181
  PhaseIdealLoop* const _phase;
182
  Node* const _new_ctrl;
183

184
 public:
185
  CloneStrategy(PhaseIdealLoop* phase, Node* new_ctrl)
186
      : _phase(phase),
187
        _new_ctrl(new_ctrl) {}
188
  NONCOPYABLE(CloneStrategy);
189

190
  Node* transform_opaque_init(OpaqueLoopInitNode* opaque_init) const override {
191
    return _phase->clone_and_register(opaque_init, _new_ctrl)->as_OpaqueLoopInit();
192
  }
193

194
  Node* transform_opaque_stride(OpaqueLoopStrideNode* opaque_stride) const override {
195
    return _phase->clone_and_register(opaque_stride, _new_ctrl)->as_OpaqueLoopStride();
196
  }
197
};
198

199
// This strategy replaces the OpaqueLoopInitNode with the provided init node and clones the OpaqueLoopStrideNode.
200
class ReplaceInitAndCloneStrideStrategy : public TransformStrategyForOpaqueLoopNodes {
201
  Node* const _new_init;
202
  Node* const _new_ctrl;
203
  PhaseIdealLoop* const _phase;
204

205
 public:
206
  ReplaceInitAndCloneStrideStrategy(Node* new_init, Node* new_ctrl, PhaseIdealLoop* phase)
207
      : _new_init(new_init),
208
        _new_ctrl(new_ctrl),
209
        _phase(phase) {}
210
  NONCOPYABLE(ReplaceInitAndCloneStrideStrategy);
211

212
  Node* transform_opaque_init(OpaqueLoopInitNode* opaque_init) const override {
213
    return _new_init;
214
  }
215

216
  Node* transform_opaque_stride(OpaqueLoopStrideNode* opaque_stride) const override {
217
    return _phase->clone_and_register(opaque_stride, _new_ctrl)->as_OpaqueLoopStride();
218
  }
219
};
220

221
// This strategy replaces the OpaqueLoopInit and OpaqueLoopStride nodes with the provided init and stride nodes,
222
// respectively.
223
class ReplaceInitAndStrideStrategy : public TransformStrategyForOpaqueLoopNodes {
224
  Node* const _new_init;
225
  Node* const _new_stride;
226

227
 public:
228
  ReplaceInitAndStrideStrategy(Node* new_init, Node* new_stride)
229
      : _new_init(new_init),
230
        _new_stride(new_stride) {}
231
  NONCOPYABLE(ReplaceInitAndStrideStrategy);
232

233
  Node* transform_opaque_init(OpaqueLoopInitNode* opaque_init) const override {
234
    return _new_init;
235
  }
236

237
  Node* transform_opaque_stride(OpaqueLoopStrideNode* opaque_stride) const override {
238
    return _new_stride;
239
  }
240
};
241

242
// Creates an identical clone of this Template Assertion Predicate Expression (i.e.cloning all nodes from the Opaque4Node
243
// to and including the OpaqueLoop* nodes). The cloned nodes are rewired to reflect the same graph structure as found for
244
// this Template Assertion Predicate Expression. The cloned nodes get 'new_ctrl' as ctrl. There is no other update done
245
// for the cloned nodes. Return the newly cloned Opaque4Node.
246
Opaque4Node* TemplateAssertionPredicateExpression::clone(Node* new_ctrl, PhaseIdealLoop* phase) {
247
  CloneStrategy clone_init_and_stride_strategy(phase, new_ctrl);
248
  return clone(clone_init_and_stride_strategy, new_ctrl, phase);
249
}
250

251
// Same as clone() but instead of cloning the OpaqueLoopInitNode, we replace it with the provided 'new_init' node.
252
Opaque4Node* TemplateAssertionPredicateExpression::clone_and_replace_init(Node* new_init, Node* new_ctrl,
253
                                                                          PhaseIdealLoop* phase) {
254
  ReplaceInitAndCloneStrideStrategy replace_init_and_clone_stride_strategy(new_init, new_ctrl, phase);
255
  return clone(replace_init_and_clone_stride_strategy, new_ctrl, phase);
256
}
257

258
// Same as clone() but instead of cloning the OpaqueLoopInit and OpaqueLoopStride node, we replace them with the provided
259
// 'new_init' and 'new_stride' nodes, respectively.
260
Opaque4Node* TemplateAssertionPredicateExpression::clone_and_replace_init_and_stride(Node* new_init, Node* new_stride,
261
                                                                                     Node* new_ctrl,
262
                                                                                     PhaseIdealLoop* phase) {
263
  ReplaceInitAndStrideStrategy replace_init_and_stride_strategy(new_init, new_stride);
264
  return clone(replace_init_and_stride_strategy, new_ctrl, phase);
265
}
266

267
// Class to collect data nodes from a source to target nodes by following the inputs of the source node recursively.
268
// The class takes a node filter to decide which input nodes to follow and a target node predicate to start backtracking
269
// from. All nodes found on all paths from source->target(s) are returned in a Unique_Node_List (without duplicates).
270
class DataNodesOnPathsToTargets : public StackObj {
271
  typedef bool (*NodeCheck)(const Node*);
272

273
  // Node filter function to decide if we should process a node or not while searching for targets.
274
  NodeCheck _node_filter;
275
  // Function to decide if a node is a target node (i.e. where we should start backtracking). This check should also
276
  // trivially pass the _node_filter.
277
  NodeCheck _is_target_node;
278
  // The resulting node collection of all nodes on paths from source->target(s).
279
  Unique_Node_List _collected_nodes;
280
  // List to track all nodes visited on the search for target nodes starting at a start node. These nodes are then used
281
  // in backtracking to find the nodes actually being on a start->target(s) path. This list also serves as visited set
282
  // to avoid double visits of a node which could happen with diamonds shapes.
283
  Unique_Node_List _nodes_to_visit;
284

285
 public:
286
  DataNodesOnPathsToTargets(NodeCheck node_filter, NodeCheck is_target_node)
287
      : _node_filter(node_filter),
288
        _is_target_node(is_target_node) {}
289
  NONCOPYABLE(DataNodesOnPathsToTargets);
290

291
  // Collect all input nodes from 'start_node'->target(s) by applying the node filter to discover new input nodes and
292
  // the target node predicate to stop discovering more inputs and start backtracking. The implementation is done
293
  // with two BFS traversal: One to collect the target nodes (if any) and one to backtrack from the target nodes to
294
  // find all other nodes on the start->target(s) paths.
295
  const Unique_Node_List& collect(Node* start_node) {
296
    assert(_collected_nodes.size() == 0 && _nodes_to_visit.size() == 0, "should not call this method twice in a row");
297
    assert(!_is_target_node(start_node), "no trivial paths where start node is also a target node");
298

299
    collect_target_nodes(start_node);
300
    backtrack_from_target_nodes();
301
    assert(_collected_nodes.size() == 0 || _collected_nodes.member(start_node),
302
           "either target node predicate was never true or must find start node again when doing backtracking work");
303
    return _collected_nodes;
304
  }
305

306
 private:
307
  // Do a BFS from the start_node to collect all target nodes. We can then do another BFS from the target nodes to
308
  // find all nodes on the paths from start->target(s).
309
  // Note: We could do a single DFS pass to search targets and backtrack in one walk. But this is much more complex.
310
  //       Given that the typical Template Assertion Predicate Expression only consists of a few nodes, we aim for
311
  //       simplicity here.
312
  void collect_target_nodes(Node* start_node) {
313
    _nodes_to_visit.push(start_node);
314
    for (uint i = 0; i < _nodes_to_visit.size(); i++) {
315
      Node* next = _nodes_to_visit[i];
316
      for (uint j = 1; j < next->req(); j++) {
317
        Node* input = next->in(j);
318
        if (_is_target_node(input)) {
319
          assert(_node_filter(input), "must also pass node filter");
320
          _collected_nodes.push(input);
321
        } else if (_node_filter(input)) {
322
          _nodes_to_visit.push(input);
323
        }
324
      }
325
    }
326
  }
327

328
  // Backtrack from all previously collected target nodes by using the visited set of the start->target(s) search. If no
329
  // node was collected in the first place (i.e. target node predicate was never true), then nothing needs to be done.
330
  void backtrack_from_target_nodes() {
331
    for (uint i = 0; i < _collected_nodes.size(); i++) {
332
      Node* node_on_path = _collected_nodes[i];
333
      for (DUIterator_Fast jmax, j = node_on_path->fast_outs(jmax); j < jmax; j++) {
334
        Node* use = node_on_path->fast_out(j);
335
        if (_nodes_to_visit.member(use)) {
336
          // use must be on a path from start->target(s) because it was also visited in the first BFS starting from
337
          // the start node.
338
          _collected_nodes.push(use);
339
        }
340
      }
341
    }
342
  }
343
};
344

345
// Clones this Template Assertion Predicate Expression and applies the given strategy to transform the OpaqueLoop* nodes.
346
Opaque4Node* TemplateAssertionPredicateExpression::clone(const TransformStrategyForOpaqueLoopNodes& transform_strategy,
347
                                                         Node* new_ctrl, PhaseIdealLoop* phase) {
348
  ResourceMark rm;
349
  auto is_opaque_loop_node = [](const Node* node) {
350
    return node->is_Opaque1();
351
  };
352
  DataNodesOnPathsToTargets data_nodes_on_path_to_targets(TemplateAssertionPredicateExpressionNode::is_maybe_in_expression,
353
                                                          is_opaque_loop_node);
354
  const Unique_Node_List& collected_nodes = data_nodes_on_path_to_targets.collect(_opaque4_node);
355
  DataNodeGraph data_node_graph(collected_nodes, phase);
356
  const OrigToNewHashtable& orig_to_new = data_node_graph.clone_with_opaque_loop_transform_strategy(transform_strategy, new_ctrl);
357
  assert(orig_to_new.contains(_opaque4_node), "must exist");
358
  Node* opaque4_clone = *orig_to_new.get(_opaque4_node);
359
  return opaque4_clone->as_Opaque4();
360
}
361

362
// Check if this node belongs a Template Assertion Predicate Expression (including OpaqueLoop* nodes).
363
bool TemplateAssertionPredicateExpressionNode::is_in_expression(Node* node) {
364
  if (is_maybe_in_expression(node)) {
365
    ResourceMark rm;
366
    Unique_Node_List list;
367
    list.push(node);
368
    for (uint i = 0; i < list.size(); i++) {
369
      Node* next = list.at(i);
370
      if (next->is_OpaqueLoopInit() || next->is_OpaqueLoopStride()) {
371
        return true;
372
      } else if (is_maybe_in_expression(next)) {
373
        list.push_non_cfg_inputs_of(next);
374
      }
375
    }
376
  }
377
  return false;
378
}
379

380
bool TemplateAssertionPredicateExpressionNode::is_template_assertion_predicate(Node* node) {
381
  return node->is_If() && node->in(1)->is_Opaque4();
382
}
383

384
// Is current node pointed to by iterator a predicate?
385
bool PredicateEntryIterator::has_next() const {
386
    return ParsePredicate::is_predicate(_current) ||
387
           RegularPredicateWithUCT::is_predicate(_current) ||
388
           AssertionPredicateWithHalt::is_predicate(_current);
389
}
390

391
// Skip the current predicate pointed to by iterator by returning the input into the predicate. This could possibly be
392
// a non-predicate node.
393
Node* PredicateEntryIterator::next_entry() {
394
  assert(has_next(), "current must be predicate");
395
  _current = _current->in(0)->in(0);
396
  return _current;
397
}
398