Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Some method to represent alias information in LLVM would be useful #1745

Closed
llvmbot opened this issue May 1, 2007 · 12 comments
Closed

Some method to represent alias information in LLVM would be useful #1745

llvmbot opened this issue May 1, 2007 · 12 comments
Labels
bugzilla Issues migrated from bugzilla enhancement Improving things as opposed to bug fixing, e.g. new or missing feature llvm:core

Comments

@llvmbot
Copy link
Collaborator

llvmbot commented May 1, 2007

Bugzilla Link 1373
Resolution FIXED
Resolved on Oct 15, 2008 10:55
Version 1.0
OS All
Depends On llvm/llvm-bugzilla-archive#1582
Reporter LLVM Bugzilla Contributor

Extended Description

From this llvm-dev thread (http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-March/008323.html),
Chris Lattner writes:

I think the goal should be to capture the most important information. The
c99 definition of restrict has some nasty and complex implementation
issues. It may not be reasonable or interesting to capture every corner
case.

A more interesting question is how to represent TBAA information in LLVM
:).

Here is a sketch of a concrete proposal to get us started:

  1. Add a new argument attribute "noalias", which can be applied to pointer
    formals and pointer function results.
  2. Add a new intrinsic "i8* @​llvm.noalias(i8*)

The semantics of 'noalias' are that they "define a new object". Any
pointer derived from it ("it" being the result of a no-alias call result,
a formal parameter, or the result of llvm.noalias) is considered to not
alias:

A. any other objects (e.g. global vars, allocas, functions, etc)
B. any other "noalias" objects
C. any other formal argument parameters or call results.

For these purposes, "pointers derived" means getelementptr and bitcast.

Can C99 restrict be mapped onto these semantics? Is "C" really safe?

With these semantics, it is clear that 'calloc' could be declared to have
a result pointer that is noalias for example, but I'm not sure if it would
be safe to map restrict onto it.

@llvmbot
Copy link
Collaborator Author

llvmbot commented May 31, 2007

This patch adds "NoAlias" to ParamAttr namespace's list of Attributes
This patch adds "NoAlias" to ParamAttr namespace's list of Attributes. No
use of it is yet made.

@llvmbot
Copy link
Collaborator Author

llvmbot commented May 31, 2007

@llvmbot
Copy link
Collaborator Author

llvmbot commented May 31, 2007

@lattner
Copy link
Collaborator

lattner commented May 31, 2007

all 3 patches look good, plz apply. In the future, please submit proposed patches to llvm-commits.
Thanks!

-Chris

@llvmbot
Copy link
Collaborator Author

llvmbot commented Jun 19, 2007

Information from Chris, this clearly explains why we need the intrinsic
llvm.noalis and its behavior:

Consider if you have something like this:

void foo(restrict *P1, restrict *P2) {
alias P1, P2 ?
}

In this case, obviously P1 and P2 don't alias. Now consider this:

void bar(void *P1, void *P2) {
foo(P1, P2);
}

Imagine if we inlined the function, we'd get this:

void bar(void *P1, void *P2) {
alias P1, P2 ?
}

Now we have to assume the pointer alias, we lost information. I'm
suggesting the intrinsics be defined to just return their pointer, so
the inline can create them. This would allow the inliner to produce:

void bar(void *P1, void *P2) {
P1tmp = llvm.noalias(P1)
P2tmp = llvm.noalias(P2)
alias P1tmp, P2tmp ?
}

which we can now decide don't alias.

The problem with this approach is that the intrinsics would block
optimizations, specifically stuff like SROA and mem2reg, which should
be updated to handle these intrinsics.

These intrinsics could also be used to translate code like this:

restrict int *G;

void bar() { *G; }

into ->

void bar() {
%tmp = load int** @​G
%tmp2 = call llvm.noalias int* tmp
}

Thanks, Chris :)

@lattner
Copy link
Collaborator

lattner commented Jun 19, 2007

happy to help :)

@llvmbot
Copy link
Collaborator Author

llvmbot commented Jul 31, 2007

BasicAA has been taught about noalias function arguments.

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070730/052392.html

@sunfishcode
Copy link
Member

It appears BasicAliasAnalysis.cpp does have an AddressMightEscape routine, which could be used to improve the analysis of queries involving a noalias pointer and a pointer with an unknown base. If the noalias pointer doesn't escape, then there is no alias. They key is to make sure that the logic for finding a base object always succeeds for expressions on which AddressMightEscape returns false.

@llvmbot
Copy link
Collaborator Author

llvmbot commented Jan 25, 2008

Acomplia
Acomplia

@tlattner
Copy link
Contributor

The content of attachment 1352 has been deleted by
Tanya Lattner tonic@nondot.org
without providing any reason.

The token used to delete this attachment was generated at 2008-01-25 11:29:20.

@lattner
Copy link
Collaborator

lattner commented Oct 15, 2008

We now support the noalias attribute, and have another PR to track the work for TBAA, closing as fixed.

@llvmbot
Copy link
Collaborator Author

llvmbot commented Nov 26, 2021

mentioned in issue llvm/llvm-bugzilla-archive#1582

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 3, 2021
@Endilll Endilll added enhancement Improving things as opposed to bug fixing, e.g. new or missing feature and removed new-feature labels Aug 15, 2023
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla enhancement Improving things as opposed to bug fixing, e.g. new or missing feature llvm:core
Projects
None yet
Development

No branches or pull requests

5 participants