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)
```
That also sounds like a good solution


On Tue, Aug 12, 2014 at 2:22 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,
>
> 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
> … <#147cc1a242a11308_>
> 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>.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/halide/Halide/pull/419/files#r16143776>.
>