• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/base/bit_set.h"
22 #include "ecmascript/compiler/circuit.h"
23 #include "ecmascript/compiler/gate_accessor.h"
24 #include "ecmascript/mem/chunk_containers.h"
25 
26 namespace panda::ecmascript::kungfu {
27 class GateRegion : public ChunkObject {
28 public:
GateRegion(Chunk * chunk)29     GateRegion(Chunk* chunk) : gateList_(chunk), preds_(chunk),
30         succs_(chunk), dominatedRegions_(chunk) {}
31     ~GateRegion() = default;
32 
AddGate(GateRef gate)33     void AddGate(GateRef gate)
34     {
35         gateList_.emplace_back(gate);
36     }
37 
AddSucc(GateRegion * to)38     void AddSucc(GateRegion *to)
39     {
40         succs_.emplace_back(to);
41         to->preds_.emplace_back(this);
42     }
43 
SetVisited(GateAccessor & acc)44     void SetVisited(GateAccessor& acc)
45     {
46         acc.SetMark(state_, MarkCode::VISITED);
47     }
48 
SetFinished(GateAccessor & acc)49     void SetFinished(GateAccessor& acc)
50     {
51         acc.SetMark(state_, MarkCode::FINISHED);
52     }
53 
IsUnvisited(GateAccessor & acc)54     bool IsUnvisited(GateAccessor& acc) const
55     {
56         return acc.GetMark(state_) == MarkCode::NO_MARK;
57     }
58 
IsVisited(GateAccessor & acc)59     bool IsVisited(GateAccessor& acc) const
60     {
61         return acc.GetMark(state_) == MarkCode::VISITED;
62     }
63 
IsFinished(GateAccessor & acc)64     bool IsFinished(GateAccessor& acc) const
65     {
66         return acc.GetMark(state_) == MarkCode::FINISHED;
67     }
68 
IsLoopHead()69     bool IsLoopHead() const
70     {
71         return stateKind_ == StateKind::LOOP_HEAD;
72     }
73 
GetState()74     GateRef GetState() const
75     {
76         return state_;
77     }
78 
SetDead()79     void SetDead()
80     {
81         stateKind_ = StateKind::DEAD;
82     }
83 
IsDead()84     bool IsDead() const
85     {
86         return stateKind_ == StateKind::DEAD;
87     }
88 
89     bool IsSimple(GateAccessor *acc) const;
90 
HasComplexOuts()91     bool HasComplexOuts() const
92     {
93         return succs_.size() > 1;
94     }
95 
GetSimpleSuccRegion()96     GateRegion* GetSimpleSuccRegion() const
97     {
98         if (succs_.size() == 1) {
99             GateRegion* dst = succs_[0];
100             if (dst->GetPreds().size() == 1) {
101                 return dst;
102             }
103         }
104         return nullptr;
105     }
106 
ReplaceSucc(GateRegion * oldSucc,GateRegion * newSucc)107     void ReplaceSucc(GateRegion* oldSucc, GateRegion* newSucc)
108     {
109         for (size_t i = 0; i < succs_.size(); i++) {
110             if (succs_[i] == oldSucc) {
111                 succs_[i] = newSucc;
112             }
113         }
114         newSucc->AddPred(this);
115     }
116 
RemovePred(GateRegion * removedRegion)117     bool RemovePred(GateRegion* removedRegion)
118     {
119         for (auto it = preds_.begin(); it != preds_.end(); it++) {
120             if (*it == removedRegion) {
121                 preds_.erase(it);
122                 return true;
123             }
124         }
125         return false;
126     }
127 
AddPred(GateRegion * r)128     void AddPred(GateRegion* r)
129     {
130         for (auto p : preds_) {
131             if (p == r) {
132                 return;
133             }
134         }
135         preds_.emplace_back(r);
136     }
137 
AddGates(ChunkVector<GateRef> & gates)138     void AddGates(ChunkVector<GateRef>& gates)
139     {
140         gateList_.insert(gateList_.end(), gates.begin(), gates.end());
141     }
142 
GetGates()143     ChunkVector<GateRef>& GetGates()
144     {
145         return gateList_;
146     }
147 
GetPreds()148     ChunkVector<GateRegion*>& GetPreds()
149     {
150         return preds_;
151     }
152 
GetId()153     size_t GetId() const
154     {
155         return id_;
156     }
157 
Clear()158     void Clear()
159     {
160         id_ = 0;
161         depth_ = INVALID_DEPTH;
162         iDominator_ = nullptr;
163         gateList_.clear();
164         preds_.clear();
165         succs_.clear();
166         dominatedRegions_.clear();
167     }
168 
SetLoopNumber(int32_t loopNumber)169     void SetLoopNumber(int32_t loopNumber)
170     {
171         loopNumber_ = static_cast<int32_t>(loopNumber);
172     }
173 
GetLoopNumber()174     int32_t GetLoopNumber() const
175     {
176         return static_cast<int32_t>(loopNumber_);
177     }
178 
HasLoopNumber()179     bool HasLoopNumber() const
180     {
181         return loopNumber_ >= 0;
182     }
183 
GetDominator()184     GateRegion* GetDominator() const
185     {
186         return iDominator_;
187     }
188 
GetDominatedRegions()189     ChunkVector<GateRegion*>& GetDominatedRegions()
190     {
191         return dominatedRegions_;
192     }
193 
GetDepth()194     int32_t GetDepth() const
195     {
196         return depth_;
197     }
198 
SetLoopIndex(int32_t loopIndex)199     void SetLoopIndex(int32_t loopIndex)
200     {
201         loopIndex_ = loopIndex;
202     }
203 
GetLoopIndex()204     int32_t GetLoopIndex() const
205     {
206         return loopIndex_;
207     }
208 
SetLoopDepth(int32_t loopDepth)209     void SetLoopDepth(int32_t loopDepth)
210     {
211         loopDepth_ = loopDepth;
212     }
213 
GetLoopDepth()214     int32_t GetLoopDepth() const
215     {
216         return loopDepth_;
217     }
218 
219 private:
220     enum StateKind {
221         BRANCH,
222         MERGE,
223         LOOP_HEAD,
224         OTHER,
225         DEAD
226     };
227     static constexpr int32_t INVALID_DEPTH = -1;
228     static constexpr int32_t INVALID_INDEX = -1;
229     size_t id_ {0};
230     int32_t depth_ {INVALID_DEPTH};
231     GateRegion* iDominator_ {nullptr};
232     ChunkVector<GateRef> gateList_;
233     ChunkVector<GateRegion*> preds_;
234     ChunkVector<GateRegion*> succs_;
235     ChunkVector<GateRegion*> dominatedRegions_;
236     GateRef state_ {Circuit::NullGate()};
237     StateKind stateKind_ {StateKind::OTHER};
238     int32_t loopNumber_ {INVALID_INDEX};
239     int32_t loopIndex_ {INVALID_INDEX};
240     int32_t loopDepth_ {INVALID_DEPTH};
241     friend class ArrayBoundsCheckElimination;
242     friend class CFGBuilder;
243     friend class GateScheduler;
244     friend class ImmediateDominatorsGenerator;
245     friend class LoopInfoBuilder;
246     friend class GraphLinearizer;
247     friend class StateDependBuilder;
248 };
249 
250 class GraphLinearizer {
251 public:
252     using ControlFlowGraph = std::vector<std::vector<GateRef>>;
253     struct LoopInfo {
254         GateRegion* loopHead {nullptr};
255         BitSet* loopBodys {nullptr};
256         ChunkVector<GateRegion*>* loopExits {nullptr};
257         LoopInfo* outer {nullptr};
258         size_t loopIndex {0};
259         size_t loopDepth {0};
260     };
261 
262     GraphLinearizer(Circuit *circuit, bool enableLog, const std::string &name, Chunk *chunk, bool onlyBB = false,
263                     bool loopInvariantCodeMotion = false, bool enableLiteCG = false)
enableLog_(enableLog)264         : enableLog_(enableLog), methodName_(name), chunk_(chunk), circuit_(circuit), acc_(circuit),
265           gateIdToGateInfo_(chunk), regionList_(chunk), regionRootList_(chunk), loops_(chunk), onlyBB_(onlyBB),
266           loopInvariantCodeMotion_(loopInvariantCodeMotion), enableLiteCG_(enableLiteCG)
267     {
268     }
269 
270     void Run(ControlFlowGraph &result);
271 
GetStateOfSchedulableGate(GateRef gate)272     GateRef GetStateOfSchedulableGate(GateRef gate) const
273     {
274         return GateToRegion(gate)->GetState();
275     }
276 
enableLiteCG()277     bool enableLiteCG() const
278     {
279         return enableLiteCG_;
280     }
281 
282 private:
283     enum class ScheduleModel { LIR, JS_OPCODE };
284     enum class ScheduleState { NONE, FIXED, SELECTOR, SCHEDELABLE };
285     struct GateInfo {
GateInfoGateInfo286         GateInfo(GateRegion* region) : region(region) {}
287         GateRegion* region {nullptr};
288         GateRegion* upperBound {nullptr};
289         size_t schedulableUseCount {0};
290         ScheduleState state_ {ScheduleState::NONE};
291 
IsSchedulableGateInfo292         bool IsSchedulable() const
293         {
294             return state_ == ScheduleState::SCHEDELABLE;
295         }
296 
IsFixedGateInfo297         bool IsFixed() const
298         {
299             return state_ == ScheduleState::FIXED || IsSelector();
300         }
301 
IsSelectorGateInfo302         bool IsSelector() const
303         {
304             return state_ == ScheduleState::SELECTOR;
305         }
306 
IsNoneGateInfo307         bool IsNone() const
308         {
309             return state_ == ScheduleState::NONE;
310         }
311     };
312 
IsLogEnabled()313     bool IsLogEnabled() const
314     {
315         return enableLog_;
316     }
317 
GetMethodName()318     const std::string& GetMethodName() const
319     {
320         return methodName_;
321     }
322 
IsEnableLoopInvariantCodeMotion()323     bool IsEnableLoopInvariantCodeMotion() const
324     {
325         return loopInvariantCodeMotion_;
326     }
327 
328     void LinearizeGraph();
329     void LinearizeRegions(ControlFlowGraph &result);
330     void CreateGateRegion(GateRef gate);
331     GateRegion* FindPredRegion(GateRef input);
332     GateRegion* GetCommonDominator(GateRegion* left, GateRegion* right) const;
333 
GetGateInfo(GateRef gate)334     GateInfo& GetGateInfo(GateRef gate)
335     {
336         auto id = acc_.GetId(gate);
337         ASSERT(id < gateIdToGateInfo_.size());
338         return gateIdToGateInfo_[id];
339     }
340 
GetGateInfo(GateRef gate)341     const GateInfo& GetGateInfo(GateRef gate) const
342     {
343         auto id = acc_.GetId(gate);
344         ASSERT(id < gateIdToGateInfo_.size());
345         return gateIdToGateInfo_[id];
346     }
347 
GateToRegion(GateRef gate)348     GateRegion* GateToRegion(GateRef gate) const
349     {
350         const GateInfo& info = GetGateInfo(gate);
351         return info.region;
352     }
353 
GateToUpperBound(GateRef gate)354     GateRegion* GateToUpperBound(GateRef gate) const
355     {
356         const GateInfo& info = GetGateInfo(gate);
357         return info.upperBound;
358     }
359 
GetEntryRegion()360     GateRegion* GetEntryRegion() const
361     {
362         ASSERT(!regionList_.empty());
363         return regionList_[0];
364     }
365 
AddFixedGateToRegion(GateRef gate,GateRegion * region)366     void AddFixedGateToRegion(GateRef gate, GateRegion* region)
367     {
368         GateInfo& info = GetGateInfo(gate);
369         ASSERT(info.upperBound == nullptr);
370         info.upperBound = region;
371         ASSERT(info.region == nullptr);
372         info.region = region;
373         if (acc_.GetOpCode(gate) == OpCode::VALUE_SELECTOR ||
374             acc_.GetOpCode(gate) == OpCode::DEPEND_SELECTOR) {
375             info.state_ = ScheduleState::SELECTOR;
376         } else {
377             info.state_ = ScheduleState::FIXED;
378         }
379         regionRootList_.emplace_back(gate);
380     }
381 
AddRootGateToRegion(GateRef gate,GateRegion * region)382     void AddRootGateToRegion(GateRef gate, GateRegion* region)
383     {
384         GateInfo& info = GetGateInfo(gate);
385         ASSERT(info.upperBound == nullptr);
386         info.upperBound = region;
387         ASSERT(info.region == nullptr);
388         info.region = region;
389         region->state_ = gate;
390         region->AddGate(gate);
391         info.state_ = ScheduleState::FIXED;
392         regionRootList_.emplace_back(gate);
393     }
394 
BindGate(GateRef gate,GateRegion * region)395     void BindGate(GateRef gate, GateRegion* region)
396     {
397         GateInfo& info = GetGateInfo(gate);
398         info.region = region;
399         region->AddGate(gate);
400     }
401 
IsScheduled(GateRef gate)402     bool IsScheduled(GateRef gate) const
403     {
404         GateRegion* region = GateToRegion(gate);
405         return region != nullptr;
406     }
407 
HasLoop()408     bool HasLoop() const
409     {
410         return loopNumber_ != 0;
411     }
412 
Reset()413     void Reset()
414     {
415         gateIdToGateInfo_.clear();
416         regionList_.clear();
417         regionRootList_.clear();
418         scheduleUpperBound_ = false;
419         model_ = ScheduleModel::LIR;
420         loopNumber_ = 0;
421     }
422 
EnableScheduleUpperBound()423     void EnableScheduleUpperBound()
424     {
425         scheduleUpperBound_ = true;
426     }
427 
SetScheduleJSOpcode()428     void SetScheduleJSOpcode()
429     {
430         model_ = ScheduleModel::JS_OPCODE;
431     }
432 
IsSchedueLIR()433     bool IsSchedueLIR() const
434     {
435         return model_ == ScheduleModel::LIR;
436     }
437 
GetLoopInfo(GateRegion * region)438     LoopInfo* GetLoopInfo(GateRegion *region)
439     {
440         auto loopIndex = region->GetLoopIndex();
441         if (loopIndex >= 0) {
442             ASSERT(static_cast<size_t>(loopIndex) <= loops_.size());
443             return &loops_[loopIndex];
444         }
445         return nullptr;
446     }
447 
448     size_t OptimizeCFG();
449     size_t OptimizeControls(GateRegion *region);
450     void MoveAndClear(GateRegion *from, GateRegion *to);
451     void PrintGraph(const char* title);
452 
453     bool enableLog_ {false};
454     bool scheduleUpperBound_ {false};
455     ScheduleModel model_ {ScheduleModel::LIR};
456     std::string methodName_;
457     Chunk* chunk_ {nullptr};
458     Circuit* circuit_ {nullptr};
459     size_t loopNumber_ {0};
460 
461     GateAccessor acc_;
462     ChunkVector<GateInfo> gateIdToGateInfo_;
463     ChunkVector<GateRegion*> regionList_;
464     ChunkVector<GateRef> regionRootList_;
465     ChunkVector<LoopInfo> loops_;
466 
467     bool onlyBB_ {false}; // dont schedule
468     bool loopInvariantCodeMotion_ {false};
469     bool enableLiteCG_ {false};
470     friend class ArrayBoundsCheckElimination;
471     friend class StringBuilderOptimizer;
472     friend class CFGBuilder;
473     friend class GateScheduler;
474     friend class ImmediateDominatorsGenerator;
475     friend class LoopInfoBuilder;
476     friend class StateSplitLinearizer;
477 };
478 };  // namespace panda::ecmascript::kungfu
479 
480 #endif  // ECMASCRIPT_COMPILER_GRAPH_LINEARIZER_H
481