1 //===------ LoopGenerators.cpp - IR helper to create loops ---------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains functions to create scalar and parallel loops as LLVM-IR. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "polly/ScopDetection.h" 15 #include "polly/CodeGen/LoopGenerators.h" 16 #include "llvm/Analysis/LoopInfo.h" 17 #include "llvm/IR/DataLayout.h" 18 #include "llvm/IR/Dominators.h" 19 #include "llvm/IR/Module.h" 20 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 21 #include "llvm/Support/CommandLine.h" 22 23 using namespace llvm; 24 using namespace polly; 25 26 static cl::opt<int> 27 PollyNumThreads("polly-num-threads", 28 cl::desc("Number of threads to use (0 = auto)"), cl::Hidden, 29 cl::init(0)); 30 31 // We generate a loop of either of the following structures: 32 // 33 // BeforeBB BeforeBB 34 // | | 35 // v v 36 // GuardBB PreHeaderBB 37 // / | | _____ 38 // __ PreHeaderBB | v \/ | 39 // / \ / | HeaderBB latch 40 // latch HeaderBB | |\ | 41 // \ / \ / | \------/ 42 // < \ / | 43 // \ / v 44 // ExitBB ExitBB 45 // 46 // depending on whether or not we know that it is executed at least once. If 47 // not, GuardBB checks if the loop is executed at least once. If this is the 48 // case we branch to PreHeaderBB and subsequently to the HeaderBB, which 49 // contains the loop iv 'polly.indvar', the incremented loop iv 50 // 'polly.indvar_next' as well as the condition to check if we execute another 51 // iteration of the loop. After the loop has finished, we branch to ExitBB. 52 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride, 53 PollyIRBuilder &Builder, Pass *P, LoopInfo &LI, 54 DominatorTree &DT, BasicBlock *&ExitBB, 55 ICmpInst::Predicate Predicate, 56 ScopAnnotator *Annotator, bool Parallel, 57 bool UseGuard) { 58 Function *F = Builder.GetInsertBlock()->getParent(); 59 LLVMContext &Context = F->getContext(); 60 61 assert(LB->getType() == UB->getType() && "Types of loop bounds do not match"); 62 IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType()); 63 assert(LoopIVType && "UB is not integer?"); 64 65 BasicBlock *BeforeBB = Builder.GetInsertBlock(); 66 BasicBlock *GuardBB = 67 UseGuard ? BasicBlock::Create(Context, "polly.loop_if", F) : nullptr; 68 BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F); 69 BasicBlock *PreHeaderBB = 70 BasicBlock::Create(Context, "polly.loop_preheader", F); 71 72 // Update LoopInfo 73 Loop *OuterLoop = LI.getLoopFor(BeforeBB); 74 Loop *NewLoop = new Loop(); 75 76 if (OuterLoop) 77 OuterLoop->addChildLoop(NewLoop); 78 else 79 LI.addTopLevelLoop(NewLoop); 80 81 if (OuterLoop) { 82 if (GuardBB) 83 OuterLoop->addBasicBlockToLoop(GuardBB, LI); 84 OuterLoop->addBasicBlockToLoop(PreHeaderBB, LI); 85 } 86 87 NewLoop->addBasicBlockToLoop(HeaderBB, LI); 88 89 // Notify the annotator (if present) that we have a new loop, but only 90 // after the header block is set. 91 if (Annotator) 92 Annotator->pushLoop(NewLoop, Parallel); 93 94 // ExitBB 95 ExitBB = SplitBlock(BeforeBB, Builder.GetInsertPoint()++, &DT, &LI); 96 ExitBB->setName("polly.loop_exit"); 97 98 // BeforeBB 99 if (GuardBB) { 100 BeforeBB->getTerminator()->setSuccessor(0, GuardBB); 101 DT.addNewBlock(GuardBB, BeforeBB); 102 103 // GuardBB 104 Builder.SetInsertPoint(GuardBB); 105 Value *LoopGuard; 106 LoopGuard = Builder.CreateICmp(Predicate, LB, UB); 107 LoopGuard->setName("polly.loop_guard"); 108 Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB); 109 DT.addNewBlock(PreHeaderBB, GuardBB); 110 } else { 111 BeforeBB->getTerminator()->setSuccessor(0, PreHeaderBB); 112 DT.addNewBlock(PreHeaderBB, BeforeBB); 113 } 114 115 // PreHeaderBB 116 Builder.SetInsertPoint(PreHeaderBB); 117 Builder.CreateBr(HeaderBB); 118 119 // HeaderBB 120 DT.addNewBlock(HeaderBB, PreHeaderBB); 121 Builder.SetInsertPoint(HeaderBB); 122 PHINode *IV = Builder.CreatePHI(LoopIVType, 2, "polly.indvar"); 123 IV->addIncoming(LB, PreHeaderBB); 124 Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType); 125 Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride, "polly.indvar_next"); 126 Value *LoopCondition; 127 UB = Builder.CreateSub(UB, Stride, "polly.adjust_ub"); 128 LoopCondition = Builder.CreateICmp(Predicate, IV, UB); 129 LoopCondition->setName("polly.loop_cond"); 130 131 // Create the loop latch and annotate it as such. 132 BranchInst *B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB); 133 if (Annotator) 134 Annotator->annotateLoopLatch(B, NewLoop, Parallel); 135 136 IV->addIncoming(IncrementedIV, HeaderBB); 137 if (GuardBB) 138 DT.changeImmediateDominator(ExitBB, GuardBB); 139 else 140 DT.changeImmediateDominator(ExitBB, HeaderBB); 141 142 // The loop body should be added here. 143 Builder.SetInsertPoint(HeaderBB->getFirstNonPHI()); 144 return IV; 145 } 146 147 Value *ParallelLoopGenerator::createParallelLoop( 148 Value *LB, Value *UB, Value *Stride, SetVector<Value *> &UsedValues, 149 ValueToValueMapTy &Map, BasicBlock::iterator *LoopBody) { 150 Value *Struct, *IV, *SubFnParam; 151 Function *SubFn; 152 153 Struct = storeValuesIntoStruct(UsedValues); 154 155 BasicBlock::iterator BeforeLoop = Builder.GetInsertPoint(); 156 IV = createSubFn(Stride, Struct, UsedValues, Map, &SubFn); 157 *LoopBody = Builder.GetInsertPoint(); 158 Builder.SetInsertPoint(BeforeLoop); 159 160 SubFnParam = Builder.CreateBitCast(Struct, Builder.getInt8PtrTy(), 161 "polly.par.userContext"); 162 163 // Add one as the upper bound provided by openmp is a < comparison 164 // whereas the codegenForSequential function creates a <= comparison. 165 UB = Builder.CreateAdd(UB, ConstantInt::get(LongType, 1)); 166 167 // Tell the runtime we start a parallel loop 168 createCallSpawnThreads(SubFn, SubFnParam, LB, UB, Stride); 169 Builder.CreateCall(SubFn, SubFnParam); 170 createCallJoinThreads(); 171 172 // Mark the end of the lifetime for the parameter struct. 173 Type *Ty = Struct->getType(); 174 ConstantInt *SizeOf = Builder.getInt64(DL.getTypeAllocSize(Ty)); 175 Builder.CreateLifetimeEnd(Struct, SizeOf); 176 177 return IV; 178 } 179 180 void ParallelLoopGenerator::createCallSpawnThreads(Value *SubFn, 181 Value *SubFnParam, Value *LB, 182 Value *UB, Value *Stride) { 183 const std::string Name = "GOMP_parallel_loop_runtime_start"; 184 185 Function *F = M->getFunction(Name); 186 187 // If F is not available, declare it. 188 if (!F) { 189 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage; 190 191 Type *Params[] = {PointerType::getUnqual(FunctionType::get( 192 Builder.getVoidTy(), Builder.getInt8PtrTy(), false)), 193 Builder.getInt8PtrTy(), Builder.getInt32Ty(), LongType, 194 LongType, LongType}; 195 196 FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), Params, false); 197 F = Function::Create(Ty, Linkage, Name, M); 198 } 199 200 Value *NumberOfThreads = Builder.getInt32(PollyNumThreads); 201 Value *Args[] = {SubFn, SubFnParam, NumberOfThreads, LB, UB, Stride}; 202 203 Builder.CreateCall(F, Args); 204 } 205 206 Value *ParallelLoopGenerator::createCallGetWorkItem(Value *LBPtr, 207 Value *UBPtr) { 208 const std::string Name = "GOMP_loop_runtime_next"; 209 210 Function *F = M->getFunction(Name); 211 212 // If F is not available, declare it. 213 if (!F) { 214 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage; 215 Type *Params[] = {LongType->getPointerTo(), LongType->getPointerTo()}; 216 FunctionType *Ty = FunctionType::get(Builder.getInt8Ty(), Params, false); 217 F = Function::Create(Ty, Linkage, Name, M); 218 } 219 220 Value *Args[] = {LBPtr, UBPtr}; 221 Value *Return = Builder.CreateCall(F, Args); 222 Return = Builder.CreateICmpNE( 223 Return, Builder.CreateZExt(Builder.getFalse(), Return->getType())); 224 return Return; 225 } 226 227 void ParallelLoopGenerator::createCallJoinThreads() { 228 const std::string Name = "GOMP_parallel_end"; 229 230 Function *F = M->getFunction(Name); 231 232 // If F is not available, declare it. 233 if (!F) { 234 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage; 235 236 FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false); 237 F = Function::Create(Ty, Linkage, Name, M); 238 } 239 240 Builder.CreateCall(F); 241 } 242 243 void ParallelLoopGenerator::createCallCleanupThread() { 244 const std::string Name = "GOMP_loop_end_nowait"; 245 246 Function *F = M->getFunction(Name); 247 248 // If F is not available, declare it. 249 if (!F) { 250 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage; 251 252 FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false); 253 F = Function::Create(Ty, Linkage, Name, M); 254 } 255 256 Builder.CreateCall(F); 257 } 258 259 Function *ParallelLoopGenerator::createSubFnDefinition() { 260 Function *F = Builder.GetInsertBlock()->getParent(); 261 std::vector<Type *> Arguments(1, Builder.getInt8PtrTy()); 262 FunctionType *FT = FunctionType::get(Builder.getVoidTy(), Arguments, false); 263 Function *SubFn = Function::Create(FT, Function::InternalLinkage, 264 F->getName() + ".polly.subfn", M); 265 266 // Do not run any polly pass on the new function. 267 SubFn->addFnAttr(PollySkipFnAttr); 268 269 Function::arg_iterator AI = SubFn->arg_begin(); 270 AI->setName("polly.par.userContext"); 271 272 return SubFn; 273 } 274 275 Value * 276 ParallelLoopGenerator::storeValuesIntoStruct(SetVector<Value *> &Values) { 277 SmallVector<Type *, 8> Members; 278 279 for (Value *V : Values) 280 Members.push_back(V->getType()); 281 282 // We do not want to allocate the alloca inside any loop, thus we allocate it 283 // in the entry block of the function and use annotations to denote the actual 284 // live span (similar to clang). 285 BasicBlock &EntryBB = Builder.GetInsertBlock()->getParent()->getEntryBlock(); 286 Instruction *IP = EntryBB.getFirstInsertionPt(); 287 StructType *Ty = StructType::get(Builder.getContext(), Members); 288 Value *Struct = new AllocaInst(Ty, 0, "polly.par.userContext", IP); 289 290 // Mark the start of the lifetime for the parameter struct. 291 ConstantInt *SizeOf = Builder.getInt64(DL.getTypeAllocSize(Ty)); 292 Builder.CreateLifetimeStart(Struct, SizeOf); 293 294 for (unsigned i = 0; i < Values.size(); i++) { 295 Value *Address = Builder.CreateStructGEP(Struct, i); 296 Builder.CreateStore(Values[i], Address); 297 } 298 299 return Struct; 300 } 301 302 void ParallelLoopGenerator::extractValuesFromStruct( 303 SetVector<Value *> OldValues, Value *Struct, ValueToValueMapTy &Map) { 304 for (unsigned i = 0; i < OldValues.size(); i++) { 305 Value *Address = Builder.CreateStructGEP(Struct, i); 306 Value *NewValue = Builder.CreateLoad(Address); 307 Map[OldValues[i]] = NewValue; 308 } 309 } 310 311 Value *ParallelLoopGenerator::createSubFn(Value *Stride, Value *StructData, 312 SetVector<Value *> Data, 313 ValueToValueMapTy &Map, 314 Function **SubFnPtr) { 315 BasicBlock *PrevBB, *HeaderBB, *ExitBB, *CheckNextBB, *PreHeaderBB, *AfterBB; 316 Value *LBPtr, *UBPtr, *UserContext, *Ret1, *HasNextSchedule, *LB, *UB, *IV; 317 Function *SubFn = createSubFnDefinition(); 318 LLVMContext &Context = SubFn->getContext(); 319 320 // Store the previous basic block. 321 PrevBB = Builder.GetInsertBlock(); 322 323 // Create basic blocks. 324 HeaderBB = BasicBlock::Create(Context, "polly.par.setup", SubFn); 325 ExitBB = BasicBlock::Create(Context, "polly.par.exit", SubFn); 326 CheckNextBB = BasicBlock::Create(Context, "polly.par.checkNext", SubFn); 327 PreHeaderBB = BasicBlock::Create(Context, "polly.par.loadIVBounds", SubFn); 328 329 DT.addNewBlock(HeaderBB, PrevBB); 330 DT.addNewBlock(ExitBB, HeaderBB); 331 DT.addNewBlock(CheckNextBB, HeaderBB); 332 DT.addNewBlock(PreHeaderBB, HeaderBB); 333 334 // Fill up basic block HeaderBB. 335 Builder.SetInsertPoint(HeaderBB); 336 LBPtr = Builder.CreateAlloca(LongType, 0, "polly.par.LBPtr"); 337 UBPtr = Builder.CreateAlloca(LongType, 0, "polly.par.UBPtr"); 338 UserContext = Builder.CreateBitCast(SubFn->arg_begin(), StructData->getType(), 339 "polly.par.userContext"); 340 341 extractValuesFromStruct(Data, UserContext, Map); 342 Builder.CreateBr(CheckNextBB); 343 344 // Add code to check if another set of iterations will be executed. 345 Builder.SetInsertPoint(CheckNextBB); 346 Ret1 = createCallGetWorkItem(LBPtr, UBPtr); 347 HasNextSchedule = Builder.CreateTrunc(Ret1, Builder.getInt1Ty(), 348 "polly.par.hasNextScheduleBlock"); 349 Builder.CreateCondBr(HasNextSchedule, PreHeaderBB, ExitBB); 350 351 // Add code to to load the iv bounds for this set of iterations. 352 Builder.SetInsertPoint(PreHeaderBB); 353 LB = Builder.CreateLoad(LBPtr, "polly.par.LB"); 354 UB = Builder.CreateLoad(UBPtr, "polly.par.UB"); 355 356 // Subtract one as the upper bound provided by openmp is a < comparison 357 // whereas the codegenForSequential function creates a <= comparison. 358 UB = Builder.CreateSub(UB, ConstantInt::get(LongType, 1), 359 "polly.par.UBAdjusted"); 360 361 Builder.CreateBr(CheckNextBB); 362 Builder.SetInsertPoint(--Builder.GetInsertPoint()); 363 IV = createLoop(LB, UB, Stride, Builder, P, LI, DT, AfterBB, 364 ICmpInst::ICMP_SLE, nullptr, true, /* UseGuard */ false); 365 366 BasicBlock::iterator LoopBody = Builder.GetInsertPoint(); 367 368 // Add code to terminate this subfunction. 369 Builder.SetInsertPoint(ExitBB); 370 createCallCleanupThread(); 371 Builder.CreateRetVoid(); 372 373 Builder.SetInsertPoint(LoopBody); 374 *SubFnPtr = SubFn; 375 376 return IV; 377 } 378