chapel-lang/chapel — pull request #384 by ronawho (2014-09-11 17:23:18+00:00)
Title: Add overflow checks to bounded range iterators

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.