llvm dev - Nov 2010 - [LLVMdev] Question About Target Dependent Optimization

My name is Isaac. I'm a student at Cal Poly State University, San Luis
Obispo, and I'm currently finishing my thesis on target-specific code
optimization for my master's degree. I was wondering if I could ask a few
questions I have about working with the LLVM codebase.

My thesis involves optimizing the way that LLVM deals with memory operations
when targeting the ARM processor (specifically the ARM and Thumb-2 ISAs).
Specifically, I'm writing a pass that runs just before the passes in the
ARMLoadStoreOptimizer.cpp file. I've already devised an algorithm that I
believe will work, and have it mostly implemented in LLVM, but I'm having
trouble with some of the details.

Specifically, I'm trying to rearrange the MachineInstrs within each
MachineBasicBlock. I've noticed that there are several tutorials in the
online documentation about creating LLVM IR transformations, but haven't
found any resources beyond the doxygen documentation for MachineInstr level
transformations. I have successfully analyzed the MachineInstrs using helper
classes that I have implemented, but I need to rearrange the MachineInstrs
themselves. When I naively use the MachineBasicBlock.remove() and
MachineBasicBlock.push_back() methods, pushing the MachineInstrs back onto
the MachineBasicBlock in a different order, LLVM crashes when I attempt to
compile a "hello world" style program. Looking at the stderr output I
setup
for logging purposes, it appears that moving the MachineInstrs in this way
does not update certain relevant information, such as when a register is
marked to be "killed."

I am continuing to look over the code in the ARMLoadStoreOptimizer.cpp file,
but I was wondering if you had a specific suggestion or a documentation
resource that I could use to perform this instruction rearrangement in an
LLVM idiomatic way. Using my algorithm, I already know where I can move
MachineInstrs without effecting program correctness, but I don't know how I
can reorder the MachineInstrs while maintaining all the associated
live-range information.

Thanks for your time, and I welcome any suggestions you might have for me,

Regards,

Isaac Asay
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101128/e2c7cab4/attachment.html>

On Nov 28, 2010, at 8:29 PM, Isaac Asay wrote:
> 
> I am continuing to look over the code in the ARMLoadStoreOptimizer.cpp
file, but I was wondering if you had a specific suggestion or a documentation
resource that I could use to perform this instruction rearrangement in an LLVM
idiomatic way. Using my algorithm, I already know where I can move MachineInstrs
without effecting program correctness, but I don't know how I can reorder
the MachineInstrs while maintaining all the associated live-range information.
After register allocation is complete, liveness information is kept in the
live-in lists on basic blocks, and kill flags on register operands.

Simply put, a register is live from a <def> operand to a <use,kill>
operand. It must not be used when it isn't live.

The rules get tricky when sub-registers are involved.

Your best bet for documentation is to read MachineVerifier.cpp and perhaps
RegisterScavenging.cpp.

If you are rearranging instructions, you must make sure that any kill flags are
moved to the last instruction using a register.

/jakob

Thanks for your response. I'm just now realizing that keeping track of
<kill> flags is harder than I thought it would be.

Regards,

Isaac


On Mon, Nov 29, 2010 at 10:47 AM, Jakob Stoklund Olesen <stoklund at
2pi.dk>wrote:
>
> On Nov 28, 2010, at 8:29 PM, Isaac Asay wrote:
> >
> > I am continuing to look over the code in the ARMLoadStoreOptimizer.cpp
> file, but I was wondering if you had a specific suggestion or a
> documentation resource that I could use to perform this instruction
> rearrangement in an LLVM idiomatic way. Using my algorithm, I already know
> where I can move MachineInstrs without effecting program correctness, but I
> don't know how I can reorder the MachineInstrs while maintaining all
the
> associated live-range information.
>
> After register allocation is complete, liveness information is kept in the
> live-in lists on basic blocks, and kill flags on register operands.
>
> Simply put, a register is live from a <def> operand to a
<use,kill>
> operand. It must not be used when it isn't live.
>
> The rules get tricky when sub-registers are involved.
>
> Your best bet for documentation is to read MachineVerifier.cpp and perhaps
> RegisterScavenging.cpp.
>
> If you are rearranging instructions, you must make sure that any kill flags
> are moved to the last instruction using a register.
>
> /jakob
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101204/a93edc83/attachment.html>