Added a case to deinterleave that works when transposing fixed sized blo...

Added a case to deinterleave that works when transposing fixed sized blocks of data. In this case we can safely interleave if the collected stores have unit stride, and each store is simply a load with a stride equal to the vector width. Adding this case makes this optimization a little easier to trigger when doing a simple transpose.

The last test in test/correctness/interleave.cpp demonstrates this. Prior to this change trans1 would not trigger the call to interleave_vector, whereas it is probably the more likely code that people would want to write. This change essentially allows us to interleave blocks of stores of the form:
```
    trans1[ramp(0, 1, 8)] = square[ramp(0, 8, 8)]
    trans1[ramp(8, 1, 8)] = square[ramp(1, 8, 8)]
    trans1[ramp(16, 1, 8)] = square[ramp(2, 8, 8)]
    trans1[ramp(24, 1, 8)] = square[ramp(3, 8, 8)]
    trans1[ramp(32, 1, 8)] = square[ramp(4, 8, 8)]
    trans1[ramp(40, 1, 8)] = square[ramp(5, 8, 8)]
    trans1[ramp(48, 1, 8)] = square[ramp(6, 8, 8)]
    trans1[ramp(56, 1, 8)] = square[ramp(7, 8, 8)]
```
whereas before we were only interleaving:
```
    trans2[ramp(0, 8, 8)] = square[ramp(0, 1, 8)]
    trans2[ramp(1, 8, 8)] = square[ramp(8, 1, 8)]
    trans2[ramp(2, 8, 8)] = square[ramp(16, 1, 8)]
    trans2[ramp(3, 8, 8)] = square[ramp(24, 1, 8)]
    trans2[ramp(4, 8, 8)] = square[ramp(32, 1, 8)]
    trans2[ramp(5, 8, 8)] = square[ramp(40, 1, 8)]
    trans2[ramp(6, 8, 8)] = square[ramp(48, 1, 8)]
    trans2[ramp(7, 8, 8)] = square[ramp(56, 1, 8)]
```
I'm now seeing **intermittent** failures of test_interleave. It does pass
sometimes (very strange!). Here are a few of the outputs I've seen:

cd tmp ; DYLD_LIBRARY_PATH=:../bin LD_LIBRARY_PATH=:../bin
../bin/test_interleave
Internal error at src/CodeGen.cpp:537 triggered by user code at
test/correctness/interleave.cpp:181:
Symbol not found: outp
bash: line 1: 52480 Abort trap: 6 DYLD_LIBRARY_PATH=:../bin
LD_LIBRARY_PATH=:../bin ../bin/test_interleave
make: *** [test_interleave] Error 134

cd tmp ; DYLD_LIBRARY_PATH=:../bin LD_LIBRARY_PATH=:../bin
../bin/test_interleave
bash: line 1: 52621 Segmentation fault: 11 DYLD_LIBRARY_PATH=:../bin
LD_LIBRARY_PATH=:../bin ../bin/test_interleave
make: *** [test_interleave] Error 139


Value still in symbol table! Type = 'bash: line 1: 52292 Segmentation
fault: 11 DYLD_LIBRARY_PATH=:../bin LD_LIBRARY_PATH=:../bin
../bin/test_interleave
make: *** [test_interleave] Error 139


So there are at least 3 distinct failure modes in addition to succeeding!

On Mon Oct 27 2014 at 10:40:35 PM Kree Cole-McLaughlin <
notifications@github.com> wrote:

> In src/BlockFlattening.cpp:
>
> > +class BlockFlattener : public IRMutator {
> > +private:
> > +
> > +    using IRMutator::visit;
> > +
> > +    void visit(const Block *op) {
> > +        /* First we dig into the block traversing down the 'first'
> > +         * stmt until we find one that is not a block. We push all of
> > +         * the rest stmt's into the 'rest' stmt of the top-level
> > +         * block, and then fix up the 'rest' stmt recursively at the
> > +         * end. The result of this mutation is an equivalent Block
> > +         * node that does not contain any Block nodes in a 'first' stmt.
> > +         */
> > +        Stmt first = op->first;
> > +        Stmt rest  = op->rest;
> > +        while(const Block *first_block = op->first.as<Block>()) {
>
> This should be fixed now with the latest push. All tests passed for me.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/halide/Halide/pull/510/files#r19454071>.
>