Points-To Analysis in Almost Linear TimeSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7TYPESSlide 9TYPING RULESSlide 11Slide 12Slide 13Slide 14ALGORITHM STAGESSlide 16Slide 17Slide 18Slide 19Slide 20ImplementationSlide 22Slide 23Table 2Table 3Related WorkSlide 27Slide 28Slide 29Conclusion & FuturePoints-To Analysis in Almost Linear TimeJosh BaumanJason BartkowiakCSCI 3294OCTOBER 9, 2001OUTLINE INTRODUCTIONTHE ALGORITHM•The Source Language•Types•Typing Rules•Stages of the Algortihm•Processing Constraints•ComplexityIMPLEMENTATIONRELATED WORKCONCLUSIONPoints To Analysis In Linear TimePaper Written by Bjarne Steensgaard(Microsoft Researcher)Written in 1995 / Presented Jan. 1996Flow Insensitive / Linear TimeFastest Interprocedural Algorithm @ time of publicationBased on a NON-Standard Type SystemIMPORTANT ASPECTS OF THE RESEARCH1) A Type System for describing a universally valid storage shape graph (SSG) for a program in Linear Space…2) A Constraint System which gives the algorithm better results…3) A Linear Time Algorithm for POINTS-TO Analysis by solving a constraint system…THE SOURCE LANGUAGETHE SOURCE LANGUAGETHE SYNTAX OF THE LANGUAGE IS AS FOLLOWS:EXAMPLE OF FUNCTIONS IN THE LANGUAGE…..Add1 = fun(x) ( r )xaddone = add(x 1)fi result = Add1(99)TYPESTYPES OF THE LANGUAGENON-STANDARD SET OF TYPES•Types describe:•Location of variables and locations created by dynamic allocations•A Set of Locations as well as possible runtime contents of those locations•A TYPE can be viewed as a NODE in a SSG (Storage Shape Graph)The following productions describe our NONSTANDARD set of types used by our Points-To Analysis:TYPING RULESTYPING RULES•Based on Non-Standard Set of Types•Specify when a program is WELL-TYPEDTYPING RULES (CONT’D.)Before introducing the typing rules we must present the notion of partial ordering and why it is important to the language’s typing rules…..“obvious” typing ruleTYPING RULE (W/PARTIAL ORDERING)TYPING RULESEXPLANATION OF A STORAGE SHAPE GRAPH (SSG)NOTE: TYPING SYSTEM ALLOWS ONLY ONE OUTGOING EDGE (TYPE VARIABLE CAN NOT BE ASSOCIATED WITH MORE THAN ONE TYPE)ALGORITHM STAGESALGORITHM STAGES•Start w/ assumption that all variables are described by diff. typesInitially type of all variables is : Type Variable consists of an equivalence class representative (ECR) with associated type info.•Merge Types as necessary to ensure WELL-TYPEDNESSJoining two types will NEVER make a statement that was well-typed no longer be well-typed…AND…when all program statements are WELL-TYPED, the program is WELL-TYPEDPROCESSING CONSTRAINTSType of Constraint : Inequality Constraint If the “Left Hand Side” type variable is associated with type other than bottom, then two type variables MUST be joined to meet the constraint.If “Left Hand Side” type variable is associated with “bottom” , then there is no need to join the two variables at this time…INFERENCE RULESCOMPLEXITYSpace Cost = # of ECR’s + # of JOIN operationsInitial # of ECR’s – proportional to # of variables in the programTime Cost - depends on “cost” of traversing statements of the program, “cost” of creating ECR’s and types, the “cost” of performing JOIN operations, and the “cost” of find operations on ECR’sImplementation•Written in Scheme •Run time is linearImplementation• Table 1- All variables are included•Table 2 - Some variables taken away•Table 3 - Optimized form of Table 2Table 1Table 2Table 3Related Work•Henglein - used type inference •Weihl - points-to analysis is closest representedRelated WorkFlow-sensitive analyses•Chase and Ruf’s algorithm -interprocedural data give polynomial time •Emami - Exponential time•Wilson and Lam - Exponential TimeRelated Work•Alias Analysis - Builds and maintains a list of access path expression that may evaluate to the same location.•Context sensitive - Assumes runtime model that makes allocation regions explicit Related WorkRelated Work• Andersen – •Non-sensitive = O(A2), A is the # of abstract locations.•Sensitive = O(A4)•Compared to our solution, which is O(A)Conclusion & Future•Almost linear time•Problems•Future - Greater