c1_ValueMap.cpp revision 1472:c18cbe5936b8
1/*
2 * Copyright (c) 1999, 2005, 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 "incls/_precompiled.incl"
26#include "incls/_c1_ValueMap.cpp.incl"
27
28
29#ifndef PRODUCT
30
31  int ValueMap::_number_of_finds = 0;
32  int ValueMap::_number_of_hits = 0;
33  int ValueMap::_number_of_kills = 0;
34
35  #define TRACE_VALUE_NUMBERING(code) if (PrintValueNumbering) { code; }
36
37#else
38
39  #define TRACE_VALUE_NUMBERING(code)
40
41#endif
42
43
44ValueMap::ValueMap()
45  : _nesting(0)
46  , _entries(ValueMapInitialSize, NULL)
47  , _killed_values()
48  , _entry_count(0)
49{
50  NOT_PRODUCT(reset_statistics());
51}
52
53
54ValueMap::ValueMap(ValueMap* old)
55  : _nesting(old->_nesting + 1)
56  , _entries(old->_entries.length())
57  , _killed_values()
58  , _entry_count(old->_entry_count)
59{
60  for (int i = size() - 1; i >= 0; i--) {
61    _entries.at_put(i, old->entry_at(i));
62  }
63  _killed_values.set_from(&old->_killed_values);
64}
65
66
67void ValueMap::increase_table_size() {
68  int old_size = size();
69  int new_size = old_size * 2 + 1;
70
71  ValueMapEntryList worklist(8);
72  ValueMapEntryArray new_entries(new_size, NULL);
73  int new_entry_count = 0;
74
75  TRACE_VALUE_NUMBERING(tty->print_cr("increasing table size from %d to %d", old_size, new_size));
76
77  for (int i = old_size - 1; i >= 0; i--) {
78    ValueMapEntry* entry;
79    for (entry = entry_at(i); entry != NULL; entry = entry->next()) {
80      if (!is_killed(entry->value())) {
81        worklist.push(entry);
82      }
83    }
84
85    while (!worklist.is_empty()) {
86      entry = worklist.pop();
87      int new_index = entry_index(entry->hash(), new_size);
88
89      if (entry->nesting() != nesting() && new_entries.at(new_index) != entry->next()) {
90        // changing entries with a lower nesting than the current nesting of the table
91        // is not allowed because then the same entry is contained in multiple value maps.
92        // clone entry when next-pointer must be changed
93        entry = new ValueMapEntry(entry->hash(), entry->value(), entry->nesting(), NULL);
94      }
95      entry->set_next(new_entries.at(new_index));
96      new_entries.at_put(new_index, entry);
97      new_entry_count++;
98    }
99  }
100
101  _entries = new_entries;
102  _entry_count = new_entry_count;
103}
104
105
106Value ValueMap::find_insert(Value x) {
107  const intx hash = x->hash();
108  if (hash != 0) {
109    // 0 hash means: exclude from value numbering
110    NOT_PRODUCT(_number_of_finds++);
111
112    for (ValueMapEntry* entry = entry_at(entry_index(hash, size())); entry != NULL; entry = entry->next()) {
113      if (entry->hash() == hash) {
114        Value f = entry->value();
115
116        if (!is_killed(f) && f->is_equal(x)) {
117          NOT_PRODUCT(_number_of_hits++);
118          TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: %s %c%d equal to %c%d  (size %d, entries %d, nesting-diff %d)", x->name(), x->type()->tchar(), x->id(), f->type()->tchar(), f->id(), size(), entry_count(), nesting() - entry->nesting()));
119
120          if (entry->nesting() != nesting() && f->as_Constant() == NULL) {
121            // non-constant values of of another block must be pinned,
122            // otherwise it is possible that they are not evaluated
123            f->pin(Instruction::PinGlobalValueNumbering);
124          }
125
126          return f;
127
128        }
129      }
130    }
131
132    // x not found, so insert it
133    if (entry_count() >= size_threshold()) {
134      increase_table_size();
135    }
136    int idx = entry_index(hash, size());
137    _entries.at_put(idx, new ValueMapEntry(hash, x, nesting(), entry_at(idx)));
138    _entry_count++;
139
140    TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: insert %s %c%d  (size %d, entries %d, nesting %d)", x->name(), x->type()->tchar(), x->id(), size(), entry_count(), nesting()));
141  }
142
143  return x;
144}
145
146
147#define GENERIC_KILL_VALUE(must_kill_implementation)                                     \
148  NOT_PRODUCT(_number_of_kills++);                                                       \
149                                                                                         \
150  for (int i = size() - 1; i >= 0; i--) {                                                \
151    ValueMapEntry* prev_entry = NULL;                                                    \
152    for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) {     \
153      Value value = entry->value();                                                      \
154                                                                                         \
155      must_kill_implementation(must_kill, entry, value)                                  \
156                                                                                         \
157      if (must_kill) {                                                                   \
158        kill_value(value);                                                               \
159                                                                                         \
160        if (prev_entry == NULL) {                                                        \
161          _entries.at_put(i, entry->next());                                             \
162          _entry_count--;                                                                \
163        } else if (prev_entry->nesting() == nesting()) {                                 \
164          prev_entry->set_next(entry->next());                                           \
165          _entry_count--;                                                                \
166        } else {                                                                         \
167          prev_entry = entry;                                                            \
168        }                                                                                \
169                                                                                         \
170        TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: killed %s %c%d  (size %d, entries %d, nesting-diff %d)", value->name(), value->type()->tchar(), value->id(), size(), entry_count(), nesting() - entry->nesting()));   \
171      } else {                                                                           \
172        prev_entry = entry;                                                              \
173      }                                                                                  \
174    }                                                                                    \
175  }                                                                                      \
176
177#define MUST_KILL_MEMORY(must_kill, entry, value)                                        \
178  bool must_kill = value->as_LoadField() != NULL || value->as_LoadIndexed() != NULL;
179
180#define MUST_KILL_ARRAY(must_kill, entry, value)                                         \
181  bool must_kill = value->as_LoadIndexed() != NULL                                       \
182                   && value->type()->tag() == type->tag();
183
184#define MUST_KILL_FIELD(must_kill, entry, value)                                         \
185  /* ciField's are not unique; must compare their contents */                            \
186  LoadField* lf = value->as_LoadField();                                                 \
187  bool must_kill = lf != NULL                                                            \
188                   && lf->field()->holder() == field->holder()                           \
189                   && lf->field()->offset() == field->offset();
190
191#define MUST_KILL_EXCEPTION(must_kill, entry, value)                                     \
192  assert(entry->nesting() < nesting(), "must not find bigger nesting than current");     \
193  bool must_kill = (entry->nesting() == nesting() - 1);
194
195
196void ValueMap::kill_memory() {
197  GENERIC_KILL_VALUE(MUST_KILL_MEMORY);
198}
199
200void ValueMap::kill_array(ValueType* type) {
201  GENERIC_KILL_VALUE(MUST_KILL_ARRAY);
202}
203
204void ValueMap::kill_field(ciField* field) {
205  GENERIC_KILL_VALUE(MUST_KILL_FIELD);
206}
207
208void ValueMap::kill_exception() {
209  GENERIC_KILL_VALUE(MUST_KILL_EXCEPTION);
210}
211
212
213void ValueMap::kill_map(ValueMap* map) {
214  assert(is_global_value_numbering(), "only for global value numbering");
215  _killed_values.set_union(&map->_killed_values);
216}
217
218void ValueMap::kill_all() {
219  assert(is_local_value_numbering(), "only for local value numbering");
220  for (int i = size() - 1; i >= 0; i--) {
221    _entries.at_put(i, NULL);
222  }
223  _entry_count = 0;
224}
225
226
227#ifndef PRODUCT
228
229void ValueMap::print() {
230  tty->print_cr("(size %d, entries %d, nesting %d)", size(), entry_count(), nesting());
231
232  int entries = 0;
233  for (int i = 0; i < size(); i++) {
234    if (entry_at(i) != NULL) {
235      tty->print("  %2d: ", i);
236      for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) {
237        Value value = entry->value();
238        tty->print("%s %c%d (%s%d) -> ", value->name(), value->type()->tchar(), value->id(), is_killed(value) ? "x" : "", entry->nesting());
239        entries++;
240      }
241      tty->print_cr("NULL");
242    }
243  }
244
245  _killed_values.print();
246  assert(entry_count() == entries, "entry_count incorrect");
247}
248
249void ValueMap::reset_statistics() {
250  _number_of_finds = 0;
251  _number_of_hits = 0;
252  _number_of_kills = 0;
253}
254
255void ValueMap::print_statistics() {
256  float hit_rate = 0;
257  if (_number_of_finds != 0) {
258    hit_rate = (float)_number_of_hits / _number_of_finds;
259  }
260
261  tty->print_cr("finds:%3d  hits:%3d   kills:%3d  hit rate: %1.4f", _number_of_finds, _number_of_hits, _number_of_kills, hit_rate);
262}
263
264#endif
265
266
267
268class ShortLoopOptimizer : public ValueNumberingVisitor {
269 private:
270  GlobalValueNumbering* _gvn;
271  BlockList             _loop_blocks;
272  bool                  _too_complicated_loop;
273
274  // simplified access to methods of GlobalValueNumbering
275  ValueMap* current_map()                        { return _gvn->current_map(); }
276  ValueMap* value_map_of(BlockBegin* block)      { return _gvn->value_map_of(block); }
277
278  // implementation for abstract methods of ValueNumberingVisitor
279  void      kill_memory()                        { _too_complicated_loop = true; }
280  void      kill_field(ciField* field)           { current_map()->kill_field(field); };
281  void      kill_array(ValueType* type)          { current_map()->kill_array(type); };
282
283 public:
284  ShortLoopOptimizer(GlobalValueNumbering* gvn)
285    : _gvn(gvn)
286    , _loop_blocks(ValueMapMaxLoopSize)
287    , _too_complicated_loop(false)
288  {
289  }
290
291  bool process(BlockBegin* loop_header);
292};
293
294
295bool ShortLoopOptimizer::process(BlockBegin* loop_header) {
296  TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block"));
297
298  _too_complicated_loop = false;
299  _loop_blocks.clear();
300  _loop_blocks.append(loop_header);
301
302  for (int i = 0; i < _loop_blocks.length(); i++) {
303    BlockBegin* block = _loop_blocks.at(i);
304    TRACE_VALUE_NUMBERING(tty->print_cr("processing loop block B%d", block->block_id()));
305
306    if (block->is_set(BlockBegin::exception_entry_flag)) {
307      // this would be too complicated
308      return false;
309    }
310
311    // add predecessors to worklist
312    for (int j = block->number_of_preds() - 1; j >= 0; j--) {
313      BlockBegin* pred = block->pred_at(j);
314
315      ValueMap* pred_map = value_map_of(pred);
316      if (pred_map != NULL) {
317        current_map()->kill_map(pred_map);
318      } else if (!_loop_blocks.contains(pred)) {
319        if (_loop_blocks.length() >= ValueMapMaxLoopSize) {
320          return false;
321        }
322        _loop_blocks.append(pred);
323      }
324    }
325
326    // use the instruction visitor for killing values
327    for (Value instr = block->next(); instr != NULL; instr = instr->next()) {
328      instr->visit(this);
329      if (_too_complicated_loop) {
330        return false;
331      }
332    }
333  }
334
335  TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized"));
336  return true;
337}
338
339
340GlobalValueNumbering::GlobalValueNumbering(IR* ir)
341  : _current_map(NULL)
342  , _value_maps(ir->linear_scan_order()->length(), NULL)
343{
344  TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering"));
345
346  ShortLoopOptimizer short_loop_optimizer(this);
347  int subst_count = 0;
348
349  BlockList* blocks = ir->linear_scan_order();
350  int num_blocks = blocks->length();
351
352  BlockBegin* start_block = blocks->at(0);
353  assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block");
354  assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions");
355
356  // initial, empty value map with nesting 0
357  set_value_map_of(start_block, new ValueMap());
358
359  for (int i = 1; i < num_blocks; i++) {
360    BlockBegin* block = blocks->at(i);
361    TRACE_VALUE_NUMBERING(tty->print_cr("**** processing block B%d", block->block_id()));
362
363    int num_preds = block->number_of_preds();
364    assert(num_preds > 0, "block must have predecessors");
365
366    BlockBegin* dominator = block->dominator();
367    assert(dominator != NULL, "dominator must exist");
368    assert(value_map_of(dominator) != NULL, "value map of dominator must exist");
369
370    // create new value map with increased nesting
371    _current_map = new ValueMap(value_map_of(dominator));
372
373    if (num_preds == 1) {
374      assert(dominator == block->pred_at(0), "dominator must be equal to predecessor");
375      // nothing to do here
376
377    } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
378      // block has incoming backward branches -> try to optimize short loops
379      if (!short_loop_optimizer.process(block)) {
380        // loop is too complicated, so kill all memory loads because there might be
381        // stores to them in the loop
382        current_map()->kill_memory();
383      }
384
385    } else {
386      // only incoming forward branches that are already processed
387      for (int j = 0; j < num_preds; j++) {
388        BlockBegin* pred = block->pred_at(j);
389        ValueMap* pred_map = value_map_of(pred);
390
391        if (pred_map != NULL) {
392          // propagate killed values of the predecessor to this block
393          current_map()->kill_map(value_map_of(pred));
394        } else {
395          // kill all memory loads because predecessor not yet processed
396          // (this can happen with non-natural loops and OSR-compiles)
397          current_map()->kill_memory();
398        }
399      }
400    }
401
402    if (block->is_set(BlockBegin::exception_entry_flag)) {
403      current_map()->kill_exception();
404    }
405
406    TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print());
407
408    // visit all instructions of this block
409    for (Value instr = block->next(); instr != NULL; instr = instr->next()) {
410      assert(!instr->has_subst(), "substitution already set");
411
412      // check if instruction kills any values
413      instr->visit(this);
414
415      if (instr->hash() != 0) {
416        Value f = current_map()->find_insert(instr);
417        if (f != instr) {
418          assert(!f->has_subst(), "can't have a substitution");
419          instr->set_subst(f);
420          subst_count++;
421        }
422      }
423    }
424
425    // remember value map for successors
426    set_value_map_of(block, current_map());
427  }
428
429  if (subst_count != 0) {
430    SubstitutionResolver resolver(ir);
431  }
432
433  TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics());
434}
435