Coverage Report

Created: 2017-10-03 07:32

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