llvm/polly/include/polly/CodeGen/LoopGenerators.h

//===- LoopGenerators.h - IR helper to create loops -------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains functions to create scalar and OpenMP parallel loops
// as LLVM-IR.
//
//===----------------------------------------------------------------------===//
#ifndef POLLY_LOOP_GENERATORS_H
#define POLLY_LOOP_GENERATORS_H

#include "polly/CodeGen/IRBuilder.h"
#include "polly/Support/ScopHelper.h"
#include "llvm/ADT/SetVector.h"

namespace polly {
AllocaInst;
BasicBlock;
DataLayout;
DominatorTree;
Function;
ICmpInst;
LoopInfo;
Module;
SetVector;
Type;
Value;

/// General scheduling types of parallel OpenMP for loops.
/// Initialization values taken from OpenMP's enum in kmp.h: sched_type.
/// Currently, only 'static' scheduling may change from chunked to non-chunked.
enum class OMPGeneralSchedulingType { … };

extern int PollyNumThreads;
extern OMPGeneralSchedulingType PollyScheduling;
extern int PollyChunkSize;

/// Create a scalar do/for-style loop.
///
/// @param LowerBound         The starting value of the induction variable.
/// @param UpperBound         The upper bound of the induction variable.
/// @param Stride             The value by which the induction variable
///                           is incremented.
///
/// @param Builder            The builder used to create the loop.
/// @param P                  A pointer to the pass that uses this function.
///                           It is used to update analysis information.
/// @param LI                 The loop info we need to update
/// @param DT                 The dominator tree we need to update
/// @param ExitBlock          The block the loop will exit to.
/// @param Predicate          The predicate used to generate the upper loop
///                           bound.
/// @param Annotator          This function can (optionally) take
///                           a ScopAnnotator which
///                           annotates loops and alias information in the SCoP.
/// @param Parallel           If this loop should be marked parallel in
///                           the Annotator.
/// @param UseGuard           Create a guard in front of the header to check if
///                           the loop is executed at least once, otherwise just
///                           assume it.
/// @param LoopVectDisabled   If the Loop vectorizer should be disabled for this
///                           loop.
///
/// @return Value*    The newly created induction variable for this loop.
Value *createLoop(Value *LowerBound, Value *UpperBound, Value *Stride,
                  PollyIRBuilder &Builder, LoopInfo &LI, DominatorTree &DT,
                  BasicBlock *&ExitBlock, ICmpInst::Predicate Predicate,
                  ScopAnnotator *Annotator = nullptr, bool Parallel = false,
                  bool UseGuard = true, bool LoopVectDisabled = false);

/// Create a DebugLoc representing generated instructions.
///
/// The IR verifier requires !dbg metadata to be set in some situations. For
/// instance, if an (inlinable) function has debug info, all its call site must
/// have debug info as well.
llvm::DebugLoc createDebugLocForGeneratedCode(Function *F);

/// The ParallelLoopGenerator allows to create parallelized loops
///
/// To parallelize a loop, we perform the following steps:
///   o  Generate a subfunction which will hold the loop body.
///   o  Create a struct to hold all outer values needed in the loop body.
///   o  Create calls to a runtime library to achieve the actual parallelism.
///      These calls will spawn and join threads, define how the work (here the
///      iterations) are distributed between them and make sure each has access
///      to the struct holding all needed values.
///
/// At the moment we support only one parallel runtime, OpenMP.
///
/// If we parallelize the outer loop of the following loop nest,
///
///   S0;
///   for (int i = 0; i < N; i++)
///     for (int j = 0; j < M; j++)
///       S1(i, j);
///   S2;
///
/// we will generate the following code (with different runtime function names):
///
///   S0;
///   auto *values = storeValuesIntoStruct();
///   // Execute subfunction with multiple threads
///   spawn_threads(subfunction, values);
///   join_threads();
///   S2;
///
///  // This function is executed in parallel by different threads
///   void subfunction(values) {
///     while (auto *WorkItem = getWorkItem()) {
///       int LB = WorkItem.begin();
///       int UB = WorkItem.end();
///       for (int i = LB; i < UB; i++)
///         for (int j = 0; j < M; j++)
///           S1(i, j);
///     }
///     cleanup_thread();
///   }
class ParallelLoopGenerator { … };
} // end namespace polly
#endif