www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4379] New: DMD chokes on large nested loop over tuple.

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379

           Summary: DMD chokes on large nested loop over tuple.
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: dsimcha yahoo.com


--- Comment #0 from David Simcha <dsimcha yahoo.com> 2010-06-23 19:42:43 PDT ---
Requires at least 14 elements to fail.

import std.stdio, std.typetuple;

alias TypeTuple!(1,2,3,4,5,6,7,8,9,10,11,12,13,14) nums;

void main() {
    foreach(num1; nums) {
        foreach(num2; nums) {
            writeln(num1, "  ", num2);
        }
    }
}

Error Message (in the reduced test case) :  
Internal error: ..\ztc\blockopt.c 619

In the original case that I isolated this from, the compiler would eat ~300 MB
of memory and hang.  I can't reproduce this symptom in a reduced test case
because the compiler crashes first, so I'm not sure whether the two symptoms
are related.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 23 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379



--- Comment #1 from David Simcha <dsimcha yahoo.com> 2010-06-23 19:57:24 PDT ---
Actually, this appears to be related to the total size of the loop body being
generated at compile time.  Nesting has nothing to do with it.  The cutoff
appears to be (of all numbers) 198 elements.

import std.stdio, std.typetuple;

// CTFE function to generate a huge tuple.
string generateHugeTuple() {
    string ret = "alias TypeTuple!(";

    foreach(outer; 0..198) {
        ret ~= '1';
        ret ~= ',';
    }

    ret = ret[0..$ - 1];  // Drop last ,
    ret ~= ") LetterTuple;";
    return ret;
}

mixin(generateHugeTuple());

void main() {
    foreach(letter; LetterTuple) {
        writeln(letter);
    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 23 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379


nfxjfg gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nfxjfg gmail.com
           Severity|normal                      |regression


--- Comment #2 from nfxjfg gmail.com 2010-06-24 05:35:43 PDT ---
Can't reproduce it with 2.046.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 24 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379


David Simcha <dsimcha yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|regression                  |normal


--- Comment #3 from David Simcha <dsimcha yahoo.com> 2010-06-24 19:42:08 PDT ---
I was able to reproduce this on 2.046.  Try making the tuples bigger.  Maybe
it's at least somewhat nondeterministic, a memory allocation bug or something.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 24 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug yahoo.com.au
            Summary|DMD chokes on large nested  |ICE(blockopt.c): foreach
                   |loop over tuple.            |over huge tuple, only with
                   |                            |-O


--- Comment #4 from Don <clugdbug yahoo.com.au> 2010-06-25 00:00:21 PDT ---
Only occurs when compiled with -O. It's an optimizer issue.
This hits the limit of the optimizer, which loops a maximum of 200 times,
hence the ICE at 198 elements. Bug 3681 also hits the same limit, but for a
different reason. Actually I think the problem is in the glue layer (maybe in
UnrolledStatement?) because the backend shouldn't need to do much work in this
example.


Reduced test case
----------
template BigTuple(U...) {
    alias U BigTuple;
}

alias
BigTuple!(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1) Tuple4379;

void bug4379() {
    foreach(x; Tuple4379) {    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch


--- Comment #5 from Don <clugdbug yahoo.com.au> 2010-11-22 01:26:45 PST ---
This turns out to be very simple. When merging blocks together, we need to
allow one pass per block, since it only merges one block per pass.
In the test case, there are more than 200 blocks, and they all get merged into
one.


PATCH:
blockopt.c, blockopt(), line 595

void blockopt(int iter)
{   block *b;
    int count;

    if (OPTIMIZER)
    {
+        int iterationLimit = 200;
+        if (iterationLimit < numblks)
+            iterationLimit = numblks;
        count = 0;
        do
        {

and line 622
            do
            {
                compdfo();              /* compute depth first order (DFO) */
                elimblks();             /* remove blocks not in DFO      */
-                assert(count < 200);
+                assert(count < iterationLimit);
                count++;
            } while (mergeblks());      /* merge together blocks         */

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 22 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |bugzilla digitalmars.com
         Resolution|                            |FIXED


--- Comment #6 from Walter Bright <bugzilla digitalmars.com> 2010-12-26
22:51:51 PST ---
http://www.dsource.org/projects/dmd/changeset/820

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 26 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4379


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jens.k.mueller gmx.de


--- Comment #7 from Don <clugdbug yahoo.com.au> 2011-03-03 00:39:59 PST ---
*** Issue 5656 has been marked as a duplicate of this issue. ***

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 03 2011