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