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