[LLVMdev] analysis and transformation of Machine IRs

Akira Hatanaka ahatanak at gmail.com
Thu Aug 26 11:05:05 PDT 2010


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>


More information about the llvm-dev mailing list