Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis

Keywords

Slicing, Abstract interpretation, Program slicing, Invariant (physics), Computer science

References

• Convenient User Annotations for a WCET ToolChristian Ferdinand, Reinhold Heckmann, Henrik Theiling — 2003
• Comparing the Galois Connection and Widening/Narrowing Approaches to Abstract InterpretationPatrick Cousot, Radhia Cousot — 1992
• A Modular Tool Architecture for Worst-Case Execution Time AnalysisAndreas Ermedahl — 2008
• Supporting Timing Analysis by Automatic Bounding of Loop IterationsChristopher Healy, Mikael Sjödin, V. Rustagi — 2000
• Experiences from Applying WCET Analysis in Industrial SettingsJan Gustafsson, Andreas Ermedahl — 2007
• Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis Using Abstract ExecutionJan Gustafsson, Andreas Ermedahl, Christer Sandberg — 2006
• Static analysis of arithmetical congruencesPhilippe Granger — 1989
• Abstract interpretationPatrick Cousot, Radhia Cousot — 1977
• Faster WCET flow analysis by program slicingChrister Sandberg, Andreas Ermedahl, Jan Gustafsson — 2006
• Towards a flow analysis for embedded system C programsJan Gustafsson, Andreas Ermedahl, Björn Lisper — 2005
• Advanced Compiler Design and ImplementationSteven S. Muchnick — 1997
• The program dependence graph and its use in optimizationJeanne Ferrante, Karl J. Ottenstein, Joe Warren — 1984
• Program slicingKeith Gallagher, David Binkley — 2008
• Interprocedural slicing using dependence graphsSusan Horwitz, Thomas Reps, David Binkley — 1990
• RETROSPECTIVE: Interprocedural Slicing Using Dependence Graphs
• INTERPRETATION : ‘A UNIFIED LATTICE MODEL FOR STATIC ANALYSIS OF PROGRAMS BY CONSTRUCTION OR APPROXIMATIONP. Cousot, R. Cousot

Cited by

• Accurate analysis of memory latencies for WCET estimationRoman Bourgade, Clément Ballabriga, Hugues Cassé — 2008
• A Formally Verified WCET Estimation ToolAndré Maroneze, Sandrine Blazy, David Pichardie — 2014
• Worst-Case Timing Estimation and Architecture Exploration in Early Design PhasesStefana Nenova, Daniel L. Kastner — 2009
• Static Analysis on Executable Code : A SurveyStefan Bygde — 2011
• Static Program Analysis for Real-Time and Embedded SystemsBjörn Lisper — 2011
• Improved precision in polyhedral analysis with wrappingStefan Bygde, Björn Lisper, Niklas Holsti — 2017
• Multi-architecture Value Analysis for Machine CodeHugues Cassé, Florian Birée, Pascal Sainrat — 2013
• Static WCET Analysis Based on Abstract Interpretation and Counting of ElementsStefan Bygde — 2010
• Deriving WCET Bounds by Abstract ExecutionAndreas Ermedahl, Jan Gustafsson, Björn Lisper — 2011
• Analysing the transformability from Action Language for fUML to ALFJean Malm, Jonas Skoog — 2015
• Software analysis methods for resource-sensitive systemsRody Kersten — 2015
• A mathematical approach towards hardware designGustafsson, Jan, Betts, Adam, Ermedahl, Andreas — 2010
• Towards Adaptable Control Flow Segmentation for measurement-Based Execution Time AnalysisMichael Zolda, Sven Bünte, Raimund Kirner — 2009
• Grid domains for analysing softwareK. Dobson — 2008
• An Overview of Approaches Towards the Timing Analysability of Parallel ArchitectureChristine Rochange — 2011
• ResAna: a resource analysis toolset for (real‐time) JAVARody Kersten, B.E. van Gastel, Olha Shkaravska — 2014
• Ranking Functions for Loops with Disjunctive Exit-ConditionsRody Kersten, M.C.J.D. van Eekelen — 2011
• CLAPP: characterizing loops in Android applicationsYanick Fratantonio, Aravind Machiry, Antonio Bianchi — 2015
• Modeling flow information of loops using compositional condition of controlsSaeed Parsa, Mehdi Sakhaei-nia — 2015
• Mesh independent loop fusion for unstructured mesh applicationsCarlo Bertolli, Adam Betts, Paul H. J. Kelly — 2012

Related papers

• The worst-case execution-time problem—overview of methods and survey of toolsReinhard Wilhelm, Jakob Engblom, Andreas Ermedahl — 2008
• Abstract interpretationPatrick Cousot, Radhia Cousot — 1977
• Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis Using Abstract ExecutionJan Gustafsson, Andreas Ermedahl, Christer Sandberg — 2006
• Data-Flow Based Detection of Loop BoundsChristoph Cullmann, Florian Martin — 2007
• Static Loop Bound Analysis of C Programs Based on Flow Analysis and Abstract InterpretationMarianne de Michiel, Armelle Bonenfant, Hugues Cassé — 2008
• A Fast and Precise Static Loop Analysis Based on Abstract Interpretation, Program Slicing and Polytope ModelsDaniel Cordes, Heiko Falk, Peter Marwedel — 2009
• Supporting Timing Analysis by Automatic Bounding of Loop IterationsChristopher Healy, Mikael Sjödin, V. Rustagi — 2000
• Automatic discovery of linear restraints among variables of a programPatrick Cousot, Nicolas Halbwachs — 1978
• Faster WCET flow analysis by program slicingChrister Sandberg, Andreas Ermedahl, Jan Gustafsson — 2006