llvm dev - Sep 2016 - ScalarEvolution pass and interprocedural analysis

Hello all,

I was looking for an analysis pass that could provide comprehensive
information on pointer arithmetic in the context of whole-program
optimization. It seems that Scalar Evolution provides exactly what I'm
looking for, but it is restricted to only intraprocedural analysis.

E.g., consider this toy snippet:

void foo(int* p) { (*p)++; }

int bar() {
  int i;
  for (i = 0; i < n; i++) {
    foo(&i);
  }
  return i;
}

Here Scalar Evolution will not be able to compute a SCEV expression on
`i` (assume no inline of foo).

So, two questions: (1) is there a way to make Scalar Evolution work in
an interprocedural manner? (2) would it be too expensive in terms of
compilation time for real-world (think memcached, nginx) programs?

Any feedback/hints/papers are welcome, thanks in advance. Also, any
good manual on how ScalarEvolution can be used in LLVM would be great
(currently I'm looking into how other LLVM passes use it).

-- 
Yours sincerely,
Dmitrii Kuvaiskii

Hi Dmitrii,

Dmitrii Kuvaiskii via llvm-dev wrote:
 > So, two questions: (1) is there a way to make Scalar Evolution work in
 > an interprocedural manner? (2) would it be too expensive in terms of
 > compilation time for real-world (think memcached, nginx) programs?

Promoting SCEV to an inter-procedural analysis will be a lot of work.
Have you been running into cases like the above in practice?  In the
example you gave, `foo` should most certainly have been inlined.

 > Any feedback/hints/papers are welcome, thanks in advance. Also, any
 > good manual on how ScalarEvolution can be used in LLVM would be great
 > (currently I'm looking into how other LLVM passes use it).

Looking at how other passes in LLVM use it is probably the right path
forward.  Feel free to ask any questions you have (either here on the
dev list or on IRC).

Thanks,
-- Sanjoy

Thank you for the answer, Sanjoy.

Here is a follow-up question on Scalar Evolution. I cannot figure out
what requirements are expected in isKnownPredicate().

Here is my code snippet in C (I don't care about loops for now, just a
single BB):
```
  char foo[10];
  size_t offset = <generally unknown>;
  ...
  foo[offset] = 32;
  foo[offset+1] = 23;
```

Here is the relevant result of running Scalar Evolution:
```
  %arrayidx = getelementptr inbounds [1000 x i8], [1000 x i8]* @foo,
i64 0, i64 %offset
  -->  (%offset + @foo)<nsw> U: full-set S: full-set
  ...
  %arrayidx1 = getelementptr inbounds [1000 x i8], [1000 x i8]* @foo,
i64 0, i64 %add
  -->  (1 + %offset + @foo) U: full-set S: full-set
```

Now I want to compare these two SCEVs in my pass via:
  SE->isKnownPredicate(ICmpInst::ICMP_ULT, scev1, scev2);

But whatever predicate I choose (ICMP_ULT, ICMP_SLT, ICMP_UGE,
ICMP_SGE), it is always false.
I expected that at least one of them will return true, since the code
snippet looks like the first SCEV is always less than the second one,
even in the case of integer overflow.
I also don't understand why the first SCEV has <nsw>, but not the
second one.

If isKnownPredicate() is the wrong method for this, what could be used instead?

On Mon, Sep 5, 2016 at 12:58 AM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:
> Hi Dmitrii,
>
> Dmitrii Kuvaiskii via llvm-dev wrote:
>> So, two questions: (1) is there a way to make Scalar Evolution work in
>> an interprocedural manner? (2) would it be too expensive in terms of
>> compilation time for real-world (think memcached, nginx) programs?
>
> Promoting SCEV to an inter-procedural analysis will be a lot of work.
> Have you been running into cases like the above in practice?  In the
> example you gave, `foo` should most certainly have been inlined.
>
>> Any feedback/hints/papers are welcome, thanks in advance. Also, any
>> good manual on how ScalarEvolution can be used in LLVM would be great
>> (currently I'm looking into how other LLVM passes use it).
>
> Looking at how other passes in LLVM use it is probably the right path
> forward.  Feel free to ask any questions you have (either here on the
> dev list or on IRC).
>
> Thanks,
> -- Sanjoy


-- 
Yours sincerely,
Dmitrii Kuvaiskii