Skip to content
  • Simon Peyton Jones's avatar
    Cure exponential behaviour in the simplifier · a1b753e8
    Simon Peyton Jones authored
    This patch nails a Bad Bug exposed in Trac #13379. Roughly,
    a deeply-nested application like
       f (f (f ....) ) )
    could make the simplifier go exponential -- without producing
    an exponential-sized result!
    
    The reason was that we
      - simplified a (big) function argument
      - then decided to inline the function
      - then preInilneUnconditionally the argument
      - and then re-simplified the big argument
    
    And if the "big argument" itself had a similar structure
    things could get very bad.
    
    Once I'd understood, it was easy to fix:
    
    * See Note Note [Avoiding exponential behaviour] for an overview
    
    * The key change is that Simplify.simplLam now as a case for
      (isSimplified dup). This is what removes the perf bug.
    
    * But I also made simplCast more parsimonious about simplifying,
      avoiding doing so when the coercion is Refl
    
    * And similarly I now try to avoid simplifying arguments
      where possible before applying rules.
      See Note [Trying rewrite rules]
    
    The latter two points tackle common cases, and in those cases make the
    simplifier take fewer iterations.
    a1b753e8