Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?

Project Infrastructure LLVM Dev List Archives
1

Hi all,

I’m playing around with implementing an existing non-LLVM AA algorithm as an LLVM AA pass. I’m looking for suggestions for getting it to fit in AliasAnalysis’s worldview, so that it might eventually be a candidate for inclusion in LLVM.

The algorithm maintains a may-point-to graph. Unfortunately the algorithm doesn’t delete an “A–>B” edge when there’s a strong update of “A” but the value copied into “A” isn’t a pointer. So the interpretation of “A” having only one outbound edge (to “B”) is a little ambiguous. It means “‘A’ definitely points to ‘B’, or ‘A’ doesn’t hold a valid pointer.”

This makes it hard for the algorithm to ever return a MustAlias result. If the graph has just two edges, “A–>C” and “B–>C”, then the most precise answer it could give for “alias(A,B)” would be “MustAlias or NoAlias, I’m not sure which”. AFAIK, with the current interface I’d have to return “MayAlias” in that case, which is unsatisfying.

One solution would be for me to adapt the algorithm to remove this ambiguity. But if possible I’d like to keep the algorithm as close to the published version as possible, so I’d rather find another solution.

Another approach is to add a value to the AliasResult enumeration, indicating “MustAlias or NoAlias, I’m not sure which”. But I’m not sure if any downstream analyses could make use of a result like that.

A third, even uglier solution would be to modify the AliasAnalysis::alias(…) methods to let the caller indicate whether or not the supplied Values can be assumed to actually contain pointers. But this strikes me as an unreasonable concession to this one AA algorithm’s quirks.

Any suggestions for how to proceed?

Thanks, Christian

2

Hi all,

I'm playing around with implementing an existing non-LLVM AA algorithm as an
LLVM AA pass. I'm looking for suggestions for getting it to fit in
AliasAnalysis's worldview, so that it might eventually be a candidate for
inclusion in LLVM.

The algorithm maintains a may-point-to graph. Unfortunately the algorithm
doesn't delete an "A-->B" edge when there's a strong update of "A" but the
value copied into "A" isn't a pointer. So the interpretation of "A" having
only one outbound edge (to "B") is a little ambiguous. It means "'A'
definitely points to 'B', or 'A' doesn't hold a valid pointer."

Define "valid pointer please"?

This makes it hard for the algorithm to ever return a MustAlias result. If
the graph has just two edges, "A-->C" and "B-->C", then the most precise
answer it could give for "alias(A,B)" would be "MustAlias or NoAlias, I'm
not sure which". AFAIK, with the current interface I'd have to return
"MayAlias" in that case, which is unsatisfying.

So i'm trying to understand what harm would come from returning MustAlias here?
If the value is undef, then we can pick one for which MustAlias is true.
If it's something else, i need to understand how you define "valid pointer".

(I agree there are situations where this would be the wrong answer,
which is why i'm trying to understand what valid pointer means)

One solution would be for me to adapt the algorithm to remove this
ambiguity. But if possible I'd like to keep the algorithm as close to the
published version as possible, so I'd rather find another solution.

Why?
Published versions are often ... wrong, not well engineered, etc :slight_smile:

Another approach is to add a value to the AliasResult enumeration,
indicating "MustAlias or NoAlias, I'm not sure which". But I'm not sure if
any downstream analyses could make use of a result like that.

Above, you say you want to not return MustAlias.
Here you say it's not clear that any downstream results could make use
of better info.

Before you go and try to figure out what should change, you really
need to actually determine whether the info you have is valuable.

I would do this by finding a pass you think you can improve with your
extra info, and seeing if it improves (add a temporary hack AA
function or something that gives info about this) by giving it must/no
vs may.

If something improves, great, we can figure out whether it's worth the
tradeoffs/etc and help you figure out what to do.
If nothing improves, it may not be worth you spending your time on it.

3

> The algorithm maintains a may-point-to graph. Unfortunately the
algorithm
> doesn't delete an "A-->B" edge when there's a strong update of "A" but
the
> value copied into "A" isn't a pointer. So the interpretation of "A"
having
> only one outbound edge (to "B") is a little ambiguous. It means "'A'
> definitely points to 'B', or 'A' doesn't hold a valid pointer."

Define "valid pointer please"?

Sorry, I can see how my phrasing raised a red flag.

The original version of the algorithm I'm looking at was designed to
analyze C source code, not LLVM IR. I'm in the process of adapting its
dataflow equations for IR.

The algorithm assumes that a correct C program can't just compute pointer
values *ex nihilo*; that they can only by obtained from certain syntactic
structures like variable declarations, or calls to *malloc*, or pointer
literals. The AA algorithm reckons that dereferencing a runtime value
obtained by some other mechanism is so likely to be a bug, that they can
skip worrying about it.

The AA algorithm uses dataflow analysis to monitor the possible propagation
of those values through the program code, and it represents those flows by
updates to the may-point-to graph. If at some code point CP, a
may-point-to graph vertex "B" has no outbound edges, that's equivalent to
saying that the AA has concluded the runtime memory modeled by "B" does not
contain any pointer that a correct program has any business trying to
dereference.

So to restate my point in the earlier email: if there's a strong-update of
the form "*A = 42;" (in C parlance), it would be nice to have this AA
algorithm remove any may-point-to graph edges originating at "A" at that
point. But, for the sake of efficiency (in the author's judgment), such
assignments are simply ignored by the dataflow equations. And so any
existing may-point-to edges originating at "A" are allowed to remain in
existence.

> One solution would be for me to adapt the algorithm to remove this

ambiguity. But if possible I'd like to keep the algorithm as close to the
> published version as possible, so I'd rather find another solution.

Why?
Published versions are often ... wrong, not well engineered, etc :slight_smile:

I'm not dead-set against modifying it, I'm just biased against doing it
without a good reason. I'm relatively new to implementing AA algorithms,
and the author seems to have put a great deal of thought into this
algorithm. So I'm trying to follow a policy of "If it's not broken, don't
fix it." Also, the more I can remain faithful to the algorithm's original
writeup, the less I'm on the hook to write my own documentation for my
implementation.

>
> Another approach is to add a value to the AliasResult enumeration,
> indicating "MustAlias or NoAlias, I'm not sure which". But I'm not sure
if
> any downstream analyses could make use of a result like that.

Above, you say you want to not return MustAlias.
Here you say it's not clear that any downstream results could make use
of better info.

Before you go and try to figure out what should change, you really
need to actually determine whether the info you have is valuable.

I would do this by finding a pass you think you can improve with your
extra info, and seeing if it improves (add a temporary hack AA
function or something that gives info about this) by giving it must/no
vs may.

If something improves, great, we can figure out whether it's worth the
tradeoffs/etc and help you figure out what to do.
If nothing improves, it may not be worth you spending your time on it.

Thanks, will do. I appreciate the feedback!

- Christian

4

> The algorithm maintains a may-point-to graph. Unfortunately the
> algorithm
> doesn't delete an "A-->B" edge when there's a strong update of "A" but
> the
> value copied into "A" isn't a pointer. So the interpretation of "A"
> having
> only one outbound edge (to "B") is a little ambiguous. It means "'A'
> definitely points to 'B', or 'A' doesn't hold a valid pointer."

Define "valid pointer please"?

Sorry, I can see how my phrasing raised a red flag.

The original version of the algorithm I'm looking at was designed to analyze
C source code, not LLVM IR. I'm in the process of adapting its dataflow
equations for IR.

The algorithm assumes that a correct C program can't just compute pointer
values ex nihilo; that they can only by obtained from certain syntactic
structures like variable declarations, or calls to malloc, or pointer
literals.

While true in theory, this is 100% wrong in practice :wink:

The AA algorithm reckons that dereferencing a runtime value
obtained by some other mechanism is so likely to be a bug, that they can
skip worrying about it.

Given that things like "calculating vtable addresses", etc, end up
looking indistinguishably the same at the IR level, you can't really.

The AA algorithm uses dataflow analysis to monitor the possible propagation
of those values through the program code, and it represents those flows by
updates to the may-point-to graph. If at some code point CP, a may-point-to
graph vertex "B" has no outbound edges, that's equivalent to saying that the
AA has concluded the runtime memory modeled by "B" does not contain any
pointer that a correct program has any business trying to dereference.

FWIW: When i first did GCC's current points-to analysis, I did the
same thing. It eliminated "non-pointer" values along the same lines.
This broke roughly "the entire world".

I tried to find some subset i felt was worthwhile and where it was
okay, but gave up after a while.

5

> The AA algorithm uses dataflow analysis to monitor the possible
propagation
> of those values through the program code, and it represents those flows
by
> updates to the may-point-to graph. If at some code point CP, a
may-point-to
> graph vertex "B" has no outbound edges, that's equivalent to saying that
the
> AA has concluded the runtime memory modeled by "B" does not contain any
> pointer that a correct program has any business trying to dereference.

FWIW: When i first did GCC's current points-to analysis, I did the
same thing. It eliminated "non-pointer" values along the same lines.
This broke roughly "the entire world".

Whoa, thanks for the warning.

I tried to find some subset i felt was worthwhile and where it was
okay, but gave up after a while.

I'm not quite sure which things you're referring to in that statement.
Would you mind clarifying?

6

You can try to ameliorate it by doing things like say "well, we
believe code patterns that look like this generate valid pointers,
but patterns that look like this can be ignored". It is very hard to
find a set of patterns you allow that gives you anything meaningfully
better, but doesn't still break the world.

As for your statement on authors putting a lot of thought into
published algorithms - they do, but honestly, published algorithms
should generally be treated like a starting point. They are often
vastly simplified for publication, or otherwise in need of significant
*engineering* work.

7

>> I tried to find some subset i felt was worthwhile and where it was
>> okay, but gave up after a while.
>
>
> I'm not quite sure which things you're referring to in that statement.
> Would you mind clarifying?

You can try to ameliorate it by doing things like say "well, we
believe code patterns that look like this generate valid pointers,
but patterns that look like this can be ignored". It is very hard to
find a set of patterns you allow that gives you anything meaningfully

Interesting. So do you know of a decent alternative? Or do you think that
may-point-to analysis in something as general as LLVM IR is basically a
dead end?

Also, can you share a few examples of code constructs which produce
pointers used in correct programs, but which are hard to recognize
statically? It's probably my inexperience talking, but the only examples I
can think of involve interfacing with hardware.

I did look at the LLVM IR for calling a virtual function in C++, since you
mentioned that as an example earlier. From manual inspection, I thought I
could spot the value flow of the virtual function pointer from where the
function was defined, into the vtable constant for that class, and then
into the class instance's vtable pointer.

As for your statement on authors putting a lot of thought into
published algorithms - they do, but honestly, published algorithms
should generally be treated like a starting point. They are often
vastly simplified for publication, or otherwise in need of significant
*engineering* work.

Thanks for the warning. Yes, I'm feeling that pain in spades :slight_smile:

8

>> I tried to find some subset i felt was worthwhile and where it was
>> okay, but gave up after a while.
>
>
> I'm not quite sure which things you're referring to in that statement.
> Would you mind clarifying?

You can try to ameliorate it by doing things like say "well, we
believe code patterns that look like this generate valid pointers,
but patterns that look like this can be ignored". It is very hard to
find a set of patterns you allow that gives you anything meaningfully

Interesting. So do you know of a decent alternative? Or do you think that
may-point-to analysis in something as general as LLVM IR is basically a dead
end?

Points-to analysis on LLVM-IR itself is fine (see the current CFL-AA,
or the old deleted andersen's implementations), and giving may-alias
and no-alias results also works. Giving must-alias answers, however,
is difficult.

In particular, i would not simply ignore some types of constructs and
expect to produce valid answers.

Also, can you share a few examples of code constructs which produce pointers
used in correct programs, but which are hard to recognize statically?

There are plenty of things that are illegal in C but legal in LLVM IR.

For example, the following is legal LLVM IR (sorry for c style, it's early)

bar(int64 a) {
int64 * foo = inttoptr(a);
baz = load *foo;
}

This is not illegal, and will produce a valid result.

Same with stuff like:
bar(int64 *a) {
int64 foo = ptrtoint(a);
baz = foo + 5;
int64 *b = inttoptr(baz);
c = load *b;
}

Again, not illegal, and produces a valid result.
You can pretty much do what you want.

Things like "c pointer aliasing rules" exist only as metadata.
So in general, you can't expect "invalid pointers" to buy you very much.

I did look at the LLVM IR for calling a virtual function in C++, since you
mentioned that as an example earlier. From manual inspection, I thought I
could spot the value flow of the virtual function pointer from where the
function was defined, into the vtable constant for that class, and then into
the class instance's vtable pointer.

This depends on the frontend generating the llvm IR :slight_smile:

9

Points-to analysis on LLVM-IR itself is fine (see the current CFL-AA,
or the old deleted andersen's implementations), and giving may-alias
and no-alias results also works. Giving must-alias answers, however,
is difficult.

In particular, i would not simply ignore some types of constructs and
expect to produce valid answers.

Makes sense. Thanks for the advice.

There are plenty of things that are illegal in C but legal in LLVM IR.

For example, the following is legal LLVM IR (sorry for c style, it's early)

bar(int64 a) {
int64 * foo = inttoptr(a);
baz = load *foo;
}

This is not illegal, and will produce a valid result.

Same with stuff like:
bar(int64 *a) {
int64 foo = ptrtoint(a);
baz = foo + 5;
int64 *b = inttoptr(baz);
c = load *b;
}

Again, not illegal, and produces a valid result.
You can pretty much do what you want.

Things like "c pointer aliasing rules" exist only as metadata.
So in general, you can't expect "invalid pointers" to buy you very much.

I see, thanks for clarifying. The AA algorithm I've been working with
assumes that the type system is going to lie, since C allows type punning.
I'm pretty sure I can port that distrust to the LLVM IR version of the
algorithm. It sounds like that would cover the examples you gave above, if
I'm also appropriately pessimistic about the behavior of unknown /
unanalyzed callers and callees.

Maybe what I'll try is to add a flag to each vertex in the may-point-to
graph, indicating whether or not the vertex's memory might hold additional,
poorly understood pointers. Then I can let an appropriate amount of hell
break loose in the analysis, if a piece of memory with that flag is used in
various ways.

That way, if over time I can make the algorithm better at detecting and
making sense of code which generates new pointer values, I can just
gradually reduce the cases where I need to set that flag.

> I did look at the LLVM IR for calling a virtual function in C++, since
you
> mentioned that as an example earlier. From manual inspection, I thought
I
> could spot the value flow of the virtual function pointer from where the
> function was defined, into the vtable constant for that class, and then
into
> the class instance's vtable pointer.
This depends on the frontend generating the llvm IR :slight_smile:

Touche.

10

Points-to analysis on LLVM-IR itself is fine (see the current CFL-AA,
or the old deleted andersen's implementations), and giving may-alias
and no-alias results also works. Giving must-alias answers, however,
is difficult.

In particular, i would not simply ignore some types of constructs and
expect to produce valid answers.

Makes sense. Thanks for the advice.

There are plenty of things that are illegal in C but legal in LLVM IR.

For example, the following is legal LLVM IR (sorry for c style, it's
early)

bar(int64 a) {
int64 * foo = inttoptr(a);
baz = load *foo;
}

This is not illegal, and will produce a valid result.

Same with stuff like:
bar(int64 *a) {
int64 foo = ptrtoint(a);
baz = foo + 5;
int64 *b = inttoptr(baz);
c = load *b;
}

Again, not illegal, and produces a valid result.
You can pretty much do what you want.

Things like "c pointer aliasing rules" exist only as metadata.
So in general, you can't expect "invalid pointers" to buy you very much.

I see, thanks for clarifying. The AA algorithm I've been working with
assumes that the type system is going to lie, since C allows type punning.

Which paper are you using?

I'm pretty sure I can port that distrust to the LLVM IR version of the
algorithm. It sounds like that would cover the examples you gave above, if
I'm also appropriately pessimistic about the behavior of unknown /
unanalyzed callers and callees.

Yup.

Maybe what I'll try is to add a flag to each vertex in the may-point-to
graph, indicating whether or not the vertex's memory might hold additional,
poorly understood pointers. Then I can let an appropriate amount of hell
break loose in the analysis, if a piece of memory with that flag is used in
various ways.

This is essentially what we do in gcc.
It is based on http://www.cs.ucsb.edu/~benh/research/papers/hardekopf07ant.pdf
as a solver, and some earlier papers that deal with field-sensitivity,
to build a field sensitive set of constraints for the program.

When we see bad things happen, we propagate various flags to say what
bad thing happened.
We used to explicitly track what the "set of variables that has become
unknown" are, but it grows too large to be sane for large programs.

Also note that to speed propagation, we prioritize propagation of that flag.

IE we propagate the various "unknown/points-to-anything/etc" flags as
fast as possible, to the exclusion of discovering other points-to
sets.

This is because once something points-to anything, it doesn't matter
what else it points to :slight_smile:

11

Which paper are you using?

I'm mostly going from Robert Wilson's 1997 phd thesis, although I'm pretty
sure I've seen a lot of the same ideas elsewhere as well.

IE we propagate the various "unknown/points-to-anything/etc" flags as

fast as possible, to the exclusion of discovering other points-to

sets.

This is because once something points-to anything, it doesn't matter
what else it points to :slight_smile:

Nice to know that the idea has been vetted in at least one AA
implementation. Thanks for the info.

12

Yes, using summary/transfer functions has been tried a lot.
Note: the numbers in most of these phd thesis do *not* get born out in practice.

See, e.g, http://www.cse.unsw.edu.au/~ysui/papers/spe14.pdf

vs

http://impact.crhc.illinois.edu/shared/report/phd-thesis-erik-nystrom.pdf

vs
the wilson thesis.

In particular, i expect the wilson algorithm is going to fall over
very badly on anything of even medium size.

Nowadays, the thing of the day seems to be using cfl reachability
based formulations and doing context-sensitivity on demand.

13

> I'm mostly going from Robert Wilson's 1997 phd thesis, although I'm
pretty
> sure I've seen a lot of the same ideas elsewhere as well.

Yes, using summary/transfer functions has been tried a lot.
Note: the numbers in most of these phd thesis do *not* get born out in
practice.

See, e.g, http://www.cse.unsw.edu.au/~ysui/papers/spe14.pdf

vs

http://impact.crhc.illinois.edu/shared/report/phd-thesis-erik-nystrom.pdf

vs
the wilson thesis.

Cool, I'll give those papers a read, thanks.

In particular, i expect the wilson algorithm is going to fall over
very badly on anything of even medium size.

Interesting. Do you mean "fall over" in terms of running time, or
precision, or something else?

Nowadays, the thing of the day seems to be using cfl reachability
based formulations and doing context-sensitivity on demand.

Out of curiosity, what's the appeal (aside from academic novelty) of the
CFL approaches?

From a personal perspective, I'm particularly interested in the maximum

analytic precision each AA approach can take, almost without regard to how
much time or memory the computation takes to run. So one thing I found
appealing about Wilson's thesis was his "location set" approach for
providing field-sensitivity.

I also liked Alain Deutsch's 1994 paper "Interprocedural may-alias analysis
for pointers: Beyond k-limiting" for the same reason. But I didn't take a
crack at implementing *that* because based on the paper's complexity, I
thought I'd go clinically insane trying to turn it into code :slight_smile:

14

> I'm mostly going from Robert Wilson's 1997 phd thesis, although I'm
> pretty
> sure I've seen a lot of the same ideas elsewhere as well.

Yes, using summary/transfer functions has been tried a lot.
Note: the numbers in most of these phd thesis do *not* get born out in
practice.

See, e.g, http://www.cse.unsw.edu.au/~ysui/papers/spe14.pdf

vs

http://impact.crhc.illinois.edu/shared/report/phd-thesis-erik-nystrom.pdf

vs
the wilson thesis.

Cool, I'll give those papers a read, thanks.

In particular, i expect the wilson algorithm is going to fall over
very badly on anything of even medium size.

Interesting. Do you mean "fall over" in terms of running time, or
precision, or something else?

Running time. Wilson's approach took 16 seconds for 4500 lines of code.
Let's assume his implementation actually did things right. Most
research impls do things like "ignore effects of external function
calls", which significantly impacts runtime in practice.

Let's further assume that scaling of computer speed from 1995 to now
eats your entire exponential factor, making the algorithm in practice
linear (This is not even close to true).

His algorithm, on a million lines of code, would take an hour to run.
Which would be pretty unacceptable.

In practice, i think you'll find it probably never finishes :slight_smile:

Nowadays, the thing of the day seems to be using cfl reachability
based formulations and doing context-sensitivity on demand.

Out of curiosity, what's the appeal (aside from academic novelty) of the CFL
approaches?

They are demand driven and easy to add context sensitivity to.
At the same time, on an all-pairs basis, they are competitive with
constraint based andersen's solvers.

You can't really do better than this, because it means you pay pretty
close to the minimal cost for the stuff you query.

From a personal perspective, I'm particularly interested in the maximum
analytic precision each AA approach can take, almost without regard to how
much time or memory the computation takes to run.

I'm wildly curious why.

So one thing I found
appealing about Wilson's thesis was his "location set" approach for
providing field-sensitivity.

I never saw this paper (it was too old for where i started), but GCC
uses something similar.

We create variables for each field of a given variable.
They are linked in a linked list with an offset and size (if known) to
the variables that contain them.

Constraints contain stride info, and intersection is then used to
compute what sub-variables a constraint touches during solving.
It is a variant of this:
http://homepages.mcs.vuw.ac.nz/~djp/files/paste04.ps

Note a few things:

Some programs have so many sub-variables you will run out of memory.
This is true in the location set approach as well.
GCC only created variables for possibly-used field ranges too.
I can point you at GCC bugs offline if you are interested

15

> From a personal perspective, I'm particularly interested in the maximum
> analytic precision each AA approach can take, almost without regard to
how
> much time or memory the computation takes to run.

I'm wildly curious why.

One reason is that I'm simply curious about the trade-off space between AA
precision and AA running-time. Since I don't make compilers for a living,
I have the luxury of staring at corners of the design space which would be
idiotic to actually include in LLVM :slight_smile:

Another reason is that in past work, I've sometimes worked on code where
I'd gladly accept a 10-day compilation time, if it bought me an extra 10%
in performance. So I sometimes wonder what's involved in making such
optimization passes available, even though people wouldn't want to use them
on a day-to-day basis.

Constraints contain stride info, and intersection is then used to

compute what sub-variables a constraint touches during solving.
It is a variant of this:
http://homepages.mcs.vuw.ac.nz/~djp/files/paste04.ps

Thanks, I'll try to give it a read.

Some programs have so many sub-variables you will run out of memory.
This is true in the location set approach as well.

I'm surprised you ran into that kind of trouble with memory. Was that back
in 32-bit days?

GCC only created variables for possibly-used field ranges too.
I can point you at GCC bugs offline if you are interested

Yeah, if you don't mind I'd be grateful for the links.

16

> From a personal perspective, I'm particularly interested in the maximum
> analytic precision each AA approach can take, almost without regard to
> how
> much time or memory the computation takes to run.

I'm wildly curious why.

One reason is that I'm simply curious about the trade-off space between AA
precision and AA running-time. Since I don't make compilers for a living, I
have the luxury of staring at corners of the design space which would be
idiotic to actually include in LLVM :slight_smile:

Fair enough.

Another reason is that in past work, I've sometimes worked on code where I'd
gladly accept a 10-day compilation time, if it bought me an extra 10% in
performance. So I sometimes wonder what's involved in making such
optimization passes available, even though people wouldn't want to use them
on a day-to-day basis.

FWIW:
I've explored this before. I built a large-scale distributed
completely precise context-sensitive alias-analysis and ran it on
about 100k machines. It was brute-force and took no shortcuts, etc.
It was run on some apps that are very large, and took many terabytes
of memory and disk :slight_smile:

My result:
Certainly there are some apps it may buy you 10%.
But most, it won't, and where it does, there are often cheaper
techniques (like runtime tests, etc) that will get you 9%.

Constraints contain stride info, and intersection is then used to
compute what sub-variables a constraint touches during solving.
It is a variant of this:
http://homepages.mcs.vuw.ac.nz/~djp/files/paste04.ps

Thanks, I'll try to give it a read.

Some programs have so many sub-variables you will run out of memory.
This is true in the location set approach as well.

I'm surprised you ran into that kind of trouble with memory. Was that back
in 32-bit days?

Even in a 64 bit world, you will run out of memory quickly. I don't
think you realize how many edges/variables/etc you are talking about
for large programs.
People had cases with structures with thousands of fields, nested
these, and instantiate them into tens of thousands of variables.
It was billions of variables :slight_smile:
Having only-used ranges got it down to tens of millions.
Now GCC just punts on some sane size.

GCC only created variables for possibly-used field ranges too.
I can point you at GCC bugs offline if you are interested

Yeah, if you don't mind I'd be grateful for the links.

I'll send them offline.

17

> Another reason is that in past work, I've sometimes worked on code where
I'd
> gladly accept a 10-day compilation time, if it bought me an extra 10% in
> performance. So I sometimes wonder what's involved in making such
> optimization passes available, even though people wouldn't want to use
them
> on a day-to-day basis.

FWIW:
I've explored this before. I built a large-scale distributed
completely precise context-sensitive alias-analysis and ran it on
about 100k machines. It was brute-force and took no shortcuts, etc.
It was run on some apps that are very large, and took many terabytes
of memory and disk :slight_smile:

My result:
Certainly there are some apps it may buy you 10%.
But most, it won't, and where it does, there are often cheaper
techniques (like runtime tests, etc) that will get you 9%.

Wow. I'll consider my curiosity to have been vicariously satisfied by your
experiment. Thanks for freeing up six months of my life :slight_smile:

Even in a 64 bit world, you will run out of memory quickly. I don't
think you realize how many edges/variables/etc you are talking about
for large programs.
People had cases with structures with thousands of fields, nested
these, and instantiate them into tens of thousands of variables.
It was billions of variables :slight_smile:
Having only-used ranges got it down to tens of millions.
Now GCC just punts on some sane size.

Thanks, I'm going to guess you're right that I'm failing to appreciate the
numbers of things involved. I appreciate the warning.