polly/lib/CodeGen/LoopGeneratorsGOMP.cpp

   1 //===------ LoopGeneratorsGOMP.cpp - IR helper to create loops ------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains functions to create parallel loops as LLVM-IR.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "polly/CodeGen/LoopGeneratorsGOMP.h"
  14 #include "llvm/IR/Dominators.h"
  15 #include "llvm/IR/Module.h"
  16
  17 using namespace llvm;
  18 using namespace polly;
  19
  20 void ParallelLoopGeneratorGOMP::createCallSpawnThreads(Value *SubFn,
  21                                                        Value *SubFnParam,
  22                                                        Value *LB, Value *UB,
  23                                                        Value *Stride) {
  24   const std::string Name = "GOMP_parallel_loop_runtime_start";
  25
  26   Function *F = M->getFunction(Name);
  27
  28   // If F is not available, declare it.
  29   if (!F) {
  30     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
  31
  32     Type *Params[] = {PointerType::getUnqual(FunctionType::get(
  33                           Builder.getVoidTy(), Builder.getPtrTy(), false)),
  34                       Builder.getPtrTy(),
  35                       Builder.getInt32Ty(),
  36                       LongType,
  37                       LongType,
  38                       LongType};
  39
  40     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), Params, false);
  41     F = Function::Create(Ty, Linkage, Name, M);
  42   }
  43
  44   Value *Args[] = {SubFn, SubFnParam, Builder.getInt32(PollyNumThreads),
  45                    LB,    UB,         Stride};
  46
  47   CallInst *Call = Builder.CreateCall(F, Args);
  48   Call->setDebugLoc(DLGenerated);
  49 }
  50
  51 void ParallelLoopGeneratorGOMP::deployParallelExecution(Function *SubFn,
  52                                                         Value *SubFnParam,
  53                                                         Value *LB, Value *UB,
  54                                                         Value *Stride) {
  55   // Tell the runtime we start a parallel loop
  56   createCallSpawnThreads(SubFn, SubFnParam, LB, UB, Stride);
  57   CallInst *Call = Builder.CreateCall(SubFn, SubFnParam);
  58   Call->setDebugLoc(DLGenerated);
  59   createCallJoinThreads();
  60 }
  61
  62 Function *ParallelLoopGeneratorGOMP::prepareSubFnDefinition(Function *F) const {
  63   FunctionType *FT =
  64       FunctionType::get(Builder.getVoidTy(), {Builder.getPtrTy()}, false);
  65   Function *SubFn = Function::Create(FT, Function::InternalLinkage,
  66                                      F->getName() + "_polly_subfn", M);
  67   // Name the function's arguments
  68   SubFn->arg_begin()->setName("polly.par.userContext");
  69   return SubFn;
  70 }
  71
  72 // Create a subfunction of the following (preliminary) structure:
  73 //
  74 //    PrevBB
  75 //       |
  76 //       v
  77 //    HeaderBB
  78 //       |   _____
  79 //       v  v    |
  80 //   CheckNextBB  PreHeaderBB
  81 //       |\       |
  82 //       | \______/
  83 //       |
  84 //       v
  85 //     ExitBB
  86 //
  87 // HeaderBB will hold allocations and loading of variables.
  88 // CheckNextBB will check for more work.
  89 // If there is more work to do: go to PreHeaderBB, otherwise go to ExitBB.
  90 // PreHeaderBB loads the new boundaries (& will lead to the loop body later on).
  91 // ExitBB marks the end of the parallel execution.
  92 std::tuple<Value *, Function *>
  93 ParallelLoopGeneratorGOMP::createSubFn(Value *Stride, AllocaInst *StructData,
  94                                        SetVector<Value *> Data,
  95                                        ValueMapT &Map) {
  96   if (PollyScheduling != OMPGeneralSchedulingType::Runtime) {
  97     // User tried to influence the scheduling type (currently not supported)
  98     errs() << "warning: Polly's GNU OpenMP backend solely "
  99               "supports the scheduling type 'runtime'.\n";
 100   }
 101
 102   if (PollyChunkSize != 0) {
 103     // User tried to influence the chunk size (currently not supported)
 104     errs() << "warning: Polly's GNU OpenMP backend solely "
 105               "supports the default chunk size.\n";
 106   }
 107
 108   Function *SubFn = createSubFnDefinition();
 109   LLVMContext &Context = SubFn->getContext();
 110
 111   // Store the previous basic block.
 112   BasicBlock *PrevBB = Builder.GetInsertBlock();
 113
 114   // Create basic blocks.
 115   BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.par.setup", SubFn);
 116   BasicBlock *ExitBB = BasicBlock::Create(Context, "polly.par.exit", SubFn);
 117   BasicBlock *CheckNextBB =
 118       BasicBlock::Create(Context, "polly.par.checkNext", SubFn);
 119   BasicBlock *PreHeaderBB =
 120       BasicBlock::Create(Context, "polly.par.loadIVBounds", SubFn);
 121
 122   DT.addNewBlock(HeaderBB, PrevBB);
 123   DT.addNewBlock(ExitBB, HeaderBB);
 124   DT.addNewBlock(CheckNextBB, HeaderBB);
 125   DT.addNewBlock(PreHeaderBB, HeaderBB);
 126
 127   // Fill up basic block HeaderBB.
 128   Builder.SetInsertPoint(HeaderBB);
 129   Value *LBPtr = Builder.CreateAlloca(LongType, nullptr, "polly.par.LBPtr");
 130   Value *UBPtr = Builder.CreateAlloca(LongType, nullptr, "polly.par.UBPtr");
 131   Value *UserContext = &*SubFn->arg_begin();
 132
 133   extractValuesFromStruct(Data, StructData->getAllocatedType(), UserContext,
 134                           Map);
 135   Builder.CreateBr(CheckNextBB);
 136
 137   // Add code to check if another set of iterations will be executed.
 138   Builder.SetInsertPoint(CheckNextBB);
 139   Value *Next = createCallGetWorkItem(LBPtr, UBPtr);
 140   Value *HasNextSchedule = Builder.CreateTrunc(
 141       Next, Builder.getInt1Ty(), "polly.par.hasNextScheduleBlock");
 142   Builder.CreateCondBr(HasNextSchedule, PreHeaderBB, ExitBB);
 143
 144   // Add code to load the iv bounds for this set of iterations.
 145   Builder.SetInsertPoint(PreHeaderBB);
 146   Value *LB = Builder.CreateLoad(LongType, LBPtr, "polly.par.LB");
 147   Value *UB = Builder.CreateLoad(LongType, UBPtr, "polly.par.UB");
 148
 149   // Subtract one as the upper bound provided by OpenMP is a < comparison
 150   // whereas the codegenForSequential function creates a <= comparison.
 151   UB = Builder.CreateSub(UB, ConstantInt::get(LongType, 1),
 152                          "polly.par.UBAdjusted");
 153
 154   Builder.CreateBr(CheckNextBB);
 155   Builder.SetInsertPoint(&*--Builder.GetInsertPoint());
 156   BasicBlock *AfterBB;
 157   Value *IV =
 158       createLoop(LB, UB, Stride, Builder, LI, DT, AfterBB, ICmpInst::ICMP_SLE,
 159                  nullptr, true, /* UseGuard */ false);
 160
 161   BasicBlock::iterator LoopBody = Builder.GetInsertPoint();
 162
 163   // Add code to terminate this subfunction.
 164   Builder.SetInsertPoint(ExitBB);
 165   createCallCleanupThread();
 166   Builder.CreateRetVoid();
 167
 168   Builder.SetInsertPoint(&*LoopBody);
 169
 170   return std::make_tuple(IV, SubFn);
 171 }
 172
 173 Value *ParallelLoopGeneratorGOMP::createCallGetWorkItem(Value *LBPtr,
 174                                                         Value *UBPtr) {
 175   const std::string Name = "GOMP_loop_runtime_next";
 176
 177   Function *F = M->getFunction(Name);
 178
 179   // If F is not available, declare it.
 180   if (!F) {
 181     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
 182     Type *Params[] = {LongType->getPointerTo(), LongType->getPointerTo()};
 183     FunctionType *Ty = FunctionType::get(Builder.getInt8Ty(), Params, false);
 184     F = Function::Create(Ty, Linkage, Name, M);
 185   }
 186
 187   Value *Args[] = {LBPtr, UBPtr};
 188   CallInst *Call = Builder.CreateCall(F, Args);
 189   Call->setDebugLoc(DLGenerated);
 190   Value *Return = Builder.CreateICmpNE(
 191       Call, Builder.CreateZExt(Builder.getFalse(), Call->getType()));
 192   return Return;
 193 }
 194
 195 void ParallelLoopGeneratorGOMP::createCallJoinThreads() {
 196   const std::string Name = "GOMP_parallel_end";
 197
 198   Function *F = M->getFunction(Name);
 199
 200   // If F is not available, declare it.
 201   if (!F) {
 202     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
 203
 204     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
 205     F = Function::Create(Ty, Linkage, Name, M);
 206   }
 207
 208   CallInst *Call = Builder.CreateCall(F, {});
 209   Call->setDebugLoc(DLGenerated);
 210 }
 211
 212 void ParallelLoopGeneratorGOMP::createCallCleanupThread() {
 213   const std::string Name = "GOMP_loop_end_nowait";
 214
 215   Function *F = M->getFunction(Name);
 216
 217   // If F is not available, declare it.
 218   if (!F) {
 219     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
 220
 221     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
 222     F = Function::Create(Ty, Linkage, Name, M);
 223   }
 224
 225   CallInst *Call = Builder.CreateCall(F, {});
 226   Call->setDebugLoc(DLGenerated);
 227 }