1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/c1/c1_ValueMap.hpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,259 @@
1.4 +/*
1.5 + * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#ifndef SHARE_VM_C1_C1_VALUEMAP_HPP
1.29 +#define SHARE_VM_C1_C1_VALUEMAP_HPP
1.30 +
1.31 +#include "c1/c1_Instruction.hpp"
1.32 +#include "c1/c1_ValueSet.hpp"
1.33 +#include "memory/allocation.hpp"
1.34 +
1.35 +class ValueMapEntry: public CompilationResourceObj {
1.36 + private:
1.37 + intx _hash;
1.38 + Value _value;
1.39 + int _nesting;
1.40 + ValueMapEntry* _next;
1.41 +
1.42 + public:
1.43 + ValueMapEntry(intx hash, Value value, int nesting, ValueMapEntry* next)
1.44 + : _hash(hash)
1.45 + , _value(value)
1.46 + , _nesting(nesting)
1.47 + , _next(next)
1.48 + {
1.49 + }
1.50 +
1.51 + intx hash() { return _hash; }
1.52 + Value value() { return _value; }
1.53 + int nesting() { return _nesting; }
1.54 + ValueMapEntry* next() { return _next; }
1.55 +
1.56 + void set_next(ValueMapEntry* next) { _next = next; }
1.57 +};
1.58 +
1.59 +define_array(ValueMapEntryArray, ValueMapEntry*)
1.60 +define_stack(ValueMapEntryList, ValueMapEntryArray)
1.61 +
1.62 +// ValueMap implements nested hash tables for value numbering. It
1.63 +// maintains a set _killed_values which represents the instructions
1.64 +// which have been killed so far and an array of linked lists of
1.65 +// ValueMapEntries names _entries. Each ValueMapEntry has a nesting
1.66 +// which indicates what ValueMap nesting it belongs to. Higher
1.67 +// nesting values are always before lower values in the linked list.
1.68 +// This allows cloning of parent ValueMaps by simply copying the heads
1.69 +// of the list. _entry_count represents the number of reachable
1.70 +// entries in the ValueMap. A ValueMap is only allowed to mutate
1.71 +// ValueMapEntries with the same nesting level. Adding or removing
1.72 +// entries at the current nesting level requires updating
1.73 +// _entry_count. Elements in the parent's list that get killed can be
1.74 +// skipped if they are at the head of the list by simply moving to the
1.75 +// next element in the list and decrementing _entry_count.
1.76 +
1.77 +class ValueMap: public CompilationResourceObj {
1.78 + private:
1.79 + int _nesting;
1.80 + ValueMapEntryArray _entries;
1.81 + ValueSet _killed_values;
1.82 + int _entry_count;
1.83 +
1.84 + int nesting() { return _nesting; }
1.85 + bool is_local_value_numbering() { return _nesting == 0; }
1.86 + bool is_global_value_numbering() { return _nesting > 0; }
1.87 +
1.88 + int entry_count() { return _entry_count; }
1.89 + int size() { return _entries.length(); }
1.90 + ValueMapEntry* entry_at(int i) { return _entries.at(i); }
1.91 +
1.92 + // calculates the index of a hash value in a hash table of size n
1.93 + int entry_index(intx hash, int n) { return (unsigned int)hash % n; }
1.94 +
1.95 + // if entry_count > size_threshold, the size of the hash table is increased
1.96 + int size_threshold() { return size(); }
1.97 +
1.98 + // management of the killed-bitset for global value numbering
1.99 + void kill_value(Value v) { if (is_global_value_numbering()) _killed_values.put(v); }
1.100 + bool is_killed(Value v) { if (is_global_value_numbering()) return _killed_values.contains(v); else return false; }
1.101 +
1.102 + // helper functions
1.103 + void increase_table_size();
1.104 +
1.105 +#ifndef PRODUCT
1.106 + static int _number_of_finds;
1.107 + static int _number_of_hits;
1.108 + static int _number_of_kills;
1.109 +#endif // PRODUCT
1.110 +
1.111 + public:
1.112 + // creation
1.113 + ValueMap(); // empty value map
1.114 + ValueMap(ValueMap* old); // value map with increased nesting
1.115 +
1.116 + // manipulation
1.117 + Value find_insert(Value x);
1.118 +
1.119 + void kill_memory();
1.120 + void kill_field(ciField* field, bool all_offsets);
1.121 + void kill_array(ValueType* type);
1.122 + void kill_exception();
1.123 + void kill_map(ValueMap* map);
1.124 + void kill_all();
1.125 +
1.126 +#ifndef PRODUCT
1.127 + // debugging/printing
1.128 + void print();
1.129 +
1.130 + static void reset_statistics();
1.131 + static void print_statistics();
1.132 +#endif
1.133 +};
1.134 +
1.135 +define_array(ValueMapArray, ValueMap*)
1.136 +
1.137 +
1.138 +class ValueNumberingVisitor: public InstructionVisitor {
1.139 + protected:
1.140 + // called by visitor functions for instructions that kill values
1.141 + virtual void kill_memory() = 0;
1.142 + virtual void kill_field(ciField* field, bool all_offsets) = 0;
1.143 + virtual void kill_array(ValueType* type) = 0;
1.144 +
1.145 + // visitor functions
1.146 + void do_StoreField (StoreField* x) {
1.147 + if (x->is_init_point() || // putstatic is an initialization point so treat it as a wide kill
1.148 + // This is actually too strict and the JMM doesn't require
1.149 + // this in all cases (e.g. load a; volatile store b; load a)
1.150 + // but possible future optimizations might require this.
1.151 + x->field()->is_volatile()) {
1.152 + kill_memory();
1.153 + } else {
1.154 + kill_field(x->field(), x->needs_patching());
1.155 + }
1.156 + }
1.157 + void do_StoreIndexed (StoreIndexed* x) { kill_array(x->type()); }
1.158 + void do_MonitorEnter (MonitorEnter* x) { kill_memory(); }
1.159 + void do_MonitorExit (MonitorExit* x) { kill_memory(); }
1.160 + void do_Invoke (Invoke* x) { kill_memory(); }
1.161 + void do_UnsafePutRaw (UnsafePutRaw* x) { kill_memory(); }
1.162 + void do_UnsafePutObject(UnsafePutObject* x) { kill_memory(); }
1.163 + void do_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x) { kill_memory(); }
1.164 + void do_Intrinsic (Intrinsic* x) { if (!x->preserves_state()) kill_memory(); }
1.165 +
1.166 + void do_Phi (Phi* x) { /* nothing to do */ }
1.167 + void do_Local (Local* x) { /* nothing to do */ }
1.168 + void do_Constant (Constant* x) { /* nothing to do */ }
1.169 + void do_LoadField (LoadField* x) {
1.170 + if (x->is_init_point() || // getstatic is an initialization point so treat it as a wide kill
1.171 + x->field()->is_volatile()) { // the JMM requires this
1.172 + kill_memory();
1.173 + }
1.174 + }
1.175 + void do_ArrayLength (ArrayLength* x) { /* nothing to do */ }
1.176 + void do_LoadIndexed (LoadIndexed* x) { /* nothing to do */ }
1.177 + void do_NegateOp (NegateOp* x) { /* nothing to do */ }
1.178 + void do_ArithmeticOp (ArithmeticOp* x) { /* nothing to do */ }
1.179 + void do_ShiftOp (ShiftOp* x) { /* nothing to do */ }
1.180 + void do_LogicOp (LogicOp* x) { /* nothing to do */ }
1.181 + void do_CompareOp (CompareOp* x) { /* nothing to do */ }
1.182 + void do_IfOp (IfOp* x) { /* nothing to do */ }
1.183 + void do_Convert (Convert* x) { /* nothing to do */ }
1.184 + void do_NullCheck (NullCheck* x) { /* nothing to do */ }
1.185 + void do_TypeCast (TypeCast* x) { /* nothing to do */ }
1.186 + void do_NewInstance (NewInstance* x) { /* nothing to do */ }
1.187 + void do_NewTypeArray (NewTypeArray* x) { /* nothing to do */ }
1.188 + void do_NewObjectArray (NewObjectArray* x) { /* nothing to do */ }
1.189 + void do_NewMultiArray (NewMultiArray* x) { /* nothing to do */ }
1.190 + void do_CheckCast (CheckCast* x) { /* nothing to do */ }
1.191 + void do_InstanceOf (InstanceOf* x) { /* nothing to do */ }
1.192 + void do_BlockBegin (BlockBegin* x) { /* nothing to do */ }
1.193 + void do_Goto (Goto* x) { /* nothing to do */ }
1.194 + void do_If (If* x) { /* nothing to do */ }
1.195 + void do_IfInstanceOf (IfInstanceOf* x) { /* nothing to do */ }
1.196 + void do_TableSwitch (TableSwitch* x) { /* nothing to do */ }
1.197 + void do_LookupSwitch (LookupSwitch* x) { /* nothing to do */ }
1.198 + void do_Return (Return* x) { /* nothing to do */ }
1.199 + void do_Throw (Throw* x) { /* nothing to do */ }
1.200 + void do_Base (Base* x) { /* nothing to do */ }
1.201 + void do_OsrEntry (OsrEntry* x) { /* nothing to do */ }
1.202 + void do_ExceptionObject(ExceptionObject* x) { /* nothing to do */ }
1.203 + void do_RoundFP (RoundFP* x) { /* nothing to do */ }
1.204 + void do_UnsafeGetRaw (UnsafeGetRaw* x) { /* nothing to do */ }
1.205 + void do_UnsafeGetObject(UnsafeGetObject* x) { /* nothing to do */ }
1.206 + void do_UnsafePrefetchRead (UnsafePrefetchRead* x) { /* nothing to do */ }
1.207 + void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) { /* nothing to do */ }
1.208 + void do_ProfileCall (ProfileCall* x) { /* nothing to do */ }
1.209 + void do_ProfileReturnType (ProfileReturnType* x) { /* nothing to do */ }
1.210 + void do_ProfileInvoke (ProfileInvoke* x) { /* nothing to do */ };
1.211 + void do_RuntimeCall (RuntimeCall* x) { /* nothing to do */ };
1.212 + void do_MemBar (MemBar* x) { /* nothing to do */ };
1.213 + void do_RangeCheckPredicate(RangeCheckPredicate* x) { /* nothing to do */ };
1.214 +#ifdef ASSERT
1.215 + void do_Assert (Assert* x) { /* nothing to do */ };
1.216 +#endif
1.217 +};
1.218 +
1.219 +
1.220 +class ValueNumberingEffects: public ValueNumberingVisitor {
1.221 + private:
1.222 + ValueMap* _map;
1.223 +
1.224 + public:
1.225 + // implementation for abstract methods of ValueNumberingVisitor
1.226 + void kill_memory() { _map->kill_memory(); }
1.227 + void kill_field(ciField* field, bool all_offsets) { _map->kill_field(field, all_offsets); }
1.228 + void kill_array(ValueType* type) { _map->kill_array(type); }
1.229 +
1.230 + ValueNumberingEffects(ValueMap* map): _map(map) {}
1.231 +};
1.232 +
1.233 +
1.234 +class GlobalValueNumbering: public ValueNumberingVisitor {
1.235 + private:
1.236 + Compilation* _compilation; // compilation data
1.237 + ValueMap* _current_map; // value map of current block
1.238 + ValueMapArray _value_maps; // list of value maps for all blocks
1.239 + ValueSet _processed_values; // marker for instructions that were already processed
1.240 + bool _has_substitutions; // set to true when substitutions must be resolved
1.241 +
1.242 + public:
1.243 + // accessors
1.244 + Compilation* compilation() const { return _compilation; }
1.245 + ValueMap* current_map() { return _current_map; }
1.246 + ValueMap* value_map_of(BlockBegin* block) { return _value_maps.at(block->linear_scan_number()); }
1.247 + void set_value_map_of(BlockBegin* block, ValueMap* map) { assert(value_map_of(block) == NULL, ""); _value_maps.at_put(block->linear_scan_number(), map); }
1.248 +
1.249 + bool is_processed(Value v) { return _processed_values.contains(v); }
1.250 + void set_processed(Value v) { _processed_values.put(v); }
1.251 +
1.252 + // implementation for abstract methods of ValueNumberingVisitor
1.253 + void kill_memory() { current_map()->kill_memory(); }
1.254 + void kill_field(ciField* field, bool all_offsets) { current_map()->kill_field(field, all_offsets); }
1.255 + void kill_array(ValueType* type) { current_map()->kill_array(type); }
1.256 +
1.257 + // main entry point that performs global value numbering
1.258 + GlobalValueNumbering(IR* ir);
1.259 + void substitute(Instruction* instr); // substitute instruction if it is contained in current value map
1.260 +};
1.261 +
1.262 +#endif // SHARE_VM_C1_C1_VALUEMAP_HPP
