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)
```
So, I've been looking at this, and I got this to work via calls to
shuffle_vector only, however, the assembly code is not that great. It turns
out that the reinterpret casts were actually pretty important on SSE. What
I'm thinking now is, instead of trying to do this general thing for all
powers of 2, which is probably not that useful, that we could make
interleave_vectors work for 2, 3, or 4 vectors. One nice thing is that this
will map directly to vst(2,3,4) commands on ARM, and we can write pretty
good llvm code for the general case. Going this way we can insert the
necessary bitcasts directly in the codegen and don't need to overload the
halide Cast node. So what I propose is to leave shuffle_vector alone, and
modify interleave_vectors to accept 2, 3, or 4 arguments. Then I can do the
necessary stuff in deinterleave to create the Call nodes to
interleave_vectors. Let me know what you think.

Thanks,
Kree


On Tue, Aug 12, 2014 at 12:10 PM, 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,
>
> Changing shuffle vectors to take 2 (or more) vectors sounds good.
> … <#147cba0c853b7715_>
> 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>.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/halide/Halide/pull/419/files#r16135418>.
>