insertion points for newly created instructions

Hi,

I've been scratching my head with a little problem: how to determine the insertion point for a newly created instruction?
The operands of these instructions can be defined in different BBs, and they may have several users. Thereby determining where to put those instructions is not obvious. In my case, these instructions don't have side-effects, and so they could be placed anywhere after the definition of the "more-recently-defined" operand, but before the last dominator of all the users.

Does LLVM already has any function that will do this (i.e., magically insert an instruction in a valid point)? If not, is there any way I can implement this without transversing all the instructions in the enclosing function?

Thanks,
Nuno

Hi,

I've been scratching my head with a little problem: how to determine the
insertion point for a newly created instruction?
The operands of these instructions can be defined in different BBs, and they
may have several users. Thereby determining where to put those instructions
is not obvious. In my case, these instructions don't have side-effects, and
so they could be placed anywhere after the definition of the
"more-recently-defined" operand, but before the last dominator of all the
users.

Does LLVM already has any function that will do this (i.e., magically insert
an instruction in a valid point)?

There is no magical utility function available to do this.

If not, is there any way I can implement
this without transversing all the instructions in the enclosing function?

Find a user that dominates all other users and then insert this
instruction just before the dominating users.

Thanks for your reply!

Hi,

I've been scratching my head with a little problem: how to determine the
insertion point for a newly created instruction?
The operands of these instructions can be defined in different BBs, and they
may have several users. Thereby determining where to put those instructions
is not obvious. In my case, these instructions don't have side-effects, and
so they could be placed anywhere after the definition of the
"more-recently-defined" operand, but before the last dominator of all the
users.

Does LLVM already has any function that will do this (i.e., magically insert
an instruction in a valid point)?

There is no magical utility function available to do this.

That's what I was afraid of :slight_smile:

If not, is there any way I can implement
this without transversing all the instructions in the enclosing function?

Find a user that dominates all other users and then insert this
instruction just before the dominating users.

The problem is if none of the users dominates the other ones. That's why I wanted to somewhat insert the new instruction after the last definition of the operands. I guess that's a tricky business..

Nuno

Nuno Lopes wrote:

Thanks for your reply!

Hi,

I've been scratching my head with a little problem: how to determine the
insertion point for a newly created instruction?
The operands of these instructions can be defined in different BBs, and they
may have several users. Thereby determining where to put those instructions
is not obvious. In my case, these instructions don't have side-effects, and
so they could be placed anywhere after the definition of the
"more-recently-defined" operand, but before the last dominator of all the
users.

Does LLVM already has any function that will do this (i.e., magically insert
an instruction in a valid point)?
      

There is no magical utility function available to do this.
    
That's what I was afraid of :slight_smile:

If not, is there any way I can implement
this without transversing all the instructions in the enclosing function?
      

Find a user that dominates all other users and then insert this
instruction just before the dominating users.
    
The problem is if none of the users dominates the other ones. That's why I wanted to somewhat insert the new instruction after the last definition of the operands. I guess that's a tricky business..
  
I'm a little confused: are you trying to find a place where your new instruction is dominated by all of the values it uses as operands, are you trying to find a place where your new instruction dominates all instructions that use its value, or both?

-- John T.

I've been scratching my head with a little problem: how to determine the
insertion point for a newly created instruction?
The operands of these instructions can be defined in different BBs, and they
may have several users. Thereby determining where to put those instructions
is not obvious. In my case, these instructions don't have side-effects, and
so they could be placed anywhere after the definition of the
"more-recently-defined" operand, but before the last dominator of all the
users.

Does LLVM already has any function that will do this (i.e., magically insert
an instruction in a valid point)?

There is no magical utility function available to do this.

That's what I was afraid of :slight_smile:

If not, is there any way I can implement
this without transversing all the instructions in the enclosing function?

Find a user that dominates all other users and then insert this
instruction just before the dominating users.

The problem is if none of the users dominates the other ones. That's why I wanted to somewhat insert the new instruction after the last definition of the operands. I guess that's a tricky business..

I'm a little confused: are you trying to find a place where your new instruction is dominated by all of the values it uses as operands, are you trying to find a place where your new instruction dominates all instructions that use its value, or both?

Both. Actually that's the necessary condition that all instructions must met. I was just trying to figure out if there was already a simple way of doing it automatically (i.e., letting llvm insert the instructions where appropriate). Something in the style of specifying the computation as a data-flow graph, and leave the linearization to the compiler.
Just for the sake of curiosity, I'm lowering certain instructions into several other simpler instructions (like lowering multiplications into adds/shifts/..), but in a way that the result of these instructions may be shared across several intermediate results.
e.g.:
A = B * 2
C = B * 4
I translate that to:
A = B << 1
C = A << 1

so 'B << 1' has 2 users: as the replacement of an operation that was previously in the code, and has an intermediate value for another computation. Maybe I should be doing this in the codegen lowering pass (dunno if that would help, anyway).

Thanks,
Nuno