Coverage Report

Created: 2017-08-21 19:50

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