Updating PHI for Instruction Domination?

So I have a loop with two blocks, a header (which points to return and latch) and a latch (which points to return and header). I have inserted a few new blocks, called H and F.

Header now points to H and latch. Latch now points to F. H points to F. F points to Header and return.

The PHI Nodes have been updated in Header accordingly, now coming from the preheader and F (instead of latch).

My issue is this: The values in the PHI instruction in the Header for F are actually defined in Latch and so if you follow the path: Header->H->F, there becomes an issue with “Instruction does not dominate all uses” (since the Header PHI is getting values defined in Latch coming from F but never going to Latch) since they haven’t been defined in that path.

My question is: Is there some call where I can rearrange the basic blocks and call some functions/utils that solve this issue? Or do I have to manually solve this myself?

Thanks again.

By manually I meant create new value names for the F PHI in Header, and create copy PHIs for each of those values in F that take the corresponding value from Latch and zero (or something else) from H.

So essentially I’m adding a path inside of the loop. Is there a way to have llvm automatically create new IR and update the PHIs simply by adding a block like this and changing the DomTree?

Not that I’m aware of.


So my best bet is to try and work in reg2mem mode and then go back to mem2reg?

I’m curious, it seems though when you split a block that the phis get updated, right?

So my best bet is to try and work in reg2mem mode and then go back to mem2reg?

I wouldn't. That sounds painful.

I'm curious, it seems though when you split a block that the phis get updated, right?

Sure. There's code in splitBasicBlock to do this. It should just take a little bit of work to get what you want done.


Yes, the first DOES sound painful (I want to avoid it) and the second is not an option. I’m adding a second path in a loop.

The old path: BB1->BB2/BB3, BB2->BB1/BB3, BB3->n/a

The new path: BB1->H/BB2, BB2->F/K, H->F, K->F, F->BB1/G, G->BB3

There are PHI nodes in BB1 that come in from BB2 for values defined in BB2. With the new possible path: BB1->H->F, BB2. Without adding new PHIs or Values, there exists a dominance instruction issue. So I want to create PHIs in F for each value in BB2 that is used in BB1. The update the PHI Values in BB1 (that used to come from BB2) to the new values in F (which are getting values from BB2/H).

The problem is that there is no way to copy the value from BB2, since there exists no Value constructor!?

This seems like a pretty large limitation anytime anyone wants to add a branch inside a loop? Is there an easier way to get what I want that I’m missing?

Since I’m not sure which instructions I might want to replicate, would it be possible to cast the Value from “PHINode::getIncomingValue” to “Instruction” and then copy that and cast it back?

Also, or is there some way to simply turn off the verification and get llvm to output the data regardless?

I guess not since Value is a superclass of Instruction.

You’re creating a new path that doesn’t include L. For all values defined in L and used outside of L, you need to determine the new reaching def. That’s specific to your transformation and can’t be automated. Once you do that, creating the phi in F is natural.


Thanks for the response. I fixed this, seems to be working fairly well so far, I did have to manually iterate over phi nodes and modify each one accordingly. The value problem was a mistake on my part, the new PHI node instructions were the values. It would seem however that there should be calls, once all the branching is done, that can automate over the new cfg and determine the PHI nodes (blocks and values) needed and automatically insert them.

Thanks everyone.