5845 – Regression(2.041) [CTFE] "stack overflow" with recursive ref argument

D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 5845 - Regression(2.041) [CTFE] "stack overflow" with recursive ref argument
Summary: Regression(2.041) [CTFE] "stack overflow" with recursive ref argument
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: dmd (show other issues)
Version: D2
Hardware: x86 Windows
: P2 normal
Assignee: No Owner
URL:
Keywords: rejects-valid
Depends on:
Blocks:
Reported: 2011年04月14日 18:14 UTC by bearophile_hugs
Modified: 2011年05月18日 21:22 UTC (History)
1 user (show)

See Also:


Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this issue.
Description bearophile_hugs 2011年04月14日 18:14:14 UTC
This program generates a "stack overflow" with DMD2 2.052, but it compiles and runs correctly with DMD1 v1.026.
The problem appears to be here:
uint solve(int niv, int dx, ref ulong diag45, ref ulong diag135, ref ulong cols) {
Removing the ref avoids the problem:
uint solve(int niv, int dx, ulong diag45, ulong diag135, ulong cols) {
Additionally: this program (with enum result=nqueen(10);) can also be used as one benchmark for CTFE speed (if run at runtime it allocates no heap memory).
import std.c.stdio: printf;
bool test(int k, int j, ulong diag45, ulong diag135, ulong cols) {
 return ((cols & (1UL << j)) +
 (diag135 & (1UL << (j + k))) +
 (diag45 & (1UL << (32 + j - k))) ) == 0;
}
void mark(int k, int j, ref ulong diag45, ref ulong diag135, ref ulong cols) {
 cols ^= (1UL << j);
 diag135 ^= (1UL << (j + k));
 diag45 ^= (1UL << (32 + j - k));
}
//uint solve(int niv, int dx, ulong diag45, ulong diag135, ulong cols) { // OK
uint solve(int niv, int dx, ref ulong diag45, ref ulong diag135, ref ulong cols) { // stack overflow
 uint solutions_found;
 if (niv) {
 for (int i = 0; i < dx; i++)
 if (test(niv, i, diag45, diag135, cols)) {
 mark(niv, i, diag45, diag135, cols);
 solutions_found += solve(niv - 1, dx, diag45, diag135, cols);
 mark(niv, i, diag45, diag135, cols);
 }
 } else {
 for (int i = 0; i < dx; i++)
 solutions_found += test(0, i, diag45, diag135, cols);
 }
 return solutions_found;
}
ulong nqueen(int n) {
 ulong diag45 = 0; // / diagonal bitboard
 ulong diag135 = 0; // \ diagonal bitboard
 ulong cols = 0; // column bitboard
 return solve(n - 1, n, diag45, diag135, cols);
}
const ulong result = nqueen(8);
void main() {
 // NQUEENS: 1, 0, 0, 2, 10, 4, 40, 92, 352, 724,
 // 2_680, 14_200, 73_712, 365_596
 printf("%lld\n", result);
}
Comment 1 Don 2011年05月17日 14:04:11 UTC
This is not useful as a benchmark.
Reduced test case:
void test5845(ulong cols) {}
uint solve(bool niv, ref ulong cols) {
 if (niv)
 solve(false, cols);
 else
 test5845(cols);
 return 65;
}
ulong nqueen(int n) {
 ulong cols = 0;
 return solve(true, cols);
}
static assert(nqueen(2) == 65);
Comment 2 bearophile_hugs 2011年05月17日 16:03:23 UTC
(In reply to comment #1)
> This is not useful as a benchmark.
Do you want to tell me why?
Comment 3 Don 2011年05月18日 01:31:35 UTC
(In reply to comment #2)
> (In reply to comment #1)
> > This is not useful as a benchmark.
> 
> Do you want to tell me why?
Because a simpler benchmark that tests exactly the same things is:
int foo(int n) {
 for (int i=0; i< n; ++i) {}
 return 0;
}
static assert(foo(10000));
Your code is longer but it tests NOTHING else.


AltStyle によって変換されたページ (->オリジナル) /