1 /* 2 * Copyright (c) 2023 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 MAPLEBE_INCLUDE_CG_CFGO_H 17 #define MAPLEBE_INCLUDE_CG_CFGO_H 18 #include "cg_cfg.h" 19 #include "optimize_common.h" 20 #include "loop.h" 21 22 namespace maplebe { 23 24 enum CfgoPhase : maple::uint8 { 25 kCfgoDefault, 26 kCfgoPreRegAlloc, 27 kCfgoPostRegAlloc, 28 kPostCfgo, 29 }; 30 31 class ChainingPattern : public OptimizationPattern { 32 public: ChainingPattern(CGFunc & func)33 explicit ChainingPattern(CGFunc &func) : OptimizationPattern(func) 34 { 35 patternName = "BB Chaining"; 36 dotColor = kCfgoChaining; 37 } 38 ~ChainingPattern() override = default; 39 40 bool Optimize(BB &curBB) override; 41 42 protected: 43 bool NoInsnBetween(const BB &from, const BB &to) const; 44 bool DoSameThing(const BB &bb1, const Insn &last1, const BB &bb2, const Insn &last2) const; 45 bool MergeFallthuBB(BB &curBB); 46 bool MergeGotoBB(BB &curBB, BB &sucBB); 47 bool MoveSuccBBAsCurBBNext(BB &curBB, BB &sucBB); 48 bool RemoveGotoInsn(BB &curBB, BB &sucBB); 49 bool ClearCurBBAndResetTargetBB(BB &curBB, BB &sucBB); 50 }; 51 52 class SequentialJumpPattern : public OptimizationPattern { 53 public: SequentialJumpPattern(CGFunc & func)54 explicit SequentialJumpPattern(CGFunc &func) : OptimizationPattern(func) 55 { 56 patternName = "Sequential Jump"; 57 dotColor = kCfgoSj; 58 } 59 60 ~SequentialJumpPattern() override = default; 61 bool Optimize(BB &curBB) override; 62 63 protected: 64 void SkipSucBB(BB &curBB, BB &sucBB) const; 65 void UpdateSwitchSucc(BB &curBB, BB &sucBB) const; 66 // If the sucBB has one invalid predBB, the sucBB can not be skipped 67 bool HasInvalidPred(BB &sucBB) const; 68 }; 69 70 class FlipBRPattern : public OptimizationPattern { 71 public: FlipBRPattern(CGFunc & func,LoopAnalysis & loop)72 explicit FlipBRPattern(CGFunc &func, LoopAnalysis &loop) : OptimizationPattern(func), loopInfo(loop) 73 { 74 patternName = "Condition Flip"; 75 dotColor = kCfgoFlipCond; 76 } 77 78 ~FlipBRPattern() override = default; 79 bool Optimize(BB &curBB) override; 80 GetPhase()81 CfgoPhase GetPhase() const 82 { 83 return phase; 84 } SetPhase(CfgoPhase val)85 void SetPhase(CfgoPhase val) 86 { 87 phase = val; 88 } 89 CfgoPhase phase = kCfgoDefault; 90 91 protected: 92 void RelocateThrowBB(BB &curBB); 93 LoopAnalysis &loopInfo; 94 95 private: 96 virtual uint32 GetJumpTargetIdx(const Insn &insn) = 0; 97 virtual MOperator FlipConditionOp(MOperator flippedOp) = 0; 98 }; 99 100 // This class represents the scenario that the BB is unreachable. 101 class UnreachBBPattern : public OptimizationPattern { 102 public: UnreachBBPattern(CGFunc & func)103 explicit UnreachBBPattern(CGFunc &func) : OptimizationPattern(func) 104 { 105 patternName = "Unreachable BB"; 106 dotColor = kCfgoUnreach; 107 } 108 109 ~UnreachBBPattern() override = default; 110 InitPattern()111 void InitPattern() override 112 { 113 cgFunc->GetTheCFG()->FindAndMarkUnreachable(*cgFunc); 114 } 115 116 bool Optimize(BB &curBB) override; 117 }; 118 119 // This class represents the scenario that a common jump BB can be duplicated 120 // to one of its another predecessor. 121 class DuplicateBBPattern : public OptimizationPattern { 122 public: DuplicateBBPattern(CGFunc & func)123 explicit DuplicateBBPattern(CGFunc &func) : OptimizationPattern(func) 124 { 125 patternName = "Duplicate BB"; 126 dotColor = kCfgoDup; 127 } 128 129 ~DuplicateBBPattern() override = default; 130 bool Optimize(BB &curBB) override; 131 132 private: 133 static constexpr int kThreshold = 10; 134 }; 135 136 // This class represents the scenario that a BB contains nothing. 137 class EmptyBBPattern : public OptimizationPattern { 138 public: EmptyBBPattern(CGFunc & func)139 explicit EmptyBBPattern(CGFunc &func) : OptimizationPattern(func) 140 { 141 patternName = "Empty BB"; 142 dotColor = kCfgoEmpty; 143 } 144 145 ~EmptyBBPattern() override = default; 146 bool Optimize(BB &curBB) override; 147 }; 148 149 /* This class represents that two pred of a BB can cross-jump 150 * BB1: insn1 BB1: insn1 151 * insn2 b BB4 (branch newBB) 152 * insn3 BB2: insn4 (fallthru, no need branch) 153 * b BB3 BB4: insn2 154 * BB2: insn4 ==> insn3 155 * insn2 b BB3 156 * insn3 157 * b BB3 158 * BB1 & BB2 is BB3's pred, and has same insns(insn2, insn3). 159 * In BB2, we can split it into two BBs and set the newBB to be the fallthru of BB2. 160 * In BB1, same insns need to be deleted, and a jump insn pointing to the new BB is 161 * generated at the end of the BB. 162 */ 163 class CrossJumpBBPattern : public OptimizationPattern { 164 public: CrossJumpBBPattern(CGFunc & func)165 explicit CrossJumpBBPattern(CGFunc &func) : OptimizationPattern(func) 166 { 167 patternName = "Cross Jump BB"; 168 dotColor = kCfgoEmpty; 169 } 170 ~CrossJumpBBPattern() override = default; 171 172 bool Optimize(BB &curBB) override; 173 174 private: 175 enum MergeDirection { 176 kDirectionNone, 177 kDirectionForward, 178 kDirectionBackward, 179 kDirectionBoth, 180 }; 181 bool OptimizeOnce(const BB &curBB); 182 bool TryCrossJumpBB(BB &bb1, BB &bb2, MergeDirection dir = kDirectionBoth); 183 bool CheckBBSuccMatch(BB &bb1, BB &bb2); 184 uint32 CheckBBInsnsMatch(BB &bb1, BB &bb2, Insn *&f1, Insn *&f2); 185 void MergeMemInfo(BB &bb1, Insn &newpos1, BB &redirectBB); 186 void GetMergeDirection(BB &bb1, BB &bb2, const Insn &f1, const Insn &f2, MergeDirection &dir); 187 188 BB &SplitBB(BB &srcBB, Insn &lastInsn); 189 190 virtual uint32 GetJumpTargetIdx(const Insn &insn) const = 0; 191 virtual MOperator FlipConditionOp(MOperator flippedOp) const = 0; 192 virtual MOperator GetUnCondBranchMOP() const = 0; 193 194 static constexpr uint32 kMaxCrossJumpPreds = 50; // limit for compiler time 195 static constexpr uint32 kMinCrossJumpPreds = 2; // Noting to do if there is not at least two incoming edges 196 }; 197 198 class CFGOptimizer : public Optimizer { 199 public: CFGOptimizer(CGFunc & func,MemPool & memPool,LoopAnalysis & loop)200 CFGOptimizer(CGFunc &func, MemPool &memPool, LoopAnalysis &loop) : Optimizer(func, memPool), loopInfo(loop) 201 { 202 name = "CFGO"; 203 } 204 205 ~CFGOptimizer() override = default; GetPhase()206 CfgoPhase GetPhase() const 207 { 208 return phase; 209 } SetPhase(CfgoPhase val)210 void SetPhase(CfgoPhase val) 211 { 212 phase = val; 213 } 214 215 protected: 216 CfgoPhase phase = kCfgoDefault; 217 LoopAnalysis &loopInfo; 218 }; 219 220 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgPreCfgo, maplebe::CGFunc) 221 OVERRIDE_DEPENDENCE 222 MAPLE_FUNC_PHASE_DECLARE_END 223 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgCfgo, maplebe::CGFunc) 224 OVERRIDE_DEPENDENCE 225 MAPLE_FUNC_PHASE_DECLARE_END 226 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgPostCfgo, maplebe::CGFunc) 227 OVERRIDE_DEPENDENCE 228 MAPLE_FUNC_PHASE_DECLARE_END 229 } // namespace maplebe 230 231 #endif // MAPLEBE_INCLUDE_CG_CFGO_H