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

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

graycol.gif

Hi Tyler,

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

graycol.gif