• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2023 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef MPL2MPL_INCLUDE_CLASS_HIERARCHY_H
17 #define MPL2MPL_INCLUDE_CLASS_HIERARCHY_H
18 #include "mir_function.h"
19 #include "maple_phase.h"
20 
21 namespace maple {
22 class KlassHierarchy;  // circular dependency exists, no other choice
23 // should be consistent with runtime
24 constexpr uint32 kClassPrim = 0x0001;
25 constexpr uint32 kClassArray = 0x0002;
26 constexpr uint32 kClassHasFinalizer = 0x0004;
27 constexpr uint32 kClassSoftreference = 0x0008;
28 constexpr uint32 kClassWeakreference = 0x0010;
29 constexpr uint32 kClassPhantomreference = 0x0020;
30 constexpr uint32 kClassFinalizereference = 0x0040;
31 constexpr uint32 kClassCleaner = 0x0080;
32 constexpr uint32 kClassFinalizerreferenceSentinel = 0x0100;
33 constexpr uint32 kClassIsExceptionKlass = 0x0200;
34 constexpr uint32 kClassIsanonymousclass = 0x0400;
35 constexpr uint32 kClassIscoldclass = 0x0800;
36 constexpr uint32 kClassNeedDecouple = 0x1000;
37 constexpr uint32 kClassLazyBindingClass = 0x2000;
38 constexpr uint32 kClassLazyBoundClass = 0x4000;  // Only used in runtime, occupancy.
39 constexpr uint32 kClassRuntimeVerify = 0x8000;   // True if need verifier in runtime (error or deferred check).
40 constexpr uint32 kClassReference =
41     (kClassSoftreference | kClassWeakreference | kClassCleaner | kClassFinalizereference | kClassPhantomreference);
42 
43 bool IsSystemPreloadedClass(const std::string &className);
44 
45 // Klass is the basic node for building class hierarchy
46 class Klass {
47 public:
48     struct KlassComparator {
operatorKlassComparator49         bool operator()(const Klass *lhs, const Klass *rhs) const
50         {
51             CHECK_NULL_FATAL(rhs);
52             CHECK_NULL_FATAL(lhs);
53             return lhs->GetKlassName() < rhs->GetKlassName();
54         }
55     };
56 
57     Klass(MIRStructType *type, MapleAllocator *alc);
58     ~Klass() = default;
59 
60     // Return true if Klass represents an interface
IsInterface()61     bool IsInterface() const
62     {
63         return structType->GetKind() == kTypeInterface;
64     }
65 
IsInterfaceIncomplete()66     bool IsInterfaceIncomplete() const
67     {
68         return structType->GetKind() == kTypeInterfaceIncomplete;
69     }
70 
IsClass()71     bool IsClass() const
72     {
73         return structType->GetKind() == kTypeClass;
74     }
75 
IsClassIncomplete()76     bool IsClassIncomplete() const
77     {
78         return structType->GetKind() == kTypeClassIncomplete;
79     }
80 
81     // Return true if found in the member methods
82     bool IsKlassMethod(const MIRFunction *func) const;
83     // Return MIRFunction if has method
84     const MIRFunction *HasMethod(const std::string &funcname) const;
GetMethods()85     const MapleList<MIRFunction *> &GetMethods() const
86     {
87         return methods;
88     }
89 
GetMethod(GStrIdx idx)90     const MIRFunction *GetMethod(GStrIdx idx) const
91     {
92         MapleMap<GStrIdx, MIRFunction *>::const_iterator it = strIdx2Method.find(idx);
93         return it != strIdx2Method.end() ? it->second : nullptr;
94     }
GetKlassNameStrIdx()95     GStrIdx GetKlassNameStrIdx() const
96     {
97         return structType->GetNameStrIdx();
98     }
99 
GetKlassName()100     const std::string &GetKlassName() const
101     {
102         return structType->GetName();
103     }
104 
GetTypeIdx()105     TyIdx GetTypeIdx() const
106     {
107         return structType->GetTypeIndex();
108     }
109 
GetMIRStructType()110     MIRStructType *GetMIRStructType() const
111     {
112         return structType;
113     }
114 
GetMIRClassType()115     MIRClassType *GetMIRClassType() const
116     {
117         CHECK_FATAL(IsClass() || IsClassIncomplete(), "must");
118         return static_cast<MIRClassType *>(structType);
119     }
120 
GetMIRInterfaceType()121     MIRInterfaceType *GetMIRInterfaceType() const
122     {
123         CHECK_FATAL(IsInterface() || IsInterfaceIncomplete(), "must be");
124         return static_cast<MIRInterfaceType *>(structType);
125     }
126 
HasSuperKlass()127     bool HasSuperKlass() const
128     {
129         return !superKlasses.empty();
130     }
131 
HasSubKlass()132     bool HasSubKlass() const
133     {
134         return !subKlasses.empty();
135     }
136 
HasImplementInterfaces()137     bool HasImplementInterfaces() const
138     {
139         return !implInterfaces.empty();
140     }
141 
142     bool ImplementsKlass() const;
SetFlag(uint32 flag)143     void SetFlag(uint32 flag)
144     {
145         flags |= flag;
146     }
147 
GetFlag(uint32 flag)148     uint32 GetFlag(uint32 flag) const
149     {
150         return flags & flag;
151     }
152 
HasFlag(uint32 flag)153     bool HasFlag(uint32 flag) const
154     {
155         return GetFlag(flag) != 0;
156     }
157 
IsExceptionKlass()158     bool IsExceptionKlass() const
159     {
160         return HasFlag(kClassIsExceptionKlass);
161     }
162 
SetExceptionKlass()163     void SetExceptionKlass()
164     {
165         SetFlag(kClassIsExceptionKlass);
166     }
167 
HasFinalizer()168     bool HasFinalizer() const
169     {
170         return HasFlag(kClassHasFinalizer);
171     }
172 
SetHasFinalizer()173     void SetHasFinalizer()
174     {
175         SetFlag(kClassHasFinalizer);
176     }
177 
HasNativeMethod()178     bool HasNativeMethod() const
179     {
180         return hasNativeMethods;
181     }
182 
SetHasNativeMethod(bool flag)183     void SetHasNativeMethod(bool flag)
184     {
185         hasNativeMethods = flag;
186     }
187 
IsReference(uint32 flag)188     bool IsReference(uint32 flag) const
189     {
190         return HasFlag(flag);
191     }
192 
IsReference()193     bool IsReference() const
194     {
195         return HasFlag(kClassReference);
196     }
197 
IsArray()198     bool IsArray() const
199     {
200         return (structType->GetName().find(JARRAY_PREFIX_STR) == 0);
201     }
202 
IsPrivateInnerAndNoSubClass()203     bool IsPrivateInnerAndNoSubClass() const
204     {
205         return isPrivateInnerAndNoSubClassFlag;
206     }
207 
SetPrivateInnerAndNoSubClass(bool flag)208     void SetPrivateInnerAndNoSubClass(bool flag)
209     {
210         isPrivateInnerAndNoSubClassFlag = flag;
211     }
212 
GetNeedDecoupling()213     bool GetNeedDecoupling() const
214     {
215         return needDecoupling;
216     }
217 
SetNeedDecoupling(bool flag)218     void SetNeedDecoupling(bool flag)
219     {
220         needDecoupling = flag;
221     }
222 
GetClinit()223     const MIRFunction *GetClinit() const
224     {
225         return clinitMethod;
226     }
SetClinit(MIRFunction * m)227     void SetClinit(MIRFunction *m)
228     {
229         clinitMethod = m;
230     }
231 
GetClassInitBridge()232     MIRSymbol *GetClassInitBridge() const
233     {
234         return classInitBridge;
235     }
236 
SetClassInitBridge(MIRSymbol * s)237     void SetClassInitBridge(MIRSymbol *s)
238     {
239         classInitBridge = s;
240     }
241 
242     // Return the function defined in the current class, or the inherited
243     // function if it is not defined in the current class.
244     MIRFunction *GetClosestMethod(GStrIdx) const;
245     // This for class only, which only has 0 or 1 super class
246     Klass *GetSuperKlass() const;
GetSuperKlasses()247     const MapleList<Klass *> &GetSuperKlasses() const
248     {
249         return superKlasses;
250     }
251 
GetSubKlasses()252     const MapleSet<Klass *, KlassComparator> &GetSubKlasses() const
253     {
254         return subKlasses;
255     }
256 
GetImplKlasses()257     const MapleSet<Klass *, KlassComparator> &GetImplKlasses() const
258     {
259         return implKlasses;
260     }
261 
GetImplInterfaces()262     const MapleSet<Klass *, KlassComparator> &GetImplInterfaces() const
263     {
264         return implInterfaces;
265     }
266 
267     // Return a vector of possible functions
268     MapleVector<MIRFunction *> *GetCandidates(GStrIdx mnameNoklassStrIdx) const;
269     // Return the unique method if there is only one target virtual function.
270     // Return nullptr if there are multiple targets.
271     MIRFunction *GetUniqueMethod(GStrIdx mnameNoklassStrIdx) const;
AddSuperKlass(Klass * superclass)272     void AddSuperKlass(Klass *superclass)
273     {
274         superKlasses.push_back(superclass);
275     }
276 
AddSubKlass(Klass * subclass)277     void AddSubKlass(Klass *subclass)
278     {
279         subKlasses.insert(subclass);
280     }
281 
AddImplKlass(Klass * implclass)282     void AddImplKlass(Klass *implclass)
283     {
284         implKlasses.insert(implclass);
285     }
286 
AddImplInterface(Klass * interfaceKlass)287     void AddImplInterface(Klass *interfaceKlass)
288     {
289         implInterfaces.insert(interfaceKlass);
290     }
291 
AddMethod(MIRFunction * func)292     void AddMethod(MIRFunction *func)
293     {
294         methods.push_front(func);
295         strIdx2Method.insert({func->GetBaseFuncNameWithTypeStrIdx(), func});
296     }
297 
298     void DelMethod(const MIRFunction &func);
299     // Count the virtual methods for subclasses and merge with itself
300     void CountVirtMethBottomUp();
301     void Dump() const;
302 
303 private:
304     void DumpKlassImplInterfaces() const;
305     void DumpKlassImplKlasses() const;
306     void DumpKlassSuperKlasses() const;
307     void DumpKlassSubKlasses() const;
308     void DumpKlassMethods() const;
309     bool IsVirtualMethod(const MIRFunction &func) const;
310     // structType can be class or interface
311     MIRStructType *structType;
312     MapleAllocator *alloc;
313     // A collection of super classes.
314     // superklass is nullptr if it is not defined in the module.
315     MapleList<Klass *> superKlasses;
316     // A collection of sub classes
317     MapleSet<Klass *, KlassComparator> subKlasses;
318     // a collection of classes which implement the current interface
319     MapleSet<Klass *, KlassComparator> implKlasses;
320     // a collection of interfaces which is implemented by the current klass
321     MapleSet<Klass *, KlassComparator> implInterfaces;
322     // A collection of class member methods
323     MapleList<MIRFunction *> methods;
324     // A mapping to track every method to its baseFuncNameWithType
325     MapleMap<GStrIdx, MIRFunction *> strIdx2Method;
326     MIRFunction *clinitMethod = nullptr;
327     MIRSymbol *classInitBridge = nullptr;
328     // A mapping to track possible implementations for each virtual function
329     MapleMap<GStrIdx, MapleVector<MIRFunction *> *> strIdx2CandidateMap;
330     // flags of this class.
331     // Now contains whether this class is exception, reference or has finalizer.
332     uint32 flags = 0;
333     bool isPrivateInnerAndNoSubClassFlag = false;
334     bool hasNativeMethods = false;
335     bool needDecoupling = true;
336 };
337 
338 // data structure to represent class information defined in the module
339 class KlassHierarchy : public AnalysisResult {
340 public:
341     KlassHierarchy(MIRModule *mirmodule, MemPool *memPool);
342     virtual ~KlassHierarchy() = default;
343 
344     // Get a class. Return nullptr it does not exist.
345     Klass *GetKlassFromStrIdx(GStrIdx strIdx) const;
346     Klass *GetKlassFromTyIdx(TyIdx tyIdx) const;
347     Klass *GetKlassFromFunc(const MIRFunction *func) const;
348     Klass *GetKlassFromName(const std::string &name) const;
349     Klass *GetKlassFromLiteral(const std::string &name) const;
GetKlasses()350     const MapleMap<GStrIdx, Klass *> &GetKlasses() const
351     {
352         return strIdx2KlassMap;
353     }
354 
355     // Get lowest common ancestor for two classes
356     Klass *GetLCA(Klass *klass1, Klass *klass2) const;
357     TyIdx GetLCA(TyIdx ty1, TyIdx ty2) const;
358     GStrIdx GetLCA(GStrIdx str1, GStrIdx str2) const;
359     const std::string &GetLCA(const std::string &name1, const std::string &name2) const;
360     // 1/0/-1: true/false/unknown
361     int IsSuperKlass(TyIdx superTyIdx, TyIdx baseTyIdx) const;
362     bool IsSuperKlass(const Klass *super, const Klass *base) const;
363     bool IsSuperKlassForInterface(const Klass *super, const Klass *base) const;
364     bool IsInterfaceImplemented(Klass *interface, const Klass *base) const;
365     bool UpdateFieldID(TyIdx baseTypeIdx, TyIdx targetTypeIdx, FieldID &fldID) const;
366     // return true if class, its super or interfaces have at least one clinit function
367     bool NeedClinitCheckRecursively(const Klass &kl) const;
368 
369     void CountVirtualMethods() const;
370     void BuildHierarchy();
371     void Dump() const;
372 
GetTopoSortedKlasses()373     const MapleVector<Klass *> &GetTopoSortedKlasses() const
374     {
375         return topoWorkList;
376     }
377 
GetModule()378     const MIRModule *GetModule() const
379     {
380         return mirModule;
381     }
382     static bool traceFlag;
383 
384 private:
385     // New all klass
386     void AddKlasses();
387     // Connect all class<->interface edges based on Depth-First Search
388     void UpdateImplementedInterfaces();
389     // Get a vector of parent class and implementing interface
390     void GetParentKlasses(const Klass &klass, std::vector<Klass *> &parentKlasses) const;
391     // Get a vector of child class and implemented class
392     void GetChildKlasses(const Klass &klass, std::vector<Klass *> &childKlasses) const;
393     void ExceptionFlagProp(Klass &klass);
394     Klass *AddClassFlag(const std::string &name, uint32 flag);
395     int GetFieldIDOffsetBetweenClasses(const Klass &super, const Klass &base) const;
396     void TopologicalSortKlasses();
397     // Return the unique method if there is only one target virtual function.
398     // Return 0 if there are multiple targets or the targets are unclear.
399     GStrIdx GetUniqueMethod(GStrIdx) const;
400     bool IsDevirtualListEmpty() const;
401     void DumpDevirtualList(const std::string &outputFileName) const;
402     void ReadDevirtualList(const std::string &inputFileName);
403     MapleAllocator alloc;
404     MIRModule *mirModule;
405     // Map from class name to klass. Use name as the key because the type
406     // information is incomplete, e.g.
407     // method to class link, e.g.
408     //    class A { void foo(); void bar(); }
409     //    class B extends A { void foo(); }
410     //    In this case, there is no link from B.bar to B in the maple file.
411     MapleMap<GStrIdx, Klass *> strIdx2KlassMap;
412     // Map from a virtual method name to its corresponding real method name
413     // This is used for devirtualization and has to be built with a closed-world view
414     MapleMap<GStrIdx, GStrIdx> vfunc2RfuncMap;
415     MapleVector<Klass *> topoWorkList;
416 };
417 }  // namespace maple
418 #endif  // MPL2MPL_INCLUDE_CLASS_HIERARCHY_H
419