Douglas do Couto Teixeira
2011-Jan-24 18:05 UTC
[LLVMdev] How to change the type of an Instruction?
On Mon, Jan 24, 2011 at 3:01 PM, Nick Lewycky <nicholas at mxc.ca> wrote:> On 01/24/2011 04:41 AM, Douglas do Couto Teixeira wrote: > >> Hi, >> >> Nick, thanks for the reply. >> I still have a problem: I only need to "clone" an Instruction, changing >> its type. That is, I would like to keep all characteristics of the old >> Instruction and create a new one only with a different type. >> > > Sure, but what about its operands? An "add" instruction must have the same > type as its operands, what do you want to do with them?I also need to convert the type of the operands. But I want to do this when they are created instead of inserting "trunc" instructions before performing an operation. But it seems hard to me.> Suppose you're going from a 32-bit add to a 64-bit add, do the old operands > get zero extended? Sign extended? You'll need to insert instructions for > that (unless they're constants in which case you can use constant > expressions). Similarly, what if the old type is a float and the new one is > an int? float to signed int, float to unsigned int, or bitcast (only legal > sometimes)?I believe I don't need worry about it because I only create smaller instructions. So I never convert a 32-bit instruction in a 64-bit instruction.> > > I am trying > >> create a new Instruction thus: >> >> %3 = add nsw i32 %1, %2 ; <i16> [#uses=2] //Old Instruction >> >> Value* Op0 = I->getOperand(0); >> Value* Op1 = I->getOperand(1); >> Value* V0 = new Value(Type::getInt16Ty(Op0->getContext()), >> Op0->getValueID()); >> > > Hunh, Value's constructor is protected. > > In any event, Value is pure base. Constructing one this way will never get > you what you want. If the ValueID indicates an Instruction, go through > Instruction to create one. > > > Value* V1 = new Value(Type::getInt16Ty(Op1->getContext()), >> Op1->getValueID()); >> Instruction* newInst = BinaryOperator::CreateNSWAdd(V0, V1, "test"); >> errs() << "NewInst:\n" << *newInst << "\n"; >> >> >> But I get something like this: >> >> %test = add nsw i16 <badref>, <badref> ; <i16> [#uses=0] >> > > The two instructions V0 and V1 you created were never inserted into the > BasicBlock so they can't be numbered, and also they don't have names. > > > What I am doing wrong? >> > > Suppose that you're going from i32 to i16. Your only choice with that > particular pair of types is a truncate. So: > > IRBuilder builder(OldInst); > Value *V0 = builder.CreateTrunc(Op0, Type::getInt16Ty()); > Value *V1 = builder.CreateTrunc(Op1, Type::getInt16Ty()); > Value *Add = builder.CreateNSWAdd(V0, V1, "test"); > > The IRBuilder will take care of the distinction between instructions and > constants for you. Note that I have not tested the above code, it may need > some fixing before it compiles. > > Nick > > >> >> Best, >> >> Douglas >> >> On Fri, Jan 21, 2011 at 8:25 PM, Nick Lewycky <nlewycky at google.com >> <mailto:nlewycky at google.com>> wrote: >> >> On 21 January 2011 12:56, Douglas do Couto Teixeira >> <douglasdocouto at gmail.com <mailto:douglasdocouto at gmail.com>> wrote: >> >> Hello guys, >> >> I wonder how I can change the type of an integer variable. For >> instance, given the instruction "%3 = add i32 %1, %2" I would >> like to alter the instruction to "%3 = add i16 %1, %2". Is there >> any way to do this? >> >> >> No. Instead you create a new Instruction, in this case with >> BinaryOperator::CreateAdd, then OldInst->replaceAllUsesWith(NewInst) >> to update all the users, then OldInst->eraseFromParent() since it's >> now dead code. >> >> Also, all values have types immutably assigned at creation, so >> you'll need to insert casts (trunc instructions in your case) to >> cast %1 and %2 from i32 to i16 for the smaller add. >> >> Nick >> >> >> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110124/be5f9cd8/attachment.html>
On 24 January 2011 10:05, Douglas do Couto Teixeira < douglasdocouto at gmail.com> wrote:> > > On Mon, Jan 24, 2011 at 3:01 PM, Nick Lewycky <nicholas at mxc.ca> wrote: > >> On 01/24/2011 04:41 AM, Douglas do Couto Teixeira wrote: >> >>> Hi, >>> >>> Nick, thanks for the reply. >>> I still have a problem: I only need to "clone" an Instruction, changing >>> its type. That is, I would like to keep all characteristics of the old >>> Instruction and create a new one only with a different type. >>> >> >> Sure, but what about its operands? An "add" instruction must have the same >> type as its operands, what do you want to do with them? > > > I also need to convert the type of the operands. But I want to do this when > they are created instead of inserting "trunc" instructions before performing > an operation. But it seems hard to me. >It is. You can walk upwards in a chain: a) if it's a constant, use ConstantExpr::getTrunc which will return another constant. b) if it's a memory load you can try to replace the pointer type too and recurse on that. But then what do you do if it's a load of a global variable? c) what if it's the type returned by a function call? Do you have a different function you can call instead? Are you going to recursively transform that function too? d) what if it's an Argument? You'll have to change the function's type which means creating a new function and splicing all the basic blocks from the old one into a new one -- then updating every call site. And don't forget that for each instruction you touch, you need to update all of their users too. Nick Suppose you're going from a 32-bit add to a 64-bit add, do the old operands>> get zero extended? Sign extended? You'll need to insert instructions for >> that (unless they're constants in which case you can use constant >> expressions). Similarly, what if the old type is a float and the new one is >> an int? float to signed int, float to unsigned int, or bitcast (only legal >> sometimes)? > > > I believe I don't need worry about it because I only create smaller > instructions. So I never convert a 32-bit instruction in a 64-bit > instruction. > > >> >> >> I am trying >> >>> create a new Instruction thus: >>> >>> %3 = add nsw i32 %1, %2 ; <i16> [#uses=2] //Old Instruction >>> >>> Value* Op0 = I->getOperand(0); >>> Value* Op1 = I->getOperand(1); >>> Value* V0 = new Value(Type::getInt16Ty(Op0->getContext()), >>> Op0->getValueID()); >>> >> >> Hunh, Value's constructor is protected. >> >> In any event, Value is pure base. Constructing one this way will never get >> you what you want. If the ValueID indicates an Instruction, go through >> Instruction to create one. >> >> >> Value* V1 = new Value(Type::getInt16Ty(Op1->getContext()), >>> Op1->getValueID()); >>> Instruction* newInst = BinaryOperator::CreateNSWAdd(V0, V1, "test"); >>> errs() << "NewInst:\n" << *newInst << "\n"; >>> >>> >>> But I get something like this: >>> >>> %test = add nsw i16 <badref>, <badref> ; <i16> [#uses=0] >>> >> >> The two instructions V0 and V1 you created were never inserted into the >> BasicBlock so they can't be numbered, and also they don't have names. >> >> >> What I am doing wrong? >>> >> >> Suppose that you're going from i32 to i16. Your only choice with that >> particular pair of types is a truncate. So: >> >> IRBuilder builder(OldInst); >> Value *V0 = builder.CreateTrunc(Op0, Type::getInt16Ty()); >> Value *V1 = builder.CreateTrunc(Op1, Type::getInt16Ty()); >> Value *Add = builder.CreateNSWAdd(V0, V1, "test"); >> >> The IRBuilder will take care of the distinction between instructions and >> constants for you. Note that I have not tested the above code, it may need >> some fixing before it compiles. >> >> Nick >> >> >>> >>> Best, >>> >>> Douglas >>> >>> On Fri, Jan 21, 2011 at 8:25 PM, Nick Lewycky <nlewycky at google.com >>> <mailto:nlewycky at google.com>> wrote: >>> >>> On 21 January 2011 12:56, Douglas do Couto Teixeira >>> <douglasdocouto at gmail.com <mailto:douglasdocouto at gmail.com>> wrote: >>> >>> Hello guys, >>> >>> I wonder how I can change the type of an integer variable. For >>> instance, given the instruction "%3 = add i32 %1, %2" I would >>> like to alter the instruction to "%3 = add i16 %1, %2". Is there >>> any way to do this? >>> >>> >>> No. Instead you create a new Instruction, in this case with >>> BinaryOperator::CreateAdd, then OldInst->replaceAllUsesWith(NewInst) >>> to update all the users, then OldInst->eraseFromParent() since it's >>> now dead code. >>> >>> Also, all values have types immutably assigned at creation, so >>> you'll need to insert casts (trunc instructions in your case) to >>> cast %1 and %2 from i32 to i16 for the smaller add. >>> >>> Nick >>> >>> >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >> >> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110124/d1b072c4/attachment.html>
On 1/24/11 12:05 PM, Douglas do Couto Teixeira wrote:> > > On Mon, Jan 24, 2011 at 3:01 PM, Nick Lewycky <nicholas at mxc.ca > <mailto:nicholas at mxc.ca>> wrote: > > On 01/24/2011 04:41 AM, Douglas do Couto Teixeira wrote: > > Hi, > > Nick, thanks for the reply. > I still have a problem: I only need to "clone" an Instruction, > changing > its type. That is, I would like to keep all characteristics of > the old > Instruction and create a new one only with a different type. > > > Sure, but what about its operands? An "add" instruction must have > the same type as its operands, what do you want to do with them? > > > I also need to convert the type of the operands. But I want to do this > when they are created instead of inserting "trunc" instructions before > performing an operation. But it seems hard to me.Actually, I don't think it will be that difficult. You basically need to do the following: 1) Take the backwards, intra-procedural slice of the instruction (i.e., find the instructions, operands, the operands' operands, the operands' operands' operands, etc.). 2) Visit all of the instructions in the slice and convert them. You want to visit definitions before uses. To do that, a) Make new phi instructions for all phis in the slice. The operands of the phis should be the Undef value. b) Use the dominator tree analysis and traverse basic blocks in dominator tree order (i.e., start at the top of the dominator tree and process each node breadth first). Convert all of the instructions in each basic block (except phis). c) Revisit all the phis and plug in their new operands. 3) Delete all the old instructions. This is a variation of the SSA construction algorithm in Zadeck et. al.'s paper (Effeciently Computing Single Static Assignment Form and the Control Dependence Graph). The only tricky part is handling non-instruction operands (e.g., function arguments, global variables, etc.). Some might be trivial to convert. Others may be difficult. You should look over all the classes derived from llvm::Value and decide how difficult it would be to convert them. -- John T.> Suppose you're going from a 32-bit add to a 64-bit add, do the old > operands get zero extended? Sign extended? You'll need to insert > instructions for that (unless they're constants in which case you > can use constant expressions). Similarly, what if the old type is > a float and the new one is an int? float to signed int, float to > unsigned int, or bitcast (only legal sometimes)? > > > I believe I don't need worry about it because I only create smaller > instructions. So I never convert a 32-bit instruction in a 64-bit > instruction. > > > > I am trying > > create a new Instruction thus: > > %3 = add nsw i32 %1, %2 ; <i16> [#uses=2] //Old Instruction > > Value* Op0 = I->getOperand(0); > Value* Op1 = I->getOperand(1); > Value* V0 = new Value(Type::getInt16Ty(Op0->getContext()), > Op0->getValueID()); > > > Hunh, Value's constructor is protected. > > In any event, Value is pure base. Constructing one this way will > never get you what you want. If the ValueID indicates an > Instruction, go through Instruction to create one. > > > Value* V1 = new Value(Type::getInt16Ty(Op1->getContext()), > Op1->getValueID()); > Instruction* newInst = BinaryOperator::CreateNSWAdd(V0, V1, > "test"); > errs() << "NewInst:\n" << *newInst << "\n"; > > > But I get something like this: > > %test = add nsw i16 <badref>, <badref> ; <i16> [#uses=0] > > > The two instructions V0 and V1 you created were never inserted > into the BasicBlock so they can't be numbered, and also they don't > have names. > > > What I am doing wrong? > > > Suppose that you're going from i32 to i16. Your only choice with > that particular pair of types is a truncate. So: > > IRBuilder builder(OldInst); > Value *V0 = builder.CreateTrunc(Op0, Type::getInt16Ty()); > Value *V1 = builder.CreateTrunc(Op1, Type::getInt16Ty()); > Value *Add = builder.CreateNSWAdd(V0, V1, "test"); > > The IRBuilder will take care of the distinction between > instructions and constants for you. Note that I have not tested > the above code, it may need some fixing before it compiles. > > Nick > > > > Best, > > Douglas > > On Fri, Jan 21, 2011 at 8:25 PM, Nick Lewycky > <nlewycky at google.com <mailto:nlewycky at google.com> > <mailto:nlewycky at google.com <mailto:nlewycky at google.com>>> wrote: > > On 21 January 2011 12:56, Douglas do Couto Teixeira > <douglasdocouto at gmail.com <mailto:douglasdocouto at gmail.com> > <mailto:douglasdocouto at gmail.com > <mailto:douglasdocouto at gmail.com>>> wrote: > > Hello guys, > > I wonder how I can change the type of an integer > variable. For > instance, given the instruction "%3 = add i32 %1, %2" I > would > like to alter the instruction to "%3 = add i16 %1, %2". > Is there > any way to do this? > > > No. Instead you create a new Instruction, in this case with > BinaryOperator::CreateAdd, then > OldInst->replaceAllUsesWith(NewInst) > to update all the users, then OldInst->eraseFromParent() > since it's > now dead code. > > Also, all values have types immutably assigned at creation, so > you'll need to insert casts (trunc instructions in your > case) to > cast %1 and %2 from i32 to i16 for the smaller add. > > Nick > > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> > http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110124/acf9bc56/attachment.html>
Douglas do Couto Teixeira
2011-Jan-28 23:01 UTC
[LLVMdev] How to change the type of an Instruction?
Hi, guys,
Thanks a lot for your help. As you know, I am trying to implement
something to change the types of the instructions. And I chose the trunc's
approach because it seems be simple. But I still have some problems and
questions. Would be great if you can help me.
I have used the results of my range analysis implementation to change
the intermediate representation. I am using the very simple expedient of
inserting a trunc right after the definition of a small variable, and
inverse truncation right after the uses of this variable. I am doing this
for correctness. So, if I have something like:
a = b + c
...
x = a + y
...
w = a - z
Then I change the program into:
a = b + c
a_small = trunc(a)
...
a1 = truncInv(a_small)
x = a1 + y
...
a2 = truncInv(a_small)
w = a2 - z
Again, I did it like this just to check for correctness. But, even if I
optimize the insertion of truncs, it seems that the end code will not be
good, and I am afraid I will miss many optimization opportunities. Like, one
of the first things that would pay off would be small peephole optmizations,
such as removing unnecessary truncation, or using small multiplication
whenever possible, and eliminating instructions such as x = y & 0xFF,
whenever I know that y < 0xFF. So, what I would like to ask you is this: is
it right to do bitwidth analysis at the intermediate representation level,
or should I re-implement my analysis at the machine level? The type system
seems to be getting in my way at the intermediate level. If I go to the
machine level, can I avoid this types of problems?
Thank you a lot,
Douglas
On Mon, Jan 24, 2011 at 4:24 PM, John Criswell <criswell at
illinois.edu>wrote:
> On 1/24/11 12:05 PM, Douglas do Couto Teixeira wrote:
>
>
>
> On Mon, Jan 24, 2011 at 3:01 PM, Nick Lewycky <nicholas at mxc.ca>
wrote:
>
>> On 01/24/2011 04:41 AM, Douglas do Couto Teixeira wrote:
>>
>>> Hi,
>>>
>>> Nick, thanks for the reply.
>>> I still have a problem: I only need to "clone" an
Instruction, changing
>>> its type. That is, I would like to keep all characteristics of the
old
>>> Instruction and create a new one only with a different type.
>>>
>>
>> Sure, but what about its operands? An "add" instruction must
have the
>> same type as its operands, what do you want to do with them?
>
>
> I also need to convert the type of the operands. But I want to do this when
> they are created instead of inserting "trunc" instructions before
performing
> an operation. But it seems hard to me.
>
>
> Actually, I don't think it will be that difficult. You basically need
to
> do the following:
>
> 1) Take the backwards, intra-procedural slice of the instruction (i.e.,
> find the instructions, operands, the operands' operands, the
operands'
> operands' operands, etc.).
>
> 2) Visit all of the instructions in the slice and convert them. You want
> to visit definitions before uses. To do that,
> a) Make new phi instructions for all phis in the slice. The operands
> of the phis should be the Undef value.
> b) Use the dominator tree analysis and traverse basic blocks in
> dominator tree order (i.e., start at the top of the dominator tree and
> process each node breadth first). Convert all of the instructions in each
> basic block (except phis).
> c) Revisit all the phis and plug in their new operands.
>
> 3) Delete all the old instructions.
>
> This is a variation of the SSA construction algorithm in Zadeck et.
al.'s
> paper (Effeciently Computing Single Static Assignment Form and the Control
> Dependence Graph).
>
> The only tricky part is handling non-instruction operands (e.g., function
> arguments, global variables, etc.). Some might be trivial to convert.
> Others may be difficult. You should look over all the classes derived from
> llvm::Value and decide how difficult it would be to convert them.
>
> -- John T.
>
>
>
>
>
>> Suppose you're going from a 32-bit add to a 64-bit add, do the old
>> operands get zero extended? Sign extended? You'll need to insert
>> instructions for that (unless they're constants in which case you
can use
>> constant expressions). Similarly, what if the old type is a float and
the
>> new one is an int? float to signed int, float to unsigned int, or
bitcast
>> (only legal sometimes)?
>
>
> I believe I don't need worry about it because I only create smaller
> instructions. So I never convert a 32-bit instruction in a 64-bit
> instruction.
>
>
>>
>>
>> I am trying
>>
>>> create a new Instruction thus:
>>>
>>> %3 = add nsw i32 %1, %2 ; <i16> [#uses=2] //Old Instruction
>>>
>>> Value* Op0 = I->getOperand(0);
>>> Value* Op1 = I->getOperand(1);
>>> Value* V0 = new Value(Type::getInt16Ty(Op0->getContext()),
>>> Op0->getValueID());
>>>
>>
>> Hunh, Value's constructor is protected.
>>
>> In any event, Value is pure base. Constructing one this way will never
get
>> you what you want. If the ValueID indicates an Instruction, go through
>> Instruction to create one.
>>
>>
>> Value* V1 = new Value(Type::getInt16Ty(Op1->getContext()),
>>> Op1->getValueID());
>>> Instruction* newInst = BinaryOperator::CreateNSWAdd(V0, V1,
"test");
>>> errs() << "NewInst:\n" << *newInst <<
"\n";
>>>
>>>
>>> But I get something like this:
>>>
>>> %test = add nsw i16 <badref>, <badref> ; <i16>
[#uses=0]
>>>
>>
>> The two instructions V0 and V1 you created were never inserted into
the
>> BasicBlock so they can't be numbered, and also they don't have
names.
>>
>>
>> What I am doing wrong?
>>>
>>
>> Suppose that you're going from i32 to i16. Your only choice with
that
>> particular pair of types is a truncate. So:
>>
>> IRBuilder builder(OldInst);
>> Value *V0 = builder.CreateTrunc(Op0, Type::getInt16Ty());
>> Value *V1 = builder.CreateTrunc(Op1, Type::getInt16Ty());
>> Value *Add = builder.CreateNSWAdd(V0, V1, "test");
>>
>> The IRBuilder will take care of the distinction between instructions
and
>> constants for you. Note that I have not tested the above code, it may
need
>> some fixing before it compiles.
>>
>> Nick
>>
>>
>>>
>>> Best,
>>>
>>> Douglas
>>>
>>> On Fri, Jan 21, 2011 at 8:25 PM, Nick Lewycky <nlewycky at
google.com
>>> <mailto:nlewycky at google.com>> wrote:
>>>
>>> On 21 January 2011 12:56, Douglas do Couto Teixeira
>>> <douglasdocouto at gmail.com <mailto:douglasdocouto at
gmail.com>> wrote:
>>>
>>> Hello guys,
>>>
>>> I wonder how I can change the type of an integer variable.
For
>>> instance, given the instruction "%3 = add i32 %1,
%2" I would
>>> like to alter the instruction to "%3 = add i16 %1,
%2". Is there
>>> any way to do this?
>>>
>>>
>>> No. Instead you create a new Instruction, in this case with
>>> BinaryOperator::CreateAdd, then
OldInst->replaceAllUsesWith(NewInst)
>>> to update all the users, then OldInst->eraseFromParent()
since it's
>>> now dead code.
>>>
>>> Also, all values have types immutably assigned at creation, so
>>> you'll need to insert casts (trunc instructions in your
case) to
>>> cast %1 and %2 from i32 to i16 for the smaller add.
>>>
>>> Nick
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110128/f594915e/attachment.html>
Apparently Analagous Threads
- [LLVMdev] How to change the type of an Instruction?
- [LLVMdev] How to change the type of an Instruction?
- [LLVMdev] How to change the type of an Instruction?
- [LLVMdev] How to change the type of an Instruction?
- [LLVMdev] How to change the type of an Instruction?