Add overflow checks to bounded iterators

The default iterators do not support positively strided ranges whose last index
is max(indexType) or negatively strided ranges whose last index is
min(indexType). E.G "for i in max(int)-10 .. max(int)"

The above example turns into the following generated code

for (i=max(int)-10; i < max(int); i+=1)

and everything is less than max(int) so you would have an infinite loop.

Prior to c for loops our iterators didn't work for maximal ranges, but they did
work for the above example. They generated the equivalent of:
for (i=max(int)-10; i != max(int)+1; i+=1)

This relies on well defined integer overflow, which is not valid since integer
overflow has undefined behavior in c.

So while the new iterators aren't as capable as the old ones, they're more
performant, and don't cause undefined behavior.

To deal with this limitation I added a function that checks for overflow and
halts with a warning about them.

If a user really wants to iterate over such a range, I added a generalIterator
that works for any range including maximal ranges, but is terribly slow. To
avoid the performance cost the user can either rewrite their loop to avoid the
problem or try a wider type if they aren't already at the max size.

If they don't care about performance they can toggle
useOptimizedRangeIterators=false which is a big hammer that will use the slow
general iterator for all cases. This will lead to absolutely awful performance.
I can't think of a way to support such ranges in an optimal  fashion, but there
may be a better way to let users pick and chose what loops use the general
iterator.

The general iterator exposed some bugs in the c for loop implementation. Namely
that the break and continue labels were getting added to the wrong structure.

There are also some tests changes.

trivial/deitz/test_max_range_iteration
types/range/hilde/maximalRange

were tests that has ranges that the new iterators do not support. I updated
these tests to include the new error. I also added compopts so they tests the
unoptimized iterator. With bounds checks off and the optimized iterators being
used these tests would have infinite loops. We break to avoid this, so one
variation of the test captures the fact that these infinite loops will occur
(and are expected, although unfortunate.)

I also added a test that checks similar behavior as the previous two tests but
it does it for unsigned and signed variations for positively and negatively
strided ranges.
Need to cast stride.

The stride needs to be casted when the idxType is unsigned. This is still
correct even if the stride is negative because val:uint + -val2:uint is the
same as val:uint + max(uint)-abs(val2)+1

E.G. 1:uint + (-1):uint ends up being 1 + 255 which will end up being 0 since
unsigned integer overflow is well defined
Change bigStride to prevent overflowing

[ok'd by brad]

Quote from brad:

"Re-reading the history of this test, it was basically guarding against
some assumptions in the early range code that the idxType and/or stride
were 32-bits.  I think as long as the stride for this thing can't be
stored in an int(32), my earlier self would be happy.  For example,
maybe something like:

  1..2*(n/3) by n/3

(with some +/-1's in there to get a few values without hitting the
overflow issue?).  I can take this if you want."
Change atomictest to prevent range iterator overflow

[ok'd by brad]

quote from brad:

"Elliot says he doesn't think this is a particularly compelling example,
which I'd agree with.  We can just set n to be something smaller. "
Change fannkuch-redux-blc.chpl to use an unbounded range

This is identical to what brad did to the other fannkuch versions in
0b09c9534e5ef7bfabdd6040f76b1e4ea817a320

Just changing this test as well
Cast histoSerial iterator indices so they don't overflow the iterator

The iterator attempts to do something like "for 0:uint..length:uint by -1" and
so the last iteration will result in overflow since 0 -1 for uints will
overflow. This just casts the uint32 to int64s to prevent that
Update t2.chpl and t8.chpl to prevent iterator overflow

[ok'd with vass]

These tests create unsigned integer overflow in a couple of cases. They have
things like for 0..9 by -1. This causes overflow for the iterators. This just
changes the bounds to things like 1..9 by -1.
Remove pointer to STATUS for range iterator overflow

I'm not quite sure where the best place to put the note is, but STATUS isn't
quite right. Something about what the behavior of iteration over ranges is
needed in the spec, but I'm not sure if we want to point to that, or if there
should be a technote or something else.
Fix typo in .good file
remove unnecessary cast for histoSerial
Merge pull request #384 from ronawho/CForLoops-maximal-checks

Add overflow checks to bounded range iterators

[reviewed by @daviditen, test changes by logical owners]

This adds overflow checking for bounded range iterators. If iteration over a
range will result in overflow, execution will halt as it could result in
undefined behavior or an infinite loop. This also provides a config param that
will allow users to iterate over such ranges (and any range, including maximal
ranges) by using a more general iterator at a high performance cost. This fixes
regressions for two tests that started failing with the original c for loops
commit and updates several other tests result in overflow, but that weren't
caught earlier.

The default range iterators do not support iteration over ranges whose last
index + stride will result in overflow. The reason for this is because the way
we generate such loops will either create infinite loops or undefined behavior.

for something like:
  "for i in 10:uint(8) .. max(uint(8))"

we generate something like this c for loop:
  for (uint8_t i = 10; i <= 255; i+=1)

and all uint8_t's are <= 255 so you'll have an infinite loop. A similar test
but with int(8) would result in undefined behavior because signed integer
overflow has undefined behavior in c. So when i is 127, i+=1 will result in
undefined behavior, and has absolutely no assurance that it will wrap around to
-128 (at least with our c backend.)

This means that the new ranges aren't as versatile as they were prior to c for
loops, but these restrictions are required in order to support
vectorize/offloading. Also the previous ranges relied on well defined integer
overflow, which at least with our c backend integer overflow results in
undefined behavior.

My current thinking is that if enough users find the inability to iterate over
such ranges to be a real problem we can try to come up with a better solution,
but until then this seems ok.

The general iterator exposed some bugs in the c for loop implementation. Namely
that the break and continue labels were getting added to the wrong structure in
build.cpp


The tests that changed:

  trivial/deitz/test_max_range_iteration
  types/range/hilde/maximalRange

were tests that had ranges that the new iterators do not support. I updated
these tests to include the new error. I also added compopts so they tests the
general iterator. With bounds checks off and the optimized iterators being
used these tests would have infinite loops. We break to avoid this, so one
variation of the test captures the fact that these infinite loops will occur
(and are expected, although unfortunate.)

I also added a test that checks similar behavior as the previous two tests but
it does it for unsigned and signed variations for positively and negatively
strided ranges.

See individual commits for the rational/approval for the following tests:

  distributions/dm/t2
  distributions/dm/t8
   - idea ok'd by Vass

  studies/parboil/histo/histoSerial
   - cast uint(32) to int(64) to allow iteration to 0 by -1

  studies/shootout/fannkuch-redux/bradc/fannkuch-redux-blc
   - similar to changes brad made on other fannkuchs

  types/atomic/ferguson/atomictest.chpl
   - Lower upper bound on iterator to avoid iterating to max(type)
   - idea ok'd by brad

  types/range/bradc/bigStride.chpl
   - Change upper bound and stride to prevent overflow
   - idea ok'd by brad


I'd like the halt message to point to some document so we can explain the
limitations in more detail. I'm not sure if that's going to be the spec, a
technote, or some other place yet.