1 /* 2 * Copyright (c) 2021 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef PANDA_VERIFICATION_ABSINT_REG_CONTEXT_H_ 17 #define PANDA_VERIFICATION_ABSINT_REG_CONTEXT_H_ 18 19 #include "value/abstract_typed_value.h" 20 21 #include "util/index.h" 22 #include "util/lazy.h" 23 #include "util/str.h" 24 #include "util/shifted_vector.h" 25 26 #include "macros.h" 27 28 #include <algorithm> 29 30 namespace panda::verifier { 31 /* 32 Design decisions: 33 1. regs - unordered map, for speed (compared to map) and space efficiency (compared to vector) 34 after implementing sparse vectors - rebase on them (taking into consideration immutability, see immer) 35 */ 36 37 class RegContext { 38 public: 39 RegContext() = default; RegContext(size_t size)40 explicit RegContext(size_t size) : Regs_(size) {} 41 ~RegContext() = default; 42 DEFAULT_COPY_SEMANTIC(RegContext); 43 DEFAULT_MOVE_SEMANTIC(RegContext); 44 45 RegContext operator&(const RegContext &rhs) const 46 { 47 RegContext result(std::max(Regs_.size(), rhs.Regs_.size())); 48 auto result_it = result.Regs_.begin(); 49 auto lhs_it = Regs_.begin(); 50 auto rhs_it = rhs.Regs_.begin(); 51 while (lhs_it != Regs_.end() && rhs_it != rhs.Regs_.end()) { 52 if (!(*lhs_it).IsNone() && !(*rhs_it).IsNone()) { 53 *result_it = *lhs_it & *rhs_it; 54 } 55 ++lhs_it; 56 ++rhs_it; 57 ++result_it; 58 } 59 return result; 60 } 61 RegContext &operator&=(const RegContext &rhs) 62 { 63 auto lhs_it = Regs_.begin(); 64 auto rhs_it = rhs.Regs_.begin(); 65 while (lhs_it != Regs_.end() && rhs_it != rhs.Regs_.end()) { 66 if (!(*lhs_it).IsNone() && !(*rhs_it).IsNone()) { 67 *lhs_it = *lhs_it & *rhs_it; 68 } else { 69 *lhs_it = AbstractTypedValue {}; 70 } 71 ++lhs_it; 72 ++rhs_it; 73 } 74 while (lhs_it != Regs_.end()) { 75 *lhs_it = AbstractTypedValue {}; 76 ++lhs_it; 77 } 78 return *this; 79 } ChangeValuesOfSameOrigin(int idx,const AbstractTypedValue & atv)80 void ChangeValuesOfSameOrigin(int idx, const AbstractTypedValue &atv) 81 { 82 if (!Regs_.InValidRange(idx)) { 83 Regs_[idx] = atv; 84 return; 85 } 86 auto old_atv = Regs_[idx]; 87 if (old_atv.IsNone()) { 88 Regs_[idx] = atv; 89 return; 90 } 91 const auto &old_origin = old_atv.GetOrigin(); 92 if (!old_origin.IsValid()) { 93 Regs_[idx] = atv; 94 return; 95 } 96 auto it = Regs_.begin(); 97 while (it != Regs_.end()) { 98 if (!(*it).IsNone()) { 99 const auto &origin = (*it).GetOrigin(); 100 if (origin.IsValid() && origin == old_origin) { 101 *it = atv; 102 } 103 } 104 ++it; 105 } 106 } 107 AbstractTypedValue &operator[](int idx) 108 { 109 if (!Regs_.InValidRange(idx)) { 110 Regs_.ExtendToInclude(idx); 111 } 112 return Regs_[idx]; 113 } 114 AbstractTypedValue operator[](int idx) const 115 { 116 ASSERT(IsRegDefined(idx) && Regs_.InValidRange(idx)); 117 return Regs_[idx]; 118 } Size()119 size_t Size() const 120 { 121 size_t size = 0; 122 EnumerateAllRegs([&size](auto, auto) { 123 ++size; 124 return true; 125 }); 126 return size; 127 } 128 template <typename Callback> EnumerateAllRegs(Callback cb)129 void EnumerateAllRegs(Callback cb) const 130 { 131 for (int idx = Regs_.begin_index(); idx < Regs_.end_index(); ++idx) { 132 if (!Regs_[idx].IsNone()) { 133 const auto &atv = Regs_[idx]; 134 if (!cb(idx, atv)) { 135 return; 136 } 137 } 138 } 139 } 140 template <typename Callback> EnumerateAllRegs(Callback cb)141 void EnumerateAllRegs(Callback cb) 142 { 143 for (int idx = Regs_.begin_index(); idx < Regs_.end_index(); ++idx) { 144 if (!Regs_[idx].IsNone()) { 145 auto &atv = Regs_[idx]; 146 if (!cb(idx, atv)) { 147 return; 148 } 149 } 150 } 151 } HasInconsistentRegs()152 bool HasInconsistentRegs() const 153 { 154 bool result = false; 155 EnumerateAllRegs([&result](int, const auto &av) { 156 if (!av.IsConsistent()) { 157 result = true; 158 return false; 159 } 160 return true; 161 }); 162 return result; 163 } InconsistentRegsNums()164 auto InconsistentRegsNums() const 165 { 166 PandaVector<int> result; 167 EnumerateAllRegs([&result](int num, const auto &av) { 168 if (!av.IsConsistent()) { 169 result.push_back(num); 170 } 171 return true; 172 }); 173 return result; 174 } IsRegDefined(int num)175 bool IsRegDefined(int num) const 176 { 177 return Regs_.InValidRange(num) && !Regs_[num].IsNone(); 178 } WasConflictOnReg(int num)179 bool WasConflictOnReg(int num) const 180 { 181 return ConflictingRegs_.count(num) > 0; 182 } Clear()183 void Clear() 184 { 185 Regs_.clear(); 186 ConflictingRegs_.clear(); 187 } RemoveInconsistentRegs()188 void RemoveInconsistentRegs() 189 { 190 EnumerateAllRegs([this](int num, auto &atv) { 191 if (!atv.IsConsistent()) { 192 ConflictingRegs_.insert(num); 193 atv = AbstractTypedValue {}; 194 } else { 195 ConflictingRegs_.erase(num); 196 } 197 return true; 198 }); 199 } 200 template <typename ImageFunc> DumpRegs(ImageFunc img)201 PandaString DumpRegs(ImageFunc img) const 202 { 203 PandaString log_string {""}; 204 bool comma = false; 205 EnumerateAllRegs([&comma, &log_string, &img](int num, const auto &abs_type_val) { 206 PandaString result {num == -1 ? "acc" : "v" + NumToStr<PandaString>(num)}; 207 result += " : "; 208 result += abs_type_val.template Image<PandaString>(img); 209 if (comma) { 210 log_string += ", "; 211 }; 212 log_string += result; 213 comma = true; 214 return true; 215 }); 216 return log_string; 217 } 218 219 private: 220 ShiftedVector<1, AbstractTypedValue> Regs_; 221 222 PandaUnorderedSet<int> ConflictingRegs_; 223 }; 224 } // namespace panda::verifier 225 226 #endif // PANDA_VERIFICATION_ABSINT_REG_CONTEXT_H_ 227