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
26namespace panda::ecmascript::kungfu {
27class GateRegion : public ChunkObject {
28public:
29    GateRegion(Chunk* chunk) : gateList_(chunk), preds_(chunk),
30        succs_(chunk), dominatedRegions_(chunk) {}
31    ~GateRegion() = default;
32
33    void AddGate(GateRef gate)
34    {
35        gateList_.emplace_back(gate);
36    }
37
38    void AddSucc(GateRegion *to)
39    {
40        succs_.emplace_back(to);
41        to->preds_.emplace_back(this);
42    }
43
44    void SetVisited(GateAccessor& acc)
45    {
46        acc.SetMark(state_, MarkCode::VISITED);
47    }
48
49    void SetFinished(GateAccessor& acc)
50    {
51        acc.SetMark(state_, MarkCode::FINISHED);
52    }
53
54    bool IsUnvisited(GateAccessor& acc) const
55    {
56        return acc.GetMark(state_) == MarkCode::NO_MARK;
57    }
58
59    bool IsVisited(GateAccessor& acc) const
60    {
61        return acc.GetMark(state_) == MarkCode::VISITED;
62    }
63
64    bool IsFinished(GateAccessor& acc) const
65    {
66        return acc.GetMark(state_) == MarkCode::FINISHED;
67    }
68
69    bool IsLoopHead() const
70    {
71        return stateKind_ == StateKind::LOOP_HEAD;
72    }
73
74    GateRef GetState() const
75    {
76        return state_;
77    }
78
79    void SetDead()
80    {
81        stateKind_ = StateKind::DEAD;
82    }
83
84    bool IsDead() const
85    {
86        return stateKind_ == StateKind::DEAD;
87    }
88
89    bool IsSimple(GateAccessor *acc) const;
90
91    bool HasComplexOuts() const
92    {
93        return succs_.size() > 1;
94    }
95
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
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
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
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
138    void AddGates(ChunkVector<GateRef>& gates)
139    {
140        gateList_.insert(gateList_.end(), gates.begin(), gates.end());
141    }
142
143    ChunkVector<GateRef>& GetGates()
144    {
145        return gateList_;
146    }
147
148    ChunkVector<GateRegion*>& GetPreds()
149    {
150        return preds_;
151    }
152
153    size_t GetId() const
154    {
155        return id_;
156    }
157
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
169    void SetLoopNumber(int32_t loopNumber)
170    {
171        loopNumber_ = static_cast<int32_t>(loopNumber);
172    }
173
174    int32_t GetLoopNumber() const
175    {
176        return static_cast<int32_t>(loopNumber_);
177    }
178
179    bool HasLoopNumber() const
180    {
181        return loopNumber_ >= 0;
182    }
183
184    GateRegion* GetDominator() const
185    {
186        return iDominator_;
187    }
188
189    ChunkVector<GateRegion*>& GetDominatedRegions()
190    {
191        return dominatedRegions_;
192    }
193
194    int32_t GetDepth() const
195    {
196        return depth_;
197    }
198
199    void SetLoopIndex(int32_t loopIndex)
200    {
201        loopIndex_ = loopIndex;
202    }
203
204    int32_t GetLoopIndex() const
205    {
206        return loopIndex_;
207    }
208
209    void SetLoopDepth(int32_t loopDepth)
210    {
211        loopDepth_ = loopDepth;
212    }
213
214    int32_t GetLoopDepth() const
215    {
216        return loopDepth_;
217    }
218
219private:
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
250class GraphLinearizer {
251public:
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)
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
272    GateRef GetStateOfSchedulableGate(GateRef gate) const
273    {
274        return GateToRegion(gate)->GetState();
275    }
276
277    bool enableLiteCG() const
278    {
279        return enableLiteCG_;
280    }
281
282private:
283    enum class ScheduleModel { LIR, JS_OPCODE };
284    enum class ScheduleState { NONE, FIXED, SELECTOR, SCHEDELABLE };
285    struct GateInfo {
286        GateInfo(GateRegion* region) : region(region) {}
287        GateRegion* region {nullptr};
288        GateRegion* upperBound {nullptr};
289        size_t schedulableUseCount {0};
290        ScheduleState state_ {ScheduleState::NONE};
291
292        bool IsSchedulable() const
293        {
294            return state_ == ScheduleState::SCHEDELABLE;
295        }
296
297        bool IsFixed() const
298        {
299            return state_ == ScheduleState::FIXED || IsSelector();
300        }
301
302        bool IsSelector() const
303        {
304            return state_ == ScheduleState::SELECTOR;
305        }
306
307        bool IsNone() const
308        {
309            return state_ == ScheduleState::NONE;
310        }
311    };
312
313    bool IsLogEnabled() const
314    {
315        return enableLog_;
316    }
317
318    const std::string& GetMethodName() const
319    {
320        return methodName_;
321    }
322
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
334    GateInfo& GetGateInfo(GateRef gate)
335    {
336        auto id = acc_.GetId(gate);
337        ASSERT(id < gateIdToGateInfo_.size());
338        return gateIdToGateInfo_[id];
339    }
340
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
348    GateRegion* GateToRegion(GateRef gate) const
349    {
350        const GateInfo& info = GetGateInfo(gate);
351        return info.region;
352    }
353
354    GateRegion* GateToUpperBound(GateRef gate) const
355    {
356        const GateInfo& info = GetGateInfo(gate);
357        return info.upperBound;
358    }
359
360    GateRegion* GetEntryRegion() const
361    {
362        ASSERT(!regionList_.empty());
363        return regionList_[0];
364    }
365
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
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
395    void BindGate(GateRef gate, GateRegion* region)
396    {
397        if (UNLIKELY(region == nullptr)) {
398            return;
399        }
400        GateInfo& info = GetGateInfo(gate);
401        info.region = region;
402        region->AddGate(gate);
403    }
404
405    bool IsScheduled(GateRef gate) const
406    {
407        GateRegion* region = GateToRegion(gate);
408        return region != nullptr;
409    }
410
411    bool HasLoop() const
412    {
413        return loopNumber_ != 0;
414    }
415
416    void Reset()
417    {
418        gateIdToGateInfo_.clear();
419        regionList_.clear();
420        regionRootList_.clear();
421        scheduleUpperBound_ = false;
422        model_ = ScheduleModel::LIR;
423        loopNumber_ = 0;
424    }
425
426    void EnableScheduleUpperBound()
427    {
428        scheduleUpperBound_ = true;
429    }
430
431    void SetScheduleJSOpcode()
432    {
433        model_ = ScheduleModel::JS_OPCODE;
434    }
435
436    bool IsSchedueLIR() const
437    {
438        return model_ == ScheduleModel::LIR;
439    }
440
441    LoopInfo* GetLoopInfo(GateRegion *region)
442    {
443        auto loopIndex = region->GetLoopIndex();
444        if (loopIndex >= 0) {
445            ASSERT(static_cast<size_t>(loopIndex) <= loops_.size());
446            return &loops_[loopIndex];
447        }
448        return nullptr;
449    }
450
451    size_t OptimizeCFG();
452    size_t OptimizeControls(GateRegion *region);
453    void MoveAndClear(GateRegion *from, GateRegion *to);
454    void PrintGraph(const char* title);
455
456    bool enableLog_ {false};
457    bool scheduleUpperBound_ {false};
458    ScheduleModel model_ {ScheduleModel::LIR};
459    std::string methodName_;
460    Chunk* chunk_ {nullptr};
461    Circuit* circuit_ {nullptr};
462    size_t loopNumber_ {0};
463
464    GateAccessor acc_;
465    ChunkVector<GateInfo> gateIdToGateInfo_;
466    ChunkVector<GateRegion*> regionList_;
467    ChunkVector<GateRef> regionRootList_;
468    ChunkVector<LoopInfo> loops_;
469
470    bool onlyBB_ {false}; // dont schedule
471    bool loopInvariantCodeMotion_ {false};
472    bool enableLiteCG_ {false};
473    friend class ArrayBoundsCheckElimination;
474    friend class StringBuilderOptimizer;
475    friend class CFGBuilder;
476    friend class GateScheduler;
477    friend class ImmediateDominatorsGenerator;
478    friend class LoopInfoBuilder;
479    friend class StateSplitLinearizer;
480    friend class InductionVariableAnalysis;
481};
482};  // namespace panda::ecmascript::kungfu
483
484#endif  // ECMASCRIPT_COMPILER_GRAPH_LINEARIZER_H
485