Using Types to Analyze and Optimize Object-Oriented Programs By: Amer DiwanType-Based Alias Analysis (TBAA)TypeDeclTypeDecl ExamplePowerPoint PresentationFieldTypeDeclFieldTypeDecl (cont’d)Slide 8SMTypeRefsSMTypeRefs (cont’d)Slide 11ApplauseSlide 13Slide 14Slide 15SMFieldTypeRefsUsing TBAAPolymorphism through subtypingType Hierarchy AnalysisIntraprocedural Type PropogationIntraprocedural Type Propogation using TBAAInterprocedural Type PropogationSummary of analysisResultsTBAA EvaluationStatic Evaluation of TBAAStatic (cont’d)Slide 28Dynamic Evaluation of TBAADynamic (cont’d)Limit Evaluation on TBAALimit evaluation (cont’d)Method InvocationStatic and Dynamic EvaluationSlide 35Limit Evaluation (cont’d)Slide 37Using Types to Analyze and Optimize Object-Oriented ProgramsBy: Amer DiwanPresented By: Jess Martin, Noah Wallace, and Will von RosenbergType-Based Alias Analysis (TBAA)•Assumes type safe programming language, i.e. Modula-3. •Comparative Analysis of Types and Subtypes•Four Functions (Versions) of TBAA–TypeDecl–FieldTypeDecl–SMTypeRefs–SMFieldTypeRefsTypeDecl•Examine the declared type of AP and assume the AP may reference any object with the same declared type or subtype.TypeDecl Example•Class X{}•Class Y{} : X•Class Z{} : X•Class D{} : Y•Class F{} : ZFieldTypeDecl•Given AP1 and AP2 it returns true if AP1 and AP2 are Aliases •Modula-3 programs may take the addresses of memory locations in only two ways: via the pass-by-reference parameter passing mechanism and the WITH statement.FieldTypeDecl (cont’d)•Identical APs always alias each other.•Two qualified expressions may be aliases if they access the same field in potentially the same object.•A pointer dereference may refer to the same location as a qualified subscripted expression only if their types are compatible and the program may take the address of the qualified or subscripted expression.•In Modula-3, a subscripted expression cannot alias a qualified expression.•Two subscripted expressions are aliases if they may subscript the same array. FieldTypeDecl ignores the actual subscripts.•For all other cases of APs, including two pointer dereferences, FieldTypeDecl uses TypeDecl to determine aliases.FieldTypeDeclClass P{ int a; float b; char c;}Class D{ int e; float g; char f;} : PInt ra[];•P and D?•P.a and D.e?•P.a and ra[i]?•*P.f and ra[i]?•D and D?SMTypeRefs•Selective Type Merging•Produces a TypeRefsTableSMTypeRefs (cont’d)•Initializes Group•Examines all assignment statements, merges <lhs> and <rhs> if types are different.•Filters infeasible aliases from Group, creating asymmetry.SMTypeRefs (cont’d)ApplauseSMTypeRefs (cont’d)SMTypeRefs (cont’d)SMTypeRefsClass Blah{}Class Piglet{}:BlahClass Pooh{}:BlahClass Pinky{}:PigletClass Brain{}:PigletClass Scooby{}:PoohClass Yogi{}:Pooh•T New Blah;•P New Piglet;•F New Pooh;•T = P;•P = F;•T = F;•What are the typeref tables for the three assignments?SMFieldTypeRefs•Fields + Selectively Merge Type References•We use SMTypeRefs instead of TypeDecl in the FieldTypeDecl algorithm•Final version of TBAAUsing TBAA•Redundant Load Elimination–Loop invariant code motion–Common subexpression elimination•Resolving method invocation–Type hierarchy analysis–Intraprocedural type propagation–Intraprocedural type propagation using TBAA–Interprocedural type propagation–Interprocedural type propagation using TBAAPolymorphism through subtyping•Polymorphic – method invocation site calls more than one user procedure at run time.•Monomorphic – method invocation site calls only one user procedure at run time.•A method is resolved if it is identified as being monomorphic.•We wish to resolve all calls and replace them with direct calls.Type Hierarchy Analysis•Simply evaluates all possible overrides (overloads) for a particular function when passed a specific variable type.Intraprocedural Type Propogation•Breaks down types into type events–Allocation–Implicit and explicit type discrimination–Assignment•Complexity O(n*v) where n is number of statements and v is the number of variables in the procedureIntraprocedural Type Propogation using TBAA•When it encounters a pointer dereference, it invokes SMFieldTypeRefs to get the set of locations referenced by the pointer deref•Analysis discovers monomorphic uses of general data structures•Complexity – O(n*(v+NT*NF)), where n is number of statements, v is number of variables, NT is number of types, and NF is number of fieldsInterprocedural Type Propogation•Call graph w/edges for each•Builds work list•Puts functions on work list if new information•Merges parameter types•Interprocedural Type Propogation using TBAA is the same implementationSummary of analysis•Type Hierarchy•Intraprocedural Type Propagation•Intraprocedural Type Propagation using TBAA•Interprocedural Type Propagation•Interprocedural Type Propagation using TBAAResults Evaluates TBAA and Method resolution analyses.Static evaluation Dynamic evaluation Limit evaluationTBAA EvaluationStatic Evaluation of TBAAStatic (cont’d)•FieldType declare is more precise than TypeDecl.•SMFieldTypeRefs offers little added precision. •FieldTypeDecl finds more redundant loads than TypeDecl and SMFieldTypeRefs does not change by any significant amountStatic (cont’d)Dynamic Evaluation of TBAADynamic (cont’d)•Two important points–1) a more precise alias analyses is not necessarily better it depends on how the analyses is used.–2) Static metrics are insufficient by themselves for evaluationLimit Evaluation on TBAA•Optimizations eliminate between 35% - 88% of the RL. •Only 5% or fewer are redundant. •Reveals that TBAA performs as well as any alias analysis could with the RLE and their benchmark.Limit evaluation (cont’d)Method InvocationStatic and Dynamic Evaluation•Type Hierarchy analysis resolves many method invocations•Intraprocedural type propagations resolves very few additional method invocations but removes NIL. •Type propagation is useful for languages that have defined semantics such as Modula-3 or Java •TBAA along with type propagation resolves most of the method invocation in the benchmarks.Limit Evaluation (cont’d)Limit Evaluation (cont’d)•Explicit type tests and cloning combined with aggressive alias analyses may be able to resolve these method invocations. •4 sites are polymorphic but they comprise more