Coverage Report

Created: 2019-02-15 18:59

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