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_ARRAY_BOUNDS_CHECK_ELIMINATION_H
17#define ECMASCRIPT_COMPILER_ARRAY_BOUNDS_CHECK_ELIMINATION_H
18
19#include "ecmascript/compiler/circuit_builder.h"
20#include "ecmascript/compiler/mcr_gate_meta_data.h"
21#include "ecmascript/compiler/gate_accessor.h"
22#include "ecmascript/compiler/graph_linearizer.h"
23#include "ecmascript/compiler/pass_manager.h"
24#include "ecmascript/mem/chunk_containers.h"
25
26namespace panda::ecmascript::kungfu {
27class ArrayBoundsCheckElimination {
28public:
29    ArrayBoundsCheckElimination(Circuit *circuit, bool enableLog, const std::string& name, Chunk* chunk)
30        : acc_(circuit), bounds_(chunk), circuit_(circuit), builder_(circuit), chunk_(chunk), enableLog_(enableLog),
31        graphLinearizer_(circuit, enableLog, name, chunk, true, true), methodName_(name), indexCheckInfo_(chunk) {}
32
33    ~ArrayBoundsCheckElimination() = default;
34    void Run();
35
36private:
37    class Bound {
38    public:
39        Bound();
40        explicit Bound(GateRef v);
41        Bound(int lower, GateRef lowerGate, int upper, GateRef upperGate);
42        Bound(TypedBinOp op, GateRef gate, int constant);
43        ~Bound(){};
44
45        int Upper()
46        {
47            return upper_;
48        }
49
50        GateRef UpperGate()
51        {
52            return upperGate_;
53        }
54
55        int Lower()
56        {
57            return lower_;
58        }
59
60        GateRef LowerGate()
61        {
62            return lowerGate_;
63        }
64
65        bool HasUpper()
66        {
67            return upperGate_ != Circuit::NullGate() || upper_ < INT_MAX;
68        }
69
70        bool HasLower()
71        {
72            return lowerGate_ != Circuit::NullGate() || lower_ > INT_MIN;
73        }
74
75        void RemoveUpper()
76        {
77            upperGate_ = Circuit::NullGate();
78            upper_ = INT_MAX;
79        }
80
81        void RemoveLower()
82        {
83            lowerGate_ = Circuit::NullGate();
84            lower_ = INT_MIN;
85        }
86
87        bool IsSmaller(Bound *b)
88        {
89            if (b->LowerGate() != upperGate_) {
90                return false;
91            }
92            return upper_ < b->Lower();
93        }
94
95        Bound* Copy(Chunk *chunk)
96        {
97            return chunk->New<Bound>(lower_, lowerGate_, upper_, upperGate_);
98        }
99
100    private:
101        int upper_ = 0;
102        GateRef upperGate_ {Circuit::NullGate()};
103        int lower_ = 0;
104        GateRef lowerGate_ {Circuit::NullGate()};
105
106        friend ArrayBoundsCheckElimination;
107    };
108
109    bool IsLogEnabled() const
110    {
111        return enableLog_;
112    }
113
114    const std::string& GetMethodName() const
115    {
116        return methodName_;
117    }
118
119    typedef ChunkVector<Bound*> BoundStack;
120    typedef ChunkVector<BoundStack*> BoundMap;
121    typedef ChunkVector<int> IntegerStack;
122    typedef ChunkVector<GateRef> GateLists;
123
124    void AddAccessIndexedInfo(GateLists &indices, GateRef gate, int idx, GateRef indexCheck);
125    void AddIfCondition(IntegerStack &pushed, GateRef x, GateRef y, TypedBinOp op);
126    Bound *AndOp(Bound *bound, Bound *b);
127    Bound *OrOp(Bound *bound, Bound *b);
128    bool Contain(GateLists &gateLists, GateRef gate);
129    void CalcBounds(GateRegion *block, GateRegion *loopHeader);
130    bool CheckLoop(GateRef array, GateRef lowerGate, int lower, GateRef upperGate, int upper);
131    GateRef FindBoundGate(GateRef gate);
132    void InBlockMotion(GateLists &indexChecked, GateLists &arrays);
133    bool InLoop(GateRef loopHeader, GateRef gate);
134    bool IsArrayLength(GateRef gate);
135    bool LoopInvariant(GateRegion *loopHeader, GateRef gate);
136    void UpdateBound(IntegerStack &pushed, GateRef gate, Bound *bound);
137    void UpdateBound(IntegerStack &pushed, GateRef x, TypedBinOp op, GateRef y, int constValue);
138    void ProcessIndexCheck(GateRegion *loopHeader, GateRef gate);
139    void RemoveIndexCheck(GateRef gate);
140    void CopyStateInAndDependIn(GateRef &stateIn, GateRef &dependIn, GateRef insertAfter);
141    void LoopInvariantMotionForIndexCheck(GateRef array, GateRef length, GateRef lengthMetaData,
142        GateRef lowerGate, int lower, GateRef upperGate, int upper, bool isTypedArray);
143    bool GetInstrAndConstValueFromUnaryOp(GateRef gate, GateRef &other, int& value);
144    bool GetInstrAndConstValueFromBinaryOp(GateRef gate, GateRef &other, int& value);
145    void GetInstrAndConstValueFromOp(GateRef gate, GateRef &instrValue, int& constValue);
146    Bound *GetBound(GateRef gate);
147    Bound *DoConstant(GateRef gate);
148    Bound *DoBinaryArithmeticOp(GateRef gate);
149    Bound *DoUnaryArithmeticOp(GateRef gate);
150    Bound *DoPhi(GateRef gate);
151    void SetBound(GateRef gate, Bound *bound);
152    void ProcessIf(IntegerStack &pushed, GateRegion *parent, OpCode cond);
153    bool InArrayBound(Bound *bound, GateRef length, GateRef array);
154    Bound *VisitGate(GateRef gate);
155
156    void ReplaceIn(GateRef stateIn, GateRef dependIn, GateRef newGate);
157
158    GateRef Predicate(GateRef left, TypedBinOp cond, GateRef right);
159    GateRef PredicateCmpWithConst(GateRef left, TypedBinOp cond, int right);
160    GateRef PredicateAdd(GateRef left, int leftConst, TypedBinOp cond, GateRef right);
161    GateRef PredicateAddCmpWithConst(GateRef left, int leftConst, TypedBinOp cond, int right);
162
163    GateAccessor acc_;
164    BoundMap bounds_;
165    Circuit *circuit_ {nullptr};
166    CircuitBuilder builder_;
167    Chunk *chunk_ {nullptr};
168    bool enableLog_ {false};
169    GraphLinearizer graphLinearizer_;
170    std::string methodName_;
171
172    class IndexCheckInfo {
173    public:
174        IndexCheckInfo(Chunk* chunk): list_(chunk) {}
175        GateLists list_;
176        int min_ {0};
177        int max_ {0};
178    };
179    typedef ChunkVector<IndexCheckInfo*> IndexCheckInfoList;
180    IndexCheckInfoList indexCheckInfo_;
181};
182}
183#endif