1 //===- IR/OpenMPIRBuilder.h - OpenMP encoding builder for LLVM IR - C++ -*-===// 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 defines the OpenMPIRBuilder class and helpers used as a convenient 10 // way to create LLVM instructions for OpenMP directives. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_FRONTEND_OPENMP_OMPIRBUILDER_H 15 #define LLVM_FRONTEND_OPENMP_OMPIRBUILDER_H 16 17 #include "llvm/Frontend/OpenMP/OMPConstants.h" 18 #include "llvm/IR/DebugLoc.h" 19 #include "llvm/IR/IRBuilder.h" 20 #include "llvm/Support/Allocator.h" 21 #include <forward_list> 22 23 namespace llvm { 24 class CanonicalLoopInfo; 25 26 /// Move the instruction after an InsertPoint to the beginning of another 27 /// BasicBlock. 28 /// 29 /// The instructions after \p IP are moved to the beginning of \p New which must 30 /// not have any PHINodes. If \p CreateBranch is true, a branch instruction to 31 /// \p New will be added such that there is no semantic change. Otherwise, the 32 /// \p IP insert block remains degenerate and it is up to the caller to insert a 33 /// terminator. 34 void spliceBB(IRBuilderBase::InsertPoint IP, BasicBlock *New, 35 bool CreateBranch); 36 37 /// Splice a BasicBlock at an IRBuilder's current insertion point. Its new 38 /// insert location will stick to after the instruction before the insertion 39 /// point (instead of moving with the instruction the InsertPoint stores 40 /// internally). 41 void spliceBB(IRBuilder<> &Builder, BasicBlock *New, bool CreateBranch); 42 43 /// Split a BasicBlock at an InsertPoint, even if the block is degenerate 44 /// (missing the terminator). 45 /// 46 /// llvm::SplitBasicBlock and BasicBlock::splitBasicBlock require a well-formed 47 /// BasicBlock. \p Name is used for the new successor block. If \p CreateBranch 48 /// is true, a branch to the new successor will new created such that 49 /// semantically there is no change; otherwise the block of the insertion point 50 /// remains degenerate and it is the caller's responsibility to insert a 51 /// terminator. Returns the new successor block. 52 BasicBlock *splitBB(IRBuilderBase::InsertPoint IP, bool CreateBranch, 53 llvm::Twine Name = {}); 54 55 /// Split a BasicBlock at \p Builder's insertion point, even if the block is 56 /// degenerate (missing the terminator). Its new insert location will stick to 57 /// after the instruction before the insertion point (instead of moving with the 58 /// instruction the InsertPoint stores internally). 59 BasicBlock *splitBB(IRBuilderBase &Builder, bool CreateBranch, 60 llvm::Twine Name = {}); 61 62 /// Split a BasicBlock at \p Builder's insertion point, even if the block is 63 /// degenerate (missing the terminator). Its new insert location will stick to 64 /// after the instruction before the insertion point (instead of moving with the 65 /// instruction the InsertPoint stores internally). 66 BasicBlock *splitBB(IRBuilder<> &Builder, bool CreateBranch, llvm::Twine Name); 67 68 /// Like splitBB, but reuses the current block's name for the new name. 69 BasicBlock *splitBBWithSuffix(IRBuilderBase &Builder, bool CreateBranch, 70 llvm::Twine Suffix = ".split"); 71 72 /// An interface to create LLVM-IR for OpenMP directives. 73 /// 74 /// Each OpenMP directive has a corresponding public generator method. 75 class OpenMPIRBuilder { 76 public: 77 /// Create a new OpenMPIRBuilder operating on the given module \p M. This will 78 /// not have an effect on \p M (see initialize). 79 OpenMPIRBuilder(Module &M) : M(M), Builder(M.getContext()) {} 80 ~OpenMPIRBuilder(); 81 82 /// Initialize the internal state, this will put structures types and 83 /// potentially other helpers into the underlying module. Must be called 84 /// before any other method and only once! 85 void initialize(); 86 87 /// Finalize the underlying module, e.g., by outlining regions. 88 /// \param Fn The function to be finalized. If not used, 89 /// all functions are finalized. 90 void finalize(Function *Fn = nullptr); 91 92 /// Add attributes known for \p FnID to \p Fn. 93 void addAttributes(omp::RuntimeFunction FnID, Function &Fn); 94 95 /// Type used throughout for insertion points. 96 using InsertPointTy = IRBuilder<>::InsertPoint; 97 98 /// Callback type for variable finalization (think destructors). 99 /// 100 /// \param CodeGenIP is the insertion point at which the finalization code 101 /// should be placed. 102 /// 103 /// A finalize callback knows about all objects that need finalization, e.g. 104 /// destruction, when the scope of the currently generated construct is left 105 /// at the time, and location, the callback is invoked. 106 using FinalizeCallbackTy = std::function<void(InsertPointTy CodeGenIP)>; 107 108 struct FinalizationInfo { 109 /// The finalization callback provided by the last in-flight invocation of 110 /// createXXXX for the directive of kind DK. 111 FinalizeCallbackTy FiniCB; 112 113 /// The directive kind of the innermost directive that has an associated 114 /// region which might require finalization when it is left. 115 omp::Directive DK; 116 117 /// Flag to indicate if the directive is cancellable. 118 bool IsCancellable; 119 }; 120 121 /// Push a finalization callback on the finalization stack. 122 /// 123 /// NOTE: Temporary solution until Clang CG is gone. 124 void pushFinalizationCB(const FinalizationInfo &FI) { 125 FinalizationStack.push_back(FI); 126 } 127 128 /// Pop the last finalization callback from the finalization stack. 129 /// 130 /// NOTE: Temporary solution until Clang CG is gone. 131 void popFinalizationCB() { FinalizationStack.pop_back(); } 132 133 /// Callback type for body (=inner region) code generation 134 /// 135 /// The callback takes code locations as arguments, each describing a 136 /// location where additional instructions can be inserted. 137 /// 138 /// The CodeGenIP may be in the middle of a basic block or point to the end of 139 /// it. The basic block may have a terminator or be degenerate. The callback 140 /// function may just insert instructions at that position, but also split the 141 /// block (without the Before argument of BasicBlock::splitBasicBlock such 142 /// that the identify of the split predecessor block is preserved) and insert 143 /// additional control flow, including branches that do not lead back to what 144 /// follows the CodeGenIP. Note that since the callback is allowed to split 145 /// the block, callers must assume that InsertPoints to positions in the 146 /// BasicBlock after CodeGenIP including CodeGenIP itself are invalidated. If 147 /// such InsertPoints need to be preserved, it can split the block itself 148 /// before calling the callback. 149 /// 150 /// AllocaIP and CodeGenIP must not point to the same position. 151 /// 152 /// \param AllocaIP is the insertion point at which new alloca instructions 153 /// should be placed. The BasicBlock it is pointing to must 154 /// not be split. 155 /// \param CodeGenIP is the insertion point at which the body code should be 156 /// placed. 157 using BodyGenCallbackTy = 158 function_ref<void(InsertPointTy AllocaIP, InsertPointTy CodeGenIP)>; 159 160 // This is created primarily for sections construct as llvm::function_ref 161 // (BodyGenCallbackTy) is not storable (as described in the comments of 162 // function_ref class - function_ref contains non-ownable reference 163 // to the callable. 164 using StorableBodyGenCallbackTy = 165 std::function<void(InsertPointTy AllocaIP, InsertPointTy CodeGenIP)>; 166 167 /// Callback type for loop body code generation. 168 /// 169 /// \param CodeGenIP is the insertion point where the loop's body code must be 170 /// placed. This will be a dedicated BasicBlock with a 171 /// conditional branch from the loop condition check and 172 /// terminated with an unconditional branch to the loop 173 /// latch. 174 /// \param IndVar is the induction variable usable at the insertion point. 175 using LoopBodyGenCallbackTy = 176 function_ref<void(InsertPointTy CodeGenIP, Value *IndVar)>; 177 178 /// Callback type for variable privatization (think copy & default 179 /// constructor). 180 /// 181 /// \param AllocaIP is the insertion point at which new alloca instructions 182 /// should be placed. 183 /// \param CodeGenIP is the insertion point at which the privatization code 184 /// should be placed. 185 /// \param Original The value being copied/created, should not be used in the 186 /// generated IR. 187 /// \param Inner The equivalent of \p Original that should be used in the 188 /// generated IR; this is equal to \p Original if the value is 189 /// a pointer and can thus be passed directly, otherwise it is 190 /// an equivalent but different value. 191 /// \param ReplVal The replacement value, thus a copy or new created version 192 /// of \p Inner. 193 /// 194 /// \returns The new insertion point where code generation continues and 195 /// \p ReplVal the replacement value. 196 using PrivatizeCallbackTy = function_ref<InsertPointTy( 197 InsertPointTy AllocaIP, InsertPointTy CodeGenIP, Value &Original, 198 Value &Inner, Value *&ReplVal)>; 199 200 /// Description of a LLVM-IR insertion point (IP) and a debug/source location 201 /// (filename, line, column, ...). 202 struct LocationDescription { 203 LocationDescription(const IRBuilderBase &IRB) 204 : IP(IRB.saveIP()), DL(IRB.getCurrentDebugLocation()) {} 205 LocationDescription(const InsertPointTy &IP) : IP(IP) {} 206 LocationDescription(const InsertPointTy &IP, const DebugLoc &DL) 207 : IP(IP), DL(DL) {} 208 InsertPointTy IP; 209 DebugLoc DL; 210 }; 211 212 /// Emitter methods for OpenMP directives. 213 /// 214 ///{ 215 216 /// Generator for '#omp barrier' 217 /// 218 /// \param Loc The location where the barrier directive was encountered. 219 /// \param DK The kind of directive that caused the barrier. 220 /// \param ForceSimpleCall Flag to force a simple (=non-cancellation) barrier. 221 /// \param CheckCancelFlag Flag to indicate a cancel barrier return value 222 /// should be checked and acted upon. 223 /// 224 /// \returns The insertion point after the barrier. 225 InsertPointTy createBarrier(const LocationDescription &Loc, omp::Directive DK, 226 bool ForceSimpleCall = false, 227 bool CheckCancelFlag = true); 228 229 /// Generator for '#omp cancel' 230 /// 231 /// \param Loc The location where the directive was encountered. 232 /// \param IfCondition The evaluated 'if' clause expression, if any. 233 /// \param CanceledDirective The kind of directive that is cancled. 234 /// 235 /// \returns The insertion point after the barrier. 236 InsertPointTy createCancel(const LocationDescription &Loc, Value *IfCondition, 237 omp::Directive CanceledDirective); 238 239 /// Generator for '#omp parallel' 240 /// 241 /// \param Loc The insert and source location description. 242 /// \param AllocaIP The insertion points to be used for alloca instructions. 243 /// \param BodyGenCB Callback that will generate the region code. 244 /// \param PrivCB Callback to copy a given variable (think copy constructor). 245 /// \param FiniCB Callback to finalize variable copies. 246 /// \param IfCondition The evaluated 'if' clause expression, if any. 247 /// \param NumThreads The evaluated 'num_threads' clause expression, if any. 248 /// \param ProcBind The value of the 'proc_bind' clause (see ProcBindKind). 249 /// \param IsCancellable Flag to indicate a cancellable parallel region. 250 /// 251 /// \returns The insertion position *after* the parallel. 252 IRBuilder<>::InsertPoint 253 createParallel(const LocationDescription &Loc, InsertPointTy AllocaIP, 254 BodyGenCallbackTy BodyGenCB, PrivatizeCallbackTy PrivCB, 255 FinalizeCallbackTy FiniCB, Value *IfCondition, 256 Value *NumThreads, omp::ProcBindKind ProcBind, 257 bool IsCancellable); 258 259 /// Generator for the control flow structure of an OpenMP canonical loop. 260 /// 261 /// This generator operates on the logical iteration space of the loop, i.e. 262 /// the caller only has to provide a loop trip count of the loop as defined by 263 /// base language semantics. The trip count is interpreted as an unsigned 264 /// integer. The induction variable passed to \p BodyGenCB will be of the same 265 /// type and run from 0 to \p TripCount - 1. It is up to the callback to 266 /// convert the logical iteration variable to the loop counter variable in the 267 /// loop body. 268 /// 269 /// \param Loc The insert and source location description. The insert 270 /// location can be between two instructions or the end of a 271 /// degenerate block (e.g. a BB under construction). 272 /// \param BodyGenCB Callback that will generate the loop body code. 273 /// \param TripCount Number of iterations the loop body is executed. 274 /// \param Name Base name used to derive BB and instruction names. 275 /// 276 /// \returns An object representing the created control flow structure which 277 /// can be used for loop-associated directives. 278 CanonicalLoopInfo *createCanonicalLoop(const LocationDescription &Loc, 279 LoopBodyGenCallbackTy BodyGenCB, 280 Value *TripCount, 281 const Twine &Name = "loop"); 282 283 /// Generator for the control flow structure of an OpenMP canonical loop. 284 /// 285 /// Instead of a logical iteration space, this allows specifying user-defined 286 /// loop counter values using increment, upper- and lower bounds. To 287 /// disambiguate the terminology when counting downwards, instead of lower 288 /// bounds we use \p Start for the loop counter value in the first body 289 /// iteration. 290 /// 291 /// Consider the following limitations: 292 /// 293 /// * A loop counter space over all integer values of its bit-width cannot be 294 /// represented. E.g using uint8_t, its loop trip count of 256 cannot be 295 /// stored into an 8 bit integer): 296 /// 297 /// DO I = 0, 255, 1 298 /// 299 /// * Unsigned wrapping is only supported when wrapping only "once"; E.g. 300 /// effectively counting downwards: 301 /// 302 /// for (uint8_t i = 100u; i > 0; i += 127u) 303 /// 304 /// 305 /// TODO: May need to add additional parameters to represent: 306 /// 307 /// * Allow representing downcounting with unsigned integers. 308 /// 309 /// * Sign of the step and the comparison operator might disagree: 310 /// 311 /// for (int i = 0; i < 42; i -= 1u) 312 /// 313 // 314 /// \param Loc The insert and source location description. 315 /// \param BodyGenCB Callback that will generate the loop body code. 316 /// \param Start Value of the loop counter for the first iterations. 317 /// \param Stop Loop counter values past this will stop the loop. 318 /// \param Step Loop counter increment after each iteration; negative 319 /// means counting down. 320 /// \param IsSigned Whether Start, Stop and Step are signed integers. 321 /// \param InclusiveStop Whether \p Stop itself is a valid value for the loop 322 /// counter. 323 /// \param ComputeIP Insertion point for instructions computing the trip 324 /// count. Can be used to ensure the trip count is available 325 /// at the outermost loop of a loop nest. If not set, 326 /// defaults to the preheader of the generated loop. 327 /// \param Name Base name used to derive BB and instruction names. 328 /// 329 /// \returns An object representing the created control flow structure which 330 /// can be used for loop-associated directives. 331 CanonicalLoopInfo *createCanonicalLoop(const LocationDescription &Loc, 332 LoopBodyGenCallbackTy BodyGenCB, 333 Value *Start, Value *Stop, Value *Step, 334 bool IsSigned, bool InclusiveStop, 335 InsertPointTy ComputeIP = {}, 336 const Twine &Name = "loop"); 337 338 /// Collapse a loop nest into a single loop. 339 /// 340 /// Merges loops of a loop nest into a single CanonicalLoopNest representation 341 /// that has the same number of innermost loop iterations as the origin loop 342 /// nest. The induction variables of the input loops are derived from the 343 /// collapsed loop's induction variable. This is intended to be used to 344 /// implement OpenMP's collapse clause. Before applying a directive, 345 /// collapseLoops normalizes a loop nest to contain only a single loop and the 346 /// directive's implementation does not need to handle multiple loops itself. 347 /// This does not remove the need to handle all loop nest handling by 348 /// directives, such as the ordered(<n>) clause or the simd schedule-clause 349 /// modifier of the worksharing-loop directive. 350 /// 351 /// Example: 352 /// \code 353 /// for (int i = 0; i < 7; ++i) // Canonical loop "i" 354 /// for (int j = 0; j < 9; ++j) // Canonical loop "j" 355 /// body(i, j); 356 /// \endcode 357 /// 358 /// After collapsing with Loops={i,j}, the loop is changed to 359 /// \code 360 /// for (int ij = 0; ij < 63; ++ij) { 361 /// int i = ij / 9; 362 /// int j = ij % 9; 363 /// body(i, j); 364 /// } 365 /// \endcode 366 /// 367 /// In the current implementation, the following limitations apply: 368 /// 369 /// * All input loops have an induction variable of the same type. 370 /// 371 /// * The collapsed loop will have the same trip count integer type as the 372 /// input loops. Therefore it is possible that the collapsed loop cannot 373 /// represent all iterations of the input loops. For instance, assuming a 374 /// 32 bit integer type, and two input loops both iterating 2^16 times, the 375 /// theoretical trip count of the collapsed loop would be 2^32 iteration, 376 /// which cannot be represented in an 32-bit integer. Behavior is undefined 377 /// in this case. 378 /// 379 /// * The trip counts of every input loop must be available at \p ComputeIP. 380 /// Non-rectangular loops are not yet supported. 381 /// 382 /// * At each nest level, code between a surrounding loop and its nested loop 383 /// is hoisted into the loop body, and such code will be executed more 384 /// often than before collapsing (or not at all if any inner loop iteration 385 /// has a trip count of 0). This is permitted by the OpenMP specification. 386 /// 387 /// \param DL Debug location for instructions added for collapsing, 388 /// such as instructions to compute/derive the input loop's 389 /// induction variables. 390 /// \param Loops Loops in the loop nest to collapse. Loops are specified 391 /// from outermost-to-innermost and every control flow of a 392 /// loop's body must pass through its directly nested loop. 393 /// \param ComputeIP Where additional instruction that compute the collapsed 394 /// trip count. If not set, defaults to before the generated 395 /// loop. 396 /// 397 /// \returns The CanonicalLoopInfo object representing the collapsed loop. 398 CanonicalLoopInfo *collapseLoops(DebugLoc DL, 399 ArrayRef<CanonicalLoopInfo *> Loops, 400 InsertPointTy ComputeIP); 401 402 private: 403 /// Modifies the canonical loop to be a statically-scheduled workshare loop. 404 /// 405 /// This takes a \p LoopInfo representing a canonical loop, such as the one 406 /// created by \p createCanonicalLoop and emits additional instructions to 407 /// turn it into a workshare loop. In particular, it calls to an OpenMP 408 /// runtime function in the preheader to obtain the loop bounds to be used in 409 /// the current thread, updates the relevant instructions in the canonical 410 /// loop and calls to an OpenMP runtime finalization function after the loop. 411 /// 412 /// \param DL Debug location for instructions added for the 413 /// workshare-loop construct itself. 414 /// \param CLI A descriptor of the canonical loop to workshare. 415 /// \param AllocaIP An insertion point for Alloca instructions usable in the 416 /// preheader of the loop. 417 /// \param NeedsBarrier Indicates whether a barrier must be inserted after 418 /// the loop. 419 /// 420 /// \returns Point where to insert code after the workshare construct. 421 InsertPointTy applyStaticWorkshareLoop(DebugLoc DL, CanonicalLoopInfo *CLI, 422 InsertPointTy AllocaIP, 423 bool NeedsBarrier); 424 425 /// Modifies the canonical loop a statically-scheduled workshare loop with a 426 /// user-specified chunk size. 427 /// 428 /// \param DL Debug location for instructions added for the 429 /// workshare-loop construct itself. 430 /// \param CLI A descriptor of the canonical loop to workshare. 431 /// \param AllocaIP An insertion point for Alloca instructions usable in 432 /// the preheader of the loop. 433 /// \param NeedsBarrier Indicates whether a barrier must be inserted after the 434 /// loop. 435 /// \param ChunkSize The user-specified chunk size. 436 /// 437 /// \returns Point where to insert code after the workshare construct. 438 InsertPointTy applyStaticChunkedWorkshareLoop(DebugLoc DL, 439 CanonicalLoopInfo *CLI, 440 InsertPointTy AllocaIP, 441 bool NeedsBarrier, 442 Value *ChunkSize); 443 444 /// Modifies the canonical loop to be a dynamically-scheduled workshare loop. 445 /// 446 /// This takes a \p LoopInfo representing a canonical loop, such as the one 447 /// created by \p createCanonicalLoop and emits additional instructions to 448 /// turn it into a workshare loop. In particular, it calls to an OpenMP 449 /// runtime function in the preheader to obtain, and then in each iteration 450 /// to update the loop counter. 451 /// 452 /// \param DL Debug location for instructions added for the 453 /// workshare-loop construct itself. 454 /// \param CLI A descriptor of the canonical loop to workshare. 455 /// \param AllocaIP An insertion point for Alloca instructions usable in the 456 /// preheader of the loop. 457 /// \param SchedType Type of scheduling to be passed to the init function. 458 /// \param NeedsBarrier Indicates whether a barrier must be insterted after 459 /// the loop. 460 /// \param Chunk The size of loop chunk considered as a unit when 461 /// scheduling. If \p nullptr, defaults to 1. 462 /// 463 /// \returns Point where to insert code after the workshare construct. 464 InsertPointTy applyDynamicWorkshareLoop(DebugLoc DL, CanonicalLoopInfo *CLI, 465 InsertPointTy AllocaIP, 466 omp::OMPScheduleType SchedType, 467 bool NeedsBarrier, 468 Value *Chunk = nullptr); 469 470 public: 471 /// Modifies the canonical loop to be a workshare loop. 472 /// 473 /// This takes a \p LoopInfo representing a canonical loop, such as the one 474 /// created by \p createCanonicalLoop and emits additional instructions to 475 /// turn it into a workshare loop. In particular, it calls to an OpenMP 476 /// runtime function in the preheader to obtain the loop bounds to be used in 477 /// the current thread, updates the relevant instructions in the canonical 478 /// loop and calls to an OpenMP runtime finalization function after the loop. 479 /// 480 /// The concrete transformation is done by applyStaticWorkshareLoop, 481 /// applyStaticChunkedWorkshareLoop, or applyDynamicWorkshareLoop, depending 482 /// on the value of \p SchedKind and \p ChunkSize. 483 /// 484 /// \param DL Debug location for instructions added for the 485 /// workshare-loop construct itself. 486 /// \param CLI A descriptor of the canonical loop to workshare. 487 /// \param AllocaIP An insertion point for Alloca instructions usable in the 488 /// preheader of the loop. 489 /// \param NeedsBarrier Indicates whether a barrier must be insterted after 490 /// the loop. 491 /// \param SchedKind Scheduling algorithm to use. 492 /// \param ChunkSize The chunk size for the inner loop. 493 /// \param HasSimdModifier Whether the simd modifier is present in the 494 /// schedule clause. 495 /// \param HasMonotonicModifier Whether the monotonic modifier is present in 496 /// the schedule clause. 497 /// \param HasNonmonotonicModifier Whether the nonmonotonic modifier is 498 /// present in the schedule clause. 499 /// \param HasOrderedClause Whether the (parameterless) ordered clause is 500 /// present. 501 /// 502 /// \returns Point where to insert code after the workshare construct. 503 InsertPointTy applyWorkshareLoop( 504 DebugLoc DL, CanonicalLoopInfo *CLI, InsertPointTy AllocaIP, 505 bool NeedsBarrier, 506 llvm::omp::ScheduleKind SchedKind = llvm::omp::OMP_SCHEDULE_Default, 507 Value *ChunkSize = nullptr, bool HasSimdModifier = false, 508 bool HasMonotonicModifier = false, bool HasNonmonotonicModifier = false, 509 bool HasOrderedClause = false); 510 511 /// Tile a loop nest. 512 /// 513 /// Tiles the loops of \p Loops by the tile sizes in \p TileSizes. Loops in 514 /// \p/ Loops must be perfectly nested, from outermost to innermost loop 515 /// (i.e. Loops.front() is the outermost loop). The trip count llvm::Value 516 /// of every loop and every tile sizes must be usable in the outermost 517 /// loop's preheader. This implies that the loop nest is rectangular. 518 /// 519 /// Example: 520 /// \code 521 /// for (int i = 0; i < 15; ++i) // Canonical loop "i" 522 /// for (int j = 0; j < 14; ++j) // Canonical loop "j" 523 /// body(i, j); 524 /// \endcode 525 /// 526 /// After tiling with Loops={i,j} and TileSizes={5,7}, the loop is changed to 527 /// \code 528 /// for (int i1 = 0; i1 < 3; ++i1) 529 /// for (int j1 = 0; j1 < 2; ++j1) 530 /// for (int i2 = 0; i2 < 5; ++i2) 531 /// for (int j2 = 0; j2 < 7; ++j2) 532 /// body(i1*3+i2, j1*3+j2); 533 /// \endcode 534 /// 535 /// The returned vector are the loops {i1,j1,i2,j2}. The loops i1 and j1 are 536 /// referred to the floor, and the loops i2 and j2 are the tiles. Tiling also 537 /// handles non-constant trip counts, non-constant tile sizes and trip counts 538 /// that are not multiples of the tile size. In the latter case the tile loop 539 /// of the last floor-loop iteration will have fewer iterations than specified 540 /// as its tile size. 541 /// 542 /// 543 /// @param DL Debug location for instructions added by tiling, for 544 /// instance the floor- and tile trip count computation. 545 /// @param Loops Loops to tile. The CanonicalLoopInfo objects are 546 /// invalidated by this method, i.e. should not used after 547 /// tiling. 548 /// @param TileSizes For each loop in \p Loops, the tile size for that 549 /// dimensions. 550 /// 551 /// \returns A list of generated loops. Contains twice as many loops as the 552 /// input loop nest; the first half are the floor loops and the 553 /// second half are the tile loops. 554 std::vector<CanonicalLoopInfo *> 555 tileLoops(DebugLoc DL, ArrayRef<CanonicalLoopInfo *> Loops, 556 ArrayRef<Value *> TileSizes); 557 558 /// Fully unroll a loop. 559 /// 560 /// Instead of unrolling the loop immediately (and duplicating its body 561 /// instructions), it is deferred to LLVM's LoopUnrollPass by adding loop 562 /// metadata. 563 /// 564 /// \param DL Debug location for instructions added by unrolling. 565 /// \param Loop The loop to unroll. The loop will be invalidated. 566 void unrollLoopFull(DebugLoc DL, CanonicalLoopInfo *Loop); 567 568 /// Fully or partially unroll a loop. How the loop is unrolled is determined 569 /// using LLVM's LoopUnrollPass. 570 /// 571 /// \param DL Debug location for instructions added by unrolling. 572 /// \param Loop The loop to unroll. The loop will be invalidated. 573 void unrollLoopHeuristic(DebugLoc DL, CanonicalLoopInfo *Loop); 574 575 /// Partially unroll a loop. 576 /// 577 /// The CanonicalLoopInfo of the unrolled loop for use with chained 578 /// loop-associated directive can be requested using \p UnrolledCLI. Not 579 /// needing the CanonicalLoopInfo allows more efficient code generation by 580 /// deferring the actual unrolling to the LoopUnrollPass using loop metadata. 581 /// A loop-associated directive applied to the unrolled loop needs to know the 582 /// new trip count which means that if using a heuristically determined unroll 583 /// factor (\p Factor == 0), that factor must be computed immediately. We are 584 /// using the same logic as the LoopUnrollPass to derived the unroll factor, 585 /// but which assumes that some canonicalization has taken place (e.g. 586 /// Mem2Reg, LICM, GVN, Inlining, etc.). That is, the heuristic will perform 587 /// better when the unrolled loop's CanonicalLoopInfo is not needed. 588 /// 589 /// \param DL Debug location for instructions added by unrolling. 590 /// \param Loop The loop to unroll. The loop will be invalidated. 591 /// \param Factor The factor to unroll the loop by. A factor of 0 592 /// indicates that a heuristic should be used to determine 593 /// the unroll-factor. 594 /// \param UnrolledCLI If non-null, receives the CanonicalLoopInfo of the 595 /// partially unrolled loop. Otherwise, uses loop metadata 596 /// to defer unrolling to the LoopUnrollPass. 597 void unrollLoopPartial(DebugLoc DL, CanonicalLoopInfo *Loop, int32_t Factor, 598 CanonicalLoopInfo **UnrolledCLI); 599 600 /// Add metadata to simd-ize a loop. 601 /// 602 /// \param DL Debug location for instructions added by unrolling. 603 /// \param Loop The loop to simd-ize. 604 void applySimd(DebugLoc DL, CanonicalLoopInfo *Loop); 605 606 /// Generator for '#omp flush' 607 /// 608 /// \param Loc The location where the flush directive was encountered 609 void createFlush(const LocationDescription &Loc); 610 611 /// Generator for '#omp taskwait' 612 /// 613 /// \param Loc The location where the taskwait directive was encountered. 614 void createTaskwait(const LocationDescription &Loc); 615 616 /// Generator for '#omp taskyield' 617 /// 618 /// \param Loc The location where the taskyield directive was encountered. 619 void createTaskyield(const LocationDescription &Loc); 620 621 /// Generator for `#omp task` 622 /// 623 /// \param Loc The location where the task construct was encountered. 624 /// \param AllocaIP The insertion point to be used for alloca instructions. 625 /// \param BodyGenCB Callback that will generate the region code. 626 /// \param Tied True if the task is tied, false if the task is untied. 627 /// \param Final i1 value which is `true` if the task is final, `false` if the 628 /// task is not final. 629 InsertPointTy createTask(const LocationDescription &Loc, 630 InsertPointTy AllocaIP, BodyGenCallbackTy BodyGenCB, 631 bool Tied = true, Value *Final = nullptr); 632 633 /// Functions used to generate reductions. Such functions take two Values 634 /// representing LHS and RHS of the reduction, respectively, and a reference 635 /// to the value that is updated to refer to the reduction result. 636 using ReductionGenTy = 637 function_ref<InsertPointTy(InsertPointTy, Value *, Value *, Value *&)>; 638 639 /// Functions used to generate atomic reductions. Such functions take two 640 /// Values representing pointers to LHS and RHS of the reduction, as well as 641 /// the element type of these pointers. They are expected to atomically 642 /// update the LHS to the reduced value. 643 using AtomicReductionGenTy = 644 function_ref<InsertPointTy(InsertPointTy, Type *, Value *, Value *)>; 645 646 /// Information about an OpenMP reduction. 647 struct ReductionInfo { 648 ReductionInfo(Type *ElementType, Value *Variable, Value *PrivateVariable, 649 ReductionGenTy ReductionGen, 650 AtomicReductionGenTy AtomicReductionGen) 651 : ElementType(ElementType), Variable(Variable), 652 PrivateVariable(PrivateVariable), ReductionGen(ReductionGen), 653 AtomicReductionGen(AtomicReductionGen) { 654 assert(cast<PointerType>(Variable->getType()) 655 ->isOpaqueOrPointeeTypeMatches(ElementType) && "Invalid elem type"); 656 } 657 658 /// Reduction element type, must match pointee type of variable. 659 Type *ElementType; 660 661 /// Reduction variable of pointer type. 662 Value *Variable; 663 664 /// Thread-private partial reduction variable. 665 Value *PrivateVariable; 666 667 /// Callback for generating the reduction body. The IR produced by this will 668 /// be used to combine two values in a thread-safe context, e.g., under 669 /// lock or within the same thread, and therefore need not be atomic. 670 ReductionGenTy ReductionGen; 671 672 /// Callback for generating the atomic reduction body, may be null. The IR 673 /// produced by this will be used to atomically combine two values during 674 /// reduction. If null, the implementation will use the non-atomic version 675 /// along with the appropriate synchronization mechanisms. 676 AtomicReductionGenTy AtomicReductionGen; 677 }; 678 679 // TODO: provide atomic and non-atomic reduction generators for reduction 680 // operators defined by the OpenMP specification. 681 682 /// Generator for '#omp reduction'. 683 /// 684 /// Emits the IR instructing the runtime to perform the specific kind of 685 /// reductions. Expects reduction variables to have been privatized and 686 /// initialized to reduction-neutral values separately. Emits the calls to 687 /// runtime functions as well as the reduction function and the basic blocks 688 /// performing the reduction atomically and non-atomically. 689 /// 690 /// The code emitted for the following: 691 /// 692 /// \code 693 /// type var_1; 694 /// type var_2; 695 /// #pragma omp <directive> reduction(reduction-op:var_1,var_2) 696 /// /* body */; 697 /// \endcode 698 /// 699 /// corresponds to the following sketch. 700 /// 701 /// \code 702 /// void _outlined_par() { 703 /// // N is the number of different reductions. 704 /// void *red_array[] = {privatized_var_1, privatized_var_2, ...}; 705 /// switch(__kmpc_reduce(..., N, /*size of data in red array*/, red_array, 706 /// _omp_reduction_func, 707 /// _gomp_critical_user.reduction.var)) { 708 /// case 1: { 709 /// var_1 = var_1 <reduction-op> privatized_var_1; 710 /// var_2 = var_2 <reduction-op> privatized_var_2; 711 /// // ... 712 /// __kmpc_end_reduce(...); 713 /// break; 714 /// } 715 /// case 2: { 716 /// _Atomic<ReductionOp>(var_1, privatized_var_1); 717 /// _Atomic<ReductionOp>(var_2, privatized_var_2); 718 /// // ... 719 /// break; 720 /// } 721 /// default: break; 722 /// } 723 /// } 724 /// 725 /// void _omp_reduction_func(void **lhs, void **rhs) { 726 /// *(type *)lhs[0] = *(type *)lhs[0] <reduction-op> *(type *)rhs[0]; 727 /// *(type *)lhs[1] = *(type *)lhs[1] <reduction-op> *(type *)rhs[1]; 728 /// // ... 729 /// } 730 /// \endcode 731 /// 732 /// \param Loc The location where the reduction was 733 /// encountered. Must be within the associate 734 /// directive and after the last local access to the 735 /// reduction variables. 736 /// \param AllocaIP An insertion point suitable for allocas usable 737 /// in reductions. 738 /// \param ReductionInfos A list of info on each reduction variable. 739 /// \param IsNoWait A flag set if the reduction is marked as nowait. 740 InsertPointTy createReductions(const LocationDescription &Loc, 741 InsertPointTy AllocaIP, 742 ArrayRef<ReductionInfo> ReductionInfos, 743 bool IsNoWait = false); 744 745 ///} 746 747 /// Return the insertion point used by the underlying IRBuilder. 748 InsertPointTy getInsertionPoint() { return Builder.saveIP(); } 749 750 /// Update the internal location to \p Loc. 751 bool updateToLocation(const LocationDescription &Loc) { 752 Builder.restoreIP(Loc.IP); 753 Builder.SetCurrentDebugLocation(Loc.DL); 754 return Loc.IP.getBlock() != nullptr; 755 } 756 757 /// Return the function declaration for the runtime function with \p FnID. 758 FunctionCallee getOrCreateRuntimeFunction(Module &M, 759 omp::RuntimeFunction FnID); 760 761 Function *getOrCreateRuntimeFunctionPtr(omp::RuntimeFunction FnID); 762 763 /// Return the (LLVM-IR) string describing the source location \p LocStr. 764 Constant *getOrCreateSrcLocStr(StringRef LocStr, uint32_t &SrcLocStrSize); 765 766 /// Return the (LLVM-IR) string describing the default source location. 767 Constant *getOrCreateDefaultSrcLocStr(uint32_t &SrcLocStrSize); 768 769 /// Return the (LLVM-IR) string describing the source location identified by 770 /// the arguments. 771 Constant *getOrCreateSrcLocStr(StringRef FunctionName, StringRef FileName, 772 unsigned Line, unsigned Column, 773 uint32_t &SrcLocStrSize); 774 775 /// Return the (LLVM-IR) string describing the DebugLoc \p DL. Use \p F as 776 /// fallback if \p DL does not specify the function name. 777 Constant *getOrCreateSrcLocStr(DebugLoc DL, uint32_t &SrcLocStrSize, 778 Function *F = nullptr); 779 780 /// Return the (LLVM-IR) string describing the source location \p Loc. 781 Constant *getOrCreateSrcLocStr(const LocationDescription &Loc, 782 uint32_t &SrcLocStrSize); 783 784 /// Return an ident_t* encoding the source location \p SrcLocStr and \p Flags. 785 /// TODO: Create a enum class for the Reserve2Flags 786 Constant *getOrCreateIdent(Constant *SrcLocStr, uint32_t SrcLocStrSize, 787 omp::IdentFlag Flags = omp::IdentFlag(0), 788 unsigned Reserve2Flags = 0); 789 790 /// Create a hidden global flag \p Name in the module with initial value \p 791 /// Value. 792 GlobalValue *createGlobalFlag(unsigned Value, StringRef Name); 793 794 /// Create an offloading section struct used to register this global at 795 /// runtime. 796 /// 797 /// Type struct __tgt_offload_entry{ 798 /// void *addr; // Pointer to the offload entry info. 799 /// // (function or global) 800 /// char *name; // Name of the function or global. 801 /// size_t size; // Size of the entry info (0 if it a function). 802 /// int32_t flags; 803 /// int32_t reserved; 804 /// }; 805 /// 806 /// \param Addr The pointer to the global being registered. 807 /// \param Name The symbol name associated with the global. 808 /// \param Size The size in bytes of the global (0 for functions). 809 /// \param Flags Flags associated with the entry. 810 /// \param SectionName The section this entry will be placed at. 811 void emitOffloadingEntry(Constant *Addr, StringRef Name, uint64_t Size, 812 int32_t Flags, 813 StringRef SectionName = "omp_offloading_entries"); 814 815 /// Generate control flow and cleanup for cancellation. 816 /// 817 /// \param CancelFlag Flag indicating if the cancellation is performed. 818 /// \param CanceledDirective The kind of directive that is cancled. 819 /// \param ExitCB Extra code to be generated in the exit block. 820 void emitCancelationCheckImpl(Value *CancelFlag, 821 omp::Directive CanceledDirective, 822 FinalizeCallbackTy ExitCB = {}); 823 824 /// Generate a barrier runtime call. 825 /// 826 /// \param Loc The location at which the request originated and is fulfilled. 827 /// \param DK The directive which caused the barrier 828 /// \param ForceSimpleCall Flag to force a simple (=non-cancellation) barrier. 829 /// \param CheckCancelFlag Flag to indicate a cancel barrier return value 830 /// should be checked and acted upon. 831 /// 832 /// \returns The insertion point after the barrier. 833 InsertPointTy emitBarrierImpl(const LocationDescription &Loc, 834 omp::Directive DK, bool ForceSimpleCall, 835 bool CheckCancelFlag); 836 837 /// Generate a flush runtime call. 838 /// 839 /// \param Loc The location at which the request originated and is fulfilled. 840 void emitFlush(const LocationDescription &Loc); 841 842 /// The finalization stack made up of finalize callbacks currently in-flight, 843 /// wrapped into FinalizationInfo objects that reference also the finalization 844 /// target block and the kind of cancellable directive. 845 SmallVector<FinalizationInfo, 8> FinalizationStack; 846 847 /// Return true if the last entry in the finalization stack is of kind \p DK 848 /// and cancellable. 849 bool isLastFinalizationInfoCancellable(omp::Directive DK) { 850 return !FinalizationStack.empty() && 851 FinalizationStack.back().IsCancellable && 852 FinalizationStack.back().DK == DK; 853 } 854 855 /// Generate a taskwait runtime call. 856 /// 857 /// \param Loc The location at which the request originated and is fulfilled. 858 void emitTaskwaitImpl(const LocationDescription &Loc); 859 860 /// Generate a taskyield runtime call. 861 /// 862 /// \param Loc The location at which the request originated and is fulfilled. 863 void emitTaskyieldImpl(const LocationDescription &Loc); 864 865 /// Return the current thread ID. 866 /// 867 /// \param Ident The ident (ident_t*) describing the query origin. 868 Value *getOrCreateThreadID(Value *Ident); 869 870 /// The underlying LLVM-IR module 871 Module &M; 872 873 /// The LLVM-IR Builder used to create IR. 874 IRBuilder<> Builder; 875 876 /// Map to remember source location strings 877 StringMap<Constant *> SrcLocStrMap; 878 879 /// Map to remember existing ident_t*. 880 DenseMap<std::pair<Constant *, uint64_t>, Constant *> IdentMap; 881 882 /// Helper that contains information about regions we need to outline 883 /// during finalization. 884 struct OutlineInfo { 885 using PostOutlineCBTy = std::function<void(Function &)>; 886 PostOutlineCBTy PostOutlineCB; 887 BasicBlock *EntryBB, *ExitBB, *OuterAllocaBB; 888 SmallVector<Value *, 2> ExcludeArgsFromAggregate; 889 890 /// Collect all blocks in between EntryBB and ExitBB in both the given 891 /// vector and set. 892 void collectBlocks(SmallPtrSetImpl<BasicBlock *> &BlockSet, 893 SmallVectorImpl<BasicBlock *> &BlockVector); 894 895 /// Return the function that contains the region to be outlined. 896 Function *getFunction() const { return EntryBB->getParent(); } 897 }; 898 899 /// Collection of regions that need to be outlined during finalization. 900 SmallVector<OutlineInfo, 16> OutlineInfos; 901 902 /// Collection of owned canonical loop objects that eventually need to be 903 /// free'd. 904 std::forward_list<CanonicalLoopInfo> LoopInfos; 905 906 /// Add a new region that will be outlined later. 907 void addOutlineInfo(OutlineInfo &&OI) { OutlineInfos.emplace_back(OI); } 908 909 /// An ordered map of auto-generated variables to their unique names. 910 /// It stores variables with the following names: 1) ".gomp_critical_user_" + 911 /// <critical_section_name> + ".var" for "omp critical" directives; 2) 912 /// <mangled_name_for_global_var> + ".cache." for cache for threadprivate 913 /// variables. 914 StringMap<AssertingVH<Constant>, BumpPtrAllocator> InternalVars; 915 916 /// Create the global variable holding the offload mappings information. 917 GlobalVariable *createOffloadMaptypes(SmallVectorImpl<uint64_t> &Mappings, 918 std::string VarName); 919 920 /// Create the global variable holding the offload names information. 921 GlobalVariable * 922 createOffloadMapnames(SmallVectorImpl<llvm::Constant *> &Names, 923 std::string VarName); 924 925 struct MapperAllocas { 926 AllocaInst *ArgsBase = nullptr; 927 AllocaInst *Args = nullptr; 928 AllocaInst *ArgSizes = nullptr; 929 }; 930 931 /// Create the allocas instruction used in call to mapper functions. 932 void createMapperAllocas(const LocationDescription &Loc, 933 InsertPointTy AllocaIP, unsigned NumOperands, 934 struct MapperAllocas &MapperAllocas); 935 936 /// Create the call for the target mapper function. 937 /// \param Loc The source location description. 938 /// \param MapperFunc Function to be called. 939 /// \param SrcLocInfo Source location information global. 940 /// \param MaptypesArg The argument types. 941 /// \param MapnamesArg The argument names. 942 /// \param MapperAllocas The AllocaInst used for the call. 943 /// \param DeviceID Device ID for the call. 944 /// \param NumOperands Number of operands in the call. 945 void emitMapperCall(const LocationDescription &Loc, Function *MapperFunc, 946 Value *SrcLocInfo, Value *MaptypesArg, Value *MapnamesArg, 947 struct MapperAllocas &MapperAllocas, int64_t DeviceID, 948 unsigned NumOperands); 949 950 public: 951 /// Generator for __kmpc_copyprivate 952 /// 953 /// \param Loc The source location description. 954 /// \param BufSize Number of elements in the buffer. 955 /// \param CpyBuf List of pointers to data to be copied. 956 /// \param CpyFn function to call for copying data. 957 /// \param DidIt flag variable; 1 for 'single' thread, 0 otherwise. 958 /// 959 /// \return The insertion position *after* the CopyPrivate call. 960 961 InsertPointTy createCopyPrivate(const LocationDescription &Loc, 962 llvm::Value *BufSize, llvm::Value *CpyBuf, 963 llvm::Value *CpyFn, llvm::Value *DidIt); 964 965 /// Generator for '#omp single' 966 /// 967 /// \param Loc The source location description. 968 /// \param BodyGenCB Callback that will generate the region code. 969 /// \param FiniCB Callback to finalize variable copies. 970 /// \param IsNowait If false, a barrier is emitted. 971 /// \param DidIt Local variable used as a flag to indicate 'single' thread 972 /// 973 /// \returns The insertion position *after* the single call. 974 InsertPointTy createSingle(const LocationDescription &Loc, 975 BodyGenCallbackTy BodyGenCB, 976 FinalizeCallbackTy FiniCB, bool IsNowait, 977 llvm::Value *DidIt); 978 979 /// Generator for '#omp master' 980 /// 981 /// \param Loc The insert and source location description. 982 /// \param BodyGenCB Callback that will generate the region code. 983 /// \param FiniCB Callback to finalize variable copies. 984 /// 985 /// \returns The insertion position *after* the master. 986 InsertPointTy createMaster(const LocationDescription &Loc, 987 BodyGenCallbackTy BodyGenCB, 988 FinalizeCallbackTy FiniCB); 989 990 /// Generator for '#omp masked' 991 /// 992 /// \param Loc The insert and source location description. 993 /// \param BodyGenCB Callback that will generate the region code. 994 /// \param FiniCB Callback to finialize variable copies. 995 /// 996 /// \returns The insertion position *after* the masked. 997 InsertPointTy createMasked(const LocationDescription &Loc, 998 BodyGenCallbackTy BodyGenCB, 999 FinalizeCallbackTy FiniCB, Value *Filter); 1000 1001 /// Generator for '#omp critical' 1002 /// 1003 /// \param Loc The insert and source location description. 1004 /// \param BodyGenCB Callback that will generate the region body code. 1005 /// \param FiniCB Callback to finalize variable copies. 1006 /// \param CriticalName name of the lock used by the critical directive 1007 /// \param HintInst Hint Instruction for hint clause associated with critical 1008 /// 1009 /// \returns The insertion position *after* the critical. 1010 InsertPointTy createCritical(const LocationDescription &Loc, 1011 BodyGenCallbackTy BodyGenCB, 1012 FinalizeCallbackTy FiniCB, 1013 StringRef CriticalName, Value *HintInst); 1014 1015 /// Generator for '#omp ordered depend (source | sink)' 1016 /// 1017 /// \param Loc The insert and source location description. 1018 /// \param AllocaIP The insertion point to be used for alloca instructions. 1019 /// \param NumLoops The number of loops in depend clause. 1020 /// \param StoreValues The value will be stored in vector address. 1021 /// \param Name The name of alloca instruction. 1022 /// \param IsDependSource If true, depend source; otherwise, depend sink. 1023 /// 1024 /// \return The insertion position *after* the ordered. 1025 InsertPointTy createOrderedDepend(const LocationDescription &Loc, 1026 InsertPointTy AllocaIP, unsigned NumLoops, 1027 ArrayRef<llvm::Value *> StoreValues, 1028 const Twine &Name, bool IsDependSource); 1029 1030 /// Generator for '#omp ordered [threads | simd]' 1031 /// 1032 /// \param Loc The insert and source location description. 1033 /// \param BodyGenCB Callback that will generate the region code. 1034 /// \param FiniCB Callback to finalize variable copies. 1035 /// \param IsThreads If true, with threads clause or without clause; 1036 /// otherwise, with simd clause; 1037 /// 1038 /// \returns The insertion position *after* the ordered. 1039 InsertPointTy createOrderedThreadsSimd(const LocationDescription &Loc, 1040 BodyGenCallbackTy BodyGenCB, 1041 FinalizeCallbackTy FiniCB, 1042 bool IsThreads); 1043 1044 /// Generator for '#omp sections' 1045 /// 1046 /// \param Loc The insert and source location description. 1047 /// \param AllocaIP The insertion points to be used for alloca instructions. 1048 /// \param SectionCBs Callbacks that will generate body of each section. 1049 /// \param PrivCB Callback to copy a given variable (think copy constructor). 1050 /// \param FiniCB Callback to finalize variable copies. 1051 /// \param IsCancellable Flag to indicate a cancellable parallel region. 1052 /// \param IsNowait If true, barrier - to ensure all sections are executed 1053 /// before moving forward will not be generated. 1054 /// \returns The insertion position *after* the sections. 1055 InsertPointTy createSections(const LocationDescription &Loc, 1056 InsertPointTy AllocaIP, 1057 ArrayRef<StorableBodyGenCallbackTy> SectionCBs, 1058 PrivatizeCallbackTy PrivCB, 1059 FinalizeCallbackTy FiniCB, bool IsCancellable, 1060 bool IsNowait); 1061 1062 /// Generator for '#omp section' 1063 /// 1064 /// \param Loc The insert and source location description. 1065 /// \param BodyGenCB Callback that will generate the region body code. 1066 /// \param FiniCB Callback to finalize variable copies. 1067 /// \returns The insertion position *after* the section. 1068 InsertPointTy createSection(const LocationDescription &Loc, 1069 BodyGenCallbackTy BodyGenCB, 1070 FinalizeCallbackTy FiniCB); 1071 1072 /// Generate conditional branch and relevant BasicBlocks through which private 1073 /// threads copy the 'copyin' variables from Master copy to threadprivate 1074 /// copies. 1075 /// 1076 /// \param IP insertion block for copyin conditional 1077 /// \param MasterVarPtr a pointer to the master variable 1078 /// \param PrivateVarPtr a pointer to the threadprivate variable 1079 /// \param IntPtrTy Pointer size type 1080 /// \param BranchtoEnd Create a branch between the copyin.not.master blocks 1081 // and copy.in.end block 1082 /// 1083 /// \returns The insertion point where copying operation to be emitted. 1084 InsertPointTy createCopyinClauseBlocks(InsertPointTy IP, Value *MasterAddr, 1085 Value *PrivateAddr, 1086 llvm::IntegerType *IntPtrTy, 1087 bool BranchtoEnd = true); 1088 1089 /// Create a runtime call for kmpc_Alloc 1090 /// 1091 /// \param Loc The insert and source location description. 1092 /// \param Size Size of allocated memory space 1093 /// \param Allocator Allocator information instruction 1094 /// \param Name Name of call Instruction for OMP_alloc 1095 /// 1096 /// \returns CallInst to the OMP_Alloc call 1097 CallInst *createOMPAlloc(const LocationDescription &Loc, Value *Size, 1098 Value *Allocator, std::string Name = ""); 1099 1100 /// Create a runtime call for kmpc_free 1101 /// 1102 /// \param Loc The insert and source location description. 1103 /// \param Addr Address of memory space to be freed 1104 /// \param Allocator Allocator information instruction 1105 /// \param Name Name of call Instruction for OMP_Free 1106 /// 1107 /// \returns CallInst to the OMP_Free call 1108 CallInst *createOMPFree(const LocationDescription &Loc, Value *Addr, 1109 Value *Allocator, std::string Name = ""); 1110 1111 /// Create a runtime call for kmpc_threadprivate_cached 1112 /// 1113 /// \param Loc The insert and source location description. 1114 /// \param Pointer pointer to data to be cached 1115 /// \param Size size of data to be cached 1116 /// \param Name Name of call Instruction for callinst 1117 /// 1118 /// \returns CallInst to the thread private cache call. 1119 CallInst *createCachedThreadPrivate(const LocationDescription &Loc, 1120 llvm::Value *Pointer, 1121 llvm::ConstantInt *Size, 1122 const llvm::Twine &Name = Twine("")); 1123 1124 /// Create a runtime call for __tgt_interop_init 1125 /// 1126 /// \param Loc The insert and source location description. 1127 /// \param InteropVar variable to be allocated 1128 /// \param InteropType type of interop operation 1129 /// \param Device devide to which offloading will occur 1130 /// \param NumDependences number of dependence variables 1131 /// \param DependenceAddress pointer to dependence variables 1132 /// \param HaveNowaitClause does nowait clause exist 1133 /// 1134 /// \returns CallInst to the __tgt_interop_init call 1135 CallInst *createOMPInteropInit(const LocationDescription &Loc, 1136 Value *InteropVar, 1137 omp::OMPInteropType InteropType, Value *Device, 1138 Value *NumDependences, 1139 Value *DependenceAddress, 1140 bool HaveNowaitClause); 1141 1142 /// Create a runtime call for __tgt_interop_destroy 1143 /// 1144 /// \param Loc The insert and source location description. 1145 /// \param InteropVar variable to be allocated 1146 /// \param Device devide to which offloading will occur 1147 /// \param NumDependences number of dependence variables 1148 /// \param DependenceAddress pointer to dependence variables 1149 /// \param HaveNowaitClause does nowait clause exist 1150 /// 1151 /// \returns CallInst to the __tgt_interop_destroy call 1152 CallInst *createOMPInteropDestroy(const LocationDescription &Loc, 1153 Value *InteropVar, Value *Device, 1154 Value *NumDependences, 1155 Value *DependenceAddress, 1156 bool HaveNowaitClause); 1157 1158 /// Create a runtime call for __tgt_interop_use 1159 /// 1160 /// \param Loc The insert and source location description. 1161 /// \param InteropVar variable to be allocated 1162 /// \param Device devide to which offloading will occur 1163 /// \param NumDependences number of dependence variables 1164 /// \param DependenceAddress pointer to dependence variables 1165 /// \param HaveNowaitClause does nowait clause exist 1166 /// 1167 /// \returns CallInst to the __tgt_interop_use call 1168 CallInst *createOMPInteropUse(const LocationDescription &Loc, 1169 Value *InteropVar, Value *Device, 1170 Value *NumDependences, Value *DependenceAddress, 1171 bool HaveNowaitClause); 1172 1173 /// The `omp target` interface 1174 /// 1175 /// For more information about the usage of this interface, 1176 /// \see openmp/libomptarget/deviceRTLs/common/include/target.h 1177 /// 1178 ///{ 1179 1180 /// Create a runtime call for kmpc_target_init 1181 /// 1182 /// \param Loc The insert and source location description. 1183 /// \param IsSPMD Flag to indicate if the kernel is an SPMD kernel or not. 1184 /// \param RequiresFullRuntime Indicate if a full device runtime is necessary. 1185 InsertPointTy createTargetInit(const LocationDescription &Loc, bool IsSPMD, 1186 bool RequiresFullRuntime); 1187 1188 /// Create a runtime call for kmpc_target_deinit 1189 /// 1190 /// \param Loc The insert and source location description. 1191 /// \param IsSPMD Flag to indicate if the kernel is an SPMD kernel or not. 1192 /// \param RequiresFullRuntime Indicate if a full device runtime is necessary. 1193 void createTargetDeinit(const LocationDescription &Loc, bool IsSPMD, 1194 bool RequiresFullRuntime); 1195 1196 ///} 1197 1198 /// Declarations for LLVM-IR types (simple, array, function and structure) are 1199 /// generated below. Their names are defined and used in OpenMPKinds.def. Here 1200 /// we provide the declarations, the initializeTypes function will provide the 1201 /// values. 1202 /// 1203 ///{ 1204 #define OMP_TYPE(VarName, InitValue) Type *VarName = nullptr; 1205 #define OMP_ARRAY_TYPE(VarName, ElemTy, ArraySize) \ 1206 ArrayType *VarName##Ty = nullptr; \ 1207 PointerType *VarName##PtrTy = nullptr; 1208 #define OMP_FUNCTION_TYPE(VarName, IsVarArg, ReturnType, ...) \ 1209 FunctionType *VarName = nullptr; \ 1210 PointerType *VarName##Ptr = nullptr; 1211 #define OMP_STRUCT_TYPE(VarName, StrName, ...) \ 1212 StructType *VarName = nullptr; \ 1213 PointerType *VarName##Ptr = nullptr; 1214 #include "llvm/Frontend/OpenMP/OMPKinds.def" 1215 1216 ///} 1217 1218 private: 1219 /// Create all simple and struct types exposed by the runtime and remember 1220 /// the llvm::PointerTypes of them for easy access later. 1221 void initializeTypes(Module &M); 1222 1223 /// Common interface for generating entry calls for OMP Directives. 1224 /// if the directive has a region/body, It will set the insertion 1225 /// point to the body 1226 /// 1227 /// \param OMPD Directive to generate entry blocks for 1228 /// \param EntryCall Call to the entry OMP Runtime Function 1229 /// \param ExitBB block where the region ends. 1230 /// \param Conditional indicate if the entry call result will be used 1231 /// to evaluate a conditional of whether a thread will execute 1232 /// body code or not. 1233 /// 1234 /// \return The insertion position in exit block 1235 InsertPointTy emitCommonDirectiveEntry(omp::Directive OMPD, Value *EntryCall, 1236 BasicBlock *ExitBB, 1237 bool Conditional = false); 1238 1239 /// Common interface to finalize the region 1240 /// 1241 /// \param OMPD Directive to generate exiting code for 1242 /// \param FinIP Insertion point for emitting Finalization code and exit call 1243 /// \param ExitCall Call to the ending OMP Runtime Function 1244 /// \param HasFinalize indicate if the directive will require finalization 1245 /// and has a finalization callback in the stack that 1246 /// should be called. 1247 /// 1248 /// \return The insertion position in exit block 1249 InsertPointTy emitCommonDirectiveExit(omp::Directive OMPD, 1250 InsertPointTy FinIP, 1251 Instruction *ExitCall, 1252 bool HasFinalize = true); 1253 1254 /// Common Interface to generate OMP inlined regions 1255 /// 1256 /// \param OMPD Directive to generate inlined region for 1257 /// \param EntryCall Call to the entry OMP Runtime Function 1258 /// \param ExitCall Call to the ending OMP Runtime Function 1259 /// \param BodyGenCB Body code generation callback. 1260 /// \param FiniCB Finalization Callback. Will be called when finalizing region 1261 /// \param Conditional indicate if the entry call result will be used 1262 /// to evaluate a conditional of whether a thread will execute 1263 /// body code or not. 1264 /// \param HasFinalize indicate if the directive will require finalization 1265 /// and has a finalization callback in the stack that 1266 /// should be called. 1267 /// \param IsCancellable if HasFinalize is set to true, indicate if the 1268 /// the directive should be cancellable. 1269 /// \return The insertion point after the region 1270 1271 InsertPointTy 1272 EmitOMPInlinedRegion(omp::Directive OMPD, Instruction *EntryCall, 1273 Instruction *ExitCall, BodyGenCallbackTy BodyGenCB, 1274 FinalizeCallbackTy FiniCB, bool Conditional = false, 1275 bool HasFinalize = true, bool IsCancellable = false); 1276 1277 /// Get the platform-specific name separator. 1278 /// \param Parts different parts of the final name that needs separation 1279 /// \param FirstSeparator First separator used between the initial two 1280 /// parts of the name. 1281 /// \param Separator separator used between all of the rest consecutive 1282 /// parts of the name 1283 static std::string getNameWithSeparators(ArrayRef<StringRef> Parts, 1284 StringRef FirstSeparator, 1285 StringRef Separator); 1286 1287 /// Gets (if variable with the given name already exist) or creates 1288 /// internal global variable with the specified Name. The created variable has 1289 /// linkage CommonLinkage by default and is initialized by null value. 1290 /// \param Ty Type of the global variable. If it is exist already the type 1291 /// must be the same. 1292 /// \param Name Name of the variable. 1293 Constant *getOrCreateOMPInternalVariable(Type *Ty, const Twine &Name, 1294 unsigned AddressSpace = 0); 1295 1296 /// Returns corresponding lock object for the specified critical region 1297 /// name. If the lock object does not exist it is created, otherwise the 1298 /// reference to the existing copy is returned. 1299 /// \param CriticalName Name of the critical region. 1300 /// 1301 Value *getOMPCriticalRegionLock(StringRef CriticalName); 1302 1303 /// Callback type for Atomic Expression update 1304 /// ex: 1305 /// \code{.cpp} 1306 /// unsigned x = 0; 1307 /// #pragma omp atomic update 1308 /// x = Expr(x_old); //Expr() is any legal operation 1309 /// \endcode 1310 /// 1311 /// \param XOld the value of the atomic memory address to use for update 1312 /// \param IRB reference to the IRBuilder to use 1313 /// 1314 /// \returns Value to update X to. 1315 using AtomicUpdateCallbackTy = 1316 const function_ref<Value *(Value *XOld, IRBuilder<> &IRB)>; 1317 1318 private: 1319 enum AtomicKind { Read, Write, Update, Capture, Compare }; 1320 1321 /// Determine whether to emit flush or not 1322 /// 1323 /// \param Loc The insert and source location description. 1324 /// \param AO The required atomic ordering 1325 /// \param AK The OpenMP atomic operation kind used. 1326 /// 1327 /// \returns wether a flush was emitted or not 1328 bool checkAndEmitFlushAfterAtomic(const LocationDescription &Loc, 1329 AtomicOrdering AO, AtomicKind AK); 1330 1331 /// Emit atomic update for constructs: X = X BinOp Expr ,or X = Expr BinOp X 1332 /// For complex Operations: X = UpdateOp(X) => CmpExch X, old_X, UpdateOp(X) 1333 /// Only Scalar data types. 1334 /// 1335 /// \param AllocaIP The insertion point to be used for alloca 1336 /// instructions. 1337 /// \param X The target atomic pointer to be updated 1338 /// \param XElemTy The element type of the atomic pointer. 1339 /// \param Expr The value to update X with. 1340 /// \param AO Atomic ordering of the generated atomic 1341 /// instructions. 1342 /// \param RMWOp The binary operation used for update. If 1343 /// operation is not supported by atomicRMW, 1344 /// or belong to {FADD, FSUB, BAD_BINOP}. 1345 /// Then a `cmpExch` based atomic will be generated. 1346 /// \param UpdateOp Code generator for complex expressions that cannot be 1347 /// expressed through atomicrmw instruction. 1348 /// \param VolatileX true if \a X volatile? 1349 /// \param IsXBinopExpr true if \a X is Left H.S. in Right H.S. part of the 1350 /// update expression, false otherwise. 1351 /// (e.g. true for X = X BinOp Expr) 1352 /// 1353 /// \returns A pair of the old value of X before the update, and the value 1354 /// used for the update. 1355 std::pair<Value *, Value *> 1356 emitAtomicUpdate(InsertPointTy AllocaIP, Value *X, Type *XElemTy, Value *Expr, 1357 AtomicOrdering AO, AtomicRMWInst::BinOp RMWOp, 1358 AtomicUpdateCallbackTy &UpdateOp, bool VolatileX, 1359 bool IsXBinopExpr); 1360 1361 /// Emit the binary op. described by \p RMWOp, using \p Src1 and \p Src2 . 1362 /// 1363 /// \Return The instruction 1364 Value *emitRMWOpAsInstruction(Value *Src1, Value *Src2, 1365 AtomicRMWInst::BinOp RMWOp); 1366 1367 public: 1368 /// a struct to pack relevant information while generating atomic Ops 1369 struct AtomicOpValue { 1370 Value *Var = nullptr; 1371 Type *ElemTy = nullptr; 1372 bool IsSigned = false; 1373 bool IsVolatile = false; 1374 }; 1375 1376 /// Emit atomic Read for : V = X --- Only Scalar data types. 1377 /// 1378 /// \param Loc The insert and source location description. 1379 /// \param X The target pointer to be atomically read 1380 /// \param V Memory address where to store atomically read 1381 /// value 1382 /// \param AO Atomic ordering of the generated atomic 1383 /// instructions. 1384 /// 1385 /// \return Insertion point after generated atomic read IR. 1386 InsertPointTy createAtomicRead(const LocationDescription &Loc, 1387 AtomicOpValue &X, AtomicOpValue &V, 1388 AtomicOrdering AO); 1389 1390 /// Emit atomic write for : X = Expr --- Only Scalar data types. 1391 /// 1392 /// \param Loc The insert and source location description. 1393 /// \param X The target pointer to be atomically written to 1394 /// \param Expr The value to store. 1395 /// \param AO Atomic ordering of the generated atomic 1396 /// instructions. 1397 /// 1398 /// \return Insertion point after generated atomic Write IR. 1399 InsertPointTy createAtomicWrite(const LocationDescription &Loc, 1400 AtomicOpValue &X, Value *Expr, 1401 AtomicOrdering AO); 1402 1403 /// Emit atomic update for constructs: X = X BinOp Expr ,or X = Expr BinOp X 1404 /// For complex Operations: X = UpdateOp(X) => CmpExch X, old_X, UpdateOp(X) 1405 /// Only Scalar data types. 1406 /// 1407 /// \param Loc The insert and source location description. 1408 /// \param AllocaIP The insertion point to be used for alloca instructions. 1409 /// \param X The target atomic pointer to be updated 1410 /// \param Expr The value to update X with. 1411 /// \param AO Atomic ordering of the generated atomic instructions. 1412 /// \param RMWOp The binary operation used for update. If operation 1413 /// is not supported by atomicRMW, or belong to 1414 /// {FADD, FSUB, BAD_BINOP}. Then a `cmpExch` based 1415 /// atomic will be generated. 1416 /// \param UpdateOp Code generator for complex expressions that cannot be 1417 /// expressed through atomicrmw instruction. 1418 /// \param IsXBinopExpr true if \a X is Left H.S. in Right H.S. part of the 1419 /// update expression, false otherwise. 1420 /// (e.g. true for X = X BinOp Expr) 1421 /// 1422 /// \return Insertion point after generated atomic update IR. 1423 InsertPointTy createAtomicUpdate(const LocationDescription &Loc, 1424 InsertPointTy AllocaIP, AtomicOpValue &X, 1425 Value *Expr, AtomicOrdering AO, 1426 AtomicRMWInst::BinOp RMWOp, 1427 AtomicUpdateCallbackTy &UpdateOp, 1428 bool IsXBinopExpr); 1429 1430 /// Emit atomic update for constructs: --- Only Scalar data types 1431 /// V = X; X = X BinOp Expr , 1432 /// X = X BinOp Expr; V = X, 1433 /// V = X; X = Expr BinOp X, 1434 /// X = Expr BinOp X; V = X, 1435 /// V = X; X = UpdateOp(X), 1436 /// X = UpdateOp(X); V = X, 1437 /// 1438 /// \param Loc The insert and source location description. 1439 /// \param AllocaIP The insertion point to be used for alloca instructions. 1440 /// \param X The target atomic pointer to be updated 1441 /// \param V Memory address where to store captured value 1442 /// \param Expr The value to update X with. 1443 /// \param AO Atomic ordering of the generated atomic instructions 1444 /// \param RMWOp The binary operation used for update. If 1445 /// operation is not supported by atomicRMW, or belong to 1446 /// {FADD, FSUB, BAD_BINOP}. Then a cmpExch based 1447 /// atomic will be generated. 1448 /// \param UpdateOp Code generator for complex expressions that cannot be 1449 /// expressed through atomicrmw instruction. 1450 /// \param UpdateExpr true if X is an in place update of the form 1451 /// X = X BinOp Expr or X = Expr BinOp X 1452 /// \param IsXBinopExpr true if X is Left H.S. in Right H.S. part of the 1453 /// update expression, false otherwise. 1454 /// (e.g. true for X = X BinOp Expr) 1455 /// \param IsPostfixUpdate true if original value of 'x' must be stored in 1456 /// 'v', not an updated one. 1457 /// 1458 /// \return Insertion point after generated atomic capture IR. 1459 InsertPointTy 1460 createAtomicCapture(const LocationDescription &Loc, InsertPointTy AllocaIP, 1461 AtomicOpValue &X, AtomicOpValue &V, Value *Expr, 1462 AtomicOrdering AO, AtomicRMWInst::BinOp RMWOp, 1463 AtomicUpdateCallbackTy &UpdateOp, bool UpdateExpr, 1464 bool IsPostfixUpdate, bool IsXBinopExpr); 1465 1466 /// Emit atomic compare for constructs: --- Only scalar data types 1467 /// cond-expr-stmt: 1468 /// x = x ordop expr ? expr : x; 1469 /// x = expr ordop x ? expr : x; 1470 /// x = x == e ? d : x; 1471 /// x = e == x ? d : x; (this one is not in the spec) 1472 /// cond-update-stmt: 1473 /// if (x ordop expr) { x = expr; } 1474 /// if (expr ordop x) { x = expr; } 1475 /// if (x == e) { x = d; } 1476 /// if (e == x) { x = d; } (this one is not in the spec) 1477 /// conditional-update-capture-atomic: 1478 /// v = x; cond-update-stmt; (IsPostfixUpdate=true, IsFailOnly=false) 1479 /// cond-update-stmt; v = x; (IsPostfixUpdate=false, IsFailOnly=false) 1480 /// if (x == e) { x = d; } else { v = x; } (IsPostfixUpdate=false, 1481 /// IsFailOnly=true) 1482 /// r = x == e; if (r) { x = d; } (IsPostfixUpdate=false, IsFailOnly=false) 1483 /// r = x == e; if (r) { x = d; } else { v = x; } (IsPostfixUpdate=false, 1484 /// IsFailOnly=true) 1485 /// 1486 /// \param Loc The insert and source location description. 1487 /// \param X The target atomic pointer to be updated. 1488 /// \param V Memory address where to store captured value (for 1489 /// compare capture only). 1490 /// \param R Memory address where to store comparison result 1491 /// (for compare capture with '==' only). 1492 /// \param E The expected value ('e') for forms that use an 1493 /// equality comparison or an expression ('expr') for 1494 /// forms that use 'ordop' (logically an atomic maximum or 1495 /// minimum). 1496 /// \param D The desired value for forms that use an equality 1497 /// comparison. If forms that use 'ordop', it should be 1498 /// \p nullptr. 1499 /// \param AO Atomic ordering of the generated atomic instructions. 1500 /// \param Op Atomic compare operation. It can only be ==, <, or >. 1501 /// \param IsXBinopExpr True if the conditional statement is in the form where 1502 /// x is on LHS. It only matters for < or >. 1503 /// \param IsPostfixUpdate True if original value of 'x' must be stored in 1504 /// 'v', not an updated one (for compare capture 1505 /// only). 1506 /// \param IsFailOnly True if the original value of 'x' is stored to 'v' 1507 /// only when the comparison fails. This is only valid for 1508 /// the case the comparison is '=='. 1509 /// 1510 /// \return Insertion point after generated atomic capture IR. 1511 InsertPointTy 1512 createAtomicCompare(const LocationDescription &Loc, AtomicOpValue &X, 1513 AtomicOpValue &V, AtomicOpValue &R, Value *E, Value *D, 1514 AtomicOrdering AO, omp::OMPAtomicCompareOp Op, 1515 bool IsXBinopExpr, bool IsPostfixUpdate, bool IsFailOnly); 1516 1517 /// Create the control flow structure of a canonical OpenMP loop. 1518 /// 1519 /// The emitted loop will be disconnected, i.e. no edge to the loop's 1520 /// preheader and no terminator in the AfterBB. The OpenMPIRBuilder's 1521 /// IRBuilder location is not preserved. 1522 /// 1523 /// \param DL DebugLoc used for the instructions in the skeleton. 1524 /// \param TripCount Value to be used for the trip count. 1525 /// \param F Function in which to insert the BasicBlocks. 1526 /// \param PreInsertBefore Where to insert BBs that execute before the body, 1527 /// typically the body itself. 1528 /// \param PostInsertBefore Where to insert BBs that execute after the body. 1529 /// \param Name Base name used to derive BB 1530 /// and instruction names. 1531 /// 1532 /// \returns The CanonicalLoopInfo that represents the emitted loop. 1533 CanonicalLoopInfo *createLoopSkeleton(DebugLoc DL, Value *TripCount, 1534 Function *F, 1535 BasicBlock *PreInsertBefore, 1536 BasicBlock *PostInsertBefore, 1537 const Twine &Name = {}); 1538 }; 1539 1540 /// Class to represented the control flow structure of an OpenMP canonical loop. 1541 /// 1542 /// The control-flow structure is standardized for easy consumption by 1543 /// directives associated with loops. For instance, the worksharing-loop 1544 /// construct may change this control flow such that each loop iteration is 1545 /// executed on only one thread. The constraints of a canonical loop in brief 1546 /// are: 1547 /// 1548 /// * The number of loop iterations must have been computed before entering the 1549 /// loop. 1550 /// 1551 /// * Has an (unsigned) logical induction variable that starts at zero and 1552 /// increments by one. 1553 /// 1554 /// * The loop's CFG itself has no side-effects. The OpenMP specification 1555 /// itself allows side-effects, but the order in which they happen, including 1556 /// how often or whether at all, is unspecified. We expect that the frontend 1557 /// will emit those side-effect instructions somewhere (e.g. before the loop) 1558 /// such that the CanonicalLoopInfo itself can be side-effect free. 1559 /// 1560 /// Keep in mind that CanonicalLoopInfo is meant to only describe a repeated 1561 /// execution of a loop body that satifies these constraints. It does NOT 1562 /// represent arbitrary SESE regions that happen to contain a loop. Do not use 1563 /// CanonicalLoopInfo for such purposes. 1564 /// 1565 /// The control flow can be described as follows: 1566 /// 1567 /// Preheader 1568 /// | 1569 /// /-> Header 1570 /// | | 1571 /// | Cond---\ 1572 /// | | | 1573 /// | Body | 1574 /// | | | | 1575 /// | <...> | 1576 /// | | | | 1577 /// \--Latch | 1578 /// | 1579 /// Exit 1580 /// | 1581 /// After 1582 /// 1583 /// The loop is thought to start at PreheaderIP (at the Preheader's terminator, 1584 /// including) and end at AfterIP (at the After's first instruction, excluding). 1585 /// That is, instructions in the Preheader and After blocks (except the 1586 /// Preheader's terminator) are out of CanonicalLoopInfo's control and may have 1587 /// side-effects. Typically, the Preheader is used to compute the loop's trip 1588 /// count. The instructions from BodyIP (at the Body block's first instruction, 1589 /// excluding) until the Latch are also considered outside CanonicalLoopInfo's 1590 /// control and thus can have side-effects. The body block is the single entry 1591 /// point into the loop body, which may contain arbitrary control flow as long 1592 /// as all control paths eventually branch to the Latch block. 1593 /// 1594 /// TODO: Consider adding another standardized BasicBlock between Body CFG and 1595 /// Latch to guarantee that there is only a single edge to the latch. It would 1596 /// make loop transformations easier to not needing to consider multiple 1597 /// predecessors of the latch (See redirectAllPredecessorsTo) and would give us 1598 /// an equivalant to PreheaderIP, AfterIP and BodyIP for inserting code that 1599 /// executes after each body iteration. 1600 /// 1601 /// There must be no loop-carried dependencies through llvm::Values. This is 1602 /// equivalant to that the Latch has no PHINode and the Header's only PHINode is 1603 /// for the induction variable. 1604 /// 1605 /// All code in Header, Cond, Latch and Exit (plus the terminator of the 1606 /// Preheader) are CanonicalLoopInfo's responsibility and their build-up checked 1607 /// by assertOK(). They are expected to not be modified unless explicitly 1608 /// modifying the CanonicalLoopInfo through a methods that applies a OpenMP 1609 /// loop-associated construct such as applyWorkshareLoop, tileLoops, unrollLoop, 1610 /// etc. These methods usually invalidate the CanonicalLoopInfo and re-use its 1611 /// basic blocks. After invalidation, the CanonicalLoopInfo must not be used 1612 /// anymore as its underlying control flow may not exist anymore. 1613 /// Loop-transformation methods such as tileLoops, collapseLoops and unrollLoop 1614 /// may also return a new CanonicalLoopInfo that can be passed to other 1615 /// loop-associated construct implementing methods. These loop-transforming 1616 /// methods may either create a new CanonicalLoopInfo usually using 1617 /// createLoopSkeleton and invalidate the input CanonicalLoopInfo, or reuse and 1618 /// modify one of the input CanonicalLoopInfo and return it as representing the 1619 /// modified loop. What is done is an implementation detail of 1620 /// transformation-implementing method and callers should always assume that the 1621 /// CanonicalLoopInfo passed to it is invalidated and a new object is returned. 1622 /// Returned CanonicalLoopInfo have the same structure and guarantees as the one 1623 /// created by createCanonicalLoop, such that transforming methods do not have 1624 /// to special case where the CanonicalLoopInfo originated from. 1625 /// 1626 /// Generally, methods consuming CanonicalLoopInfo do not need an 1627 /// OpenMPIRBuilder::InsertPointTy as argument, but use the locations of the 1628 /// CanonicalLoopInfo to insert new or modify existing instructions. Unless 1629 /// documented otherwise, methods consuming CanonicalLoopInfo do not invalidate 1630 /// any InsertPoint that is outside CanonicalLoopInfo's control. Specifically, 1631 /// any InsertPoint in the Preheader, After or Block can still be used after 1632 /// calling such a method. 1633 /// 1634 /// TODO: Provide mechanisms for exception handling and cancellation points. 1635 /// 1636 /// Defined outside OpenMPIRBuilder because nested classes cannot be 1637 /// forward-declared, e.g. to avoid having to include the entire OMPIRBuilder.h. 1638 class CanonicalLoopInfo { 1639 friend class OpenMPIRBuilder; 1640 1641 private: 1642 BasicBlock *Header = nullptr; 1643 BasicBlock *Cond = nullptr; 1644 BasicBlock *Latch = nullptr; 1645 BasicBlock *Exit = nullptr; 1646 1647 /// Add the control blocks of this loop to \p BBs. 1648 /// 1649 /// This does not include any block from the body, including the one returned 1650 /// by getBody(). 1651 /// 1652 /// FIXME: This currently includes the Preheader and After blocks even though 1653 /// their content is (mostly) not under CanonicalLoopInfo's control. 1654 /// Re-evaluated whether this makes sense. 1655 void collectControlBlocks(SmallVectorImpl<BasicBlock *> &BBs); 1656 1657 /// Sets the number of loop iterations to the given value. This value must be 1658 /// valid in the condition block (i.e., defined in the preheader) and is 1659 /// interpreted as an unsigned integer. 1660 void setTripCount(Value *TripCount); 1661 1662 /// Replace all uses of the canonical induction variable in the loop body with 1663 /// a new one. 1664 /// 1665 /// The intended use case is to update the induction variable for an updated 1666 /// iteration space such that it can stay normalized in the 0...tripcount-1 1667 /// range. 1668 /// 1669 /// The \p Updater is called with the (presumable updated) current normalized 1670 /// induction variable and is expected to return the value that uses of the 1671 /// pre-updated induction values should use instead, typically dependent on 1672 /// the new induction variable. This is a lambda (instead of e.g. just passing 1673 /// the new value) to be able to distinguish the uses of the pre-updated 1674 /// induction variable and uses of the induction varible to compute the 1675 /// updated induction variable value. 1676 void mapIndVar(llvm::function_ref<Value *(Instruction *)> Updater); 1677 1678 public: 1679 /// Returns whether this object currently represents the IR of a loop. If 1680 /// returning false, it may have been consumed by a loop transformation or not 1681 /// been intialized. Do not use in this case; 1682 bool isValid() const { return Header; } 1683 1684 /// The preheader ensures that there is only a single edge entering the loop. 1685 /// Code that must be execute before any loop iteration can be emitted here, 1686 /// such as computing the loop trip count and begin lifetime markers. Code in 1687 /// the preheader is not considered part of the canonical loop. 1688 BasicBlock *getPreheader() const; 1689 1690 /// The header is the entry for each iteration. In the canonical control flow, 1691 /// it only contains the PHINode for the induction variable. 1692 BasicBlock *getHeader() const { 1693 assert(isValid() && "Requires a valid canonical loop"); 1694 return Header; 1695 } 1696 1697 /// The condition block computes whether there is another loop iteration. If 1698 /// yes, branches to the body; otherwise to the exit block. 1699 BasicBlock *getCond() const { 1700 assert(isValid() && "Requires a valid canonical loop"); 1701 return Cond; 1702 } 1703 1704 /// The body block is the single entry for a loop iteration and not controlled 1705 /// by CanonicalLoopInfo. It can contain arbitrary control flow but must 1706 /// eventually branch to the \p Latch block. 1707 BasicBlock *getBody() const { 1708 assert(isValid() && "Requires a valid canonical loop"); 1709 return cast<BranchInst>(Cond->getTerminator())->getSuccessor(0); 1710 } 1711 1712 /// Reaching the latch indicates the end of the loop body code. In the 1713 /// canonical control flow, it only contains the increment of the induction 1714 /// variable. 1715 BasicBlock *getLatch() const { 1716 assert(isValid() && "Requires a valid canonical loop"); 1717 return Latch; 1718 } 1719 1720 /// Reaching the exit indicates no more iterations are being executed. 1721 BasicBlock *getExit() const { 1722 assert(isValid() && "Requires a valid canonical loop"); 1723 return Exit; 1724 } 1725 1726 /// The after block is intended for clean-up code such as lifetime end 1727 /// markers. It is separate from the exit block to ensure, analogous to the 1728 /// preheader, it having just a single entry edge and being free from PHI 1729 /// nodes should there be multiple loop exits (such as from break 1730 /// statements/cancellations). 1731 BasicBlock *getAfter() const { 1732 assert(isValid() && "Requires a valid canonical loop"); 1733 return Exit->getSingleSuccessor(); 1734 } 1735 1736 /// Returns the llvm::Value containing the number of loop iterations. It must 1737 /// be valid in the preheader and always interpreted as an unsigned integer of 1738 /// any bit-width. 1739 Value *getTripCount() const { 1740 assert(isValid() && "Requires a valid canonical loop"); 1741 Instruction *CmpI = &Cond->front(); 1742 assert(isa<CmpInst>(CmpI) && "First inst must compare IV with TripCount"); 1743 return CmpI->getOperand(1); 1744 } 1745 1746 /// Returns the instruction representing the current logical induction 1747 /// variable. Always unsigned, always starting at 0 with an increment of one. 1748 Instruction *getIndVar() const { 1749 assert(isValid() && "Requires a valid canonical loop"); 1750 Instruction *IndVarPHI = &Header->front(); 1751 assert(isa<PHINode>(IndVarPHI) && "First inst must be the IV PHI"); 1752 return IndVarPHI; 1753 } 1754 1755 /// Return the type of the induction variable (and the trip count). 1756 Type *getIndVarType() const { 1757 assert(isValid() && "Requires a valid canonical loop"); 1758 return getIndVar()->getType(); 1759 } 1760 1761 /// Return the insertion point for user code before the loop. 1762 OpenMPIRBuilder::InsertPointTy getPreheaderIP() const { 1763 assert(isValid() && "Requires a valid canonical loop"); 1764 BasicBlock *Preheader = getPreheader(); 1765 return {Preheader, std::prev(Preheader->end())}; 1766 }; 1767 1768 /// Return the insertion point for user code in the body. 1769 OpenMPIRBuilder::InsertPointTy getBodyIP() const { 1770 assert(isValid() && "Requires a valid canonical loop"); 1771 BasicBlock *Body = getBody(); 1772 return {Body, Body->begin()}; 1773 }; 1774 1775 /// Return the insertion point for user code after the loop. 1776 OpenMPIRBuilder::InsertPointTy getAfterIP() const { 1777 assert(isValid() && "Requires a valid canonical loop"); 1778 BasicBlock *After = getAfter(); 1779 return {After, After->begin()}; 1780 }; 1781 1782 Function *getFunction() const { 1783 assert(isValid() && "Requires a valid canonical loop"); 1784 return Header->getParent(); 1785 } 1786 1787 /// Consistency self-check. 1788 void assertOK() const; 1789 1790 /// Invalidate this loop. That is, the underlying IR does not fulfill the 1791 /// requirements of an OpenMP canonical loop anymore. 1792 void invalidate(); 1793 }; 1794 1795 } // end namespace llvm 1796 1797 #endif // LLVM_FRONTEND_OPENMP_OMPIRBUILDER_H 1798