llvm dev - May 2017 - UD and DU chains for LLVM IR before running mem2reg

Hi,


Just had  a simple question ,


The use-def and def-use chains provided by llvm::Value class ,

would they work for IR that has not been optimized by the "mem2reg"
pass ?

( ie, IR code that contains memory interactions and is not in SSA form yet )


Thanks,

Malhar
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170525/d6ef82a8/attachment.html>

On 25 May 2017, at 12:54, Jajoo, Malhar via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> The use-def and def-use chains provided by llvm::Value class ,
> would they work for IR that has not been optimized by the
"mem2reg" pass ?
> ( ie, IR code that contains memory interactions and is not in SSA form yet
)
It depends on what you mean by ‘work’.  They will exist and will link
instructions, but all loads and stores to an alloca will appear as uses of that
alloca.

David

On 25 May 2017, at 17:06, Jajoo, Malhar <malhar.jajoo14 at imperial.ac.uk>
wrote:
> 
> Hi David,
> 
> Thanks for your reply. 
> However , 1 small issue with that  - 
> 
> let's say on seeing a particular variable , I want to find the most
recent assignment to that (  store instruction )  variable , how will I be able
to find the most recent ( since the allocas are pushed to the top of the IR (
and hence the most recent use may not be the actual one in my custom language )
This is nontrivial (if it were easy, we wouldn’t bother with SSA form), because
it depends on the CFG.  There may not even be a single most recent store.  For
example, consider the following code:

int x;
if (y == 0)
  x = 1;
else
  x = 2;
foo(x);

At the call to foo(x), what is the most recent store to x?  It depends on which
path through the CFG was taken: it’s either x=1 or x=2.  If you perform SSA
construction, then you will end up with a phi node[1] and an SSA register rather
than stores to an alloca for x.

The real question is why do you want to avoid using the mechanisms that are
explicitly designed to solve these problems?  Do they not work for something in
your language?

David

[1] Actually, in this example, you’ll end up with a select instruction, but
ignore that for now.

On 25 May 2017, at 17:32, Jajoo, Malhar <malhar.jajoo14 at imperial.ac.uk>
wrote:
> 
> 
> Hi David,
> 
> Thanks for your reply , I am aware of those issues.
> ( my issue is quite complex - monomorphization for iN types at runtime ) 
This shouldn’t preclude performing SSA construction.
> However, I have a simpler question -
> 
> Do the "alloca" instructions need to be at the top always ?
> and do they need to be in reverse order ( reverse order of parameters and
then reverse order of variable declarations ?)
No, with two caveats:

 - mem2reg / SROA will only work reliably with allocas in the entry block

 - Alloca instructions will allocate stack space whenever they are reached: if
you accidentally put one in a loop then you can end up increasing your stack
size considerably (if you actually dynamic allocations dependent on control
flow, you are advised to look at the stack save and restore intrinsics).

David