Deinterleave Powers of 2

I've added some functionality to the deinterleave mutator to handle powers of 2. The motivation for this is to generate efficient assembly code for converting from planar to interleaved data in the case of RGBA data, for example. With these changes we can write Halide code like:

```
  Func output("output");
  output(x, c) = input(x, c);

  // Set extent and stride so that we convert from planar to interleaved.
  output.output_buffer()
      .set_min(1, 0)
      .set_stride(0, 4)
      .set_stride(1, 1)
      .set_extent(1, 4);

  // Schedule
  Var cx("cx");
  output
      .bound(c, 0, 4)
      .reorder(c, x)
      .fuse(c, x, cx)
      .vectorize(cx, 64);
  ```

And we will generate a decent block of punpck*** and mov*** calls on SSE architectures, e.g.:

```
	vmovdqu	(%rsi,%rax), %xmm0
	movq	40(%rsp), %rcx          # 8-byte Reload
	movslq	%ecx, %rcx
	leaq	(%rcx,%rax), %rdx
	vmovdqu	1(%rsi,%rdx), %xmm1
	vpunpcklbw	%xmm1, %xmm0, %xmm2 
	vpunpckhbw	%xmm1, %xmm0, %xmm0 
	leaq	(%rax,%rcx,2), %rdx
	vmovdqu	2(%rsi,%rdx), %xmm1
	leaq	(%rcx,%rcx,2), %rcx
	addq	%rax, %rcx
	vmovdqu	3(%rsi,%rcx), %xmm3
	vpunpcklbw	%xmm3, %xmm1, %xmm4 
	vpunpckhbw	%xmm3, %xmm1, %xmm1 
	vpunpcklwd	%xmm1, %xmm0, %xmm3 
	vpunpckhwd	%xmm1, %xmm0, %xmm0 
	vpunpcklwd	%xmm4, %xmm2, %xmm1 
	vpunpckhwd	%xmm4, %xmm2, %xmm2 
	movq	56(%rsp), %rax          # 8-byte Reload
	cltq
	movq	8(%rsp), %rcx           # 8-byte Reload
	vmovdqu	%xmm2, 16(%rcx,%rax)
	vmovdqu	%xmm1, (%rcx,%rax)
	vmovdqu	%xmm0, 48(%rcx,%rax)
	vmovdqu	%xmm3, 32(%rcx,%rax)
```
There is also a Halide shuffle_vector intrinsic that maps directly to
llvm's shuffle_vector. It might be easier to just emit that directly
instead of interleave_vectors.

The advantage of interleave_vectors is that deinterleave understands it
(even lanes of interleave vectors is just the first arg). If we make
deinterleave understand shuffle_vector (not very hard, I think, just take
the even/odd lanes of the shuffle mask, and then simplify it away if the
shuffle mask turns into 0, 1, 2, ...), then we could remove
interleave_vectors entirely and just always use shuffle_vector.

This would be a more complex change though. Up to you.


On Tue, Aug 12, 2014 at 10:38 AM, Kree Cole-McLaughlin <
notifications@github.com> wrote:

> In src/Deinterleave.cpp:
>
> > +                Type s = t;
> > +                t.bits  <<= 1;
> > +                s.width <<= 1;
> > +                num_lanes >>= 1;
> > +
> > +                for (int j = 0; j < num_lanes; ++j) {
> > +                    Expr a = lanes[i][2*j];
> > +                    Expr b = lanes[i][2*j + 1];
> > +
> > +                    lanes[i-1][j] = Cast::make(t, Call::make(s, Call::interleave_vectors,
> > +                                                             vec(a, b), Call::Intrinsic));
> > +                }
> > +            }
> > +
> > +            t.width <<= 1;
> > +            return Cast::make(e.type(), Call::make(t, Call::interleave_vectors,
>
> So the intention here was to reinterpret a vector of bytes as a vector of
> words, and then a vector of words as a vector of double words, etc... This
> aligns with the instructions we expect to be emitted in the assembly, e.g.
> punpcklbw followed by punpcklwd, and so on. So I was intentionally
> overloading the Cast node to provide a reinterpret cast for this case.
> However, I just tested if I can get LLVM to generate the correct code
> without the casting, and I can if I do a strided interleave, i.e.
> interleave 2 vectors using 2 elements at a time from each. So I will change
> this add an optional stride argument to interleave_vectors and remove the
> change the CodeGen::visit(Cast*).
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/halide/Halide/pull/419/files#r16129046>.
>