• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2021-2024 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 COMPILER_ANALYSIS_ESCAPE_H
17 #define COMPILER_ANALYSIS_ESCAPE_H
18 
19 #include <algorithm>
20 #include <variant>
21 
22 #include "compiler_options.h"
23 #include "optimizer/ir/constants.h"
24 #include "optimizer/ir/graph.h"
25 #include "optimizer/ir/graph_visitor.h"
26 #include "optimizer/pass.h"
27 #include "optimizer/analysis/loop_analyzer.h"
28 #include "optimizer/ir/runtime_interface.h"
29 #include "mem/arena_allocator.h"
30 #include "utils/bit_vector.h"
31 #include "compiler_logger.h"
32 #include "utils/logger.h"
33 
34 namespace ark::compiler {
35 using FieldId = uint64_t;
36 using InstId = uint32_t;
37 using BlockId = uint32_t;
38 using StateId = uint32_t;
39 using FieldPtr = RuntimeInterface::FieldPtr;
40 using ClassPtr = RuntimeInterface::ClassPtr;
41 
42 class VirtualState;
43 class BasicBlockState;
44 class PhiState;
45 class ScalarReplacement;
46 class ZeroInst;
47 struct Index;
48 
49 using StateOwner = std::variant<Inst *, PhiState *, const ZeroInst *>;
50 using MaterializationSite = std::variant<Inst *, BasicBlock *>;
51 using Field = std::variant<FieldPtr, Index>;
52 
53 struct Index {
54     ClassPtr klass;  // NOLINT(misc-non-private-member-variables-in-classes)
55     uint64_t index;  // NOLINT(misc-non-private-member-variables-in-classes)
56 
57     bool operator==(const Index &other) const
58     {
59         return klass == other.klass && index == other.index;
60     }
61 
62     bool operator<(const Index &other) const
63     {
64         return klass < other.klass || (klass == other.klass && index < other.index);
65     }
66 };
67 
68 struct FieldComporator {
operatorFieldComporator69     bool operator()(const Field &field1, const Field &field2) const
70     {
71         return GetUniqVal(field1) < GetUniqVal(field2);
72     }
73 
74 private:
GetUniqValFieldComporator75     uint64_t GetUniqVal(const Field &field) const
76     {
77         if (std::holds_alternative<FieldPtr>(field)) {
78             return reinterpret_cast<uint64_t>(std::get<FieldPtr>(field));
79         }
80         auto index = std::get<Index>(field);
81         // NOLINTNEXTLINE(readability-magic-numbers)
82         return (reinterpret_cast<uint64_t>(index.klass) << 32U) | index.index;
83     }
84 };
85 
86 // NOLINTNEXTLINE(fuchsia-multiple-inheritance)
87 class EscapeAnalysis : public Optimization, public GraphVisitor {
88 public:
89     static constexpr StateId MATERIALIZED_ID = 0;
90 
EscapeAnalysis(Graph * graph)91     explicit EscapeAnalysis(Graph *graph)
92         : Optimization(graph),
93           blockStates_(graph->GetLocalAllocator()->Adapter()),
94           aliases_(graph->GetLocalAllocator()->Adapter()),
95           materializationInfo_(graph->GetLocalAllocator()->Adapter()),
96           phis_(graph->GetLocalAllocator()->Adapter()),
97           saveStateInfo_(graph->GetLocalAllocator()->Adapter()),
98           virtualizableAllocations_(graph->GetLocalAllocator()->Adapter()),
99           mergeProcessor_(this),
100           liveIns_(graph)
101     {
102     }
103 
104     NO_MOVE_SEMANTIC(EscapeAnalysis);
105     NO_COPY_SEMANTIC(EscapeAnalysis);
106     ~EscapeAnalysis() override = default;
107 
108     bool RunImpl() override;
109 
GetPassName()110     const char *GetPassName() const override
111     {
112         return "EscapeAnalysis";
113     }
114 
IsEnable()115     bool IsEnable() const override
116     {
117         return g_options.IsCompilerScalarReplacement();
118     }
119 
IsAllocInst(Inst * inst)120     static bool IsAllocInst(Inst *inst)
121     {
122         return inst->GetOpcode() == Opcode::NewObject || inst->GetOpcode() == Opcode::NewArray;
123     }
124 // NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
125 #define DEFINE_VISIT(InstName)                                   \
126     static void Visit##InstName(GraphVisitor *v, Inst *inst)     \
127     {                                                            \
128         static_cast<EscapeAnalysis *>(v)->Visit##InstName(inst); \
129     }
130 
131 // NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
132 #define DEFINE_VISIT_WITH_CALLBACK(InstName, Callback)       \
133     static void Visit##InstName(GraphVisitor *v, Inst *inst) \
134     {                                                        \
135         static_cast<EscapeAnalysis *>(v)->Callback(inst);    \
136     }
137 
138     DEFINE_VISIT(NewObject);
139     DEFINE_VISIT(NewArray);
140     DEFINE_VISIT(LoadObject);
141     DEFINE_VISIT(LoadArray);
142     DEFINE_VISIT(StoreObject);
143     DEFINE_VISIT(StoreArray);
144     DEFINE_VISIT(NullCheck);
145     DEFINE_VISIT(SaveState);
146     DEFINE_VISIT(SafePoint);
147     // NOTE(schernykh): support it
148     // DEFINE_VISIT(SaveStateDeoptimize)
149     DEFINE_VISIT(GetInstanceClass);
150 
151     DEFINE_VISIT_WITH_CALLBACK(Deoptimize, MaterializeDeoptSaveState);
152     DEFINE_VISIT_WITH_CALLBACK(DeoptimizeIf, MaterializeDeoptSaveState);
153     DEFINE_VISIT_WITH_CALLBACK(DeoptimizeCompare, MaterializeDeoptSaveState);
154     DEFINE_VISIT_WITH_CALLBACK(DeoptimizeCompareImm, MaterializeDeoptSaveState);
155     DEFINE_VISIT_WITH_CALLBACK(LoadAndInitClass, VisitSaveStateUser);
156     DEFINE_VISIT_WITH_CALLBACK(LoadClass, VisitSaveStateUser);
157 
158 #undef DEFINE_VISIT
159 #undef DEFINE_VISIT_WITH_CALLBACK
160 
VisitCallStatic(GraphVisitor * v,Inst * inst)161     static void VisitCallStatic([[maybe_unused]] GraphVisitor *v, [[maybe_unused]] Inst *inst)
162     {
163         static_cast<EscapeAnalysis *>(v)->VisitCall(inst->CastToCallStatic());
164     }
VisitCallVirtual(GraphVisitor * v,Inst * inst)165     static void VisitCallVirtual([[maybe_unused]] GraphVisitor *v, [[maybe_unused]] Inst *inst)
166     {
167         static_cast<EscapeAnalysis *>(v)->VisitCall(inst->CastToCallVirtual());
168     }
VisitCompare(GraphVisitor * v,Inst * inst)169     static void VisitCompare([[maybe_unused]] GraphVisitor *v, [[maybe_unused]] Inst *inst)
170     {
171         static_cast<EscapeAnalysis *>(v)->VisitCmpRef(inst, inst->CastToCompare()->GetCc());
172     }
VisitIf(GraphVisitor * v,Inst * inst)173     static void VisitIf([[maybe_unused]] GraphVisitor *v, [[maybe_unused]] Inst *inst)
174     {
175         static_cast<EscapeAnalysis *>(v)->VisitCmpRef(inst, inst->CastToIf()->GetCc());
176     }
VisitPhi(GraphVisitor * v,Inst * inst)177     static void VisitPhi([[maybe_unused]] GraphVisitor *v, [[maybe_unused]] Inst *inst)
178     {
179         // Phi's handled during block's state merge
180     }
VisitReturnInlined(GraphVisitor * v,Inst * inst)181     static void VisitReturnInlined([[maybe_unused]] GraphVisitor *v, [[maybe_unused]] Inst *inst)
182     {
183         // do nothing
184     }
185     // by default all ref-input are materialized and materialized state is recorded for ref-output
VisitDefault(Inst * inst)186     void VisitDefault([[maybe_unused]] Inst *inst) override
187     {
188         VisitSaveStateUser(inst);
189         Materialize(inst);
190     }
191     void VisitAllocation(Inst *inst);
192 
GetBlocksToVisit()193     const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override
194     {
195         UNREACHABLE();
196     }
197 
198     // only for testing
RelaxClassRestrictions()199     void RelaxClassRestrictions()
200     {
201         relaxClassRestrictions_ = true;
202     }
203 
204 #include "optimizer/ir/visitor.inc"
205 private:
206     static constexpr InstId ZERO_INST_ID = std::numeric_limits<InstId>::max() - 1U;
207     static constexpr size_t MAX_NESTNESS = 5;
208 
209     class MergeProcessor {
210     public:
MergeProcessor(EscapeAnalysis * parent)211         explicit MergeProcessor(EscapeAnalysis *parent)
212             : parent_(parent),
213               fieldsMergeBuffer_(parent->GetLocalAllocator()->Adapter()),
214               statesMergeBuffer_(parent->GetLocalAllocator()->Adapter()),
215               allFields_(parent->GetLocalAllocator()->Adapter()),
216               pendingInsts_(parent->GetLocalAllocator()->Adapter())
217         {
218         }
219         ~MergeProcessor() = default;
220         NO_COPY_SEMANTIC(MergeProcessor);
221         NO_MOVE_SEMANTIC(MergeProcessor);
222 
223         // Compute initial state of a block by merging states of its predecessors.
224         void MergeStates(BasicBlock *block);
225 
226     private:
227         EscapeAnalysis *parent_;
228         ArenaVector<StateOwner> fieldsMergeBuffer_;
229         ArenaVector<StateOwner> statesMergeBuffer_;
230         ArenaVector<Field> allFields_;
231         ArenaVector<StateOwner> pendingInsts_;
232 
233         bool MergeFields(BasicBlock *block, BasicBlockState *blockState, StateId stateToMerge, VirtualState *vstate,
234                          ArenaVector<StateOwner> &mergeQueue);
235         bool MergeState(StateOwner inst, BasicBlock *block, BasicBlockState *newState);
236         void CheckStatesAndInsertIntoBuffer(StateOwner inst, BasicBlock *block);
237         void MaterializeObjectsAtTheBeginningOfBlock(BasicBlock *block);
238         void CollectInstructionsToMerge(BasicBlock *block);
239         void ProcessPhis(BasicBlock *block, BasicBlockState *newState);
240     };
241 
242     class LiveInAnalysis {
243     public:
LiveInAnalysis(Graph * graph)244         explicit LiveInAnalysis(Graph *graph)
245             : graph_(graph),
246               liveIn_(graph_->GetLocalAllocator()->Adapter()),
247               allInsts_(graph_->GetLocalAllocator()->Adapter())
248         {
249         }
250         ~LiveInAnalysis() = default;
251         NO_COPY_SEMANTIC(LiveInAnalysis);
252         NO_MOVE_SEMANTIC(LiveInAnalysis);
253 
254         // Compute set of ref-typed instructions live at the beginning of each
255         // basic blocks. Return false if graph don't contain NewObject instructions.
256         bool Run();
257 
258         template <typename Callback>
VisitAlive(const BasicBlock * block,Callback && cb)259         void VisitAlive(const BasicBlock *block, Callback &&cb)
260         {
261             auto &liveIns = liveIn_[block->GetId()];
262             auto span = liveIns.GetContainerDataSpan();
263             for (size_t maskIdx = 0; maskIdx < span.size(); ++maskIdx) {
264                 auto mask = span[maskIdx];
265                 size_t maskOffset = 0;
266                 while (mask != 0) {
267                     auto offset = static_cast<size_t>(Ctz(mask));
268                     mask = (mask >> offset) >> 1U;
269                     maskOffset += offset;
270                     size_t liveIdx = maskIdx * sizeof(mask) * BITS_PER_BYTE + maskOffset;
271                     ++maskOffset;  // consume current bit
272                     ASSERT(liveIdx < allInsts_.size());
273                     ASSERT(allInsts_[liveIdx] != nullptr);
274                     cb(allInsts_[liveIdx]);
275                 }
276             }
277         }
278 
279     private:
280         Graph *graph_;
281         // Live ins evaluation requires union of successor's live ins,
282         // bit vector's union works faster than set's union.
283         ArenaVector<ArenaBitVector> liveIn_;
284         ArenaVector<Inst *> allInsts_;
285 
AddInst(Inst * inst)286         void AddInst(Inst *inst)
287         {
288             if (inst->GetId() >= allInsts_.size()) {
289                 allInsts_.resize(inst->GetId() + 1);
290             }
291             allInsts_[inst->GetId()] = inst;
292         }
293 
294         void ProcessBlock(BasicBlock *block);
295     };
296 
297     Marker visited_ {UNDEF_MARKER};
298     ArenaVector<BasicBlockState *> blockStates_;
299     ArenaMap<Inst *, StateOwner> aliases_;
300     // list of instructions with corresponding virtual state values bound
301     // to a save state or an allocation site
302     ArenaUnorderedMap<MaterializationSite, ArenaMap<Inst *, VirtualState *>> materializationInfo_;
303     ArenaVector<ArenaMap<Field, PhiState *, FieldComporator>> phis_;
304     ArenaUnorderedMap<Inst *, ArenaBitVector> saveStateInfo_;
305     ArenaSet<Inst *> virtualizableAllocations_;
306     MergeProcessor mergeProcessor_;
307     LiveInAnalysis liveIns_;
308     // 0 is materialized state
309     StateId stateId_ = MATERIALIZED_ID + 1;
310     bool virtualizationChanged_ {false};
311     bool relaxClassRestrictions_ {false};
312 
313     void VisitCmpRef(Inst *inst, ConditionCode cc);
314     void VisitSaveStateUser(Inst *inst);
315     void VisitCall(CallInst *inst);
316     void VisitNewObject(Inst *inst);
317     void VisitLoadObject(Inst *inst);
318     void VisitStoreObject(Inst *inst);
319     void VisitNewArray(Inst *inst);
320     void VisitStoreArray(Inst *inst);
321     void VisitLoadArray(Inst *inst);
322     void VisitNullCheck(Inst *inst);
323     void VisitSaveState(Inst *inst);
324     void VisitSaveStateDeoptimize(Inst *inst);
325     void VisitSafePoint(Inst *inst);
326     void VisitGetInstanceClass(Inst *inst);
327     void VisitBlockInternal(BasicBlock *block);
328     void HandleMaterializationSite(Inst *inst);
329 
330     void MaterializeDeoptSaveState(Inst *inst);
331 
332     void Initialize();
333     void PropagateLoadObjectsUpwards();
334     void CreateTemporaryLoads(Inst *phi);
335     bool FindVirtualizableAllocations();
336     bool AllPredecessorsVisited(const BasicBlock *block);
337 #ifndef NDEBUG
338     Marker removableLoads_ {UNDEF_MARKER};
339     bool EnsureLoadsRemoval();
340 #endif
341 
IsRefField(FieldPtr field)342     bool IsRefField(FieldPtr field) const
343     {
344         return IsReference(GetGraph()->GetRuntime()->GetFieldType(field));
345     }
346 
GetState(const BasicBlock * block)347     BasicBlockState *GetState(const BasicBlock *block) const
348     {
349         return blockStates_[block->GetId()];
350     }
351 
352     std::pair<PhiState *, bool> CreatePhi(BasicBlock *targetBlock, BasicBlockState *blockState, Field field,
353                                           ArenaVector<StateOwner> &inputs, VirtualState *vstate);
354     VirtualState *CreateVState(Inst *inst);
355     VirtualState *CreateVState(Inst *inst, StateId id);
356 
357     void MaterializeInBlock(StateOwner inst, BasicBlock *block);
358     void Materialize(StateOwner inst, BasicBlock *block);
359     void Materialize(StateOwner inst, Inst *before);
360     void Materialize(Inst *inst);
361     void RegisterMaterialization(MaterializationSite site, Inst *inst);
362     void RegisterVirtualObjectFieldsForMaterialization(Inst *ss);
363     bool RegisterFieldsMaterialization(Inst *site, VirtualState *state, BasicBlockState *blockState,
364                                        const ArenaMap<Inst *, VirtualState *> &states);
365 
366     bool ProcessBlock(BasicBlock *block, size_t depth = 0);
367     bool ProcessLoop(BasicBlock *header, size_t depth = 0);
368     void FillVirtualInputs(Inst *inst);
AddVirtualizableAllocation(Inst * inst)369     void AddVirtualizableAllocation(Inst *inst)
370     {
371         COMPILER_LOG(DEBUG, PEA) << "Candidate for virtualization: " << *inst;
372         virtualizableAllocations_.insert(inst);
373     }
RemoveVirtualizableAllocation(Inst * inst)374     void RemoveVirtualizableAllocation(Inst *inst)
375     {
376         virtualizableAllocations_.erase(inst);
377     }
378 
GetLocalAllocator()379     ArenaAllocator *GetLocalAllocator()
380     {
381         return GetGraph()->GetLocalAllocator();
382     }
383 
384     void DumpVStates();
385     void DumpMStates();
386     void DumpAliases();
387     void Dump();
388 };
389 
390 class ScalarReplacement {
391 public:
ScalarReplacement(Graph * graph,ArenaMap<Inst *,StateOwner> & aliases,ArenaVector<ArenaMap<Field,PhiState *,FieldComporator>> & phis,ArenaUnorderedMap<MaterializationSite,ArenaMap<Inst *,VirtualState * >> & materializationSites,ArenaUnorderedMap<Inst *,ArenaBitVector> & saveStateLiveness)392     ScalarReplacement(Graph *graph, ArenaMap<Inst *, StateOwner> &aliases,
393                       ArenaVector<ArenaMap<Field, PhiState *, FieldComporator>> &phis,
394                       ArenaUnorderedMap<MaterializationSite, ArenaMap<Inst *, VirtualState *>> &materializationSites,
395                       ArenaUnorderedMap<Inst *, ArenaBitVector> &saveStateLiveness)
396         : graph_(graph),
397           aliases_(aliases),
398           phis_(phis),
399           materializationSites_(materializationSites),
400           saveStateLiveness_(saveStateLiveness),
401           allocatedPhis_(graph_->GetLocalAllocator()->Adapter()),
402           materializedObjects_(graph_->GetLocalAllocator()->Adapter()),
403           removalQueue_(graph_->GetLocalAllocator()->Adapter())
404     {
405     }
406 
407     ~ScalarReplacement() = default;
408     NO_COPY_SEMANTIC(ScalarReplacement);
409     NO_MOVE_SEMANTIC(ScalarReplacement);
410 
411     void Apply(ArenaSet<Inst *> &candidates);
412 
413 private:
414     Graph *graph_;
415     ArenaMap<Inst *, StateOwner> &aliases_;
416     ArenaVector<ArenaMap<Field, PhiState *, FieldComporator>> &phis_;
417     ArenaUnorderedMap<MaterializationSite, ArenaMap<Inst *, VirtualState *>> &materializationSites_;
418     ArenaUnorderedMap<Inst *, ArenaBitVector> &saveStateLiveness_;
419 
420     ArenaMap<PhiState *, PhiInst *> allocatedPhis_;
421     ArenaMap<Inst *, ArenaVector<Inst *>> materializedObjects_;
422 
423     ArenaVector<Inst *> removalQueue_;
424     Marker removeInstMarker_ {UNDEF_MARKER};
425 
426     void ProcessRemovalQueue();
427     bool IsEnqueuedForRemoval(Inst *inst) const;
428     void EnqueueForRemoval(Inst *inst);
429     void UpdateAllocationUsers();
430     void UpdateSaveStates();
431     Inst *ResolveAllocation(Inst *inst, BasicBlock *block);
432     void ResolvePhiInputs();
433     void ReplaceAliases();
434     Inst *ResolveAlias(const StateOwner &alias, const Inst *inst);
435     Inst *CreateNewObject(Inst *originalInst, Inst *saveState);
436     Inst *CreateNewArray(Inst *originalInst, Inst *saveState);
437     void InitializeObject(Inst *alloc, Inst *instBefore, VirtualState *state);
438     void MaterializeObjects();
439     void Materialize(Inst *originalInst, Inst *ssAlloc, Inst *ssInit, VirtualState *state);
440     void MaterializeAtNewSaveState(Inst *site, ArenaMap<Inst *, VirtualState *> &state);
441     void MaterializeInEmptyBlock(BasicBlock *block, ArenaMap<Inst *, VirtualState *> &state);
442     void MaterializeAtExistingSaveState(SaveStateInst *saveState, ArenaMap<Inst *, VirtualState *> &state);
443     void CreatePhis();
444     SaveStateInst *CopySaveState(Inst *inst, VirtualState *except);
445     void PatchSaveStates();
446     void PatchSaveStatesInBlock(BasicBlock *block, ArenaVector<ArenaSet<Inst *>> &liveness);
447     void PatchSaveStatesInLoop(Loop *loop, ArenaSet<Inst *> &loopLiveIns, ArenaVector<ArenaSet<Inst *>> &liveness);
448     void FillLiveInsts(BasicBlock *block, ArenaSet<Inst *> &liveIns, ArenaVector<ArenaSet<Inst *>> &liveness);
449     void PatchSaveState(SaveStateInst *saveState, ArenaSet<Inst *> &liveInstructions);
450     void AddLiveInputs(Inst *inst, ArenaSet<Inst *> &liveIns);
451     CallInst *FindCallerInst(BasicBlock *target, Inst *start = nullptr);
452     void FixPhiInputTypes();
453     bool HasUsageOutsideBlock(Inst *inst, BasicBlock *initialBlock);
454 };
455 }  // namespace ark::compiler
456 
457 #endif  // COMPILER_ANALYSIS_ESCAPE_H
458