llvm dev - Aug 2010 - [LLVMdev] analysis and transformation of Machine IRs

Hello LLVM developers,

I have a few questions regarding analysis and transformation of Machine IRs.

I am writing a scheduling pass that transforms single basic block loops.
Details of the pass can be found in an email I sent two weeks ago.
http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-August/033808.html
I have changed my pass to run before Live Variable Analysis since then.

1, Induction variable recognition
I need to find which SSA value is used as the induction variable that
controls a loop. Currently I determine that a value is the induction
variable I am looking for if the following conditions are met:

1) it is an operand of either the branch instruction or the instruction that
sets the condition code for the branch
2) the instruction that defines the value uses an operand defined by a phi
instruction
3) the phi instruction uses the value

For example, in the code below which loops n times,

(begin)
...
(I0) v3 := n
(I1) v0 := 0
...
_LoopBody_:
(I2) v1 := phi(v0, v2)
...
(I3) v2 := v1 + 1
...
(I4) cmp v2, v3
(I5) brne _Loopbody_
...
(end)

v2 is the induction variable because,
1) v2 is an operand of I4
2) I3 uses v1, which is defined by a phi instruction
3) the phi instruction I2 uses v2

Is there a better way to do what I am trying to do?
Are there libraries I can use that work on Machine IRs?

2. Insertion of add/sub instructions.
I need to change the number of times a loop is executed. In order to do
that, I am considering modifying the value of the induction variable or the
exit value before entering the loop. For example, if I wanted to execute the
loop (n - 3) times in the code above, I could modify it in the following
ways:

1) add 3 to v0
(I1) v0 :(I1_1) v0_1 := v0 + 3  <= add inserted here
...
(I2) v1 := phi(v0_1, v2) <= change operand

2) subtract 3 from v3.
(I0) v3 :(I0.a) v3_1 := v3 - 3 <= sub inserted here
...
(I4) cmp v2, v3_1 <= change operand

Is there a class or function that generates an add or sub instruction in a
target-independent manner? I am looking for something similar to
TargetInstrInfo::copyRegTpReg but one that creates other types of
instructions.

Any advice, comments and suggestions are appreciated.

Thank you in advance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100826/b683bbfb/attachment.html>

On Aug 26, 2010, at 11:05 AM, Akira Hatanaka wrote:
> Is there a class or function that generates an add or sub instruction in a
target-independent manner?
No. Such a target hook does not exist.
> I am looking for something similar to TargetInstrInfo::copyRegTpReg but one
that creates other types of instructions.
It almost sounds like you should be writing a normal optimization pass that
operates on LLVM IR instead of a code generator pass. That is a lot easier too.
Are you doing something similar to LoopUnroll.cpp?

/jakob

Thank you for replying to my email.

On Tue, Aug 31, 2010 at 2:01 PM, Jakob Stoklund Olesen <stoklund at
2pi.dk>wrote:
>
> On Aug 26, 2010, at 11:05 AM, Akira Hatanaka wrote:
>
> > Is there a class or function that generates an add or sub instruction
in
> a target-independent manner?
>
> No. Such a target hook does not exist.
>
> > I am looking for something similar to TargetInstrInfo::copyRegTpReg
but
> one that creates other types of instructions.
>
> It almost sounds like you should be writing a normal optimization pass that
> operates on LLVM IR instead of a code generator pass. That is a lot easier
> too. Are you doing something similar to LoopUnroll.cpp?
>
> /jakob
>
>
It reorders and replicates instructions in the original machine basic block,
so in a sense it is similar to LoopUnroll.cpp.

As you have pointed out, I agree that an LLVM IR scheduling pass would be
much easier to write. However, since the scheduling pass I am writing uses
the target instructions' latency and resource usage information, it would be
hard to generate a good schedule if it were operating on the LLVM IR instead
of the Machine IR.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100831/9438b46f/attachment.html>