local_value_numbering.h revision 9b7085a4e7c40e7fa01932ea1647a4a33ac1c585 
1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_
18#define ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_
19
20#include "compiler_internals.h"
21
22#define NO_VALUE 0xffff
23#define ARRAY_REF 0xfffe
24
25namespace art {
26
27// Key is s_reg, value is value name.
28typedef SafeMap<uint16_t, uint16_t> SregValueMap;
29// Key is concatenation of quad, value is value name.
30typedef SafeMap<uint64_t, uint16_t> ValueMap;
31// Key represents a memory address, value is generation.
32typedef SafeMap<uint32_t, uint16_t> MemoryVersionMap;
33
34class LocalValueNumbering {
35 public:
36  explicit LocalValueNumbering(CompilationUnit* cu) : cu_(cu) {}
37
38  static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
39    return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 |
40            static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier));
41  };
42
43  uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
44    uint16_t res;
45    uint64_t key = BuildKey(op, operand1, operand2, modifier);
46    ValueMap::iterator it = value_map_.find(key);
47    if (it != value_map_.end()) {
48      res = it->second;
49    } else {
50      res = value_map_.size() + 1;
51      value_map_.Put(key, res);
52    }
53    return res;
54  };
55
56  bool ValueExists(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const {
57    uint64_t key = BuildKey(op, operand1, operand2, modifier);
58    ValueMap::const_iterator it = value_map_.find(key);
59    return (it != value_map_.end());
60  };
61
62  uint16_t GetMemoryVersion(uint16_t base, uint16_t field) {
63    uint32_t key = (base << 16) | field;
64    uint16_t res;
65    MemoryVersionMap::iterator it = memory_version_map_.find(key);
66    if (it == memory_version_map_.end()) {
67      res = 0;
68      memory_version_map_.Put(key, res);
69    } else {
70      res = it->second;
71    }
72    return res;
73  };
74
75  void AdvanceMemoryVersion(uint16_t base, uint16_t field) {
76    uint32_t key = (base << 16) | field;
77    MemoryVersionMap::iterator it = memory_version_map_.find(key);
78    if (it == memory_version_map_.end()) {
79      memory_version_map_.Put(key, 0);
80    } else {
81      it->second++;
82    }
83  };
84
85  void SetOperandValue(uint16_t s_reg, uint16_t value) {
86    SregValueMap::iterator it = sreg_value_map_.find(s_reg);
87    if (it != sreg_value_map_.end()) {
88      DCHECK_EQ(it->second, value);
89    } else {
90      sreg_value_map_.Put(s_reg, value);
91    }
92  };
93
94  uint16_t GetOperandValue(int s_reg) {
95    uint16_t res = NO_VALUE;
96    SregValueMap::iterator it = sreg_value_map_.find(s_reg);
97    if (it != sreg_value_map_.end()) {
98      res = it->second;
99    } else {
100      // First use
101      res = LookupValue(NO_VALUE, s_reg, NO_VALUE, NO_VALUE);
102      sreg_value_map_.Put(s_reg, res);
103    }
104    return res;
105  };
106
107  void SetOperandValueWide(uint16_t s_reg, uint16_t value) {
108    SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
109    if (it != sreg_wide_value_map_.end()) {
110      DCHECK_EQ(it->second, value);
111    } else {
112      sreg_wide_value_map_.Put(s_reg, value);
113    }
114  };
115
116  uint16_t GetOperandValueWide(int s_reg) {
117    uint16_t res = NO_VALUE;
118    SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
119    if (it != sreg_wide_value_map_.end()) {
120      res = it->second;
121    } else {
122      // First use
123      res = LookupValue(NO_VALUE, s_reg, NO_VALUE, NO_VALUE);
124      sreg_wide_value_map_.Put(s_reg, res);
125    }
126    return res;
127  };
128
129  uint16_t GetValueNumber(MIR* mir);
130
131 private:
132  CompilationUnit* const cu_;
133  SregValueMap sreg_value_map_;
134  SregValueMap sreg_wide_value_map_;
135  ValueMap value_map_;
136  MemoryVersionMap memory_version_map_;
137  std::set<uint16_t> null_checked_;
138};
139
140} // namespace art
141
142#endif  // ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_
143