Add rewrite by-reference parameter pass

[grosser]

Summary

This pass detangles induction variables from functions, which take variables by
reference. Most fortran functions compiled with gfortran pass variables by
reference. Unfortunately a common pattern, printf calls of induction variables,
prevent in this situation the promotion of the induction variable to a register,
which again inhibits any kind of loop analysis. To work around this issue
we developed a specialized pass which introduces separate alloca slots for
known-read-only references, which indicate the mem2reg pass that the induction
variables can be promoted to registers and consquently enable SCEV to work.

We currently hardcode the information that a function
_gfortran_transfer_integer_write does not read its second parameter, as
dragonegg does not add the right annotations and we cannot change old dragonegg
releases. Hopefully flang will produce the right annotations.

[bollu]

Nit: Consider using IRBuilder? Not sure if this is needed, but maybe it avoids the extra parameter. YMMV. Other than that LGTM.

lib/Transform/RewriteByReferenceParameters.cpp

42

Could you please document why this is necessary?

55

Nit: this proofs useful -> this proves useful

65

Perhaps we can make this slightly nicer with the pattern matching utilities. If not, I believe we should at least use the Operator versions so this can work on constant versions of the operands as well.

72

Consider appending the original alloca name?

74

Consider appending the original alloca name?

76

Consider appending the original Alloca name?

test/RewriteByReferenceParameters/fortran_io.ll

27

I believe we can reduce this type to whatever we want to. Consider making this smaller?

[grosser]

Thanks for the nice review. I addressed all but one comment, which can likely be improved in a subsequent commit. Will go ahead and commit this now.

lib/Transform/RewriteByReferenceParameters.cpp

42

I generalized the code for this to not be necessary.

65

Not sure what you mean. As this seems to be an extension of this functionality, I will go ahead without this and we can improve this in a subsequent commit.

[etherzhhb]

Sorry this may be too late. Alexandre and me had discussed similar problem (but not exactly the same)

1. maybe we could improve the ArgumentPromotion pass for this
2. this pass seems to be generic, maybe we could move this to LLVM?

[grosser]

It's certainly not too late. Until now it seemed to me like a very specific optimization for gfortran. I did not see any such examples before. If we can generalize this, we can certainly try to upstream this. Could you share some of the examples you are seeing?

[etherzhhb]

In D36800#844026, @grosser wrote:

It's certainly not too late. Until now it seemed to me like a very specific optimization for gfortran. I did not see any such examples before. If we can generalize this, we can certainly try to upstream this. Could you share some of the examples you are seeing?

"by-reference" is one side, another side is the function return something via a pointer argument (e.g. the opencl sincos function)[1]:

int *p;
a = return_via_p(p);

We want to transform it to:

{ a, b } = return_via_p();
*p = b;

Also, a pointer can be read-modify-write:

int *p;
a = read_modify_write_p(p);

we want to transform it to:

int *p;
int pin = *p;
{a, b} = read_modify_write_p(pin);
*p = b;

[1]https://www.khronos.org/registry/OpenCL/sdk/1.0/docs/man/xhtml/sin.html

[grosser]

In D36800#844034, @etherzhhb wrote:

In D36800#844026, @grosser wrote:

It's certainly not too late. Until now it seemed to me like a very specific optimization for gfortran. I did not see any such examples before. If we can generalize this, we can certainly try to upstream this. Could you share some of the examples you are seeing?

"by-reference" is one side, another side is the function return something via a pointer argument (e.g. the opencl sincos function)[1]:

int *p;
a = return_via_p(p);

We want to transform it to:

{ a, b } = return_via_p();
*p = b;

Also, a pointer can be read-modify-write:

int *p;
a = read_modify_write_p(p);

we want to transform it to:

int *p;
int pin = *p;
{a, b} = read_modify_write_p(pin);
*p = b;

I see. These all seem to require us to modify the function declarations. Hence, are likely out-of-scope for a function pass, but certainly a good fit for the argument promotion pass. Feel free to add me as a reviewer in case you would like to contribute patches for your two examples.

As the fortran functions are part of an external library the change I committed here likely does not benefit from argpromotion.

Best,
Tobias

include/polly/LinkAllPasses.h

 llvm::Pass *createDOTViewerPass();
 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 llvm::Pass *createPollyCanonicalizePass();
 llvm::Pass *createPolyhedralInfoPass();
 llvm::Pass *createScopDetectionWrapperPassPass();
 llvm::Pass *createScopInfoRegionPassPass();
 llvm::Pass *createScopInfoWrapperPassPass();
+llvm::Pass *createRewriteByrefParamsPass();
 llvm::Pass *createIslAstInfoWrapperPassPass();
 llvm::Pass *createCodeGenerationPass();
 #ifdef GPU_CODEGEN
 llvm::Pass *createPPCGCodeGenerationPass(GPUArch Arch = GPUArch::NVPTX64,
                                          GPURuntime Runtime = GPURuntime::CUDA);
 
 llvm::Pass *
 createManagedMemoryRewritePassPass(GPUArch Arch = GPUArch::NVPTX64,

 namespace llvm {
 class PassRegistry;
 void initializeCodePreparationPass(llvm::PassRegistry &);
 void initializeDeadCodeElimPass(llvm::PassRegistry &);
 void initializeJSONExporterPass(llvm::PassRegistry &);
 void initializeJSONImporterPass(llvm::PassRegistry &);
 void initializeIslAstInfoWrapperPassPass(llvm::PassRegistry &);
 void initializeCodeGenerationPass(llvm::PassRegistry &);
+void initializeRewriteByrefParamsPass(llvm::PassRegistry &);
 #ifdef GPU_CODEGEN
 void initializePPCGCodeGenerationPass(llvm::PassRegistry &);
 void initializeManagedMemoryRewritePassPass(llvm::PassRegistry &);
 #endif
 void initializeIslScheduleOptimizerPass(llvm::PassRegistry &);
 void initializeMaximalStaticExpanderPass(llvm::PassRegistry &);
 void initializePollyCanonicalizePass(llvm::PassRegistry &);
 void initializeFlattenSchedulePass(llvm::PassRegistry &);
 void initializeDeLICMPass(llvm::PassRegistry &);
 } // namespace llvm
 
 #endif

lib/CMakeLists.txt

add_library(PollyCore OBJECT
   Transform/ScheduleOptimizer.cpp
   Transform/FlattenSchedule.cpp
   Transform/FlattenAlgo.cpp
   Transform/ForwardOpTree.cpp
   Transform/DeLICM.cpp
   Transform/ZoneAlgo.cpp
   Transform/Simplify.cpp
   Transform/MaximalStaticExpansion.cpp
+  Transform/RewriteByReferenceParameters.cpp
   ${POLLY_HEADER_FILES}
   )
 set_target_properties(PollyCore PROPERTIES FOLDER "Polly")
 
 # Create the library that can be linked into LLVM's tools and Polly's unittests.
 # It depends on all library it needs, such that with
 # LLVM_POLLY_LINK_INTO_TOOLS=ON, its dependencies like PollyISL are linked as
 # well.

lib/Support/RegisterPasses.cpp

#endif
   initializeMaximalStaticExpanderPass(Registry);
   initializeIslAstInfoWrapperPassPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializePolyhedralInfoPass(Registry);
   initializeScopDetectionWrapperPassPass(Registry);
   initializeScopInfoRegionPassPass(Registry);
   initializeScopInfoWrapperPassPass(Registry);
+  initializeRewriteByrefParamsPass(Registry);
   initializeCodegenCleanupPass(Registry);
   initializeFlattenSchedulePass(Registry);
   initializeForwardOpTreePass(Registry);
   initializeDeLICMPass(Registry);
   initializeSimplifyPass(Registry);
   initializeDumpModulePass(Registry);
   initializePruneUnprofitablePass(Registry);
 }

lib/Transform/Canonicalization.cpp

 using namespace polly;
 
 static cl::opt<bool>
     PollyInliner("polly-run-inliner",
                  cl::desc("Run an early inliner pass before Polly"), cl::Hidden,
                  cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 void polly::registerCanonicalicationPasses(llvm::legacy::PassManagerBase &PM) {
+  PM.add(polly::createRewriteByrefParamsPass());
   PM.add(llvm::createPromoteMemoryToRegisterPass());
   PM.add(llvm::createInstructionCombiningPass());
   PM.add(llvm::createCFGSimplificationPass());
   PM.add(llvm::createTailCallEliminationPass());
   PM.add(llvm::createCFGSimplificationPass());
   PM.add(llvm::createReassociatePass());
   PM.add(llvm::createLoopRotatePass());
   if (PollyInliner) {

lib/Transform/RewriteByReferenceParameters.cpp

+//===------ RewriteByReferenceParameters.cpp --------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass introduces separate 'alloca' instructions for read-only
+// by-reference function parameters to indicate that these paramters are
+// read-only. After this transformation -mem2reg has more freedom to promote
+// variables to registers, which allows SCEV to work in more cases.
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/LinkAllPasses.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/PassManager.h"
+
+#define DEBUG_TYPE "polly-rewrite-byref-params"
+
+using namespace llvm;
+
+namespace {
+
+class RewriteByrefParams : public FunctionPass {
+private:
+  RewriteByrefParams(const RewriteByrefParams &) = delete;
+  const RewriteByrefParams &operator=(const RewriteByrefParams &) = delete;
+
+public:
+  static char ID;
+  explicit RewriteByrefParams() : FunctionPass(ID) {}
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {}
+
+  void tryRewriteInstruction(Instruction &Inst) {
+    BasicBlock *Entry = &Inst.getParent()->getParent()->getEntryBlock();
+
+    if (Inst.getParent() == Entry)
+      return;
+
+    auto *Call = dyn_cast<CallInst>(&Inst);
+
+    if (!Call)
+      return;
+
+    llvm::Function *F = Call->getCalledFunction();
+
+    if (!F)
+      return;
+
+    // We currently match for a very specific function. In case this proofs
+    // useful, we can make this code dependent on readonly metadata.
+    if (!F->hasName() || F->getName() != "_gfortran_transfer_integer_write")
+      return;
+
+    auto *BitCast = dyn_cast<BitCastInst>(Call->getOperand(1));
+
+    if (!BitCast)
+      return;
+
+    auto *Alloca = dyn_cast<AllocaInst>(BitCast->getOperand(0));
+
+    if (!Alloca)
+      return;
+
+    auto NewAlloca =
+        new AllocaInst(Alloca->getType()->getElementType(), 0,
+                       "polly_byref_alloca", Entry->getTerminator());
+
+    auto *LoadedVal = new LoadInst(Alloca, "polly_byref_load", &Inst);
+    new StoreInst(LoadedVal, NewAlloca, &Inst);
+    auto *NewBitCast = new BitCastInst(NewAlloca, BitCast->getType(),
+                                       "polly_byref_cast", &Inst);
+    Call->setOperand(1, NewBitCast);
+  }
+
+  virtual bool runOnFunction(Function &F) override {
+    for (BasicBlock &BB : F)
+      for (Instruction &Inst : BB)
+        tryRewriteInstruction(Inst);
+
+    return true;
+  }
+};
+
+char RewriteByrefParams::ID;
+} // anonymous namespace
+
+Pass *polly::createRewriteByrefParamsPass() { return new RewriteByrefParams(); }
+
+INITIALIZE_PASS_BEGIN(RewriteByrefParams, "polly-rewrite-byref-params",
+                      "Polly - Rewrite by reference parameters", false, false)
+INITIALIZE_PASS_END(RewriteByrefParams, "polly-rewrite-byref-params",
+                    "Polly - Rewrite by reference parameters", false, false)

test/RewriteByReferenceParameters/fortran_io.ll

+; RUN: opt %loadPolly -polly-rewrite-byref-params -S < %s \
+; RUN: | FileCheck %s
+
+
+; Verify that we rewrite the read-only by-reference into a separate alloca slot.
+; This is useful in case %j3 is an induction variable, which should be promoted
+; by -mem2reg into a register.
+
+; CHECK: define void @foo(%struct.__st_parameter_dt* %p) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %j3 = alloca i32, align 4
+; CHECK-NEXT:   %tmp = bitcast i32* %j3 to i8*
+; CHECK-NEXT:   %polly_byref_alloca = alloca i32
+; CHECK-NEXT:   br label %bb
+
+; CHECK: bb:                                               ; preds = %entry
+; CHECK-NEXT:   %polly_byref_load = load i32, i32* %j3
+; CHECK-NEXT:   store i32 %polly_byref_load, i32* %polly_byref_alloca
+; CHECK-NEXT:   %polly_byref_cast = bitcast i32* %polly_byref_alloca to i8*
+; CHECK-NEXT:   call void @_gfortran_transfer_integer_write(%struct.__st_parameter_dt* %p, i8* %polly_byref_cast, i32 4)
+; CHECK-NEXT:   ret void
+; CHECK-NEXT: }
+
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64: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"
+
+%struct.__st_parameter_dt = type { %struct.__st_parameter_common, i64, i64*, i64*, i8*, i8*, i32, i32, i8*, i8*, i32, i32, i8*, [256 x i8], i32*, i64, i8*, i32, i32, i8*, i8*, i32, i32, i8*, i8*, i32, i32, i8*, i8*, i32, [4 x i8] }
+%struct.__st_parameter_common = type { i32, i32, i8*, i32, i32, i8*, i32* }
+
+declare void @_gfortran_transfer_integer_write(%struct.__st_parameter_dt*, i8*, i32)
+
+define void @foo(%struct.__st_parameter_dt* %p) {
+entry:
+  %j3 = alloca i32, align 4
+  %tmp = bitcast i32* %j3 to i8*
+  br label %bb
+
+bb:
+  call void @_gfortran_transfer_integer_write(%struct.__st_parameter_dt* %p, i8* %tmp, i32 4)
+  ret void
+}