aoqi@0: /* aoqi@0: * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved. aoqi@0: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. aoqi@0: * aoqi@0: * This code is free software; you can redistribute it and/or modify it aoqi@0: * under the terms of the GNU General Public License version 2 only, as aoqi@0: * published by the Free Software Foundation. aoqi@0: * aoqi@0: * This code is distributed in the hope that it will be useful, but WITHOUT aoqi@0: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or aoqi@0: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License aoqi@0: * version 2 for more details (a copy is included in the LICENSE file that aoqi@0: * accompanied this code). aoqi@0: * aoqi@0: * You should have received a copy of the GNU General Public License version aoqi@0: * 2 along with this work; if not, write to the Free Software Foundation, aoqi@0: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. aoqi@0: * aoqi@0: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA aoqi@0: * or visit www.oracle.com if you need additional information or have any aoqi@0: * questions. aoqi@0: * aoqi@0: */ aoqi@0: aoqi@0: #ifndef SHARE_VM_C1_C1_VALUEMAP_HPP aoqi@0: #define SHARE_VM_C1_C1_VALUEMAP_HPP aoqi@0: aoqi@0: #include "c1/c1_Instruction.hpp" aoqi@0: #include "c1/c1_ValueSet.hpp" aoqi@0: #include "memory/allocation.hpp" aoqi@0: aoqi@0: class ValueMapEntry: public CompilationResourceObj { aoqi@0: private: aoqi@0: intx _hash; aoqi@0: Value _value; aoqi@0: int _nesting; aoqi@0: ValueMapEntry* _next; aoqi@0: aoqi@0: public: aoqi@0: ValueMapEntry(intx hash, Value value, int nesting, ValueMapEntry* next) aoqi@0: : _hash(hash) aoqi@0: , _value(value) aoqi@0: , _nesting(nesting) aoqi@0: , _next(next) aoqi@0: { aoqi@0: } aoqi@0: aoqi@0: intx hash() { return _hash; } aoqi@0: Value value() { return _value; } aoqi@0: int nesting() { return _nesting; } aoqi@0: ValueMapEntry* next() { return _next; } aoqi@0: aoqi@0: void set_next(ValueMapEntry* next) { _next = next; } aoqi@0: }; aoqi@0: aoqi@0: define_array(ValueMapEntryArray, ValueMapEntry*) aoqi@0: define_stack(ValueMapEntryList, ValueMapEntryArray) aoqi@0: aoqi@0: // ValueMap implements nested hash tables for value numbering. It aoqi@0: // maintains a set _killed_values which represents the instructions aoqi@0: // which have been killed so far and an array of linked lists of aoqi@0: // ValueMapEntries names _entries. Each ValueMapEntry has a nesting aoqi@0: // which indicates what ValueMap nesting it belongs to. Higher aoqi@0: // nesting values are always before lower values in the linked list. aoqi@0: // This allows cloning of parent ValueMaps by simply copying the heads aoqi@0: // of the list. _entry_count represents the number of reachable aoqi@0: // entries in the ValueMap. A ValueMap is only allowed to mutate aoqi@0: // ValueMapEntries with the same nesting level. Adding or removing aoqi@0: // entries at the current nesting level requires updating aoqi@0: // _entry_count. Elements in the parent's list that get killed can be aoqi@0: // skipped if they are at the head of the list by simply moving to the aoqi@0: // next element in the list and decrementing _entry_count. aoqi@0: aoqi@0: class ValueMap: public CompilationResourceObj { aoqi@0: private: aoqi@0: int _nesting; aoqi@0: ValueMapEntryArray _entries; aoqi@0: ValueSet _killed_values; aoqi@0: int _entry_count; aoqi@0: aoqi@0: int nesting() { return _nesting; } aoqi@0: bool is_local_value_numbering() { return _nesting == 0; } aoqi@0: bool is_global_value_numbering() { return _nesting > 0; } aoqi@0: aoqi@0: int entry_count() { return _entry_count; } aoqi@0: int size() { return _entries.length(); } aoqi@0: ValueMapEntry* entry_at(int i) { return _entries.at(i); } aoqi@0: aoqi@0: // calculates the index of a hash value in a hash table of size n aoqi@0: int entry_index(intx hash, int n) { return (unsigned int)hash % n; } aoqi@0: aoqi@0: // if entry_count > size_threshold, the size of the hash table is increased aoqi@0: int size_threshold() { return size(); } aoqi@0: aoqi@0: // management of the killed-bitset for global value numbering aoqi@0: void kill_value(Value v) { if (is_global_value_numbering()) _killed_values.put(v); } aoqi@0: bool is_killed(Value v) { if (is_global_value_numbering()) return _killed_values.contains(v); else return false; } aoqi@0: aoqi@0: // helper functions aoqi@0: void increase_table_size(); aoqi@0: aoqi@0: #ifndef PRODUCT aoqi@0: static int _number_of_finds; aoqi@0: static int _number_of_hits; aoqi@0: static int _number_of_kills; aoqi@0: #endif // PRODUCT aoqi@0: aoqi@0: public: aoqi@0: // creation aoqi@0: ValueMap(); // empty value map aoqi@0: ValueMap(ValueMap* old); // value map with increased nesting aoqi@0: aoqi@0: // manipulation aoqi@0: Value find_insert(Value x); aoqi@0: aoqi@0: void kill_memory(); aoqi@0: void kill_field(ciField* field, bool all_offsets); aoqi@0: void kill_array(ValueType* type); aoqi@0: void kill_exception(); aoqi@0: void kill_map(ValueMap* map); aoqi@0: void kill_all(); aoqi@0: aoqi@0: #ifndef PRODUCT aoqi@0: // debugging/printing aoqi@0: void print(); aoqi@0: aoqi@0: static void reset_statistics(); aoqi@0: static void print_statistics(); aoqi@0: #endif aoqi@0: }; aoqi@0: aoqi@0: define_array(ValueMapArray, ValueMap*) aoqi@0: aoqi@0: aoqi@0: class ValueNumberingVisitor: public InstructionVisitor { aoqi@0: protected: aoqi@0: // called by visitor functions for instructions that kill values aoqi@0: virtual void kill_memory() = 0; aoqi@0: virtual void kill_field(ciField* field, bool all_offsets) = 0; aoqi@0: virtual void kill_array(ValueType* type) = 0; aoqi@0: aoqi@0: // visitor functions aoqi@0: void do_StoreField (StoreField* x) { aoqi@0: if (x->is_init_point() || // putstatic is an initialization point so treat it as a wide kill aoqi@0: // This is actually too strict and the JMM doesn't require aoqi@0: // this in all cases (e.g. load a; volatile store b; load a) aoqi@0: // but possible future optimizations might require this. aoqi@0: x->field()->is_volatile()) { aoqi@0: kill_memory(); aoqi@0: } else { aoqi@0: kill_field(x->field(), x->needs_patching()); aoqi@0: } aoqi@0: } aoqi@0: void do_StoreIndexed (StoreIndexed* x) { kill_array(x->type()); } aoqi@0: void do_MonitorEnter (MonitorEnter* x) { kill_memory(); } aoqi@0: void do_MonitorExit (MonitorExit* x) { kill_memory(); } aoqi@0: void do_Invoke (Invoke* x) { kill_memory(); } aoqi@0: void do_UnsafePutRaw (UnsafePutRaw* x) { kill_memory(); } aoqi@0: void do_UnsafePutObject(UnsafePutObject* x) { kill_memory(); } aoqi@0: void do_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x) { kill_memory(); } aoqi@0: void do_Intrinsic (Intrinsic* x) { if (!x->preserves_state()) kill_memory(); } aoqi@0: aoqi@0: void do_Phi (Phi* x) { /* nothing to do */ } aoqi@0: void do_Local (Local* x) { /* nothing to do */ } aoqi@0: void do_Constant (Constant* x) { /* nothing to do */ } aoqi@0: void do_LoadField (LoadField* x) { aoqi@0: if (x->is_init_point() || // getstatic is an initialization point so treat it as a wide kill aoqi@0: x->field()->is_volatile()) { // the JMM requires this aoqi@0: kill_memory(); aoqi@0: } aoqi@0: } aoqi@0: void do_ArrayLength (ArrayLength* x) { /* nothing to do */ } aoqi@0: void do_LoadIndexed (LoadIndexed* x) { /* nothing to do */ } aoqi@0: void do_NegateOp (NegateOp* x) { /* nothing to do */ } aoqi@0: void do_ArithmeticOp (ArithmeticOp* x) { /* nothing to do */ } aoqi@0: void do_ShiftOp (ShiftOp* x) { /* nothing to do */ } aoqi@0: void do_LogicOp (LogicOp* x) { /* nothing to do */ } aoqi@0: void do_CompareOp (CompareOp* x) { /* nothing to do */ } aoqi@0: void do_IfOp (IfOp* x) { /* nothing to do */ } aoqi@0: void do_Convert (Convert* x) { /* nothing to do */ } aoqi@0: void do_NullCheck (NullCheck* x) { /* nothing to do */ } aoqi@0: void do_TypeCast (TypeCast* x) { /* nothing to do */ } aoqi@0: void do_NewInstance (NewInstance* x) { /* nothing to do */ } aoqi@0: void do_NewTypeArray (NewTypeArray* x) { /* nothing to do */ } aoqi@0: void do_NewObjectArray (NewObjectArray* x) { /* nothing to do */ } aoqi@0: void do_NewMultiArray (NewMultiArray* x) { /* nothing to do */ } aoqi@0: void do_CheckCast (CheckCast* x) { /* nothing to do */ } aoqi@0: void do_InstanceOf (InstanceOf* x) { /* nothing to do */ } aoqi@0: void do_BlockBegin (BlockBegin* x) { /* nothing to do */ } aoqi@0: void do_Goto (Goto* x) { /* nothing to do */ } aoqi@0: void do_If (If* x) { /* nothing to do */ } aoqi@0: void do_IfInstanceOf (IfInstanceOf* x) { /* nothing to do */ } aoqi@0: void do_TableSwitch (TableSwitch* x) { /* nothing to do */ } aoqi@0: void do_LookupSwitch (LookupSwitch* x) { /* nothing to do */ } aoqi@0: void do_Return (Return* x) { /* nothing to do */ } aoqi@0: void do_Throw (Throw* x) { /* nothing to do */ } aoqi@0: void do_Base (Base* x) { /* nothing to do */ } aoqi@0: void do_OsrEntry (OsrEntry* x) { /* nothing to do */ } aoqi@0: void do_ExceptionObject(ExceptionObject* x) { /* nothing to do */ } aoqi@0: void do_RoundFP (RoundFP* x) { /* nothing to do */ } aoqi@0: void do_UnsafeGetRaw (UnsafeGetRaw* x) { /* nothing to do */ } aoqi@0: void do_UnsafeGetObject(UnsafeGetObject* x) { /* nothing to do */ } aoqi@0: void do_UnsafePrefetchRead (UnsafePrefetchRead* x) { /* nothing to do */ } aoqi@0: void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) { /* nothing to do */ } aoqi@0: void do_ProfileCall (ProfileCall* x) { /* nothing to do */ } aoqi@0: void do_ProfileReturnType (ProfileReturnType* x) { /* nothing to do */ } aoqi@0: void do_ProfileInvoke (ProfileInvoke* x) { /* nothing to do */ }; aoqi@0: void do_RuntimeCall (RuntimeCall* x) { /* nothing to do */ }; aoqi@0: void do_MemBar (MemBar* x) { /* nothing to do */ }; aoqi@0: void do_RangeCheckPredicate(RangeCheckPredicate* x) { /* nothing to do */ }; aoqi@0: #ifdef ASSERT aoqi@0: void do_Assert (Assert* x) { /* nothing to do */ }; aoqi@0: #endif aoqi@0: }; aoqi@0: aoqi@0: aoqi@0: class ValueNumberingEffects: public ValueNumberingVisitor { aoqi@0: private: aoqi@0: ValueMap* _map; aoqi@0: aoqi@0: public: aoqi@0: // implementation for abstract methods of ValueNumberingVisitor aoqi@0: void kill_memory() { _map->kill_memory(); } aoqi@0: void kill_field(ciField* field, bool all_offsets) { _map->kill_field(field, all_offsets); } aoqi@0: void kill_array(ValueType* type) { _map->kill_array(type); } aoqi@0: aoqi@0: ValueNumberingEffects(ValueMap* map): _map(map) {} aoqi@0: }; aoqi@0: aoqi@0: aoqi@0: class GlobalValueNumbering: public ValueNumberingVisitor { aoqi@0: private: aoqi@0: Compilation* _compilation; // compilation data aoqi@0: ValueMap* _current_map; // value map of current block aoqi@0: ValueMapArray _value_maps; // list of value maps for all blocks aoqi@0: ValueSet _processed_values; // marker for instructions that were already processed aoqi@0: bool _has_substitutions; // set to true when substitutions must be resolved aoqi@0: aoqi@0: public: aoqi@0: // accessors aoqi@0: Compilation* compilation() const { return _compilation; } aoqi@0: ValueMap* current_map() { return _current_map; } aoqi@0: ValueMap* value_map_of(BlockBegin* block) { return _value_maps.at(block->linear_scan_number()); } aoqi@0: void set_value_map_of(BlockBegin* block, ValueMap* map) { assert(value_map_of(block) == NULL, ""); _value_maps.at_put(block->linear_scan_number(), map); } aoqi@0: aoqi@0: bool is_processed(Value v) { return _processed_values.contains(v); } aoqi@0: void set_processed(Value v) { _processed_values.put(v); } aoqi@0: aoqi@0: // implementation for abstract methods of ValueNumberingVisitor aoqi@0: void kill_memory() { current_map()->kill_memory(); } aoqi@0: void kill_field(ciField* field, bool all_offsets) { current_map()->kill_field(field, all_offsets); } aoqi@0: void kill_array(ValueType* type) { current_map()->kill_array(type); } aoqi@0: aoqi@0: // main entry point that performs global value numbering aoqi@0: GlobalValueNumbering(IR* ir); aoqi@0: void substitute(Instruction* instr); // substitute instruction if it is contained in current value map aoqi@0: }; aoqi@0: aoqi@0: #endif // SHARE_VM_C1_C1_VALUEMAP_HPP