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 ECMASCRIPT_COMPILER_GRAPH_LINEARIZER_H 17 #define ECMASCRIPT_COMPILER_GRAPH_LINEARIZER_H 18 19 #include <numeric> 20 21 #include "ecmascript/compiler/circuit.h" 22 #include "ecmascript/compiler/gate_accessor.h" 23 #include "ecmascript/mem/chunk_containers.h" 24 25 namespace panda::ecmascript::kungfu { 26 class GateRegion : public ChunkObject { 27 public: GateRegion(Chunk * chunk)28 GateRegion(Chunk* chunk) : gateList_(chunk), preds_(chunk), 29 succs_(chunk), dominatedRegions_(chunk) {} 30 ~GateRegion() = default; 31 AddGate(GateRef gate)32 void AddGate(GateRef gate) 33 { 34 gateList_.emplace_back(gate); 35 } 36 AddSucc(GateRegion * to)37 void AddSucc(GateRegion *to) 38 { 39 succs_.emplace_back(to); 40 to->preds_.emplace_back(this); 41 } 42 SetVisited(GateAccessor & acc)43 void SetVisited(GateAccessor& acc) 44 { 45 acc.SetMark(state_, MarkCode::VISITED); 46 } 47 SetFinished(GateAccessor & acc)48 void SetFinished(GateAccessor& acc) 49 { 50 acc.SetMark(state_, MarkCode::FINISHED); 51 } 52 IsUnvisited(GateAccessor & acc)53 bool IsUnvisited(GateAccessor& acc) const 54 { 55 return acc.GetMark(state_) == MarkCode::NO_MARK; 56 } 57 IsVisited(GateAccessor & acc)58 bool IsVisited(GateAccessor& acc) const 59 { 60 return acc.GetMark(state_) == MarkCode::VISITED; 61 } 62 IsFinished(GateAccessor & acc)63 bool IsFinished(GateAccessor& acc) const 64 { 65 return acc.GetMark(state_) == MarkCode::FINISHED; 66 } 67 IsLoopHead()68 bool IsLoopHead() const 69 { 70 return stateKind_ == StateKind::LOOP_HEAD; 71 } 72 GetState()73 GateRef GetState() const 74 { 75 return state_; 76 } 77 SetDead()78 void SetDead() 79 { 80 stateKind_ = StateKind::DEAD; 81 } 82 IsDead()83 bool IsDead() const 84 { 85 return stateKind_ == StateKind::DEAD; 86 } 87 88 bool IsSimple(GateAccessor *acc) const; 89 HasComplexOuts()90 bool HasComplexOuts() const 91 { 92 return succs_.size() > 1; 93 } 94 GetSimpleSuccRegion()95 GateRegion* GetSimpleSuccRegion() const 96 { 97 if (succs_.size() == 1) { 98 GateRegion* dst = succs_[0]; 99 if (dst->GetPreds().size() == 1) { 100 return dst; 101 } 102 } 103 return nullptr; 104 } 105 ReplaceSucc(GateRegion * oldSucc,GateRegion * newSucc)106 void ReplaceSucc(GateRegion* oldSucc, GateRegion* newSucc) 107 { 108 for (size_t i = 0; i < succs_.size(); i++) { 109 if (succs_[i] == oldSucc) { 110 succs_[i] = newSucc; 111 } 112 } 113 newSucc->AddPred(this); 114 } 115 RemovePred(GateRegion * removedRegion)116 bool RemovePred(GateRegion* removedRegion) 117 { 118 for (auto it = preds_.begin(); it != preds_.end(); it++) { 119 if (*it == removedRegion) { 120 preds_.erase(it); 121 return true; 122 } 123 } 124 return false; 125 } 126 AddPred(GateRegion * r)127 void AddPred(GateRegion* r) 128 { 129 for (auto p : preds_) { 130 if (p == r) { 131 return; 132 } 133 } 134 preds_.emplace_back(r); 135 } 136 AddGates(ChunkVector<GateRef> & gates)137 void AddGates(ChunkVector<GateRef>& gates) 138 { 139 gateList_.insert(gateList_.end(), gates.begin(), gates.end()); 140 } 141 GetGates()142 ChunkVector<GateRef>& GetGates() 143 { 144 return gateList_; 145 } 146 GetPreds()147 ChunkVector<GateRegion*>& GetPreds() 148 { 149 return preds_; 150 } 151 GetId()152 size_t GetId() const 153 { 154 return id_; 155 } 156 Clear()157 void Clear() 158 { 159 id_ = 0; 160 depth_ = INVALID_DEPTH; 161 iDominator_ = nullptr; 162 gateList_.clear(); 163 preds_.clear(); 164 succs_.clear(); 165 dominatedRegions_.clear(); 166 } 167 SetLoopNumber(size_t loopNumber)168 void SetLoopNumber(size_t loopNumber) 169 { 170 loopNumber_ = static_cast<int32_t>(loopNumber); 171 } 172 GetLoopNumber()173 size_t GetLoopNumber() const 174 { 175 return static_cast<size_t>(loopNumber_); 176 } 177 HasLoopNumber()178 bool HasLoopNumber() const 179 { 180 return loopNumber_ >= 0; 181 } 182 183 private: 184 enum StateKind { 185 BRANCH, 186 MERGE, 187 LOOP_HEAD, 188 OTHER, 189 DEAD 190 }; 191 static constexpr int32_t INVALID_DEPTH = -1; 192 size_t id_ {0}; 193 int32_t depth_ {INVALID_DEPTH}; 194 GateRegion* iDominator_ {nullptr}; 195 GateRegion* loopHead_ {nullptr}; 196 ChunkVector<GateRef> gateList_; 197 ChunkVector<GateRegion*> preds_; 198 ChunkVector<GateRegion*> succs_; 199 ChunkVector<GateRegion*> dominatedRegions_; 200 GateRef state_ {Circuit::NullGate()}; 201 StateKind stateKind_ {StateKind::OTHER}; 202 int32_t loopNumber_ {INVALID_DEPTH}; 203 friend class CFGBuilder; 204 friend class GateScheduler; 205 friend class ImmediateDominatorsGenerator; 206 friend class LoopInfoBuilder; 207 friend class GraphLinearizer; 208 friend class StateDependBuilder; 209 }; 210 211 class GraphLinearizer { 212 public: 213 using ControlFlowGraph = std::vector<std::vector<GateRef>>; 214 GraphLinearizer(Circuit * circuit,bool enableLog,const std::string & name,Chunk * chunk)215 GraphLinearizer(Circuit *circuit, bool enableLog, const std::string& name, Chunk* chunk) 216 : enableLog_(enableLog), methodName_(name), chunk_(chunk), circuit_(circuit), 217 acc_(circuit), gateIdToGateInfo_(chunk), 218 regionList_(chunk), regionRootList_(chunk) {} 219 220 void Run(ControlFlowGraph &result); 221 private: 222 enum class ScheduleModel { LIR, JS_OPCODE }; 223 enum class ScheduleState { NONE, FIXED, SELECTOR, SCHEDELABLE }; 224 struct GateInfo { GateInfoGateInfo225 GateInfo(GateRegion* region) : region(region) {} 226 GateRegion* region {nullptr}; 227 GateRegion* upperBound {nullptr}; 228 size_t schedulableUseCount {0}; 229 ScheduleState state_ {ScheduleState::NONE}; 230 IsSchedulableGateInfo231 bool IsSchedulable() const 232 { 233 return state_ == ScheduleState::SCHEDELABLE; 234 } 235 IsFixedGateInfo236 bool IsFixed() const 237 { 238 return state_ == ScheduleState::FIXED || IsSelector(); 239 } 240 IsSelectorGateInfo241 bool IsSelector() const 242 { 243 return state_ == ScheduleState::SELECTOR; 244 } 245 IsNoneGateInfo246 bool IsNone() const 247 { 248 return state_ == ScheduleState::NONE; 249 } 250 }; 251 IsLogEnabled()252 bool IsLogEnabled() const 253 { 254 return enableLog_; 255 } 256 GetMethodName()257 const std::string& GetMethodName() const 258 { 259 return methodName_; 260 } 261 262 void LinearizeGraph(); 263 void LinearizeRegions(ControlFlowGraph &result); 264 void CreateGateRegion(GateRef gate); 265 GateRegion* FindPredRegion(GateRef input); 266 GateRegion* GetCommonDominator(GateRegion* left, GateRegion* right) const; 267 GetGateInfo(GateRef gate)268 GateInfo& GetGateInfo(GateRef gate) 269 { 270 auto id = acc_.GetId(gate); 271 ASSERT(id < gateIdToGateInfo_.size()); 272 return gateIdToGateInfo_[id]; 273 } 274 GetGateInfo(GateRef gate)275 const GateInfo& GetGateInfo(GateRef gate) const 276 { 277 auto id = acc_.GetId(gate); 278 ASSERT(id < gateIdToGateInfo_.size()); 279 return gateIdToGateInfo_[id]; 280 } 281 GateToRegion(GateRef gate)282 GateRegion* GateToRegion(GateRef gate) const 283 { 284 const GateInfo& info = GetGateInfo(gate); 285 return info.region; 286 } 287 GateToUpperBound(GateRef gate)288 GateRegion* GateToUpperBound(GateRef gate) const 289 { 290 const GateInfo& info = GetGateInfo(gate); 291 return info.upperBound; 292 } 293 GetEntryRegion()294 GateRegion* GetEntryRegion() const 295 { 296 ASSERT(!regionList_.empty()); 297 return regionList_[0]; 298 } 299 AddFixedGateToRegion(GateRef gate,GateRegion * region)300 void AddFixedGateToRegion(GateRef gate, GateRegion* region) 301 { 302 GateInfo& info = GetGateInfo(gate); 303 ASSERT(info.upperBound == nullptr); 304 info.upperBound = region; 305 ASSERT(info.region == nullptr); 306 info.region = region; 307 if (acc_.GetOpCode(gate) == OpCode::VALUE_SELECTOR || 308 acc_.GetOpCode(gate) == OpCode::DEPEND_SELECTOR) { 309 info.state_ = ScheduleState::SELECTOR; 310 } else { 311 info.state_ = ScheduleState::FIXED; 312 } 313 regionRootList_.emplace_back(gate); 314 } 315 AddRootGateToRegion(GateRef gate,GateRegion * region)316 void AddRootGateToRegion(GateRef gate, GateRegion* region) 317 { 318 GateInfo& info = GetGateInfo(gate); 319 ASSERT(info.upperBound == nullptr); 320 info.upperBound = region; 321 ASSERT(info.region == nullptr); 322 info.region = region; 323 region->state_ = gate; 324 region->AddGate(gate); 325 info.state_ = ScheduleState::FIXED; 326 regionRootList_.emplace_back(gate); 327 } 328 BindGate(GateRef gate,GateRegion * region)329 void BindGate(GateRef gate, GateRegion* region) 330 { 331 GateInfo& info = GetGateInfo(gate); 332 info.region = region; 333 region->AddGate(gate); 334 } 335 IsScheduled(GateRef gate)336 bool IsScheduled(GateRef gate) const 337 { 338 GateRegion* region = GateToRegion(gate); 339 return region != nullptr; 340 } 341 HasLoop()342 bool HasLoop() const 343 { 344 return loopNumber_ != 0; 345 } 346 Reset()347 void Reset() 348 { 349 gateIdToGateInfo_.clear(); 350 regionList_.clear(); 351 regionRootList_.clear(); 352 scheduleUpperBound_ = false; 353 model_ = ScheduleModel::LIR; 354 loopNumber_ = 0; 355 } 356 EnableScheduleUpperBound()357 void EnableScheduleUpperBound() 358 { 359 scheduleUpperBound_ = true; 360 } 361 SetScheduleJSOpcode()362 void SetScheduleJSOpcode() 363 { 364 model_ = ScheduleModel::JS_OPCODE; 365 } 366 IsSchedueLIR()367 bool IsSchedueLIR() const 368 { 369 return model_ == ScheduleModel::LIR; 370 } 371 372 size_t OptimizeCFG(); 373 size_t OptimizeControls(GateRegion *region); 374 void MoveAndClear(GateRegion *from, GateRegion *to); 375 void PrintGraph(const char* title); 376 377 bool enableLog_ {false}; 378 bool scheduleUpperBound_ {false}; 379 ScheduleModel model_ {ScheduleModel::LIR}; 380 std::string methodName_; 381 Chunk* chunk_ {nullptr}; 382 Circuit* circuit_ {nullptr}; 383 size_t loopNumber_ {0}; 384 385 GateAccessor acc_; 386 ChunkVector<GateInfo> gateIdToGateInfo_; 387 ChunkVector<GateRegion*> regionList_; 388 ChunkVector<GateRef> regionRootList_; 389 390 friend class CFGBuilder; 391 friend class GateScheduler; 392 friend class ImmediateDominatorsGenerator; 393 friend class LoopInfoBuilder; 394 friend class StateSplitLinearizer; 395 }; 396 }; // namespace panda::ecmascript::kungfu 397 398 #endif // ECMASCRIPT_COMPILER_GRAPH_LINEARIZER_H 399