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_BALANCE_EXPRESSIONS_H_ 17 #define COMPILER_OPTIMIZER_BALANCE_EXPRESSIONS_H_ 18 19 #include "optimizer/ir/basicblock.h" 20 #include "optimizer/ir/graph.h" 21 #include "optimizer/pass.h" 22 #include "utils/arena_containers.h" 23 24 namespace panda::compiler { 25 class BalanceExpressions : public Optimization { 26 public: 27 // For current realization, any binary commutative and associative operator suits; 28 29 static constexpr size_t DEFAULT_GRAPH_DEPTH = 3; 30 BalanceExpressions(Graph * graph)31 explicit BalanceExpressions(Graph *graph) 32 : Optimization(graph), 33 sources_(graph->GetLocalAllocator()->Adapter()), 34 operators_(graph->GetLocalAllocator()->Adapter()) 35 { 36 sources_.reserve(1U << DEFAULT_GRAPH_DEPTH); 37 operators_.reserve(1U << DEFAULT_GRAPH_DEPTH); 38 } 39 40 bool RunImpl() override; 41 GetPassName()42 const char *GetPassName() const override 43 { 44 return "BalanceExpressions"; 45 } 46 IsEnable()47 bool IsEnable() const override 48 { 49 return options.IsCompilerBalanceExpressions(); 50 } 51 52 void Dump(std::ostream *out) const; 53 54 void InvalidateAnalyses() override; 55 56 private: 57 void ProcessBB(BasicBlock *bb); 58 bool SuitableInst(Inst *inst); 59 60 Inst *ProccesExpressionChain(Inst *last_operator); 61 void AnalyzeInputsRec(Inst *inst); 62 void TryExtendChainRec(Inst *inst); 63 64 bool NeedsOptimization(); 65 Inst *OptimizeExpression(Inst *inst_after_expr); 66 template <bool is_first_call> 67 Inst *AllocateSourcesRec(size_t first_idx, size_t last_idx); 68 Inst *GetOperand(size_t first_idx, size_t last_idx); 69 Inst *GenerateElementalOperator(Inst *lhs, Inst *rhs); 70 void Reset(); 71 void Dump(); 72 SetOpcode(Opcode opc)73 void SetOpcode(Opcode opc) 74 { 75 opcode_ = opc; 76 } GetOpcode()77 Opcode GetOpcode() const 78 { 79 return opcode_; 80 } SetBB(BasicBlock * bb)81 void SetBB(BasicBlock *bb) 82 { 83 bb_ = bb; 84 } GetBB()85 BasicBlock *GetBB() const 86 { 87 return bb_; 88 } SetIsApplied(bool value)89 void SetIsApplied(bool value) 90 { 91 is_applied_ = value; 92 } 93 94 // Calculates the lowest integral power of two that is greater than `val` 95 // Same as std::bit_ceil() introduced in C++20 96 template <typename T> GetBitCeil(T val)97 T GetBitCeil(T val) 98 { 99 static_assert(std::is_unsigned<T>::value); 100 if (val <= 1) { 101 return 1; 102 } 103 104 size_t highest_bit_idx = 0; 105 T val_copy = val; 106 while (val_copy != 0) { 107 val_copy = val_copy >> 1U; 108 highest_bit_idx++; 109 } 110 111 T res = 1U; 112 ASSERT(highest_bit_idx >= 1); 113 if ((val << (std::numeric_limits<T>::digits - highest_bit_idx + 1)) == 0) { 114 // (highest_bit_idx >= 1) as soon as (val > 1) 115 // NOLINTNEXTLINE(clang-analyzer-core.UndefinedBinaryOperatorResult) 116 return res << (highest_bit_idx - 1); 117 } 118 return res << (highest_bit_idx); 119 } 120 121 // If x is not 0 or 1, calculates the largest integral power of two that is less than `val` 122 // Same as std::bit_floor() introduced in C++20, except that return strictly less than `val` 123 template <typename T> GetBitFloor(T val)124 T GetBitFloor(T val) 125 { 126 static_assert(std::is_unsigned<T>::value); 127 if (val <= 1) { 128 return 0; 129 } 130 131 size_t highest_bit_idx = 0; 132 T val_copy = val; 133 while (val_copy != 0) { 134 val_copy = val_copy >> 1U; 135 highest_bit_idx++; 136 } 137 T res = 1U; 138 ASSERT(highest_bit_idx >= 2U); 139 if ((val << (std::numeric_limits<T>::digits - highest_bit_idx + 1)) == 0) { 140 // (highest_bit_idx >= 2) as soon as (val > 1) 141 // NOLINTNEXTLINE(clang-analyzer-core.UndefinedBinaryOperatorResult) 142 return res << (highest_bit_idx - 2U); 143 } 144 // (highest_bit_idx >= 2) as soon as (val > 1) 145 // NOLINTNEXTLINE(clang-analyzer-core.UndefinedBinaryOperatorResult) 146 return res << (highest_bit_idx - 1); 147 } 148 149 private: 150 Opcode opcode_ {Opcode::INVALID}; 151 Marker processed_inst_mrk_ = UNDEF_MARKER; 152 153 // i.e. critical path 154 size_t expr_cur_depth_ {0}; 155 size_t expr_max_depth_ {0}; 156 157 BasicBlock *bb_ {nullptr}; 158 159 // Expression's terms: 160 InstVector sources_; 161 162 // Expression's operators: 163 InstVector operators_; 164 size_t operators_alloc_idx_ = 0; 165 166 bool is_applied_ {false}; 167 }; 168 169 inline std::ostream &operator<<(std::ostream &os, const BalanceExpressions &expr) 170 { 171 expr.Dump(&os); 172 return os; 173 } 174 } // namespace panda::compiler 175 176 #endif // COMPILER_OPTIMIZER_BALANCE_EXPRESSIONS_H_ 177