How is gcc optimizing this loop?

Question

So I encountered some strange behavior, which I stripped down to the following minimal example:

#include <iostream>
#include <vector>

int main()
{
  std::vector<int> vec;

  for(int i = 0; i < 1000; i++)
  {
    vec.push_back(2150000 * i);
    if(i % 100 == 0) std::cout << i << std::endl;
  }
}

When compiling with gcc 7.3.0 using the command

c++ -Wall -O2 program.cpp -o program

I get no warnings. Running the program produces the following output:

0
100
200
300
400
500
600
700
800
900
1000
1100
1200
1300

[ snip several thousand lines of output ]

1073741600
1073741700
1073741800
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted (core dumped)

which I guess means that I finally ran out of memory for the vector.

Clearly something is wrong here. I guess this has something to do with the fact that 2150000 * 1000 is slightly larger than 2^31, but it's not quite as simple as that -- if I decrease this number to 2149000 then the program behaves as expected:

0
100
200
300
400
500
600
700
800
900

The cout isn't necessary to reproduce this behavior, so I suppose a minimal example is actually

#include <vector>

int main()
{
  std::vector<int> vec;

  for(int i = 0; i < 1000; i++)
  {
    vec.push_back(2150000 * i);
  }
}

Running this causes the program to wait for a long time and then crash.

Question

I'm fairly new to C++ at any serious level. Am I doing something stupid here that allows for undefined behavior, and if so, what? Or is this a bug in gcc?

I did try to Google this, but I don't really know what to Google.

Addendum

I see that (signed) integer overflow is undefined behavior in C++. To my understanding, that would only mean that the behavior of the expression

21500000 * i

is undefined -- i.e. that it could evaluate to an arbitrary number. That said, we can see that this expression is at least not changing the value of i.

Answer 1

To answer my own question, after examining the assembler output it looks like g++ optimizes this loop by changing

for(int i = 0; i < 1000; i++)
{
  vec.push_back(2150000 * i);
}

to something like

for(int j = 0; j < 1000 * 2150000; j += 2150000)
{
  vec.push_back(j);
}

I guess the addition is faster than doing a multiplication each cycle, and the rule about overflows being undefined behavior means that this change can be made without worrying about whether this introduces unexpected behavior if that calculation overflows.

Of course the conditional in the optimized loop always fails, so ultimately I end up with something more like

for(int j = 0; true; j += 2150000)
{
  vec.push_back(j);
}