Pointer analysis

For the above program, an idealized, fully precise analysis would compute the following results: (Where X::Y represents the stack allocation holding the local variable Y in the function X.)[7] Context-sensitive, flow-sensitive algorithms achieve higher precision, generally at the cost of some performance, by analyzing each procedure several times, once per context.[10] Three common variants of context-sensitive, flow-insensitive analysis are:[11] In call-site sensitivity, the points-to set of each variable (the set of abstract heap allocations each variable could point to) is further qualified by a context consisting of a list of callsites in the program.The following program demonstrates how call-site sensitivity can achieve higher precision than a flow-insensitive, context-insensitive analysis.Unlike call-site sensitivity, object-sensitivity is non-syntactic or non-local: the context entries are derived during the points-to analysis itself.
A diagram showing how pointer analysis abstracts runtime memory
Flow-insensitive pointer analyses often abstract possible runtime allocations by their allocation site. At runtime, this program creates three separate heap allocations. A flow-insensitive pointer analysis would treat these as a single abstract memory location, leading to a loss of precision.
computer sciencestatic code analysispointersvariablesstorage locationsescape analysisshape analysisalias analysisundecidablestructobjectpolyvarianceSteensgaard's algorithmunion-find data structureabstract interpretationDatalogCompiler optimizationsPeephole optimizationLocal value numberingLoop nest optimizationLoop splittingLoop unrollingLoop unswitchingSoftware pipeliningStrength reductionData-flowanalysisAvailable expressionCommon subexpression eliminationConstant foldingDead storeInduction variable recognition and eliminationLive-variable analysisUpwards exposed usesUse-define chainReaching definitionsGlobal value numberingSparse conditional constant propagationCode generationInstruction schedulingInstruction selectionRegister allocationRematerializationDeforestationTail-call eliminationInterprocedural optimizationBounds-checking eliminationCompile-time function executionDead-code eliminationExpression templatesInline expansionJump threadingPartial evaluationProfile-guided optimizationArray-access analysisControl-flow analysisData-flow analysisDependence analysisValue range analysis