[LLVMdev] mem2reg optimization

Nicolas Capens nicolas at capens.net
Mon Oct 6 22:32:09 PDT 2008

Hi Dan,

I don't want to beat a dead horse here, but why would anyone want to use
mem2reg after LICM or other passes that can move around loads and stores? I
fully understand the design goal to arbitrarily reorder other passes but for
mem2reg it actually seems vital to run it as the first pass to make all
other passes useful.

Anyway, this can definitely also be done with an analysis pass that provides
information about ordering between loads and stores. It's just ironic that
this information is already available in the use lists if you run mem2reg as
the first pass...



-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Dan Gohman
Sent: Friday, 03 October, 2008 19:34
To: LLVM Developers Mailing List
Cc: 'LLVM Developers Mailing List'
Subject: Re: [LLVMdev] mem2reg optimization

On Thu, October 2, 2008 10:17 am, Nicolas Capens wrote:
> Hi all,
> I haven't had a chance yet to do some accurate profiling, but does anyone
> have some more insight in the use list order? *bump*

I thought this was answered; use lists are not currently in
any intentional order.

> It seems very valuable to me (from a performance standpoint) to keep the
> use
> list in (reverse) order. But if this can't be guaranteed it might still be
> interesting to have some fast variants of passes that do make some
> assumptions (like my patch for mem2reg). I believe I can optimize more
> passes by making such assumption about the order of the use lists, so any
> and all information about that is welcome.

Keeping use lists sorted, in general, seems expensive. Take a pass
like LICM; when an Instruction is hoisted from a loop, its position
in any use lists it's on may need to change if they are to remain
sorted. Determining the new position would require determining
where the other instructions in the list are.

The property of being able to arbitrarily reorder LLVM passes
is an important design goal. I don't think we want to have variants
that make assumptions about use list ordering unless there are
very significant advantages.

That said, it's an interesting idea. Would you be able to
perform the same optimizations using an analysis pass that
provides a topological ordering for all Instructions?


LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu

More information about the llvm-dev mailing list