• 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 char kJavaLangNoMethodStr[] = "Ljava_2Flang_2FNoSuchMethodException_3B";
41 constexpr uint32 kClassReference =
42     (kClassSoftreference | kClassWeakreference | kClassCleaner | kClassFinalizereference | kClassPhantomreference);
43 
44 bool IsSystemPreloadedClass(const std::string &className);
45 
46 // Klass is the basic node for building class hierarchy
47 class Klass {
48 public:
49     struct KlassComparator {
operatorKlassComparator50         bool operator()(const Klass *lhs, const Klass *rhs) const
51         {
52             CHECK_NULL_FATAL(rhs);
53             CHECK_NULL_FATAL(lhs);
54             return lhs->GetKlassName() < rhs->GetKlassName();
55         }
56     };
57 
58     Klass(MIRStructType *type, MapleAllocator *alc);
59     ~Klass() = default;
60 
61     // Return true if Klass represents an interface
IsInterface()62     bool IsInterface() const
63     {
64         return structType->GetKind() == kTypeInterface;
65     }
66 
IsInterfaceIncomplete()67     bool IsInterfaceIncomplete() const
68     {
69         return structType->GetKind() == kTypeInterfaceIncomplete;
70     }
71 
72     // Return true if Klass represents a normal java class
IsClass()73     bool IsClass() const
74     {
75         return structType->GetKind() == kTypeClass;
76     }
77 
IsClassIncomplete()78     bool IsClassIncomplete() const
79     {
80         return structType->GetKind() == kTypeClassIncomplete;
81     }
82 
83     // Return true if found in the member methods
84     bool IsKlassMethod(const MIRFunction *func) const;
85     // Return MIRFunction if has method
86     const MIRFunction *HasMethod(const std::string &funcname) const;
GetMethods()87     const MapleList<MIRFunction *> &GetMethods() const
88     {
89         return methods;
90     }
91 
GetMethod(GStrIdx idx)92     const MIRFunction *GetMethod(GStrIdx idx) const
93     {
94         MapleMap<GStrIdx, MIRFunction *>::const_iterator it = strIdx2Method.find(idx);
95         return it != strIdx2Method.end() ? it->second : nullptr;
96     }
GetKlassNameStrIdx()97     GStrIdx GetKlassNameStrIdx() const
98     {
99         return structType->GetNameStrIdx();
100     }
101 
GetKlassName()102     const std::string &GetKlassName() const
103     {
104         return structType->GetName();
105     }
106 
GetTypeIdx()107     TyIdx GetTypeIdx() const
108     {
109         return structType->GetTypeIndex();
110     }
111 
GetMIRStructType()112     MIRStructType *GetMIRStructType() const
113     {
114         return structType;
115     }
116 
GetMIRClassType()117     MIRClassType *GetMIRClassType() const
118     {
119         CHECK_FATAL(IsClass() || IsClassIncomplete(), "must");
120         return static_cast<MIRClassType *>(structType);
121     }
122 
GetMIRInterfaceType()123     MIRInterfaceType *GetMIRInterfaceType() const
124     {
125         CHECK_FATAL(IsInterface() || IsInterfaceIncomplete(), "must be");
126         return static_cast<MIRInterfaceType *>(structType);
127     }
128 
HasSuperKlass()129     bool HasSuperKlass() const
130     {
131         return !superKlasses.empty();
132     }
133 
HasSubKlass()134     bool HasSubKlass() const
135     {
136         return !subKlasses.empty();
137     }
138 
HasImplementInterfaces()139     bool HasImplementInterfaces() const
140     {
141         return !implInterfaces.empty();
142     }
143 
144     bool ImplementsKlass() const;
SetFlag(uint32 flag)145     void SetFlag(uint32 flag)
146     {
147         flags |= flag;
148     }
149 
GetFlag(uint32 flag)150     uint32 GetFlag(uint32 flag) const
151     {
152         return flags & flag;
153     }
154 
HasFlag(uint32 flag)155     bool HasFlag(uint32 flag) const
156     {
157         return GetFlag(flag) != 0;
158     }
159 
IsExceptionKlass()160     bool IsExceptionKlass() const
161     {
162         return HasFlag(kClassIsExceptionKlass);
163     }
164 
SetExceptionKlass()165     void SetExceptionKlass()
166     {
167         SetFlag(kClassIsExceptionKlass);
168     }
169 
HasFinalizer()170     bool HasFinalizer() const
171     {
172         return HasFlag(kClassHasFinalizer);
173     }
174 
SetHasFinalizer()175     void SetHasFinalizer()
176     {
177         SetFlag(kClassHasFinalizer);
178     }
179 
HasNativeMethod()180     bool HasNativeMethod() const
181     {
182         return hasNativeMethods;
183     }
184 
SetHasNativeMethod(bool flag)185     void SetHasNativeMethod(bool flag)
186     {
187         hasNativeMethods = flag;
188     }
189 
IsReference(uint32 flag)190     bool IsReference(uint32 flag) const
191     {
192         return HasFlag(flag);
193     }
194 
IsReference()195     bool IsReference() const
196     {
197         return HasFlag(kClassReference);
198     }
199 
IsArray()200     bool IsArray() const
201     {
202         return (structType->GetName().find(JARRAY_PREFIX_STR) == 0);
203     }
204 
IsPrivateInnerAndNoSubClass()205     bool IsPrivateInnerAndNoSubClass() const
206     {
207         return isPrivateInnerAndNoSubClassFlag;
208     }
209 
SetPrivateInnerAndNoSubClass(bool flag)210     void SetPrivateInnerAndNoSubClass(bool flag)
211     {
212         isPrivateInnerAndNoSubClassFlag = flag;
213     }
214 
GetNeedDecoupling()215     bool GetNeedDecoupling() const
216     {
217         return needDecoupling;
218     }
219 
SetNeedDecoupling(bool flag)220     void SetNeedDecoupling(bool flag)
221     {
222         needDecoupling = flag;
223     }
224 
GetClinit()225     const MIRFunction *GetClinit() const
226     {
227         return clinitMethod;
228     }
SetClinit(MIRFunction * m)229     void SetClinit(MIRFunction *m)
230     {
231         clinitMethod = m;
232     }
233 
GetClassInitBridge()234     MIRSymbol *GetClassInitBridge() const
235     {
236         return classInitBridge;
237     }
238 
SetClassInitBridge(MIRSymbol * s)239     void SetClassInitBridge(MIRSymbol *s)
240     {
241         classInitBridge = s;
242     }
243 
244     // Return the function defined in the current class, or the inherited
245     // function if it is not defined in the current class.
246     MIRFunction *GetClosestMethod(GStrIdx) const;
247     // This for class only, which only has 0 or 1 super class
248     Klass *GetSuperKlass() const;
GetSuperKlasses()249     const MapleList<Klass *> &GetSuperKlasses() const
250     {
251         return superKlasses;
252     }
253 
GetSubKlasses()254     const MapleSet<Klass *, KlassComparator> &GetSubKlasses() const
255     {
256         return subKlasses;
257     }
258 
GetImplKlasses()259     const MapleSet<Klass *, KlassComparator> &GetImplKlasses() const
260     {
261         return implKlasses;
262     }
263 
GetImplInterfaces()264     const MapleSet<Klass *, KlassComparator> &GetImplInterfaces() const
265     {
266         return implInterfaces;
267     }
268 
269     // Return a vector of possible functions
270     MapleVector<MIRFunction *> *GetCandidates(GStrIdx mnameNoklassStrIdx) const;
271     // Return the unique method if there is only one target virtual function.
272     // Return nullptr if there are multiple targets.
273     MIRFunction *GetUniqueMethod(GStrIdx mnameNoklassStrIdx) const;
AddSuperKlass(Klass * superclass)274     void AddSuperKlass(Klass *superclass)
275     {
276         superKlasses.push_back(superclass);
277     }
278 
AddSubKlass(Klass * subclass)279     void AddSubKlass(Klass *subclass)
280     {
281         subKlasses.insert(subclass);
282     }
283 
AddImplKlass(Klass * implclass)284     void AddImplKlass(Klass *implclass)
285     {
286         implKlasses.insert(implclass);
287     }
288 
AddImplInterface(Klass * interfaceKlass)289     void AddImplInterface(Klass *interfaceKlass)
290     {
291         implInterfaces.insert(interfaceKlass);
292     }
293 
AddMethod(MIRFunction * func)294     void AddMethod(MIRFunction *func)
295     {
296         methods.push_front(func);
297         strIdx2Method.insert({func->GetBaseFuncNameWithTypeStrIdx(), func});
298     }
299 
300     void DelMethod(const MIRFunction &func);
301     // Collect the virtual methods from parent class and interfaces
302     void CountVirtMethTopDown(const KlassHierarchy &kh);
303     // Count the virtual methods for subclasses and merge with itself
304     void CountVirtMethBottomUp();
305     void Dump() const;
306 
307 private:
308     void DumpKlassImplInterfaces() const;
309     void DumpKlassImplKlasses() const;
310     void DumpKlassSuperKlasses() const;
311     void DumpKlassSubKlasses() const;
312     void DumpKlassMethods() const;
313     bool IsVirtualMethod(const MIRFunction &func) const;
314     // structType can be class or interface
315     MIRStructType *structType;
316     MapleAllocator *alloc;
317     // A collection of super classes.
318     // superklass is nullptr if it is not defined in the module.
319     MapleList<Klass *> superKlasses;
320     // A collection of sub classes
321     MapleSet<Klass *, KlassComparator> subKlasses;
322     // a collection of classes which implement the current interface
323     MapleSet<Klass *, KlassComparator> implKlasses;
324     // a collection of interfaces which is implemented by the current klass
325     MapleSet<Klass *, KlassComparator> implInterfaces;
326     // A collection of class member methods
327     MapleList<MIRFunction *> methods;
328     // A mapping to track every method to its baseFuncNameWithType
329     MapleMap<GStrIdx, MIRFunction *> strIdx2Method;
330     MIRFunction *clinitMethod = nullptr;
331     MIRSymbol *classInitBridge = nullptr;
332     // A mapping to track possible implementations for each virtual function
333     MapleMap<GStrIdx, MapleVector<MIRFunction *> *> strIdx2CandidateMap;
334     // flags of this class.
335     // Now contains whether this class is exception, reference or has finalizer.
336     uint32 flags = 0;
337     bool isPrivateInnerAndNoSubClassFlag = false;
338     bool hasNativeMethods = false;
339     bool needDecoupling = true;
340 };
341 
342 // Some well known types like java.lang.Object. They may be commonly referenced.
343 // j - java
344 // jl - java lang
345 // jlr - java lang reflect
346 class WKTypes {
347 public:
348     class Util {
349     public:
350         static bool MayRefString(const BaseNode &n, MIRType &type);
351         static bool MayRefMeta(const BaseNode &n, MIRType &type);
352         static bool MayNotRefCyclicly(const BaseNode &n, MIRType &type);
GetJavaLangObjectType()353         static MIRType *GetJavaLangObjectType()
354         {
355             return javaLangObject;
356         }
357 
358     private:
359         static bool NotCyclicType(MIRType &type, std::set<MIRType *> &workList);
360     };
361     static void Init();
362 
363 private:
364     static MIRType *javaLangObject;
365     static MIRType *javaLangString;
366     static MIRType *javaLangObjectSerializable;
367     static MIRType *javaLangComparable;
368     static MIRType *javaLangCharSequence;
369     static MIRType *javaLangClass;
370     static MIRType *javaLangRefGenericDeclaration;
371     static MIRType *javaLangRefAnnotatedElement;
372     static MIRType *javaLangRefType;
373     static MIRType *javaLangRefMethod;
374     static MIRType *javaLangRefExecutable;
375     static MIRType *javaLangRefAccessibleObject;
376     static MIRType *javaLangRefMember;
377     static MIRType *javaLangRefField;
378     static MIRType *javaLangRefConstructor;
379 };
380 
381 // data structure to represent class information defined in the module
382 class KlassHierarchy : public AnalysisResult {
383 public:
384     KlassHierarchy(MIRModule *mirmodule, MemPool *memPool);
385     virtual ~KlassHierarchy() = default;
386 
387     // Get a class. Return nullptr it does not exist.
388     Klass *GetKlassFromStrIdx(GStrIdx strIdx) const;
389     Klass *GetKlassFromTyIdx(TyIdx tyIdx) const;
390     Klass *GetKlassFromFunc(const MIRFunction *func) const;
391     Klass *GetKlassFromName(const std::string &name) const;
392     Klass *GetKlassFromLiteral(const std::string &name) const;
GetKlasses()393     const MapleMap<GStrIdx, Klass *> &GetKlasses() const
394     {
395         return strIdx2KlassMap;
396     }
397 
398     // Get lowest common ancestor for two classes
399     Klass *GetLCA(Klass *klass1, Klass *klass2) const;
400     TyIdx GetLCA(TyIdx ty1, TyIdx ty2) const;
401     GStrIdx GetLCA(GStrIdx str1, GStrIdx str2) const;
402     const std::string &GetLCA(const std::string &name1, const std::string &name2) const;
403     // 1/0/-1: true/false/unknown
404     int IsSuperKlass(TyIdx superTyIdx, TyIdx baseTyIdx) const;
405     bool IsSuperKlass(const Klass *super, const Klass *base) const;
406     bool IsSuperKlassForInterface(const Klass *super, const Klass *base) const;
407     bool IsInterfaceImplemented(Klass *interface, const Klass *base) const;
408     bool UpdateFieldID(TyIdx baseTypeIdx, TyIdx targetTypeIdx, FieldID &fldID) const;
409     // return true if class, its super or interfaces have at least one clinit function
410     bool NeedClinitCheckRecursively(const Klass &kl) const;
411 
412     void CountVirtualMethods() const;
413     void BuildHierarchy();
414     void Dump() const;
415 
GetTopoSortedKlasses()416     const MapleVector<Klass *> &GetTopoSortedKlasses() const
417     {
418         return topoWorkList;
419     }
420 
GetModule()421     const MIRModule *GetModule() const
422     {
423         return mirModule;
424     }
425     static bool traceFlag;
426 
427 private:
428     // New all klass
429     void AddKlasses();
430     // Add superklass/subclass edge and class methods for each class
431     void AddKlassRelationAndMethods();
432     void TagThrowableKlasses();
433     // Connect all class<->interface edges based on Depth-First Search
434     void UpdateImplementedInterfaces();
435     // Get a vector of parent class and implementing interface
436     void GetParentKlasses(const Klass &klass, std::vector<Klass *> &parentKlasses) const;
437     // Get a vector of child class and implemented class
438     void GetChildKlasses(const Klass &klass, std::vector<Klass *> &childKlasses) const;
439     void ExceptionFlagProp(Klass &klass);
440     Klass *AddClassFlag(const std::string &name, uint32 flag);
441     int GetFieldIDOffsetBetweenClasses(const Klass &super, const Klass &base) const;
442     void TopologicalSortKlasses();
443     void MarkClassFlags();
444     // Return the unique method if there is only one target virtual function.
445     // Return 0 if there are multiple targets or the targets are unclear.
446     GStrIdx GetUniqueMethod(GStrIdx) const;
447     bool IsDevirtualListEmpty() const;
448     void DumpDevirtualList(const std::string &outputFileName) const;
449     void ReadDevirtualList(const std::string &inputFileName);
450     MapleAllocator alloc;
451     MIRModule *mirModule;
452     // Map from class name to klass. Use name as the key because the type
453     // information is incomplete, e.g.
454     // method to class link, e.g.
455     //    class A { void foo(); void bar(); }
456     //    class B extends A { void foo(); }
457     //    In this case, there is no link from B.bar to B in the maple file.
458     MapleMap<GStrIdx, Klass *> strIdx2KlassMap;
459     // Map from a virtual method name to its corresponding real method name
460     // This is used for devirtualization and has to be built with a closed-world view
461     MapleMap<GStrIdx, GStrIdx> vfunc2RfuncMap;
462     MapleVector<Klass *> topoWorkList;
463 };
464 }  // namespace maple
465 #endif  // MPL2MPL_INCLUDE_CLASS_HIERARCHY_H
466