This is an archive of the discontinued LLVM Phabricator instance.

[Polly] [Fortran Support] Add pattern matching to find Fortran array descriptor
ClosedPublic

Authored by bollu on Apr 28 2017, 2:41 AM.

Details

Summary

Dragonegg genereates Fortran arrays that have been created using Allocate(..),
as well as globals in a specific way. This allows us to acces their internal
structure and query for properties such as dimension.

This patch adds preliminary support for detection and storage of the Fortran
array descriptor structures. For now, the tests simply check that Fortran
arrays are being detected.

We can build up on this to emit run-time checks for array dimensions. That will
be a separate patch

Event Timeline

bollu created this revision.Apr 28 2017, 2:41 AM
Meinersbur edited edge metadata.Apr 28 2017, 4:38 AM

Can you explain why you need to call ConstantExpr::getAsInstruction(). The patch could be significantly simpler we do not "convert" a ConstantExpr to Instruction. Am I missing something?

DraggonEgg is a de-facto abandoned project (The test cases were generated by LLVM 3.3.1). To use DraggonEgg with Polly today, one has to emit the code with an old release of LLVM with DraggenEgg to a bitcode file, then import it into a newer LLVM with Polly. To compile Fortran, there is flang. Is there still a need to support DraggonEgg?

include/polly/ScopBuilder.h
90

Please use proper capitalization: @see polly::FortranArrayDescriptor

92

Please use the same capitalization as the argument name: @param Inst ...

include/polly/ScopInfo.h
413

"dumb struct" is also called a Plain Old Data (POD). See http://www.cplusplus.com/reference/type_traits/is_pod/.

It is not, btw. std::unique_ptr and AssertingVH have destructors.

I think you should just remove that line, as it is misleading.

432

Do you have other means of explaining the delete-issue than pointing to an unofficial mirror url?

452

This line is only used for asserts. You could put that part with this asserts into a #ifndef NDEBUG block.

468

Did you consider making this method const?

This seems to be the only public accessor of this class. DescriptorOwningInstruction is used to not prematurely free the instruction. To do need to store a reference to Descriptor or would its name be enough?

689

I don't know if Doxygen processes @see if not on its own line.

690

Did you consider moving this fields where the other fields of this class are defined?

lib/Analysis/ScopBuilder.cpp
1

Mistake?

117–130

Please don't just copy the IR from somewhere, only include things that are relevant. For instance !tbaa !5 doesn't mean anything without the MDNode.

Please also explain what the code you are matching is supposed to do.

181–182

I don't undersant why we need to call ConstantExpr::getAsInstruction? Can't we just also patch the ConstantExpr?

201

Can we avoid matching by name? The name should have no influence on the semantics.

252–253

Again, why the need for ConstantExpr::getAsInstruction()?

lib/Analysis/ScopInfo.cpp
1026

Did you consider having FAD as an argument of `MemoryAccesses ctor. It seems to be required only for initialization.

bollu added a comment.Apr 28 2017, 6:45 AM

I'm not super familiar with the LLVM API to manipulate IR, so apologies for any API abuse!

Can you explain why you need to call ConstantExpr::getAsInstruction(). The patch could be significantly simpler we do not "convert" a ConstantExpr to Instruction. Am I missing something?

From what I understand, the docs seem to imply that ConstantExpr is a black-box. I wish to pattern match on the GetElementPtr constant expression.

  • [lvm::GetElementPtrConstantExpr](http://llvm.org/docs/doxygen/html/classllvm_1_1GetElementPtrConstantExpr.html) mentions that "...GetElementPtrConstantExpr - This class is private to Constants.cpp, and is used behind the s.cenes to implement getelementpr constant exprs".
  • Similarly, I wish to destructure a ConstantExpr into a Bitcast, since I wanted to access the array that is being bitcasted.

The only API that seemed to expose the internals of which ContantExpr is being exposed is getAsInstruction(). If this is a misuse of the API, I'd like to know what the correct pattern is. Yes, if there's a clean way to get this information, the ugliness goes away.

bollu added inline comments.Apr 28 2017, 6:56 AM
include/polly/ScopBuilder.h
92

Thanks for the catch, will fix.

include/polly/ScopInfo.h
413

right. I meant "dumb" in the sense of "contains no dynamic behaviour" / "is used as a data aggregate", not "has no complex behaviour on destruction".

Do you have a better name for that sort of thing? I agree, "dumb" is misleading.

432

Everywhere else the method getAsInstruction is used, they attach to a basic-block that LLVM frees.

I can point to the official LLVM sources instead of the mirror, but the point is the same, is it not? It is used in a test within LLVM to free the chunk of memory.

468

yes, this should be const. Thanks for the catch.

I think I will need the Descriptor later on, to generate things such as run-time checks. I will need access to the LLVM IR Value to generate Load/Store instructions from the Descriptor.

lib/Analysis/ScopBuilder.cpp
201

do you want me to match based on the internal structure of the struct? I could do that, but again, there could be another struct with the same layout.

Would be OK with the solution where I pattern match on both the name and the structure?

lib/Analysis/ScopInfo.cpp
1026

I considered it. However, in that case, construction of the MemoryAccess becomes more complex (and tied in with the Fortran stuff). I wanted to keep the changes to MemoryAccess as isolated as possible.

Currently, computing the array descriptor is somewhat orthogonal from the computation of the memory access. I didn't want to tightly couple them for the reasons mentioned above.

If this is a misuse of the API, I'd like to know what the correct pattern is. Yes, if there's a clean way to get this information, the ugliness goes away.

I wouldn't call it a misuse, but it isn't beautiful either. On the other hand, there might not be a beautiful way.

What you can do is check the Opcode of the ConstantExpr CE->getOpcode() == Instruction::GetElementPtr, and manually inspect the Operands, e.g. check if they're all ConstantInts.

I'm not super familiar with the LLVM API to manipulate IR, so apologies for any API abuse!

Can you explain why you need to call ConstantExpr::getAsInstruction(). The patch could be significantly simpler we do not "convert" a ConstantExpr to Instruction. Am I missing something?

From what I understand, the docs seem to imply that ConstantExpr is a black-box. I wish to pattern match on the GetElementPtr constant expression.

  • [lvm::GetElementPtrConstantExpr](http://llvm.org/docs/doxygen/html/classllvm_1_1GetElementPtrConstantExpr.html) mentions that "...GetElementPtrConstantExpr - This class is private to Constants.cpp, and is used behind the s.cenes to implement getelementpr constant exprs".
  • Similarly, I wish to destructure a ConstantExpr into a Bitcast, since I wanted to access the array that is being bitcasted.

The only API that seemed to expose the internals of which ContantExpr is being exposed is getAsInstruction(). If this is a misuse of the API, I'd like to know what the correct pattern is. Yes, if there's a clean way to get this information, the ugliness goes away.

Have you tried llvm::GEPOperator?

bollu updated this revision to Diff 97104.Apr 28 2017, 8:21 AM
  • [NFC wrt patch] fix capitalization, comment order and style, comment phrasing.
  • Fix mistake comment
  • Change order of comments to separate out Fortran parts
  • Wrap Fortran pattern matching in ScopBuilder.h in a ..@
  • Document pattern matching functions properly, remove extra un-necessary IR cruft.
  • remove "dumb struct" comment. Still looking for a way to describe that this struct should not have behaviour. Rather, it is used as an aggregate.
bollu updated this revision to Diff 97106.Apr 28 2017, 8:26 AM

[NFC wrt patch] Don't return StringRef for name, clone & return a std::string

Fails for msvc with:

C:\Users\Meinersbur\src\llvm\tools\polly\lib\Analysis\ScopBuilder.cpp(218): error C2668: 'llvm::make_unique': ambiguous call to overloaded function
C:\Users\Meinersbur\src\llvm\include\llvm/ADT/STLExtras.h(927): note: could be 'std::unique_ptr<polly::FortranArrayDescriptor,std::default_delete<_Ty>> llvm::make_unique<polly::FortranArrayDescriptor,llvm::GlobalValue*&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>>>(llvm::GlobalValue *&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>> &&)'
        with
        [
            _Ty=polly::FortranArrayDescriptor
        ]
C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE\memory(1628): note: or       'std::unique_ptr<polly::FortranArrayDescriptor,std::default_delete<_Ty>> std::make_unique<polly::FortranArrayDescriptor,llvm::GlobalValue*&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>>>(llvm::GlobalValue *&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>> &&)' [found using argument-dependent lookup]
        with
        [
            _Ty=polly::FortranArrayDescriptor
        ]
C:\Users\Meinersbur\src\llvm\tools\polly\lib\Analysis\ScopBuilder.cpp(218): note: while trying to match the argument list '(llvm::GlobalValue *, std::unique_ptr<llvm::Instruction,std::default_delete<_Ty>>)'
        with
        [
            _Ty=llvm::Instruction
        ]
C:\Users\Meinersbur\src\llvm\tools\polly\lib\Analysis\ScopBuilder.cpp(276): error C2668: 'llvm::make_unique': ambiguous call to overloaded function
C:\Users\Meinersbur\src\llvm\include\llvm/ADT/STLExtras.h(927): note: could be 'std::unique_ptr<polly::FortranArrayDescriptor,std::default_delete<_Ty>> llvm::make_unique<polly::FortranArrayDescriptor,llvm::GlobalValue*&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>>>(llvm::GlobalValue *&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>> &&)'
        with
        [
            _Ty=polly::FortranArrayDescriptor
        ]
C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE\memory(1628): note: or       'std::unique_ptr<polly::FortranArrayDescriptor,std::default_delete<_Ty>> std::make_unique<polly::FortranArrayDescriptor,llvm::GlobalValue*&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>>>(llvm::GlobalValue *&,std::unique_ptr<llvm::Instruction,std::default_delete<llvm::Instruction>> &&)' [found using argument-dependent lookup]
        with
        [
            _Ty=polly::FortranArrayDescriptor
        ]
C:\Users\Meinersbur\src\llvm\tools\polly\lib\Analysis\ScopBuilder.cpp(276): note: while trying to match the argument list '(llvm::GlobalValue *, std::unique_ptr<llvm::Instruction,std::default_delete<_Ty>>)'
        with
        [
            _Ty=llvm::Instruction
        ]
lib/Analysis/ScopBuilder.cpp
181–182

With this your test cases still work:

diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp
index c399e0d2..9d9b381d 100644
--- a/lib/Analysis/ScopBuilder.cpp
+++ b/lib/Analysis/ScopBuilder.cpp
@@ -183,16 +183,7 @@ ScopBuilder::findFortranArrayDescriptorForAllocArrayAccess(MemAccInst Inst) {
     if (!DescriptorGEP)
       continue;

-    // this needs to be deleted, on the basis of:
-    // https://github.com/llvm-mirror/llvm/blob/93e6e5414ded14bcbb233baaaa5567132fee9a0c/unittests/IR/ConstantsTest.cpp#L186
-    std::unique_ptr<Instruction> DescriptorGEPRawInst(
-        DescriptorGEP->getAsInstruction());
-
-    // We want an instruction and not a ConstantExpr since this should
-    // give us more flexibility to inspect the GEP.
-    auto *DescriptorGEPInst =
-        dyn_cast<GetElementPtrInst>(DescriptorGEPRawInst.get());
-
+    auto *DescriptorGEPInst = dyn_cast<GEPOperator>(DescriptorGEP);
     if (!(DescriptorGEPInst && DescriptorGEPInst->hasAllConstantIndices())) {
       continue;
     }
@@ -214,8 +205,7 @@ ScopBuilder::findFortranArrayDescriptorForAllocArrayAccess(MemAccInst Inst) {
     if (!Descriptor) {
       continue;
     }
-    return make_unique<FortranArrayDescriptor>(Descriptor,
-                                               std::move(DescriptorGEPRawInst));
+    return make_unique<FortranArrayDescriptor>(Descriptor, nullptr);
   }

   return nullptr;
278

The ; is unnecessary

etherzhhb added inline comments.
lib/Analysis/ScopBuilder.cpp
140

Maybe functions from llvm/IR/PatternMatch.h can help you to simplify this function

685–691

Actually findFortranArrayDescriptorForAllocArrayAccess and findFortranArrayDescriptorForNonAllocArrayAccess do not need to return a std::unique_ptr.

If setFortranArrayDescriptor is written as:

void MemoryAccess::setFortranArrayDescriptor(FortranArrayDescriptor *FAD) {
  this->FAD.reset(FAD);

  // TODO: write checks to make sure it looks _exactly_ like a Fortran array
  // descriptor
};
bollu added a comment.May 1 2017, 6:35 AM

@Meinersbur: Are there windows buildbots for Polly whose outputs I can look at? I think the ambiguity is between llvm::make_unique and std::make_unique.

bollu updated this revision to Diff 97286.May 1 2017, 7:58 AM
  • [NFC wrt patch] clarified which make_unique to pick. Pick llvm::make_unique

If you are not going to use dyn_cast<GEPOperator>, could you please state the reason why?

bollu updated this revision to Diff 97405.May 2 2017, 1:08 AM
  • replace getAsInstruction with dyn_cast<[GEP|BitCast]Operator>. Thanks @Meinersbur!
bollu added a comment.May 2 2017, 1:30 AM

@Meinersbur:

Fixed, I'm using dyn_cast<GEPOperator>. I wanted to explore the other error, not that I was against using GEPOperator. Thanks for pointing me to it!

Could you point me to how I could have discovered that GEPOperator works in this case on my own? I later read that *Operator acts as a unifying API to manipulate *Instruction and *ConstantExpr, but is there someplace in the documentation that this relationship is expressed? It's described in llvm::Operator, but not in llvm::Instruction or llvm::ConstantExpr from what I've seen.

@etherzhhb:

Maybe functions from llvm/IR/PatternMatch.h can help you to simplify this function

I looked at PatternMatch.h, and I did not find a way to pattern match against GEP instructions. Am I missing it or does the functionality not exist?

Actually findFortranArrayDescriptorForAllocArrayAccess and findFortranArrayDescriptorForNonAllocArrayAccess do not need to return a std::unique_ptr.

I would prefer to return a unique_ptr with make_unique at the site of the allocation itself since it prevents a whole class of bugs. Could you tell me the rationale for not wishing to
take a unique_ptr as a parameter to MemoryAccess::setFortranArrayDescriptor?

I hoped to get rid of FortranaArrayDescriptor entirely. All the it is used for is getName(). ScopArrayInfo already has a BaseName property that you could use for this purpose.

Could you point me to how I could have discovered that GEPOperator works in this case on my own? I later read that *Operator acts as a unifying API to manipulate *Instruction and *ConstantExpr, but is there someplace in the documentation that this relationship is expressed? It's described in llvm::Operator, but not in llvm::Instruction or llvm::ConstantExpr from what I've seen.

I look how other code in LLVM does things.

In this case I was looking for uses of GetElementPtrConstantExpr as I did not believe that no other code in LLVM was expecting the structure of constants. I found non-Constants.cpp uses in GEPOperator, which is used in all of LLVM.

I could not find a non-Doxygen documentation for this.

@etherzhhb:

Maybe functions from llvm/IR/PatternMatch.h can help you to simplify this function

I looked at PatternMatch.h, and I did not find a way to pattern match against GEP instructions. Am I missing it or does the functionality not exist?

I cannot find a matcher for GEP either.

Actually findFortranArrayDescriptorForAllocArrayAccess and findFortranArrayDescriptorForNonAllocArrayAccess do not need to return a std::unique_ptr.

I would prefer to return a unique_ptr with make_unique at the site of the allocation itself since it prevents a whole class of bugs. Could you tell me the rationale for not wishing to
take a unique_ptr as a parameter to MemoryAccess::setFortranArrayDescriptor?

If FortranArrayDescriptor is a type that has to be allocated on the heap (because it is identified by memory location; compared by its address) then I find unique_ptr appropriate. If it is used as a container only ("dumb struct"), then you can also pass-by-value, especially if it has just one member. The bug classes "use-after-free" don't "memory leak" don't even exist for pass-by-value.

With one member only, I don't even see a need to introduce that struct. You can just pass the GlobalValue.

include/polly/ScopInfo.h
437–438

This is not necessary anymore because with NDEBUG not set, the asserts will use the variable.

lib/Analysis/ScopBuilder.cpp
1

There is still a change in the diff.

201

Mmmh, not sure.

Ideally, DraggonEgg would add an annotation saying this is an array (access) so we don't have to rely on name and/or structure and on other compilers not generating the same name/structure for some other purpose. Would that be possible?

If not, let's keep the detection by name.

226–228

The order is confusing to me. Could you consider

///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
///      %slot is optional because if you are writing to the 0th index, we don't need a GEP.
230–231

The implementation does not check for alignment.

253–258

Shorten to

auto *BitcastOperator = dyn_cast<BitCastOperator>(MemLoad->getPointerOperand());
if (!BitcastOperator)
  return nullptr;

?

bollu added a comment.May 2 2017, 11:15 PM

I hoped to get rid of FortranArrayDescriptor entirely. All the it is used for is getName(). ScopArrayInfo already has a BaseName property that you could use for this purpose.

Ah yes, that's fair. I was considering keeping FortranArrayDescriptor around in case I wish to describe more properties, but for now I suppose I could kill the struct.

I'm writing a patch currently which will use the GlobalValue in the FortranArrayDescriptor. I suppose I could make this a memory of the ScopArrayInfo, and pull it out later on if need be. Does that sound OK?

I suppose I could make this a memory of the ScopArrayInfo, and pull it out later on if need be. Does that sound OK?

Yes, sounds great!

bollu updated this revision to Diff 97930.May 5 2017, 4:27 AM
  • [NFC wrt patch] nuke all references to FortranArayDescriptor struct
  • [NFC wrt patch] Make changes suggested by @Meinersbur
  • [NFW wrt patch] removed braces for one-line if/else
bollu updated this revision to Diff 97935.May 5 2017, 4:52 AM
  • Check for alignment of store/load
grosser edited edge metadata.May 5 2017, 4:54 AM

For some reason your diff contains parts of Philip's changes :(

lib/Analysis/ScopBuilder.cpp
1

Unrelated change.

bollu updated this revision to Diff 97936.May 5 2017, 4:57 AM
  • [NFC wrt patch] fixing diff of patch to diff against upstream/master
bollu updated this revision to Diff 97938.May 5 2017, 5:06 AM
  • [NFC wrt patch] reorder comment to make it easier to read
  • [NFC wrt patch] add period at comment end
bollu added a comment.May 5 2017, 5:08 AM

@Meinersbur: I restructured the code as you requested. Could you please take another look?

Meinersbur accepted this revision.May 5 2017, 8:28 AM

Accepting, because I don't see more significant code improvements.

However, I have some concerns remaining:

  • The detection code is too general. findFortranArrayDescriptorForNonAllocArrayAccess is a load from a global pointer, GEP and an access to it. That is very common code and we will get false positives. The prefix "struct.array" also does not seem to be unique to draggonegg's Fortran-style arrays. At the moment there is no effect of array descriptors, but let me suggest to add a command-line switch that enables detection of these arrays and can be enabled manually when compiling Fortran code (i.e. off by default)
  • I still don't know that the Fortran Array Descriptor will be used for, hence I cannot evaluate whether the code is useful at all.
This revision is now accepted and ready to land.May 5 2017, 8:28 AM
bollu updated this revision to Diff 98164.May 8 2017, 7:11 AM
  • Add better pattern matching checks for type of fortran array descriptor
bollu added inline comments.May 8 2017, 7:17 AM
lib/Analysis/ScopBuilder.cpp
136

@Meinersbur: I added more rigorous checks to make sure that a Global that we believe to be a fortran array is almost surely one. I would appreciate it if you take a look at it.

I am somewhat against adding a flag, for two reasons:

  1. Not being behind a flag allows us to catch false positives for this sort of code, which is valuable
  1. Polly already has a lot of options, and I don't want to add to the combinatorial explosion :)

If you think that even these pattern matches are too less, I could actually regex match against the name.

However, I am of the opinion that since this is a structural and a name based match, plus incredibly specific nature of "struct.descriptor_dimension" should make this foolproof.

Meinersbur added inline comments.May 9 2017, 7:36 AM
lib/Analysis/ScopBuilder.cpp
136

There is still nothing unique that only DragonEgg would generate. The name "struct.descriptor_dimension" make false positives less likely, but not I can even craft one using clang:

struct descriptor_dimension {int x,y,z};

clang -emit-llvm -S -o -

%struct.descriptor_dimension = type { i32, i32, i32 }

I wouldn't bet on that no code ever written or will be written in the future does not contain a struct of 3 ints called "descriptor_dimension" or "array1_real".

  1. Not being behind a flag allows us to catch false positives for this sort of code, which is valuable

If you want to test for false positves, just use the flag. Being off by default doesn't make it impossible to test your code. I'd rather not use our users as guinea pigs. I'd also prefer not having to tell someone in a bug report that they were using the wrong variable/type name.

Once we compile something different depending on whether a Fortran array is detected, we don't even know whether a miscompilation is caused by a false positve since the only difference you can observe is the miscompilation (no error message or the like). Since there isn't even a flag to switch it off to see whether it works then, I cannot even check whether a false positive was the cause of a miscompilation.

Sorry, I have a rather strong opinion about this.

  1. Polly already has a lot of options, and I don't want to add to the combinatorial explosion.

Tobias seems to have no hesitation to add more flags (we already have so many). Most are hidden, i.e. not meant for end users.

Telling the compiler what kind of input we are handling is a perfect reason for a new command line switch.

I can offer the alternative to modify your LLVM+DragonEgg such that it generates a unique flag/attribute/metadata that identifies a Fortran array. DragonEgg is not developed anymore, and you are probably the only one using it with Polly. Since DraggonEgg is in the LLVM repository, you can even upstream it.

bollu added a comment.May 9 2017, 7:47 AM

I'd rather not use our users as guinea pigs. I'd also prefer not having to tell someone in a bug report that they were using the wrong variable/type name.

I understand. I didn't consider the ramifications of this generating false positives, I'm sorry.

Very well, I'll put this behind a flag for now. If I choose to modify dragonegg such that we will generate no false positives, then we can perhaps remove the flag. I hope that sounds okay?

Very well, I'll put this behind a flag for now. If I choose to modify dragonegg such that we will generate no false positives, then we can perhaps remove the flag. I hope that sounds okay?

Yes, this is what I had in mind. Thank you.

bollu updated this revision to Diff 98289.May 9 2017, 8:12 AM
  • hide fortran array detection behind option that is disabled by default
bollu added a comment.May 9 2017, 8:14 AM

@Meinersbur: Done, I added an option to hide this behind.

@Meinersbur I would like it if you re-check this in its current state, after which I'll be comfortable upstreaming this. Thanks!

Yes, looks great.

lib/Analysis/ScopBuilder.cpp
40

Capitalization of first latter.

687

If there are only two functions to call, the answer is: no.

This revision was automatically updated to reflect the committed changes.
./CMakeLists.txt