Coverage Report

Created: 2019-04-21 11:35

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/CodeGen/BlockGenerators.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- BlockGenerators.cpp - Generate code for statements -----*- 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 implements the BlockGenerator and VectorBlockGenerator classes,
10
// which generate sequential code and vectorized code for a polyhedral
11
// statement, respectively.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "polly/CodeGen/BlockGenerators.h"
16
#include "polly/CodeGen/IslExprBuilder.h"
17
#include "polly/CodeGen/RuntimeDebugBuilder.h"
18
#include "polly/Options.h"
19
#include "polly/ScopInfo.h"
20
#include "polly/Support/ScopHelper.h"
21
#include "polly/Support/VirtualInstruction.h"
22
#include "llvm/Analysis/LoopInfo.h"
23
#include "llvm/Analysis/RegionInfo.h"
24
#include "llvm/Analysis/ScalarEvolution.h"
25
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
26
#include "llvm/Transforms/Utils/Local.h"
27
#include "isl/ast.h"
28
#include <deque>
29
30
using namespace llvm;
31
using namespace polly;
32
33
static cl::opt<bool> Aligned("enable-polly-aligned",
34
                             cl::desc("Assumed aligned memory accesses."),
35
                             cl::Hidden, cl::init(false), cl::ZeroOrMore,
36
                             cl::cat(PollyCategory));
37
38
bool PollyDebugPrinting;
39
static cl::opt<bool, true> DebugPrintingX(
40
    "polly-codegen-add-debug-printing",
41
    cl::desc("Add printf calls that show the values loaded/stored."),
42
    cl::location(PollyDebugPrinting), cl::Hidden, cl::init(false),
43
    cl::ZeroOrMore, cl::cat(PollyCategory));
44
45
static cl::opt<bool> TraceStmts(
46
    "polly-codegen-trace-stmts",
47
    cl::desc("Add printf calls that print the statement being executed"),
48
    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
49
50
static cl::opt<bool> TraceScalars(
51
    "polly-codegen-trace-scalars",
52
    cl::desc("Add printf calls that print the values of all scalar values "
53
             "used in a statement. Requires -polly-codegen-trace-stmts."),
54
    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
55
56
BlockGenerator::BlockGenerator(
57
    PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,
58
    AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap,
59
    ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
60
    : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
61
      EntryBB(nullptr), ScalarMap(ScalarMap), EscapeMap(EscapeMap),
62
89
      GlobalMap(GlobalMap), StartBlock(StartBlock) {}
63
64
Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
65
                                             ValueMapT &BBMap,
66
                                             LoopToScevMapT &LTS,
67
225
                                             Loop *L) const {
68
225
  if (!SE.isSCEVable(Old->getType()))
69
0
    return nullptr;
70
225
71
225
  const SCEV *Scev = SE.getSCEVAtScope(Old, L);
72
225
  if (!Scev)
73
0
    return nullptr;
74
225
75
225
  if (isa<SCEVCouldNotCompute>(Scev))
76
0
    return nullptr;
77
225
78
225
  const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS, SE);
79
225
  ValueMapT VTV;
80
225
  VTV.insert(BBMap.begin(), BBMap.end());
81
225
  VTV.insert(GlobalMap.begin(), GlobalMap.end());
82
225
83
225
  Scop &S = *Stmt.getParent();
84
225
  const DataLayout &DL = S.getFunction().getParent()->getDataLayout();
85
225
  auto IP = Builder.GetInsertPoint();
86
225
87
225
  assert(IP != Builder.GetInsertBlock()->end() &&
88
225
         "Only instructions can be insert points for SCEVExpander");
89
225
  Value *Expanded =
90
225
      expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV,
91
225
                    StartBlock->getSinglePredecessor());
92
225
93
225
  BBMap[Old] = Expanded;
94
225
  return Expanded;
95
225
}
96
97
Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
98
645
                                   LoopToScevMapT &LTS, Loop *L) const {
99
645
100
645
  auto lookupGlobally = [this](Value *Old) -> Value * {
101
398
    Value *New = GlobalMap.lookup(Old);
102
398
    if (!New)
103
386
      return nullptr;
104
12
105
12
    // Required by:
106
12
    // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded.ll
107
12
    // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll
108
12
    // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll
109
12
    // * Isl/CodeGen/OpenMP/invariant_base_pointers_preloaded.ll
110
12
    // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
111
12
    // * Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll
112
12
    // GlobalMap should be a mapping from (value in original SCoP) to (copied
113
12
    // value in generated SCoP), without intermediate mappings, which might
114
12
    // easily require transitiveness as well.
115
12
    if (Value *NewRemapped = GlobalMap.lookup(New))
116
1
      New = NewRemapped;
117
12
118
12
    // No test case for this code.
119
12
    if (Old->getType()->getScalarSizeInBits() <
120
12
        New->getType()->getScalarSizeInBits())
121
0
      New = Builder.CreateTruncOrBitCast(New, Old->getType());
122
12
123
12
    return New;
124
12
  };
125
645
126
645
  Value *New = nullptr;
127
645
  auto VUse = VirtualUse::create(&Stmt, L, Old, true);
128
645
  switch (VUse.getKind()) {
129
645
  case VirtualUse::Block:
130
16
    // BasicBlock are constants, but the BlockGenerator copies them.
131
16
    New = BBMap.lookup(Old);
132
16
    break;
133
645
134
645
  case VirtualUse::Constant:
135
118
    // Used by:
136
118
    // * Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll
137
118
    // Constants should not be redefined. In this case, the GlobalMap just
138
118
    // contains a mapping to the same constant, which is unnecessary, but
139
118
    // harmless.
140
118
    if ((New = lookupGlobally(Old)))
141
1
      break;
142
117
143
117
    assert(!BBMap.count(Old));
144
117
    New = Old;
145
117
    break;
146
117
147
117
  case VirtualUse::ReadOnly:
148
10
    assert(!GlobalMap.count(Old));
149
10
150
10
    // Required for:
151
10
    // * Isl/CodeGen/MemAccess/create_arrays.ll
152
10
    // * Isl/CodeGen/read-only-scalars.ll
153
10
    // * ScheduleOptimizer/pattern-matching-based-opts_10.ll
154
10
    // For some reason these reload a read-only value. The reloaded value ends
155
10
    // up in BBMap, buts its value should be identical.
156
10
    //
157
10
    // Required for:
158
10
    // * Isl/CodeGen/OpenMP/single_loop_with_param.ll
159
10
    // The parallel subfunctions need to reference the read-only value from the
160
10
    // parent function, this is done by reloading them locally.
161
10
    if ((New = BBMap.lookup(Old)))
162
9
      break;
163
1
164
1
    New = Old;
165
1
    break;
166
1
167
271
  case VirtualUse::Synthesizable:
168
271
    // Used by:
169
271
    // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
170
271
    // * Isl/CodeGen/OpenMP/recomputed-srem.ll
171
271
    // * Isl/CodeGen/OpenMP/reference-other-bb.ll
172
271
    // * Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
173
271
    // For some reason synthesizable values end up in GlobalMap. Their values
174
271
    // are the same as trySynthesizeNewValue would return. The legacy
175
271
    // implementation prioritized GlobalMap, so this is what we do here as well.
176
271
    // Ideally, synthesizable values should not end up in GlobalMap.
177
271
    if ((New = lookupGlobally(Old)))
178
2
      break;
179
269
180
269
    // Required for:
181
269
    // * Isl/CodeGen/RuntimeDebugBuilder/combine_different_values.ll
182
269
    // * Isl/CodeGen/getNumberOfIterations.ll
183
269
    // * Isl/CodeGen/non_affine_float_compare.ll
184
269
    // * ScheduleOptimizer/pattern-matching-based-opts_10.ll
185
269
    // Ideally, synthesizable values are synthesized by trySynthesizeNewValue,
186
269
    // not precomputed (SCEVExpander has its own caching mechanism).
187
269
    // These tests fail without this, but I think trySynthesizeNewValue would
188
269
    // just re-synthesize the same instructions.
189
269
    if ((New = BBMap.lookup(Old)))
190
44
      break;
191
225
192
225
    New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L);
193
225
    break;
194
225
195
225
  case VirtualUse::Hoisted:
196
9
    // TODO: Hoisted invariant loads should be found in GlobalMap only, but not
197
9
    // redefined locally (which will be ignored anyway). That is, the following
198
9
    // assertion should apply: assert(!BBMap.count(Old))
199
9
200
9
    New = lookupGlobally(Old);
201
9
    break;
202
225
203
225
  case VirtualUse::Intra:
204
221
  case VirtualUse::Inter:
205
221
    assert(!GlobalMap.count(Old) &&
206
221
           "Intra and inter-stmt values are never global");
207
221
    New = BBMap.lookup(Old);
208
221
    break;
209
645
  }
210
645
  assert(New && "Unexpected scalar dependence in region!");
211
645
  return New;
212
645
}
213
214
void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
215
152
                                    ValueMapT &BBMap, LoopToScevMapT &LTS) {
216
152
  // We do not generate debug intrinsics as we did not investigate how to
217
152
  // copy them correctly. At the current state, they just crash the code
218
152
  // generation as the meta-data operands are not correctly copied.
219
152
  if (isa<DbgInfoIntrinsic>(Inst))
220
0
    return;
221
152
222
152
  Instruction *NewInst = Inst->clone();
223
152
224
152
  // Replace old operands with the new ones.
225
278
  for (Value *OldOperand : Inst->operands()) {
226
278
    Value *NewOperand =
227
278
        getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));
228
278
229
278
    if (!NewOperand) {
230
0
      assert(!isa<StoreInst>(NewInst) &&
231
0
             "Store instructions are always needed!");
232
0
      NewInst->deleteValue();
233
0
      return;
234
0
    }
235
278
236
278
    NewInst->replaceUsesOfWith(OldOperand, NewOperand);
237
278
  }
238
152
239
152
  Builder.Insert(NewInst);
240
152
  BBMap[Inst] = NewInst;
241
152
242
152
  // When copying the instruction onto the Module meant for the GPU,
243
152
  // debug metadata attached to an instruction causes all related
244
152
  // metadata to be pulled into the Module. This includes the DICompileUnit,
245
152
  // which will not be listed in llvm.dbg.cu of the Module since the Module
246
152
  // doesn't contain one. This fails the verification of the Module and the
247
152
  // subsequent generation of the ASM string.
248
152
  if (NewInst->getModule() != Inst->getModule())
249
0
    NewInst->setDebugLoc(llvm::DebugLoc());
250
152
251
152
  if (!NewInst->getType()->isVoidTy())
252
140
    NewInst->setName("p_" + Inst->getName());
253
152
}
254
255
Value *
256
BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
257
                                         ValueMapT &BBMap, LoopToScevMapT &LTS,
258
227
                                         isl_id_to_ast_expr *NewAccesses) {
259
227
  const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
260
227
  return generateLocationAccessed(
261
227
      Stmt, getLoopForStmt(Stmt),
262
227
      Inst.isNull() ? 
nullptr0
: Inst.getPointerOperand(), BBMap, LTS,
263
227
      NewAccesses, MA.getId().release(), MA.getAccessValue()->getType());
264
227
}
265
266
Value *BlockGenerator::generateLocationAccessed(
267
    ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,
268
    LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id,
269
233
    Type *ExpectedType) {
270
233
  isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id);
271
233
272
233
  if (AccessExpr) {
273
33
    AccessExpr = isl_ast_expr_address_of(AccessExpr);
274
33
    auto Address = ExprBuilder->create(AccessExpr);
275
33
276
33
    // Cast the address of this memory access to a pointer type that has the
277
33
    // same element type as the original access, but uses the address space of
278
33
    // the newly generated pointer.
279
33
    auto OldPtrTy = ExpectedType->getPointerTo();
280
33
    auto NewPtrTy = Address->getType();
281
33
    OldPtrTy = PointerType::get(OldPtrTy->getElementType(),
282
33
                                NewPtrTy->getPointerAddressSpace());
283
33
284
33
    if (OldPtrTy != NewPtrTy)
285
4
      Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
286
33
    return Address;
287
33
  }
288
200
  assert(
289
200
      Pointer &&
290
200
      "If expression was not generated, must use the original pointer value");
291
200
  return getNewValue(Stmt, Pointer, BBMap, LTS, L);
292
200
}
293
294
Value *
295
BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
296
                                   LoopToScevMapT &LTS, ValueMapT &BBMap,
297
81
                                   __isl_keep isl_id_to_ast_expr *NewAccesses) {
298
81
  if (Access.isLatestArrayKind())
299
6
    return generateLocationAccessed(*Access.getStatement(), L, nullptr, BBMap,
300
6
                                    LTS, NewAccesses, Access.getId().release(),
301
6
                                    Access.getAccessValue()->getType());
302
75
303
75
  return getOrCreateAlloca(Access);
304
75
}
305
306
1.13k
Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
307
1.13k
  auto *StmtBB = Stmt.getEntryBlock();
308
1.13k
  return LI.getLoopFor(StmtBB);
309
1.13k
}
310
311
Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load,
312
                                         ValueMapT &BBMap, LoopToScevMapT &LTS,
313
92
                                         isl_id_to_ast_expr *NewAccesses) {
314
92
  if (Value *PreloadLoad = GlobalMap.lookup(Load))
315
5
    return PreloadLoad;
316
87
317
87
  Value *NewPointer =
318
87
      generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);
319
87
  Value *ScalarLoad = Builder.CreateAlignedLoad(
320
87
      NewPointer, Load->getAlignment(), Load->getName() + "_p_scalar_");
321
87
322
87
  if (PollyDebugPrinting)
323
0
    RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
324
0
                                          ": ", ScalarLoad, "\n");
325
87
326
87
  return ScalarLoad;
327
87
}
328
329
void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store,
330
                                        ValueMapT &BBMap, LoopToScevMapT &LTS,
331
106
                                        isl_id_to_ast_expr *NewAccesses) {
332
106
  MemoryAccess &MA = Stmt.getArrayAccessFor(Store);
333
106
  isl::set AccDom = MA.getAccessRelation().domain();
334
106
  std::string Subject = MA.getId().get_name();
335
106
336
106
  generateConditionalExecution(Stmt, AccDom, Subject.c_str(), [&, this]() {
337
105
    Value *NewPointer =
338
105
        generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
339
105
    Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap,
340
105
                                      LTS, getLoopForStmt(Stmt));
341
105
342
105
    if (PollyDebugPrinting)
343
0
      RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to  ", NewPointer,
344
0
                                            ": ", ValueOperand, "\n");
345
105
346
105
    Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment());
347
105
  });
348
106
}
349
350
422
bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
351
422
  Loop *L = getLoopForStmt(Stmt);
352
422
  return (Stmt.isBlockStmt() || 
!Stmt.getRegion()->contains(L)30
) &&
353
422
         
canSynthesize(Inst, *Stmt.getParent(), &SE, L)415
;
354
422
}
355
356
void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
357
                                     ValueMapT &BBMap, LoopToScevMapT &LTS,
358
363
                                     isl_id_to_ast_expr *NewAccesses) {
359
363
  // Terminator instructions control the control flow. They are explicitly
360
363
  // expressed in the clast and do not need to be copied.
361
363
  if (Inst->isTerminator())
362
6
    return;
363
357
364
357
  // Synthesizable statements will be generated on-demand.
365
357
  if (canSyntheziseInStmt(Stmt, Inst))
366
4
    return;
367
353
368
353
  if (auto *Load = dyn_cast<LoadInst>(Inst)) {
369
92
    Value *NewLoad = generateArrayLoad(Stmt, Load, BBMap, LTS, NewAccesses);
370
92
    // Compute NewLoad before its insertion in BBMap to make the insertion
371
92
    // deterministic.
372
92
    BBMap[Load] = NewLoad;
373
92
    return;
374
92
  }
375
261
376
261
  if (auto *Store = dyn_cast<StoreInst>(Inst)) {
377
106
    // Identified as redundant by -polly-simplify.
378
106
    if (!Stmt.getArrayAccessOrNULLFor(Store))
379
0
      return;
380
106
381
106
    generateArrayStore(Stmt, Store, BBMap, LTS, NewAccesses);
382
106
    return;
383
106
  }
384
155
385
155
  if (auto *PHI = dyn_cast<PHINode>(Inst)) {
386
14
    copyPHIInstruction(Stmt, PHI, BBMap, LTS);
387
14
    return;
388
14
  }
389
141
390
141
  // Skip some special intrinsics for which we do not adjust the semantics to
391
141
  // the new schedule. All others are handled like every other instruction.
392
141
  if (isIgnoredIntrinsic(Inst))
393
0
    return;
394
141
395
141
  copyInstScalar(Stmt, Inst, BBMap, LTS);
396
141
}
397
398
144
void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) {
399
144
  auto NewBB = Builder.GetInsertBlock();
400
1.06k
  for (auto I = NewBB->rbegin(); I != NewBB->rend(); 
I++925
) {
401
925
    Instruction *NewInst = &*I;
402
925
403
925
    if (!isInstructionTriviallyDead(NewInst))
404
907
      continue;
405
18
406
18
    for (auto Pair : BBMap)
407
70
      if (Pair.second == NewInst) {
408
14
        BBMap.erase(Pair.first);
409
14
      }
410
18
411
18
    NewInst->eraseFromParent();
412
18
    I = NewBB->rbegin();
413
18
  }
414
144
}
415
416
void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
417
144
                              isl_id_to_ast_expr *NewAccesses) {
418
144
  assert(Stmt.isBlockStmt() &&
419
144
         "Only block statements can be copied by the block generator");
420
144
421
144
  ValueMapT BBMap;
422
144
423
144
  BasicBlock *BB = Stmt.getBasicBlock();
424
144
  copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
425
144
  removeDeadInstructions(BB, BBMap);
426
144
}
427
428
155
BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
429
155
  BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
430
155
                                  &*Builder.GetInsertPoint(), &DT, &LI);
431
155
  CopyBB->setName("polly.stmt." + BB->getName());
432
155
  return CopyBB;
433
155
}
434
435
BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
436
                                   ValueMapT &BBMap, LoopToScevMapT &LTS,
437
144
                                   isl_id_to_ast_expr *NewAccesses) {
438
144
  BasicBlock *CopyBB = splitBB(BB);
439
144
  Builder.SetInsertPoint(&CopyBB->front());
440
144
  generateScalarLoads(Stmt, LTS, BBMap, NewAccesses);
441
144
  generateBeginStmtTrace(Stmt, LTS, BBMap);
442
144
443
144
  copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
444
144
445
144
  // After a basic block was copied store all scalars that escape this block in
446
144
  // their alloca.
447
144
  generateScalarStores(Stmt, LTS, BBMap, NewAccesses);
448
144
  return CopyBB;
449
144
}
450
451
void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
452
                            ValueMapT &BBMap, LoopToScevMapT &LTS,
453
155
                            isl_id_to_ast_expr *NewAccesses) {
454
155
  EntryBB = &CopyBB->getParent()->getEntryBlock();
455
155
456
155
  // Block statements and the entry blocks of region statement are code
457
155
  // generated from instruction lists. This allow us to optimize the
458
155
  // instructions that belong to a certain scop statement. As the code
459
155
  // structure of region statements might be arbitrary complex, optimizing the
460
155
  // instruction list is not yet supported.
461
155
  if (Stmt.isBlockStmt() || 
(11
Stmt.isRegionStmt()11
&&
Stmt.getEntryBlock() == BB11
))
462
149
    for (Instruction *Inst : Stmt.getInstructions())
463
311
      copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses);
464
6
  else
465
6
    for (Instruction &Inst : *BB)
466
24
      copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
467
155
}
468
469
77
Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
470
77
  assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind");
471
77
472
77
  return getOrCreateAlloca(Access.getLatestScopArrayInfo());
473
77
}
474
475
104
Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
476
104
  assert(!Array->isArrayKind() && "Trying to get alloca for array kind");
477
104
478
104
  auto &Addr = ScalarMap[Array];
479
104
480
104
  if (Addr) {
481
60
    // Allow allocas to be (temporarily) redirected once by adding a new
482
60
    // old-alloca-addr to new-addr mapping to GlobalMap. This functionality
483
60
    // is used for example by the OpenMP code generation where a first use
484
60
    // of a scalar while still in the host code allocates a normal alloca with
485
60
    // getOrCreateAlloca. When the values of this scalar are accessed during
486
60
    // the generation of the parallel subfunction, these values are copied over
487
60
    // to the parallel subfunction and each request for a scalar alloca slot
488
60
    // must be forwarded to the temporary in-subfunction slot. This mapping is
489
60
    // removed when the subfunction has been generated and again normal host
490
60
    // code is generated. Due to the following reasons it is not possible to
491
60
    // perform the GlobalMap lookup right after creating the alloca below, but
492
60
    // instead we need to check GlobalMap at each call to getOrCreateAlloca:
493
60
    //
494
60
    //   1) GlobalMap may be changed multiple times (for each parallel loop),
495
60
    //   2) The temporary mapping is commonly only known after the initial
496
60
    //      alloca has already been generated, and
497
60
    //   3) The original alloca value must be restored after leaving the
498
60
    //      sub-function.
499
60
    if (Value *NewAddr = GlobalMap.lookup(&*Addr))
500
1
      return NewAddr;
501
59
    return Addr;
502
59
  }
503
44
504
44
  Type *Ty = Array->getElementType();
505
44
  Value *ScalarBase = Array->getBasePtr();
506
44
  std::string NameExt;
507
44
  if (Array->isPHIKind())
508
12
    NameExt = ".phiops";
509
32
  else
510
32
    NameExt = ".s2a";
511
44
512
44
  const DataLayout &DL = Builder.GetInsertBlock()->getModule()->getDataLayout();
513
44
514
44
  Addr = new AllocaInst(Ty, DL.getAllocaAddrSpace(),
515
44
                        ScalarBase->getName() + NameExt);
516
44
  EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
517
44
  Addr->insertBefore(&*EntryBB->getFirstInsertionPt());
518
44
519
44
  return Addr;
520
44
}
521
522
20
void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) {
523
20
  Instruction *Inst = cast<Instruction>(Array->getBasePtr());
524
20
525
20
  // If there are escape users we get the alloca for this instruction and put it
526
20
  // in the EscapeMap for later finalization. Lastly, if the instruction was
527
20
  // copied multiple times we already did this and can exit.
528
20
  if (EscapeMap.count(Inst))
529
0
    return;
530
20
531
20
  EscapeUserVectorTy EscapeUsers;
532
26
  for (User *U : Inst->users()) {
533
26
534
26
    // Non-instruction user will never escape.
535
26
    Instruction *UI = dyn_cast<Instruction>(U);
536
26
    if (!UI)
537
0
      continue;
538
26
539
26
    if (S.contains(UI))
540
16
      continue;
541
10
542
10
    EscapeUsers.push_back(UI);
543
10
  }
544
20
545
20
  // Exit if no escape uses were found.
546
20
  if (EscapeUsers.empty())
547
10
    return;
548
10
549
10
  // Get or create an escape alloca for this instruction.
550
10
  auto *ScalarAddr = getOrCreateAlloca(Array);
551
10
552
10
  // Remember that this instruction has escape uses and the escape alloca.
553
10
  EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
554
10
}
555
556
void BlockGenerator::generateScalarLoads(
557
    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
558
149
    __isl_keep isl_id_to_ast_expr *NewAccesses) {
559
274
  for (MemoryAccess *MA : Stmt) {
560
274
    if (MA->isOriginalArrayKind() || 
MA->isWrite()82
)
561
245
      continue;
562
29
563
#ifndef NDEBUG
564
    auto StmtDom =
565
        Stmt.getDomain().intersect_params(Stmt.getParent()->getContext());
566
    auto AccDom = MA->getAccessRelation().domain();
567
    assert(!StmtDom.is_subset(AccDom).is_false() &&
568
           "Scalar must be loaded in all statement instances");
569
#endif
570
571
29
    auto *Address =
572
29
        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
573
29
    assert((!isa<Instruction>(Address) ||
574
29
            DT.dominates(cast<Instruction>(Address)->getParent(),
575
29
                         Builder.GetInsertBlock())) &&
576
29
           "Domination violation");
577
29
    BBMap[MA->getAccessValue()] =
578
29
        Builder.CreateLoad(Address, Address->getName() + ".reload");
579
29
  }
580
149
}
581
582
Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt,
583
4
                                              const isl::set &Subdomain) {
584
4
  isl::ast_build AstBuild = Stmt.getAstBuild();
585
4
  isl::set Domain = Stmt.getDomain();
586
4
587
4
  isl::union_map USchedule = AstBuild.get_schedule();
588
4
  USchedule = USchedule.intersect_domain(Domain);
589
4
590
4
  assert(!USchedule.is_empty());
591
4
  isl::map Schedule = isl::map::from_union_map(USchedule);
592
4
593
4
  isl::set ScheduledDomain = Schedule.range();
594
4
  isl::set ScheduledSet = Subdomain.apply(Schedule);
595
4
596
4
  isl::ast_build RestrictedBuild = AstBuild.restrict(ScheduledDomain);
597
4
598
4
  isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduledSet);
599
4
  Value *IsInSetExpr = ExprBuilder->create(IsInSet.copy());
600
4
  IsInSetExpr = Builder.CreateICmpNE(
601
4
      IsInSetExpr, ConstantInt::get(IsInSetExpr->getType(), 0));
602
4
603
4
  return IsInSetExpr;
604
4
}
605
606
void BlockGenerator::generateConditionalExecution(
607
    ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject,
608
159
    const std::function<void()> &GenThenFunc) {
609
159
  isl::set StmtDom = Stmt.getDomain();
610
159
611
159
  // If the condition is a tautology, don't generate a condition around the
612
159
  // code.
613
159
  bool IsPartialWrite =
614
159
      !StmtDom.intersect_params(Stmt.getParent()->getContext())
615
159
           .is_subset(Subdomain);
616
159
  if (!IsPartialWrite) {
617
155
    GenThenFunc();
618
155
    return;
619
155
  }
620
4
621
4
  // Generate the condition.
622
4
  Value *Cond = buildContainsCondition(Stmt, Subdomain);
623
4
624
4
  // Don't call GenThenFunc if it is never executed. An ast index expression
625
4
  // might not be defined in this case.
626
4
  if (auto *Const = dyn_cast<ConstantInt>(Cond))
627
2
    if (Const->isZero())
628
2
      return;
629
2
630
2
  BasicBlock *HeadBlock = Builder.GetInsertBlock();
631
2
  StringRef BlockName = HeadBlock->getName();
632
2
633
2
  // Generate the conditional block.
634
2
  SplitBlockAndInsertIfThen(Cond, &*Builder.GetInsertPoint(), false, nullptr,
635
2
                            &DT, &LI);
636
2
  BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator());
637
2
  BasicBlock *ThenBlock = Branch->getSuccessor(0);
638
2
  BasicBlock *TailBlock = Branch->getSuccessor(1);
639
2
640
2
  // Assign descriptive names.
641
2
  if (auto *CondInst = dyn_cast<Instruction>(Cond))
642
2
    CondInst->setName("polly." + Subject + ".cond");
643
2
  ThenBlock->setName(BlockName + "." + Subject + ".partial");
644
2
  TailBlock->setName(BlockName + ".cont");
645
2
646
2
  // Put the client code into the conditional block and continue in the merge
647
2
  // block afterwards.
648
2
  Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt());
649
2
  GenThenFunc();
650
2
  Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt());
651
2
}
652
653
0
static std::string getInstName(Value *Val) {
654
0
  std::string Result;
655
0
  raw_string_ostream OS(Result);
656
0
  Val->printAsOperand(OS, false);
657
0
  return OS.str();
658
0
}
659
660
void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT &LTS,
661
149
                                            ValueMapT &BBMap) {
662
149
  if (!TraceStmts)
663
149
    return;
664
0
665
0
  Scop *S = Stmt.getParent();
666
0
  const char *BaseName = Stmt.getBaseName();
667
0
668
0
  isl::ast_build AstBuild = Stmt.getAstBuild();
669
0
  isl::set Domain = Stmt.getDomain();
670
0
671
0
  isl::union_map USchedule = AstBuild.get_schedule().intersect_domain(Domain);
672
0
  isl::map Schedule = isl::map::from_union_map(USchedule);
673
0
  assert(Schedule.is_empty().is_false() &&
674
0
         "The stmt must have a valid instance");
675
0
676
0
  isl::multi_pw_aff ScheduleMultiPwAff =
677
0
      isl::pw_multi_aff::from_map(Schedule.reverse());
678
0
  isl::ast_build RestrictedBuild = AstBuild.restrict(Schedule.range());
679
0
680
0
  // Sequence of strings to print.
681
0
  SmallVector<llvm::Value *, 8> Values;
682
0
683
0
  // Print the name of the statement.
684
0
  // TODO: Indent by the depth of the statement instance in the schedule tree.
685
0
  Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, BaseName));
686
0
  Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "("));
687
0
688
0
  // Add the coordinate of the statement instance.
689
0
  int DomDims = ScheduleMultiPwAff.dim(isl::dim::out);
690
0
  for (int i = 0; i < DomDims; i += 1) {
691
0
    if (i > 0)
692
0
      Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ","));
693
0
694
0
    isl::ast_expr IsInSet =
695
0
        RestrictedBuild.expr_from(ScheduleMultiPwAff.get_pw_aff(i));
696
0
    Values.push_back(ExprBuilder->create(IsInSet.copy()));
697
0
  }
698
0
699
0
  if (TraceScalars) {
700
0
    Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")"));
701
0
    DenseSet<Instruction *> Encountered;
702
0
703
0
    // Add the value of each scalar (and the result of PHIs) used in the
704
0
    // statement.
705
0
    // TODO: Values used in region-statements.
706
0
    for (Instruction *Inst : Stmt.insts()) {
707
0
      if (!RuntimeDebugBuilder::isPrintable(Inst->getType()))
708
0
        continue;
709
0
710
0
      if (isa<PHINode>(Inst)) {
711
0
        Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, " "));
712
0
        Values.push_back(RuntimeDebugBuilder::getPrintableString(
713
0
            Builder, getInstName(Inst)));
714
0
        Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "="));
715
0
        Values.push_back(getNewValue(Stmt, Inst, BBMap, LTS,
716
0
                                     LI.getLoopFor(Inst->getParent())));
717
0
      } else {
718
0
        for (Value *Op : Inst->operand_values()) {
719
0
          // Do not print values that cannot change during the execution of the
720
0
          // SCoP.
721
0
          auto *OpInst = dyn_cast<Instruction>(Op);
722
0
          if (!OpInst)
723
0
            continue;
724
0
          if (!S->contains(OpInst))
725
0
            continue;
726
0
727
0
          // Print each scalar at most once, and exclude values defined in the
728
0
          // statement itself.
729
0
          if (Encountered.count(OpInst))
730
0
            continue;
731
0
732
0
          Values.push_back(
733
0
              RuntimeDebugBuilder::getPrintableString(Builder, " "));
734
0
          Values.push_back(RuntimeDebugBuilder::getPrintableString(
735
0
              Builder, getInstName(OpInst)));
736
0
          Values.push_back(
737
0
              RuntimeDebugBuilder::getPrintableString(Builder, "="));
738
0
          Values.push_back(getNewValue(Stmt, OpInst, BBMap, LTS,
739
0
                                       LI.getLoopFor(Inst->getParent())));
740
0
          Encountered.insert(OpInst);
741
0
        }
742
0
      }
743
0
744
0
      Encountered.insert(Inst);
745
0
    }
746
0
747
0
    Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "\n"));
748
0
  } else {
749
0
    Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")\n"));
750
0
  }
751
0
752
0
  RuntimeDebugBuilder::createCPUPrinter(Builder, ArrayRef<Value *>(Values));
753
0
}
754
755
void BlockGenerator::generateScalarStores(
756
    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
757
144
    __isl_keep isl_id_to_ast_expr *NewAccesses) {
758
144
  Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
759
144
760
144
  assert(Stmt.isBlockStmt() &&
761
144
         "Region statements need to use the generateScalarStores() function in "
762
144
         "the RegionGenerator");
763
144
764
256
  for (MemoryAccess *MA : Stmt) {
765
256
    if (MA->isOriginalArrayKind() || 
MA->isRead()74
)
766
208
      continue;
767
48
768
48
    isl::set AccDom = MA->getAccessRelation().domain();
769
48
    std::string Subject = MA->getId().get_name();
770
48
771
48
    generateConditionalExecution(
772
48
        Stmt, AccDom, Subject.c_str(), [&, this, MA]() {
773
47
          Value *Val = MA->getAccessValue();
774
47
          if (MA->isAnyPHIKind()) {
775
27
            assert(MA->getIncoming().size() >= 1 &&
776
27
                   "Block statements have exactly one exiting block, or "
777
27
                   "multiple but "
778
27
                   "with same incoming block and value");
779
27
            assert(std::all_of(MA->getIncoming().begin(),
780
27
                               MA->getIncoming().end(),
781
27
                               [&](std::pair<BasicBlock *, Value *> p) -> bool {
782
27
                                 return p.first == Stmt.getBasicBlock();
783
27
                               }) &&
784
27
                   "Incoming block must be statement's block");
785
27
            Val = MA->getIncoming()[0].second;
786
27
          }
787
47
          auto Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,
788
47
                                            BBMap, NewAccesses);
789
47
790
47
          Val = getNewValue(Stmt, Val, BBMap, LTS, L);
791
47
          assert((!isa<Instruction>(Val) ||
792
47
                  DT.dominates(cast<Instruction>(Val)->getParent(),
793
47
                               Builder.GetInsertBlock())) &&
794
47
                 "Domination violation");
795
47
          assert((!isa<Instruction>(Address) ||
796
47
                  DT.dominates(cast<Instruction>(Address)->getParent(),
797
47
                               Builder.GetInsertBlock())) &&
798
47
                 "Domination violation");
799
47
800
47
          // The new Val might have a different type than the old Val due to
801
47
          // ScalarEvolution looking through bitcasts.
802
47
          if (Val->getType() != Address->getType()->getPointerElementType())
803
1
            Address = Builder.CreateBitOrPointerCast(
804
1
                Address, Val->getType()->getPointerTo());
805
47
806
47
          Builder.CreateStore(Val, Address);
807
47
        });
808
48
  }
809
144
}
810
811
87
void BlockGenerator::createScalarInitialization(Scop &S) {
812
87
  BasicBlock *ExitBB = S.getExit();
813
87
  BasicBlock *PreEntryBB = S.getEnteringBlock();
814
87
815
87
  Builder.SetInsertPoint(&*StartBlock->begin());
816
87
817
192
  for (auto &Array : S.arrays()) {
818
192
    if (Array->getNumberOfDimensions() != 0)
819
146
      continue;
820
46
    if (Array->isPHIKind()) {
821
13
      // For PHI nodes, the only values we need to store are the ones that
822
13
      // reach the PHI node from outside the region. In general there should
823
13
      // only be one such incoming edge and this edge should enter through
824
13
      // 'PreEntryBB'.
825
13
      auto PHI = cast<PHINode>(Array->getBasePtr());
826
13
827
39
      for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; 
BI++26
)
828
26
        if (!S.contains(*BI) && 
*BI != PreEntryBB4
)
829
26
          
llvm_unreachable0
("Incoming edges from outside the scop should always "
830
13
                           "come from PreEntryBB");
831
13
832
13
      int Idx = PHI->getBasicBlockIndex(PreEntryBB);
833
13
      if (Idx < 0)
834
9
        continue;
835
4
836
4
      Value *ScalarValue = PHI->getIncomingValue(Idx);
837
4
838
4
      Builder.CreateStore(ScalarValue, getOrCreateAlloca(Array));
839
4
      continue;
840
4
    }
841
33
842
33
    auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
843
33
844
33
    if (Inst && 
S.contains(Inst)29
)
845
20
      continue;
846
13
847
13
    // PHI nodes that are not marked as such in their SAI object are either exit
848
13
    // PHI nodes we model as common scalars but without initialization, or
849
13
    // incoming phi nodes that need to be initialized. Check if the first is the
850
13
    // case for Inst and do not create and initialize memory if so.
851
13
    if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))
852
9
      if (!S.hasSingleExitEdge() && 
PHI->getBasicBlockIndex(ExitBB) >= 08
)
853
8
        continue;
854
5
855
5
    Builder.CreateStore(Array->getBasePtr(), getOrCreateAlloca(Array));
856
5
  }
857
87
}
858
859
87
void BlockGenerator::createScalarFinalization(Scop &S) {
860
87
  // The exit block of the __unoptimized__ region.
861
87
  BasicBlock *ExitBB = S.getExitingBlock();
862
87
  // The merge block __just after__ the region and the optimized region.
863
87
  BasicBlock *MergeBB = S.getExit();
864
87
865
87
  // The exit block of the __optimized__ region.
866
87
  BasicBlock *OptExitBB = *(pred_begin(MergeBB));
867
87
  if (OptExitBB == ExitBB)
868
0
    OptExitBB = *(++pred_begin(MergeBB));
869
87
870
87
  Builder.SetInsertPoint(OptExitBB->getTerminator());
871
87
  for (const auto &EscapeMapping : EscapeMap) {
872
10
    // Extract the escaping instruction and the escaping users as well as the
873
10
    // alloca the instruction was demoted to.
874
10
    Instruction *EscapeInst = EscapeMapping.first;
875
10
    const auto &EscapeMappingValue = EscapeMapping.second;
876
10
    const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;
877
10
    Value *ScalarAddr = EscapeMappingValue.first;
878
10
879
10
    // Reload the demoted instruction in the optimized version of the SCoP.
880
10
    Value *EscapeInstReload =
881
10
        Builder.CreateLoad(ScalarAddr, EscapeInst->getName() + ".final_reload");
882
10
    EscapeInstReload =
883
10
        Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());
884
10
885
10
    // Create the merge PHI that merges the optimized and unoptimized version.
886
10
    PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
887
10
                                        EscapeInst->getName() + ".merge");
888
10
    MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
889
10
890
10
    // Add the respective values to the merge PHI.
891
10
    MergePHI->addIncoming(EscapeInstReload, OptExitBB);
892
10
    MergePHI->addIncoming(EscapeInst, ExitBB);
893
10
894
10
    // The information of scalar evolution about the escaping instruction needs
895
10
    // to be revoked so the new merged instruction will be used.
896
10
    if (SE.isSCEVable(EscapeInst->getType()))
897
8
      SE.forgetValue(EscapeInst);
898
10
899
10
    // Replace all uses of the demoted instruction with the merge PHI.
900
10
    for (Instruction *EUser : EscapeUsers)
901
10
      EUser->replaceUsesOfWith(EscapeInst, MergePHI);
902
10
  }
903
87
}
904
905
87
void BlockGenerator::findOutsideUsers(Scop &S) {
906
192
  for (auto &Array : S.arrays()) {
907
192
908
192
    if (Array->getNumberOfDimensions() != 0)
909
146
      continue;
910
46
911
46
    if (Array->isPHIKind())
912
13
      continue;
913
33
914
33
    auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
915
33
916
33
    if (!Inst)
917
4
      continue;
918
29
919
29
    // Scop invariant hoisting moves some of the base pointers out of the scop.
920
29
    // We can ignore these, as the invariant load hoisting already registers the
921
29
    // relevant outside users.
922
29
    if (!S.contains(Inst))
923
9
      continue;
924
20
925
20
    handleOutsideUsers(S, Array);
926
20
  }
927
87
}
928
929
87
void BlockGenerator::createExitPHINodeMerges(Scop &S) {
930
87
  if (S.hasSingleExitEdge())
931
71
    return;
932
16
933
16
  auto *ExitBB = S.getExitingBlock();
934
16
  auto *MergeBB = S.getExit();
935
16
  auto *AfterMergeBB = MergeBB->getSingleSuccessor();
936
16
  BasicBlock *OptExitBB = *(pred_begin(MergeBB));
937
16
  if (OptExitBB == ExitBB)
938
0
    OptExitBB = *(++pred_begin(MergeBB));
939
16
940
16
  Builder.SetInsertPoint(OptExitBB->getTerminator());
941
16
942
33
  for (auto &SAI : S.arrays()) {
943
33
    auto *Val = SAI->getBasePtr();
944
33
945
33
    // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
946
33
    // the original PHI's value or the reloaded incoming values from the
947
33
    // generated code. An llvm::Value is merged between the original code's
948
33
    // value or the generated one.
949
33
    if (!SAI->isExitPHIKind())
950
25
      continue;
951
8
952
8
    PHINode *PHI = dyn_cast<PHINode>(Val);
953
8
    if (!PHI)
954
0
      continue;
955
8
956
8
    if (PHI->getParent() != AfterMergeBB)
957
0
      continue;
958
8
959
8
    std::string Name = PHI->getName();
960
8
    Value *ScalarAddr = getOrCreateAlloca(SAI);
961
8
    Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload");
962
8
    Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
963
8
    Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
964
8
    assert((!isa<Instruction>(OriginalValue) ||
965
8
            cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&
966
8
           "Original value must no be one we just generated.");
967
8
    auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
968
8
    MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
969
8
    MergePHI->addIncoming(Reload, OptExitBB);
970
8
    MergePHI->addIncoming(OriginalValue, ExitBB);
971
8
    int Idx = PHI->getBasicBlockIndex(MergeBB);
972
8
    PHI->setIncomingValue(Idx, MergePHI);
973
8
  }
974
16
}
975
976
87
void BlockGenerator::invalidateScalarEvolution(Scop &S) {
977
87
  for (auto &Stmt : S)
978
152
    if (Stmt.isCopyStmt())
979
2
      continue;
980
150
    else if (Stmt.isBlockStmt())
981
145
      for (auto &Inst : *Stmt.getBasicBlock())
982
1.67k
        SE.forgetValue(&Inst);
983
5
    else if (Stmt.isRegionStmt())
984
5
      for (auto *BB : Stmt.getRegion()->blocks())
985
11
        for (auto &Inst : *BB)
986
47
          SE.forgetValue(&Inst);
987
5
    else
988
5
      
llvm_unreachable0
("Unexpected statement type found");
989
87
990
87
  // Invalidate SCEV of loops surrounding the EscapeUsers.
991
87
  for (const auto &EscapeMapping : EscapeMap) {
992
10
    const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second;
993
10
    for (Instruction *EUser : EscapeUsers) {
994
10
      if (Loop *L = LI.getLoopFor(EUser->getParent()))
995
12
        
while (6
L) {
996
6
          SE.forgetLoop(L);
997
6
          L = L->getParentLoop();
998
6
        }
999
10
    }
1000
10
  }
1001
87
}
1002
1003
87
void BlockGenerator::finalizeSCoP(Scop &S) {
1004
87
  findOutsideUsers(S);
1005
87
  createScalarInitialization(S);
1006
87
  createExitPHINodeMerges(S);
1007
87
  createScalarFinalization(S);
1008
87
  invalidateScalarEvolution(S);
1009
87
}
1010
1011
VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
1012
                                           std::vector<LoopToScevMapT> &VLTS,
1013
                                           isl_map *Schedule)
1014
11
    : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
1015
11
  assert(Schedule && "No statement domain provided");
1016
11
}
1017
1018
Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old,
1019
                                            ValueMapT &VectorMap,
1020
                                            VectorValueMapT &ScalarMaps,
1021
19
                                            Loop *L) {
1022
19
  if (Value *NewValue = VectorMap.lookup(Old))
1023
18
    return NewValue;
1024
1
1025
1
  int Width = getVectorWidth();
1026
1
1027
1
  Value *Vector = UndefValue::get(VectorType::get(Old->getType(), Width));
1028
1
1029
5
  for (int Lane = 0; Lane < Width; 
Lane++4
)
1030
4
    Vector = Builder.CreateInsertElement(
1031
4
        Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L),
1032
4
        Builder.getInt32(Lane));
1033
1
1034
1
  VectorMap[Old] = Vector;
1035
1
1036
1
  return Vector;
1037
1
}
1038
1039
16
Type *VectorBlockGenerator::getVectorPtrTy(const Value *Val, int Width) {
1040
16
  PointerType *PointerTy = dyn_cast<PointerType>(Val->getType());
1041
16
  assert(PointerTy && "PointerType expected");
1042
16
1043
16
  Type *ScalarType = PointerTy->getElementType();
1044
16
  VectorType *VectorType = VectorType::get(ScalarType, Width);
1045
16
1046
16
  return PointerType::getUnqual(VectorType);
1047
16
}
1048
1049
Value *VectorBlockGenerator::generateStrideOneLoad(
1050
    ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
1051
4
    __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) {
1052
4
  unsigned VectorWidth = getVectorWidth();
1053
4
  auto *Pointer = Load->getPointerOperand();
1054
4
  Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth);
1055
4
  unsigned Offset = NegativeStride ? 
VectorWidth - 11
:
03
;
1056
4
1057
4
  Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset],
1058
4
                                               VLTS[Offset], NewAccesses);
1059
4
  Value *VectorPtr =
1060
4
      Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
1061
4
  LoadInst *VecLoad =
1062
4
      Builder.CreateLoad(VectorPtr, Load->getName() + "_p_vec_full");
1063
4
  if (!Aligned)
1064
4
    VecLoad->setAlignment(8);
1065
4
1066
4
  if (NegativeStride) {
1067
1
    SmallVector<Constant *, 16> Indices;
1068
5
    for (int i = VectorWidth - 1; i >= 0; 
i--4
)
1069
4
      Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i));
1070
1
    Constant *SV = llvm::ConstantVector::get(Indices);
1071
1
    Value *RevVecLoad = Builder.CreateShuffleVector(
1072
1
        VecLoad, VecLoad, SV, Load->getName() + "_reverse");
1073
1
    return RevVecLoad;
1074
1
  }
1075
3
1076
3
  return VecLoad;
1077
3
}
1078
1079
Value *VectorBlockGenerator::generateStrideZeroLoad(
1080
    ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap,
1081
2
    __isl_keep isl_id_to_ast_expr *NewAccesses) {
1082
2
  auto *Pointer = Load->getPointerOperand();
1083
2
  Type *VectorPtrType = getVectorPtrTy(Pointer, 1);
1084
2
  Value *NewPointer =
1085
2
      generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses);
1086
2
  Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType,
1087
2
                                           Load->getName() + "_p_vec_p");
1088
2
  LoadInst *ScalarLoad =
1089
2
      Builder.CreateLoad(VectorPtr, Load->getName() + "_p_splat_one");
1090
2
1091
2
  if (!Aligned)
1092
2
    ScalarLoad->setAlignment(8);
1093
2
1094
2
  Constant *SplatVector = Constant::getNullValue(
1095
2
      VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
1096
2
1097
2
  Value *VectorLoad = Builder.CreateShuffleVector(
1098
2
      ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
1099
2
  return VectorLoad;
1100
2
}
1101
1102
Value *VectorBlockGenerator::generateUnknownStrideLoad(
1103
    ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
1104
2
    __isl_keep isl_id_to_ast_expr *NewAccesses) {
1105
2
  int VectorWidth = getVectorWidth();
1106
2
  auto *Pointer = Load->getPointerOperand();
1107
2
  VectorType *VectorType = VectorType::get(
1108
2
      dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth);
1109
2
1110
2
  Value *Vector = UndefValue::get(VectorType);
1111
2
1112
18
  for (int i = 0; i < VectorWidth; 
i++16
) {
1113
16
    Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i],
1114
16
                                                 VLTS[i], NewAccesses);
1115
16
    Value *ScalarLoad =
1116
16
        Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_");
1117
16
    Vector = Builder.CreateInsertElement(
1118
16
        Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_");
1119
16
  }
1120
2
1121
2
  return Vector;
1122
2
}
1123
1124
void VectorBlockGenerator::generateLoad(
1125
    ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
1126
12
    VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1127
12
  if (Value *PreloadLoad = GlobalMap.lookup(Load)) {
1128
4
    VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad,
1129
4
                                                Load->getName() + "_p");
1130
4
    return;
1131
4
  }
1132
8
1133
8
  if (!VectorType::isValidElementType(Load->getType())) {
1134
0
    for (int i = 0; i < getVectorWidth(); i++)
1135
0
      ScalarMaps[i][Load] =
1136
0
          generateArrayLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses);
1137
0
    return;
1138
0
  }
1139
8
1140
8
  const MemoryAccess &Access = Stmt.getArrayAccessFor(Load);
1141
8
1142
8
  // Make sure we have scalar values available to access the pointer to
1143
8
  // the data location.
1144
8
  extractScalarValues(Load, VectorMap, ScalarMaps);
1145
8
1146
8
  Value *NewLoad;
1147
8
  if (Access.isStrideZero(isl::manage_copy(Schedule)))
1148
2
    NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses);
1149
6
  else if (Access.isStrideOne(isl::manage_copy(Schedule)))
1150
3
    NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses);
1151
3
  else if (Access.isStrideX(isl::manage_copy(Schedule), -1))
1152
1
    NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true);
1153
2
  else
1154
2
    NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses);
1155
8
1156
8
  VectorMap[Load] = NewLoad;
1157
8
}
1158
1159
void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
1160
                                         ValueMapT &VectorMap,
1161
1
                                         VectorValueMapT &ScalarMaps) {
1162
1
  int VectorWidth = getVectorWidth();
1163
1
  Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
1164
1
                                     ScalarMaps, getLoopForStmt(Stmt));
1165
1
1166
1
  assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction");
1167
1
1168
1
  const CastInst *Cast = dyn_cast<CastInst>(Inst);
1169
1
  VectorType *DestType = VectorType::get(Inst->getType(), VectorWidth);
1170
1
  VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType);
1171
1
}
1172
1173
void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
1174
                                          ValueMapT &VectorMap,
1175
4
                                          VectorValueMapT &ScalarMaps) {
1176
4
  Loop *L = getLoopForStmt(Stmt);
1177
4
  Value *OpZero = Inst->getOperand(0);
1178
4
  Value *OpOne = Inst->getOperand(1);
1179
4
1180
4
  Value *NewOpZero, *NewOpOne;
1181
4
  NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
1182
4
  NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);
1183
4
1184
4
  Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
1185
4
                                       Inst->getName() + "p_vec");
1186
4
  VectorMap[Inst] = NewInst;
1187
4
}
1188
1189
void VectorBlockGenerator::copyStore(
1190
    ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
1191
10
    VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1192
10
  const MemoryAccess &Access = Stmt.getArrayAccessFor(Store);
1193
10
1194
10
  auto *Pointer = Store->getPointerOperand();
1195
10
  Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
1196
10
                                 ScalarMaps, getLoopForStmt(Stmt));
1197
10
1198
10
  // Make sure we have scalar values available to access the pointer to
1199
10
  // the data location.
1200
10
  extractScalarValues(Store, VectorMap, ScalarMaps);
1201
10
1202
10
  if (Access.isStrideOne(isl::manage_copy(Schedule))) {
1203
9
    Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth());
1204
9
    Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0],
1205
9
                                                 VLTS[0], NewAccesses);
1206
9
1207
9
    Value *VectorPtr =
1208
9
        Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
1209
9
    StoreInst *Store = Builder.CreateStore(Vector, VectorPtr);
1210
9
1211
9
    if (!Aligned)
1212
9
      Store->setAlignment(8);
1213
9
  } else {
1214
5
    for (unsigned i = 0; i < ScalarMaps.size(); 
i++4
) {
1215
4
      Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i));
1216
4
      Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i],
1217
4
                                                   VLTS[i], NewAccesses);
1218
4
      Builder.CreateStore(Scalar, NewPointer);
1219
4
    }
1220
1
  }
1221
10
}
1222
1223
bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst,
1224
22
                                             ValueMapT &VectorMap) {
1225
22
  for (Value *Operand : Inst->operands())
1226
28
    if (VectorMap.count(Operand))
1227
16
      return true;
1228
22
  
return false6
;
1229
22
}
1230
1231
bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst,
1232
                                               ValueMapT &VectorMap,
1233
25
                                               VectorValueMapT &ScalarMaps) {
1234
25
  bool HasVectorOperand = false;
1235
25
  int VectorWidth = getVectorWidth();
1236
25
1237
42
  for (Value *Operand : Inst->operands()) {
1238
42
    ValueMapT::iterator VecOp = VectorMap.find(Operand);
1239
42
1240
42
    if (VecOp == VectorMap.end())
1241
31
      continue;
1242
11
1243
11
    HasVectorOperand = true;
1244
11
    Value *NewVector = VecOp->second;
1245
11
1246
67
    for (int i = 0; i < VectorWidth; 
++i56
) {
1247
57
      ValueMapT &SM = ScalarMaps[i];
1248
57
1249
57
      // If there is one scalar extracted, all scalar elements should have
1250
57
      // already been extracted by the code here. So no need to check for the
1251
57
      // existence of all of them.
1252
57
      if (SM.count(Operand))
1253
1
        break;
1254
56
1255
56
      SM[Operand] =
1256
56
          Builder.CreateExtractElement(NewVector, Builder.getInt32(i));
1257
56
    }
1258
11
  }
1259
25
1260
25
  return HasVectorOperand;
1261
25
}
1262
1263
void VectorBlockGenerator::copyInstScalarized(
1264
    ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
1265
7
    VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1266
7
  bool HasVectorOperand;
1267
7
  int VectorWidth = getVectorWidth();
1268
7
1269
7
  HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps);
1270
7
1271
35
  for (int VectorLane = 0; VectorLane < getVectorWidth(); 
VectorLane++28
)
1272
28
    BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane],
1273
28
                                    VLTS[VectorLane], NewAccesses);
1274
7
1275
7
  if (!VectorType::isValidElementType(Inst->getType()) || 
!HasVectorOperand6
)
1276
6
    return;
1277
1
1278
1
  // Make the result available as vector value.
1279
1
  VectorType *VectorType = VectorType::get(Inst->getType(), VectorWidth);
1280
1
  Value *Vector = UndefValue::get(VectorType);
1281
1
1282
5
  for (int i = 0; i < VectorWidth; 
i++4
)
1283
4
    Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst],
1284
4
                                         Builder.getInt32(i));
1285
1
1286
1
  VectorMap[Inst] = Vector;
1287
1
}
1288
1289
102
int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); }
1290
1291
void VectorBlockGenerator::copyInstruction(
1292
    ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
1293
76
    VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1294
76
  // Terminator instructions control the control flow. They are explicitly
1295
76
  // expressed in the clast and do not need to be copied.
1296
76
  if (Inst->isTerminator())
1297
11
    return;
1298
65
1299
65
  if (canSyntheziseInStmt(Stmt, Inst))
1300
31
    return;
1301
34
1302
34
  if (auto *Load = dyn_cast<LoadInst>(Inst)) {
1303
12
    generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
1304
12
    return;
1305
12
  }
1306
22
1307
22
  if (hasVectorOperands(Inst, VectorMap)) {
1308
16
    if (auto *Store = dyn_cast<StoreInst>(Inst)) {
1309
10
      // Identified as redundant by -polly-simplify.
1310
10
      if (!Stmt.getArrayAccessOrNULLFor(Store))
1311
0
        return;
1312
10
1313
10
      copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
1314
10
      return;
1315
10
    }
1316
6
1317
6
    if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) {
1318
1
      copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
1319
1
      return;
1320
1
    }
1321
5
1322
5
    if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) {
1323
4
      copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps);
1324
4
      return;
1325
4
    }
1326
7
1327
7
    // Fallthrough: We generate scalar instructions, if we don't know how to
1328
7
    // generate vector code.
1329
7
  }
1330
7
1331
7
  copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses);
1332
7
}
1333
1334
void VectorBlockGenerator::generateScalarVectorLoads(
1335
11
    ScopStmt &Stmt, ValueMapT &VectorBlockMap) {
1336
20
  for (MemoryAccess *MA : Stmt) {
1337
20
    if (MA->isArrayKind() || 
MA->isWrite()1
)
1338
19
      continue;
1339
1
1340
1
    auto *Address = getOrCreateAlloca(*MA);
1341
1
    Type *VectorPtrType = getVectorPtrTy(Address, 1);
1342
1
    Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType,
1343
1
                                             Address->getName() + "_p_vec_p");
1344
1
    auto *Val = Builder.CreateLoad(VectorPtr, Address->getName() + ".reload");
1345
1
    Constant *SplatVector = Constant::getNullValue(
1346
1
        VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
1347
1
1348
1
    Value *VectorVal = Builder.CreateShuffleVector(
1349
1
        Val, Val, SplatVector, Address->getName() + "_p_splat");
1350
1
    VectorBlockMap[MA->getAccessValue()] = VectorVal;
1351
1
  }
1352
11
}
1353
1354
11
void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) {
1355
20
  for (MemoryAccess *MA : Stmt) {
1356
20
    if (MA->isArrayKind() || 
MA->isRead()1
)
1357
20
      continue;
1358
0
1359
0
    llvm_unreachable("Scalar stores not expected in vector loop");
1360
0
  }
1361
11
}
1362
1363
void VectorBlockGenerator::copyStmt(
1364
11
    ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1365
11
  assert(Stmt.isBlockStmt() &&
1366
11
         "TODO: Only block statements can be copied by the vector block "
1367
11
         "generator");
1368
11
1369
11
  BasicBlock *BB = Stmt.getBasicBlock();
1370
11
  BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
1371
11
                                  &*Builder.GetInsertPoint(), &DT, &LI);
1372
11
  CopyBB->setName("polly.stmt." + BB->getName());
1373
11
  Builder.SetInsertPoint(&CopyBB->front());
1374
11
1375
11
  // Create two maps that store the mapping from the original instructions of
1376
11
  // the old basic block to their copies in the new basic block. Those maps
1377
11
  // are basic block local.
1378
11
  //
1379
11
  // As vector code generation is supported there is one map for scalar values
1380
11
  // and one for vector values.
1381
11
  //
1382
11
  // In case we just do scalar code generation, the vectorMap is not used and
1383
11
  // the scalarMap has just one dimension, which contains the mapping.
1384
11
  //
1385
11
  // In case vector code generation is done, an instruction may either appear
1386
11
  // in the vector map once (as it is calculating >vectorwidth< values at a
1387
11
  // time. Or (if the values are calculated using scalar operations), it
1388
11
  // appears once in every dimension of the scalarMap.
1389
11
  VectorValueMapT ScalarBlockMap(getVectorWidth());
1390
11
  ValueMapT VectorBlockMap;
1391
11
1392
11
  generateScalarVectorLoads(Stmt, VectorBlockMap);
1393
11
1394
11
  for (Instruction &Inst : *BB)
1395
76
    copyInstruction(Stmt, &Inst, VectorBlockMap, ScalarBlockMap, NewAccesses);
1396
11
1397
11
  verifyNoScalarStores(Stmt);
1398
11
}
1399
1400
BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
1401
11
                                             BasicBlock *BBCopy) {
1402
11
1403
11
  BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock();
1404
11
  BasicBlock *BBCopyIDom = EndBlockMap.lookup(BBIDom);
1405
11
1406
11
  if (BBCopyIDom)
1407
11
    DT.changeImmediateDominator(BBCopy, BBCopyIDom);
1408
11
1409
11
  return StartBlockMap.lookup(BBIDom);
1410
11
}
1411
1412
// This is to determine whether an llvm::Value (defined in @p BB) is usable when
1413
// leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
1414
// does not work in cases where the exit block has edges from outside the
1415
// region. In that case the llvm::Value would never be usable in in the exit
1416
// block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
1417
// for the subregion's exiting edges only. We need to determine whether an
1418
// llvm::Value is usable in there. We do this by checking whether it dominates
1419
// all exiting blocks individually.
1420
static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
1421
11
                                      BasicBlock *BB) {
1422
20
  for (auto ExitingBB : predecessors(R->getExit())) {
1423
20
    // Check for non-subregion incoming edges.
1424
20
    if (!R->contains(ExitingBB))
1425
3
      continue;
1426
17
1427
17
    if (!DT.dominates(BB, ExitingBB))
1428
5
      return false;
1429
17
  }
1430
11
1431
11
  
return true6
;
1432
11
}
1433
1434
// Find the direct dominator of the subregion's exit block if the subregion was
1435
// simplified.
1436
5
static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {
1437
5
  BasicBlock *Common = nullptr;
1438
9
  for (auto ExitingBB : predecessors(R->getExit())) {
1439
9
    // Check for non-subregion incoming edges.
1440
9
    if (!R->contains(ExitingBB))
1441
1
      continue;
1442
8
1443
8
    // First exiting edge.
1444
8
    if (!Common) {
1445
5
      Common = ExitingBB;
1446
5
      continue;
1447
5
    }
1448
3
1449
3
    Common = DT.findNearestCommonDominator(Common, ExitingBB);
1450
3
  }
1451
5
1452
5
  assert(Common && R->contains(Common));
1453
5
  return Common;
1454
5
}
1455
1456
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
1457
5
                               isl_id_to_ast_expr *IdToAstExp) {
1458
5
  assert(Stmt.isRegionStmt() &&
1459
5
         "Only region statements can be copied by the region generator");
1460
5
1461
5
  // Forget all old mappings.
1462
5
  StartBlockMap.clear();
1463
5
  EndBlockMap.clear();
1464
5
  RegionMaps.clear();
1465
5
  IncompletePHINodeMap.clear();
1466
5
1467
5
  // Collection of all values related to this subregion.
1468
5
  ValueMapT ValueMap;
1469
5
1470
5
  // The region represented by the statement.
1471
5
  Region *R = Stmt.getRegion();
1472
5
1473
5
  // Create a dedicated entry for the region where we can reload all demoted
1474
5
  // inputs.
1475
5
  BasicBlock *EntryBB = R->getEntry();
1476
5
  BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
1477
5
                                       &*Builder.GetInsertPoint(), &DT, &LI);
1478
5
  EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
1479
5
  Builder.SetInsertPoint(&EntryBBCopy->front());
1480
5
1481
5
  ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
1482
5
  generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);
1483
5
  generateBeginStmtTrace(Stmt, LTS, EntryBBMap);
1484
5
1485
11
  for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; 
++PI6
)
1486
6
    if (!R->contains(*PI)) {
1487
5
      StartBlockMap[*PI] = EntryBBCopy;
1488
5
      EndBlockMap[*PI] = EntryBBCopy;
1489
5
    }
1490
5
1491
5
  // Iterate over all blocks in the region in a breadth-first search.
1492
5
  std::deque<BasicBlock *> Blocks;
1493
5
  SmallSetVector<BasicBlock *, 8> SeenBlocks;
1494
5
  Blocks.push_back(EntryBB);
1495
5
  SeenBlocks.insert(EntryBB);
1496
5
1497
16
  while (!Blocks.empty()) {
1498
11
    BasicBlock *BB = Blocks.front();
1499
11
    Blocks.pop_front();
1500
11
1501
11
    // First split the block and update dominance information.
1502
11
    BasicBlock *BBCopy = splitBB(BB);
1503
11
    BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);
1504
11
1505
11
    // Get the mapping for this block and initialize it with either the scalar
1506
11
    // loads from the generated entering block (which dominates all blocks of
1507
11
    // this subregion) or the maps of the immediate dominator, if part of the
1508
11
    // subregion. The latter necessarily includes the former.
1509
11
    ValueMapT *InitBBMap;
1510
11
    if (BBCopyIDom) {
1511
11
      assert(RegionMaps.count(BBCopyIDom));
1512
11
      InitBBMap = &RegionMaps[BBCopyIDom];
1513
11
    } else
1514
0
      InitBBMap = &EntryBBMap;
1515
11
    auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));
1516
11
    ValueMapT &RegionMap = Inserted.first->second;
1517
11
1518
11
    // Copy the block with the BlockGenerator.
1519
11
    Builder.SetInsertPoint(&BBCopy->front());
1520
11
    copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);
1521
11
1522
11
    // In order to remap PHI nodes we store also basic block mappings.
1523
11
    StartBlockMap[BB] = BBCopy;
1524
11
    EndBlockMap[BB] = Builder.GetInsertBlock();
1525
11
1526
11
    // Add values to incomplete PHI nodes waiting for this block to be copied.
1527
11
    for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
1528
1
      addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
1529
11
    IncompletePHINodeMap[BB].clear();
1530
11
1531
11
    // And continue with new successors inside the region.
1532
27
    for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 
SI++16
)
1533
16
      if (R->contains(*SI) && 
SeenBlocks.insert(*SI)8
)
1534
6
        Blocks.push_back(*SI);
1535
11
1536
11
    // Remember value in case it is visible after this subregion.
1537
11
    if (isDominatingSubregionExit(DT, R, BB))
1538
6
      ValueMap.insert(RegionMap.begin(), RegionMap.end());
1539
11
  }
1540
5
1541
5
  // Now create a new dedicated region exit block and add it to the region map.
1542
5
  BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
1543
5
                                      &*Builder.GetInsertPoint(), &DT, &LI);
1544
5
  ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
1545
5
  StartBlockMap[R->getExit()] = ExitBBCopy;
1546
5
  EndBlockMap[R->getExit()] = ExitBBCopy;
1547
5
1548
5
  BasicBlock *ExitDomBBCopy = EndBlockMap.lookup(findExitDominator(DT, R));
1549
5
  assert(ExitDomBBCopy &&
1550
5
         "Common exit dominator must be within region; at least the entry node "
1551
5
         "must match");
1552
5
  DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
1553
5
1554
5
  // As the block generator doesn't handle control flow we need to add the
1555
5
  // region control flow by hand after all blocks have been copied.
1556
11
  for (BasicBlock *BB : SeenBlocks) {
1557
11
1558
11
    BasicBlock *BBCopyStart = StartBlockMap[BB];
1559
11
    BasicBlock *BBCopyEnd = EndBlockMap[BB];
1560
11
    Instruction *TI = BB->getTerminator();
1561
11
    if (isa<UnreachableInst>(TI)) {
1562
0
      while (!BBCopyEnd->empty())
1563
0
        BBCopyEnd->begin()->eraseFromParent();
1564
0
      new UnreachableInst(BBCopyEnd->getContext(), BBCopyEnd);
1565
0
      continue;
1566
0
    }
1567
11
1568
11
    Instruction *BICopy = BBCopyEnd->getTerminator();
1569
11
1570
11
    ValueMapT &RegionMap = RegionMaps[BBCopyStart];
1571
11
    RegionMap.insert(StartBlockMap.begin(), StartBlockMap.end());
1572
11
1573
11
    Builder.SetInsertPoint(BICopy);
1574
11
    copyInstScalar(Stmt, TI, RegionMap, LTS);
1575
11
    BICopy->eraseFromParent();
1576
11
  }
1577
5
1578
5
  // Add counting PHI nodes to all loops in the region that can be used as
1579
5
  // replacement for SCEVs referring to the old loop.
1580
11
  for (BasicBlock *BB : SeenBlocks) {
1581
11
    Loop *L = LI.getLoopFor(BB);
1582
11
    if (L == nullptr || 
L->getHeader() != BB9
||
!R->contains(L)1
)
1583
10
      continue;
1584
1
1585
1
    BasicBlock *BBCopy = StartBlockMap[BB];
1586
1
    Value *NullVal = Builder.getInt32(0);
1587
1
    PHINode *LoopPHI =
1588
1
        PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv");
1589
1
    Instruction *LoopPHIInc = BinaryOperator::CreateAdd(
1590
1
        LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc");
1591
1
    LoopPHI->insertBefore(&BBCopy->front());
1592
1
    LoopPHIInc->insertBefore(BBCopy->getTerminator());
1593
1
1594
2
    for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) {
1595
2
      if (!R->contains(PredBB))
1596
1
        continue;
1597
1
      if (L->contains(PredBB))
1598
1
        LoopPHI->addIncoming(LoopPHIInc, EndBlockMap[PredBB]);
1599
0
      else
1600
0
        LoopPHI->addIncoming(NullVal, EndBlockMap[PredBB]);
1601
1
    }
1602
1
1603
1
    for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy)))
1604
2
      if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
1605
1
        LoopPHI->addIncoming(NullVal, PredBBCopy);
1606
1
1607
1
    LTS[L] = SE.getUnknown(LoopPHI);
1608
1
  }
1609
5
1610
5
  // Continue generating code in the exit block.
1611
5
  Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
1612
5
1613
5
  // Write values visible to other statements.
1614
5
  generateScalarStores(Stmt, LTS, ValueMap, IdToAstExp);
1615
5
  StartBlockMap.clear();
1616
5
  EndBlockMap.clear();
1617
5
  RegionMaps.clear();
1618
5
  IncompletePHINodeMap.clear();
1619
5
}
1620
1621
PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
1622
3
                                       ValueMapT &BBMap, Loop *L) {
1623
3
  ScopStmt *Stmt = MA->getStatement();
1624
3
  Region *SubR = Stmt->getRegion();
1625
3
  auto Incoming = MA->getIncoming();
1626
3
1627
3
  PollyIRBuilder::InsertPointGuard IPGuard(Builder);
1628
3
  PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
1629
3
  BasicBlock *NewSubregionExit = Builder.GetInsertBlock();
1630
3
1631
3
  // This can happen if the subregion is simplified after the ScopStmts
1632
3
  // have been created; simplification happens as part of CodeGeneration.
1633
3
  if (OrigPHI->getParent() != SubR->getExit()) {
1634
0
    BasicBlock *FormerExit = SubR->getExitingBlock();
1635
0
    if (FormerExit)
1636
0
      NewSubregionExit = StartBlockMap.lookup(FormerExit);
1637
0
  }
1638
3
1639
3
  PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
1640
3
                                    "polly." + OrigPHI->getName(),
1641
3
                                    NewSubregionExit->getFirstNonPHI());
1642
3
1643
3
  // Add the incoming values to the PHI.
1644
6
  for (auto &Pair : Incoming) {
1645
6
    BasicBlock *OrigIncomingBlock = Pair.first;
1646
6
    BasicBlock *NewIncomingBlockStart = StartBlockMap.lookup(OrigIncomingBlock);
1647
6
    BasicBlock *NewIncomingBlockEnd = EndBlockMap.lookup(OrigIncomingBlock);
1648
6
    Builder.SetInsertPoint(NewIncomingBlockEnd->getTerminator());
1649
6
    assert(RegionMaps.count(NewIncomingBlockStart));
1650
6
    assert(RegionMaps.count(NewIncomingBlockEnd));
1651
6
    ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlockStart];
1652
6
1653
6
    Value *OrigIncomingValue = Pair.second;
1654
6
    Value *NewIncomingValue =
1655
6
        getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
1656
6
    NewPHI->addIncoming(NewIncomingValue, NewIncomingBlockEnd);
1657
6
  }
1658
3
1659
3
  return NewPHI;
1660
3
}
1661
1662
Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
1663
5
                                      ValueMapT &BBMap) {
1664
5
  ScopStmt *Stmt = MA->getStatement();
1665
5
1666
5
  // TODO: Add some test cases that ensure this is really the right choice.
1667
5
  Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());
1668
5
1669
5
  if (MA->isAnyPHIKind()) {
1670
3
    auto Incoming = MA->getIncoming();
1671
3
    assert(!Incoming.empty() &&
1672
3
           "PHI WRITEs must have originate from at least one incoming block");
1673
3
1674
3
    // If there is only one incoming value, we do not need to create a PHI.
1675
3
    if (Incoming.size() == 1) {
1676
0
      Value *OldVal = Incoming[0].second;
1677
0
      return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1678
0
    }
1679
3
1680
3
    return buildExitPHI(MA, LTS, BBMap, L);
1681
3
  }
1682
2
1683
2
  // MemoryKind::Value accesses leaving the subregion must dominate the exit
1684
2
  // block; just pass the copied value.
1685
2
  Value *OldVal = MA->getAccessValue();
1686
2
  return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1687
2
}
1688
1689
void RegionGenerator::generateScalarStores(
1690
    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
1691
5
    __isl_keep isl_id_to_ast_expr *NewAccesses) {
1692
5
  assert(Stmt.getRegion() &&
1693
5
         "Block statements need to use the generateScalarStores() "
1694
5
         "function in the BlockGenerator");
1695
5
1696
18
  for (MemoryAccess *MA : Stmt) {
1697
18
    if (MA->isOriginalArrayKind() || 
MA->isRead()8
)
1698
13
      continue;
1699
5
1700
5
    isl::set AccDom = MA->getAccessRelation().domain();
1701
5
    std::string Subject = MA->getId().get_name();
1702
5
    generateConditionalExecution(
1703
5
        Stmt, AccDom, Subject.c_str(), [&, this, MA]() {
1704
5
          Value *NewVal = getExitScalar(MA, LTS, BBMap);
1705
5
          Value *Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,
1706
5
                                              BBMap, NewAccesses);
1707
5
          assert((!isa<Instruction>(NewVal) ||
1708
5
                  DT.dominates(cast<Instruction>(NewVal)->getParent(),
1709
5
                               Builder.GetInsertBlock())) &&
1710
5
                 "Domination violation");
1711
5
          assert((!isa<Instruction>(Address) ||
1712
5
                  DT.dominates(cast<Instruction>(Address)->getParent(),
1713
5
                               Builder.GetInsertBlock())) &&
1714
5
                 "Domination violation");
1715
5
          Builder.CreateStore(NewVal, Address);
1716
5
        });
1717
5
  }
1718
5
}
1719
1720
void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,
1721
                                      PHINode *PHICopy, BasicBlock *IncomingBB,
1722
4
                                      LoopToScevMapT &LTS) {
1723
4
  // If the incoming block was not yet copied mark this PHI as incomplete.
1724
4
  // Once the block will be copied the incoming value will be added.
1725
4
  BasicBlock *BBCopyStart = StartBlockMap[IncomingBB];
1726
4
  BasicBlock *BBCopyEnd = EndBlockMap[IncomingBB];
1727
4
  if (!BBCopyStart) {
1728
1
    assert(!BBCopyEnd);
1729
1
    assert(Stmt.represents(IncomingBB) &&
1730
1
           "Bad incoming block for PHI in non-affine region");
1731
1
    IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));
1732
1
    return;
1733
1
  }
1734
3
1735
3
  assert(RegionMaps.count(BBCopyStart) &&
1736
3
         "Incoming PHI block did not have a BBMap");
1737
3
  ValueMapT &BBCopyMap = RegionMaps[BBCopyStart];
1738
3
1739
3
  Value *OpCopy = nullptr;
1740
3
1741
3
  if (Stmt.represents(IncomingBB)) {
1742
1
    Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
1743
1
1744
1
    // If the current insert block is different from the PHIs incoming block
1745
1
    // change it, otherwise do not.
1746
1
    auto IP = Builder.GetInsertPoint();
1747
1
    if (IP->getParent() != BBCopyEnd)
1748
0
      Builder.SetInsertPoint(BBCopyEnd->getTerminator());
1749
1
    OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
1750
1
    if (IP->getParent() != BBCopyEnd)
1751
0
      Builder.SetInsertPoint(&*IP);
1752
2
  } else {
1753
2
    // All edges from outside the non-affine region become a single edge
1754
2
    // in the new copy of the non-affine region. Make sure to only add the
1755
2
    // corresponding edge the first time we encounter a basic block from
1756
2
    // outside the non-affine region.
1757
2
    if (PHICopy->getBasicBlockIndex(BBCopyEnd) >= 0)
1758
0
      return;
1759
2
1760
2
    // Get the reloaded value.
1761
2
    OpCopy = getNewValue(Stmt, PHI, BBCopyMap, LTS, getLoopForStmt(Stmt));
1762
2
  }
1763
3
1764
3
  assert(OpCopy && "Incoming PHI value was not copied properly");
1765
3
  PHICopy->addIncoming(OpCopy, BBCopyEnd);
1766
3
}
1767
1768
void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
1769
                                         ValueMapT &BBMap,
1770
2
                                         LoopToScevMapT &LTS) {
1771
2
  unsigned NumIncoming = PHI->getNumIncomingValues();
1772
2
  PHINode *PHICopy =
1773
2
      Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName());
1774
2
  PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI());
1775
2
  BBMap[PHI] = PHICopy;
1776
2
1777
2
  for (BasicBlock *IncomingBB : PHI->blocks())
1778
3
    addOperandToPHI(Stmt, PHI, PHICopy, IncomingBB, LTS);
1779
2
}