[OpenMPOpt] ICV Tracking

[sstefan1]

Summary

This is first part if ICV tracking support in OpenMPOpt. Things that are included in this pathc:

• ICV information definition (not complete) in OMPKinds.def.
• OpenMP-specific information cache based on Attributor's InformationCache. This should should make it easier to share information between them.
• possibility of running the Attributor through runAttributor().
• AAICVTracking AbstractAttribute with basic tracking.

Since there are a lot of changes to agree up on, I left out the deduplication part for now. There are 2 possible places where that can be done: current deduplication functions, or within AAICVTracking's manifest.

This can also be treated as a RFC.

[jdoerfert]

I left a first set of comments. I think the overall direction is good, some interesting opportunities are opening up (see below). We need tests and also to split the patch (some suggestions below).

llvm/include/llvm/Frontend/OpenMP/OMPKinds.def

367

Remove the comment for now. and also the clause stuff.

llvm/include/llvm/Transforms/IPO/Attributor.h

822

Why do we want a pointer here? We can derive from InformationCache elsewhere and still provide a reference, right?

877

I think everything else would just duplicate code. This can be public but the comment should mention that use *after* the Attributor was started to run is restricted to the Attributor itself. Initial seeding can be done via this function.

929

Just moving this to be public with a new comment LGTM. Feel free to do this right away. If you want input on the comment, let me know.

2980

I think the AA should live in OpenMP opt. TBH, similar to a comment below, I would like us to have a "simplification AA" here at some point. More specifically for this use case a "call simplifier". Those interfaces would live with the Attributor and be used by it, via some registration mechanism. It might even be useful to have the general logic in here eventually so that only a few functions need to be implemented by the user, e.g., bool interactsWithHiddenState(CallBase &CB), Optional<Value> getNewHiddenState(CallBase &CB), bool returnsHiddenState(CallBase &CB). The generic algorithm would track the "hidden state" (here ICV value) and provide all the logic. We can do that in a follow up or now. WDYT?

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

59

As long as there is no other user we keep it here.

94

I think we need to do that eventually but for a first restricted deduction, see below, we might not need to. Just remove the comments for now then.

117

Documentation gone? We need some for both functions.

127

Why this change?

302

I think an RFC commit moving everything into a "cache" helper class should be provided seperatly. That seems trivial to accept and will significantly shrink this diff.

686

I feel the instance might be preferable so we can access AAs later, e.g., via A.lookupAAFor.

688

I think in the long run we want to register the ICV tracking attribute as another "simplification" attribute (for runtime calls). Then, the Attributor can ask all simplification attributes for a better value for a call, potentially resulting in better liveness and therefore better ICV tracking ;)

For now we could whitelist only ICV tracking (I guess).

808

Style: Add braces if you have a comment that makes the body multi-line.
You have to verify there is no cal in-between the two instructions too:

set_num_threads(2);
foo(); // resets num_threads
get_num_threads();

^ negative test we should keep.

We expand our tracking efforts in a follow up, for now we can be restrictive and correct with some positive and negative tests.

815

I don't think this works:

if (...)
  set_num_threads(2);
get_num_threads();

^ negative test we should keep.

For the first version go with the same basic block only

[sstefan1]

In D81788#2091453, @jdoerfert wrote:

I left a first set of comments. I think the overall direction is good, some interesting opportunities are opening up (see below). We need tests and also to split the patch (some suggestions below).

Maybe D81114 should be commited first, or should I just abandon that and put the tests here?

I'll split this with at least two more patches.

llvm/include/llvm/Transforms/IPO/Attributor.h

822

So that we can later cast it to OMPInformationCache and use openmp-specific information. This seemed like least amount of change.

877

I guess then it should also be allowed to be used after Attributor run is finished? Say we want to know ICV value after the Attributor run and all the deduplication, we still won't have querying attribute. Or should we also expose lookupAAFor?

929

You mean a NFC commit without a review?

2980

I think this should work, but I'll have to put more thought into (mainly the registration mechanism). this I'm in favor of getting this in first, since this is already proven to be rather large patch with lots of changes.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

117

Forgot to copy. Will do.

127

I think this comes from the fact that the same OMPInfoCache is shared between the Attributor and OpenMPOPT. Maybe we'll be able to avoid this after splitting up the patch, but I'm not sure.

815

I agree. Not to proud of this part tbh. I'll leave this out for now.

[jdoerfert]

I think this needs a rebase once some other landed.

llvm/include/llvm/Transforms/IPO/Attributor.h

822

You can cast regardless. If there is no other reason, please keep it a reference :)

877

Iff you are careful, you can use this *after* a run, e.g. if you only use information from attributes at a fixpoint. Exposing lookup makes this less error prone and would allow us to have an assert even. The other way is to create and remember all interesting locations. That is usually what we did so far but if we have non AA users lookup might be useful as well.

929

Yes. The code movement parts.

2980

Agreed. We can even split them further and submit the NFC parts so it becomes clearer to me what changes :)

[sstefan1]

• clean up the patch
• basic deduplication

[jdoerfert]

Nit: Add documentation to functions and classes please. Describe what happens and why if applicable.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

702

I'm really happy one can add a local AA like this :)

754

Style: & in both above.

759

Nit: Is this necessary?

778

Nit: GetterRFI

780

We might want to "push" the information from setters instead. That would allow us to remove setters that are not useful, e.g. it is reset before it could have been read. We also need to look at other/implicit reads and writes later: https://godbolt.org/z/fdBqiF

I'm fine with starting here but let me know what you think about pushing instead?

785

Can we replace the pair with a struct that has proper member names and documentation.

820

Somehow broken.

828

Style: & and GetterRFI.

832

Make both conditionals early exits

llvm/test/Transforms/OpenMP/icv_tracking.ll

57 ↗

(On Diff #272562)

I thought this min was necessary but I doubt it reading the standard again. Maybe just remove the fixme

96 ↗

(On Diff #272562)

I guess this should be use(10) too, right? And tmp4 should be removed.

[sstefan1]

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

780

I guess we would first need to be aware of 'other' reads and writes, since without that information we could for example remove a setter that was supposed to be read.

I think we can do that with this approach as well. If the value wasn't read when we reach new setter, we mark the last one for removal? Not really sure if one is better than other.

820

The comment is broken?

832

I guess this makes sense now, but as we improve this, more conditionals will be added and it won't make sense to exit early.

llvm/test/Transforms/OpenMP/icv_tracking.ll

96 ↗

(On Diff #272562)

Yes, but only once we add callsite information. Right now we don't know if use might have set a new value.

[jdoerfert]

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

780

Both directions conceptually work. Let's wait and see. The correctness should never be compromised, I mean if you see something that you don't know you have to assume it reads and writes the ICV anyway.

820

Yes, a stray \p , right?

832

It depends. Having 3 early exists is, for me at least, nicer than one big condition.

llvm/test/Transforms/OpenMP/icv_tracking.ll

96 ↗

(On Diff #272562)

I see.

[sstefan1]

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

832

Just to make sure we're on the same page here. I'm not saying there will be one big condition. Rather, right now there is the case when both instructions are in the same BB. In the future we also want to cover the case when they are not. Does that make sense?

[sstefan1]

addressing comments

[jdoerfert]

Some nits to be addressed, otherwise LGTM.

Address the clang-tidy warnings where possible please.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

746

& and below. I assume you don't want to copy it all the time.

777

Note: Once we do proper optimistic initialization we need to compute the replacement value in the update. For now this is fine.

811

Nit: If you declare this as template<> struct DenseMapInfo<ICVValue> you don't need to specify it with the map later.

858

Wouldn't a const block do just fine below?

[lebedev.ri]

I've reverted this in rG1d542f0ca83fa1411d6501a8d088450d83abd5b8.

There appears to be some kind of memory corruption/use-after-free/etc
going on here. In particular, in OpenMPOpt::deleteParallelRegions(),
in DeleteCallCB(), CI is garbage.

Reduced reproducer: ./bin/opt -O3 /tmp/test.ll:

; ModuleID = '/home/lebedevri/CREDUCE/input.c'
source_filename = "/home/lebedevri/CREDUCE/input.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

%struct.ident_t = type { i32, i32, i32, i32, i8* }

@.str = private unnamed_addr constant [23 x i8] c";unknown;unknown;0;0;;\00", align 1
@0 = private unnamed_addr global %struct.ident_t { i32 0, i32 2, i32 0, i32 0, i8* getelementptr inbounds ([23 x i8], [23 x i8]* @.str, i32 0, i32 0) }, align 8

; Function Attrs: nounwind uwtable
define dso_local i32 @b() #0 {
  %1 = alloca i32, align 4
  %2 = call i32 @a()
  %3 = load i32, i32* %1, align 4
  ret i32 %3
}

; Function Attrs: nounwind uwtable
define internal i32 @a() #0 {
  %1 = alloca i32, align 4
  %2 = call i32 @b()
  call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* @0, i32 0, void (i32*, i32*, ...)* bitcast (void (i32*, i32*)* @.omp_outlined. to void (i32*, i32*, ...)*))
  %3 = load i32, i32* %1, align 4
  ret i32 %3
}

; Function Attrs: norecurse nounwind uwtable
define internal void @.omp_outlined.(i32* noalias %0, i32* noalias %1) #1 {
  %3 = alloca i32*, align 8
  %4 = alloca i32*, align 8
  store i32* %0, i32** %3, align 8, !tbaa !2
  store i32* %1, i32** %4, align 8, !tbaa !2
  ret void
}

; Function Attrs: nounwind
declare !callback !6 void @__kmpc_fork_call(%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) #2

attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #2 = { nounwind }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"Debian clang version 11.0.0-++20200709100646+c92a8c0a0f6-1~exp1~20200709201313.3348"}
!2 = !{!3, !3, i64 0}
!3 = !{!"any pointer", !4, i64 0}
!4 = !{!"omnipotent char", !5, i64 0}
!5 = !{!"Simple C/C++ TBAA"}
!6 = !{!7}
!7 = !{i64 2, i64 -1, i64 -1, i1 true}

[sstefan1]

fixing the issue with dead uses.

[jdoerfert]

Add the reproducer as test please. With that one and the change below, LGTM.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

188

-Size
+RFIs.size()

just add the function to the EnumeratedArray please.

[jdoerfert]

llvm/include/llvm/ADT/EnumeratedArray.h

41 ↗

(On Diff #277182)

Nit: const

llvm/include/llvm/Frontend/OpenMP/OMPConstants.h

 /// Make the enum values available in the llvm::omp namespace. This allows us to
 /// write something like OMPD_parallel if we have a `using namespace omp`. At
 /// the same time we do not loose the strong type guarantees of the enum class,
 /// that is we cannot pass an unsigned as Directive without an explicit cast.
 #define OMP_DIRECTIVE(Enum, ...) constexpr auto Enum = omp::Directive::Enum;
 #define OMP_CLAUSE(Enum, ...) constexpr auto Enum = omp::Clause::Enum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
 
+/// IDs for all Internal Control Variables (ICVs).
+enum class InternalControlVar {
+#define ICV_DATA_ENV(Enum, ...) Enum,
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+};
+
+#define ICV_DATA_ENV(Enum, ...)                                                \
+  constexpr auto Enum = omp::InternalControlVar::Enum;
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+
 /// IDs for all omp runtime library (RTL) functions.
 enum class RuntimeFunction {
 #define OMP_RTL(Enum, ...) Enum,
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
 };
 
 #define OMP_RTL(Enum, ...) constexpr auto Enum = omp::RuntimeFunction::Enum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"

llvm/include/llvm/Frontend/OpenMP/OMPKinds.def

 __OMP_FUNCTION_TYPE(TaskRoutineEntry, false, Int32, Int32,
                     /* kmp_task_t */ VoidPtr)
 
 #undef __OMP_FUNCTION_TYPE
 #undef OMP_FUNCTION_TYPE
 
 ///}
 
+/// Internal Control Variables information
+///
+///{
+
+#ifndef ICV_DATA_ENV
+#define ICV_DATA_ENV(Name, EnvVarName, Init)
+#endif
+
+#define __ICV_DATA_ENV(Name, EnvVarName, Init)                                 \
+  ICV_DATA_ENV(ICV_##Name, #EnvVarName, Init)
+
+__ICV_DATA_ENV(nthreads, OMP_NUM_THREADS, IMPLEMENTATION_DEFINED)
+__ICV_DATA_ENV(__last, last, LAST)
+
+#undef __ICV_DATA_ENV
+#undef ICV_DATA_ENV
+
+#ifndef ICV_RT_SET
+#define ICV_RT_SET(Name, RTL)
+#endif
+
+#define __ICV_RT_SET(Name, RTL) ICV_RT_SET(ICV_##Name, OMPRTL_##RTL)
+
+__ICV_RT_SET(nthreads, omp_set_num_threads)
+
+#undef __ICV_RT_SET
+#undef ICV_RT_SET
+
+#ifndef ICV_RT_GET
+#define ICV_RT_GET(Name, RTL)
+#endif
+
+#define __ICV_RT_GET(Name, RTL) ICV_RT_GET(ICV_##Name, OMPRTL_##RTL)
+
+__ICV_RT_GET(nthreads, omp_get_max_threads)
+
+#undef __ICV_RT_GET
+#undef ICV_RT_GET
+
+#ifndef ICV_CLAUSE
+#define ICV_CLAUSE(Name, Clause)
+#endif
+
+#define __ICV_ClAUSE(Name, Clause) ICV_CLAUSE(ICV_##Name, Clause)
+
+#undef __ICV_CLAUSE
+#undef ICV_CLAUSE
+
+// #ifndef ICV_VALUE_TYPE
+// #define ICV_VALUE_TYPE
+// #endif
+
+// #define __ICV_VALUE_TYPE(Name, Type) ICV_VALUE_TYPE(Name, Type)
+
+///}
+
 /// Runtime library function (and their attributes)
 ///
 ///{
 
 #ifndef OMP_RTL
 #define OMP_RTL(Enum, Str, IsVarArg, ReturnType, ...)
 #endif
 

llvm/include/llvm/Transforms/IPO/Attributor.h

 struct Attributor {
   /// Constructor
   ///
   /// \param Functions The set of functions we are deriving attributes for.
   /// \param InfoCache Cache to hold various information accessible for
   ///                  the abstract attributes.
   /// \param CGUpdater Helper to update an underlying call graph.
   /// \param Whitelist If not null, a set limiting the attribute opportunities.
-  Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
+  Attributor(SetVector<Function *> &Functions, InformationCache *InfoCache,
              CallGraphUpdater &CGUpdater,
              DenseSet<const char *> *Whitelist = nullptr)
-      : Allocator(InfoCache.Allocator), Functions(Functions),
+      : Allocator(InfoCache->Allocator), Functions(Functions),
         InfoCache(InfoCache), CGUpdater(CGUpdater), Whitelist(Whitelist) {}
 
   ~Attributor();
 
   /// Run the analyses until a fixpoint is reached or enforced (timeout).
   ///
   /// The attributes registered with this Attributor can be used after as long
   /// as the Attributor is not destroyed (it owns the attributes now).
   ///
   /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
struct Attributor {
   const AAType &getAndUpdateAAFor(const AbstractAttribute &QueryingAA,
                                   const IRPosition &IRP,
                                   bool TrackDependence = true,
                                   DepClassTy DepClass = DepClassTy::REQUIRED) {
     return getOrCreateAAFor<AAType>(IRP, &QueryingAA, TrackDependence, DepClass,
                                     /* ForceUpdate */ true);
   }
 
+  /// FIXME: should this be allowed to be public, or should there be another
+  //         way to create AA, outside of the Attributor, without the
+  //         QueryingAA?
+  /// The private version of getAAFor that allows to omit a querying abstract
+  /// attribute. See also the public getAAFor method.
+  template <typename AAType>
+  const AAType &getOrCreateAAFor(const IRPosition &IRP,
+                                 const AbstractAttribute *QueryingAA = nullptr,
+                                 bool TrackDependence = false,
+                                 DepClassTy DepClass = DepClassTy::OPTIONAL,
+                                 bool ForceUpdate = false) {
+    if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence)) {
+      if (ForceUpdate)
+        updateAA(*AAPtr);
+      return *AAPtr;
+    }
+
+    // No matching attribute found, create one.
+    // Use the static create method.
+    auto &AA = AAType::createForPosition(IRP, *this);
+    registerAA(AA);
+
+    // For now we ignore naked and optnone functions.
+    bool Invalidate = Whitelist && !Whitelist->count(&AAType::ID);
+    const Function *FnScope = IRP.getAnchorScope();
+    if (FnScope)
+      Invalidate |= FnScope->hasFnAttribute(Attribute::Naked) ||
+                    FnScope->hasFnAttribute(Attribute::OptimizeNone);
+
+    // Bootstrap the new attribute with an initial update to propagate
+    // information, e.g., function -> call site. If it is not on a given
+    // whitelist we will not perform updates at all.
+    if (Invalidate) {
+      AA.getState().indicatePessimisticFixpoint();
+      return AA;
+    }
+
+    AA.initialize(*this);
+
+    // We can initialize (=look at) code outside the current function set but
+    // not call update because that would again spawn new abstract attributes in
+    // potentially unconnected code regions (=SCCs).
+    if (FnScope && !Functions.count(const_cast<Function *>(FnScope))) {
+      AA.getState().indicatePessimisticFixpoint();
+      return AA;
+    }
+
+    updateAA(AA);
+
+    if (TrackDependence && AA.getState().isValidState())
+      recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
+                       DepClass);
+    return AA;
+  }
+
   /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
   /// \p FromAA changes \p ToAA should be updated as well.
   ///
   /// This method should be used in conjunction with the `getAAFor` method and
   /// with the TrackDependence flag passed to the method set to false. This can
   /// be beneficial to avoid false dependences but it requires the users of
   /// `getAAFor` to explicitly record true dependences through this method.
   /// The \p DepClass flag indicates if the dependence is striclty necessary.
template <typename AAType> AAType &registerAA(AAType &AA) {
     assert(!AAPtr && "Attribute already in map!");
     AAPtr = &AA;
 
     AllAbstractAttributes.push_back(&AA);
     return AA;
   }
 
   /// Return the internal information cache.
-  InformationCache &getInfoCache() { return InfoCache; }
+  InformationCache &getInfoCache() { return *InfoCache; }
 
   /// Return true if this is a module pass, false otherwise.
   bool isModulePass() const {
     return !Functions.empty() &&
            Functions.size() == Functions.front()->getParent()->size();
   }
 
   /// Return true if we derive attributes for \p Fn
struct Attributor {
   /// various places.
   void identifyDefaultAbstractAttributes(Function &F);
 
   /// Determine whether the function \p F is IPO amendable
   ///
   /// If a function is exactly defined or it has alwaysinline attribute
   /// and is viable to be inlined, we say it is IPO amendable
   bool isFunctionIPOAmendable(const Function &F) {
-    return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F);
+    return F.hasExactDefinition() || InfoCache->InlineableFunctions.count(&F);
   }
 
   /// Mark the internal function \p F as live.
   ///
   /// This will trigger the identification and initialization of attributes for
   /// \p F.
   void markLiveInternalFunction(const Function &F) {
     assert(F.hasLocalLinkage() &&
struct Attributor {
   ///
   /// This method will evaluate \p Pred on all instructions that read or write
   /// to memory present in the information cache and return true if \p Pred
   /// holds on all of them.
   bool checkForAllReadWriteInstructions(function_ref<bool(Instruction &)> Pred,
                                         AbstractAttribute &QueryingAA);
 
   /// Return the data layout associated with the anchor scope.
-  const DataLayout &getDataLayout() const { return InfoCache.DL; }
+  const DataLayout &getDataLayout() const { return InfoCache->DL; }
 
   /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
   BumpPtrAllocator &Allocator;
 
 private:
   /// Run `::update` on \p AA and track the dependences queried while doing so.
   /// Also adjust the state if we know further updates are not necessary.
   ChangeStatus updateAA(AbstractAttribute &AA);
private:
   /// all call sites are known, hence the function has internal linkage.
   /// If true is returned, \p AllCallSitesKnown is set if all possible call
   /// sites of the function have been visited.
   bool checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
                             const Function &Fn, bool RequireAllCallSites,
                             const AbstractAttribute *QueryingAA,
                             bool &AllCallSitesKnown);
 
-  /// The private version of getAAFor that allows to omit a querying abstract
-  /// attribute. See also the public getAAFor method.
-  template <typename AAType>
-  const AAType &getOrCreateAAFor(const IRPosition &IRP,
-                                 const AbstractAttribute *QueryingAA = nullptr,
-                                 bool TrackDependence = false,
-                                 DepClassTy DepClass = DepClassTy::OPTIONAL,
-                                 bool ForceUpdate = false) {
-    if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence)) {
-      if (ForceUpdate)
-        updateAA(*AAPtr);
-      return *AAPtr;
-    }
-
-    // No matching attribute found, create one.
-    // Use the static create method.
-    auto &AA = AAType::createForPosition(IRP, *this);
-    registerAA(AA);
-
-    // For now we ignore naked and optnone functions.
-    bool Invalidate = Whitelist && !Whitelist->count(&AAType::ID);
-    const Function *FnScope = IRP.getAnchorScope();
-    if (FnScope)
-      Invalidate |= FnScope->hasFnAttribute(Attribute::Naked) ||
-                    FnScope->hasFnAttribute(Attribute::OptimizeNone);
-
-    // Bootstrap the new attribute with an initial update to propagate
-    // information, e.g., function -> call site. If it is not on a given
-    // whitelist we will not perform updates at all.
-    if (Invalidate) {
-      AA.getState().indicatePessimisticFixpoint();
-      return AA;
-    }
-
-    AA.initialize(*this);
-
-    // We can initialize (=look at) code outside the current function set but
-    // not call update because that would again spawn new abstract attributes in
-    // potentially unconnected code regions (=SCCs).
-    if (FnScope && !Functions.count(const_cast<Function *>(FnScope))) {
-      AA.getState().indicatePessimisticFixpoint();
-      return AA;
-    }
-
-    updateAA(AA);
-
-    if (TrackDependence && AA.getState().isValidState())
-      recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
-                       DepClass);
-    return AA;
-  }
-
   /// Return the attribute of \p AAType for \p IRP if existing.
   template <typename AAType>
   AAType *lookupAAFor(const IRPosition &IRP,
                       const AbstractAttribute *QueryingAA = nullptr,
                       bool TrackDependence = false,
                       DepClassTy DepClass = DepClassTy::OPTIONAL) {
     static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
                   "Cannot query an attribute with a type not derived from "
private:
   /// Map to remember all requested signature changes (= argument replacements).
   DenseMap<Function *, SmallVector<std::unique_ptr<ArgumentReplacementInfo>, 8>>
       ArgumentReplacementMap;
 
   /// The set of functions we are deriving attributes for.
   SetVector<Function *> &Functions;
 
   /// The information cache that holds pre-processed (LLVM-IR) information.
-  InformationCache &InfoCache;
+  InformationCache *InfoCache;
 
   /// Helper to update an underlying call graph.
   CallGraphUpdater &CGUpdater;
 
   /// Set of functions for which we modified the content such that it might
   /// impact the call graph.
   SmallPtrSet<Function *, 8> CGModifiedFunctions;
 
if (RangeV.isEmptySet())
       return llvm::None;
     return nullptr;
   }
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
+/// An abstract interface for tracking OpenMp Internal Control Variables (ICVs).
+// struct AAICVTracker : public StateWrapper<BooleanState, AbstractAttribute> {
+// using Base = StateWrapper<BooleanState, AbstractAttribute>;
+// AAICVTracker(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
+
+// /// Returns true if value is assumed to be tracked.
+// bool isAssumedTracked() const { return getAssumed(); }
+
+// /// Returns true if value is known to be tracked.
+// bool isKnownTracked() const { return getKnown(); }
+
+// /// Create an abstract attribute view for the position \p IRP.
+// static AAICVTracker &createForPosition(const IRPosition &IRP, Attributor &A);
+
+// // Return the value with which /p I can be replaced.
+// virtual Value *getReplacementValue(const Instruction *I) = 0;
+
+// static const char ID;
+// };
+
 /// Run options, used by the pass manager.
 enum AttributorRunOption {
   NONE = 0,
   MODULE = 1 << 0,
   CGSCC = 1 << 1,
   ALL = MODULE | CGSCC
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

if (!AssociatedFunction)
     return false;
 
   // TODO: use the function scope once we have call site AAReturnedValues.
   const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
   const auto &LivenessAA =
       getAAFor<AAIsDead>(QueryingAA, QueryIRP, /* TrackDependence */ false);
 
   auto &OpcodeInstMap =
-      InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction);
+      InfoCache->getOpcodeInstMapForFunction(*AssociatedFunction);
   if (!checkForAllInstructionsImpl(this, OpcodeInstMap, Pred, &QueryingAA,
                                    &LivenessAA, Opcodes, CheckBBLivenessOnly))
     return false;
 
   return true;
 }
 
 bool Attributor::checkForAllReadWriteInstructions(
     function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA) {
 
   const Function *AssociatedFunction =
       QueryingAA.getIRPosition().getAssociatedFunction();
   if (!AssociatedFunction)
     return false;
 
   // TODO: use the function scope once we have call site AAReturnedValues.
   const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
   const auto &LivenessAA =
       getAAFor<AAIsDead>(QueryingAA, QueryIRP, /* TrackDependence */ false);
 
   for (Instruction *I :
-       InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) {
+       InfoCache->getReadOrWriteInstsForFunction(*AssociatedFunction)) {
     // Skip dead instructions.
     if (isAssumedDead(IRPosition::value(*I), &QueryingAA, &LivenessAA))
       continue;
 
     if (!Pred(*I))
       return false;
   }
 
bool Attributor::isValidFunctionSignatureRewrite(
   auto InstPred = [](Instruction &I) {
     if (auto *CI = dyn_cast<CallInst>(&I))
       return !CI->isMustTailCall();
     return true;
   };
 
   // Forbid must-tail calls for now.
   // TODO:
-  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*Fn);
+  auto &OpcodeInstMap = InfoCache->getOpcodeInstMapForFunction(*Fn);
   if (!checkForAllInstructionsImpl(nullptr, OpcodeInstMap, InstPred, nullptr,
                                    nullptr, {Instruction::Call})) {
     LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n");
     return false;
   }
 
   return true;
 }
void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   if (!VisitedFunctions.insert(&F).second)
     return;
   if (F.isDeclaration())
     return;
 
   // In non-module runs we need to look at the call sites of a function to
   // determine if it is part of a must-tail call edge. This will influence what
   // attributes we can derive.
-  InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(F);
+  InformationCache::FunctionInfo &FI = InfoCache->getFunctionInfo(F);
   if (!isModulePass() && !FI.CalledViaMustTail) {
     for (const Use &U : F.uses())
       if (const auto *CB = dyn_cast<CallBase>(U.getUser()))
         if (CB->isCallee(&U) && CB->isMustTailCall())
           FI.CalledViaMustTail = true;
   }
 
   IRPosition FPos = IRPosition::function(F);
for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) {
       getOrCreateAAFor<AAMemoryBehavior>(CBArgPos);
 
       // Call site argument attribute "nofree".
       getOrCreateAAFor<AANoFree>(CBArgPos);
     }
     return true;
   };
 
-  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
+  auto &OpcodeInstMap = InfoCache->getOpcodeInstMapForFunction(F);
   bool Success;
   Success = checkForAllInstructionsImpl(
       nullptr, OpcodeInstMap, CallSitePred, nullptr, nullptr,
       {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
        (unsigned)Instruction::Call});
   (void)Success;
   assert(Success && "Expected the check call to be successful!");
 
static bool runAttributorOnFunctions(InformationCache &InfoCache,
   if (Functions.empty())
     return false;
 
   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << Functions.size()
                     << " functions.\n");
 
   // Create an Attributor and initially empty information cache that is filled
   // while we identify default attribute opportunities.
-  Attributor A(Functions, InfoCache, CGUpdater);
+  Attributor A(Functions, &InfoCache, CGUpdater);
 
   // Create shallow wrappers for all functions that are not IPO amendable
   if (AllowShallowWrappers)
     for (Function *F : Functions)
       if (!A.isFunctionIPOAmendable(*F))
         createShallowWrapper(*F);
 
   for (Function *F : Functions) {

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Frontend/OpenMP/OMPConstants.h"
 #include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/IPO/Attributor.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
 using namespace llvm;
 using namespace omp;
 using namespace types;
 
 #define DEBUG_TYPE "openmp-opt"
 

 STATISTIC(NumOpenMPRuntimeFunctionUsesIdentified,
           "Number of OpenMP runtime function uses identified");
 
 #if !defined(NDEBUG)
 static constexpr auto TAG = "[" DEBUG_TYPE "]";
 #endif
 
 namespace {
-struct OpenMPOpt {
 
-  using OptimizationRemarkGetter =
-      function_ref<OptimizationRemarkEmitter &(Function *)>;
+// FIXME: Put in Attributor.h or keep this?
+struct AAICVTracker;
 
-  OpenMPOpt(SmallVectorImpl<Function *> &SCC,
-            SmallPtrSetImpl<Function *> &ModuleSlice,
-            CallGraphUpdater &CGUpdater, OptimizationRemarkGetter OREGetter)
-      : M(*(*SCC.begin())->getParent()), SCC(SCC), ModuleSlice(ModuleSlice),
-        OMPBuilder(M), CGUpdater(CGUpdater), OREGetter(OREGetter) {
+/// OpenMP specific information. For now, stores RFIs and ICVs also needed for
+/// Attributor runs.
+/// FIXME: Maybe put this in a header file?
+struct OMPInformationCache : public InformationCache {
+  OMPInformationCache(Module &M, AnalysisGetter &AG,
+                      BumpPtrAllocator &Allocator, SetVector<Function *> *CGSCC,
+                      SmallPtrSetImpl<Function *> &ModuleSlice)
+      : InformationCache(M, AG, Allocator, CGSCC), ModuleSlice(ModuleSlice),
+        OMPBuilder(M) {
     initializeTypes(M);
     initializeRuntimeFunctions();
+    initializeInternalControlVars();
+
     OMPBuilder.initialize();
   }
 
+  /// Generic information that describes an internal control variable.
+  struct InternalControlVarInfo {
+    /// The kind, as described by InternalControlVar enum.
+    InternalControlVar Kind;
+
+    /// Environment variable associated with this ICV.
+    StringRef EnvVarName;
+
+    /// Setter RTL function associated with this ICV.
+    RuntimeFunction Setter;
+
+    /// Getter RTL function associated with this ICV.
+    RuntimeFunction Getter;
+
+    /// RTL Function corresponding to the override clause of this ICV
+    RuntimeFunction Clause;
+
+    /// TODO: define these.
+    /// Type of the ICV.
+    // Type *ValueType;
+    //
+    /// Initial Value
+
+    /// Scope.
+  };
+
   /// Generic information that describes a runtime function
   struct RuntimeFunctionInfo {
 
     /// The kind, as described by the RuntimeFunction enum.
     RuntimeFunction Kind;
 
     /// The name of the function.
     StringRef Name;
struct RuntimeFunctionInfo {
     /// The declaration if available.
     Function *Declaration = nullptr;
 
     /// Uses of this runtime function per function containing the use.
     using UseVector = SmallVector<Use *, 16>;
 
     /// Return the vector of uses in function \p F.
     UseVector &getOrCreateUseVector(Function *F) {
-      std::unique_ptr<UseVector> &UV = UsesMap[F];
+      std::shared_ptr<UseVector> &UV = UsesMap[F];
       if (!UV)
-        UV = std::make_unique<UseVector>();
+        UV = std::make_shared<UseVector>();
       return *UV;
     }
 
     /// Return the vector of uses in function \p F or `nullptr` if there are
     /// none.
     const UseVector *getUseVector(Function &F) const {
       auto I = UsesMap.find(&F);
       if (I != UsesMap.end())
         return I->second.get();
       return nullptr;
     }
 
     /// Return how many functions contain uses of this runtime function.
     size_t getNumFunctionsWithUses() const { return UsesMap.size(); }
 
     /// Return the number of arguments (or the minimal number for variadic
     /// functions).
     size_t getNumArgs() const { return ArgumentTypes.size(); }
 
-    /// Run the callback \p CB on each use and forget the use if the result is
-    /// true. The callback will be fed the function in which the use was
-    /// encountered as second argument.
     void foreachUse(function_ref<bool(Use &, Function &)> CB) {
+      for (auto &It : UsesMap)
+        foreachUse(CB, It.first, It.second.get());
+    }
+
+    void foreachUse(function_ref<bool(Use &, Function &)> CB, Function *F,
+                    UseVector *Uses = nullptr) {
       SmallVector<unsigned, 8> ToBeDeleted;
-      for (auto &It : UsesMap) {
-        ToBeDeleted.clear();
-        unsigned Idx = 0;
-        UseVector &UV = *It.second;
-        for (Use *U : UV) {
-          if (CB(*U, *It.first))
-            ToBeDeleted.push_back(Idx);
-          ++Idx;
-        }
+      UseVector &UV = Uses ? *Uses : getOrCreateUseVector(F);
+
+        if (CB(*U, *F))
 
-        // Remove the to-be-deleted indices in reverse order as prior
-        // modifcations will not modify the smaller indices.
-        while (!ToBeDeleted.empty()) {
-          unsigned Idx = ToBeDeleted.pop_back_val();
-          UV[Idx] = UV.back();
-          UV.pop_back();
-        }
-      }
-    }
 
   private:
     /// Map from functions to all uses of this runtime function contained in
     /// them.
-    DenseMap<Function *, std::unique_ptr<UseVector>> UsesMap;
+    DenseMap<Function *, std::shared_ptr<UseVector>> UsesMap;
+  };
+
+  /// The slice of the module we are allowed to look at.
+  SmallPtrSetImpl<Function *> &ModuleSlice;
+
+  /// An OpenMP-IR-Builder instance
+  OpenMPIRBuilder OMPBuilder;
+
+  /// Map from runtime function kind to the runtime function description.
+  EnumeratedArray<RuntimeFunctionInfo, RuntimeFunction,
+                  RuntimeFunction::OMPRTL___last>
+      RFIs;
+
+  /// Map from ICV kind to the ICV description.
+  EnumeratedArray<InternalControlVarInfo, InternalControlVar,
+                  InternalControlVar::ICV___last>
+      ICVs;
+
+  /// Helper to initialize all internal control variable information for those
+  /// defined in OMPKinds.def.
+  void initializeInternalControlVars() {
+#define ICV_RT_SET(_Name, RTL)                                                 \
+  {                                                                            \
+    auto &ICV = ICVs[_Name];                                                   \
+    ICV.Setter = RTL;                                                          \
+  }
+#define ICV_RT_GET(Name, RTL)                                                  \
+  {                                                                            \
+    auto &ICV = ICVs[Name];                                                    \
+    ICV.Getter = RTL;                                                          \
+  }
+#define ICV_DATA_ENV(Name, _EnvVarName, Init)                                  \
+  {                                                                            \
+    auto &ICV = ICVs[Name];                                                    \
+    ICV.Kind = Name;                                                           \
+    ICV.EnvVarName = _EnvVarName;                                              \
+  }
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+  }
+
+  /// Returns true if the function declaration \p F matches the runtime
+  /// function types, that is, return type \p RTFRetType, and argument types
+  /// \p RTFArgTypes.
+  static bool declMatchesRTFTypes(Function *F, Type *RTFRetType,
+                                  SmallVector<Type *, 8> &RTFArgTypes) {
+    // TODO: We should output information to the user (under debug output
+    //       and via remarks).
+
+    if (!F)
+      return false;
+    if (F->getReturnType() != RTFRetType)
+      return false;
+    if (F->arg_size() != RTFArgTypes.size())
+      return false;
+
+    auto RTFTyIt = RTFArgTypes.begin();
+    for (Argument &Arg : F->args()) {
+      if (Arg.getType() != *RTFTyIt)
+        return false;
+
+      ++RTFTyIt;
+    }
+
+    return true;
+  }
+
+  /// Helper to initialize all runtime function information for those defined
+  /// in OpenMPKinds.def.
+  void initializeRuntimeFunctions() {
+    // Helper to collect all uses of the decleration in the UsesMap.
+    auto CollectUses = [&](RuntimeFunctionInfo &RFI) {
+      unsigned NumUses = 0;
+      if (!RFI.Declaration)
+        return NumUses;
+      OMPBuilder.addAttributes(RFI.Kind, *RFI.Declaration);
+
+      NumOpenMPRuntimeFunctionsIdentified += 1;
+      NumOpenMPRuntimeFunctionUsesIdentified += RFI.Declaration->getNumUses();
+
+      // TODO: We directly convert uses into proper calls and unknown uses.
+      for (Use &U : RFI.Declaration->uses()) {
+        if (Instruction *UserI = dyn_cast<Instruction>(U.getUser())) {
+          if (ModuleSlice.count(UserI->getFunction())) {
+            RFI.getOrCreateUseVector(UserI->getFunction()).push_back(&U);
+            ++NumUses;
+          }
+        } else {
+          RFI.getOrCreateUseVector(nullptr).push_back(&U);
+          ++NumUses;
+        }
+      }
+      return NumUses;
     };
 
+    Module &M = *((*ModuleSlice.begin())->getParent());
+
+#define OMP_RTL(_Enum, _Name, _IsVarArg, _ReturnType, ...)                     \
+  {                                                                            \
+    SmallVector<Type *, 8> ArgsTypes({__VA_ARGS__});                           \
+    Function *F = M.getFunction(_Name);                                        \
+    if (declMatchesRTFTypes(F, _ReturnType, ArgsTypes)) {                      \
+      auto &RFI = RFIs[_Enum];                                                 \
+      RFI.Kind = _Enum;                                                        \
+      RFI.Name = _Name;                                                        \
+      RFI.IsVarArg = _IsVarArg;                                                \
+      RFI.ReturnType = _ReturnType;                                            \
+      RFI.ArgumentTypes = std::move(ArgsTypes);                                \
+      RFI.Declaration = F;                                                     \
+      unsigned NumUses = CollectUses(RFI);                                     \
+      (void)NumUses;                                                           \
+      LLVM_DEBUG({                                                             \
+        dbgs() << TAG << RFI.Name << (RFI.Declaration ? "" : " not")           \
+               << " found\n";                                                  \
+        if (RFI.Declaration)                                                   \
+          dbgs() << TAG << "-> got " << NumUses << " uses in "                 \
+                 << RFI.getNumFunctionsWithUses()                              \
+                 << " different functions.\n";                                 \
+      });                                                                      \
+    }                                                                          \
+  }
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+
+    // TODO: We should attach the attributes defined in OMPKinds.def.
+  }
+};
+
+struct OpenMPOpt {
+
+  using OptimizationRemarkGetter =
+      function_ref<OptimizationRemarkEmitter &(Function *)>;
+
+  OpenMPOpt(SmallVectorImpl<Function *> &SCC, CallGraphUpdater &CGUpdater,
+            OptimizationRemarkGetter OREGetter,
+            OMPInformationCache *OMPInfoCache)
+      : M(*(*SCC.begin())->getParent()), SCC(SCC),
+        ModuleSlice(OMPInfoCache->ModuleSlice), CGUpdater(CGUpdater),
+        OREGetter(OREGetter), OMPInfoCache(OMPInfoCache) {}
+
   /// Run all OpenMP optimizations on the underlying SCC/ModuleSlice.
   bool run() {
     bool Changed = false;
 
     LLVM_DEBUG(dbgs() << TAG << "Run on SCC with " << SCC.size()
                       << " functions in a slice with " << ModuleSlice.size()
                       << " functions\n");
 
+    Changed |= runAttributor();
+
+    // Initialize custom attribute set.
     Changed |= deduplicateRuntimeCalls();
     Changed |= deleteParallelRegions();
 
     return Changed;
   }
 
+  /// Return the call if \p U is a callee use in a regular call. If \p RFI is
+  /// given it has to be the callee or a nullptr is returned.
+  static CallInst *getCallIfRegularCall(
+      Use &U, OMPInformationCache::RuntimeFunctionInfo *RFI = nullptr) {
+    CallInst *CI = dyn_cast<CallInst>(U.getUser());
+    if (CI && CI->isCallee(&U) && !CI->hasOperandBundles() &&
+        (!RFI || CI->getCalledFunction() == RFI->Declaration))
+      return CI;
+    return nullptr;
+  }
+
+  /// Return the call if \p V is a regular call. If \p RFI is given it has to be
+  /// the callee or a nullptr is returned.
+  static CallInst *getCallIfRegularCall(
+      Value &V, OMPInformationCache::RuntimeFunctionInfo *RFI = nullptr) {
+    CallInst *CI = dyn_cast<CallInst>(&V);
+    if (CI && !CI->hasOperandBundles() &&
+        (!RFI || CI->getCalledFunction() == RFI->Declaration))
+      return CI;
+    return nullptr;
+  }
+
 private:
   /// Try to delete parallel regions if possible.
   bool deleteParallelRegions() {
     const unsigned CallbackCalleeOperand = 2;
 
-    RuntimeFunctionInfo &RFI = RFIs[OMPRTL___kmpc_fork_call];
+    OMPInformationCache::RuntimeFunctionInfo &RFI =
+        OMPInfoCache->RFIs[OMPRTL___kmpc_fork_call];
+
     if (!RFI.Declaration)
       return false;
 
     bool Changed = false;
     auto DeleteCallCB = [&](Use &U, Function &) {
       CallInst *CI = getCallIfRegularCall(U);
       if (!CI)
         return false;
bool deduplicateRuntimeCalls() {
     // Global-tid is handled separately.
     SmallSetVector<Value *, 16> GTIdArgs;
     collectGlobalThreadIdArguments(GTIdArgs);
     LLVM_DEBUG(dbgs() << TAG << "Found " << GTIdArgs.size()
                       << " global thread ID arguments\n");
 
     for (Function *F : SCC) {
       for (auto DeduplicableRuntimeCallID : DeduplicableRuntimeCallIDs)
-        deduplicateRuntimeCalls(*F, RFIs[DeduplicableRuntimeCallID]);
+        deduplicateRuntimeCalls(*F,
+                                OMPInfoCache->RFIs[DeduplicableRuntimeCallID]);
 
       // __kmpc_global_thread_num is special as we can replace it with an
       // argument in enough cases to make it worth trying.
       Value *GTIdArg = nullptr;
       for (Argument &Arg : F->args())
         if (GTIdArgs.count(&Arg)) {
           GTIdArg = &Arg;
           break;
         }
       Changed |= deduplicateRuntimeCalls(
-          *F, RFIs[OMPRTL___kmpc_global_thread_num], GTIdArg);
+          *F, OMPInfoCache->RFIs[OMPRTL___kmpc_global_thread_num], GTIdArg);
     }
 
     return Changed;
   }
 
   static Value *combinedIdentStruct(Value *CurrentIdent, Value *NextIdent,
                                     bool GlobalOnly, bool &SingleChoice) {
     if (CurrentIdent == NextIdent)
       return CurrentIdent;
 
     // TODO: Figure out how to actually combine multiple debug locations. For
     //       now we just keep an existing one if there is a single choice.
     if (!GlobalOnly || isa<GlobalValue>(NextIdent)) {
       SingleChoice = !CurrentIdent;
       return NextIdent;
     }
     return nullptr;
   }
 
   /// Return an `struct ident_t*` value that represents the ones used in the
   /// calls of \p RFI inside of \p F. If \p GlobalOnly is true, we will not
   /// return a local `struct ident_t*`. For now, if we cannot find a suitable
   /// return value we create one from scratch. We also do not yet combine
   /// information, e.g., the source locations, see combinedIdentStruct.
-  Value *getCombinedIdentFromCallUsesIn(RuntimeFunctionInfo &RFI, Function &F,
-                                        bool GlobalOnly) {
+  Value *
+  getCombinedIdentFromCallUsesIn(OMPInformationCache::RuntimeFunctionInfo &RFI,
+                                 Function &F, bool GlobalOnly) {
     bool SingleChoice = true;
     Value *Ident = nullptr;
     auto CombineIdentStruct = [&](Use &U, Function &Caller) {
       CallInst *CI = getCallIfRegularCall(U, &RFI);
       if (!CI || &F != &Caller)
         return false;
       Ident = combinedIdentStruct(Ident, CI->getArgOperand(0),
                                   /* GlobalOnly */ true, SingleChoice);
       return false;
     };
     RFI.foreachUse(CombineIdentStruct);
 
     if (!Ident || !SingleChoice) {
       // The IRBuilder uses the insertion block to get to the module, this is
       // unfortunate but we work around it for now.
-      if (!OMPBuilder.getInsertionPoint().getBlock())
-        OMPBuilder.updateToLocation(OpenMPIRBuilder::InsertPointTy(
-            &F.getEntryBlock(), F.getEntryBlock().begin()));
+      if (!OMPInfoCache->OMPBuilder.getInsertionPoint().getBlock())
+        OMPInfoCache->OMPBuilder.updateToLocation(
+            OpenMPIRBuilder::InsertPointTy(&F.getEntryBlock(),
+                                           F.getEntryBlock().begin()));
       // Create a fallback location if non was found.
       // TODO: Use the debug locations of the calls instead.
-      Constant *Loc = OMPBuilder.getOrCreateDefaultSrcLocStr();
-      Ident = OMPBuilder.getOrCreateIdent(Loc);
+      Constant *Loc = OMPInfoCache->OMPBuilder.getOrCreateDefaultSrcLocStr();
+      Ident = OMPInfoCache->OMPBuilder.getOrCreateIdent(Loc);
     }
     return Ident;
   }
 
   /// Try to eliminiate calls of \p RFI in \p F by reusing an existing one or
   /// \p ReplVal if given.
-  bool deduplicateRuntimeCalls(Function &F, RuntimeFunctionInfo &RFI,
+  bool deduplicateRuntimeCalls(Function &F,
+                               OMPInformationCache::RuntimeFunctionInfo &RFI,
                                Value *ReplVal = nullptr) {
     auto *UV = RFI.getUseVector(F);
     if (!UV || UV->size() + (ReplVal != nullptr) < 2)
       return false;
 
-    LLVM_DEBUG(dbgs() << TAG << "Deduplicate " << UV->size() << " uses of "
-                      << RFI.Name
-                      << (ReplVal ? " with an existing value\n" : "\n")
-                      << "\n");
+    LLVM_DEBUG(
+        dbgs() << TAG << "Deduplicate " << UV->size() << " uses of " << RFI.Name
+               << (ReplVal ? " with an existing value\n" : "\n") << "\n");
     assert((!ReplVal || (isa<Argument>(ReplVal) &&
                          cast<Argument>(ReplVal)->getParent() == &F)) &&
            "Unexpected replacement value!");
 
     // TODO: Use dominance to find a good position instead.
     auto CanBeMoved = [](CallBase &CB) {
       unsigned NumArgs = CB.getNumArgOperands();
       if (NumArgs == 0)
void collectGlobalThreadIdArguments(SmallSetVector<Value *, 16> &GTIdArgs) {
     // a GTId.
     auto CallArgOpIsGTId = [&](Function &F, unsigned ArgNo, CallInst &RefCI) {
       if (!F.hasLocalLinkage())
         return false;
       for (Use &U : F.uses()) {
         if (CallInst *CI = getCallIfRegularCall(U)) {
           Value *ArgOp = CI->getArgOperand(ArgNo);
           if (CI == &RefCI || GTIdArgs.count(ArgOp) ||
-              getCallIfRegularCall(*ArgOp,
-                                   &RFIs[OMPRTL___kmpc_global_thread_num]))
+              getCallIfRegularCall(
+                  *ArgOp, &OMPInfoCache->RFIs[OMPRTL___kmpc_global_thread_num]))
             continue;
         }
         return false;
       }
       return true;
     };
 
     // Helper to identify uses of a GTId as GTId arguments.
     auto AddUserArgs = [&](Value &GTId) {
       for (Use &U : GTId.uses())
         if (CallInst *CI = dyn_cast<CallInst>(U.getUser()))
           if (CI->isArgOperand(&U))
             if (Function *Callee = CI->getCalledFunction())
               if (CallArgOpIsGTId(*Callee, U.getOperandNo(), *CI))
                 GTIdArgs.insert(Callee->getArg(U.getOperandNo()));
     };
 
     // The argument users of __kmpc_global_thread_num calls are GTIds.
-    RuntimeFunctionInfo &GlobThreadNumRFI =
-        RFIs[OMPRTL___kmpc_global_thread_num];
+    OMPInformationCache::RuntimeFunctionInfo &GlobThreadNumRFI =
+        OMPInfoCache->RFIs[OMPRTL___kmpc_global_thread_num];
+
     GlobThreadNumRFI.foreachUse([&](Use &U, Function &F) {
       if (CallInst *CI = getCallIfRegularCall(U, &GlobThreadNumRFI))
         AddUserArgs(*CI);
       return false;
     });
 
     // Transitively search for more arguments by looking at the users of the
     // ones we know already. During the search the GTIdArgs vector is extended
     // so we cannot cache the size nor can we use a range based for.
     for (unsigned u = 0; u < GTIdArgs.size(); ++u)
       AddUserArgs(*GTIdArgs[u]);
   }
 
-  /// Return the call if \p U is a callee use in a regular call. If \p RFI is
-  /// given it has to be the callee or a nullptr is returned.
-  CallInst *getCallIfRegularCall(Use &U, RuntimeFunctionInfo *RFI = nullptr) {
-    CallInst *CI = dyn_cast<CallInst>(U.getUser());
-    if (CI && CI->isCallee(&U) && !CI->hasOperandBundles() &&
-        (!RFI || CI->getCalledFunction() == RFI->Declaration))
-      return CI;
-    return nullptr;
-  }
-
-  /// Return the call if \p V is a regular call. If \p RFI is given it has to be
-  /// the callee or a nullptr is returned.
-  CallInst *getCallIfRegularCall(Value &V, RuntimeFunctionInfo *RFI = nullptr) {
-    CallInst *CI = dyn_cast<CallInst>(&V);
-    if (CI && !CI->hasOperandBundles() &&
-        (!RFI || CI->getCalledFunction() == RFI->Declaration))
-      return CI;
-    return nullptr;
-  }
-
-  /// Returns true if the function declaration \p F matches the runtime
-  /// function types, that is, return type \p RTFRetType, and argument types
-  /// \p RTFArgTypes.
-  static bool declMatchesRTFTypes(Function *F, Type *RTFRetType,
-                                  SmallVector<Type *, 8> &RTFArgTypes) {
-    // TODO: We should output information to the user (under debug output
-    //       and via remarks).
-
-    if (!F)
-      return false;
-    if (F->getReturnType() != RTFRetType)
-      return false;
-    if (F->arg_size() != RTFArgTypes.size())
-      return false;
-
-    auto RTFTyIt = RTFArgTypes.begin();
-    for (Argument &Arg : F->args()) {
-      if (Arg.getType() != *RTFTyIt)
-        return false;
-
-      ++RTFTyIt;
-    }
-
-    return true;
-  }
-
-  /// Helper to initialize all runtime function information for those defined in
-  /// OpenMPKinds.def.
-  void initializeRuntimeFunctions() {
-    // Helper to collect all uses of the decleration in the UsesMap.
-    auto CollectUses = [&](RuntimeFunctionInfo &RFI) {
-      unsigned NumUses = 0;
-      if (!RFI.Declaration)
-        return NumUses;
-      OMPBuilder.addAttributes(RFI.Kind, *RFI.Declaration);
-
-      NumOpenMPRuntimeFunctionsIdentified += 1;
-      NumOpenMPRuntimeFunctionUsesIdentified += RFI.Declaration->getNumUses();
-
-      // TODO: We directly convert uses into proper calls and unknown uses.
-      for (Use &U : RFI.Declaration->uses()) {
-        if (Instruction *UserI = dyn_cast<Instruction>(U.getUser())) {
-          if (ModuleSlice.count(UserI->getFunction())) {
-            RFI.getOrCreateUseVector(UserI->getFunction()).push_back(&U);
-            ++NumUses;
-          }
-        } else {
-          RFI.getOrCreateUseVector(nullptr).push_back(&U);
-          ++NumUses;
-        }
-      }
-      return NumUses;
-    };
-
-#define OMP_RTL(_Enum, _Name, _IsVarArg, _ReturnType, ...)                     \
-  {                                                                            \
-    SmallVector<Type *, 8> ArgsTypes({__VA_ARGS__});                           \
-    Function *F = M.getFunction(_Name);                                        \
-    if (declMatchesRTFTypes(F, _ReturnType, ArgsTypes)) {                      \
-      auto &RFI = RFIs[_Enum];                                                 \
-      RFI.Kind = _Enum;                                                        \
-      RFI.Name = _Name;                                                        \
-      RFI.IsVarArg = _IsVarArg;                                                \
-      RFI.ReturnType = _ReturnType;                                            \
-      RFI.ArgumentTypes = std::move(ArgsTypes);                                \
-      RFI.Declaration = F;                                                     \
-      unsigned NumUses = CollectUses(RFI);                                     \
-      (void)NumUses;                                                           \
-      LLVM_DEBUG({                                                             \
-        dbgs() << TAG << RFI.Name << (RFI.Declaration ? "" : " not")           \
-               << " found\n";                                                  \
-        if (RFI.Declaration)                                                   \
-          dbgs() << TAG << "-> got " << NumUses << " uses in "                 \
-                 << RFI.getNumFunctionsWithUses()                              \
-                 << " different functions.\n";                                 \
-      });                                                                      \
-    }                                                                          \
-  }
-#include "llvm/Frontend/OpenMP/OMPKinds.def"
-
-    // TODO: We should attach the attributes defined in OMPKinds.def.
-  }
-
   /// Emit a remark generically
   ///
   /// This template function can be used to generically emit a remark. The
   /// RemarkKind should be one of the following:
   ///   - OptimizationRemark to indicate a successful optimization attempt
   ///   - OptimizationRemarkMissed to report a failed optimization attempt
   ///   - OptimizationRemarkAnalysis to provide additional information about an
   ///     optimization attempt
   ///
   /// The remark is built using a callback function provided by the caller that
   /// takes a RemarkKind as input and returns a RemarkKind.
   template <typename RemarkKind,
             typename RemarkCallBack = function_ref<RemarkKind(RemarkKind &&)>>
   void emitRemark(Instruction *Inst, StringRef RemarkName,
                   RemarkCallBack &&RemarkCB) {
     Function *F = Inst->getParent()->getParent();
     auto &ORE = OREGetter(F);
 
-    ORE.emit([&]() {
-      return RemarkCB(RemarkKind(DEBUG_TYPE, RemarkName, Inst));
-    });
+    ORE.emit(
+        [&]() { return RemarkCB(RemarkKind(DEBUG_TYPE, RemarkName, Inst)); });
   }
 
   /// The underyling module.
   Module &M;
 
   /// The SCC we are operating on.
   SmallVectorImpl<Function *> &SCC;
 
   /// The slice of the module we are allowed to look at.
   SmallPtrSetImpl<Function *> &ModuleSlice;
 
   /// An OpenMP-IR-Builder instance
-  OpenMPIRBuilder OMPBuilder;
+  // OpenMPIRBuilder OMPBuilder;
 
   /// Callback to update the call graph, the first argument is a removed call,
   /// the second an optional replacement call.
   CallGraphUpdater &CGUpdater;
 
   /// Callback to get an OptimizationRemarkEmitter from a Function *
   OptimizationRemarkGetter OREGetter;
 
-  /// Map from runtime function kind to the runtime function description.
-  EnumeratedArray<RuntimeFunctionInfo, RuntimeFunction,
-                  RuntimeFunction::OMPRTL___last>
-      RFIs;
+  /// OpenMP-specific information cache. Also used for Attributor runs.
+  OMPInformationCache *OMPInfoCache;
+
+  bool runAttributor() {
+    if (SCC.empty())
+      return false;
+
+    // TODO: Expose runAttributorOnFunctions() or have an Attributor instance?
+
+    // TODO: WhiteList some attributes? AAIsDead?
+
+    SetVector<Function *> Functions(SCC.begin(), SCC.end());
+
+    // Create an Attributor with openmp-specific infocache
+    Attributor A(Functions, OMPInfoCache, CGUpdater);
+
+    registerAAs(A, Functions);
+
+    ChangeStatus Changed = A.run();
+
+    LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
+                      << " functions, result: " << Changed << ".\n");
+
+    return Changed == ChangeStatus::CHANGED;
+  }
+
+  void registerAAs(Attributor &A, SetVector<Function *> Functions) {
+    for (Function *F : Functions) {
+      if (F->isDeclaration())
+        continue;
+
+      A.getOrCreateAAFor<AAICVTracker>(IRPosition::function(*F));
+    }
+  }
+};
+
+struct AAICVTracker : public StateWrapper<BooleanState, AbstractAttribute> {
+  using Base = StateWrapper<BooleanState, AbstractAttribute>;
+  AAICVTracker(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
+
+  /// Returns true if value is assumed to be tracked.
+  bool isAssumedTracked() const { return getAssumed(); }
+
+  /// Returns true if value is known to be tracked.
+  bool isKnownTracked() const { return getAssumed(); }
+
+  /// TODO: figure out how to get hold of ICV infos here.
+  /// Create an abstract attribute biew for the position \p IRP.
+  static AAICVTracker &createForPosition(const IRPosition &IRP, Attributor &A);
+
+  // virtual Value *getReplacementValue(const Instruction *I) = 0;
+  virtual Value *getReplacementValue(InternalControlVar ICV,
+                                     const Instruction *I) = 0;
+
+  static const char ID;
+};
+
+struct AAICVTrackerFunction : public AAICVTracker {
+  AAICVTrackerFunction(const IRPosition &IRP, Attributor &A)
+      : AAICVTracker(IRP, A) {}
+
+  // FIXME: come up with better string.
+  const std::string getAsStr() const override { return "ICVTracker"; }
+
+  // FIXME: come up with some stats.
+  void trackStatistics() const override {}
+
+  // void initialize(Attributor &A) override {
+  // Instruction *Entry = &(getAnchorScope()->getEntryBlock().front());
+
+  // /// Implementation defined value.
+  // ICVValuesMap[Entry] = nullptr;
+  // }
+
+  /// TODO: decide whether to deduplicate here, or use current
+  /// deduplicateRuntimeCalls function.
+  ChangeStatus manifest(Attributor &A) override {
+    return ChangeStatus::UNCHANGED;
+  }
+
+  // Map of ICV to their values at specific program point.
+  EnumeratedArray<SmallSetVector<std::pair<Instruction *, Value *>, 4>,
+                  InternalControlVar, InternalControlVar::ICV___last>
+      ICVValuesMap;
+
+  ChangeStatus updateImpl(Attributor &A) override {
+    ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
+    InternalControlVar TrackableICVs[] = {
+        // Currently only nthreads is being tracked
+        ICV_nthreads};
+
+    Function *F = getAnchorScope();
+
+    auto OMPInfoCache = static_cast<OMPInformationCache *>(&(A.getInfoCache()));
+
+    for (InternalControlVar ICV : TrackableICVs) {
+      auto Setter = OMPInfoCache->RFIs[OMPInfoCache->ICVs[ICV].Setter];
+
+      auto TrackValues = [&](Use &U, Function &) {
+        CallInst *CI = OpenMPOpt::getCallIfRegularCall(U);
+        if (!CI)
+          return false;
+
+        // FIXME: handle setters with more that 1 arguments.
+        /// Track new value.
+        if (ICVValuesMap[ICV].insert(std::make_pair(CI, CI->getArgOperand(0))))
+          HasChanged = ChangeStatus::CHANGED;
+
+        return false;
+      };
+
+      Setter.foreachUse(TrackValues, F);
+    }
+
+    return HasChanged;
+  }
+
+  /// Return the value with which \p can be replaced.
+  Value *getReplacementValue(InternalControlVar ICV,
+                             const Instruction *I) override {
+    BasicBlock *CurrBB = const_cast<BasicBlock *>(I->getParent());
+
+    auto ValuesSet = ICVValuesMap[ICV];
+
+    for (auto &pair : ValuesSet)
+      if (CurrBB == pair.first->getParent())
+        if (pair.first->comesBefore(I))
+          // both instructions are in the same BB and at \p I we know the ICV
+          // value.
+          return pair.second;
+
+    // first predecessor that contains one of the tracked instructions
+    // contains the tracked value.
+    for (BasicBlock *Pred : predecessors(CurrBB))
+      for (auto pair : ValuesSet)
+        if (pair.first->getParent() == Pred)
+          return pair.second;
+
+    // No value was tracked.
+    return nullptr;
+  }
 };
 } // namespace
 
+const char AAICVTracker::ID = 0;
+
+AAICVTracker &AAICVTracker::createForPosition(const IRPosition &IRP,
+                                              Attributor &A) {
+  AAICVTracker *AA = nullptr;
+  switch (IRP.getPositionKind()) {
+  case IRPosition::IRP_INVALID:
+  case IRPosition::IRP_FLOAT:
+  case IRPosition::IRP_ARGUMENT:
+  case IRPosition::IRP_RETURNED:
+  case IRPosition::IRP_CALL_SITE_RETURNED:
+  case IRPosition::IRP_CALL_SITE_ARGUMENT:
+  case IRPosition::IRP_CALL_SITE:
+    llvm_unreachable("ICVTracker can only be created for function position!");
+  case IRPosition::IRP_FUNCTION:
+    AA = new (A.Allocator) AAICVTrackerFunction(IRP, A);
+    break;
+  }
+
+  return *AA;
+}
+
 PreservedAnalyses OpenMPOptPass::run(LazyCallGraph::SCC &C,
                                      CGSCCAnalysisManager &AM,
                                      LazyCallGraph &CG, CGSCCUpdateResult &UR) {
   if (!containsOpenMP(*C.begin()->getFunction().getParent(), OMPInModule))
     return PreservedAnalyses::all();
 
   if (DisableOpenMPOptimizations)
     return PreservedAnalyses::all();
 
   SmallPtrSet<Function *, 16> ModuleSlice;
   SmallVector<Function *, 16> SCC;
   for (LazyCallGraph::Node &N : C) {
     SCC.push_back(&N.getFunction());
     ModuleSlice.insert(SCC.back());
   }
 
   if (SCC.empty())
     return PreservedAnalyses::all();
 
-  auto OREGetter = [&C, &CG, &AM](Function *F) -> OptimizationRemarkEmitter & {
-    FunctionAnalysisManager &FAM =
-        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
+
+  AnalysisGetter AG(FAM);
+
+  auto OREGetter = [&FAM](Function *F) -> OptimizationRemarkEmitter & {
     return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F);
   };
 
   CallGraphUpdater CGUpdater;
   CGUpdater.initialize(CG, C, AM, UR);
+
+  SetVector<Function *> Functions(SCC.begin(), SCC.end());
+  BumpPtrAllocator Allocator;
+  OMPInformationCache InfoCache(*(Functions.back()->getParent()), AG, Allocator,
+                                /*CGSCC*/ &Functions, ModuleSlice);
+
   // TODO: Compute the module slice we are allowed to look at.
-  OpenMPOpt OMPOpt(SCC, ModuleSlice, CGUpdater, OREGetter);
+  OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, &InfoCache);
   bool Changed = OMPOpt.run();
   (void)Changed;
   return PreservedAnalyses::all();
 }
 
 namespace {
 
 struct OpenMPOptLegacyPass : public CallGraphSCCPass {
bool runOnSCC(CallGraphSCC &CGSCC) override {
     DenseMap<Function *, std::unique_ptr<OptimizationRemarkEmitter>> OREMap;
     auto OREGetter = [&OREMap](Function *F) -> OptimizationRemarkEmitter & {
       std::unique_ptr<OptimizationRemarkEmitter> &ORE = OREMap[F];
       if (!ORE)
         ORE = std::make_unique<OptimizationRemarkEmitter>(F);
       return *ORE;
     };
 
+    AnalysisGetter AG;
+    SetVector<Function *> Functions(SCC.begin(), SCC.end());
+    BumpPtrAllocator Allocator;
+    OMPInformationCache InfoCache(*(Functions.back()->getParent()), AG,
+                                  Allocator,
+                                  /*CGSCC*/ &Functions, ModuleSlice);
     // TODO: Compute the module slice we are allowed to look at.
-    OpenMPOpt OMPOpt(SCC, ModuleSlice, CGUpdater, OREGetter);
+    OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, &InfoCache);
     return OMPOpt.run();
   }
 
   bool doFinalization(CallGraph &CG) override { return CGUpdater.finalize(); }
 };
 
 } // end anonymous namespace