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)
```
Changing shuffle vectors to take 2 (or more) vectors sounds good.


On Tue, Aug 12, 2014 at 12:06 PM, 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,
>
> This looks like a really good idea. As it is trying to get strided
> interleave_vectors to play nice with deinterleave doesn't look like much
> fun. Dealing with shuffle_vector directly seems like it could be the right
> things to do. But, it looks as if the shuffle_vector intrinsic only
> operates on a single vector argument: Value *arg = codegen(op->args[0]);
>  value = builder->CreateShuffleVector(arg, arg,
> ConstantVector::get(indices));
> We need to be able to shuffle 2 vectors together. is there any reason why
> we shouldn't change shuffle_vector to use the first 2 args as the input
> vectors?
> … <#147cb9d3db8e68a2_>
> On Tue, Aug 12, 2014 at 11:57 AM, Andrew Adams <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, 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. …
> <#147cb94c9b81afe2_> 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>. — Reply to
> this email directly or view it on GitHub <
> https://github.com/halide/Halide/pull/419/files#r16134545>.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/halide/Halide/pull/419/files#r16135190>.
>