Top-Down FunctionAttrs propagation for noalias, dereferenceable and nonnull inference

[hfinkel]

Summary

This patch introduces a new module-level pass which does a top-down traversal of the call graph, inferring when possible for local functions, parameter attributes: noalias, dereferenceable and nonnull. It does this based on an examination of all call sites.

Inference on nonnull is straightforward (all callers must pass an argument we know is nonnull). noalias requires two things at all call sites: that the parameter not alias with any other parameter, and that it not have been captured prior to the call site. dereferenceability requires that we know the pointer is derefenceable at all call sites, obviously, but then we also need to get the size. We use the type size (which is fine b/c we've already verified that a load of that type is safe), but we also use getObjectSize to see if we can do better. We don't always know that the size that getObjectSize returns is valid (because the malloc could have failed, for example), but it will be valid if there is also an access, and isSafeToLoadUnconditionally checks for that.

There is a quirk about scheduling this in the current pass manager: Inference of noalias requires a capturing analysis which greatly benefits from running after the existing FunctionAttrs pass which will infer nocapture parameters. However, the existing FunctionAttrs pass is a CGSCC pass that runs in the main CGSCC pass manager after the inliner. But this being a top-down traversal of the call graph (and thus a module pass), and one that should run early, needs to run before the inliner's CGSCC pass manager. As a result, I think the best option is to insert an extra run of the regular FunctionAttrs pass just prior to this one, and these just prior to the main CGSCC pass manager. Since both preserve the call graph, it should not cause it to be recomputed.

I see no compile-time impact (either from the extra run on functionattrs or from this new pass). Compiling sqlite, for example, both passes take less than 0.1% of the total time.

[hfinkel]

Use isDereferenceablePointer (which checks things like argument's dereferenceable attribute) in addition to using isSafeToLoadUnconditionally (which is mostly useful for its local instruction scan). Also fixed up one of the test cases.

[hfinkel]

Updated based on Nick's comments; we need to ensure a stable answer for SCCs (which the df_iterator won't do).

The regular SCC iterator returns the SCCs bottom-up (it uses Tarjan's Algorithm, and knows it has found the root of an SCC as it passes it on the way up -- it is not clear there is a better way). Because we can't collect SCCs in a purely top-down fashion anyway, I've just changed it to store those returned by the bottom-up SCC iterator in a vector and visit this stored vector in reverse order. This pass does not modify the call graph, so this method should be stable.

In the future, we can get a better answer by speculating the attributes within each SCC, and then removing them afterward if call sites are found where the attributes can't be proved. I'll implement this as follow-up work.

[hfinkel]

Also added support for inferring the align attribute (which, post r213670, is now a useful thing to do).

[hfinkel]

Ping.

[reames]

Overall, looks pretty reasonable. A few minor code comments inline.

I might suggest separating the addition of the patch and adding to the pass manager. In particular, adding the second run of the attribute analysis should probably be discussed more broadly.

lib/Transforms/IPO/FunctionAttrsTD.cpp

83

Stylistically, I'd prefer this separated into two checks. Your combining correctness and profitability criteria. Also, rather than "return MadeChange", just "return false" for the early exits. It makes the flow clearer.

92

Please rename MaxSize. It appears to actually be MaxKnownDeferenceable and the current name is highly confusing.

113

A comment here that reminds the reader the default state is fully speculative/optimistic would be helpful.

115

Do you need to iterate the uses, or can you iterate the users directly?

126

Shouldn't this be F?

132

A general point: this function is *way* too complex. Split it into reasonable helper functions. One arrangement would be:
struct ArgState
updateArgAtCallSite(...) {}
updateForCallSite(...) {}
identifyCallSites(...) {}
addIndicatedAtrributes(...) {}

158

Is this a correctness bug? Or a missed optimization? I can't tell from your FIXME.

171

Er, this doesn't look right. We've verified that loading from the pointer *up to* a certain number of bytes is safe. We have not said anything beyond that.

176

It looks like IsDerefernceable could become a function of MaxSize on the state object?

185

I don't understand why you need this check. Is it safe to record an align attribute less than the ABI alignment? If not, that seems slightly odd.

237

I'm not clear why this check is needed. Aren't you only iterating 'number of argument' times anyways?

250

The first is just an early exit, but what are the second two checks for? Are they functionally required?

[hfinkel]

• Original Message -----

From: "Philip Reames" <[e-mail]>
To: [e-mail], [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Wednesday, September 10, 2014 12:59:48 PM
Subject: Re: [PATCH] Top-Down FunctionAttrs propagation for noalias, dereferenceable and nonnull inference

Overall, looks pretty reasonable. A few minor code comments inline.

I might suggest separating the addition of the patch and adding to
the pass manager. In particular, adding the second run of the
attribute analysis should probably be discussed more broadly.

Thanks for the review!

I also need to revisit the way that the noalias inference is done because it is not quite right in this patch. Just checking alias(AI, BI) == NoAlias is not sufficient: a[i] and a[i+1] don't alias, but obviously pointers based on them could. I can really only do this when we have distinct sets of underlying objects (which makes several other things much simpler -- including the capture checking and the ramifications on the optimization pipeline).

-Hal

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:82
@@ +81,3 @@
+ bool MadeChange = false;
+ if (F.isDeclaration() || !F.hasLocalLinkage() || F.arg_empty() ||

+ F.use_empty())

Stylistically, I'd prefer this separated into two checks. Your
combining correctness and profitability criteria. Also, rather than
"return MadeChange", just "return false" for the early exits. It
makes the flow clearer.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:91
@@ +90,3 @@
+ bool IsAlign;
+ uint64_t MaxSize, MaxAlign;

+

Please rename MaxSize. It appears to actually be
MaxKnownDeferenceable and the current name is highly confusing.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:112
@@ +111,3 @@
+ SmallVector<AttrState, 16> ArgumentState;
+ ArgumentState.resize(F.arg_size());

+

A comment here that reminds the reader the default state is fully
speculative/optimistic would be helpful.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:114
@@ +113,3 @@
+
+ for (Use &U : F.uses()) {

+ User *UR = U.getUser();

Do you need to iterate the uses, or can you iterate the users
directly?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:125
@@ +124,3 @@
+ CallSite CS(cast<Instruction>(UR));
+ if (!CS.isCallee(&U))

+ return MadeChange;

Shouldn't this be F?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:131
@@ +130,3 @@
+ Function::arg_iterator Arg = F.arg_begin();
+ for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i,
++AI, ++Arg) {

+ // If we've already excluded this argument, ignore it.

A general point: this function is *way* too complex. Split it into
reasonable helper functions. One arrangement would be:
struct ArgState
updateArgAtCallSite(...) {}
updateForCallSite(...) {}
identifyCallSites(...) {}
addIndicatedAtrributes(...) {}

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:157
@@ +156,3 @@
+ ArgumentState[i].IsDereferenceable = false;
+ FIXME: isSafeToLoadUnconditionally does not understand
memset.
+ FIXME: We can use getObjectSize for most things, but

for mallocs

Is this a correctness bug? Or a missed optimization? I can't tell
from your FIXME.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:170
@@ +169,3 @@
+ // trap, so we can use at least that size.
+ Size = std::max(Size, TypeSize);

+ }

Er, this doesn't look right. We've verified that loading from the
pointer *up to* a certain number of bytes is safe. We have not said
anything beyond that.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:175
@@ +174,3 @@
+ if (!ArgumentState[i].MaxSize)
+ ArgumentState[i].IsDereferenceable = false;

+ }

It looks like IsDerefernceable could become a function of MaxSize on
the state object?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:184
@@ +183,3 @@
+ unsigned Align = getKnownAlignment(*AI, DL);
+ if (Align > DL->getABITypeAlignment(ETy))

+ ArgumentState[i].MaxAlign =

I don't understand why you need this check. Is it safe to record an
align attribute less than the ABI alignment? If not, that seems
slightly odd.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:236
@@ +235,3 @@
+
+ bool HaveCand = false;

+ for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i)

I'm not clear why this check is needed. Aren't you only iterating
'number of argument' times anyways?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:249
@@ +248,3 @@
+ for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i, ++AI)
{
+ if (!ArgumentState[i].any() || AI->hasInAllocaAttr() ||
AI->hasByValAttr())

+ continue;

The first is just an early exit, but what are the second two checks
for? Are they functionally required?

http://reviews.llvm.org/D4609

[hfinkel]

• Original Message -----

From: "Hal Finkel" <[e-mail]>
To: [e-mail]
Cc: [e-mail]
Sent: Wednesday, September 10, 2014 1:13:01 PM
Subject: Re: [PATCH] Top-Down FunctionAttrs propagation for noalias, dereferenceable and nonnull inference

• Original Message -----

From: "Philip Reames" <[e-mail]>
To: [e-mail], [e-mail], [e-mail],
[e-mail]
Cc: [e-mail]
Sent: Wednesday, September 10, 2014 12:59:48 PM
Subject: Re: [PATCH] Top-Down FunctionAttrs propagation for
noalias, dereferenceable and nonnull inference

Overall, looks pretty reasonable. A few minor code comments
inline.

I might suggest separating the addition of the patch and adding to
the pass manager. In particular, adding the second run of the
attribute analysis should probably be discussed more broadly.

Thanks for the review!

I also need to revisit the way that the noalias inference is done
because it is not quite right in this patch. Just checking alias(AI,
BI) == NoAlias is not sufficient: a[i] and a[i+1] don't alias, but
obviously pointers based on them could. I can really only do this
when we have distinct sets of underlying objects (which makes
several other things much simpler -- including the capture checking
and the ramifications on the optimization pipeline).

Actually, I take that back. It does not make the capture checking simpler.

-Hal

-Hal

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:82
@@ +81,3 @@
+ bool MadeChange = false;
+ if (F.isDeclaration() || !F.hasLocalLinkage() || F.arg_empty()

+ F.use_empty())

Stylistically, I'd prefer this separated into two checks. Your
combining correctness and profitability criteria. Also, rather
than
"return MadeChange", just "return false" for the early exits. It
makes the flow clearer.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:91
@@ +90,3 @@
+ bool IsAlign;
+ uint64_t MaxSize, MaxAlign;

+

Please rename MaxSize. It appears to actually be
MaxKnownDeferenceable and the current name is highly confusing.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:112
@@ +111,3 @@
+ SmallVector<AttrState, 16> ArgumentState;
+ ArgumentState.resize(F.arg_size());

+

A comment here that reminds the reader the default state is fully
speculative/optimistic would be helpful.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:114
@@ +113,3 @@
+
+ for (Use &U : F.uses()) {

+ User *UR = U.getUser();

Do you need to iterate the uses, or can you iterate the users
directly?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:125
@@ +124,3 @@
+ CallSite CS(cast<Instruction>(UR));
+ if (!CS.isCallee(&U))

+ return MadeChange;

Shouldn't this be F?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:131
@@ +130,3 @@
+ Function::arg_iterator Arg = F.arg_begin();
+ for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i,
++AI, ++Arg) {

+ // If we've already excluded this argument, ignore it.

A general point: this function is *way* too complex. Split it into
reasonable helper functions. One arrangement would be:
struct ArgState
updateArgAtCallSite(...) {}
updateForCallSite(...) {}
identifyCallSites(...) {}
addIndicatedAtrributes(...) {}

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:157
@@ +156,3 @@
+ ArgumentState[i].IsDereferenceable = false;
+ FIXME: isSafeToLoadUnconditionally does not
understand
memset.
+ FIXME: We can use getObjectSize for most things, but

for mallocs

Is this a correctness bug? Or a missed optimization? I can't tell
from your FIXME.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:170
@@ +169,3 @@
+ // trap, so we can use at least that size.
+ Size = std::max(Size, TypeSize);

+ }

Er, this doesn't look right. We've verified that loading from the
pointer *up to* a certain number of bytes is safe. We have not
said
anything beyond that.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:175
@@ +174,3 @@
+ if (!ArgumentState[i].MaxSize)
+ ArgumentState[i].IsDereferenceable = false;

+ }

It looks like IsDerefernceable could become a function of MaxSize
on
the state object?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:184
@@ +183,3 @@
+ unsigned Align = getKnownAlignment(*AI, DL);
+ if (Align > DL->getABITypeAlignment(ETy))

+ ArgumentState[i].MaxAlign =

I don't understand why you need this check. Is it safe to record
an
align attribute less than the ABI alignment? If not, that seems
slightly odd.

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:236
@@ +235,3 @@
+
+ bool HaveCand = false;

+ for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i)

I'm not clear why this check is needed. Aren't you only iterating
'number of argument' times anyways?

Comment at: lib/Transforms/IPO/FunctionAttrsTD.cpp:249
@@ +248,3 @@
+ for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i,
++AI)
{
+ if (!ArgumentState[i].any() || AI->hasInAllocaAttr() ||
AI->hasByValAttr())

+ continue;

The first is just an early exit, but what are the second two checks
for? Are they functionally required?

http://reviews.llvm.org/D4609

Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[Prazek]

Did you push it to master?

[haicheng]

Hi Hal,

I am wondering what's your plan of this patch? I am particularly interested in the propagation of noalias attributes.

Thank you,

Haicheng

[hfinkel]

In D4609#801397, @haicheng wrote:

Hi Hal,

I am wondering what's your plan of this patch? I am particularly interested in the propagation of noalias attributes.

I've not thought about this in a while, but I'd certainly like to see this functionality. Aside from some refactoring, it needs two things:

1. The noalias inference needs to be updated to be correct. The easiest way to do this is, instead of actually doing an alias check on the arguments, to call GetUnderlyingObjects and check for disjoint sets of *identified* underlying objects (still checking for capturing, and possibly restricting to local identified objects unless we can do a global capture check). Any set that is disjoint from the others means that its associated argument can be marked as noalias.
2. I'd like to revisit how the iteration is done and how this fits with the rest of the pass manager. While it does naturally iterate top down, and the CGSCC pass manager normally iterates the other way, there should be a way to put this logic into the part of the pipeline that is iterating with the inliner. I was never satisfied with the idea that we'd only do this once at the beginning of the pipeline. Now that we have a new pass manager, we can think about how this might work in that framework as well. Also, the new pass manager should make it more natural to get a per-function dominator tree, etc. @chandlerc, thoughts on how this might best be done?

Thank you,

Haicheng

[haicheng]

In D4609#833428, @hfinkel wrote:

In D4609#801397, @haicheng wrote:

Hi Hal,

I am wondering what's your plan of this patch? I am particularly interested in the propagation of noalias attributes.

I've not thought about this in a while, but I'd certainly like to see this functionality. Aside from some refactoring, it needs two things:

1. The noalias inference needs to be updated to be correct. The easiest way to do this is, instead of actually doing an alias check on the arguments, to call GetUnderlyingObjects and check for disjoint sets of *identified* underlying objects (still checking for capturing, and possibly restricting to local identified objects unless we can do a global capture check). Any set that is disjoint from the others means that its associated argument can be marked as noalias.
2. I'd like to revisit how the iteration is done and how this fits with the rest of the pass manager. While it does naturally iterate top down, and the CGSCC pass manager normally iterates the other way, there should be a way to put this logic into the part of the pipeline that is iterating with the inliner. I was never satisfied with the idea that we'd only do this once at the beginning of the pipeline. Now that we have a new pass manager, we can think about how this might work in that framework as well. Also, the new pass manager should make it more natural to get a per-function dominator tree, etc. @chandlerc, thoughts on how this might best be done?

Thank you,

Haicheng

That is great. I rebased your code and replaced the alias check with cheking distinct sets of underlying objects. It is working for most benchmarks of llvm-test-suite and spec20xx.

[hfinkel]

In D4609#835270, @haicheng wrote:

In D4609#833428, @hfinkel wrote:

In D4609#801397, @haicheng wrote:

Hi Hal,

I am wondering what's your plan of this patch? I am particularly interested in the propagation of noalias attributes.

I've not thought about this in a while, but I'd certainly like to see this functionality. Aside from some refactoring, it needs two things:

1. The noalias inference needs to be updated to be correct. The easiest way to do this is, instead of actually doing an alias check on the arguments, to call GetUnderlyingObjects and check for disjoint sets of *identified* underlying objects (still checking for capturing, and possibly restricting to local identified objects unless we can do a global capture check). Any set that is disjoint from the others means that its associated argument can be marked as noalias.
2. I'd like to revisit how the iteration is done and how this fits with the rest of the pass manager. While it does naturally iterate top down, and the CGSCC pass manager normally iterates the other way, there should be a way to put this logic into the part of the pipeline that is iterating with the inliner. I was never satisfied with the idea that we'd only do this once at the beginning of the pipeline. Now that we have a new pass manager, we can think about how this might work in that framework as well. Also, the new pass manager should make it more natural to get a per-function dominator tree, etc. @chandlerc, thoughts on how this might best be done?

Thank you,

Haicheng

That is great. I rebased your code and replaced the alias check with cheking distinct sets of underlying objects. It is working for most benchmarks of llvm-test-suite and spec20xx.

It occurs to me that the need for this might be removed by another potential improvement (suggested to me by Chandler at EuroLLVM this year): We can make CGSCC analysis wrapper for our current analysis passes in order to allow these analyses to look back through function arguments into the function's callers. To make this work, we'd:

1. Make CGSCC analysis passes corresponding to our current analysis passes. For example, AA, ValueTracking, etc. (I realize that ValueTracking is not really an analysis pass right now, and while we might want to change that at some point, I don't think it matters for this description).
2. These pass accept analysis queries and produce results by looking at the calling functions and calling the function/local analysis on the values at each call site, and then intersecting the results. If there are too many call sites, or unknown call sites, then you need to give up.
3. Provide these CGSCC analysis handles to the corresponding local analyses so that, as they do a recursive analysis, when they hit arguments, then can call into the CGSCC analyses to continue the analysis into the callers.

If we did that, do you think we'd still need this transformation?

[haicheng]

It occurs to me that the need for this might be removed by another potential improvement (suggested to me by Chandler at EuroLLVM this year): We can make CGSCC analysis wrapper for our current analysis passes in order to allow these analyses to look back through function arguments into the function's callers. To make this work, we'd:

1. Make CGSCC analysis passes corresponding to our current analysis passes. For example, AA, ValueTracking, etc. (I realize that ValueTracking is not really an analysis pass right now, and while we might want to change that at some point, I don't think it matters for this description).
2. These pass accept analysis queries and produce results by looking at the calling functions and calling the function/local analysis on the values at each call site, and then intersecting the results. If there are too many call sites, or unknown call sites, then you need to give up.
3. Provide these CGSCC analysis handles to the corresponding local analyses so that, as they do a recursive analysis, when they hit arguments, then can call into the CGSCC analyses to continue the analysis into the callers.

If we did that, do you think we'd still need this transformation?

What you described was close to what I was looking for before I found this patch. I don't know how difficult to implement it, but I can try to hook CGSCC with BasicAA first.

Thank you.

Haicheng

[etherzhhb]

lib/Transforms/IPO/FunctionAttrsTD.cpp

320

This is unused?

[haicheng]

It occurs to me that the need for this might be removed by another potential improvement (suggested to me by Chandler at EuroLLVM this year): We can make CGSCC analysis wrapper for our current analysis passes in order to allow these analyses to look back through function arguments into the function's callers. To make this work, we'd:

1. Make CGSCC analysis passes corresponding to our current analysis passes. For example, AA, ValueTracking, etc. (I realize that ValueTracking is not really an analysis pass right now, and while we might want to change that at some point, I don't think it matters for this description).
2. These pass accept analysis queries and produce results by looking at the calling functions and calling the function/local analysis on the values at each call site, and then intersecting the results. If there are too many call sites, or unknown call sites, then you need to give up.
3. Provide these CGSCC analysis handles to the corresponding local analyses so that, as they do a recursive analysis, when they hit arguments, then can call into the CGSCC analyses to continue the analysis into the callers.

If we did that, do you think we'd still need this transformation?

Hi Hal,

I spent some time thinking about the alternative method you mentioned here. I think the alternative can cover many cases that this patch tries to solve, but this patch still could bring some additional advantages.

1. The new pass provides a place dedicated to do the Top-Down propagation. It is simpler and easy to maintain. We can add more attributes to propagate in the future.
2. Not only the direct users of AA or value tracking can get benefits from this patch, any pass runs after this new pass can easily get access to the propagated attributes.
3. The alternative one has a long way to go, but your patch is almost there. I spend some time fixing the bugs and it is working for most of cases now.

I am thinking maybe the two methods can co-exist. This patch can cut the number of recursive calls and together they can cover more cases. Do you think it is worthwhile if I continue working on this patch?

include/llvm-c/Transforms/IPO.h

 void LLVMAddConstantMergePass(LLVMPassManagerRef PM);
 
 /** See llvm::createDeadArgEliminationPass function. */
 void LLVMAddDeadArgEliminationPass(LLVMPassManagerRef PM);
 
 /** See llvm::createFunctionAttrsPass function. */
 void LLVMAddFunctionAttrsPass(LLVMPassManagerRef PM);
 
+/** See llvm::createFunctionAttrsTDPass function. */
+void LLVMAddFunctionAttrsTDPass(LLVMPassManagerRef PM);
+
 /** See llvm::createFunctionInliningPass function. */
 void LLVMAddFunctionInliningPass(LLVMPassManagerRef PM);
 
 /** See llvm::createAlwaysInlinerPass function. */
 void LLVMAddAlwaysInlinerPass(LLVMPassManagerRef PM);
 
 /** See llvm::createGlobalDCEPass function. */
 void LLVMAddGlobalDCEPass(LLVMPassManagerRef PM);

include/llvm/InitializePasses.h

 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeThreadSanitizerPass(PassRegistry&);
 void initializeDataFlowSanitizerPass(PassRegistry&);
 void initializeScalarizerPass(PassRegistry&);
 void initializeEarlyCSEPass(PassRegistry&);
 void initializeExpandISelPseudosPass(PassRegistry&);
 void initializeFindUsedTypesPass(PassRegistry&);
 void initializeFunctionAttrsPass(PassRegistry&);
+void initializeFunctionAttrsTDPass(PassRegistry&);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);
 void initializeGVNPass(PassRegistry&);
 void initializeGlobalDCEPass(PassRegistry&);
 void initializeGlobalOptPass(PassRegistry&);
 void initializeGlobalsModRefPass(PassRegistry&);
 void initializeIPCPPass(PassRegistry&);
 void initializeIPSCCPPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void)llvm::createMergedLoadStoreMotionPass();
       (void) llvm::createGVNPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();
       (void) llvm::createInstructionNamerPass();
       (void) llvm::createMetaRenamerPass();
       (void) llvm::createFunctionAttrsPass();
+      (void) llvm::createFunctionAttrsTDPass();
       (void) llvm::createMergeFunctionsPass();
       (void) llvm::createPrintModulePass(*(llvm::raw_ostream*)nullptr);
       (void) llvm::createPrintFunctionPass(*(llvm::raw_ostream*)nullptr);
       (void) llvm::createPrintBasicBlockPass(*(llvm::raw_ostream*)nullptr);
       (void) llvm::createModuleDebugInfoPrinterPass();
       (void) llvm::createPartialInliningPass();
       (void) llvm::createLintPass();
       (void) llvm::createSinkingPass();

include/llvm/Transforms/IPO.h

 /// createFunctionAttrsPass - This pass discovers functions that do not access
 /// memory, or only read memory, and gives them the readnone/readonly attribute.
 /// It also discovers function arguments that are not captured by the function
 /// and marks them with the nocapture attribute.
 ///
 Pass *createFunctionAttrsPass();
 
 //===----------------------------------------------------------------------===//
+/// createFunctionAttrsTDPass - This pass discovers function arguments that
+/// are always nonnull, dereferenceable and/or noalias.
+///
+ModulePass *createFunctionAttrsTDPass();
+
+//===----------------------------------------------------------------------===//
 /// createMergeFunctionsPass - This pass discovers identical functions and
 /// collapses them.
 ///
 ModulePass *createMergeFunctionsPass();
 
 //===----------------------------------------------------------------------===//
 /// createPartialInliningPass - This pass inlines parts of functions.
 ///

lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::initializeLTOPasses() {
   initializePruneEHPass(R);
   initializeGlobalDCEPass(R);
   initializeArgPromotionPass(R);
   initializeJumpThreadingPass(R);
   initializeSROAPass(R);
   initializeSROA_DTPass(R);
   initializeSROA_SSAUpPass(R);
   initializeFunctionAttrsPass(R);
+  initializeFunctionAttrsTDPass(R);
   initializeGlobalsModRefPass(R);
   initializeLICMPass(R);
   initializeMergedLoadStoreMotionPass(R);
   initializeGVNPass(R);
   initializeMemCpyOptPass(R);
   initializeDCEPass(R);
   initializeCFGSimplifyPassPass(R);
 }

lib/Transforms/IPO/CMakeLists.txt

 add_llvm_library(LLVMipo
   ArgumentPromotion.cpp
   BarrierNoopPass.cpp
   ConstantMerge.cpp
   DeadArgumentElimination.cpp
   ExtractGV.cpp
   FunctionAttrs.cpp
+  FunctionAttrsTD.cpp
   GlobalDCE.cpp
   GlobalOpt.cpp
   IPConstantPropagation.cpp
   IPO.cpp
   InlineAlways.cpp
   InlineSimple.cpp
   Inliner.cpp
   Internalize.cpp

lib/Transforms/IPO/FunctionAttrsTD.cpp

+//===----- FunctionAttrsTD.cpp - Deduce Function Parameter Attributes -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass traverses the call graph top-down in order to deduce
+// function-parameter attributes for local functions based on properties of
+// their callers (nonnull, dereferenceable, noalias).
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetLibraryInfo.h"
+#include "llvm/Transforms/Utils/Local.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "functionattrs-td"
+
+STATISTIC(NumNonNull, "Number of arguments marked nonnull");
+STATISTIC(NumNoAlias, "Number of arguments marked noalias");
+STATISTIC(NumDereferenceable, "Number of arguments marked dereferenceable");
+
+namespace {
+  class FunctionAttrsTD : public ModulePass {
+    const DataLayout *DL;
+    AliasAnalysis *AA;
+    TargetLibraryInfo *TLI;
+
+    bool addFuncAttrs(Function &F, DenseMap<Function *, DominatorTree *> &DTs);
+
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    explicit FunctionAttrsTD();
+    bool runOnModule(Module &M) override;
+
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.setPreservesCFG();
+      AU.addRequired<CallGraphWrapperPass>();
+      AU.addPreserved<CallGraphWrapperPass>();
+      AU.addRequired<TargetLibraryInfo>();
+      AU.addPreserved<TargetLibraryInfo>();
+      AU.addRequired<AliasAnalysis>();
+      AU.addPreserved<AliasAnalysis>();
+    }
+  };
+} // end anonymous namespace
+
+char FunctionAttrsTD::ID = 0;
+INITIALIZE_PASS(FunctionAttrsTD, "functionattrs-td",
+                "Top-down function parameter attributes", false, false)
+
+FunctionAttrsTD::FunctionAttrsTD() : ModulePass(ID) {
+  initializeFunctionAttrsTDPass(*PassRegistry::getPassRegistry());
+}
+
+bool FunctionAttrsTD::addFuncAttrs(Function &F,
+       DenseMap<Function *, DominatorTree *> &DTs) {
+  bool MadeChange = false;
+  if (F.isDeclaration() || !F.hasLocalLinkage() || F.arg_empty() ||
+      F.use_empty())
+    return MadeChange;
+
+  struct AttrState {
+    bool IsNonNull;
+    bool IsNoAlias;
+    bool IsDereferenceable;
+    uint64_t MaxSize;
+
+    AttrState() : IsNonNull(true), IsNoAlias(true),
+                  IsDereferenceable(true), MaxSize(UINT64_MAX) {}
+
+    bool any() const {
+      return IsNonNull || IsNoAlias || IsDereferenceable;
+    }
+
+    void setNone() {
+      IsNonNull = false;
+      IsNoAlias = false;
+      IsDereferenceable = false;
+    }
+  };
+
+  // For each argument, keep track of whether it is donated or not.
+  // The bool is set to true when found to be non-donated.
+  SmallVector<AttrState, 16> ArgumentState;
+  ArgumentState.resize(F.arg_size());
+
+  for (Use &U : F.uses()) {
+    User *UR = U.getUser();
+    // Ignore blockaddress uses.
+    if (isa<BlockAddress>(UR)) continue;
+    
+    // Used by a non-instruction, or not the callee of a function, do not
+    // transform.
+    if (!isa<CallInst>(UR) && !isa<InvokeInst>(UR))
+      return MadeChange;
+    
+    CallSite CS(cast<Instruction>(UR));
+    if (!CS.isCallee(&U))
+      return MadeChange;
+
+    // Check out all of the arguments. Note that we don't inspect varargs here.
+    CallSite::arg_iterator AI = CS.arg_begin();
+    Function::arg_iterator Arg = F.arg_begin();
+    for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i, ++AI, ++Arg) {
+      // If we've already excluded this argument, ignore it.
+      if (!ArgumentState[i].any())
+        continue;
+
+      Type *Ty = (*AI)->getType();
+      if (!Ty->isPointerTy()) {
+        ArgumentState[i].setNone();
+        continue;
+      }
+
+      if (ArgumentState[i].IsNonNull && !Arg->hasNonNullAttr()) {
+        if (!isKnownNonNull(*AI, TLI))
+          ArgumentState[i].IsNonNull = false;
+      }
+
+      Type *ETy = Ty->getPointerElementType();
+      if (!DL || !ETy->isSized()) {
+        ArgumentState[i].IsDereferenceable = false;
+      } else if (ArgumentState[i].IsDereferenceable &&
+                 ArgumentState[i].MaxSize > Arg->getDereferenceableBytes()) {
+        uint64_t TypeSize = DL->getTypeStoreSize(ETy);
+        if (!(*AI)->isDereferenceablePointer(DL) &&
+            !isSafeToLoadUnconditionally(*AI, CS.getInstruction(),
+                                         getKnownAlignment(*AI, DL), DL)) {
+          ArgumentState[i].IsDereferenceable = false;
+        } else {
+          uint64_t Size;
+          if (!getObjectSize(*AI, Size, DL, TLI)) {
+            Size = TypeSize;
+          } else {
+      // We've already verified that a load of the type size would not
+      // trap, so we can use at least that size.
+            Size = std::max(Size, TypeSize);
+          }
+
+          ArgumentState[i].MaxSize = std::min(ArgumentState[i].MaxSize, Size);
+          if (!ArgumentState[i].MaxSize)
+            ArgumentState[i].IsDereferenceable = false;
+        }
+      }
+     
+      if (isa<GlobalValue>(*AI)) {
+        ArgumentState[i].IsNoAlias = false;
+      } else if (ArgumentState[i].IsNoAlias && !Arg->hasNoAliasAttr()) {
+        bool NoAlias = true;
+        for (CallSite::arg_iterator BI = CS.arg_begin(), BIE = CS.arg_end();
+             BI != BIE; ++BI) {
+          if (BI == AI)
+            continue;
+
+          if (AA->alias(*AI, *BI) != AliasAnalysis::NoAlias) {
+            NoAlias = false;
+            break;
+          }
+        }
+
+        SmallVector<Value*, 16> UObjects;
+        GetUnderlyingObjects(*AI, UObjects, DL);
+        for (Value *V : UObjects)
+          if (!isIdentifiedFunctionLocal(V)) {
+            NoAlias = false;
+            break;
+          }
+
+        if (NoAlias) {
+          DominatorTree *DT;
+          Function *Caller = CS.getInstruction()->getParent()->getParent();
+          auto DTI = DTs.find(Caller);
+          if (DTI == DTs.end()) {
+            DT = new DominatorTree;
+            DT->recalculate(*Caller);
+            DTs[Caller] = DT;
+          } else {
+            DT = DTI->second;
+          }
+
+          if (PointerMayBeCapturedBefore(*AI, /* ReturnCaptures */ false,
+                                         /* StoreCaptures */ false,
+                                         CS.getInstruction(), DT))
+            ArgumentState[i].IsNoAlias = false;
+        } else {
+          ArgumentState[i].IsNoAlias = false;
+        }
+      }
+    }
+
+    bool HaveCand = false;
+    for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i)
+      if (ArgumentState[i].any()) {
+        HaveCand = true;
+        break;
+      }
+
+    if (!HaveCand)
+      break;
+  }
+
+  Function::arg_iterator AI = F.arg_begin();
+  for (unsigned i = 0, e = ArgumentState.size(); i != e; ++i, ++AI) {
+    if (!ArgumentState[i].any() || AI->hasInAllocaAttr() || AI->hasByValAttr())
+      continue;
+
+    if (!AI->hasNonNullAttr() && ArgumentState[i].IsNonNull &&
+        (!ArgumentState[i].IsDereferenceable ||
+         AI->getType()->getPointerAddressSpace() != 0)) {
+      AttrBuilder B;
+      B.addAttribute(Attribute::NonNull);
+
+      AI->addAttr(AttributeSet::get(F.getContext(), AI->getArgNo() + 1, B));
+      ++NumNonNull;
+      MadeChange = true;
+    }
+
+    if (!AI->hasNoAliasAttr() && ArgumentState[i].IsNoAlias) {
+      AttrBuilder B;
+      B.addAttribute(Attribute::NoAlias);
+
+      AI->addAttr(AttributeSet::get(F.getContext(), AI->getArgNo() + 1, B));
+      ++NumNoAlias;
+      MadeChange = true;
+    }
+
+    if (!AI->getDereferenceableBytes() && ArgumentState[i].IsDereferenceable) {
+      AttrBuilder B;
+      B.addDereferenceableAttr(ArgumentState[i].MaxSize);
+
+      AI->addAttr(AttributeSet::get(F.getContext(), AI->getArgNo() + 1, B));
+      ++NumDereferenceable;
+      MadeChange = true;
+    }
+  }
+
+  return MadeChange;
+}
+
+bool FunctionAttrsTD::runOnModule(Module &M) {
+  AA = &getAnalysis<AliasAnalysis>();
+  TLI = &getAnalysis<TargetLibraryInfo>();
+  DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
+  DL = DLP ? &DLP->getDataLayout() : nullptr;
+
+  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+  CallGraphNode *ExternalNode = CG.getExternalCallingNode();
+  bool Changed = false;
+
+  DenseMap<Function *, DominatorTree *> DTs;
+  for (df_iterator<CallGraphNode*> I = df_begin(ExternalNode),
+       IE = df_end(ExternalNode); I != IE; ++I) {
+    Function *F = (*I)->getFunction();
+    if (!F)
+      continue;
+    DEBUG(dbgs() << "FATD visiting: " << F->getName() << "\n");
+
+    Changed |= addFuncAttrs(*F, DTs);
+  }
+
+  return Changed;
+}
+
+ModulePass *llvm::createFunctionAttrsTDPass() { return new FunctionAttrsTD(); }
+

lib/Transforms/IPO/IPO.cpp

 using namespace llvm;
 
 void llvm::initializeIPO(PassRegistry &Registry) {
   initializeArgPromotionPass(Registry);
   initializeConstantMergePass(Registry);
   initializeDAEPass(Registry);
   initializeDAHPass(Registry);
   initializeFunctionAttrsPass(Registry);
+  initializeFunctionAttrsTDPass(Registry);
   initializeGlobalDCEPass(Registry);
   initializeGlobalOptPass(Registry);
   initializeIPCPPass(Registry);
   initializeAlwaysInlinerPass(Registry);
   initializeSimpleInlinerPass(Registry);
   initializeInternalizePassPass(Registry);
   initializeLoopExtractorPass(Registry);
   initializeBlockExtractorPassPass(Registry);

 void LLVMAddDeadArgEliminationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createDeadArgEliminationPass());
 }
 
 void LLVMAddFunctionAttrsPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createFunctionAttrsPass());
 }
 
+void LLVMAddFunctionAttrsTDPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createFunctionAttrsTDPass());
+}
+
 void LLVMAddFunctionInliningPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createFunctionInliningPass());
 }
 
 void LLVMAddAlwaysInlinerPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(llvm::createAlwaysInlinerPass());
 }
 

lib/Transforms/IPO/PassManagerBuilder.cpp

if (!DisableUnitAtATime) {
     MPM.add(createIPSCCPPass());              // IP SCCP
     MPM.add(createGlobalOptimizerPass());     // Optimize out global vars
 
     MPM.add(createDeadArgEliminationPass());  // Dead argument elimination
 
     MPM.add(createInstructionCombiningPass());// Clean up after IPCP & DAE
     addExtensionsToPM(EP_Peephole, MPM);
     MPM.add(createCFGSimplificationPass());   // Clean up after IPCP & DAE
+
+    MPM.add(createFunctionAttrsPass());       // Set nocapture attr
+    MPM.add(createFunctionAttrsTDPass());     // Set noalias attr
   }
 
   // Start of CallGraph SCC passes.
   if (!DisableUnitAtATime)
     MPM.add(createPruneEHPass());             // Remove dead EH info
   if (Inliner) {
     MPM.add(Inliner);
     Inliner = nullptr;
void PassManagerBuilder::populateLTOPassManager(PassManagerBase &PM,
   // Break up allocas
   if (UseNewSROA)
     PM.add(createSROAPass());
   else
     PM.add(createScalarReplAggregatesPass());
 
   // Run a few AA driven optimizations here and now, to cleanup the code.
   PM.add(createFunctionAttrsPass()); // Add nocapture.
+  PM.add(createFunctionAttrsTDPass()); // Add noalias.
   PM.add(createGlobalsModRefPass()); // IP alias analysis.
 
   PM.add(createLICMPass());                 // Hoist loop invariants.
   PM.add(createMergedLoadStoreMotionPass()); // Merge load/stores in diamonds
   PM.add(createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 
   // Nuke dead stores.

test/Transforms/FunctionAttrsTD/large-agg.ll

+; RUN: opt -S -basicaa -functionattrs-td < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.s = type { [65280 x i32] }
+%struct.x = type opaque
+%struct.x.0 = type opaque
+
+; CHECK: define void @bar()
+
+; Function Attrs: nounwind uwtable
+define void @bar() #0 {
+entry:
+  %x = alloca %struct.s, align 4
+  %y = alloca %struct.s, align 4
+  %0 = bitcast %struct.s* %x to i8*
+  call void @llvm.lifetime.start(i64 261120, i8* %0) #1
+  %1 = bitcast %struct.s* %y to i8*
+  call void @llvm.lifetime.start(i64 261120, i8* %1) #1
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds %struct.s* %x, i64 0, i32 0, i64 %indvars.iv
+  %2 = trunc i64 %indvars.iv to i32
+  store i32 %2, i32* %arrayidx, align 4, !tbaa !0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 17800
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  %3 = bitcast %struct.s* %y to %struct.x*
+  call fastcc void @foo(%struct.s* %x, %struct.x* %3)
+  call void @llvm.lifetime.end(i64 261120, i8* %1) #1
+  call void @llvm.lifetime.end(i64 261120, i8* %0) #1
+  ret void
+}
+
+; Function Attrs: nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture) #1
+
+; CHECK: define internal fastcc void @foo(%struct.s* noalias nocapture readonly dereferenceable(261120) %x, %struct.x* noalias %y)
+
+; Function Attrs: noinline nounwind uwtable
+define internal fastcc void @foo(%struct.s* nocapture readonly %x, %struct.x* %y) #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %sum.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds %struct.s* %x, i64 0, i32 0, i64 %indvars.iv
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  %add = add nsw i32 %0, %sum.05
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 16000
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  %1 = bitcast %struct.x* %y to %struct.x.0*
+  tail call void @goo(i32 %add, %struct.x.0* %1) #1
+  ret void
+}
+
+; Function Attrs: nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture) #1
+
+declare void @goo(i32, %struct.x.0*)
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+attributes #2 = { noinline nounwind uwtable }
+
+!0 = metadata !{metadata !1, metadata !1, i64 0}
+!1 = metadata !{metadata !"int", metadata !2, i64 0}
+!2 = metadata !{metadata !"omnipotent char", metadata !3, i64 0}
+!3 = metadata !{metadata !"Simple C/C++ TBAA"}

test/Transforms/FunctionAttrsTD/malloc.ll

+; RUN: opt -S -basicaa -functionattrs-td < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: define i32 @bar()
+
+; Function Attrs: nounwind uwtable
+define i32 @bar() #0 {
+entry:
+  %call = tail call noalias i8* @malloc(i64 12345) #3
+  %0 = bitcast i8* %call to i32*
+  store i32 10, i32* %0, align 4, !tbaa !0
+  tail call fastcc void @foo(i32* %0)
+  ret i32 0
+}
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64) #1
+
+; CHECK: define internal fastcc void @foo(i32* noalias dereferenceable(12345) %x)
+
+; Function Attrs: noinline nounwind uwtable
+define internal fastcc void @foo(i32* %x) #2 {
+entry:
+  %arrayidx = getelementptr inbounds i32* %x, i64 5
+  store i32 10, i32* %arrayidx, align 4, !tbaa !0
+  tail call void @goo(i32* %x) #3
+  ret void
+}
+
+declare void @goo(i32*) #3
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+attributes #2 = { noinline nounwind uwtable }
+attributes #3 = { nounwind }
+
+!0 = metadata !{metadata !1, metadata !1, i64 0}
+!1 = metadata !{metadata !"int", metadata !2, i64 0}
+!2 = metadata !{metadata !"omnipotent char", metadata !3, i64 0}
+!3 = metadata !{metadata !"Simple C/C++ TBAA"}
+