1 /*
  2  * Copyright (c) 1999, 2019, 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 #ifndef SHARE_C1_C1_GRAPHBUILDER_HPP
 26 #define SHARE_C1_C1_GRAPHBUILDER_HPP
 27 
 28 #include "c1/c1_IR.hpp"
 29 #include "c1/c1_Instruction.hpp"
 30 #include "c1/c1_ValueMap.hpp"
 31 #include "c1/c1_ValueStack.hpp"
 32 #include "ci/ciMethodData.hpp"
 33 #include "ci/ciStreams.hpp"
 34 #include "compiler/compileLog.hpp"
 35 
 36 class MemoryBuffer;
 37 
 38 class DelayedFieldAccess : public CompilationResourceObj {
 39 private:
 40   Value            _obj;
 41   ciInstanceKlass* _holder;
 42   int              _offset;
 43 public:
 44   DelayedFieldAccess(Value obj, ciInstanceKlass* holder, int offset)
 45   : _obj(obj), _holder(holder) , _offset(offset) { }
 46 
 47   Value obj() const               { return _obj; }
 48   ciInstanceKlass* holder() const { return _holder; }
 49   int offset() const              { return _offset; }
 50   void inc_offset(int offset)     { _offset += offset; }
 51 };
 52 
 53 class GraphBuilder {
 54  private:
 55   // Per-scope data. These are pushed and popped as we descend into
 56   // inlined methods. Currently in order to generate good code in the
 57   // inliner we have to attempt to inline methods directly into the
 58   // basic block we are parsing; this adds complexity.
 59   class ScopeData: public CompilationResourceObj {
 60    private:
 61     ScopeData*  _parent;
 62     // bci-to-block mapping
 63     BlockList*   _bci2block;
 64     // Scope
 65     IRScope*     _scope;
 66     // Whether this scope or any parent scope has exception handlers
 67     bool         _has_handler;
 68     // The bytecodes
 69     ciBytecodeStream* _stream;
 70 
 71     // Work list
 72     BlockList*   _work_list;
 73 
 74     // Maximum inline size for this scope
 75     intx         _max_inline_size;
 76     // Expression stack depth at point where inline occurred
 77     int          _caller_stack_size;
 78 
 79     // The continuation point for the inline. Currently only used in
 80     // multi-block inlines, but eventually would like to use this for
 81     // all inlines for uniformity and simplicity; in this case would
 82     // get the continuation point from the BlockList instead of
 83     // fabricating it anew because Invokes would be considered to be
 84     // BlockEnds.
 85     BlockBegin*  _continuation;
 86 
 87     // Was this ScopeData created only for the parsing and inlining of
 88     // a jsr?
 89     bool         _parsing_jsr;
 90     // We track the destination bci of the jsr only to determine
 91     // bailout conditions, since we only handle a subset of all of the
 92     // possible jsr-ret control structures. Recursive invocations of a
 93     // jsr are disallowed by the verifier.
 94     int          _jsr_entry_bci;
 95     // We need to track the local variable in which the return address
 96     // was stored to ensure we can handle inlining the jsr, because we
 97     // don't handle arbitrary jsr/ret constructs.
 98     int          _jsr_ret_addr_local;
 99     // If we are parsing a jsr, the continuation point for rets
100     BlockBegin*  _jsr_continuation;
101     // Cloned XHandlers for jsr-related ScopeDatas
102     XHandlers*   _jsr_xhandlers;
103 
104     // Number of returns seen in this scope
105     int          _num_returns;
106 
107     // In order to generate profitable code for inlining, we currently
108     // have to perform an optimization for single-block inlined
109     // methods where we continue parsing into the same block. This
110     // allows us to perform CSE across inlined scopes and to avoid
111     // storing parameters to the stack. Having a global register
112     // allocator and being able to perform global CSE would allow this
113     // code to be removed and thereby simplify the inliner.
114     BlockBegin*  _cleanup_block;       // The block to which the return was added
115     Instruction* _cleanup_return_prev; // Instruction before return instruction
116     ValueStack*  _cleanup_state;       // State of that block (not yet pinned)
117 
118     // When inlining do not push the result on the stack
119     bool         _ignore_return;
120 
121    public:
122     ScopeData(ScopeData* parent);
123 
124     ScopeData* parent() const                      { return _parent;            }
125 
126     BlockList* bci2block() const                   { return _bci2block;         }
127     void       set_bci2block(BlockList* bci2block) { _bci2block = bci2block;    }
128 
129     // NOTE: this has a different effect when parsing jsrs
130     BlockBegin* block_at(int bci);
131 
132     IRScope* scope() const                         { return _scope;             }
133     // Has side-effect of setting has_handler flag
134     void set_scope(IRScope* scope);
135 
136     // Whether this or any parent scope has exception handlers
137     bool has_handler() const                       { return _has_handler;       }
138     void set_has_handler()                         { _has_handler = true;       }
139 
140     // Exception handlers list to be used for this scope
141     XHandlers* xhandlers() const;
142 
143     // How to get a block to be parsed
144     void add_to_work_list(BlockBegin* block);
145     // How to remove the next block to be parsed; returns NULL if none left
146     BlockBegin* remove_from_work_list();
147     // Indicates parse is over
148     bool is_work_list_empty() const;
149 
150     ciBytecodeStream* stream()                     { return _stream;            }
151     void set_stream(ciBytecodeStream* stream)      { _stream = stream;          }
152 
153     intx max_inline_size() const                   { return _max_inline_size;   }
154 
155     BlockBegin* continuation() const               { return _continuation;      }
156     void set_continuation(BlockBegin* cont)        { _continuation = cont;      }
157 
158     // Indicates whether this ScopeData was pushed only for the
159     // parsing and inlining of a jsr
160     bool parsing_jsr() const                       { return _parsing_jsr;       }
161     void set_parsing_jsr()                         { _parsing_jsr = true;       }
162     int  jsr_entry_bci() const                     { return _jsr_entry_bci;     }
163     void set_jsr_entry_bci(int bci)                { _jsr_entry_bci = bci;      }
164     void set_jsr_return_address_local(int local_no){ _jsr_ret_addr_local = local_no; }
165     int  jsr_return_address_local() const          { return _jsr_ret_addr_local; }
166     // Must be called after scope is set up for jsr ScopeData
167     void setup_jsr_xhandlers();
168 
169     // The jsr continuation is only used when parsing_jsr is true, and
170     // is different from the "normal" continuation since we can end up
171     // doing a return (rather than a ret) from within a subroutine
172     BlockBegin* jsr_continuation() const           { return _jsr_continuation;  }
173     void set_jsr_continuation(BlockBegin* cont)    { _jsr_continuation = cont;  }
174 
175     int num_returns();
176     void incr_num_returns();
177 
178     void set_inline_cleanup_info(BlockBegin* block,
179                                  Instruction* return_prev,
180                                  ValueStack* return_state);
181     BlockBegin*  inline_cleanup_block() const      { return _cleanup_block; }
182     Instruction* inline_cleanup_return_prev() const{ return _cleanup_return_prev; }
183     ValueStack*  inline_cleanup_state() const      { return _cleanup_state; }
184 
185     bool ignore_return() const                     { return _ignore_return;          }
186     void set_ignore_return(bool ignore_return)     { _ignore_return = ignore_return; }
187   };
188 
189   // for all GraphBuilders
190   static bool       _can_trap[Bytecodes::number_of_java_codes];
191 
192   // for each instance of GraphBuilder
193   ScopeData*        _scope_data;                 // Per-scope data; used for inlining
194   Compilation*      _compilation;                // the current compilation
195   ValueMap*         _vmap;                       // the map of values encountered (for CSE)
196   MemoryBuffer*     _memory;
197   const char*       _inline_bailout_msg;         // non-null if most recent inline attempt failed
198   int               _instruction_count;          // for bailing out in pathological jsr/ret cases
199   BlockBegin*       _start;                      // the start block
200   BlockBegin*       _osr_entry;                  // the osr entry block block
201   ValueStack*       _initial_state;              // The state for the start block
202 
203   // for each call to connect_to_end; can also be set by inliner
204   BlockBegin*       _block;                      // the current block
205   ValueStack*       _state;                      // the current execution state
206   Instruction*      _last;                       // the last instruction added
207   bool              _skip_block;                 // skip processing of the rest of this block
208 
209   // support for optimization of accesses to flattened fields and arrays
210   DelayedFieldAccess* _pending_field_access;
211   DelayedLoadIndexed* _pending_load_indexed;
212 
213   // accessors
214   ScopeData*        scope_data() const           { return _scope_data; }
215   Compilation*      compilation() const          { return _compilation; }
216   BlockList*        bci2block() const            { return scope_data()->bci2block(); }
217   ValueMap*         vmap() const                 { assert(UseLocalValueNumbering, "should not access otherwise"); return _vmap; }
218   bool              has_handler() const          { return scope_data()->has_handler(); }
219 
220   BlockBegin*       block() const                { return _block; }
221   ValueStack*       state() const                { return _state; }
222   void              set_state(ValueStack* state) { _state = state; }
223   IRScope*          scope() const                { return scope_data()->scope(); }
224   ciMethod*         method() const               { return scope()->method(); }
225   ciBytecodeStream* stream() const               { return scope_data()->stream(); }
226   Instruction*      last() const                 { return _last; }
227   Bytecodes::Code   code() const                 { return stream()->cur_bc(); }
228   int               bci() const                  { return stream()->cur_bci(); }
229   int               next_bci() const             { return stream()->next_bci(); }
230   bool              has_pending_field_access()   { return _pending_field_access != NULL; }
231   DelayedFieldAccess* pending_field_access()     { return _pending_field_access; }
232   void              set_pending_field_access(DelayedFieldAccess* delayed) { _pending_field_access = delayed; }
233   bool              has_pending_load_indexed()   { return _pending_load_indexed != NULL; }
234   DelayedLoadIndexed* pending_load_indexed()     { return _pending_load_indexed; }
235   void              set_pending_load_indexed(DelayedLoadIndexed* delayed) { _pending_load_indexed = delayed; }
236 
237   // unified bailout support
238   void bailout(const char* msg) const            { compilation()->bailout(msg); }
239   bool bailed_out() const                        { return compilation()->bailed_out(); }
240 
241   // stack manipulation helpers
242   void ipush(Value t) const                      { state()->ipush(t); }
243   void lpush(Value t) const                      { state()->lpush(t); }
244   void fpush(Value t) const                      { state()->fpush(t); }
245   void dpush(Value t) const                      { state()->dpush(t); }
246   void apush(Value t) const                      { state()->apush(t); }
247   void  push(ValueType* type, Value t) const     { state()-> push(type, t); }
248 
249   Value ipop()                                   { return state()->ipop(); }
250   Value lpop()                                   { return state()->lpop(); }
251   Value fpop()                                   { return state()->fpop(); }
252   Value dpop()                                   { return state()->dpop(); }
253   Value apop()                                   { return state()->apop(); }
254   Value  pop(ValueType* type)                    { return state()-> pop(type); }
255 
256   // instruction helpers
257   void load_constant();
258   void load_local(ValueType* type, int index);
259   void store_local(ValueType* type, int index);
260   void store_local(ValueStack* state, Value value, int index);
261   void load_indexed (BasicType type);
262   void store_indexed(BasicType type);
263   void stack_op(Bytecodes::Code code);
264   void arithmetic_op(ValueType* type, Bytecodes::Code code, ValueStack* state_before = NULL);
265   void negate_op(ValueType* type);
266   void shift_op(ValueType* type, Bytecodes::Code code);
267   void logic_op(ValueType* type, Bytecodes::Code code);
268   void compare_op(ValueType* type, Bytecodes::Code code);
269   void convert(Bytecodes::Code op, BasicType from, BasicType to);
270   void increment();
271   void _goto(int from_bci, int to_bci);
272   void if_node(Value x, If::Condition cond, Value y, ValueStack* stack_before);
273   void if_zero(ValueType* type, If::Condition cond);
274   void if_null(ValueType* type, If::Condition cond);
275   void if_same(ValueType* type, If::Condition cond);
276   void jsr(int dest);
277   void ret(int local_index);
278   void table_switch();
279   void lookup_switch();
280   void method_return(Value x, bool ignore_return = false);
281   void call_register_finalizer();
282   void access_field(Bytecodes::Code code);
283   void invoke(Bytecodes::Code code);
284   void new_instance(int klass_index);
285   void new_type_array();
286   void new_object_array();
287   void check_cast(int klass_index);
288   void instance_of(int klass_index);
289   void monitorenter(Value x, int bci);
290   void monitorexit(Value x, int bci);
291   void new_multi_array(int dimensions);
292   void throw_op(int bci);
293   Value round_fp(Value fp_value);
294 
295   // inline types
296   void default_value(int klass_index);
297   void withfield(int field_index);
298   void copy_inline_content(ciInlineKlass* vk, Value src, int src_off, Value dest, int dest_off, ValueStack* state_before, ciField* encloding_field = NULL);
299 
300   // stack/code manipulation helpers
301   Instruction* append_with_bci(Instruction* instr, int bci);
302   Instruction* append(Instruction* instr);
303   Instruction* append_split(StateSplit* instr);
304 
305   // other helpers
306   BlockBegin* block_at(int bci)                  { return scope_data()->block_at(bci); }
307   XHandlers* handle_exception(Instruction* instruction);
308   void connect_to_end(BlockBegin* beg);
309   void null_check(Value value);
310   void eliminate_redundant_phis(BlockBegin* start);
311   BlockEnd* iterate_bytecodes_for_block(int bci);
312   void iterate_all_blocks(bool start_in_current_block_for_inlining = false);
313   Dependencies* dependency_recorder() const; // = compilation()->dependencies()
314   bool direct_compare(ciKlass* k);
315   Value make_constant(ciConstant value, ciField* field);
316 
317   void kill_all();
318 
319   // use of state copy routines (try to minimize unnecessary state
320   // object allocations):
321 
322   // - if the instruction unconditionally needs a full copy of the
323   // state (for patching for example), then use copy_state_before*
324 
325   // - if the instruction needs a full copy of the state only for
326   // handler generation (Instruction::needs_exception_state() returns
327   // false) then use copy_state_exhandling*
328 
329   // - if the instruction needs either a full copy of the state for
330   // handler generation and a least a minimal copy of the state (as
331   // returned by Instruction::exception_state()) for debug info
332   // generation (that is when Instruction::needs_exception_state()
333   // returns true) then use copy_state_for_exception*
334 
335   ValueStack* copy_state_before_with_bci(int bci);
336   ValueStack* copy_state_before();
337   ValueStack* copy_state_exhandling_with_bci(int bci);
338   ValueStack* copy_state_exhandling();
339   ValueStack* copy_state_for_exception_with_bci(int bci);
340   ValueStack* copy_state_for_exception();
341   ValueStack* copy_state_if_bb(bool is_bb) { return (is_bb || compilation()->is_optimistic()) ? copy_state_before() : NULL; }
342   ValueStack* copy_state_indexed_access() { return compilation()->is_optimistic() ? copy_state_before() : copy_state_for_exception(); }
343 
344   //
345   // Inlining support
346   //
347 
348   // accessors
349   bool parsing_jsr() const                               { return scope_data()->parsing_jsr();           }
350   BlockBegin* continuation() const                       { return scope_data()->continuation();          }
351   BlockBegin* jsr_continuation() const                   { return scope_data()->jsr_continuation();      }
352   void set_continuation(BlockBegin* continuation)        { scope_data()->set_continuation(continuation); }
353   void set_inline_cleanup_info(BlockBegin* block,
354                                Instruction* return_prev,
355                                ValueStack* return_state) { scope_data()->set_inline_cleanup_info(block,
356                                                                                                   return_prev,
357                                                                                                   return_state); }
358   void set_inline_cleanup_info() {
359     set_inline_cleanup_info(_block, _last, _state);
360   }
361   BlockBegin*  inline_cleanup_block() const              { return scope_data()->inline_cleanup_block();  }
362   Instruction* inline_cleanup_return_prev() const        { return scope_data()->inline_cleanup_return_prev(); }
363   ValueStack*  inline_cleanup_state() const              { return scope_data()->inline_cleanup_state();  }
364   void restore_inline_cleanup_info() {
365     _block = inline_cleanup_block();
366     _last  = inline_cleanup_return_prev();
367     _state = inline_cleanup_state();
368   }
369   void incr_num_returns()                                { scope_data()->incr_num_returns();             }
370   int  num_returns() const                               { return scope_data()->num_returns();           }
371   intx max_inline_size() const                           { return scope_data()->max_inline_size();       }
372   int  inline_level() const                              { return scope()->level();                      }
373   int  recursive_inline_level(ciMethod* callee) const;
374 
375   // inlining of synchronized methods
376   void inline_sync_entry(Value lock, BlockBegin* sync_handler);
377   void fill_sync_handler(Value lock, BlockBegin* sync_handler, bool default_handler = false);
378 
379   void build_graph_for_intrinsic(ciMethod* callee, bool ignore_return);
380 
381   // inliners
382   bool try_inline(           ciMethod* callee, bool holder_known, bool ignore_return, Bytecodes::Code bc = Bytecodes::_illegal, Value receiver = NULL);
383   bool try_inline_intrinsics(ciMethod* callee, bool ignore_return = false);
384   bool try_inline_full(      ciMethod* callee, bool holder_known, bool ignore_return, Bytecodes::Code bc = Bytecodes::_illegal, Value receiver = NULL);
385   bool try_inline_jsr(int jsr_dest_bci);
386 
387   const char* check_can_parse(ciMethod* callee) const;
388   const char* should_not_inline(ciMethod* callee) const;
389 
390   // JSR 292 support
391   bool try_method_handle_inline(ciMethod* callee, bool ignore_return);
392 
393   // Inline type support
394   void update_larval_state(Value v) {
395     if (v != NULL && v->as_NewInlineTypeInstance() != NULL) {
396       v->as_NewInlineTypeInstance()->set_not_larva_anymore();
397     }
398   }
399   void update_larva_stack_count(Value v) {
400     if (v != NULL && v->as_NewInlineTypeInstance() != NULL &&
401         v->as_NewInlineTypeInstance()->in_larval_state()) {
402       v->as_NewInlineTypeInstance()->decrement_on_stack_count();
403     }
404   }
405 
406   // helpers
407   void inline_bailout(const char* msg);
408   BlockBegin* header_block(BlockBegin* entry, BlockBegin::Flag f, ValueStack* state);
409   BlockBegin* setup_start_block(int osr_bci, BlockBegin* std_entry, BlockBegin* osr_entry, ValueStack* init_state);
410   void setup_osr_entry_block();
411   void clear_inline_bailout();
412   ValueStack* state_at_entry();
413   void push_root_scope(IRScope* scope, BlockList* bci2block, BlockBegin* start);
414   void push_scope(ciMethod* callee, BlockBegin* continuation);
415   void push_scope_for_jsr(BlockBegin* jsr_continuation, int jsr_dest_bci);
416   void pop_scope();
417   void pop_scope_for_jsr();
418 
419   void append_unsafe_get(ciMethod* callee, BasicType t, bool is_volatile);
420   void append_unsafe_put(ciMethod* callee, BasicType t, bool is_volatile);
421   void append_unsafe_CAS(ciMethod* callee);
422   void append_unsafe_get_and_set(ciMethod* callee, bool is_add);
423   void append_char_access(ciMethod* callee, bool is_store);
424 
425   void print_inlining(ciMethod* callee, const char* msg, bool success = true);
426 
427   void profile_call(ciMethod* callee, Value recv, ciKlass* predicted_holder, Values* obj_args, bool inlined);
428   void profile_return_type(Value ret, ciMethod* callee, ciMethod* m = NULL, int bci = -1);
429   void profile_invocation(ciMethod* inlinee, ValueStack* state);
430 
431   // Shortcuts to profiling control.
432   bool is_profiling()          { return _compilation->is_profiling();          }
433   bool profile_branches()      { return _compilation->profile_branches();      }
434   bool profile_calls()         { return _compilation->profile_calls();         }
435   bool profile_inlined_calls() { return _compilation->profile_inlined_calls(); }
436   bool profile_checkcasts()    { return _compilation->profile_checkcasts();    }
437   bool profile_parameters()    { return _compilation->profile_parameters();    }
438   bool profile_arguments()     { return _compilation->profile_arguments();     }
439   bool profile_return()        { return _compilation->profile_return();        }
440   bool profile_array_accesses(){ return _compilation->profile_array_accesses();}
441 
442   Values* args_list_for_profiling(ciMethod* target, int& start, bool may_have_receiver);
443   Values* collect_args_for_profiling(Values* args, ciMethod* target, bool may_have_receiver);
444   void check_args_for_profiling(Values* obj_args, int expected);
445 
446  public:
447   NOT_PRODUCT(void print_stats();)
448 
449   // initialization
450   static void initialize();
451 
452   // public
453   static bool can_trap(ciMethod* method, Bytecodes::Code code) {
454     assert(0 <= code && code < Bytecodes::number_of_java_codes, "illegal bytecode");
455     if (_can_trap[code]) return true;
456     // special handling for finalizer registration
457     return code == Bytecodes::_return && method->intrinsic_id() == vmIntrinsics::_Object_init;
458   }
459 
460   // creation
461   GraphBuilder(Compilation* compilation, IRScope* scope);
462   static void sort_top_into_worklist(BlockList* worklist, BlockBegin* top);
463 
464   BlockBegin* start() const                      { return _start; }
465 };
466 
467 #endif // SHARE_C1_C1_GRAPHBUILDER_HPP