[Polly][Fortran Array] generate run-time size computation for outermost dimension of fortran array

[bollu]

Summary

This patch tracks D32639, so this must be kept in sync with it.

• 1. Change ScopArrayInfo and its building phase to track that it is a

Fortran array. Before, this was entirely in MemoryAccess. Now, the SAI
needs to know whether it contains a fortran array or not.

• 2. Add a "dummy" pwAff into ScopArrayInfo for the virtual

outermost dimension.

• 3. Synthesize a custom Value for the pwAff isl Id such that it

computes the outermost dimension size. This matches code generated by
dragonegg

• 4. Anyone who tries to refer to the outermost dimension size from now

on will use the synthesized Value

The changes are quite large, and are somewhat "sweeping". Also note that
the diff will look much smaller once D32639 has been mainlined.

Also, I am unfamiliar with the schedule API, and I believe
that what I have done in ScopInfo.cpp is a hack. However, I'm not sure
what the right of doing this is.

[Meinersbur]

Can you upload a diff to D32639 (that is git diff 3526edc9617a 444607a22002)?

[bollu]

@Meinersbur: I put this up here to "track progress" in some sense. I think it will be easier to merge this if I ship parts of functionality from this in separate patches (it is also easier to discuss). But sure, I can diff against 444607a22002.

[Meinersbur]

Phabricator has a "dependent commit" feature (Top right "Edit Related Revisions...") which was made for such cases.

[bollu]

• [FortranArrays] Codegen runtime size computation for Fortran Arrays
• Merge branch 'fortran-arrays-add-match-for-param' into fortran-arrays-generate-bounds-checks
• fix merge commit with fortran-arrays-add-param

[bollu]

@Meinersbur: Please don't review this thoroughly till I fix the issue with the getContext() as mentioned. I'm putting this up as a general "follow along" as I mentioned before. It's diffed against D33075

lib/Analysis/ScopInfo.cpp

2194 ↗

(On Diff #98601)

From what I can tell, this is a memory leak since getContext() creates a new isl_set. However, I seem to need the new copy for this code to work.

Ah, I just understood what's going on: it's shadowing the Scop::Context and is performing the isl_schedule_gist_domain_params on that?

[bollu]

lib/Analysis/ScopInfo.cpp

2194 ↗

(On Diff #98601)

Now I don't understand why this even works. How does creating a new isl_set and using it to isl_schedule_gist_domain_params allow me to access these parameters in the code generation phase? I need to read up on what exactly isl_schedule_gist_domain_params does).

[bollu]

• refactor fortran array addition into schedule into a separate function. still using isl_schedule_gist_domain_params

[Meinersbur]

include/polly/CodeGen/IslNodeBuilder.h

80 ↗

(On Diff #98737)

Fortran

81 ↗

(On Diff #98737)

Could you document here hat "materialize" means?

lib/Analysis/ScopInfo.cpp

2194 ↗

(On Diff #98601)

If you have trouble with leak, try using

auto FortranArraysContext = give(getContextWithFortranArrays(Context, arrays());

isl_schedule_gist_domain_params simplifies a schedule using information from the set. The set may say e.g. that a parameter is always greater than zero, such that the generated AST for the schedule does not need to add a condition whether the parameter is at least zero.

317 ↗

(On Diff #98737)

Just assert(FAD && ... (Here and everywhere; no need to compare to nullptr)

Spelling: "Fortran array descriptor"

403 ↗

(On Diff #98737)

Local variables in LLVM style start with capital letter.

2231 ↗

(On Diff #98737)

Unintended change?

3447 ↗

(On Diff #98737)

Drop this->

lib/CodeGen/IslNodeBuilder.cpp

998–1009 ↗

(On Diff #98737)

I assume you are going to make this more readable

lib/CodeGen/PPCGCodeGeneration.cpp

2173–2174 ↗

(On Diff #98737)

assert(i && "...");

test/Isl/CodeGen/fortran_array_runtime_size_generation.ll

3–7 ↗

(On Diff #98737)

Please only add required switches

[bollu]

• Rebase to use D33190
• Implement fixes suggested by @Meinersbur

[Meinersbur]

include/polly/CodeGen/IslNodeBuilder.h

80 ↗

(On Diff #98737)

Don't forget to also capitalize Fortran in the title.

include/polly/ScopInfo.h

267 ↗

(On Diff #98991)

array, dot at the end of sentence.

268 ↗

(On Diff #98991)

I suggest some other terminology. "make" sounds like the funcion adds a new array.

Suggestion: updateFortranArraySize

428 ↗

(On Diff #98991)

Dot at the end of sentence.

lib/Analysis/ScopInfo.cpp

324–325 ↗

(On Diff #98991)

No need to compare to nullptr.

330 ↗

(On Diff #98991)

Remove this->

332 ↗

(On Diff #98991)

You can pass this ScopArrayInfo as user pointer. Might potentially avoid name collision (Maybe the name is already unique, the adding the ScopArrayPointer still helps isl's hash algorithm and might be useful to extract later)

403 ↗

(On Diff #98991)

const is unnecessary.

Suggestion for name: IsOutermostSizeKnown.

You could also just print [*] whenever getDimensionSizePw() returns nullptr. This should simplify the function. You can add asserta to check whether there is a situation where nullptr (not) is allowed.

2207 ↗

(On Diff #98991)

Declare as static or in anonymous namespace if not in polly namespace.

2207 ↗

(On Diff #98991)

Naming suggestion: getFortranArraysContext

2211 ↗

(On Diff #98991)

Capital first letter for local variables and function parameters.

2212 ↗

(On Diff #98991)

Fortran, incomplete sentence

2213 ↗

(On Diff #98991)

Use TODO instead of HACK

2216 ↗

(On Diff #98991)

Comparison with nullptr

2218 ↗

(On Diff #98991)

Please use LLVM style variable names.

2256–2258 ↗

(On Diff #98991)

Did you consider updating Scop::Context instead?

If you do so, be sure to to it before Stmt.realignParams(), which reads that context.

3485 ↗

(On Diff #98991)

We start local variables with capital letters.

3489–3491 ↗

(On Diff #98991)

I'd suggest to remove the const from getLatestScopArrayInfo. It doesn't serve a purpose if we have to cast it away.

Objects of type ScopArrayInfo are (like llvm::Value) are identified by address or BasePtr and kind. These are immutable properties, so we don't need to pass objects of type ScopArrayInfo as const.

lib/CodeGen/IslNodeBuilder.cpp

1051 ↗

(On Diff #98991)

Unnecessary const_cast

1071 ↗

(On Diff #98991)

Unnecessary dyn_cast

[bollu]

• [NFC wrt patch] Style & naming convention changes

[bollu]

include/polly/ScopInfo.h

268 ↗

(On Diff #98991)

that is slightly misleading, since it holds on to the FAD. update to me means that it should use the FAD and then not keep a reference to it. I'm not sure if the terminology within llvm/Polly for update means something else.

How about receiveFortranArrayDescriptor?

lib/Analysis/ScopInfo.cpp

324–325 ↗

(On Diff #98991)

Ah, because of the combination of the first and second assert?

332 ↗

(On Diff #98991)

I can see the benefit of giving it to improve the hashing (did not know that isl used the user pointer in its hash function).

However, I personally dislike using the user for isl_id in general: it's non-local, indirect, and there is no simple way to find out where the user came from (as far as I know). What are your opinions on this?

2256–2258 ↗

(On Diff #98991)

I wanted to work on a separate context because I felt it would be "cleaner", but I'm not sure about that anymore. What do you suggest, updating Scop::Context?

3489–3491 ↗

(On Diff #98991)

Alternate option is to follow OO philosophy: Ask, don't tell :). So just ask MemoryAccess to make its ScopArrayInfo model a Fortran array.

[bollu]

@Meinersbur: Addressed comments for most things, left comments on things I want to discuss on. Could you take another look?

[Meinersbur]

include/polly/ScopInfo.h

2079 ↗

(On Diff #99117)

arrays

2080 ↗

(On Diff #99117)

Fortran

268 ↗

(On Diff #98991)

We already use the verb "update" for this purpose in Scop::updateAccessDimensionality and ScopArrayInfo::updateSizes. I suggest use the same terminology for consistency (or suggestion another patch that changes all these names).

With "receive", I'd assume some communication is going on.

Another suggestion is the verb "apply".

lib/Analysis/ScopInfo.cpp

324–325 ↗

(On Diff #98991)

What I mean is to generally use

if (ptr)
if (!ptr)
assert(ptr && "...");
...

instead of

if (ptr != nullptr)
if (ptr == nullptr)
assert(ptr != nullptr && "...")
...

There is no explicit rule about this, it is just that Polly's current code base uses the former. This is for internal code style consistency.

332 ↗

(On Diff #98991)

First, I was wrong that the user pointer is used for the hash here. isl uses the it only when the isl_id has no name. Id does so such that iteration order over hastables remains deterministic when user is a pointer. Unfortunately isl has no equivalent of SetVector.

I "feel" that using the user pointer is a good safety precaution to protect from duplicate names. For instance, I could call a variable "${param_name}_fortranarr_size" that is used as an for-loop upper bound. In this case, it would not conflict, but only because that parameter's isl_id has the user pointer set (to the llvm::Value).

Since I think it it just good practice, just keep if you wish. Maybe also also Tobias for his toughts.

Anyway, I don't get you arguments against it. What do you mean by

• non-local
• indirect
• there is no simple way to find out where the user came from

?

2256–2258 ↗

(On Diff #98991)

Yes, it is supposed to do exactly that later (call isl_schedule_gist_domain_params on the context).

3489–3491 ↗

(On Diff #98991)

Possible, sure. But it clutters the MemoryAccess interface with a function that can only be called from here. I'd prefer it to have only general purpose methods since ScopInfo.h is imported by from a lot of other places.

Analogon: llvm::Instruction having a makeVectorInstruction() method.

lib/CodeGen/PPCGCodeGeneration.cpp

2173–2174 ↗

(On Diff #98737)

Correction: i==0 is ok, i is not pointer.

test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll

55 ↗

(On Diff #99117)

What information does this add?

[bollu]

• Updated style changes.
• Added the Fortran arrays' outermost dimension into the Context of

the Scop. This needs a change in one test case that checks the context.

• Cleaned up the getContextWithFortranArrays() function, and its interaction with Scop::Context.

[bollu]

@Meinersbur: made changes as requested. Could you take a look?

lib/Analysis/ScopInfo.cpp

403 ↗

(On Diff #98991)

You could also just print [*] whenever getDimensionSizePw() returns nullptr. This should simplify the function. You can add asserta to check whether there is a situation where nullptr (not) is allowed.

This will not work, because we will need to print [*] in the case when we are printing SCEV as well. So, we will need to specialise for the outermost dimension anyway.

3489–3491 ↗

(On Diff #98991)

If I have to remove the const, then code in other parts would be affected as well. Shall I do that in a separate patch?

[bollu]

• fortran -> Fortran
• pwAff -> isl_pw_aff

[bollu]

• . and newline for comments

[bollu]

• [NFC] remove metadata from comment

[bollu]

• Squash all commits into one, fix some style stuff.

[Meinersbur]

LGTM

[RKSimon]

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

1036

@bollu I realise this is a very old patch, but coverity has a dead code warning about the first 'size' not being used: https://bugs.llvm.org/show_bug.cgi?id=52173

polly/trunk/include/polly/CodeGen/IslNodeBuilder.h

IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator,
                  &ExprBuilder, StartBlock),
         RegionGen(BlockGen), DL(DL), LI(LI), SE(SE), DT(DT),
         StartBlock(StartBlock) {}
 
   virtual ~IslNodeBuilder() = default;
 
   void addParameters(__isl_take isl_set *Context);
 
+  /// Create Values which hold the sizes of the outermost dimension of all
+  /// Fortran arrays in the current scop.
+  ///
+  /// @returns False, if a problem occurred and a Fortran array was not
+  /// materialized. True otherwise.
+  bool materializeFortranArrayOutermostDimension();
+
   /// Generate code that evaluates @p Condition at run-time.
   ///
   /// This function is typically called to generate the LLVM-IR for the
   /// run-time condition of the scop, that verifies that all the optimistic
   /// assumptions we have taken during scop modeling and transformation
   /// hold at run-time.
   ///
   /// @param Condition The condition to evaluate

polly/trunk/include/polly/ScopInfo.h

public:
   ///
   ///  @param Sizes       A vector of array sizes where the rightmost array
   ///                     sizes need to match the innermost array sizes already
   ///                     defined in SAI.
   ///  @param CheckConsistency Update sizes, even if new sizes are inconsistent
   ///                          with old sizes
   bool updateSizes(ArrayRef<const SCEV *> Sizes, bool CheckConsistency = true);
 
+  /// Make the ScopArrayInfo model a Fortran array.
+  /// It receives the Fortran array descriptor and stores this.
+  /// It also adds a piecewise expression for the outermost dimension
+  /// since this information is available for Fortran arrays at runtime.
+  void applyAndSetFAD(Value *FAD);
+
   /// Destructor to free the isl id of the base pointer.
   ~ScopArrayInfo();
 
   /// Set the base pointer to @p BP.
   void setBasePtr(Value *BP) { BasePtr = BP; }
 
   /// Return the base pointer.
   Value *getBasePtr() const { return BasePtr; }
private:
   /// We distinguish between SCALAR, PHI and ARRAY objects.
   MemoryKind Kind;
 
   /// The data layout of the module.
   const DataLayout &DL;
 
   /// The scop this SAI object belongs to.
   Scop &S;
+
+  /// If this array models a Fortran array, then this points
+  /// to the Fortran array descriptor.
+  Value *FAD;
 };
 
 /// Represent memory accesses in statements.
 class MemoryAccess {
   friend class Scop;
   friend class ScopStmt;
 
 public:
__isl_give isl_set *getInvalidContext() const {
     return isl_set_params(getInvalidDomain());
   }
 
   /// Get the stride of this memory access in the specified Schedule. Schedule
   /// is a map from the statement to a schedule where the innermost dimension is
   /// the dimension of the innermost loop containing the statement.
   __isl_give isl_set *getStride(__isl_take const isl_map *Schedule) const;
 
+  /// Get the FortranArrayDescriptor corresponding to this memory access if
+  /// it exists, and nullptr otherwise.
+  Value *getFortranArrayDescriptor() const { return this->FAD; };
+
   /// Is the stride of the access equal to a certain width? Schedule is a map
   /// from the statement to a schedule where the innermost dimension is the
   /// dimension of the innermost loop containing the statement.
   bool isStrideX(__isl_take const isl_map *Schedule, int StrideWidth) const;
 
   /// Is consecutive memory accessed for a given statement instance set?
   /// Schedule is a map from the statement to a schedule where the innermost
   /// dimension is the dimension of the innermost loop containing the
private:
   /// Assume that all memory accesses are within bounds.
   ///
   /// After we have built a model of all memory accesses, we need to assume
   /// that the model we built matches reality -- aka. all modeled memory
   /// accesses always remain within bounds. We do this as last step, after
   /// all memory accesses have been modeled and canonicalized.
   void assumeNoOutOfBounds();
 
+  /// Mark arrays that have memory accesses with FortranArrayDescriptor.
+  void markFortranArrays();
+
   /// Finalize all access relations.
   ///
   /// When building up access relations, temporary access relations that
   /// correctly represent each individual access are constructed. However, these
   /// access relations can be inconsistent or non-optimal when looking at the
   /// set of accesses as a whole. This function finalizes the memory accesses
   /// and constructs a globally consistent state.
   void finalizeAccesses();

polly/trunk/lib/Analysis/ScopInfo.cpp

static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
   return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
                              MemoryKind::Array);
 }
 
 ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx,
                              ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
                              const DataLayout &DL, Scop *S,
                              const char *BaseName)
-    : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
+    : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S),
+      FAD(nullptr) {
   std::string BasePtrName =
       BaseName ? BaseName
                : getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(),
                                       Kind == MemoryKind::PHI ? "__phi" : "",
                                       UseInstructionNames);
   Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
 
   updateSizes(Sizes);
void ScopArrayInfo::updateElementType(Type *NewElementType) {
   if (NewElementSize % OldElementSize == 0 && NewElementSize < OldElementSize) {
     ElementType = NewElementType;
   } else {
     auto GCD = GreatestCommonDivisor64(NewElementSize, OldElementSize);
     ElementType = IntegerType::get(ElementType->getContext(), GCD);
   }
 }
 
+/// Make the ScopArrayInfo model a Fortran Array
+void ScopArrayInfo::applyAndSetFAD(Value *FAD) {
+  assert(FAD && "got invalid Fortran array descriptor");
+  if (this->FAD) {
+    assert(this->FAD == FAD &&
+           "receiving different array descriptors for same array");
+    return;
+  }
+
+  assert(DimensionSizesPw.size() > 0 && !DimensionSizesPw[0]);
+  assert(!this->FAD);
+  this->FAD = FAD;
+
+  isl_space *Space = isl_space_set_alloc(S.getIslCtx(), 1, 0);
+
+  std::string param_name = getName();
+  param_name += "_fortranarr_size";
+  // TODO: see if we need to add `this` as the id user pointer
+  isl_id *IdPwAff = isl_id_alloc(S.getIslCtx(), param_name.c_str(), nullptr);
+
+  Space = isl_space_set_dim_id(Space, isl_dim_param, 0, IdPwAff);
+  isl_basic_set *Identity = isl_basic_set_universe(Space);
+  isl_local_space *LocalSpace = isl_basic_set_get_local_space(Identity);
+  isl_basic_set_free(Identity);
+
+  isl_pw_aff *PwAff =
+      isl_pw_aff_from_aff(isl_aff_var_on_domain(LocalSpace, isl_dim_param, 0));
+
+  DimensionSizesPw[0] = PwAff;
+}
+
 bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,
                                 bool CheckConsistency) {
   int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
   int ExtraDimsNew = NewSizes.size() - SharedDims;
   int ExtraDimsOld = DimensionSizes.size() - SharedDims;
 
   if (CheckConsistency) {
     for (int i = 0; i < SharedDims; i++) {
__isl_give isl_id *ScopArrayInfo::getBasePtrId() const {
   return isl_id_copy(Id);
 }
 
 void ScopArrayInfo::dump() const { print(errs()); }
 
 void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
   OS.indent(8) << *getElementType() << " " << getName();
   unsigned u = 0;
-  if (getNumberOfDimensions() > 0 && !getDimensionSize(0)) {
+  // If this is a Fortran array, then we can print the outermost dimension
+  // as a isl_pw_aff even though there is no SCEV information.
+  bool IsOutermostSizeKnown = SizeAsPwAff && FAD;
+
+  if (!IsOutermostSizeKnown && getNumberOfDimensions() > 0 &&
+      !getDimensionSize(0)) {
     OS << "[*]";
     u++;
   }
   for (; u < getNumberOfDimensions(); u++) {
     OS << "[";
 
     if (SizeAsPwAff) {
       auto *Size = getDimensionSizePw(u);

 void Scop::addParameterBounds() {
   unsigned PDim = 0;
   for (auto *Parameter : Parameters) {
     ConstantRange SRange = SE->getSignedRange(Parameter);
     Context = addRangeBoundsToSet(Context, SRange, PDim++, isl_dim_param);
   }
 }
 
+// We use the outermost dimension to generate GPU transfers for Fortran arrays
+// even when the array bounds are not known statically. To do so, we need the
+// outermost dimension information. We add this into the context so that the
+// outermost dimension is available during codegen.
+// We currently do not care about dimensions other than the outermost
+// dimension since it doesn't affect transfers.
+static isl_set *addFortranArrayOutermostDimParams(__isl_give isl_set *Context,
+                                                  Scop::array_range Arrays) {
+
+  std::vector<isl_id *> OutermostSizeIds;
+  for (auto Array : Arrays) {
+    // To check if an array is a Fortran array, we check if it has a isl_pw_aff
+    // for its outermost dimension. Fortran arrays will have this since the
+    // outermost dimension size can be picked up from their runtime description.
+    // TODO: actually need to check if it has a FAD, but for now this works.
+    if (Array->getNumberOfDimensions() > 0) {
+      isl_pw_aff *PwAff = Array->getDimensionSizePw(0);
+      if (!PwAff)
+        continue;
+
+      isl_id *Id = isl_pw_aff_get_dim_id(PwAff, isl_dim_param, 0);
+      isl_pw_aff_free(PwAff);
+      assert(Id && "Invalid Id for PwAff expression in Fortran array");
+      OutermostSizeIds.push_back(Id);
+    }
+  }
+
+  const int NumTrueParams = isl_set_dim(Context, isl_dim_param);
+  Context = isl_set_add_dims(Context, isl_dim_param, OutermostSizeIds.size());
+
+  for (size_t i = 0; i < OutermostSizeIds.size(); i++) {
+    Context = isl_set_set_dim_id(Context, isl_dim_param, NumTrueParams + i,
+                                 OutermostSizeIds[i]);
+    Context =
+        isl_set_lower_bound_si(Context, isl_dim_param, NumTrueParams + i, 0);
+  }
+
+  return Context;
+}
+
 void Scop::realignParams() {
   if (PollyIgnoreParamBounds)
     return;
 
   // Add all parameters into a common model.
   isl_space *Space = isl_space_params_alloc(getIslCtx(), ParameterIds.size());
 
   unsigned PDim = 0;
   for (const auto *Parameter : Parameters) {
     isl_id *id = getIdForParam(Parameter);
     Space = isl_space_set_dim_id(Space, isl_dim_param, PDim++, id);
   }
 
   // Align the parameters of all data structures to the model.
   Context = isl_set_align_params(Context, Space);
 
+  // Add the outermost dimension of the Fortran arrays into the Context.
+  // See the description of the function for more information.
+  Context = addFortranArrayOutermostDimParams(Context, arrays());
+
   // As all parameters are known add bounds to them.
   addParameterBounds();
 
   for (ScopStmt &Stmt : *this)
     Stmt.realignParams();
-
   // Simplify the schedule according to the context too.
   Schedule = isl_schedule_gist_domain_params(Schedule, getContext());
 }
 
 static __isl_give isl_set *
 simplifyAssumptionContext(__isl_take isl_set *AssumptionContext,
                           const Scop &S) {
   // If we have modeled all blocks in the SCoP that have side effects we can
for (auto Array : arrays()) {
     Array->updateSizes(Sizes, false /* CheckConsistency */);
 
     isl_set_free(Elements);
   }
   isl_union_set_free(Accessed);
   return;
 }
 
+void Scop::markFortranArrays() {
+  for (ScopStmt &Stmt : Stmts) {
+    for (MemoryAccess *MemAcc : Stmt) {
+      Value *FAD = MemAcc->getFortranArrayDescriptor();
+      if (!FAD)
+        continue;
+
+      // TODO: const_cast-ing to edit
+      ScopArrayInfo *SAI =
+          const_cast<ScopArrayInfo *>(MemAcc->getLatestScopArrayInfo());
+      assert(SAI && "memory access into a Fortran array does not "
+                    "have an associated ScopArrayInfo");
+      SAI->applyAndSetFAD(FAD);
+    }
+  }
+}
+
 void Scop::finalizeAccesses() {
   updateAccessDimensionality();
   foldSizeConstantsToRight();
   foldAccessRelations();
   assumeNoOutOfBounds();
+  markFortranArrays();
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
   isl_set_free(InvalidContext);
   isl_schedule_free(Schedule);
 

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

bool IslNodeBuilder::materializeParameters() {
   for (const SCEV *Param : S.parameters()) {
     isl_id *Id = S.getIdForParam(Param);
     if (!materializeValue(Id))
       return false;
   }
   return true;
 }
 
+/// Generate the computation of the size of the outermost dimension from the
+/// Fortran array descriptor (in this case, `@g_arr`). The final `%size`
+/// contains the size of the array.
+///
+/// %arrty = type { i8*, i64, i64, [3 x %desc.dimensionty] }
+/// %desc.dimensionty = type { i64, i64, i64 }
+/// @g_arr = global %arrty zeroinitializer, align 32
+/// ...
+/// %0 = load i64, i64* getelementptr inbounds
+///                       (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 2)
+/// %1 = load i64, i64* getelementptr inbounds
+///                      (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 1)
+/// %2 = sub nsw i64 %0, %1
+/// %size = add nsw i64 %2, 1
+static Value *buildFADOutermostDimensionLoad(Value *GlobalDescriptor,
+                                             PollyIRBuilder &Builder,
+                                             std::string ArrayName) {
+  assert(GlobalDescriptor && "invalid global descriptor given");
+
+  Value *endIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
+                      Builder.getInt64(0), Builder.getInt32(2)};
+  Value *endPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, endIdx,
+                                            ArrayName + "_end_ptr");
+  Value *end = Builder.CreateLoad(endPtr, ArrayName + "_end");
+
+  Value *beginIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
+                        Builder.getInt64(0), Builder.getInt32(1)};
+  Value *beginPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, beginIdx,
+                                              ArrayName + "_begin_ptr");
+  Value *begin = Builder.CreateLoad(beginPtr, ArrayName + "_begin");
+
+  Value *size =
+      Builder.CreateNSWSub(end, begin, ArrayName + "_end_begin_delta");
+  Type *endType = dyn_cast<IntegerType>(end->getType());
+  assert(endType && "expected type of end to be integral");
+
+  size = Builder.CreateNSWAdd(end,
+                              ConstantInt::get(endType, 1, /* signed = */ true),
+                              ArrayName + "_size");
+
+  return size;
+}
+
+bool IslNodeBuilder::materializeFortranArrayOutermostDimension() {
+  for (const ScopStmt &Stmt : S) {
+    for (const MemoryAccess *Access : Stmt) {
+      if (!Access->isArrayKind())
+        continue;
+
+      const ScopArrayInfo *Array = Access->getScopArrayInfo();
+      if (!Array)
+        continue;
+
+      if (Array->getNumberOfDimensions() == 0)
+        continue;
+
+      Value *FAD = Access->getFortranArrayDescriptor();
+      if (!FAD)
+        continue;
+
+      isl_pw_aff *ParametricPwAff = Array->getDimensionSizePw(0);
+      assert(ParametricPwAff && "parameteric pw_aff corresponding "
+                                "to outermost dimension does not "
+                                "exist");
+
+      isl_id *Id = isl_pw_aff_get_dim_id(ParametricPwAff, isl_dim_param, 0);
+      isl_pw_aff_free(ParametricPwAff);
+
+      assert(Id && "pw_aff is not parametric");
+
+      if (IDToValue.count(Id)) {
+        isl_id_free(Id);
+        continue;
+      }
+
+      Value *FinalValue =
+          buildFADOutermostDimensionLoad(FAD, Builder, Array->getName());
+      assert(FinalValue && "unable to build Fortran array "
+                           "descriptor load of outermost dimension");
+      IDToValue[Id] = FinalValue;
+      isl_id_free(Id);
+    }
+  }
+  return true;
+}
+
 /// Add the number of dimensions in @p BS to @p U.
 static isl_stat countTotalDims(__isl_take isl_basic_set *BS, void *U) {
   unsigned *NumTotalDim = static_cast<unsigned *>(U);
   *NumTotalDim += isl_basic_set_total_dim(BS);
   isl_basic_set_free(BS);
   return isl_stat_ok;
 }
 
bool IslNodeBuilder::preloadInvariantLoads() {
 
   return true;
 }
 
 void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
   // Materialize values for the parameters of the SCoP.
   materializeParameters();
 
+  // materialize the outermost dimension parameters for a Fortran array.
+  // NOTE: materializeParameters() does not work since it looks through
+  // the SCEVs. We don't have a corresponding SCEV for the array size
+  // parameter
+  materializeFortranArrayOutermostDimension();
+
   // Generate values for the current loop iteration for all surrounding loops.
   //
   // We may also reference loops outside of the scop which do not contain the
   // scop itself, but as the number of such scops may be arbitrarily large we do
   // not generate code for them here, but only at the point of code generation
   // where these values are needed.
   Loop *L = LI.getLoopFor(S.getEntry());
 

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

__isl_give isl_set *getExtent(ScopArrayInfo *Array) {
 
     Extent = isl_set_intersect(
         Extent, isl_pw_aff_le_set(OuterMin, isl_pw_aff_copy(Val)));
     Extent = isl_set_intersect(Extent, isl_pw_aff_ge_set(OuterMax, Val));
 
     for (unsigned i = 1; i < NumDims; ++i)
       Extent = isl_set_lower_bound_si(Extent, isl_dim_set, i, 0);
 
-    for (unsigned i = 1; i < NumDims; ++i) {
+    for (unsigned i = 0; i < NumDims; ++i) {
       isl_pw_aff *PwAff =
           const_cast<isl_pw_aff *>(Array->getDimensionSizePw(i));
+
+      // isl_pw_aff can be NULL for zero dimension. Only in the case of a
+      // Fortran array will we have a legitimate dimension.
+      if (!PwAff) {
+        assert(i == 0 && "invalid dimension isl_pw_aff for nonzero dimension");
+        continue;
+      }
+
       isl_pw_aff *Val = isl_pw_aff_from_aff(isl_aff_var_on_domain(
           isl_local_space_from_space(Array->getSpace()), isl_dim_set, i));
       PwAff = isl_pw_aff_add_dims(PwAff, isl_dim_in,
                                   isl_pw_aff_dim(Val, isl_dim_in));
       PwAff = isl_pw_aff_set_tuple_id(PwAff, isl_dim_in,
                                       isl_pw_aff_get_tuple_id(Val, isl_dim_in));
       auto *Set = isl_pw_aff_gt_set(PwAff, Val);
       Extent = isl_set_intersect(Set, Extent);

polly/trunk/test/Isl/CodeGen/fortran_array_runtime_size_generation.ll

+; Check that the runtime size computation is generated for Fortran arrays.
+
+; PPCG code generation backend:
+; RUN: opt %loadPolly -S -polly-detect-fortran-arrays \
+; RUN: -polly-target=gpu  -polly-acc-mincompute=0 \
+; RUN: -polly-codegen-ppcg < %s | FileCheck %s 
+
+; Regular code generation backend:
+; RUN: opt %loadPolly -S -polly-detect-fortran-arrays \
+; RUN: -polly-codegen < %s | FileCheck %s
+
+; What the input fortran code should look like. NOTE: this is fake, the
+; .ll file was hand-written.
+; 
+; MODULE testmod
+; USE data_parameters, ONLY : &
+; IMPLICIT NONE
+; 
+; INTEGER (KIND=iintegers), ALLOCATABLE, PRIVATE  :: &
+;   arrin(:), arrout(:)
+; CONTAINS
+;
+; SUBROUTINE test()
+;   INTEGER (KIND=iintegers) :: i
+; 
+;   DO i = 1, 100
+;       arrout(i) = arrin(i) * arrin(i)
+;   END DO
+; END SUBROUTINE test
+; END MODULE testmod
+
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i32:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+module asm "\09.ident\09\22GCC: (GNU) 4.6.4 LLVM: 3.3.1\22"
+
+%"struct.array1_real(kind=8)" = type { i8*, i32, i32, [1 x %struct.descriptor_dimension] }
+%struct.descriptor_dimension = type { i32, i32, i32 }
+
+@arrin = unnamed_addr global %"struct.array1_real(kind=8)" zeroinitializer, align 32
+@arrout = unnamed_addr global %"struct.array1_real(kind=8)" zeroinitializer, align 32
+
+; Function Attrs: nounwind uwtable
+define void @__src_soil_MOD_terra1() unnamed_addr #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %rawmemin1 = load i32*, i32** bitcast (%"struct.array1_real(kind=8)"* @arrin to i32**), align 32, !tbaa !0
+  %rawmemout2 = load i32*, i32** bitcast (%"struct.array1_real(kind=8)"* @arrout to i32**), align 32, !tbaa !0
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.body
+  %indvars.iv = phi i64 [ 1, %entry.split ], [ %indvars.iv.next4, %for.body ]
+  %inslot = getelementptr inbounds i32, i32* %rawmemin1, i64 %indvars.iv
+  %inval = load i32, i32* %inslot, align 8
+  %outslot = getelementptr inbounds i32, i32* %rawmemout2, i64 %indvars.iv
+  %out = mul nsw i32 %inval, %inval
+  store i32 %out, i32* %outslot, align 8
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next4, 100
+  br i1 %exitcond, label %return, label %for.body
+
+return:                                           ; preds = %for.body
+  ret void
+}
+
+attributes #0 = { nounwind uwtable }
+
+!0 = !{!1, !1, i32 0}
+!1 = !{!"alias set 3: void*", !2}
+!2 = distinct !{!2}
+
+
+; CHECK:       %MemRef_rawmemin1_end = load i32, i32* getelementptr inbounds (%"struct.array1_real(kind=8)", %"struct.array1_real(kind=8)"* @arrin, i64 0, i32 3, i64 0, i32 2)
+; CHECK-NEXT:  %MemRef_rawmemin1_begin = load i32, i32* getelementptr inbounds (%"struct.array1_real(kind=8)", %"struct.array1_real(kind=8)"* @arrin, i64 0, i32 3, i64 0, i32 1)
+; CHECK-NEXT:  %MemRef_rawmemin1_end_begin_delta = sub nsw i32 %MemRef_rawmemin1_end, %MemRef_rawmemin1_begin
+; CHECK-NEXT:  %MemRef_rawmemin1_size = add nsw i32 %MemRef_rawmemin1_end, 1
+; CHECK-NEXT:  %MemRef_rawmemout2_end = load i32, i32* getelementptr inbounds (%"struct.array1_real(kind=8)", %"struct.array1_real(kind=8)"* @arrout, i64 0, i32 3, i64 0, i32 2)
+; CHECK-NEXT:  %MemRef_rawmemout2_begin = load i32, i32* getelementptr inbounds (%"struct.array1_real(kind=8)", %"struct.array1_real(kind=8)"* @arrout, i64 0, i32 3, i64 0, i32 1)
+; CHECK-NEXT:  %MemRef_rawmemout2_end_begin_delta = sub nsw i32 %MemRef_rawmemout2_end, %MemRef_rawmemout2_begin
+; CHECK-NEXT:  %MemRef_rawmemout2_size = add nsw i32 %MemRef_rawmemout2_end, 1

polly/trunk/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored_read_and_write.ll

 return.loopexit:                                  ; preds = %"9"
   br label %return
 
 return:                                           ; preds = %return.loopexit, %entry.split
   ret void
 }
 
 ; CHECK:      ReadAccess := [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0]
-; CHECK-NEXT:     [p_0_loaded_from_n] -> { Stmt_9[i0] -> MemRef0[o0] };
+; CHECK-NEXT:     [p_0_loaded_from_n, MemRef0_fortranarr_size, MemRef1_fortranarr_size] -> { Stmt_9[i0] -> MemRef0[o0] };
 ; CHECK-NEXT: MayWriteAccess := [Reduction Type: NONE] [Fortran array descriptor: ys] [Scalar: 0]
-; CHECK-NEXT:     [p_0_loaded_from_n] -> { Stmt_9[i0] -> MemRef1[o0] };
+; CHECK-NEXT:     [p_0_loaded_from_n, MemRef0_fortranarr_size, MemRef1_fortranarr_size] -> { Stmt_9[i0] -> MemRef1[o0] };