Coverage Report

Created: 2017-03-24 03:18

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