LLVM Inter-procedural Analysis on function arguments

Question

Hi, I have some questions about inter-procedural analysis in LLVM.

For example, let's say that there is a code as following:

void f1(int *a, int *b, int *c) {...}
void f2(int *a, int *b, int *c) {...}

int main() {
  int *a = malloc (...);
  int *b = malloc (...);
  int *c = malloc (...);
  int *d = malloc (...);
  int *e = malloc (...);

  f1(a, b, c);
  f2(c, d, e);

  return 0;
}

I want to make information whether in attribute or metadata that f1's third argument is identical to f2's first argument.

But I am not sure the way to approach this.

I thought of Alias Analysis can lead me the way but it seems kind of different from what I'm trying to do.

The easiest way can be just iterating function arguments and collect information but doesn't seem to be safe at all.

Any advice will be helpful.

Thanks, Jake

arnt arnt · Accepted Answer · 2020-11-25T08:32:56

This is made simpler by LLVM IR being an SSA language.

What you want is (in C-like languages) to know whether c1 and b2 are the same in f1(a1, b1, c2); f2(a2, b2, c3);, right? When you have converted that to SSA form, in LLVM IR, that will be two call instructions, perhaps call @f1, %a1, %b1, %c1 and call @f2, %a2, %b2, %c2. Unlike in the C-like source, %c1 and %b2 aren't variables, they're values. They're initialised exactly once (SSA means static single assignment), so checking whether %a3 and %b2 are equal just requires looking at exactly two definitions and testing for equality. If they are, you call a3.replaceAllUsesWith(b2) and you're done.

Testing for equality may be trickier than it sounds, though. For example, if the two values are (unsigned int)(4+3) and (signed int)(2+3+2) in the source language, the IR will look similar, but most compilers will not produce the exact same IR. Are values of two different types equal, anyway, in your context? And what if the values are (signed byte)(127+127+2) and (unsigned int)(256)?

And are you sane or multithreaded — what if one value is written to memory and immediately read back (but might have been changed by another thread in the right nanosecond)? Equality testing offers many opportunities for pedantry.

You will find some useful helper functions in ConstantFolding.h, and depending on source language it may be helpful to require that the mem2reg pass is run before your analysis. Good luck.

LLVM Inter-procedural Analysis on function arguments

1 Answers