1 /** 2 * Copyright (c) 2021-2022 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 COMPILER_OPTIMIZER_OPTIMIZATIONS_VN_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_VN_H 18 19 #include <unordered_map> 20 #include <array> 21 #include "utils/hash.h" 22 #include "optimizer/pass.h" 23 24 namespace panda::compiler { 25 class Inst; 26 class VnObject; 27 class Graph; 28 29 class VnObject { 30 public: 31 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-member-init,hicpp-member-init) VnObject()32 explicit VnObject() 33 { 34 for (uint8_t i = 0; i < MAX_ARRAY_SIZE; i++) { 35 objs_[i] = 0; 36 } 37 } 38 NO_MOVE_SEMANTIC(VnObject); 39 NO_COPY_SEMANTIC(VnObject); 40 ~VnObject() = default; 41 42 void Add(Inst *inst); 43 void Add(uint32_t obj); 44 void Add(uint64_t obj); 45 bool Compare(VnObject *obj); GetSize()46 uint32_t GetSize() const 47 { 48 return size_objs_; 49 } GetElement(uint32_t index)50 uint64_t GetElement(uint32_t index) const 51 { 52 ASSERT(index < size_objs_); 53 return objs_[index]; 54 } GetArray()55 uint32_t *GetArray() 56 { 57 return objs_.data(); 58 } 59 60 private: 61 uint8_t size_objs_ {0}; 62 // opcode, type, 2 inputs, 2 advanced property 63 static constexpr uint8_t MAX_ARRAY_SIZE = 6; 64 std::array<uint32_t, MAX_ARRAY_SIZE> objs_; 65 }; 66 67 struct VnObjEqual { operatorVnObjEqual68 bool operator()(VnObject *obj1, VnObject *obj2) const 69 { 70 return obj1->Compare(obj2); 71 } 72 }; 73 74 struct VnObjHash { operatorVnObjHash75 uint32_t operator()(VnObject *obj) const 76 { 77 return GetHash32(reinterpret_cast<const uint8_t *>(obj->GetArray()), obj->GetSize()); 78 } 79 }; 80 81 /* 82 * Optimization assigns numbers(named vn) to all instructions. 83 * Equivalent instructions have equivalent vn. 84 * If instruction A dominates B and they have equivalent vn, users B are moved to A and DCE removes B at the end. 85 * The instruction with the property NO_CSE has unique vn and they can't be removed. 86 * The optimization creates VnObject for instruction without NO_CSE. 87 * The VnObject is key for the instruction. 88 * The unordered_map is used for searching equivalent instruction by the key(VnObject). 89 */ 90 class ValNum : public Optimization { 91 public: 92 explicit ValNum(Graph *graph); 93 NO_MOVE_SEMANTIC(ValNum); 94 NO_COPY_SEMANTIC(ValNum); 95 ~ValNum() override = default; 96 97 bool RunImpl() override; 98 GetPassName()99 const char *GetPassName() const override 100 { 101 return "GVN"; 102 } 103 IsEnable()104 bool IsEnable() const override 105 { 106 return options.IsCompilerVn(); 107 } 108 109 void InvalidateAnalyses() override; 110 111 void FindEqualVnOrCreateNew(Inst *inst); 112 113 private: 114 using InstVector = ArenaVector<Inst *>; 115 116 // Sets vn for the inst 117 void SetInstValNum(Inst *inst); 118 119 bool TryToApplyCse(Inst *inst, InstVector *equiv_insts); 120 121 // !TODO add own allocator 122 ArenaUnorderedMap<VnObject *, InstVector, VnObjHash, VnObjEqual> map_insts_; 123 124 uint32_t curr_vn_ {0}; 125 bool cse_is_appied_ {false}; 126 }; 127 } // namespace panda::compiler 128 129 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_VN_H 130