polly/lib/CodeGen/LoopGenerators.cpp

   1 //===------ LoopGenerators.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 scalar loops and orchestrate the
  10 // creation of parallel loops as LLVM-IR.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "polly/CodeGen/LoopGenerators.h"
  15 #include "polly/Options.h"
  16 #include "polly/ScopDetection.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/IR/DataLayout.h"
  19 #include "llvm/IR/DebugInfoMetadata.h"
  20 #include "llvm/IR/Dominators.h"
  21 #include "llvm/IR/Module.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  24
  25 using namespace llvm;
  26 using namespace polly;
  27
  28 int polly::PollyNumThreads;
  29 OMPGeneralSchedulingType polly::PollyScheduling;
  30 int polly::PollyChunkSize;
  31
  32 static cl::opt<int, true>
  33     XPollyNumThreads("polly-num-threads",
  34                      cl::desc("Number of threads to use (0 = auto)"),
  35                      cl::Hidden, cl::location(polly::PollyNumThreads),
  36                      cl::init(0), cl::cat(PollyCategory));
  37
  38 static cl::opt<OMPGeneralSchedulingType, true> XPollyScheduling(
  39     "polly-scheduling",
  40     cl::desc("Scheduling type of parallel OpenMP for loops"),
  41     cl::values(clEnumValN(OMPGeneralSchedulingType::StaticChunked, "static",
  42                           "Static scheduling"),
  43                clEnumValN(OMPGeneralSchedulingType::Dynamic, "dynamic",
  44                           "Dynamic scheduling"),
  45                clEnumValN(OMPGeneralSchedulingType::Guided, "guided",
  46                           "Guided scheduling"),
  47                clEnumValN(OMPGeneralSchedulingType::Runtime, "runtime",
  48                           "Runtime determined (OMP_SCHEDULE)")),
  49     cl::Hidden, cl::location(polly::PollyScheduling),
  50     cl::init(OMPGeneralSchedulingType::Runtime), cl::Optional,
  51     cl::cat(PollyCategory));
  52
  53 static cl::opt<int, true>
  54     XPollyChunkSize("polly-scheduling-chunksize",
  55                     cl::desc("Chunksize to use by the OpenMP runtime calls"),
  56                     cl::Hidden, cl::location(polly::PollyChunkSize),
  57                     cl::init(0), cl::Optional, cl::cat(PollyCategory));
  58
  59 // We generate a loop of either of the following structures:
  60 //
  61 //              BeforeBB                      BeforeBB
  62 //                 |                             |
  63 //                 v                             v
  64 //              GuardBB                      PreHeaderBB
  65 //              /      |                         |   _____
  66 //     __  PreHeaderBB  |                        v  \/    |
  67 //    /  \    /         |                     HeaderBB  latch
  68 // latch  HeaderBB      |                        |\       |
  69 //    \  /    \         /                        | \------/
  70 //     <       \       /                         |
  71 //              \     /                          v
  72 //              ExitBB                         ExitBB
  73 //
  74 // depending on whether or not we know that it is executed at least once. If
  75 // not, GuardBB checks if the loop is executed at least once. If this is the
  76 // case we branch to PreHeaderBB and subsequently to the HeaderBB, which
  77 // contains the loop iv 'polly.indvar', the incremented loop iv
  78 // 'polly.indvar_next' as well as the condition to check if we execute another
  79 // iteration of the loop. After the loop has finished, we branch to ExitBB.
  80 // We expect the type of UB, LB, UB+Stride to be large enough for values that
  81 // UB may take throughout the execution of the loop, including the computation
  82 // of indvar + Stride before the final abort.
  83 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
  84                          PollyIRBuilder &Builder, LoopInfo &LI,
  85                          DominatorTree &DT, BasicBlock *&ExitBB,
  86                          ICmpInst::Predicate Predicate,
  87                          ScopAnnotator *Annotator, bool Parallel, bool UseGuard,
  88                          bool LoopVectDisabled) {
  89   Function *F = Builder.GetInsertBlock()->getParent();
  90   LLVMContext &Context = F->getContext();
  91
  92   assert(LB->getType() == UB->getType() && "Types of loop bounds do not match");
  93   IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
  94   assert(LoopIVType && "UB is not integer?");
  95
  96   BasicBlock *BeforeBB = Builder.GetInsertBlock();
  97   BasicBlock *GuardBB =
  98       UseGuard ? BasicBlock::Create(Context, "polly.loop_if", F) : nullptr;
  99   BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F);
 100   BasicBlock *PreHeaderBB =
 101       BasicBlock::Create(Context, "polly.loop_preheader", F);
 102
 103   // Update LoopInfo
 104   Loop *OuterLoop = LI.getLoopFor(BeforeBB);
 105   Loop *NewLoop = LI.AllocateLoop();
 106
 107   if (OuterLoop)
 108     OuterLoop->addChildLoop(NewLoop);
 109   else
 110     LI.addTopLevelLoop(NewLoop);
 111
 112   if (OuterLoop) {
 113     if (GuardBB)
 114       OuterLoop->addBasicBlockToLoop(GuardBB, LI);
 115     OuterLoop->addBasicBlockToLoop(PreHeaderBB, LI);
 116   }
 117
 118   NewLoop->addBasicBlockToLoop(HeaderBB, LI);
 119
 120   // Notify the annotator (if present) that we have a new loop, but only
 121   // after the header block is set.
 122   if (Annotator)
 123     Annotator->pushLoop(NewLoop, Parallel);
 124
 125   // ExitBB
 126   ExitBB = SplitBlock(BeforeBB, &*Builder.GetInsertPoint(), &DT, &LI);
 127   ExitBB->setName("polly.loop_exit");
 128
 129   // BeforeBB
 130   if (GuardBB) {
 131     BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
 132     DT.addNewBlock(GuardBB, BeforeBB);
 133
 134     // GuardBB
 135     Builder.SetInsertPoint(GuardBB);
 136     Value *LoopGuard;
 137     LoopGuard = Builder.CreateICmp(Predicate, LB, UB);
 138     LoopGuard->setName("polly.loop_guard");
 139     Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB);
 140     DT.addNewBlock(PreHeaderBB, GuardBB);
 141   } else {
 142     BeforeBB->getTerminator()->setSuccessor(0, PreHeaderBB);
 143     DT.addNewBlock(PreHeaderBB, BeforeBB);
 144   }
 145
 146   // PreHeaderBB
 147   Builder.SetInsertPoint(PreHeaderBB);
 148   Builder.CreateBr(HeaderBB);
 149
 150   // HeaderBB
 151   DT.addNewBlock(HeaderBB, PreHeaderBB);
 152   Builder.SetInsertPoint(HeaderBB);
 153   PHINode *IV = Builder.CreatePHI(LoopIVType, 2, "polly.indvar");
 154   IV->addIncoming(LB, PreHeaderBB);
 155   Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType);
 156   Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride, "polly.indvar_next");
 157   Value *LoopCondition =
 158       Builder.CreateICmp(Predicate, IncrementedIV, UB, "polly.loop_cond");
 159
 160   // Create the loop latch and annotate it as such.
 161   BranchInst *B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
 162   if (Annotator)
 163     Annotator->annotateLoopLatch(B, NewLoop, Parallel, LoopVectDisabled);
 164
 165   IV->addIncoming(IncrementedIV, HeaderBB);
 166   if (GuardBB)
 167     DT.changeImmediateDominator(ExitBB, GuardBB);
 168   else
 169     DT.changeImmediateDominator(ExitBB, HeaderBB);
 170
 171   // The loop body should be added here.
 172   Builder.SetInsertPoint(HeaderBB->getFirstNonPHI());
 173   return IV;
 174 }
 175
 176 Value *ParallelLoopGenerator::createParallelLoop(
 177     Value *LB, Value *UB, Value *Stride, SetVector<Value *> &UsedValues,
 178     ValueMapT &Map, BasicBlock::iterator *LoopBody) {
 179
 180   AllocaInst *Struct = storeValuesIntoStruct(UsedValues);
 181   BasicBlock::iterator BeforeLoop = Builder.GetInsertPoint();
 182
 183   Value *IV;
 184   Function *SubFn;
 185   std::tie(IV, SubFn) = createSubFn(Stride, Struct, UsedValues, Map);
 186   *LoopBody = Builder.GetInsertPoint();
 187   Builder.SetInsertPoint(&*BeforeLoop);
 188
 189   // Add one as the upper bound provided by OpenMP is a < comparison
 190   // whereas the codegenForSequential function creates a <= comparison.
 191   UB = Builder.CreateAdd(UB, ConstantInt::get(LongType, 1));
 192
 193   // Execute the prepared subfunction in parallel.
 194   deployParallelExecution(SubFn, Struct, LB, UB, Stride);
 195
 196   return IV;
 197 }
 198
 199 Function *ParallelLoopGenerator::createSubFnDefinition() {
 200   Function *F = Builder.GetInsertBlock()->getParent();
 201   Function *SubFn = prepareSubFnDefinition(F);
 202
 203   // Certain backends (e.g., NVPTX) do not support '.'s in function names.
 204   // Hence, we ensure that all '.'s are replaced by '_'s.
 205   std::string FunctionName = SubFn->getName().str();
 206   std::replace(FunctionName.begin(), FunctionName.end(), '.', '_');
 207   SubFn->setName(FunctionName);
 208
 209   // Do not run any polly pass on the new function.
 210   SubFn->addFnAttr(PollySkipFnAttr);
 211
 212   return SubFn;
 213 }
 214
 215 AllocaInst *
 216 ParallelLoopGenerator::storeValuesIntoStruct(SetVector<Value *> &Values) {
 217   SmallVector<Type *, 8> Members;
 218
 219   for (Value *V : Values)
 220     Members.push_back(V->getType());
 221
 222   const DataLayout &DL = Builder.GetInsertBlock()->getModule()->getDataLayout();
 223
 224   // We do not want to allocate the alloca inside any loop, thus we allocate it
 225   // in the entry block of the function and use annotations to denote the actual
 226   // live span (similar to clang).
 227   BasicBlock &EntryBB = Builder.GetInsertBlock()->getParent()->getEntryBlock();
 228   BasicBlock::iterator IP = EntryBB.getFirstInsertionPt();
 229   StructType *Ty = StructType::get(Builder.getContext(), Members);
 230   AllocaInst *Struct = new AllocaInst(Ty, DL.getAllocaAddrSpace(), nullptr,
 231                                       "polly.par.userContext", IP);
 232
 233   for (unsigned i = 0; i < Values.size(); i++) {
 234     Value *Address = Builder.CreateStructGEP(Ty, Struct, i);
 235     Address->setName("polly.subfn.storeaddr." + Values[i]->getName());
 236     Builder.CreateStore(Values[i], Address);
 237   }
 238
 239   return Struct;
 240 }
 241
 242 void ParallelLoopGenerator::extractValuesFromStruct(
 243     SetVector<Value *> OldValues, Type *Ty, Value *Struct, ValueMapT &Map) {
 244   for (unsigned i = 0; i < OldValues.size(); i++) {
 245     Value *Address = Builder.CreateStructGEP(Ty, Struct, i);
 246     Type *ElemTy = cast<GetElementPtrInst>(Address)->getResultElementType();
 247     Value *NewValue = Builder.CreateLoad(ElemTy, Address);
 248     NewValue->setName("polly.subfunc.arg." + OldValues[i]->getName());
 249     Map[OldValues[i]] = NewValue;
 250   }
 251 }
 252
 253 DebugLoc polly::createDebugLocForGeneratedCode(Function *F) {
 254   if (!F)
 255     return DebugLoc();
 256
 257   LLVMContext &Ctx = F->getContext();
 258   DISubprogram *DILScope =
 259       dyn_cast_or_null<DISubprogram>(F->getMetadata(LLVMContext::MD_dbg));
 260   if (!DILScope)
 261     return DebugLoc();
 262   return DILocation::get(Ctx, 0, 0, DILScope);
 263 }