• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2021-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 #include "optimizer/ir/analysis.h"
17 #include "optimizer/ir/basicblock.h"
18 #include "optimizer/ir/graph.h"
19 #include "optimizer/analysis/alias_analysis.h"
20 #include "compiler_logger.h"
21 
22 /**
23  * See  "Efficient Field-sensitive pointer analysis for C" by "David J. Pearce
24  * and Paul H. J. Kelly and Chris Hankin
25  *
26  * We treat each IR Inst as a constraint that may be applied to a set of
27  * aliases of some virtual register.  Virtual registers are used as constraint
28  * variables as well.
29  *
30  * In order to solve the system of set constraints, the following is done:
31  *
32  * 1. Each constraint variable x has a solution set associated with it, Sol(x).
33  * Implemented through AliasAnalysis::points_to_ that contains mapping of
34  * virtual register to possible aliases.
35  *
36  * 2. Constraints are separated into direct, copy.
37  *
38  * - Direct constraints are constraints that require no extra processing, such
39  * as P = &Q.
40  *
41  * - Copy constraints are those of the form P = Q.  Such semantic can be
42  * obtained through NullCheck, Mov, and Phi instructions.
43  *
44  * 3. All direct constraints of the form P = &Q are processed, such that Q is
45  * added to Sol(P).
46  *
47  * 4. A directed graph is built out of the copy constraints.  Each constraint
48  * variable is a node in the graph, and an edge from Q to P is added for each
49  * copy constraint of the form P = Q.
50  *
51  * 5. The graph is then walked, and solution sets are propagated along the copy
52  * edges, such that an edge from Q to P causes Sol(P) <- Sol(P) union Sol(Q).
53  *
54  * 6. The process of walking the graph is iterated until no solution sets
55  * change.
56  *
57  * To add new instructions to alias analysis please consider following:
58  *     - IsLocalAlias method: to add instructions that create new object
59  *     - ParseInstruction method: to add a new instruction alias analysis works for
60  *     - AliasAnalysis class: to add a visitor for a new instruction that should be analyzed
61  *
62  * NOTE(Evgenii Kudriashov): Prior to walking the graph in steps 5 and 6, We
63  * need to perform static cycle elimination on the constraint graph, as well as
64  * off-line variable substitution.
65  *
66  * NOTE(Evgenii Kudriashov): To add flow-sensitivity the "Flow-sensitive
67  * pointer analysis for millions of lines of code" by Ben Hardekopf and Calvin
68  * Lin may be considered.
69  *
70  * NOTE(Evgenii Kudriashov): After implementing VRP and SCEV the "Loop-Oriented
71  * Array- and Field-Sensitive Pointer Analysis for Automatic SIMD
72  * Vectorization" by Yulei Sui, Xiaokang Fan, Hao Zhou, and Jingling Xue may be
73  * considered to add advanced analysis of array indices.
74  */
75 
76 namespace panda::compiler {
77 
AliasAnalysis(Graph * graph)78 AliasAnalysis::AliasAnalysis(Graph *graph) : Analysis(graph), pointsTo_(graph->GetAllocator()->Adapter()) {}
79 
GetBlocksToVisit() const80 const ArenaVector<BasicBlock *> &AliasAnalysis::GetBlocksToVisit() const
81 {
82     return GetGraph()->GetBlocksRPO();
83 }
84 
RunImpl()85 bool AliasAnalysis::RunImpl()
86 {
87     Init();
88 
89     VisitGraph();
90 
91     // Initialize solution sets
92     for (auto pair : *direct_) {
93         auto it = pointsTo_.try_emplace(pair.first, GetGraph()->GetAllocator()->Adapter());
94         ASSERT(pair.first.GetBase() == nullptr || pair.first.GetBase()->GetOpcode() != Opcode::NullCheck);
95         ASSERT(pair.second.GetBase() == nullptr || pair.second.GetBase()->GetOpcode() != Opcode::NullCheck);
96         it.first->second.insert(pair.second);
97     }
98 
99     // Build graph
100     for (auto pair : *copy_) {
101         auto it = chains_->try_emplace(pair.first, GetGraph()->GetLocalAllocator()->Adapter());
102         ASSERT(pair.first.GetBase() == nullptr || pair.first.GetBase()->GetOpcode() != Opcode::NullCheck);
103         ASSERT(pair.second.GetBase() == nullptr || pair.second.GetBase()->GetOpcode() != Opcode::NullCheck);
104         it.first->second.push_back(pair.second);
105     }
106 
107     SolveConstraints();
108 
109 #ifndef NDEBUG
110     if (CompilerLogger::IsComponentEnabled(CompilerLoggerComponents::ALIAS_ANALYSIS)) {
111         std::ostringstream out;
112         DumpChains(&out);
113         Dump(&out);
114         COMPILER_LOG(DEBUG, ALIAS_ANALYSIS) << out.str();
115     }
116 #endif
117     return true;
118 }
119 
Init()120 void AliasAnalysis::Init()
121 {
122     auto allocator = GetGraph()->GetLocalAllocator();
123     chains_ = allocator->New<PointerMap<ArenaVector<Pointer>>>(allocator->Adapter());
124     direct_ = allocator->New<PointerPairVector>(allocator->Adapter());
125     copy_ = allocator->New<PointerPairVector>(allocator->Adapter());
126     inputsSet_ = allocator->New<ArenaSet<Inst *>>(allocator->Adapter());
127     ASSERT(chains_ != nullptr);
128     ASSERT(direct_ != nullptr);
129     ASSERT(copy_ != nullptr);
130     ASSERT(inputsSet_ != nullptr);
131     pointsTo_.clear();
132 }
133 
Dump(std::ostream * out) const134 void Pointer::Dump(std::ostream *out) const
135 {
136     switch (type_) {
137         case OBJECT:
138             (*out) << "v" << base_->GetId();
139             break;
140         case STATIC_FIELD:
141             (*out) << "SF #" << imm_;
142             break;
143         case POOL_CONSTANT:
144             (*out) << "PC #" << imm_;
145             break;
146         case OBJECT_FIELD:
147             (*out) << "v" << base_->GetId() << " #" << imm_;
148             break;
149         case ARRAY_ELEMENT:
150             (*out) << "v" << base_->GetId() << "[";
151             if (idx_ != nullptr) {
152                 (*out) << "v" << idx_->GetId();
153                 if (imm_ != 0) {
154                     (*out) << "+" << imm_;
155                 }
156             } else {
157                 (*out) << imm_;
158             }
159             (*out) << "]";
160             break;
161         case DICTIONARY_ELEMENT:
162             (*out) << "v" << base_->GetId() << "[";
163             (*out) << "v" << idx_->GetId();
164             if (imm_ != 0) {
165                 (*out) << "#NAME";
166             } else {
167                 (*out) << "#INDEX";
168             }
169             (*out) << "]";
170             break;
171         default:
172             UNREACHABLE();
173     }
174     if (local_) {
175         (*out) << "(local)";
176     }
177     if (volatile_) {
178         (*out) << "(v)";
179     }
180 }
181 
PointerLess(const Pointer & lhs,const Pointer & rhs)182 static bool PointerLess(const Pointer &lhs, const Pointer &rhs)
183 {
184     if (lhs.GetBase() == rhs.GetBase()) {
185         return lhs.GetImm() < rhs.GetImm();
186     }
187     if (lhs.GetBase() == nullptr) {
188         return true;
189     }
190     if (rhs.GetBase() == nullptr) {
191         return false;
192     }
193     return lhs.GetBase()->GetId() < rhs.GetBase()->GetId();
194 }
195 
GetDynamicAccessPointer(Inst * inst,Inst * base,DynObjectAccessType type,DynObjectAccessMode mode)196 static Pointer GetDynamicAccessPointer(Inst *inst, Inst *base, DynObjectAccessType type, DynObjectAccessMode mode)
197 {
198     if (type == DynObjectAccessType::UNKNOWN || mode == DynObjectAccessMode::UNKNOWN) {
199         return Pointer::CreateObject(base);
200     }
201 
202     Inst *idx = inst->GetDataFlowInput(1);
203     uint64_t imm = 0;
204     if (type == DynObjectAccessType::BY_NAME) {
205         ASSERT_DO(mode != DynObjectAccessMode::ARRAY,
206                   (std::cerr << "Unexpected access type BY_NAME for access mode ARRAY: ", inst->Dump(&std::cerr)));
207         imm = UINT64_MAX;
208     } else {
209         ASSERT_DO(type == DynObjectAccessType::BY_INDEX,
210                   (std::cerr << "Unsupported dynamic access type in alias analysis: ", inst->Dump(&std::cerr)));
211     }
212     if (mode == DynObjectAccessMode::ARRAY) {
213         return Pointer::CreateArrayElement(base, idx, imm);
214     }
215     ASSERT_DO(mode == DynObjectAccessMode::DICTIONARY,
216               (std::cerr << "Unsupported dynamic access mode in alias analysis: ", inst->Dump(&std::cerr)));
217     return Pointer::CreateDictionaryElement(base, idx, imm);
218 }
219 
DumpChains(std::ostream * out) const220 void AliasAnalysis::DumpChains(std::ostream *out) const
221 {
222     ArenaVector<Pointer> sortedKeys(GetGraph()->GetLocalAllocator()->Adapter());
223     for (auto &pair : *chains_) {
224         sortedKeys.push_back(pair.first);
225     }
226     std::sort(sortedKeys.begin(), sortedKeys.end(), PointerLess);
227 
228     (*out) << "The chains are the following:" << std::endl;
229     for (auto &p : sortedKeys) {
230         (*out) << "\t";
231         p.Dump(out);
232         (*out) << ": {";
233 
234         // Sort by instruction ID to add more readability to logs
235         ArenaVector<Pointer> sorted(chains_->at(p), GetGraph()->GetLocalAllocator()->Adapter());
236         std::sort(sorted.begin(), sorted.end(), PointerLess);
237         auto edge = sorted.begin();
238         if (edge != sorted.end()) {
239             edge->Dump(out);
240             while (++edge != sorted.end()) {
241                 (*out) << ", ";
242                 edge->Dump(out);
243             }
244         }
245         (*out) << "}" << std::endl;
246     }
247 }
248 
Dump(std::ostream * out) const249 void AliasAnalysis::Dump(std::ostream *out) const
250 {
251     ArenaVector<Pointer> sortedKeys(GetGraph()->GetLocalAllocator()->Adapter());
252     for (auto &pair : pointsTo_) {
253         sortedKeys.push_back(pair.first);
254     }
255     std::sort(sortedKeys.begin(), sortedKeys.end(), PointerLess);
256 
257     (*out) << "The solution set is the following:" << std::endl;
258     for (auto &p : sortedKeys) {
259         (*out) << "\t";
260         p.Dump(out);
261         (*out) << ": {";
262 
263         // Sort by instruction ID to add more readability to logs
264         auto values = pointsTo_.at(p);
265         ArenaVector<Pointer> sorted(values.begin(), values.end(), GetGraph()->GetLocalAllocator()->Adapter());
266         std::sort(sorted.begin(), sorted.end(), PointerLess);
267         auto iter = sorted.begin();
268         if (iter != sorted.end()) {
269             iter->Dump(out);
270             while (++iter != sorted.end()) {
271                 (*out) << ", ";
272                 iter->Dump(out);
273             }
274         }
275         (*out) << "}" << std::endl;
276     }
277 }
278 
CheckInstAlias(Inst * mem1,Inst * mem2) const279 AliasType AliasAnalysis::CheckInstAlias(Inst *mem1, Inst *mem2) const
280 {
281     ASSERT(mem1->IsMemory() && mem2->IsMemory());
282     Pointer p1 = {};
283     Pointer p2 = {};
284 
285     if (!ParseInstruction(mem1, &p1) || !ParseInstruction(mem2, &p2)) {
286         return MAY_ALIAS;
287     }
288 
289     // Instructions with different types cannot alias each other. Handle
290     // difference only in numeric types for now.
291     if (IsTypeNumeric(mem1->GetType()) && IsTypeNumeric(mem2->GetType()) &&
292         GetTypeSize(mem1->GetType(), GetGraph()->GetArch()) != GetTypeSize(mem2->GetType(), GetGraph()->GetArch())) {
293         return NO_ALIAS;
294     }
295     // Instructions with a primitive type and the reference type cannot alias each other.
296     if ((IsTypeNumeric(mem1->GetType()) && mem2->IsReferenceOrAny()) ||
297         (IsTypeNumeric(mem2->GetType()) && mem1->IsReferenceOrAny())) {
298         return NO_ALIAS;
299     }
300 
301     return CheckMemAddress(p1, p2);
302 }
303 
CheckRefAlias(Inst * ref1,Inst * ref2) const304 AliasType AliasAnalysis::CheckRefAlias(Inst *ref1, Inst *ref2) const
305 {
306     ASSERT(ref1->IsReferenceOrAny());
307     ASSERT(ref2->IsReferenceOrAny());
308     return CheckMemAddress(Pointer::CreateObject(ref1), Pointer::CreateObject(ref2));
309 }
310 
CheckMemAddressEmptyIntersectionCase(const PointerSet & aliases1,const PointerSet & aliases2,const Pointer & p1,const Pointer & p2) const311 AliasType AliasAnalysis::CheckMemAddressEmptyIntersectionCase(const PointerSet &aliases1, const PointerSet &aliases2,
312                                                               const Pointer &p1, const Pointer &p2) const
313 {
314     // If at least one set of aliases consists of only local aliases then there is NO_ALIAS
315     auto isOuter = [](Pointer const &p) { return !p.IsLocal(); };
316     if (std::find_if(aliases1.begin(), aliases1.end(), isOuter) == aliases1.end() ||
317         std::find_if(aliases2.begin(), aliases2.end(), isOuter) == aliases2.end()) {
318         return NO_ALIAS;
319     }
320     // Different fields cannot alias each other even if they are not created locally
321     if (p1.GetType() == OBJECT_FIELD && !p1.HasSameOffset(p2)) {
322         return NO_ALIAS;
323     }
324     if (p1.GetType() == ARRAY_ELEMENT) {
325         auto equal = IsSameOffsets(p1.GetIdx(), p2.GetIdx());
326         // If it is known that indices are different OR Imm indices are different then there is
327         // no alias.  If they are both different we can't certainly say so.
328         if ((equal == Trilean::FALSE && p1.GetImm() == p2.GetImm()) ||
329             (equal == Trilean::TRUE && p1.GetImm() != p2.GetImm())) {
330             return NO_ALIAS;
331         }
332     }
333     if (p1.GetType() == DICTIONARY_ELEMENT) {
334         auto equal = IsSameOffsets(p1.GetIdx(), p2.GetIdx());
335         if (equal == Trilean::FALSE && p1.GetImm() == p2.GetImm()) {
336             return NO_ALIAS;
337         }
338     }
339     return MAY_ALIAS;
340 }
341 
342 /**
343  * We have 5 types of pointers: OBJECT, OBJECT_FIELD, POOL_CONSTANT,
344  * STATIC_FIELD and ARRAY_ELEMENT.  They correspond to groups of memory storing
345  * and loading instructions.  Assuming that these groups cannot load the same
346  * memory address (at IR level), it is true that different types of pointers
347  * cannot alias each other.
348  *
349  * Global pointers such as STATIC_FIELD and POOL_CONSTANT are checked through
350  * their unique TypeId.
351  *
352  * For OBJECT_FIELDs we look at objects they referenced to.  If they refer to
353  * the same objects then depending on TypeId they MUST_ALIAS or NO_ALIAS.  If
354  * the situation of the referenced objects is unclear then they MAY_ALIAS.
355  *
356  * The same is for ARRAY_ELEMENT.  Instead of TypeId we look at index and compare them.
357  *
358  * All function's arguments MAY_ALIAS each other.  Created objects in the
359  * function may not alias arguments.
360  */
CheckMemAddress(const Pointer & p1,const Pointer & p2) const361 AliasType AliasAnalysis::CheckMemAddress(const Pointer &p1, const Pointer &p2) const
362 {
363     if (p1.GetType() != p2.GetType()) {
364         return NO_ALIAS;
365     }
366 
367     if (p1.GetType() == STATIC_FIELD || p2.GetType() == STATIC_FIELD || p1.GetType() == POOL_CONSTANT ||
368         p2.GetType() == POOL_CONSTANT) {
369         if (p1.HasSameOffset(p2)) {
370             return MUST_ALIAS;
371         }
372         return NO_ALIAS;
373     }
374 
375     auto baseObj1 = Pointer::CreateObject(p1.GetBase());
376     auto baseObj2 = Pointer::CreateObject(p2.GetBase());
377     ASSERT_DO(pointsTo_.find(baseObj1) != pointsTo_.end(),
378               (std::cerr << "Undefined inst in AliasAnalysis: ", p1.GetBase()->Dump(&std::cerr)));
379     ASSERT_DO(pointsTo_.find(baseObj2) != pointsTo_.end(),
380               (std::cerr << "Undefined inst in AliasAnalysis: ", p2.GetBase()->Dump(&std::cerr)));
381     auto &aliases1 = pointsTo_.at(baseObj1);
382     auto &aliases2 = pointsTo_.at(baseObj2);
383     // Find the intersection
384     const Pointer *intersection = nullptr;
385     for (auto &alias : aliases1) {
386         if (aliases2.find(alias) != aliases2.end()) {
387             intersection = &alias;
388             break;
389         }
390     }
391 
392     // The only common intersection
393     if (intersection != nullptr && aliases1.size() == 1 && aliases2.size() == 1) {
394         return SingleIntersectionAliasing(p1, p2, intersection);
395     }
396     // Empty intersection: check that both addresses are not parameters
397     if (intersection == nullptr) {
398         return CheckMemAddressEmptyIntersectionCase(aliases1, aliases2, p1, p2);
399     }
400     return MAY_ALIAS;
401 }
402 
403 /// Checks aliasing if P1 and P2 point to the one single object.
404 /* static */
SingleIntersectionAliasing(const Pointer & p1,const Pointer & p2,const Pointer * intersection)405 AliasType AliasAnalysis::SingleIntersectionAliasing(const Pointer &p1, const Pointer &p2, const Pointer *intersection)
406 {
407     ASSERT(p1.GetType() == p2.GetType());
408     switch (p1.GetType()) {
409         case ARRAY_ELEMENT:
410             if (IsSameOffsets(p1.GetIdx(), p2.GetIdx()) != Trilean::TRUE) {
411                 return MAY_ALIAS;
412             }
413             if (p1.GetImm() != p2.GetImm()) {
414                 return NO_ALIAS;
415             }
416             break;
417         case DICTIONARY_ELEMENT:
418             if (IsSameOffsets(p1.GetIdx(), p2.GetIdx()) != Trilean::TRUE) {
419                 return MAY_ALIAS;
420             }
421             if (p1.GetImm() != p2.GetImm()) {
422                 return MAY_ALIAS;
423             }
424             break;
425         case OBJECT_FIELD:
426             if (!p1.HasSameOffset(p2)) {
427                 return NO_ALIAS;
428             }
429             break;
430         case OBJECT:
431             break;
432         default:
433             UNREACHABLE();
434     }
435     if (intersection->IsVolatile()) {
436         return MAY_ALIAS;
437     }
438     return MUST_ALIAS;
439 }
440 
SolveConstraintsMainLoop(Pointer & ref,Pointer & edge,bool & added,PointerSet & sols)441 void AliasAnalysis::SolveConstraintsMainLoop(Pointer &ref, Pointer &edge, bool &added, PointerSet &sols)
442 {
443     for (auto &alias : pointsTo_.at(ref)) {
444         ASSERT(alias.GetBase() == nullptr || alias.GetBase()->GetOpcode() != Opcode::NullCheck);
445         if (edge.GetType() == OBJECT_FIELD && ref.GetBase() == edge.GetBase()) {
446             // Propagating from object to fields: A{a} -> A.F{a.f}
447             if (alias.GetType() == OBJECT) {
448                 Pointer p = Pointer::CreateObjectField(alias.GetBase(), edge.GetImm(), edge.GetTypePtr());
449                 p.SetLocalVolatile(alias.IsLocal(), edge.IsVolatile());
450 
451                 added |= sols.insert(p).second;
452                 continue;
453             }
454             // In case A{a.g} -> A.F we propagate symbolic name: A{a.g} -> A.F{A.F}
455             Pointer p = Pointer::CreateObjectField(ref.GetBase(), edge.GetImm(), edge.GetTypePtr());
456             p.SetLocalVolatile(alias.IsLocal(), edge.IsVolatile());
457 
458             added |= sols.insert(p).second;
459             continue;
460         }
461         if (edge.GetType() == ARRAY_ELEMENT && ref.GetBase() == edge.GetBase()) {
462             // Propagating from object to elements: A{a} -> A[i]{a[i]}
463             if (alias.GetType() == OBJECT) {
464                 Pointer p = Pointer::CreateArrayElement(alias.GetBase(), edge.GetIdx(), edge.GetImm());
465                 p.SetLocalVolatile(alias.IsLocal(), edge.IsVolatile());
466 
467                 added |= sols.insert(p).second;
468                 continue;
469             }
470             // In case A{a[j]} -> A[i] we propagate symbolic name: A{a[j]} -> A[i]{A[i]}
471             Pointer p = Pointer::CreateArrayElement(ref.GetBase(), edge.GetIdx(), edge.GetImm());
472             p.SetLocalVolatile(alias.IsLocal(), edge.IsVolatile());
473 
474             added |= sols.insert(p).second;
475             continue;
476         }
477         if (edge.GetType() == DICTIONARY_ELEMENT && ref.GetBase() == edge.GetBase()) {
478             // Propagating from object to elements: A{a} -> A[i]{a[i]}
479             if (alias.GetType() == OBJECT) {
480                 Pointer p = Pointer::CreateDictionaryElement(alias.GetBase(), edge.GetIdx());
481                 p.SetLocalVolatile(alias.IsLocal(), edge.IsVolatile());
482 
483                 added |= sols.insert(p).second;
484                 continue;
485             }
486             // In case A{a[j]} -> A[i] we propagate symbolic name: A{a[j]} -> A[i]{A[i]}
487             Pointer p = Pointer::CreateDictionaryElement(ref.GetBase(), edge.GetIdx());
488             p.SetLocalVolatile(alias.IsLocal(), edge.IsVolatile());
489 
490             added |= sols.insert(p).second;
491             continue;
492         }
493         added |= sols.insert(alias).second;
494     }
495 }
496 
497 /**
498  * Here we propagate solutions obtained from direct constraints through copy
499  * constraints e.g: we have a node A with solution {a} and the node A was
500  * copied to B and C (this->chains_ maintains these links), and C was copied to
501  * D.
502  *
503  *    A{a} -> B
504  *        \-> C -> D
505  *
506  * After first iteration (iterating A node) we will obtain
507  *
508  *     A{a} -> B{a}
509  *         \-> C{a} -> D
510  *
511  * After second iteration (iterating B node) nothing changes
512  *
513  * After third iteration (iterating C node):
514  *
515  * A{a} -> B{a}
516  *     \-> C{a} -> D{a}
517  *
518  * For complex nodes (OBJECT_FIELD, ARRAY_ELEMENT) we create auxiliary nodes e.g.
519  * if a field F was accessed from object A then we have two nodes:
520  *
521  * A{a} -> A.F
522  *
523  * And solutions from A would be propagated as following:
524  *
525  * A{a} -> A.F{a.F}
526  *
527  * The function works using worklist to process only updated nodes.
528  */
SolveConstraints()529 void AliasAnalysis::SolveConstraints()
530 {
531     ArenaQueue<Pointer> worklist(GetGraph()->GetLocalAllocator()->Adapter());
532     for (auto &pair : *direct_) {
533         if (chains_->find(pair.first) != chains_->end()) {
534             worklist.push(pair.first);
535         }
536     }
537 
538     while (!worklist.empty()) {
539         Pointer &ref = worklist.front();
540         ASSERT(ref.GetBase() == nullptr || ref.GetBase()->GetOpcode() != Opcode::NullCheck);
541         for (auto &edge : chains_->at(ref)) {
542             // POOL_CONSTANT cannot be assignee
543             ASSERT(edge.GetType() != POOL_CONSTANT);
544             auto &sols = pointsTo_.try_emplace(edge, GetGraph()->GetAllocator()->Adapter()).first->second;
545             bool added = false;
546 
547             SolveConstraintsMainLoop(ref, edge, added, sols);
548 
549             if (added && chains_->find(edge) != chains_->end()) {
550                 worklist.push(edge);
551             }
552             ASSERT(!sols.empty());
553         }
554         worklist.pop();
555     }
556 }
557 
558 /// Selects the address from instruction that should be checked on alias
ParseInstruction(Inst * inst,Pointer * pointer)559 bool AliasAnalysis::ParseInstruction(Inst *inst, Pointer *pointer)
560 {
561     Pointer p {};
562     switch (inst->GetOpcode()) {
563         case Opcode::LoadArray:
564         case Opcode::LoadArrayI:
565         case Opcode::StoreArray:
566         case Opcode::StoreArrayI:
567             p = ParseArrayElement(inst);
568             break;
569         case Opcode::LoadString:
570         case Opcode::LoadType:
571         case Opcode::UnresolvedLoadType:
572             p = ParsePoolConstant(inst);
573             break;
574         case Opcode::LoadStatic:
575         case Opcode::StoreStatic:
576         case Opcode::UnresolvedStoreStatic:
577         case Opcode::LoadResolvedObjectFieldStatic:
578         case Opcode::StoreResolvedObjectFieldStatic:
579             p = ParseStaticField(inst);
580             break;
581         case Opcode::LoadObject:
582         case Opcode::StoreObject:
583         case Opcode::LoadResolvedObjectField:
584         case Opcode::StoreResolvedObjectField:
585             p = ParseObjectField(inst);
586             break;
587         case Opcode::LoadObjectDynamic:
588         case Opcode::StoreObjectDynamic:
589             p = ParseDynamicField(inst);
590             break;
591         default:
592             return false;
593     }
594 
595     auto base = p.GetBase();
596     if (base != nullptr) {
597         // Currently unhandled and return always MAY_ALIAS
598         if (base->GetOpcode() == Opcode::LoadArrayPair || base->GetOpcode() == Opcode::LoadArrayPairI ||
599             base->GetOpcode() == Opcode::LoadPairPart || base->GetOpcode() == Opcode::CatchPhi ||
600             base->GetOpcode() == Opcode::Load || base->GetOpcode() == Opcode::LoadI ||
601             base->GetOpcode() == Opcode::Store || base->GetOpcode() == Opcode::StoreI) {
602             return false;
603         }
604     }
605 
606     *pointer = p;
607     return true;
608 }
609 
ParseArrayElement(Inst * inst)610 Pointer AliasAnalysis::ParseArrayElement(Inst *inst)
611 {
612     uint32_t imm = 0;
613     Inst *offset = nullptr;
614     switch (inst->GetOpcode()) {
615         case Opcode::LoadArray:
616         case Opcode::StoreArray:
617             offset = inst->GetDataFlowInput(1);
618             break;
619         case Opcode::LoadArrayI:
620             imm = inst->CastToLoadArrayI()->GetImm();
621             break;
622         case Opcode::StoreArrayI:
623             imm = inst->CastToStoreArrayI()->GetImm();
624             break;
625         default:
626             UNREACHABLE();
627     }
628     auto base = inst->GetDataFlowInput(0);
629     return Pointer::CreateArrayElement(base, offset, imm);
630 }
631 
ParsePoolConstant(Inst * inst)632 Pointer AliasAnalysis::ParsePoolConstant(Inst *inst)
633 {
634     uint32_t typeId = 0;
635     switch (inst->GetOpcode()) {
636         case Opcode::LoadString:
637             typeId = inst->CastToLoadString()->GetTypeId();
638             break;
639         case Opcode::LoadType:
640             typeId = inst->CastToLoadType()->GetTypeId();
641             break;
642         case Opcode::UnresolvedLoadType:
643             typeId = inst->CastToUnresolvedLoadType()->GetTypeId();
644             break;
645         default:
646             UNREACHABLE();
647     }
648     return Pointer::CreatePoolConstant(typeId);
649 }
650 
ParseStaticField(Inst * inst)651 Pointer AliasAnalysis::ParseStaticField(Inst *inst)
652 {
653     uint32_t typeId = 0;
654     void *typePtr = nullptr;
655     switch (inst->GetOpcode()) {
656         case Opcode::LoadStatic:
657             typeId = inst->CastToLoadStatic()->GetTypeId();
658             typePtr = inst->CastToLoadStatic()->GetObjField();
659             break;
660         case Opcode::LoadResolvedObjectFieldStatic:
661             typeId = inst->CastToLoadResolvedObjectFieldStatic()->GetTypeId();
662             break;
663         case Opcode::StoreStatic:
664             typeId = inst->CastToStoreStatic()->GetTypeId();
665             typePtr = inst->CastToStoreStatic()->GetObjField();
666             break;
667         case Opcode::UnresolvedStoreStatic:
668             typeId = inst->CastToUnresolvedStoreStatic()->GetTypeId();
669             break;
670         case Opcode::StoreResolvedObjectFieldStatic:
671             typeId = inst->CastToStoreResolvedObjectFieldStatic()->GetTypeId();
672             break;
673         default:
674             UNREACHABLE();
675     }
676     return Pointer::CreateStaticField(typeId, typePtr);
677 }
678 
ParseObjectField(Inst * inst)679 Pointer AliasAnalysis::ParseObjectField(Inst *inst)
680 {
681     uint32_t typeId = 0;
682     void *typePtr = nullptr;
683     bool isStatic = false;
684     switch (inst->GetOpcode()) {
685         case Opcode::LoadObject:
686             isStatic = inst->CastToLoadObject()->GetObjectType() == ObjectType::MEM_STATIC;
687             typeId = inst->CastToLoadObject()->GetTypeId();
688             typePtr = inst->CastToLoadObject()->GetObjField();
689             break;
690         case Opcode::LoadResolvedObjectField:
691             typeId = inst->CastToLoadResolvedObjectField()->GetTypeId();
692             break;
693         case Opcode::StoreObject:
694             isStatic = inst->CastToStoreObject()->GetObjectType() == ObjectType::MEM_STATIC;
695             typeId = inst->CastToStoreObject()->GetTypeId();
696             typePtr = inst->CastToStoreObject()->GetObjField();
697             break;
698         case Opcode::StoreResolvedObjectField:
699             typeId = inst->CastToStoreResolvedObjectField()->GetTypeId();
700             break;
701         default:
702             UNREACHABLE();
703     }
704     auto base = inst->GetDataFlowInput(0);
705     return isStatic ? Pointer::CreateStaticField(typeId, typePtr) : Pointer::CreateObjectField(base, typeId, typePtr);
706 }
707 
ParseDynamicField(Inst * inst)708 Pointer AliasAnalysis::ParseDynamicField(Inst *inst)
709 {
710     auto base = inst->GetDataFlowInput(0);
711 
712     DynObjectAccessType type;
713     DynObjectAccessMode mode;
714     switch (inst->GetOpcode()) {
715         case Opcode::LoadObjectDynamic:
716             type = inst->CastToLoadObjectDynamic()->GetAccessType();
717             mode = inst->CastToLoadObjectDynamic()->GetAccessMode();
718             break;
719         case Opcode::StoreObjectDynamic:
720             type = inst->CastToStoreObjectDynamic()->GetAccessType();
721             mode = inst->CastToStoreObjectDynamic()->GetAccessMode();
722             break;
723         default:
724             UNREACHABLE();
725     }
726 
727     return GetDynamicAccessPointer(inst, base, type, mode);
728 }
729 
730 /**
731  * Compares offsets. Since we have a situation when we cannot determine either equal offsets or not,
732  * we use three valued logic. It is handy when we want to know whether offsets are definitely
733  * different or definitely equal.
734  */
735 /* static */
IsSameOffsets(const Inst * off1,const Inst * off2)736 AliasAnalysis::Trilean AliasAnalysis::IsSameOffsets(const Inst *off1, const Inst *off2)
737 {
738     if (off1 == off2) {
739         return Trilean::TRUE;
740     }
741     if (off1 == nullptr || off2 == nullptr) {
742         return Trilean::FALSE;
743     }
744 
745     if (off1->GetVN() != INVALID_VN && off2->GetVN() != INVALID_VN && off1->GetVN() == off2->GetVN()) {
746         return Trilean::TRUE;
747     }
748 
749     if (off1->IsConst() && off2->IsConst() &&
750         off1->CastToConstant()->GetRawValue() != off2->CastToConstant()->GetRawValue()) {
751         return Trilean::FALSE;
752     }
753 
754     return Trilean::UNKNOWN;
755 }
756 
757 /// Instructions that definitely are not an alias of anything.
VisitNullPtr(GraphVisitor * v,Inst * inst)758 void AliasAnalysis::VisitNullPtr(GraphVisitor *v, Inst *inst)
759 {
760     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
761 }
VisitLoadUndefined(GraphVisitor * v,Inst * inst)762 void AliasAnalysis::VisitLoadUndefined(GraphVisitor *v, Inst *inst)
763 {
764     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
765 }
VisitInitObject(GraphVisitor * v,Inst * inst)766 void AliasAnalysis::VisitInitObject(GraphVisitor *v, Inst *inst)
767 {
768     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
769 }
VisitNewObject(GraphVisitor * v,Inst * inst)770 void AliasAnalysis::VisitNewObject(GraphVisitor *v, Inst *inst)
771 {
772     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
773 }
VisitNewArray(GraphVisitor * v,Inst * inst)774 void AliasAnalysis::VisitNewArray(GraphVisitor *v, Inst *inst)
775 {
776     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
777 }
VisitMultiArray(GraphVisitor * v,Inst * inst)778 void AliasAnalysis::VisitMultiArray(GraphVisitor *v, Inst *inst)
779 {
780     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
781 }
VisitInitEmptyString(GraphVisitor * v,Inst * inst)782 void AliasAnalysis::VisitInitEmptyString(GraphVisitor *v, Inst *inst)
783 {
784     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
785 }
VisitInitString(GraphVisitor * v,Inst * inst)786 void AliasAnalysis::VisitInitString(GraphVisitor *v, Inst *inst)
787 {
788     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
789 }
790 
791 /**
792  * Instructions that can introduce references that are an alias of
793  * something already existed.
794  */
VisitConstant(GraphVisitor * v,Inst * inst)795 void AliasAnalysis::VisitConstant(GraphVisitor *v, Inst *inst)
796 {
797     if (inst->IsReferenceOrAny()) {
798         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
799     }
800 }
VisitParameter(GraphVisitor * v,Inst * inst)801 void AliasAnalysis::VisitParameter(GraphVisitor *v, Inst *inst)
802 {
803     if (inst->IsReferenceOrAny()) {
804         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
805     }
806 }
VisitLoadImmediate(GraphVisitor * v,Inst * inst)807 void AliasAnalysis::VisitLoadImmediate(GraphVisitor *v, Inst *inst)
808 {
809     if (inst->IsReferenceOrAny()) {
810         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
811     }
812 }
VisitIntrinsic(GraphVisitor * v,Inst * inst)813 void AliasAnalysis::VisitIntrinsic(GraphVisitor *v, Inst *inst)
814 {
815     if (inst->IsReferenceOrAny()) {
816         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
817     }
818 }
VisitBuiltin(GraphVisitor * v,Inst * inst)819 void AliasAnalysis::VisitBuiltin(GraphVisitor *v, Inst *inst)
820 {
821     if (inst->IsReferenceOrAny()) {
822         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
823     }
824 }
VisitCallStatic(GraphVisitor * v,Inst * inst)825 void AliasAnalysis::VisitCallStatic(GraphVisitor *v, Inst *inst)
826 {
827     if (inst->IsReferenceOrAny()) {
828         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
829     }
830 }
VisitCallResolvedStatic(GraphVisitor * v,Inst * inst)831 void AliasAnalysis::VisitCallResolvedStatic(GraphVisitor *v, Inst *inst)
832 {
833     if (inst->IsReferenceOrAny()) {
834         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
835     }
836 }
VisitCallVirtual(GraphVisitor * v,Inst * inst)837 void AliasAnalysis::VisitCallVirtual(GraphVisitor *v, Inst *inst)
838 {
839     if (inst->IsReferenceOrAny()) {
840         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
841     }
842 }
VisitCallResolvedVirtual(GraphVisitor * v,Inst * inst)843 void AliasAnalysis::VisitCallResolvedVirtual(GraphVisitor *v, Inst *inst)
844 {
845     if (inst->IsReferenceOrAny()) {
846         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
847     }
848 }
VisitCallDynamic(GraphVisitor * v,Inst * inst)849 void AliasAnalysis::VisitCallDynamic(GraphVisitor *v, Inst *inst)
850 {
851     if (inst->IsReferenceOrAny()) {
852         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
853     }
854 }
VisitGetManagedClassObject(GraphVisitor * v,Inst * inst)855 void AliasAnalysis::VisitGetManagedClassObject(GraphVisitor *v, Inst *inst)
856 {
857     if (inst->IsReferenceOrAny()) {
858         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
859     }
860 }
VisitResolveObjectFieldStatic(GraphVisitor * v,Inst * inst)861 void AliasAnalysis::VisitResolveObjectFieldStatic(GraphVisitor *v, Inst *inst)
862 {
863     if (inst->IsReferenceOrAny()) {
864         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
865     }
866 }
867 
868 /// Instructions that introduce static fields (global variables).
VisitLoadStatic(GraphVisitor * v,Inst * inst)869 void AliasAnalysis::VisitLoadStatic(GraphVisitor *v, Inst *inst)
870 {
871     if (!inst->IsReferenceOrAny()) {
872         return;
873     }
874     auto visitor = static_cast<AliasAnalysis *>(v);
875     auto typedInst = inst->CastToLoadStatic();
876     uint32_t typeId = typedInst->GetTypeId();
877     Pointer sfield = Pointer::CreateStaticField(typeId, typedInst->GetObjField());
878 
879     sfield.SetVolatile(typedInst->GetVolatile());
880 
881     visitor->AddDirectEdge(sfield);
882     visitor->AddCopyEdge(sfield, Pointer::CreateObject(inst));
883 }
884 
VisitLoadResolvedObjectFieldStatic(GraphVisitor * v,Inst * inst)885 void AliasAnalysis::VisitLoadResolvedObjectFieldStatic(GraphVisitor *v, Inst *inst)
886 {
887     if (!inst->IsReferenceOrAny()) {
888         return;
889     }
890     auto visitor = static_cast<AliasAnalysis *>(v);
891     auto typedInst = inst->CastToLoadResolvedObjectFieldStatic();
892     uint32_t typeId = typedInst->GetTypeId();
893     Pointer sfield = Pointer::CreateStaticField(typeId);
894 
895     sfield.SetVolatile(IsVolatileMemInst(typedInst));
896 
897     visitor->AddDirectEdge(sfield);
898     visitor->AddCopyEdge(sfield, Pointer::CreateObject(inst));
899 }
900 
VisitStoreStatic(GraphVisitor * v,Inst * inst)901 void AliasAnalysis::VisitStoreStatic(GraphVisitor *v, Inst *inst)
902 {
903     if (!inst->IsReferenceOrAny()) {
904         return;
905     }
906     auto visitor = static_cast<AliasAnalysis *>(v);
907     auto typedInst = inst->CastToStoreStatic();
908     uint32_t typeId = typedInst->GetTypeId();
909     Pointer sfield = Pointer::CreateStaticField(typeId, typedInst->GetObjField());
910 
911     sfield.SetVolatile(typedInst->GetVolatile());
912 
913     visitor->AddDirectEdge(sfield);
914     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)), sfield);
915 }
916 
VisitStoreResolvedObjectFieldStatic(GraphVisitor * v,Inst * inst)917 void AliasAnalysis::VisitStoreResolvedObjectFieldStatic(GraphVisitor *v, Inst *inst)
918 {
919     if (inst->GetType() != DataType::REFERENCE) {
920         return;
921     }
922     auto visitor = static_cast<AliasAnalysis *>(v);
923     auto typedInst = inst->CastToStoreResolvedObjectFieldStatic();
924     uint32_t typeId = typedInst->GetTypeId();
925     Pointer sfield = Pointer::CreateStaticField(typeId);
926 
927     sfield.SetVolatile(IsVolatileMemInst(typedInst));
928 
929     visitor->AddDirectEdge(sfield);
930     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)), sfield);
931 }
932 
VisitUnresolvedStoreStatic(GraphVisitor * v,Inst * inst)933 void AliasAnalysis::VisitUnresolvedStoreStatic(GraphVisitor *v, Inst *inst)
934 {
935     if (!inst->IsReferenceOrAny()) {
936         return;
937     }
938     auto visitor = static_cast<AliasAnalysis *>(v);
939     auto typedInst = inst->CastToUnresolvedStoreStatic();
940     uint32_t typeId = typedInst->GetTypeId();
941     Pointer sfield = Pointer::CreateStaticField(typeId);
942 
943     sfield.SetVolatile(IsVolatileMemInst(typedInst));
944 
945     visitor->AddDirectEdge(sfield);
946     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)), sfield);
947 }
948 
949 /// Instructions that introduce unique constant references (global constants).
VisitLoadRuntimeClass(GraphVisitor * v,Inst * inst)950 void AliasAnalysis::VisitLoadRuntimeClass(GraphVisitor *v, Inst *inst)
951 {
952     if (inst->IsReferenceOrAny()) {
953         uint32_t typeId = inst->CastToLoadRuntimeClass()->GetTypeId();
954         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
955     }
956 }
957 
VisitLoadClass(GraphVisitor * v,Inst * inst)958 void AliasAnalysis::VisitLoadClass(GraphVisitor *v, Inst *inst)
959 {
960     if (inst->IsReferenceOrAny()) {
961         uint32_t typeId = inst->CastToLoadClass()->GetTypeId();
962         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
963     }
964 }
VisitLoadAndInitClass(GraphVisitor * v,Inst * inst)965 void AliasAnalysis::VisitLoadAndInitClass(GraphVisitor *v, Inst *inst)
966 {
967     if (inst->IsReferenceOrAny()) {
968         uint32_t typeId = inst->CastToLoadAndInitClass()->GetTypeId();
969         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
970     }
971 }
VisitUnresolvedLoadAndInitClass(GraphVisitor * v,Inst * inst)972 void AliasAnalysis::VisitUnresolvedLoadAndInitClass(GraphVisitor *v, Inst *inst)
973 {
974     if (inst->IsReferenceOrAny()) {
975         uint32_t typeId = inst->CastToUnresolvedLoadAndInitClass()->GetTypeId();
976         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
977     }
978 }
VisitGetGlobalVarAddress(GraphVisitor * v,Inst * inst)979 void AliasAnalysis::VisitGetGlobalVarAddress(GraphVisitor *v, Inst *inst)
980 {
981     if (inst->IsReferenceOrAny()) {
982         uint32_t typeId = inst->CastToGetGlobalVarAddress()->GetTypeId();
983         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
984     }
985 }
VisitLoadString(GraphVisitor * v,Inst * inst)986 void AliasAnalysis::VisitLoadString(GraphVisitor *v, Inst *inst)
987 {
988     if (inst->IsReferenceOrAny()) {
989         uint32_t typeId = inst->CastToLoadString()->GetTypeId();
990         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
991     }
992 }
VisitLoadConstArray(GraphVisitor * v,Inst * inst)993 void AliasAnalysis::VisitLoadConstArray(GraphVisitor *v, Inst *inst)
994 {
995     if (inst->IsReferenceOrAny()) {
996         uint32_t typeId = inst->CastToLoadConstArray()->GetTypeId();
997         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
998     }
999 }
VisitLoadType(GraphVisitor * v,Inst * inst)1000 void AliasAnalysis::VisitLoadType(GraphVisitor *v, Inst *inst)
1001 {
1002     if (inst->IsReferenceOrAny()) {
1003         uint32_t typeId = inst->CastToLoadType()->GetTypeId();
1004         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
1005     }
1006 }
VisitUnresolvedLoadType(GraphVisitor * v,Inst * inst)1007 void AliasAnalysis::VisitUnresolvedLoadType(GraphVisitor *v, Inst *inst)
1008 {
1009     if (inst->IsReferenceOrAny()) {
1010         uint32_t typeId = inst->CastToUnresolvedLoadType()->GetTypeId();
1011         static_cast<AliasAnalysis *>(v)->AddConstantDirectEdge(inst, typeId);
1012     }
1013 }
1014 
VisitLoadObjFromConst(GraphVisitor * v,Inst * inst)1015 void AliasAnalysis::VisitLoadObjFromConst(GraphVisitor *v, Inst *inst)
1016 {
1017     if (inst->IsReferenceOrAny()) {
1018         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
1019     }
1020 }
1021 
1022 /// Instructions that introduce aliases.
VisitLoadArray(GraphVisitor * v,Inst * inst)1023 void AliasAnalysis::VisitLoadArray(GraphVisitor *v, Inst *inst)
1024 {
1025     if (!inst->IsReferenceOrAny()) {
1026         return;
1027     }
1028     auto visitor = static_cast<AliasAnalysis *>(v);
1029     Inst *arr = inst->GetDataFlowInput(0);
1030     Inst *idx = inst->GetDataFlowInput(1);
1031     Pointer obj = Pointer::CreateObject(arr);
1032     Pointer elem = Pointer::CreateArrayElement(arr, idx);
1033     Pointer val = Pointer::CreateObject(inst);
1034 
1035     visitor->AddCopyEdge(obj, elem);
1036     visitor->AddCopyEdge(elem, val);
1037 }
1038 
VisitStoreArray(GraphVisitor * v,Inst * inst)1039 void AliasAnalysis::VisitStoreArray(GraphVisitor *v, Inst *inst)
1040 {
1041     if (!inst->IsReferenceOrAny()) {
1042         return;
1043     }
1044     auto visitor = static_cast<AliasAnalysis *>(v);
1045     Inst *arr = inst->GetDataFlowInput(0);
1046     Inst *idx = inst->GetDataFlowInput(1);
1047     Pointer obj = Pointer::CreateObject(arr);
1048     Pointer elem = Pointer::CreateArrayElement(arr, idx);
1049     Pointer val = Pointer::CreateObject(inst->GetDataFlowInput(2U));
1050 
1051     visitor->AddCopyEdge(obj, elem);
1052     visitor->AddCopyEdge(val, elem);
1053 }
1054 
VisitLoadArrayI(GraphVisitor * v,Inst * inst)1055 void AliasAnalysis::VisitLoadArrayI(GraphVisitor *v, Inst *inst)
1056 {
1057     if (!inst->IsReferenceOrAny()) {
1058         return;
1059     }
1060     auto visitor = static_cast<AliasAnalysis *>(v);
1061     Inst *arr = inst->GetDataFlowInput(0);
1062     Pointer obj = Pointer::CreateObject(arr);
1063     Pointer elem = Pointer::CreateArrayElement(arr, nullptr, inst->CastToLoadArrayI()->GetImm());
1064     Pointer val = Pointer::CreateObject(inst);
1065 
1066     visitor->AddCopyEdge(obj, elem);
1067     visitor->AddCopyEdge(elem, val);
1068 }
1069 
VisitStoreArrayI(GraphVisitor * v,Inst * inst)1070 void AliasAnalysis::VisitStoreArrayI(GraphVisitor *v, Inst *inst)
1071 {
1072     if (!inst->IsReferenceOrAny()) {
1073         return;
1074     }
1075     auto visitor = static_cast<AliasAnalysis *>(v);
1076     Inst *arr = inst->GetDataFlowInput(0);
1077     Pointer obj = Pointer::CreateObject(arr);
1078     Pointer elem = Pointer::CreateArrayElement(arr, nullptr, inst->CastToStoreArrayI()->GetImm());
1079     Pointer val = Pointer::CreateObject(inst->GetDataFlowInput(1));
1080 
1081     visitor->AddCopyEdge(obj, elem);
1082     visitor->AddCopyEdge(val, elem);
1083 }
1084 
VisitLoadArrayPair(GraphVisitor * v,Inst * inst)1085 void AliasAnalysis::VisitLoadArrayPair(GraphVisitor *v, Inst *inst)
1086 {
1087     if (!inst->IsReferenceOrAny()) {
1088         return;
1089     }
1090     auto visitor = static_cast<AliasAnalysis *>(v);
1091     auto *load = inst->CastToLoadArrayPair();
1092     Inst *arr = load->GetDataFlowInput(load->GetArray());
1093     Pointer obj = Pointer::CreateObject(arr);
1094     for (auto &user : load->GetUsers()) {
1095         ASSERT(user.GetInst()->GetOpcode() == Opcode::LoadPairPart);
1096         auto uinst = user.GetInst()->CastToLoadPairPart();
1097 
1098         Pointer elem = Pointer::CreateArrayElement(arr, load->GetIndex(), uinst->GetImm());
1099         Pointer val = Pointer::CreateObject(uinst);
1100         visitor->AddCopyEdge(obj, elem);
1101         visitor->AddCopyEdge(elem, val);
1102         visitor->AddCopyEdge(elem, Pointer::CreateObject(load));
1103     }
1104 }
1105 
VisitStoreArrayPair(GraphVisitor * v,Inst * inst)1106 void AliasAnalysis::VisitStoreArrayPair(GraphVisitor *v, Inst *inst)
1107 {
1108     if (!inst->IsReferenceOrAny()) {
1109         return;
1110     }
1111     auto visitor = static_cast<AliasAnalysis *>(v);
1112     auto *store = inst->CastToStoreArrayPair();
1113     Inst *arr = store->GetDataFlowInput(store->GetArray());
1114     Pointer obj = Pointer::CreateObject(arr);
1115     Pointer elFst = Pointer::CreateArrayElement(arr, store->GetIndex());
1116     Pointer elSnd = Pointer::CreateArrayElement(arr, store->GetIndex(), 1);
1117     Pointer valFst = Pointer::CreateObject(store->GetDataFlowInput(store->GetStoredValue(0)));
1118     Pointer valSnd = Pointer::CreateObject(store->GetDataFlowInput(store->GetStoredValue(1)));
1119 
1120     visitor->AddCopyEdge(obj, elFst);
1121     visitor->AddCopyEdge(obj, elSnd);
1122     visitor->AddCopyEdge(valFst, elFst);
1123     visitor->AddCopyEdge(valSnd, elSnd);
1124 }
1125 
VisitLoadArrayPairI(GraphVisitor * v,Inst * inst)1126 void AliasAnalysis::VisitLoadArrayPairI(GraphVisitor *v, Inst *inst)
1127 {
1128     if (!inst->IsReferenceOrAny()) {
1129         return;
1130     }
1131     auto visitor = static_cast<AliasAnalysis *>(v);
1132     auto *load = inst->CastToLoadArrayPairI();
1133     Inst *arr = load->GetDataFlowInput(load->GetArray());
1134     Pointer obj = Pointer::CreateObject(arr);
1135     for (auto &user : load->GetUsers()) {
1136         ASSERT(user.GetInst()->GetOpcode() == Opcode::LoadPairPart);
1137         auto uinst = user.GetInst()->CastToLoadPairPart();
1138 
1139         Pointer elem = Pointer::CreateArrayElement(arr, nullptr, load->GetImm() + uinst->GetImm());
1140         Pointer val = Pointer::CreateObject(uinst);
1141         visitor->AddCopyEdge(obj, elem);
1142         visitor->AddCopyEdge(elem, val);
1143         visitor->AddCopyEdge(elem, Pointer::CreateObject(load));
1144     }
1145 }
1146 
VisitStoreArrayPairI(GraphVisitor * v,Inst * inst)1147 void AliasAnalysis::VisitStoreArrayPairI(GraphVisitor *v, Inst *inst)
1148 {
1149     if (!inst->IsReferenceOrAny()) {
1150         return;
1151     }
1152     auto visitor = static_cast<AliasAnalysis *>(v);
1153     auto *store = inst->CastToStoreArrayPairI();
1154     Inst *arr = store->GetDataFlowInput(store->GetArray());
1155     Pointer obj = Pointer::CreateObject(arr);
1156     Pointer elFst = Pointer::CreateArrayElement(arr, nullptr, store->GetImm());
1157     Pointer elSnd = Pointer::CreateArrayElement(arr, nullptr, store->GetImm() + 1);
1158     Pointer valFst = Pointer::CreateObject(store->GetDataFlowInput(store->GetFirstValue()));
1159     Pointer valSnd = Pointer::CreateObject(store->GetDataFlowInput(store->GetSecondValue()));
1160 
1161     visitor->AddCopyEdge(obj, elFst);
1162     visitor->AddCopyEdge(obj, elSnd);
1163     visitor->AddCopyEdge(valFst, elFst);
1164     visitor->AddCopyEdge(valSnd, elSnd);
1165 }
1166 
VisitLoadObject(GraphVisitor * v,Inst * inst)1167 void AliasAnalysis::VisitLoadObject(GraphVisitor *v, Inst *inst)
1168 {
1169     if (!inst->IsReferenceOrAny()) {
1170         return;
1171     }
1172     auto visitor = static_cast<AliasAnalysis *>(v);
1173     auto typedInst = inst->CastToLoadObject();
1174     uint32_t typeId = typedInst->GetTypeId();
1175     if (inst->CastToLoadObject()->GetObjectType() == ObjectType::MEM_STATIC) {
1176         Pointer sfield = Pointer::CreateStaticField(typeId, typedInst->GetObjField());
1177 
1178         sfield.SetVolatile(typedInst->GetVolatile());
1179 
1180         visitor->AddDirectEdge(sfield);
1181         visitor->AddCopyEdge(sfield, Pointer::CreateObject(inst));
1182     } else {
1183         Inst *dfobj = inst->GetDataFlowInput(0);
1184         Pointer obj = Pointer::CreateObject(dfobj);
1185         Pointer ifield = Pointer::CreateObjectField(dfobj, typeId, typedInst->GetObjField());
1186         Pointer to = Pointer::CreateObject(inst);
1187 
1188         ifield.SetVolatile(typedInst->GetVolatile());
1189 
1190         visitor->AddCopyEdge(obj, ifield);
1191         visitor->AddCopyEdge(ifield, to);
1192     }
1193 }
1194 
VisitLoadResolvedObjectField(GraphVisitor * v,Inst * inst)1195 void AliasAnalysis::VisitLoadResolvedObjectField(GraphVisitor *v, Inst *inst)
1196 {
1197     if (!inst->IsReferenceOrAny()) {
1198         return;
1199     }
1200     auto visitor = static_cast<AliasAnalysis *>(v);
1201     auto typedInst = inst->CastToLoadResolvedObjectField();
1202     uint32_t typeId = typedInst->GetTypeId();
1203     Inst *dfobj = inst->GetDataFlowInput(0);
1204     Pointer obj = Pointer::CreateObject(dfobj);
1205     Pointer ifield = Pointer::CreateObjectField(dfobj, typeId);
1206     Pointer to = Pointer::CreateObject(inst);
1207 
1208     ifield.SetVolatile(IsVolatileMemInst(typedInst));
1209 
1210     visitor->AddCopyEdge(obj, ifield);
1211     visitor->AddCopyEdge(ifield, to);
1212 }
1213 
VisitStoreObject(GraphVisitor * v,Inst * inst)1214 void AliasAnalysis::VisitStoreObject(GraphVisitor *v, Inst *inst)
1215 {
1216     if (!inst->IsReferenceOrAny()) {
1217         return;
1218     }
1219     auto visitor = static_cast<AliasAnalysis *>(v);
1220     auto typedInst = inst->CastToStoreObject();
1221     uint32_t typeId = typedInst->GetTypeId();
1222     if (inst->CastToStoreObject()->GetObjectType() == ObjectType::MEM_STATIC) {
1223         Pointer sfield = Pointer::CreateStaticField(typeId, typedInst->GetObjField());
1224 
1225         sfield.SetVolatile(typedInst->GetVolatile());
1226 
1227         visitor->AddDirectEdge(sfield);
1228         visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)), sfield);
1229     } else {
1230         Inst *dfobj = inst->GetDataFlowInput(0);
1231         Pointer obj = Pointer::CreateObject(dfobj);
1232         Pointer ifield = Pointer::CreateObjectField(dfobj, typeId, typedInst->GetObjField());
1233         Pointer val = Pointer::CreateObject(inst->GetDataFlowInput(1));
1234 
1235         ifield.SetVolatile(typedInst->GetVolatile());
1236 
1237         visitor->AddCopyEdge(obj, ifield);
1238         visitor->AddCopyEdge(val, ifield);
1239     }
1240 }
1241 
VisitStoreResolvedObjectField(GraphVisitor * v,Inst * inst)1242 void AliasAnalysis::VisitStoreResolvedObjectField(GraphVisitor *v, Inst *inst)
1243 {
1244     if (!inst->IsReferenceOrAny()) {
1245         return;
1246     }
1247     auto visitor = static_cast<AliasAnalysis *>(v);
1248     auto typedInst = inst->CastToStoreResolvedObjectField();
1249     uint32_t typeId = typedInst->GetTypeId();
1250     Inst *dfobj = inst->GetDataFlowInput(0);
1251     Pointer obj = Pointer::CreateObject(dfobj);
1252     Pointer ifield = Pointer::CreateObjectField(dfobj, typeId);
1253     Pointer val = Pointer::CreateObject(inst->GetDataFlowInput(1));
1254 
1255     ifield.SetVolatile(IsVolatileMemInst(inst));
1256 
1257     visitor->AddCopyEdge(obj, ifield);
1258     visitor->AddCopyEdge(val, ifield);
1259 }
1260 
VisitCatchPhi(GraphVisitor * v,Inst * inst)1261 void AliasAnalysis::VisitCatchPhi(GraphVisitor *v, Inst *inst)
1262 {
1263     if (!inst->IsReferenceOrAny()) {
1264         return;
1265     }
1266     auto visitor = static_cast<AliasAnalysis *>(v);
1267     auto inputsSet = visitor->GetClearInputsSet();
1268     for (size_t i = 0; i < inst->GetInputsCount(); i++) {
1269         inputsSet->insert(inst->GetDataFlowInput(i));
1270     }
1271 
1272     for (auto inputInst : *inputsSet) {
1273         visitor->AddCopyEdge(Pointer::CreateObject(inputInst), Pointer::CreateObject(inst));
1274     }
1275 }
1276 
VisitPhi(GraphVisitor * v,Inst * inst)1277 void AliasAnalysis::VisitPhi(GraphVisitor *v, Inst *inst)
1278 {
1279     if (!inst->IsReferenceOrAny()) {
1280         return;
1281     }
1282     auto visitor = static_cast<AliasAnalysis *>(v);
1283     for (size_t i = 0; i < inst->GetInputsCount(); i++) {
1284         visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(i)), Pointer::CreateObject(inst));
1285     }
1286 }
1287 
VisitSelect(GraphVisitor * v,Inst * inst)1288 void AliasAnalysis::VisitSelect(GraphVisitor *v, Inst *inst)
1289 {
1290     if (!inst->IsReferenceOrAny()) {
1291         return;
1292     }
1293     ASSERT(inst->GetInputsCount() == 4U);
1294     auto visitor = static_cast<AliasAnalysis *>(v);
1295     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)), Pointer::CreateObject(inst));
1296     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(1)), Pointer::CreateObject(inst));
1297 }
1298 
VisitSelectImm(GraphVisitor * v,Inst * inst)1299 void AliasAnalysis::VisitSelectImm(GraphVisitor *v, Inst *inst)
1300 {
1301     if (!inst->IsReferenceOrAny()) {
1302         return;
1303     }
1304     ASSERT(inst->GetInputsCount() == 3U);
1305     auto visitor = static_cast<AliasAnalysis *>(v);
1306     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)), Pointer::CreateObject(inst));
1307     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(1)), Pointer::CreateObject(inst));
1308 }
1309 
VisitMov(GraphVisitor * v,Inst * inst)1310 void AliasAnalysis::VisitMov(GraphVisitor *v, Inst *inst)
1311 {
1312     if (!inst->IsReferenceOrAny()) {
1313         return;
1314     }
1315     auto visitor = static_cast<AliasAnalysis *>(v);
1316     visitor->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)), Pointer::CreateObject(inst));
1317 }
1318 
VisitCastAnyTypeValue(GraphVisitor * v,Inst * inst)1319 void AliasAnalysis::VisitCastAnyTypeValue(GraphVisitor *v, Inst *inst)
1320 {
1321     if (inst->GetType() == DataType::REFERENCE) {
1322         static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
1323     }
1324 }
1325 
VisitCastValueToAnyType(GraphVisitor * v,Inst * inst)1326 void AliasAnalysis::VisitCastValueToAnyType(GraphVisitor *v, Inst *inst)
1327 {
1328     if (inst->CastToCastValueToAnyType()->GetInputType(0) == DataType::REFERENCE) {
1329         static_cast<AliasAnalysis *>(v)->AddCopyEdge(Pointer::CreateObject(inst->GetDataFlowInput(0)),
1330                                                      Pointer::CreateObject(inst));
1331     }
1332 }
1333 
VisitGetAnyTypeName(GraphVisitor * v,Inst * inst)1334 void AliasAnalysis::VisitGetAnyTypeName(GraphVisitor *v, Inst *inst)
1335 {
1336     static_cast<AliasAnalysis *>(v)->AddDirectEdge(Pointer::CreateObject(inst));
1337 }
1338 
VisitLoadConstantPool(GraphVisitor * v,Inst * inst)1339 void AliasAnalysis::VisitLoadConstantPool(GraphVisitor *v, Inst *inst)
1340 {
1341     Inst *dfobj = inst->GetDataFlowInput(0);
1342     Pointer obj = Pointer::CreateObject(dfobj);
1343     Pointer to = Pointer::CreateObject(inst);
1344     static_cast<AliasAnalysis *>(v)->AddCopyEdge(obj, to);
1345 }
1346 
VisitLoadLexicalEnv(GraphVisitor * v,Inst * inst)1347 void AliasAnalysis::VisitLoadLexicalEnv(GraphVisitor *v, Inst *inst)
1348 {
1349     Inst *dfobj = inst->GetDataFlowInput(0);
1350     Pointer obj = Pointer::CreateObject(dfobj);
1351     Pointer to = Pointer::CreateObject(inst);
1352     static_cast<AliasAnalysis *>(v)->AddCopyEdge(obj, to);
1353 }
1354 
VisitLoadObjectDynamic(GraphVisitor * v,Inst * inst)1355 void AliasAnalysis::VisitLoadObjectDynamic(GraphVisitor *v, Inst *inst)
1356 {
1357     if (!inst->IsReferenceOrAny()) {
1358         return;
1359     }
1360     auto visitor = static_cast<AliasAnalysis *>(v);
1361     auto type = inst->CastToLoadObjectDynamic()->GetAccessType();
1362     auto mode = inst->CastToLoadObjectDynamic()->GetAccessMode();
1363 
1364     Inst *dfobj = inst->GetDataFlowInput(0);
1365     Pointer obj = Pointer::CreateObject(dfobj);
1366     Pointer val = Pointer::CreateObject(inst);
1367     Pointer elem = GetDynamicAccessPointer(inst, dfobj, type, mode);
1368 
1369     visitor->AddCopyEdge(obj, elem);
1370     visitor->AddCopyEdge(elem, val);
1371 }
1372 
VisitStoreObjectDynamic(GraphVisitor * v,Inst * inst)1373 void AliasAnalysis::VisitStoreObjectDynamic(GraphVisitor *v, Inst *inst)
1374 {
1375     if (!inst->IsReferenceOrAny()) {
1376         return;
1377     }
1378     auto visitor = static_cast<AliasAnalysis *>(v);
1379     auto type = inst->CastToStoreObjectDynamic()->GetAccessType();
1380     auto mode = inst->CastToStoreObjectDynamic()->GetAccessMode();
1381 
1382     Inst *dfobj = inst->GetDataFlowInput(0);
1383     Pointer obj = Pointer::CreateObject(dfobj);
1384     Pointer val = Pointer::CreateObject(inst);
1385     Pointer elem = GetDynamicAccessPointer(inst, dfobj, type, mode);
1386 
1387     visitor->AddCopyEdge(obj, elem);
1388     visitor->AddCopyEdge(val, elem);
1389 }
1390 
VisitLoadFromConstantPool(GraphVisitor * v,Inst * inst)1391 void AliasAnalysis::VisitLoadFromConstantPool(GraphVisitor *v, Inst *inst)
1392 {
1393     if (!inst->IsReferenceOrAny()) {
1394         return;
1395     }
1396     uint32_t typeId = inst->CastToLoadFromConstantPool()->GetTypeId();
1397     auto visitor = static_cast<AliasAnalysis *>(v);
1398     Inst *constpool = inst->GetDataFlowInput(0);
1399     Pointer obj = Pointer::CreateObject(constpool);
1400     Pointer elem = Pointer::CreateArrayElement(constpool, nullptr, typeId);
1401     Pointer val = Pointer::CreateObject(inst);
1402 
1403     visitor->AddCopyEdge(obj, elem);
1404     visitor->AddCopyEdge(elem, val);
1405 }
1406 
VisitDefault(Inst * inst)1407 void AliasAnalysis::VisitDefault([[maybe_unused]] Inst *inst)
1408 {
1409     /* Ignore the following instructions with REFERENCE type intentionally */
1410     switch (inst->GetOpcode()) {
1411         // Handled on its input
1412         case Opcode::LoadPairPart:
1413         // No passes that check class references aliasing
1414         case Opcode::GetInstanceClass:
1415         case Opcode::LoadImmediate:
1416         // NOTE(ekudriashov): Probably should be added
1417         case Opcode::Monitor:
1418         // Mitigated by using GetDataFlowInput
1419         case Opcode::NullCheck:
1420         case Opcode::RefTypeCheck:
1421         case Opcode::AnyTypeCheck:
1422         case Opcode::ObjByIndexCheck:
1423         case Opcode::HclassCheck:
1424         // Irrelevant for analysis
1425         case Opcode::Return:
1426         case Opcode::ReturnI:
1427         // NOTE(compiler team): support Load, Store
1428         case Opcode::Load:
1429         case Opcode::LoadI:
1430         case Opcode::Store:
1431         case Opcode::StoreI:
1432         // No need to analyze
1433         case Opcode::LiveOut:
1434         case Opcode::FunctionImmediate:
1435             return;
1436         default:
1437             ASSERT_DO(!inst->IsReferenceOrAny(),
1438                       (std::cerr << "Unsupported instruction in alias analysis: ", inst->Dump(&std::cerr)));
1439             return;
1440     }
1441 }
1442 }  // namespace panda::compiler
1443