llvm dev - Jun 2016 - Adding BB input/output registers during ISel

Hello all,

I am developing an out-of-tree backend for a unique simd processor and I'm
looking for a bit of help. In my current design, it's possible for a case
to arise where I decide during instruction legalization that a fixed-sized
array of vectors which has been initially allocated on the stack needs to
be lowered into the vector register file. I have this design working for
the case where the stack object's lifetime resides entirely within a single
basic block: I start with an undef node to represent the set of registers
to which the buffer is allocated, and replace stores to the buffer with
insert_subvector's and replace loads with extract_subvector's.

I'm now looking at generalizing the design for the case where the stack
object's lifetime spans across 2 or more basic blocks and am hoping someone
from the community will be able to offer a little insight so that if there
are major issues here I can find out sooner rather than later. I'd like to
add this newly-created big vector value as an input reg for all BBs that
reference the original stack object but do not contain it's LIFETIME_START
node, and I'd like to add it as an output reg for all BBs that reference
the original stack object but do not contain it's LIFETIME_END node. I can
create Copy From/ToReg nodes easily enough and I think I can get the reg
number using MachineRegisterInfo::createVirtualRegister(). But I don't
quite understand how I set up the mapping from the new outputs of some BBs
to the new inputs of other BBs. I dug through the code and it looks like I
may be able to do this by manipulating
FunctionLoweringInfo::PHINodesToUpdate and/or directly adding PHI
instructions to the MachineBasicBlock's. Here are my specific questions:

	1.) Are there any existing targets that manipulate BB input/output
regs that I could look at as an example? Or can anyone provide a brief
explanation of how to accomplish this?
	2.) I realize that the design I've described might sound a little
bizarre, but does it at least sound possible? I can provide a little more
detail and am open to suggestions if there are alternative designs I'm
overlooking.


Thanks in advance,

Tyler
Logic Design Engineer
IBM
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160601/c0bcc3a5/attachment.html>

On 1 June 2016 at 08:13, Tyler Kenney via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I'd like to
> add this newly-created big vector value as an input reg for all BBs that
> reference the original stack object but do not contain it's
LIFETIME_START
> node, and I'd like to add it as an output reg for all BBs that
reference the
> original stack object but do not contain it's LIFETIME_END node.
This doesn't sound sufficient. For example:

    int foo(int res, int tst) {
      if (tst) bar();
      return res;
    }

Whatever register contains "res" is also a live-in & out for the
basic-block calling bar even though it's not referenced there. I think
you need some kind of real CFG analysis.

Tim.

Tim,

Thanks for the response. Since I started this project I've become quite
familiar with isel for single basic blocks but moving up a level and
looking at CFGs and multi-BB functions is a bit new to me, so I really
appreciate the feedback.

I've got a few questions on your example if you don't mind:

	1.) Can you provide another example of a BB that would have an
unreferenced live-in live-out var without making a function call? My target
is an embedded chip and, at least for the foreseeable future, we do not
intend to support function calls. It's inline everything or bust (which I
believe is also how the AMD GPU backend functions?). Although I don't
really want to eliminate the possibility of supporting function calls down
the line, this particular example is not my highest concern at the moment
if I could catch it and throw an error in this case, that would be OK.

	2.) What is the problem with having a basic-block that ignores an
unreferenced live-in, live out? I am sure that will cause an issue, but I'd
like to understand a little better what the issue will be. To put it
another way, what would happen if I was somehow able to surgically remove
res as a live-in & live-out from the BB calling bar() in your example, but
change nothing else?

	3.) Just to make sure I understand, I assume you would say the
following has the opposite problem:

	 I'd like to add this newly-created big vector value as an input reg
for all BBs in the func except the one that contains its LIFETIME_START
node, and I'd like to add it as an output reg for all BBs in the func
except the one that does not contain its LIFETIME_END node.

	That has the problem that I may add the inputs & outputs to BBs that
shouldn't have them, right? Again, do you know how this issue would
manifest itself?


	4.) More generic LLVM question here: is there any sort of convention
for distinguishing between live-ins/outs for a func and live-ins/outs for a
BB? It seems like most of the time I see those terms they're referring to
function live-ins/outs, but not always.


Tyler




From:	Tim Northover <t.p.northover at gmail.com>
To:	Tyler Kenney/Marlborough/IBM at IBMUS
Cc:	LLVM Developers Mailing List <llvm-dev at lists.llvm.org>
Date:	06/01/2016 12:25 PM
Subject:	Re: [llvm-dev] Adding BB input/output registers during ISel



On 1 June 2016 at 08:13, Tyler Kenney via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I'd like to
> add this newly-created big vector value as an input reg for all BBs that
> reference the original stack object but do not contain it's
LIFETIME_START
> node, and I'd like to add it as an output reg for all BBs that
reference
the
> original stack object but do not contain it's LIFETIME_END node.
This doesn't sound sufficient. For example:

    int foo(int res, int tst) {
      if (tst) bar();
      return res;
    }

Whatever register contains "res" is also a live-in & out for the
basic-block calling bar even though it's not referenced there. I think
you need some kind of real CFG analysis.

Tim.


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160601/a099d0e1/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160601/a099d0e1/attachment.gif>

Hi Tyler,

On 1 June 2016 at 11:27, Tyler Kenney <tjkenney at us.ibm.com>
wrote:
> 1.) Can you provide another example of a BB that would have an unreferenced
live-in live-out var without making a function call?
The function call was just there to make sure the block wasn't removed
as dead code. The same issue applies to all basic blocks: any block
control passes through from a definition to a use has to have the vreg
marked as live.
> 2.) What is the problem with having a basic-block that ignores an
unreferenced live-in, live out? I am sure that will cause an issue, but I'd
like to understand a little better what the issue will be. To put it another
way, what would happen if I was somehow able to surgically remove res as a
live-in & live-out from the BB calling bar() in your example, but change
nothing else?
I'm afraid I don't know specifically what *would* go wrong, but the
malformed data-flow information could confuse any inter-block analysis
that happens after your pass. Register allocation might decide to
reuse (and clobber) the vector register in the unmarked middle block,
for example.
> 3.) Just to make sure I understand, I assume you would say the following
has the opposite problem:
>
>  I'd like to add this newly-created big vector value as an input reg
for all BBs in the func except the one that contains its LIFETIME_START node,
and I'd like to add it as an output reg for all BBs in the func except the
one that does not contain its LIFETIME_END node.
>
> That has the problem that I may add the inputs & outputs to BBs that
shouldn't have them, right? Again, do you know how this issue would manifest
itself?
Extra live-ins and outs are probably less harmful since they just
restrict what's allowed. The big problem with this second scenario is
the same as the first: real uses of this register are unmarked at BB
edges.
> 4.) More generic LLVM question here: is there any sort of convention for
distinguishing between live-ins/outs for a func and live-ins/outs for a BB? It
seems like most of the time I see those terms they're referring to function
live-ins/outs, but not always.
I don't think so. They're basically the same thing just at different
levels.

Cheers.

Tim.

Thanks Tim. I'll work on a design that does the proper CFG analysis so I
know which BBs to add the live-ins & outs to.

Can you or anyone else comment on the process of adding the live-ins & outs
to each basic-block that needs them? Like I said, I can create the nodes
easily enough but I don't quite understand how to adjust the PHI nodes to
be sure the new inputs & outputs are mapped to each other appropriately.
Sounds like it's safe to assume there's no other target I can look to
for
an example on this?

Tyler





From:	Tim Northover <t.p.northover at gmail.com>
To:	Tyler Kenney/Marlborough/IBM at IBMUS
Cc:	LLVM Developers Mailing List <llvm-dev at lists.llvm.org>
Date:	06/01/2016 02:42 PM
Subject:	Re: [llvm-dev] Adding BB input/output registers during ISel



Hi Tyler,

On 1 June 2016 at 11:27, Tyler Kenney <tjkenney at us.ibm.com>
wrote:
> 1.) Can you provide another example of a BB that would have an
unreferenced live-in live-out var without making a function call?

The function call was just there to make sure the block wasn't removed
as dead code. The same issue applies to all basic blocks: any block
control passes through from a definition to a use has to have the vreg
marked as live.
> 2.) What is the problem with having a basic-block that ignores an
unreferenced live-in, live out? I am sure that will cause an issue, but I'd
like to understand a little better what the issue will be. To put it
another way, what would happen if I was somehow able to surgically remove
res as a live-in & live-out from the BB calling bar() in your example, but
change nothing else?

I'm afraid I don't know specifically what *would* go wrong, but the
malformed data-flow information could confuse any inter-block analysis
that happens after your pass. Register allocation might decide to
reuse (and clobber) the vector register in the unmarked middle block,
for example.
> 3.) Just to make sure I understand, I assume you would say the following
has the opposite problem:
>
>  I'd like to add this newly-created big vector value as an input reg
for
all BBs in the func except the one that contains its LIFETIME_START node,
and I'd like to add it as an output reg for all BBs in the func except the
one that does not contain its LIFETIME_END node.
>
> That has the problem that I may add the inputs & outputs to BBs that
shouldn't have them, right? Again, do you know how this issue would
manifest itself?

Extra live-ins and outs are probably less harmful since they just
restrict what's allowed. The big problem with this second scenario is
the same as the first: real uses of this register are unmarked at BB
edges.
> 4.) More generic LLVM question here: is there any sort of convention for
distinguishing between live-ins/outs for a func and live-ins/outs for a BB?
It seems like most of the time I see those terms they're referring to
function live-ins/outs, but not always.

I don't think so. They're basically the same thing just at different
levels.

Cheers.

Tim.


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160602/e3f27393/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160602/e3f27393/attachment.gif>