Summary

Compiling some files may cause infinite optimization loops, eating all available memory

Metadata

Attachments

Description

chicken (master -- e5f341a81cb2d5b8c4f7d8eedabcd35c1ecb7281) dies with a segmentation fault when attempting to compile the attached file (srfi-14-test.scm).

While compiling, it uses more than 2GB of RAM. It crashed after running for more than 9 minutes on a 2.4GHz processor. The system is Linux x86.

I tried building chicken with DEBUGBUILD=1 and running it under gdb, but it didn't crash in more than 10 hours, when I stopped it (it was still using 2GB of RAM).

Changes and comments

[2012-06-20 12:28:52 UTC] mario attached srfi-14-test.scm (description=srfi-14-test.scm)

[2012-06-30 16:14:12 UTC] sjamaan set milestone to 4.8.0

[2012-06-30 16:14:12 UTC] sjamaan changed summary

[2012-06-30 16:14:12 UTC] sjamaan wrote:

csc -debug o srfi-14.scm shows that it gets stuck contracting the same procedures over and over.

This is potentially a severe bug affecting other cases too so I'm promoting this to milestone 4.8.0.

[2012-07-01 16:36:09 UTC] sjamaan wrote:

It's not an infinite loop, but it keeps contracting the same procedure more than once. If you rip out all the tests under "shiver's tests" the problem goes away. Put some of them back, it takes longer. Put more back, it takes even longer etc.

It's not the macro either. Looks like the cond is causing the problem. Looks like an O(n^2) behavior with n being the number of branches in the cond.

Here's a simplified case that clearly shows what's going on:

 #!scm
 (cond ((not (= 1 2)) (print 2))
       ((not (= 5 6)) (print 4))
       (else (print 'nothing)))



 csc -debug o test.scm
 Removed `not' forms: 2 
 contracted procedure: k31 
 folded constant expression: (= (quote 5) (quote 6)) 
 contracted procedure: k22 
 contracted procedure: k31 
 folded constant expression: (= (quote 5) (quote 6)) 
 folded constant expression: (= (quote 1) (quote 2)) 
 replaced variables: 21 
 contracted procedure: k22 
 removed binding forms: 2 
 substituted constant variable: r23 
 contracted procedure: k31 
 removed binding forms: 4 
 removed conditional forms: 1 
 removed binding forms: 1

Note the double occurrance of the folded expression, which is probably a result of the fact that the procedure k31 that's generated by cond's expansion is contracted twice. Add a line and you get three entries for the newly added line:

 #!scm
 (cond ((not (= 1 2)) (print 2))
       ((not (= 5 6)) (print 4))
       ((not (= 7 8)) (print 5))
       (else (print 'nothing)))



 csc -debug o test.scm
 Removed `not' forms: 3 
 contracted procedure: k40 
 folded constant expression: (= (quote 7) (quote 8)) 
 contracted procedure: k31 
 contracted procedure: k40 
 folded constant expression: (= (quote 7) (quote 8)) 
 folded constant expression: (= (quote 5) (quote 6)) 
 contracted procedure: k22 
 contracted procedure: k40 
 folded constant expression: (= (quote 7) (quote 8)) 
 contracted procedure: k31 
 contracted procedure: k40 
 folded constant expression: (= (quote 7) (quote 8)) 
 folded constant expression: (= (quote 5) (quote 6)) 
 folded constant expression: (= (quote 1) (quote 2)) 
 replaced variables: 53 
 contracted procedure: k22 
 removed binding forms: 2 
 substituted constant variable: r23 
 contracted procedure: k31 
 removed binding forms: 4 
 removed conditional forms: 1 
 removed binding forms: 1

And another line:

 #!scm
 (cond ((not (= 1 2)) (print 2))
       ((not (= 5 6)) (print 4))
       ((not (= 7 8)) (print 5))
       ((not (= 9 10)) (print 6))
       (else (print 'nothing)))



 csc -debug o test.scm
 Removed `not' forms: 4 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k40 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 contracted procedure: k31 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k40 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 folded constant expression: (= (quote 5) (quote 6)) 
 contracted procedure: k22 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k40 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 contracted procedure: k31 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k40 
 contracted procedure: k49 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 folded constant expression: (= (quote 5) (quote 6)) 
 folded constant expression: (= (quote 1) (quote 2)) 
 replaced variables: 117 
 contracted procedure: k22 
 removed binding forms: 2 
 substituted constant variable: r23 
 contracted procedure: k31 
 removed binding forms: 4 
 removed conditional forms: 1 
 removed binding forms: 1

Interestingly, it does not happen when you remove the "not".

[2012-07-01 16:38:57 UTC] sjamaan wrote:

Further simplification: if you convert it to a nested if the problem still occurs:

 #!scm
 (if (not (= 1 2))
     (print 2)
     (if (not (= 5 6))
         (print 4)
         (if (not (= 7 8))
             (print 5)
             (if (not (= 9 10))
                 (print 6)
                 (print 'nothing)))))



 $ csc -debug o test.scm
 Removed `not' forms: 4 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k37 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 contracted procedure: k28 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k37 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 folded constant expression: (= (quote 5) (quote 6)) 
 contracted procedure: k19 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k37 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 contracted procedure: k28 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 contracted procedure: k37 
 contracted procedure: k46 
 folded constant expression: (= (quote 9) (quote 10)) 
 folded constant expression: (= (quote 7) (quote 8)) 
 folded constant expression: (= (quote 5) (quote 6)) 
 folded constant expression: (= (quote 1) (quote 2)) 
 replaced variables: 117 
 contracted procedure: k19 
 removed binding forms: 2 
 substituted constant variable: r20 
 contracted procedure: k28 
 removed binding forms: 4 
 removed conditional forms: 1 
 removed binding forms: 1

[2012-07-01 18:21:53 UTC] sjamaan wrote:

Could this be due to the fact that perform-pre-optimization! mutates the nodes? Perhaps this creates an inconsistency between the analysis database and the node tree. Felix?

[2012-07-02 13:57:23 UTC] felix changed status from new to assigned

[2012-07-02 13:57:23 UTC] felix set owner to felix

[2012-07-02 13:57:23 UTC] felix wrote:

Multiple contractions of the same function is already incorrect ("contraction" means inlining of a function called once). I think the real problem are nested contractions. In the last example above, `k46` is nested in `k37`. The former gets contracted, then the latter (in the same optimization pass). In this case it seems to happens repeatedly. For inlining this case (an inlined procedure being the target of additional inlining) is taken care of by having the `inline-target` db entry - we probably need this (or something similar) for contraction, too.

[2012-07-02 20:40:34 UTC] sjamaan wrote:

Do multiple contractions of the same form even happen for programs without perform-pre-optimization!?

[2012-07-02 20:41:53 UTC] sjamaan wrote:

In other words, do you think the bug is in the parts of the optimizer that handle contractions rather than perform-pre-optimization!?

[2012-07-03 11:32:19 UTC] felix wrote:

Replying to sjamaan: > In other words, do you think the bug is in the parts of the optimizer that handle contractions rather than perform-pre-optimization!?

I do, yes. There is a check for the `inline-target` db entry, which is done for procedures where inlining takes place. I think this must also be done for contractions, but I have to try it out first (real soon).

[2012-07-06 08:48:46 UTC] felix wrote:

This is actually not related to nested contractions or inlining conflicts. The problem appears to be that copy-propagation inserts references to contracted procedures.

[2012-07-06 15:31:41 UTC] mario changed status from assigned to closed

[2012-07-06 15:31:41 UTC] mario set resolution to fixed

[2012-07-06 15:31:41 UTC] mario wrote:

Fixed by 285f53dbca729cffb4c4d9ee84e4ba893c882546

[2012-09-24 21:47:48 UTC] felix changed milestone from 4.8.0 to 4.9.0

[2012-09-24 21:47:48 UTC] felix wrote:

Milestone 4.8.0 deleted