|
1 /* |
|
2 * Copyright 1997-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or |
|
21 * have any questions. |
|
22 * |
|
23 */ |
|
24 |
|
25 // Portions of code courtesy of Clifford Click |
|
26 |
|
27 // Optimization - Graph Style |
|
28 |
|
29 class Matcher; |
|
30 class Node; |
|
31 class RegionNode; |
|
32 class TypeNode; |
|
33 class PhiNode; |
|
34 class GotoNode; |
|
35 class MultiNode; |
|
36 class MultiBranchNode; |
|
37 class IfNode; |
|
38 class PCTableNode; |
|
39 class JumpNode; |
|
40 class CatchNode; |
|
41 class NeverBranchNode; |
|
42 class ProjNode; |
|
43 class CProjNode; |
|
44 class IfTrueNode; |
|
45 class IfFalseNode; |
|
46 class CatchProjNode; |
|
47 class JProjNode; |
|
48 class JumpProjNode; |
|
49 class SCMemProjNode; |
|
50 class PhaseIdealLoop; |
|
51 |
|
52 //------------------------------RegionNode------------------------------------- |
|
53 // The class of RegionNodes, which can be mapped to basic blocks in the |
|
54 // program. Their inputs point to Control sources. PhiNodes (described |
|
55 // below) have an input point to a RegionNode. Merged data inputs to PhiNodes |
|
56 // correspond 1-to-1 with RegionNode inputs. The zero input of a PhiNode is |
|
57 // the RegionNode, and the zero input of the RegionNode is itself. |
|
58 class RegionNode : public Node { |
|
59 public: |
|
60 // Node layout (parallels PhiNode): |
|
61 enum { Region, // Generally points to self. |
|
62 Control // Control arcs are [1..len) |
|
63 }; |
|
64 |
|
65 RegionNode( uint required ) : Node(required) { |
|
66 init_class_id(Class_Region); |
|
67 init_req(0,this); |
|
68 } |
|
69 |
|
70 Node* is_copy() const { |
|
71 const Node* r = _in[Region]; |
|
72 if (r == NULL) |
|
73 return nonnull_req(); |
|
74 return NULL; // not a copy! |
|
75 } |
|
76 PhiNode* has_phi() const; // returns an arbitrary phi user, or NULL |
|
77 PhiNode* has_unique_phi() const; // returns the unique phi user, or NULL |
|
78 // Is this region node unreachable from root? |
|
79 bool is_unreachable_region(PhaseGVN *phase) const; |
|
80 virtual int Opcode() const; |
|
81 virtual bool pinned() const { return (const Node *)in(0) == this; } |
|
82 virtual bool is_CFG () const { return true; } |
|
83 virtual uint hash() const { return NO_HASH; } // CFG nodes do not hash |
|
84 virtual bool depends_only_on_test() const { return false; } |
|
85 virtual const Type *bottom_type() const { return Type::CONTROL; } |
|
86 virtual const Type *Value( PhaseTransform *phase ) const; |
|
87 virtual Node *Identity( PhaseTransform *phase ); |
|
88 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); |
|
89 virtual const RegMask &out_RegMask() const; |
|
90 }; |
|
91 |
|
92 //------------------------------JProjNode-------------------------------------- |
|
93 // jump projection for node that produces multiple control-flow paths |
|
94 class JProjNode : public ProjNode { |
|
95 public: |
|
96 JProjNode( Node* ctrl, uint idx ) : ProjNode(ctrl,idx) {} |
|
97 virtual int Opcode() const; |
|
98 virtual bool is_CFG() const { return true; } |
|
99 virtual uint hash() const { return NO_HASH; } // CFG nodes do not hash |
|
100 virtual const Node* is_block_proj() const { return in(0); } |
|
101 virtual const RegMask& out_RegMask() const; |
|
102 virtual uint ideal_reg() const { return 0; } |
|
103 }; |
|
104 |
|
105 //------------------------------PhiNode---------------------------------------- |
|
106 // PhiNodes merge values from different Control paths. Slot 0 points to the |
|
107 // controlling RegionNode. Other slots map 1-for-1 with incoming control flow |
|
108 // paths to the RegionNode. For speed reasons (to avoid another pass) we |
|
109 // can turn PhiNodes into copys in-place by NULL'ing out their RegionNode |
|
110 // input in slot 0. |
|
111 class PhiNode : public TypeNode { |
|
112 const TypePtr* const _adr_type; // non-null only for Type::MEMORY nodes. |
|
113 // Size is bigger to hold the _adr_type field. |
|
114 virtual uint hash() const; // Check the type |
|
115 virtual uint cmp( const Node &n ) const; |
|
116 virtual uint size_of() const { return sizeof(*this); } |
|
117 |
|
118 // Determine a unique non-trivial input, if any. |
|
119 // Ignore casts if it helps. Return NULL on failure. |
|
120 Node* unique_input(PhaseTransform *phase); |
|
121 // Determine if CMoveNode::is_cmove_id can be used at this join point. |
|
122 Node* is_cmove_id(PhaseTransform* phase, int true_path); |
|
123 |
|
124 public: |
|
125 // Node layout (parallels RegionNode): |
|
126 enum { Region, // Control input is the Phi's region. |
|
127 Input // Input values are [1..len) |
|
128 }; |
|
129 |
|
130 PhiNode( Node *r, const Type *t, const TypePtr* at = NULL ) |
|
131 : TypeNode(t,r->req()), _adr_type(at) { |
|
132 init_class_id(Class_Phi); |
|
133 init_req(0, r); |
|
134 verify_adr_type(); |
|
135 } |
|
136 // create a new phi with in edges matching r and set (initially) to x |
|
137 static PhiNode* make( Node* r, Node* x ); |
|
138 // extra type arguments override the new phi's bottom_type and adr_type |
|
139 static PhiNode* make( Node* r, Node* x, const Type *t, const TypePtr* at = NULL ); |
|
140 // create a new phi with narrowed memory type |
|
141 PhiNode* slice_memory(const TypePtr* adr_type) const; |
|
142 // like make(r, x), but does not initialize the in edges to x |
|
143 static PhiNode* make_blank( Node* r, Node* x ); |
|
144 |
|
145 // Accessors |
|
146 RegionNode* region() const { Node* r = in(Region); assert(!r || r->is_Region(), ""); return (RegionNode*)r; } |
|
147 |
|
148 Node* is_copy() const { |
|
149 // The node is a real phi if _in[0] is a Region node. |
|
150 DEBUG_ONLY(const Node* r = _in[Region];) |
|
151 assert(r != NULL && r->is_Region(), "Not valid control"); |
|
152 return NULL; // not a copy! |
|
153 } |
|
154 |
|
155 // Check for a simple dead loop. |
|
156 enum LoopSafety { Safe = 0, Unsafe, UnsafeLoop }; |
|
157 LoopSafety simple_data_loop_check(Node *in) const; |
|
158 // Is it unsafe data loop? It becomes a dead loop if this phi node removed. |
|
159 bool is_unsafe_data_reference(Node *in) const; |
|
160 int is_diamond_phi() const; |
|
161 virtual int Opcode() const; |
|
162 virtual bool pinned() const { return in(0) != 0; } |
|
163 virtual const TypePtr *adr_type() const { verify_adr_type(true); return _adr_type; } |
|
164 virtual const Type *Value( PhaseTransform *phase ) const; |
|
165 virtual Node *Identity( PhaseTransform *phase ); |
|
166 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); |
|
167 virtual const RegMask &out_RegMask() const; |
|
168 virtual const RegMask &in_RegMask(uint) const; |
|
169 #ifndef PRODUCT |
|
170 virtual void dump_spec(outputStream *st) const; |
|
171 #endif |
|
172 #ifdef ASSERT |
|
173 void verify_adr_type(VectorSet& visited, const TypePtr* at) const; |
|
174 void verify_adr_type(bool recursive = false) const; |
|
175 #else //ASSERT |
|
176 void verify_adr_type(bool recursive = false) const {} |
|
177 #endif //ASSERT |
|
178 }; |
|
179 |
|
180 //------------------------------GotoNode--------------------------------------- |
|
181 // GotoNodes perform direct branches. |
|
182 class GotoNode : public Node { |
|
183 public: |
|
184 GotoNode( Node *control ) : Node(control) { |
|
185 init_flags(Flag_is_Goto); |
|
186 } |
|
187 virtual int Opcode() const; |
|
188 virtual bool pinned() const { return true; } |
|
189 virtual bool is_CFG() const { return true; } |
|
190 virtual uint hash() const { return NO_HASH; } // CFG nodes do not hash |
|
191 virtual const Node *is_block_proj() const { return this; } |
|
192 virtual bool depends_only_on_test() const { return false; } |
|
193 virtual const Type *bottom_type() const { return Type::CONTROL; } |
|
194 virtual const Type *Value( PhaseTransform *phase ) const; |
|
195 virtual Node *Identity( PhaseTransform *phase ); |
|
196 virtual const RegMask &out_RegMask() const; |
|
197 }; |
|
198 |
|
199 //------------------------------CProjNode-------------------------------------- |
|
200 // control projection for node that produces multiple control-flow paths |
|
201 class CProjNode : public ProjNode { |
|
202 public: |
|
203 CProjNode( Node *ctrl, uint idx ) : ProjNode(ctrl,idx) {} |
|
204 virtual int Opcode() const; |
|
205 virtual bool is_CFG() const { return true; } |
|
206 virtual uint hash() const { return NO_HASH; } // CFG nodes do not hash |
|
207 virtual const Node *is_block_proj() const { return in(0); } |
|
208 virtual const RegMask &out_RegMask() const; |
|
209 virtual uint ideal_reg() const { return 0; } |
|
210 }; |
|
211 |
|
212 //---------------------------MultiBranchNode----------------------------------- |
|
213 // This class defines a MultiBranchNode, a MultiNode which yields multiple |
|
214 // control values. These are distinguished from other types of MultiNodes |
|
215 // which yield multiple values, but control is always and only projection #0. |
|
216 class MultiBranchNode : public MultiNode { |
|
217 public: |
|
218 MultiBranchNode( uint required ) : MultiNode(required) { |
|
219 init_class_id(Class_MultiBranch); |
|
220 } |
|
221 }; |
|
222 |
|
223 //------------------------------IfNode----------------------------------------- |
|
224 // Output selected Control, based on a boolean test |
|
225 class IfNode : public MultiBranchNode { |
|
226 // Size is bigger to hold the probability field. However, _prob does not |
|
227 // change the semantics so it does not appear in the hash & cmp functions. |
|
228 virtual uint size_of() const { return sizeof(*this); } |
|
229 public: |
|
230 |
|
231 // Degrees of branch prediction probability by order of magnitude: |
|
232 // PROB_UNLIKELY_1e(N) is a 1 in 1eN chance. |
|
233 // PROB_LIKELY_1e(N) is a 1 - PROB_UNLIKELY_1e(N) |
|
234 #define PROB_UNLIKELY_MAG(N) (1e- ## N ## f) |
|
235 #define PROB_LIKELY_MAG(N) (1.0f-PROB_UNLIKELY_MAG(N)) |
|
236 |
|
237 // Maximum and minimum branch prediction probabilties |
|
238 // 1 in 1,000,000 (magnitude 6) |
|
239 // |
|
240 // Although PROB_NEVER == PROB_MIN and PROB_ALWAYS == PROB_MAX |
|
241 // they are used to distinguish different situations: |
|
242 // |
|
243 // The name PROB_MAX (PROB_MIN) is for probabilities which correspond to |
|
244 // very likely (unlikely) but with a concrete possibility of a rare |
|
245 // contrary case. These constants would be used for pinning |
|
246 // measurements, and as measures for assertions that have high |
|
247 // confidence, but some evidence of occasional failure. |
|
248 // |
|
249 // The name PROB_ALWAYS (PROB_NEVER) is to stand for situations for which |
|
250 // there is no evidence at all that the contrary case has ever occurred. |
|
251 |
|
252 #define PROB_NEVER PROB_UNLIKELY_MAG(6) |
|
253 #define PROB_ALWAYS PROB_LIKELY_MAG(6) |
|
254 |
|
255 #define PROB_MIN PROB_UNLIKELY_MAG(6) |
|
256 #define PROB_MAX PROB_LIKELY_MAG(6) |
|
257 |
|
258 // Static branch prediction probabilities |
|
259 // 1 in 10 (magnitude 1) |
|
260 #define PROB_STATIC_INFREQUENT PROB_UNLIKELY_MAG(1) |
|
261 #define PROB_STATIC_FREQUENT PROB_LIKELY_MAG(1) |
|
262 |
|
263 // Fair probability 50/50 |
|
264 #define PROB_FAIR (0.5f) |
|
265 |
|
266 // Unknown probability sentinel |
|
267 #define PROB_UNKNOWN (-1.0f) |
|
268 |
|
269 // Probability "constructors", to distinguish as a probability any manifest |
|
270 // constant without a names |
|
271 #define PROB_LIKELY(x) ((float) (x)) |
|
272 #define PROB_UNLIKELY(x) (1.0f - (float)(x)) |
|
273 |
|
274 // Other probabilities in use, but without a unique name, are documented |
|
275 // here for lack of a better place: |
|
276 // |
|
277 // 1 in 1000 probabilities (magnitude 3): |
|
278 // threshold for converting to conditional move |
|
279 // likelihood of null check failure if a null HAS been seen before |
|
280 // likelihood of slow path taken in library calls |
|
281 // |
|
282 // 1 in 10,000 probabilities (magnitude 4): |
|
283 // threshold for making an uncommon trap probability more extreme |
|
284 // threshold for for making a null check implicit |
|
285 // likelihood of needing a gc if eden top moves during an allocation |
|
286 // likelihood of a predicted call failure |
|
287 // |
|
288 // 1 in 100,000 probabilities (magnitude 5): |
|
289 // threshold for ignoring counts when estimating path frequency |
|
290 // likelihood of FP clipping failure |
|
291 // likelihood of catching an exception from a try block |
|
292 // likelihood of null check failure if a null has NOT been seen before |
|
293 // |
|
294 // Magic manifest probabilities such as 0.83, 0.7, ... can be found in |
|
295 // gen_subtype_check() and catch_inline_exceptions(). |
|
296 |
|
297 float _prob; // Probability of true path being taken. |
|
298 float _fcnt; // Frequency counter |
|
299 IfNode( Node *control, Node *b, float p, float fcnt ) |
|
300 : MultiBranchNode(2), _prob(p), _fcnt(fcnt) { |
|
301 init_class_id(Class_If); |
|
302 init_req(0,control); |
|
303 init_req(1,b); |
|
304 } |
|
305 virtual int Opcode() const; |
|
306 virtual bool pinned() const { return true; } |
|
307 virtual const Type *bottom_type() const { return TypeTuple::IFBOTH; } |
|
308 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); |
|
309 virtual const Type *Value( PhaseTransform *phase ) const; |
|
310 virtual const RegMask &out_RegMask() const; |
|
311 void dominated_by(Node* prev_dom, PhaseIterGVN* igvn); |
|
312 int is_range_check(Node* &range, Node* &index, jint &offset); |
|
313 static Node* up_one_dom(Node* curr, bool linear_only = false); |
|
314 |
|
315 #ifndef PRODUCT |
|
316 virtual void dump_spec(outputStream *st) const; |
|
317 #endif |
|
318 }; |
|
319 |
|
320 class IfTrueNode : public CProjNode { |
|
321 public: |
|
322 IfTrueNode( IfNode *ifnode ) : CProjNode(ifnode,1) { |
|
323 init_class_id(Class_IfTrue); |
|
324 } |
|
325 virtual int Opcode() const; |
|
326 virtual Node *Identity( PhaseTransform *phase ); |
|
327 }; |
|
328 |
|
329 class IfFalseNode : public CProjNode { |
|
330 public: |
|
331 IfFalseNode( IfNode *ifnode ) : CProjNode(ifnode,0) { |
|
332 init_class_id(Class_IfFalse); |
|
333 } |
|
334 virtual int Opcode() const; |
|
335 virtual Node *Identity( PhaseTransform *phase ); |
|
336 }; |
|
337 |
|
338 |
|
339 //------------------------------PCTableNode------------------------------------ |
|
340 // Build an indirect branch table. Given a control and a table index, |
|
341 // control is passed to the Projection matching the table index. Used to |
|
342 // implement switch statements and exception-handling capabilities. |
|
343 // Undefined behavior if passed-in index is not inside the table. |
|
344 class PCTableNode : public MultiBranchNode { |
|
345 virtual uint hash() const; // Target count; table size |
|
346 virtual uint cmp( const Node &n ) const; |
|
347 virtual uint size_of() const { return sizeof(*this); } |
|
348 |
|
349 public: |
|
350 const uint _size; // Number of targets |
|
351 |
|
352 PCTableNode( Node *ctrl, Node *idx, uint size ) : MultiBranchNode(2), _size(size) { |
|
353 init_class_id(Class_PCTable); |
|
354 init_req(0, ctrl); |
|
355 init_req(1, idx); |
|
356 } |
|
357 virtual int Opcode() const; |
|
358 virtual const Type *Value( PhaseTransform *phase ) const; |
|
359 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); |
|
360 virtual const Type *bottom_type() const; |
|
361 virtual bool pinned() const { return true; } |
|
362 }; |
|
363 |
|
364 //------------------------------JumpNode--------------------------------------- |
|
365 // Indirect branch. Uses PCTable above to implement a switch statement. |
|
366 // It emits as a table load and local branch. |
|
367 class JumpNode : public PCTableNode { |
|
368 public: |
|
369 JumpNode( Node* control, Node* switch_val, uint size) : PCTableNode(control, switch_val, size) { |
|
370 init_class_id(Class_Jump); |
|
371 } |
|
372 virtual int Opcode() const; |
|
373 virtual const RegMask& out_RegMask() const; |
|
374 virtual const Node* is_block_proj() const { return this; } |
|
375 }; |
|
376 |
|
377 class JumpProjNode : public JProjNode { |
|
378 virtual uint hash() const; |
|
379 virtual uint cmp( const Node &n ) const; |
|
380 virtual uint size_of() const { return sizeof(*this); } |
|
381 |
|
382 private: |
|
383 const int _dest_bci; |
|
384 const uint _proj_no; |
|
385 const int _switch_val; |
|
386 public: |
|
387 JumpProjNode(Node* jumpnode, uint proj_no, int dest_bci, int switch_val) |
|
388 : JProjNode(jumpnode, proj_no), _dest_bci(dest_bci), _proj_no(proj_no), _switch_val(switch_val) { |
|
389 init_class_id(Class_JumpProj); |
|
390 } |
|
391 |
|
392 virtual int Opcode() const; |
|
393 virtual const Type* bottom_type() const { return Type::CONTROL; } |
|
394 int dest_bci() const { return _dest_bci; } |
|
395 int switch_val() const { return _switch_val; } |
|
396 uint proj_no() const { return _proj_no; } |
|
397 #ifndef PRODUCT |
|
398 virtual void dump_spec(outputStream *st) const; |
|
399 #endif |
|
400 }; |
|
401 |
|
402 //------------------------------CatchNode-------------------------------------- |
|
403 // Helper node to fork exceptions. "Catch" catches any exceptions thrown by |
|
404 // a just-prior call. Looks like a PCTableNode but emits no code - just the |
|
405 // table. The table lookup and branch is implemented by RethrowNode. |
|
406 class CatchNode : public PCTableNode { |
|
407 public: |
|
408 CatchNode( Node *ctrl, Node *idx, uint size ) : PCTableNode(ctrl,idx,size){ |
|
409 init_class_id(Class_Catch); |
|
410 } |
|
411 virtual int Opcode() const; |
|
412 virtual const Type *Value( PhaseTransform *phase ) const; |
|
413 }; |
|
414 |
|
415 // CatchProjNode controls which exception handler is targetted after a call. |
|
416 // It is passed in the bci of the target handler, or no_handler_bci in case |
|
417 // the projection doesn't lead to an exception handler. |
|
418 class CatchProjNode : public CProjNode { |
|
419 virtual uint hash() const; |
|
420 virtual uint cmp( const Node &n ) const; |
|
421 virtual uint size_of() const { return sizeof(*this); } |
|
422 |
|
423 private: |
|
424 const int _handler_bci; |
|
425 |
|
426 public: |
|
427 enum { |
|
428 fall_through_index = 0, // the fall through projection index |
|
429 catch_all_index = 1, // the projection index for catch-alls |
|
430 no_handler_bci = -1 // the bci for fall through or catch-all projs |
|
431 }; |
|
432 |
|
433 CatchProjNode(Node* catchnode, uint proj_no, int handler_bci) |
|
434 : CProjNode(catchnode, proj_no), _handler_bci(handler_bci) { |
|
435 init_class_id(Class_CatchProj); |
|
436 assert(proj_no != fall_through_index || handler_bci < 0, "fall through case must have bci < 0"); |
|
437 } |
|
438 |
|
439 virtual int Opcode() const; |
|
440 virtual Node *Identity( PhaseTransform *phase ); |
|
441 virtual const Type *bottom_type() const { return Type::CONTROL; } |
|
442 int handler_bci() const { return _handler_bci; } |
|
443 bool is_handler_proj() const { return _handler_bci >= 0; } |
|
444 #ifndef PRODUCT |
|
445 virtual void dump_spec(outputStream *st) const; |
|
446 #endif |
|
447 }; |
|
448 |
|
449 |
|
450 //---------------------------------CreateExNode-------------------------------- |
|
451 // Helper node to create the exception coming back from a call |
|
452 class CreateExNode : public TypeNode { |
|
453 public: |
|
454 CreateExNode(const Type* t, Node* control, Node* i_o) : TypeNode(t, 2) { |
|
455 init_req(0, control); |
|
456 init_req(1, i_o); |
|
457 } |
|
458 virtual int Opcode() const; |
|
459 virtual Node *Identity( PhaseTransform *phase ); |
|
460 virtual bool pinned() const { return true; } |
|
461 uint match_edge(uint idx) const { return 0; } |
|
462 virtual uint ideal_reg() const { return Op_RegP; } |
|
463 }; |
|
464 |
|
465 //------------------------------NeverBranchNode------------------------------- |
|
466 // The never-taken branch. Used to give the appearance of exiting infinite |
|
467 // loops to those algorithms that like all paths to be reachable. Encodes |
|
468 // empty. |
|
469 class NeverBranchNode : public MultiBranchNode { |
|
470 public: |
|
471 NeverBranchNode( Node *ctrl ) : MultiBranchNode(1) { init_req(0,ctrl); } |
|
472 virtual int Opcode() const; |
|
473 virtual bool pinned() const { return true; }; |
|
474 virtual const Type *bottom_type() const { return TypeTuple::IFBOTH; } |
|
475 |
|
476 virtual void emit(CodeBuffer &cbuf, PhaseRegAlloc *ra_) const { } |
|
477 virtual uint size(PhaseRegAlloc *ra_) const { return 0; } |
|
478 #ifndef PRODUCT |
|
479 virtual void format( PhaseRegAlloc *, outputStream *st ) const; |
|
480 #endif |
|
481 }; |