Coverage Report

Created: 2017-04-29 12:21

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