[ThinLTO] Add FunctionAttr NoRecurse and ReadAttr propagation to ThinLTO

[ncharlie]

Summary

This patch addresses part of Bug 33648. It adds new information to the summary and implements part of the FunctionAttrs pass (propagating read attrs and norecurse attrs). The other part of the pass is not implement at the moment, since it requires argument information which currently is not included in the summary.

[ncharlie]

lib/Transforms/IPO/FunctionImport.cpp

551

Not sure if this is the best place for this function.

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

409

Not sure if this is the best place for this function.

[ncharlie]

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

413

I'm don't think this entirely correct. The reason I did it this way was so I could reuse the computeFunctionBodyMemoryAccess from the original FunctionAttrs pass. I think I'll need to modify that function a bit to work with the Index so it can access information about functions external to the current module.

[ncharlie]

• added memory access info to index callgraph edges
• renamed functions

[ncharlie]

refactored code and removed unnecessary SCCNodes

[ncharlie]

Just a note: this isn't fully completed yet. I still have to add tests and do some verification, but I wanted to make it's on the right track.

[mehdi_amini]

Thanks, that's a very good start! Few comments inline, I didn't understand everything.

include/llvm/IR/ModuleSummaryIndex.h

60

I think we may get to the point with this structure where documenting fields here would be nice.

294

Doc.

366

Doc (including return value).

I'd suggest naming it: `updateCalleeMemAccessKind()`

include/llvm/Transforms/IPO/FunctionAttrs.h

36

DenseMap instead of std::map?

include/llvm/Transforms/IPO/FunctionImport.h

106

Doc (simple).

129

Doc.

lib/Transforms/IPO/FunctionImport.cpp

424

Here I'd expect a better description of "how" you're gonna achieve the API contract, i.e. a high level view about what's involved.

425

naming could help understand. Something like `all_of_calllees` or something like that (may still need a comment.

427

std::function``` is heavy, use ```llvm::function_ref``` here.

430

Are we sure there can't be an alias summary here?

440

early continue:

FunctionSummary *F = dyn_cast<FunctionSummary>(S.get());
if (!F) continue;
...

443

Doc.

445

Not sure why the second condition is needed?

551

Agree, but coherent with the one right below...

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

443

Why do we need to mark the edges?

[ncharlie]

lib/Transforms/IPO/FunctionImport.cpp

445

I copied that out of the original FunctionAttrs pass to prevent the function from being marked NoRecurse if it calls itself (http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/FunctionAttrs.cpp#1068).

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

443

I was planning on using that to propagate read attrs up to the caller. For instance:

void x(int *k) { // can't mark readonly since k could be global
  *k++;
}

void j() {
  int i = 5;
  x(&i); // since i is local memory, we can mark j as readnone
}

I'm currently working on implementing this - when I finish I'll update the patch.

[tejohnson]

In D35633#816514, @ncharlie wrote:

Just a note: this isn't fully completed yet. I still have to add tests and do some verification, but I wanted to make it's on the right track.

It looks like you are on the right track from the standpoint of dividing it up into pieces implemented during the compile step (building the index), the thin link (propagating), the backend (applying). I have a few comments after a quick initial perusal. But note when you have something ready for a full review, you should create a new patch that adds llvm-commits as a subscriber.

lib/Transforms/IPO/FunctionAttrs.cpp

94

These used to be continues, I think the change to an early return will mean that not all call site args are analyzed?

lib/Transforms/IPO/FunctionImport.cpp

443

CalleeInfo unused.

But in any case, I don't think the checking here is sufficient as it will only detect self-recursion, not indirect recursion (e.g. A->B->A). For that you need to build the SCC (strongly connected components) on the call graph in the index. See for example addNoRecurseAttrs where it first checks if the SCC has more than one function (in which case there is automatically indirect recursion).

I wonder if the SCC builder in llvm can be made to work for the index call graph? See SCCIterator.h. You'd need to provide GraphTraits for the index graph.

Additionally, the memory access info needs to be propagated during the thin link. See how FunctionAttrs propagates them across the SCC. See addReadAttrs() for example.

559

As mentioned above, this needs to be computed on the SCC.

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

413

This is called from the compile step, so there is no information in the Index for external functions. Here you just want to compute the per function attribute info to put into the index for the global analysis to use during the thin link.

494

Can this just be moved into the ModuleSummaryIndex builder (see ModuleSummaryAnalysis.cpp)? We should do all the building of the index there.

[ncharlie]

Updated as per comments.

[ncharlie]

Thank you for the feedback and corrections, @mehdi_amini and @tejohnson. I wasn't understanding the purpose of SCCNodes when I initially wrote the patch - thanks for clarifying :)

I'm going to work on GraphTraits for the ModuleSummaryIndex so SCCNodes can be used during the propagation step. After doing that and some cleanup I'll resubmit the patch to llvm-commits, unless anyone has any major modifications I should make to this patch.

lib/Transforms/IPO/FunctionAttrs.cpp

94

It's kinda messed up by the diff, I moved callsite analysis to its own function (analyseCallSite). Line 148 shows where it's called.

lib/Transforms/IPO/FunctionImport.cpp

443

But in any case, I don't think the checking here is sufficient as it will only detect self-recursion, not indirect recursion (e.g. A->B->A).

Ah, good point. Now I see what the SCCNodes are for.

I wonder if the SCC builder in llvm can be made to work for the index call graph? See SCCIterator.h. You'd need to provide GraphTraits for the index graph.

I started looking into this, and I think it'll be possible with a few more iterator types.

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

445

This comment does not display in the right place for me right now, to clarify I'm wondering about this:

if (!S->fflags().NoRecurse ||
    S->getOriginalName() == F->getOriginalName())

So the second check here is intended to check for self-recursion. Are we recording self-recursion in the summaries?
Can we check GUID equality instead of string comparison?
Also we need a test for this exact condition, i.e. a test that would fail with if (!S->fflags().NoRecurse) alone.

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

443

I think it is complex enough that doing it in two patches would be easier to review and assert correctness, catch edge cases, and make sure we have the right level of test coverage.
The first patch could be just doing the "simple case", and then you can extend it with the most advanced one. For the simple case you shouldn't need to touch edges I believe.

Also if possible, I'd even break it so that you first implement propagating only readnone, forget about norecurse and other stuff, and you don't need SCC. Then you can add more stuff. Again we'll have more targeted testing and we are less likely to miss anything in review (and if we need to bisect a failure, it'll be easier to pinpoint the faulty logic as well).

[ncharlie]

lib/Transforms/IPO/FunctionImport.cpp

445

Are we recording self-recursion in the summaries?

I think so. I'll double check, but I think this is a redundant check (in which case I'll remove it).

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

443

Sounds good - I was thinking about splitting it into multiple patches, and I agree with that level of granularity (i.e. a patch for propagating readnone, a patch for readnone propagated across call edges, and a patch for no recurse).

[davide]

This is a decent start, some comments inline. Thanks!

include/llvm/IR/ModuleSummaryIndex.h

306

Comment?

370–372

Do you need the -> bool ?

lib/Transforms/IPO/FunctionAttrs.cpp

89–94

range for?

121–123

I find this a little harder to read, maybe you can use an explicit continue instead of LLVM_FALLTHROUGH ?

993

spurious new whiteline.

[ncharlie]

Patch is being split into multiple dependent patches.

include/llvm/IR/ModuleSummaryIndex.h

 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 namespace yaml {
 
 template <typename T> struct MappingTraits;
+struct ModuleSummaryIndexWithModule;
 
 } // end namespace yaml
 
 /// \brief Class to accumulate and hold information about a callee.
 struct CalleeInfo {
   enum class HotnessType : uint8_t {
     Unknown = 0,
     Cold = 1,
     None = 2,
     Hot = 3,
     Critical = 4
   };
+  enum class MemoryAccessType : uint8_t { None = 0, Read = 1, MayWrite = 2 };
   HotnessType Hotness = HotnessType::Unknown;
+  MemoryAccessType MemoryAccess = MemoryAccessType::MayWrite;
 
   CalleeInfo() = default;
-  explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {}
+  explicit CalleeInfo(HotnessType Hotness, MemoryAccessType A)
+      : Hotness(Hotness), MemoryAccess(A) {}
 
   void updateHotness(const HotnessType OtherHotness) {
     Hotness = std::max(Hotness, OtherHotness);
   }
 };
 
 class GlobalValueSummary;
 
public:
   /// A specification for a virtual function call with all constant integer
   /// arguments. This is used to perform virtual constant propagation on the
   /// summary.
   struct ConstVCall {
     VFuncId VFunc;
     std::vector<uint64_t> Args;
   };
 
+  struct FFlags {
+    unsigned ReadNone : 1;
+    unsigned ReadOnly : 1;
+    unsigned NoRecurse : 1;
+    unsigned NoAlias : 1;
+  };
+
 private:
   /// Number of instructions (ignoring debug instructions, e.g.) computed
   /// during the initial compile step when the summary index is first built.
   unsigned InstCount;
 
+  FFlags FunFlags;
+
   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
   std::vector<EdgeTy> CallGraphEdgeList;
 
   /// All type identifier related information. Because these fields are
   /// relatively uncommon we only allocate space for them if necessary.
   struct TypeIdInfo {
     /// List of type identifiers used by this function in llvm.type.test
     /// intrinsics other than by an llvm.assume intrinsic, represented as GUIDs.
struct TypeIdInfo {
     /// all constant integer arguments.
     std::vector<ConstVCall> TypeTestAssumeConstVCalls,
         TypeCheckedLoadConstVCalls;
   };
 
   std::unique_ptr<TypeIdInfo> TIdInfo;
 
 public:
-  FunctionSummary(GVFlags Flags, unsigned NumInsts, std::vector<ValueInfo> Refs,
-                  std::vector<EdgeTy> CGEdges,
+  FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
+                  std::vector<ValueInfo> Refs, std::vector<EdgeTy> CGEdges,
                   std::vector<GlobalValue::GUID> TypeTests,
                   std::vector<VFuncId> TypeTestAssumeVCalls,
                   std::vector<VFuncId> TypeCheckedLoadVCalls,
                   std::vector<ConstVCall> TypeTestAssumeConstVCalls,
                   std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
-        InstCount(NumInsts), CallGraphEdgeList(std::move(CGEdges)) {
+        InstCount(NumInsts), FunFlags(FunFlags),
+        CallGraphEdgeList(std::move(CGEdges)) {
     if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
         !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
         !TypeCheckedLoadConstVCalls.empty())
       TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
           std::move(TypeTests), std::move(TypeTestAssumeVCalls),
           std::move(TypeCheckedLoadVCalls),
           std::move(TypeTestAssumeConstVCalls),
           std::move(TypeCheckedLoadConstVCalls)});
   }
 
   /// Check if this is a function summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == FunctionKind;
   }
 
+  FFlags &fflags() { return FunFlags; }
+
   /// Get the instruction count recorded for this function.
   unsigned instCount() const { return InstCount; }
 
   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
 
   /// Returns the list of type identifiers used by this function in
   /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
   /// represented as GUIDs.
   ArrayRef<GlobalValue::GUID> type_tests() const {
     if (TIdInfo)
       return TIdInfo->TypeTests;
     return {};
   }
 
   /// Returns the list of virtual calls made by this function using
   /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
   /// integer arguments.
   ArrayRef<VFuncId> type_test_assume_vcalls() const {
     if (TIdInfo)
       return TIdInfo->TypeTestAssumeVCalls;
private:
   /// considered live.
   bool WithGlobalValueDeadStripping = false;
 
   std::set<std::string> CfiFunctionDefs;
   std::set<std::string> CfiFunctionDecls;
 
   // YAML I/O support.
   friend yaml::MappingTraits<ModuleSummaryIndex>;
+  friend yaml::MappingTraits<yaml::ModuleSummaryIndexWithModule>;
 
   GlobalValueSummaryMapTy::value_type *
   getOrInsertValuePtr(GlobalValue::GUID GUID) {
     return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo{}).first;
   }
 
 public:
   gvsummary_iterator begin() { return GlobalValueMap.begin(); }

include/llvm/IR/ModuleSummaryIndexYAML.h

if (Key.getAsInteger(0, KeyInt)) {
       return;
     }
     auto &Elem = V[KeyInt];
     for (auto &FSum : FSums) {
       Elem.SummaryList.push_back(llvm::make_unique<FunctionSummary>(
           GlobalValueSummary::GVFlags(
               static_cast<GlobalValue::LinkageTypes>(FSum.Linkage),
               FSum.NotEligibleToImport, FSum.Live),
-          0, ArrayRef<ValueInfo>{}, ArrayRef<FunctionSummary::EdgeTy>{},
-          std::move(FSum.TypeTests), std::move(FSum.TypeTestAssumeVCalls),
+          0, FunctionSummary::FFlags{}, ArrayRef<ValueInfo>{},
+          ArrayRef<FunctionSummary::EdgeTy>{}, std::move(FSum.TypeTests),
+          std::move(FSum.TypeTestAssumeVCalls),
           std::move(FSum.TypeCheckedLoadVCalls),
           std::move(FSum.TypeTestAssumeConstVCalls),
           std::move(FSum.TypeCheckedLoadConstVCalls)));
     }
   }
   static void output(IO &io, GlobalValueSummaryMapTy &V) {
     for (auto &P : V) {
       std::vector<FunctionSummaryYaml> FSums;

include/llvm/Transforms/IPO/FunctionAttrs.h

 /// 'readnone' attributes.
 enum MemoryAccessKind {
   MAK_ReadNone = 0,
   MAK_ReadOnly = 1,
   MAK_MayWrite = 2
 };
 
 /// Returns the memory access properties of this copy of the function.
-MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR);
+MemoryAccessKind
+computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR,
+                                SmallSetVector<Function *, 8> SCCNodes = {});
 
 /// Computes function attributes in post-order over the call graph.
 ///
 /// By operating in post-order, this pass computes precise attributes for
 /// called functions prior to processsing their callers. This "bottom-up"
 /// approach allows powerful interprocedural inference of function attributes
 /// like memory access patterns, etc. It can discover functions that do not
 /// access memory, or only read memory, and give them the readnone/readonly

include/llvm/Transforms/IPO/FunctionImport.h

 //===- llvm/Transforms/IPO/FunctionImport.h - ThinLTO importing -*- C++ -*-===//
 //
 //                      The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUNCTIONIMPORT_H
 #define LLVM_FUNCTIONIMPORT_H
 
 #include "llvm/ADT/StringMap.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Error.h"
 
 #include <functional>
 #include <map>
 #include <unordered_set>

 
 /// Compute all the symbols that are "dead": i.e these that can't be reached
 /// in the graph from any of the given symbols listed in
 /// \p GUIDPreservedSymbols.
 void computeDeadSymbols(
     ModuleSummaryIndex &Index,
     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
 
+void computeFunctionAttrs(ModuleSummaryIndex &Index);
+
 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 /// \p ModulePath.
 //
 /// This includes summaries from that module (in case any global summary based
 /// optimizations were recorded) and from any definitions in other modules that
 /// should be imported.
 //
 /// \p ModuleToSummariesForIndex will be populated with the needed summaries
 /// from each required module path. Use a std::map instead of StringMap to get
 /// stable order for bitcode emission.
 void gatherImportedSummariesForModule(
     StringRef ModulePath,
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     const FunctionImporter::ImportMapTy &ImportList,
     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex);
 
 /// Emit into \p OutputFilename the files module \p ModulePath will import from.
 std::error_code
 EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename,
                  const FunctionImporter::ImportMapTy &ModuleImports);
 
+void thinLTOInsertFunctionAttrsForModule(Module &TheModule,
+                                         const ModuleSummaryIndex &Index);
+
 /// Resolve WeakForLinker values in \p TheModule based on the information
 /// recorded in the summaries during global summary-based analysis.
 void thinLTOResolveWeakForLinkerModule(Module &TheModule,
                                        const GVSummaryMapTy &DefinedGlobals);
 
 /// Internalize \p TheModule based on the information recorded in the summaries
 /// during global summary-based analysis.
 void thinLTOInternalizeModule(Module &TheModule,
                               const GVSummaryMapTy &DefinedGlobals);
 }
 
 #endif // LLVM_FUNCTIONIMPORT_H

lib/Analysis/ModuleSummaryAnalysis.cpp

computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
   bool NonRenamableLocal = isNonRenamableLocal(F);
   bool NotEligibleForImport =
       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
       // Inliner doesn't handle variadic functions.
       // FIXME: refactor this to use the same code that inliner is using.
       F.isVarArg();
   GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
                                     /* Live = */ false);
+  FunctionSummary::FFlags FunFlags{
+      F.hasFnAttribute(Attribute::ReadNone),
+      F.hasFnAttribute(Attribute::ReadOnly),
+      F.hasFnAttribute(Attribute::NoRecurse),
+      F.hasFnAttribute(Attribute::NoAlias),
+  };
   auto FuncSummary = llvm::make_unique<FunctionSummary>(
-      Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
-      TypeTests.takeVector(), TypeTestAssumeVCalls.takeVector(),
-      TypeCheckedLoadVCalls.takeVector(),
+      Flags, NumInsts, FunFlags, RefEdges.takeVector(),
+      CallGraphEdges.takeVector(), TypeTests.takeVector(),
+      TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
       TypeTestAssumeConstVCalls.takeVector(),
       TypeCheckedLoadConstVCalls.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(F.getGUID());
   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 }
 
 static void
ModuleSymbolTable::CollectAsmSymbols(
           if (!GV)
             return;
           assert(GV->isDeclaration() && "Def in module asm already has definition");
           GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
                                               /* NotEligibleToImport = */ true,
                                               /* Live = */ true);
           CantBePromoted.insert(GlobalValue::getGUID(Name));
           // Create the appropriate summary type.
-          if (isa<Function>(GV)) {
+          if (Function *F = dyn_cast<Function>(GV)) {
             std::unique_ptr<FunctionSummary> Summary =
                 llvm::make_unique<FunctionSummary>(
-                    GVFlags, 0, ArrayRef<ValueInfo>{},
-                    ArrayRef<FunctionSummary::EdgeTy>{},
+                    GVFlags, 0,
+                    FunctionSummary::FFlags{
+                        F->hasFnAttribute(Attribute::ReadNone),
+                        F->hasFnAttribute(Attribute::ReadOnly),
+                        F->hasFnAttribute(Attribute::NoRecurse),
+                        F->hasFnAttribute(Attribute::NoAlias)},
+                    ArrayRef<ValueInfo>{}, ArrayRef<FunctionSummary::EdgeTy>{},
                     ArrayRef<GlobalValue::GUID>{},
                     ArrayRef<FunctionSummary::VFuncId>{},
                     ArrayRef<FunctionSummary::VFuncId>{},
                     ArrayRef<FunctionSummary::ConstVCall>{},
                     ArrayRef<FunctionSummary::ConstVCall>{});
             Index.addGlobalValueSummary(Name, std::move(Summary));
           } else {
             std::unique_ptr<GlobalVarSummary> Summary =

lib/Bitcode/Reader/BitcodeReader.cpp

static GlobalValue::LinkageTypes getDecodedLinkage(unsigned Val) {
   case 18:
     return GlobalValue::LinkOnceAnyLinkage;
   case 11: // Old value with implicit comdat.
   case 19:
     return GlobalValue::LinkOnceODRLinkage;
   }
 }
 
+static FunctionSummary::FFlags getDecodedFFlags(uint64_t RawFlags) {
+  FunctionSummary::FFlags Flags;
+  Flags.ReadNone = RawFlags & 0x1;
+  Flags.ReadOnly = (RawFlags >> 1) & 0x1;
+  Flags.NoRecurse = (RawFlags >> 2) & 0x1;
+  Flags.NoAlias = (RawFlags >> 3) & 0x1;
+  return Flags;
+}
+
 /// Decode the flags for GlobalValue in the summary.
 static GlobalValueSummary::GVFlags getDecodedGVSummaryFlags(uint64_t RawFlags,
                                                             uint64_t Version) {
   // Summary were not emitted before LLVM 3.9, we don't need to upgrade Linkage
   // like getDecodedLinkage() above. Any future change to the linkage enum and
   // to getDecodedLinkage() will need to be taken into account here as above.
   auto Linkage = GlobalValue::LinkageTypes(RawFlags & 0xF); // 4 bits
   RawFlags = RawFlags >> 4;

 
 std::vector<FunctionSummary::EdgeTy> ModuleSummaryIndexBitcodeReader::makeCallList(
     ArrayRef<uint64_t> Record, bool IsOldProfileFormat, bool HasProfile) {
   std::vector<FunctionSummary::EdgeTy> Ret;
   Ret.reserve(Record.size());
   for (unsigned I = 0, E = Record.size(); I != E; ++I) {
     CalleeInfo::HotnessType Hotness = CalleeInfo::HotnessType::Unknown;
     ValueInfo Callee = getValueInfoFromValueId(Record[I]).first;
+    CalleeInfo::MemoryAccessType MA =
+        static_cast<CalleeInfo::MemoryAccessType>(Record[++I]);
     if (IsOldProfileFormat) {
       I += 1; // Skip old callsitecount field
       if (HasProfile)
         I += 1; // Skip old profilecount field
     } else if (HasProfile)
       Hotness = static_cast<CalleeInfo::HotnessType>(Record[++I]);
-    Ret.push_back(FunctionSummary::EdgeTy{Callee, CalleeInfo{Hotness}});
+    Ret.push_back(FunctionSummary::EdgeTy{Callee, CalleeInfo{Hotness, MA}});
   }
   return Ret;
 }
 
 // Eagerly parse the entire summary block. This populates the GlobalValueSummary
 // objects in the index.
 Error ModuleSummaryIndexBitcodeReader::parseEntireSummary(unsigned ID) {
   if (Stream.EnterSubBlock(ID))
while (true) {
     // FS_PERMODULE_PROFILE: [valueid, flags, instcount, numrefs,
     //                        numrefs x valueid,
     //                        n x (valueid, hotness)]
     case bitc::FS_PERMODULE:
     case bitc::FS_PERMODULE_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t RawFlags = Record[1];
       unsigned InstCount = Record[2];
-      unsigned NumRefs = Record[3];
+      uint64_t RawFunFlags = Record[3];
+      unsigned NumRefs = Record[4];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       // The module path string ref set in the summary must be owned by the
       // index's module string table. Since we don't have a module path
       // string table section in the per-module index, we create a single
       // module path string table entry with an empty (0) ID to take
       // ownership.
-      static int RefListStartIndex = 4;
+      static int RefListStartIndex = 5;
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
       std::vector<ValueInfo> Refs = makeRefList(
           ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_PERMODULE_PROFILE);
       std::vector<FunctionSummary::EdgeTy> Calls = makeCallList(
           ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
           IsOldProfileFormat, HasProfile);
       auto FS = llvm::make_unique<FunctionSummary>(
-          Flags, InstCount, std::move(Refs), std::move(Calls),
-          std::move(PendingTypeTests), std::move(PendingTypeTestAssumeVCalls),
+          Flags, InstCount, getDecodedFFlags(RawFunFlags), std::move(Refs),
+          std::move(Calls), std::move(PendingTypeTests),
+          std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
       PendingTypeTestAssumeConstVCalls.clear();
       PendingTypeCheckedLoadConstVCalls.clear();
while (true) {
     // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, numrefs,
     //                       numrefs x valueid, n x (valueid, hotness)]
     case bitc::FS_COMBINED:
     case bitc::FS_COMBINED_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
       uint64_t RawFlags = Record[2];
       unsigned InstCount = Record[3];
-      unsigned NumRefs = Record[4];
+      uint64_t RawFunFlags = Record[4];
+      unsigned NumRefs = Record[5];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
-      static int RefListStartIndex = 5;
+      static int RefListStartIndex = 6;
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
       std::vector<ValueInfo> Refs = makeRefList(
           ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE);
       std::vector<FunctionSummary::EdgeTy> Edges = makeCallList(
           ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
           IsOldProfileFormat, HasProfile);
       ValueInfo VI = getValueInfoFromValueId(ValueID).first;
       auto FS = llvm::make_unique<FunctionSummary>(
-          Flags, InstCount, std::move(Refs), std::move(Edges),
-          std::move(PendingTypeTests), std::move(PendingTypeTestAssumeVCalls),
+          Flags, InstCount, getDecodedFFlags(RawFunFlags), std::move(Refs),
+          std::move(Edges), std::move(PendingTypeTests),
+          std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
       PendingTypeTestAssumeConstVCalls.clear();
       PendingTypeCheckedLoadConstVCalls.clear();

lib/Bitcode/Writer/BitcodeWriter.cpp

static unsigned getEncodedLinkage(const GlobalValue::LinkageTypes Linkage) {
   }
   llvm_unreachable("Invalid linkage");
 }
 
 static unsigned getEncodedLinkage(const GlobalValue &GV) {
   return getEncodedLinkage(GV.getLinkage());
 }
 
+static uint64_t getEncodedFFlags(FunctionSummary::FFlags Flags) {
+  uint64_t RawFlags = 0;
+  RawFlags |= Flags.ReadNone;
+  RawFlags |= (Flags.ReadOnly << 1);
+  RawFlags |= (Flags.NoRecurse << 2);
+  RawFlags |= (Flags.NoAlias << 3);
+  return RawFlags;
+}
+
 // Decode the flags for GlobalValue in the summary
 static uint64_t getEncodedGVSummaryFlags(GlobalValueSummary::GVFlags Flags) {
   uint64_t RawFlags = 0;
 
   RawFlags |= Flags.NotEligibleToImport; // bool
   RawFlags |= (Flags.Live << 1);
   // Linkage don't need to be remapped at that time for the summary. Any future
   // change to the getEncodedLinkage() function will need to be taken into

 }
 
 void ModuleBitcodeWriter::writeDIGlobalVariableExpression(
     const DIGlobalVariableExpression *N, SmallVectorImpl<uint64_t> &Record,
     unsigned Abbrev) {
   Record.push_back(N->isDistinct());
   Record.push_back(VE.getMetadataOrNullID(N->getVariable()));
   Record.push_back(VE.getMetadataOrNullID(N->getExpression()));
-  
   Stream.EmitRecord(bitc::METADATA_GLOBAL_VAR_EXPR, Record, Abbrev);
   Record.clear();
 }
 
 void ModuleBitcodeWriter::writeDIObjCProperty(const DIObjCProperty *N,
                                               SmallVectorImpl<uint64_t> &Record,
                                               unsigned Abbrev) {
   Record.push_back(N->isDistinct());
void ModuleBitcodeWriter::writePerModuleFunctionSummaryRecord(
     const Function &F) {
   NameVals.push_back(ValueID);
 
   FunctionSummary *FS = cast<FunctionSummary>(Summary);
   writeFunctionTypeMetadataRecords(Stream, FS);
 
   NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
   NameVals.push_back(FS->instCount());
+  NameVals.push_back(getEncodedFFlags(FS->fflags()));
   NameVals.push_back(FS->refs().size());
 
   for (auto &RI : FS->refs())
     NameVals.push_back(VE.getValueID(RI.getValue()));
 
   bool HasProfileData = F.getEntryCount().hasValue();
   for (auto &ECI : FS->calls()) {
     NameVals.push_back(getValueId(ECI.first));
+    NameVals.push_back(static_cast<uint8_t>(ECI.second.MemoryAccess));
     if (HasProfileData)
       NameVals.push_back(static_cast<uint8_t>(ECI.second.Hotness));
   }
 
   unsigned FSAbbrev = (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
   unsigned Code =
       (HasProfileData ? bitc::FS_PERMODULE_PROFILE : bitc::FS_PERMODULE);
 
forEachSummary([&](GVInfo I) {
 
     auto *FS = cast<FunctionSummary>(S);
     writeFunctionTypeMetadataRecords(Stream, FS);
 
     NameVals.push_back(*ValueId);
     NameVals.push_back(Index.getModuleId(FS->modulePath()));
     NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
     NameVals.push_back(FS->instCount());
+    NameVals.push_back(getEncodedFFlags(FS->fflags()));
     // Fill in below
     NameVals.push_back(0);
 
     unsigned Count = 0;
     for (auto &RI : FS->refs()) {
       auto RefValueId = getValueId(RI.getGUID());
       if (!RefValueId)
         continue;
       NameVals.push_back(*RefValueId);
       Count++;
     }
-    NameVals[4] = Count;
+    NameVals[5] = Count;
 
     bool HasProfileData = false;
     for (auto &EI : FS->calls()) {
       HasProfileData |= EI.second.Hotness != CalleeInfo::HotnessType::Unknown;
       if (HasProfileData)
         break;
     }
 
for (auto &EI : FS->calls()) {
         GUID = Index.getGUIDFromOriginalID(GUID);
         if (GUID == 0)
           continue;
         CallValueId = getValueId(GUID);
         if (!CallValueId)
           continue;
       }
       NameVals.push_back(*CallValueId);
+      NameVals.push_back(static_cast<uint8_t>(EI.second.MemoryAccess));
       if (HasProfileData)
         NameVals.push_back(static_cast<uint8_t>(EI.second.Hotness));
     }
 
     unsigned FSAbbrev = (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
     unsigned Code =
         (HasProfileData ? bitc::FS_COMBINED_PROFILE : bitc::FS_COMBINED);
 

lib/LTO/LTO.cpp

if (Res.second.VisibleOutsideSummary &&
         // IRName will be defined if we have seen the prevailing copy of
         // this value. If not, no need to preserve any ThinLTO copies.
         !Res.second.IRName.empty())
       GUIDPreservedSymbols.insert(GlobalValue::getGUID(
           GlobalValue::dropLLVMManglingEscape(Res.second.IRName)));
   }
 
   computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
+  computeFunctionAttrs(ThinLTO.CombinedIndex);
 
   // Save the status of having a regularLTO combined module, as
   // this is needed for generating the ThinLTO Task ID, and
   // the CombinedModule will be moved at the end of runRegularLTO.
   bool HasRegularLTO = RegularLTO.CombinedModule != nullptr ||
                        !RegularLTO.ModsWithSummaries.empty();
   // Invoke regular LTO if there was a regular LTO module to start with.
   if (HasRegularLTO)

lib/LTO/LTOBackend.cpp

Error lto::thinBackend(Config &Conf, unsigned Task, AddStreamFn AddStream,
   }
 
   if (Conf.PreOptModuleHook && !Conf.PreOptModuleHook(Task, Mod))
     return Error::success();
 
   renameModuleForThinLTO(Mod, CombinedIndex);
 
   thinLTOResolveWeakForLinkerModule(Mod, DefinedGlobals);
+  thinLTOInsertFunctionAttrsForModule(Mod, CombinedIndex);
 
   if (Conf.PostPromoteModuleHook && !Conf.PostPromoteModuleHook(Task, Mod))
     return Error::success();
 
   if (!DefinedGlobals.empty())
     thinLTOInternalizeModule(Mod, DefinedGlobals);
 
   if (Conf.PostInternalizeModuleHook &&

lib/Transforms/IPO/FunctionAttrs.cpp

if (AliasAnalysis::onlyReadsMemory(MRB))
       return MAK_ReadOnly;
 
     // Conservatively assume it writes to memory.
     return MAK_MayWrite;
   }
 
   // Scan the function body for instructions that may read or write memory.
   bool ReadsMemory = false;
   for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
     Instruction *I = &*II;
 
     // Some instructions can be ignored even if they read or write memory.
     // Detect these now, skipping to the next instruction if one is found.
     CallSite CS(cast<Value>(I));
     if (CS) {
       // Ignore calls to functions in the same SCC, as long as the call sites
       // don't have operand bundles.  Calls with operand bundles are allowed to
       // have memory effects not described by the memory effects of the call
       // target.
       if (!CS.hasOperandBundles() && CS.getCalledFunction() &&
           SCCNodes.count(CS.getCalledFunction()))
         continue;
if (CS) {
         // If it reads, note it.
         if (MRB & MRI_Ref)
           ReadsMemory = true;
         continue;
       }
 
       // Check whether all pointer arguments point to local memory, and
       // ignore calls that only access local memory.
       for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
            CI != CE; ++CI) {
         Value *Arg = *CI;
         if (!Arg->getType()->isPtrOrPtrVectorTy())
           continue;
 
         AAMDNodes AAInfo;
         I->getAAMetadata(AAInfo);
         MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
 
         // Skip accesses to local or constant memory as they don't impact the
for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
 
     // If this instruction may read memory, remember that.
     ReadsMemory |= I->mayReadFromMemory();
   }
 
   return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
 }
 
-MemoryAccessKind llvm::computeFunctionBodyMemoryAccess(Function &F,
-                                                       AAResults &AAR) {
-  return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
+MemoryAccessKind
+llvm::computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR,
+                                      SmallSetVector<Function *, 8> SCCNodes) {
+  return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, SCCNodes);
 }
 
 /// Deduce readonly/readnone attributes for the SCC.
 template <typename AARGetterT>
 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
   // Check if any of the functions in the SCC read or write memory.  If they
   // write memory then they can't be marked readnone or readonly.
   bool ReadsMemory = false;
if (auto CS = CallSite(&I)) {
             Changed = true;
           }
         }
       }
     }
     if (!isGuaranteedToTransferExecutionToSuccessor(&I))
       break;
   }
-  
   return Changed;
 }
 
 /// Deduce nocapture attributes for the SCC.
 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
   bool Changed = false;
 
   ArgumentGraph AG;
if (SCCReturnsNonNull) {
     for (Function *F : SCCNodes) {
       if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
                                           Attribute::NonNull) ||
           !F->getReturnType()->isPointerTy())
         continue;
 
       DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
       F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
+
       ++NumNonNullReturn;
       MadeChange = true;
     }
   }
 
   return MadeChange;
 }
 

lib/Transforms/IPO/FunctionImport.cpp

 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/Linker/Linker.h"
 #include "llvm/Object/IRObjectFile.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/SourceMgr.h"
+#include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
 
 #define DEBUG_TYPE "function-import"
 
 using namespace llvm;
 
 STATISTIC(NumImportedFunctions, "Number of functions imported");
#ifndef NDEBUG
   for (auto &Src : ImportList) {
     auto SrcModName = Src.first();
     DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from "
                  << SrcModName << "\n");
   }
 #endif
 }
 
+void llvm::computeFunctionAttrs(ModuleSummaryIndex &Index) {
+  auto propagateNoRecurse = [](FunctionSummary *F) {
+    for (auto &C : F->calls()) {
+      for (auto &V : C.first.getSummaryList()) {
+        FunctionSummary *S = cast<FunctionSummary>(V.get());
+        if (!S->fflags().NoRecurse ||
+            S->getOriginalName() == F->getOriginalName())
+          break;
+      }
+
+      F->fflags().NoRecurse = true;
+    }
+  };
+
+  for (const auto &P : Index) {
+    for (auto &S : P.second.SummaryList)
+      if (FunctionSummary *F = dyn_cast<FunctionSummary>(S.get())) {
+        // TODO: propagate NoRecurseTopdown
+        propagateNoRecurse(F);
+      }
+  }
+}
+
 void llvm::computeDeadSymbols(
     ModuleSummaryIndex &Index,
     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
   assert(!Index.withGlobalValueDeadStripping());
   if (!ComputeDead)
     return;
   if (GUIDPreservedSymbols.empty())
     // Don't do anything when nothing is live, this is friendly with tests.
llvm::EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename,
   raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None);
   if (EC)
     return EC;
   for (auto &ILI : ModuleImports)
     ImportsOS << ILI.first() << "\n";
   return std::error_code();
 }
 
+void llvm::thinLTOInsertFunctionAttrsForModule(
+    Module &TheModule, const ModuleSummaryIndex &Index) {
+  for (Function &F : TheModule) {
+    if (!Index.findSummaryInModule(F.getGUID(), F.getParent()->getName()))
+      continue; // skip functions that aren't in the index
+    GlobalValueSummary *GV = Index.getGlobalValueSummary(F);
+    FunctionSummary *FS = cast<FunctionSummary>(GV);
+    if (FS->fflags().ReadNone)
+      F.setDoesNotAccessMemory();
+    if (FS->fflags().ReadOnly)
+      F.setOnlyReadsMemory();
+  }
+}
+
 /// Fixup WeakForLinker linkages in \p TheModule based on summary analysis.
 void llvm::thinLTOResolveWeakForLinkerModule(
     Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
   auto ConvertToDeclaration = [](GlobalValue &GV) {
     DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName() << "\n");
     if (Function *F = dyn_cast<Function>(&GV)) {
       F->deleteBody();
       F->clearMetadata();

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
+#include "llvm/Transforms/IPO/FunctionImport.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 using namespace llvm;
 
 namespace {
 
 // Promote each local-linkage entity defined by ExportM and used by ImportM by
 // changing visibility and appending the given ModuleId.
for (auto &GO : M.global_objects()) {
     GO.getMetadata(LLVMContext::MD_type, MDs);
     if (!MDs.empty())
       return true;
   }
 
   return false;
 }
 
+static void computeThinMemoryAccess(Module &TheModule,
+                                    const ModuleSummaryIndex &Index,
+                                    LegacyAARGetter AARGetter) {
+  SmallSetVector<Function *, 8> SCCNodes;
+  for (Function &C : TheModule.getFunctionList()) {
+    SCCNodes.insert(&C);
+  }
+
+  for (Function &F : TheModule) {
+    GlobalValueSummary *GV;
+
+    if (!(GV = Index.findSummaryInModule(F.getGUID(), "")))
+      continue; // skip functions that aren't in the index
+
+    FunctionSummary *FS = cast<FunctionSummary>(GV);
+    AAResults &R = AARGetter(F);
+
+    bool Changed = false;
+    switch (computeFunctionBodyMemoryAccess(F, R, SCCNodes)) {
+    case MAK_MayWrite:
+      break;
+    case MAK_ReadOnly:
+      if (!FS->fflags().ReadOnly) {
+        Changed = true;
+        FS->fflags().ReadOnly = true;
+      }
+      break;
+    case MAK_ReadNone:
+      if (!FS->fflags().ReadNone) {
+        Changed = true;
+        FS->fflags().ReadOnly = false;
+        FS->fflags().ReadNone = true;
+      }
+      break;
+    }
+  }
+}
+
 void writeThinLTOBitcode(raw_ostream &OS, raw_ostream *ThinLinkOS,
                          function_ref<AAResults &(Function &)> AARGetter,
                          Module &M, const ModuleSummaryIndex *Index) {
   // See if this module has any type metadata. If so, we need to split it.
   if (requiresSplit(M))
     return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M);
 
   // Otherwise we can just write it out as a regular module.
explicit WriteThinLTOBitcode(raw_ostream &o, raw_ostream *ThinLinkOS)
     initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
   }
 
   StringRef getPassName() const override { return "ThinLTO Bitcode Writer"; }
 
   bool runOnModule(Module &M) override {
     const ModuleSummaryIndex *Index =
         &(getAnalysis<ModuleSummaryIndexWrapperPass>().getIndex());
+    computeThinMemoryAccess(M, *Index, LegacyAARGetter(*this));
     writeThinLTOBitcode(OS, ThinLinkOS, LegacyAARGetter(*this), M, Index);
     return true;
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<ModuleSummaryIndexWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();