Pragma Insanity: Weird Behaviour with Pragma O3

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Here is a simple problem. Count the number of array $$$A$$$ of non-negative integers size $$$N$$$ such that $$$\sum\limits_{i=1}^{N} A_i \cdot i=K$$$. Where $$$N,K \leq 5000$$$. Find the answer modulo $$$1000000007$$$.

I unfortunately cannot share the link to a submissions page as it is on a private local judge.

Update: I have asked judge devs of the local judge, the compile command is g++ -O2 -o {compiledName} {sourceName} -m64 -static -std=gnu++14 -lm -s -w -Wall -Wshadow -fmax-errors=512

But anyways, here is the problem.

AC code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	rep(x,n+1,1) if (k>=x) rep(y,k+1,x){
		assert(y-x>=0);
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

WA code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	rep(x,n+1,1) if (k>=x) rep(y,k+1,x){
		//assert(y-x>=0);
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

For the testcase $$$N=K=2500$$$ (which is the partition number for $$$2500$$$) the answer should be $$$729287017$$$, but the WA code gives $$$735199643$$$ (testing on atcoder custom invocation with C++ (GCC 9.2.1) ). This makes zero sense because the only thing different between these two codes is just the commented assert.

After further investigating, I managed to figure out that the problem was something to do with #pragma GCC optimize("O3").

Below is another set of AC and WA codes where the only difference is #pragma GCC optimize("O3").

AC code

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3")

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	for (int x=n;x>=1;x--) for (int y=k;y>=x;y--){
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

WA code

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	for (int x=n;x>=1;x--) for (int y=k;y>=x;y--){
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

I was super confused when I found out about this so I told kostia244. He told me that perhaps it is overflow. And indeed, after changing int memo[5005] to long long memo[5005], it is AC.

AC code with long long

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

const int MOD=1000000007;

int n,k;
long long memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	for (int x=n;x>=1;x--) for (int y=k;y>=x;y--){
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

So now we are both scratching our heads at this weird behaviour. Does anyone have an idea why this happens? Should we include macros in our codes by default now?

Sorry for tagging but ToxicPie9 nor

Comments (4)

Write comment?

Maksim1744

3 years ago, # |

+34

I don't want to sound like someone who calls every UB a compiler bug, but I don't see anything illegal in your code. Also I can reproduce this locally with g++-8 and g++-9, but it works correctly with g++-10 or g++-11, so maybe they actually fixed something?

→ Reply

nor

3 years ago, # ^ |

+30

I too have strong reasons to believe it's a compiler bug (and I suspect it is related to optimizations that are triggered due to the array's memory layout). For instance, replacing the array with a vector of size $$$\max(n, k) + 1$$$ (or even 5005) is fine. Replacing it by a local array of size 5005 is also buggy.

ivan100sic

+22

To me this looks like a compiler bug in the O3 optimizer in GCC 9. I could only reproduce it with GCC 9, but not 10 or 11.

ssvb

+18

I further reduced the testcase using C-Vise and submitted a report to GCC bugzilla: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103615

AtCoder uses GCC 9.2, but there were two bugfix releases from the 9.x branch since then: changes from 9.2 to 9.3 and changes from 9.3 to 9.4. Let's say, if GCC developers backport the necessary bugfix to GCC 9.5, how likely are AtCoder and the other online judges to upgrade their old 9.x compilers?

errorgorn's blog