Skip to content
  1. Dec 07, 2023
  2. Dec 06, 2023
  3. Dec 05, 2023
    • Carlos Galindo's avatar
      Slicing algorithms unification and overhaul. · 8fb45278
      Carlos Galindo authored
      Main motivation: AdaptedStandardAlgorithm is not an equivalent context-insensitive version of StandardAlgorithm, because it groups nodes as if it were slicing the SDG.
      Secondary motivation: apply the same traversal rules (if applicable) to all slicing algorithms, instead of having different versions that haven't been updated since they stopped being used in benchmarks.
      - Introduced the OnePassStandardAlgorithm, field-insensitive version of OnePassConstrainedAlgorithm.
      - Document all available slicing algorithms and their quirks (javadoc on interface).
      - Unified traversal rules for the EDG on SlicingAlgorithm.
      
      Changes to specific algorithms:
      - StandardAlgorithm, AdaptedStandardAlgorithm: include last edge type in traversal.
      - ConstrainedAlgorithm, OnePassConstrainedAlgorithm:
        - Simplify NodeWork processing and EdgeWork constructor.
        - Upstream types of edges that can't be traversed during SummaryGeneration.
      - ConstrainedAlgorithm: copy changes of commit 523c3112.
      - Pseudo-predicate algorithms: unify conditional traversal on SlicingAlgorithm and simplify both algorithms.
      
      Other, minor changes:
      - Add EDG#clearConstraints, moved from OnePassConstrainedAlgorithm#slice (was commented out)
      - LAST#getResFromNode: add check for null NodeInfo.
      - Documentation
      8fb45278
    • Carlos Galindo's avatar
      OnePassConstrainedAlg: fix two bugs (loop detection and traversed edges) · 523c3112
      Carlos Galindo authored
      - Bug 1: if a loop was detected, but it wasn't an increasing loop, no NodeWork was generated (step 4). In the case of balanced loops (and some decreasing loops), this may lead to incorrect results.
      - Bug 2: inclusion in traversedEdges was conditional on edge type, but it should be based on Constraint type, as that is what determines the PDA analysis' result. Now it doesn't include edges with ignored edge constraints. Previously, this behaviour excluded Summary edges with ListComprehensionConstraints (generated as external in SummaryEdgeGenerator#buildListsNthSummaries).
      - Other changes:
        1. Shortened try-catch looking for StackOverflow
        2. Extracted loop detection from for-loop, adding a check to avoid loop detection if newConstraintsList is empty.
        3. Moved traversedEdges update logic to PDA, as it is closely linked to PDA#isIncreasingLoop.
        4. Reformatted file (whitespace and indentation).
      523c3112
  4. Dec 04, 2023
  5. Nov 30, 2023
  6. Nov 29, 2023
  7. Nov 28, 2023
  8. Nov 23, 2023
  9. Nov 20, 2023
    • Carlos Galindo's avatar
      Work-list based and Reps tabular slicing for recursive programs. · 58d95b2c
      Carlos Galindo authored
      - Worklist approach implemented through a Config flag in SummaryTable.
      - Unconstrained and constrained variantes (TabularAlgorithm & ConstrainedTabularAlgorithm). The constrained version features a limit to the size of the stack.
      - Constrained subsumed variant for efficiency (ConstrainedSubsumedTabularAlgorithm).
      - Efficient EdgeList (linked-list) to store edges visited through a traversal.
      - Bump language level to 16.
      - eKnife cli: added switch to use tabular algorithms.
      - Moved benchmarks out of eKnife and BencherTest.
      58d95b2c
  10. Oct 25, 2023
    • Carlos Galindo's avatar
      Benchmarks for non-recursive tabular slicing. · 4d630beb
      Carlos Galindo authored
      - ️️SummaryTable: actual-out node may none or multiple matching formal-out.
      - EDG, SummaryTable: get and clear methods for stats.
      - EKnife, BencherTest: adapted for benchmarks in which running the benchmark alters the graph itself.
      4d630beb
  11. Oct 19, 2023
    • Carlos Galindo's avatar
      Tabular slicing (v1): non-recursive · 830c6df6
      Carlos Galindo authored
      - Move summary settings from EDGFactory to Config.
      - The EDG now contains a SummaryTable, a map which computes summaries on-the-fly.
      - ConstrainedAlgorithm: now looks up summary edges in SummaryTable.
      - Fixed typo in SummaryEdgeGenerator#generateOnlyExternal.
      830c6df6
Loading