Coverage Report

Created: 2019-02-20 07:29

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/include/polly/CodeGen/LoopGenerators.h
Line
Count
Source
1
//===- LoopGenerators.h - IR helper to create loops -------------*- 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 contains functions to create scalar and OpenMP parallel loops
10
// as LLVM-IR.
11
//
12
//===----------------------------------------------------------------------===//
13
#ifndef POLLY_LOOP_GENERATORS_H
14
#define POLLY_LOOP_GENERATORS_H
15
16
#include "polly/CodeGen/IRBuilder.h"
17
#include "polly/Support/ScopHelper.h"
18
19
#include "llvm/ADT/SetVector.h"
20
#include "llvm/IR/ValueMap.h"
21
22
namespace llvm {
23
class Value;
24
class Pass;
25
class BasicBlock;
26
} // namespace llvm
27
28
namespace polly {
29
using namespace llvm;
30
31
/// Create a scalar do/for-style loop.
32
///
33
/// @param LowerBound         The starting value of the induction variable.
34
/// @param UpperBound         The upper bound of the induction variable.
35
/// @param Stride             The value by which the induction variable
36
///                           is incremented.
37
///
38
/// @param Builder            The builder used to create the loop.
39
/// @param P                  A pointer to the pass that uses this function.
40
///                           It is used to update analysis information.
41
/// @param LI                 The loop info for the current function
42
/// @param DT                 The dominator tree we need to update
43
/// @param ExitBlock          The block the loop will exit to.
44
/// @param Predicate          The predicate used to generate the upper loop
45
///                           bound.
46
/// @param Annotator          This function can (optionally) take
47
///                           a ScopAnnotator which
48
///                           annotates loops and alias information in the SCoP.
49
/// @param Parallel           If this loop should be marked parallel in
50
///                           the Annotator.
51
/// @param UseGuard           Create a guard in front of the header to check if
52
///                           the loop is executed at least once, otherwise just
53
///                           assume it.
54
/// @param LoopVectDisabled   If the Loop vectorizer should be disabled for this
55
///                           loop.
56
///
57
/// @return Value*    The newly created induction variable for this loop.
58
Value *createLoop(Value *LowerBound, Value *UpperBound, Value *Stride,
59
                  PollyIRBuilder &Builder, LoopInfo &LI, DominatorTree &DT,
60
                  BasicBlock *&ExitBlock, ICmpInst::Predicate Predicate,
61
                  ScopAnnotator *Annotator = NULL, bool Parallel = false,
62
                  bool UseGuard = true, bool LoopVectDisabled = false);
63
64
/// The ParallelLoopGenerator allows to create parallelized loops
65
///
66
/// To parallelize a loop, we perform the following steps:
67
///   o  Generate a subfunction which will hold the loop body.
68
///   o  Create a struct to hold all outer values needed in the loop body.
69
///   o  Create calls to a runtime library to achieve the actual parallelism.
70
///      These calls will spawn and join threads, define how the work (here the
71
///      iterations) are distributed between them and make sure each has access
72
///      to the struct holding all needed values.
73
///
74
/// At the moment we support only one parallel runtime, OpenMP.
75
///
76
/// If we parallelize the outer loop of the following loop nest,
77
///
78
///   S0;
79
///   for (int i = 0; i < N; i++)
80
///     for (int j = 0; j < M; j++)
81
///       S1(i, j);
82
///   S2;
83
///
84
/// we will generate the following code (with different runtime function names):
85
///
86
///   S0;
87
///   auto *values = storeValuesIntoStruct();
88
///   // Execute subfunction with multiple threads
89
///   spawn_threads(subfunction, values);
90
///   join_threads();
91
///   S2;
92
///
93
///  // This function is executed in parallel by different threads
94
///   void subfunction(values) {
95
///     while (auto *WorkItem = getWorkItem()) {
96
///       int LB = WorkItem.begin();
97
///       int UB = WorkItem.end();
98
///       for (int i = LB; i < UB; i++)
99
///         for (int j = 0; j < M; j++)
100
///           S1(i, j);
101
///     }
102
///     cleanup_thread();
103
///   }
104
class ParallelLoopGenerator {
105
public:
106
  /// Create a parallel loop generator for the current function.
107
  ParallelLoopGenerator(PollyIRBuilder &Builder, LoopInfo &LI,
108
                        DominatorTree &DT, const DataLayout &DL)
109
      : Builder(Builder), LI(LI), DT(DT),
110
        LongType(
111
            Type::getIntNTy(Builder.getContext(), DL.getPointerSizeInBits())),
112
30
        M(Builder.GetInsertBlock()->getParent()->getParent()) {}
113
114
  /// Create a parallel loop.
115
  ///
116
  /// This function is the main function to automatically generate a parallel
117
  /// loop with all its components.
118
  ///
119
  /// @param LB        The lower bound for the loop we parallelize.
120
  /// @param UB        The upper bound for the loop we parallelize.
121
  /// @param Stride    The stride of the loop we parallelize.
122
  /// @param Values    A set of LLVM-IR Values that should be available in
123
  ///                  the new loop body.
124
  /// @param VMap      A map to allow outside access to the new versions of
125
  ///                  the values in @p Values.
126
  /// @param LoopBody  A pointer to an iterator that is set to point to the
127
  ///                  body of the created loop. It should be used to insert
128
  ///                  instructions that form the actual loop body.
129
  ///
130
  /// @return The newly created induction variable for this loop.
131
  Value *createParallelLoop(Value *LB, Value *UB, Value *Stride,
132
                            SetVector<Value *> &Values, ValueMapT &VMap,
133
                            BasicBlock::iterator *LoopBody);
134
135
private:
136
  /// The IR builder we use to create instructions.
137
  PollyIRBuilder &Builder;
138
139
  /// The loop info of the current function we need to update.
140
  LoopInfo &LI;
141
142
  /// The dominance tree of the current function we need to update.
143
  DominatorTree &DT;
144
145
  /// The type of a "long" on this hardware used for backend calls.
146
  Type *LongType;
147
148
  /// The current module
149
  Module *M;
150
151
public:
152
  /// The functions below can be used if one does not want to generate a
153
  /// specific OpenMP parallel loop, but generate individual parts of it
154
  /// (e.g., the subfunction definition).
155
156
  /// Create a runtime library call to spawn the worker threads.
157
  ///
158
  /// @param SubFn      The subfunction which holds the loop body.
159
  /// @param SubFnParam The parameter for the subfunction (basically the struct
160
  ///                   filled with the outside values).
161
  /// @param LB         The lower bound for the loop we parallelize.
162
  /// @param UB         The upper bound for the loop we parallelize.
163
  /// @param Stride     The stride of the loop we parallelize.
164
  void createCallSpawnThreads(Value *SubFn, Value *SubFnParam, Value *LB,
165
                              Value *UB, Value *Stride);
166
167
  /// Create a runtime library call to join the worker threads.
168
  void createCallJoinThreads();
169
170
  /// Create a runtime library call to get the next work item.
171
  ///
172
  /// @param LBPtr A pointer value to store the work item begin in.
173
  /// @param UBPtr A pointer value to store the work item end in.
174
  ///
175
  /// @returns A true value if the work item is not empty.
176
  Value *createCallGetWorkItem(Value *LBPtr, Value *UBPtr);
177
178
  /// Create a runtime library call to allow cleanup of the thread.
179
  ///
180
  /// @note This function is called right before the thread will exit the
181
  ///       subfunction and only if the runtime system depends on it.
182
  void createCallCleanupThread();
183
184
  /// Create a struct for all @p Values and store them in there.
185
  ///
186
  /// @param Values The values which should be stored in the struct.
187
  ///
188
  /// @return The created struct.
189
  AllocaInst *storeValuesIntoStruct(SetVector<Value *> &Values);
190
191
  /// Extract all values from the @p Struct and construct the mapping.
192
  ///
193
  /// @param Values The values which were stored in the struct.
194
  /// @param Struct The struct holding all the values in @p Values.
195
  /// @param VMap   A map to associate every element of @p Values with the
196
  ///               new llvm value loaded from the @p Struct.
197
  void extractValuesFromStruct(SetVector<Value *> Values, Type *Ty,
198
                               Value *Struct, ValueMapT &VMap);
199
200
  /// Create the definition of the parallel subfunction.
201
  Function *createSubFnDefinition();
202
203
  /// Create the parallel subfunction.
204
  ///
205
  /// @param Stride The induction variable increment.
206
  /// @param Struct A struct holding all values in @p Values.
207
  /// @param Values A set of LLVM-IR Values that should be available in
208
  ///               the new loop body.
209
  /// @param VMap   A map to allow outside access to the new versions of
210
  ///               the values in @p Values.
211
  /// @param SubFn  The newly created subfunction is returned here.
212
  ///
213
  /// @return The newly created induction variable.
214
  Value *createSubFn(Value *Stride, AllocaInst *Struct,
215
                     SetVector<Value *> UsedValues, ValueMapT &VMap,
216
                     Function **SubFn);
217
};
218
} // end namespace polly
219
#endif