Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/HexagonStoreWidening.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- HexagonStoreWidening.cpp------------------------------------------===//
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
// Replace sequences of "narrow" stores to adjacent memory locations with
10
// a fewer "wide" stores that have the same effect.
11
// For example, replace:
12
//   S4_storeirb_io  %vreg100, 0, 0   ; store-immediate-byte
13
//   S4_storeirb_io  %vreg100, 1, 0   ; store-immediate-byte
14
// with
15
//   S4_storeirh_io  %vreg100, 0, 0   ; store-immediate-halfword
16
// The above is the general idea.  The actual cases handled by the code
17
// may be a bit more complex.
18
// The purpose of this pass is to reduce the number of outstanding stores,
19
// or as one could say, "reduce store queue pressure".  Also, wide stores
20
// mean fewer stores, and since there are only two memory instructions allowed
21
// per packet, it also means fewer packets, and ultimately fewer cycles.
22
//===---------------------------------------------------------------------===//
23
24
#define DEBUG_TYPE "hexagon-widen-stores"
25
26
#include "HexagonInstrInfo.h"
27
#include "HexagonRegisterInfo.h"
28
#include "HexagonSubtarget.h"
29
#include "llvm/ADT/SmallPtrSet.h"
30
#include "llvm/ADT/StringRef.h"
31
#include "llvm/Analysis/AliasAnalysis.h"
32
#include "llvm/Analysis/MemoryLocation.h"
33
#include "llvm/CodeGen/MachineBasicBlock.h"
34
#include "llvm/CodeGen/MachineFunction.h"
35
#include "llvm/CodeGen/MachineFunctionPass.h"
36
#include "llvm/CodeGen/MachineInstr.h"
37
#include "llvm/CodeGen/MachineInstrBuilder.h"
38
#include "llvm/CodeGen/MachineMemOperand.h"
39
#include "llvm/CodeGen/MachineOperand.h"
40
#include "llvm/CodeGen/MachineRegisterInfo.h"
41
#include "llvm/IR/DebugLoc.h"
42
#include "llvm/MC/MCInstrDesc.h"
43
#include "llvm/Pass.h"
44
#include "llvm/Support/Debug.h"
45
#include "llvm/Support/ErrorHandling.h"
46
#include "llvm/Support/MathExtras.h"
47
#include "llvm/Support/raw_ostream.h"
48
#include <algorithm>
49
#include <cassert>
50
#include <cstdint>
51
#include <iterator>
52
#include <vector>
53
54
using namespace llvm;
55
56
namespace llvm {
57
58
  FunctionPass *createHexagonStoreWidening();
59
  void initializeHexagonStoreWideningPass(PassRegistry&);
60
61
} // end namespace llvm
62
63
namespace {
64
65
  struct HexagonStoreWidening : public MachineFunctionPass {
66
    const HexagonInstrInfo      *TII;
67
    const HexagonRegisterInfo   *TRI;
68
    const MachineRegisterInfo   *MRI;
69
    AliasAnalysis               *AA;
70
    MachineFunction             *MF;
71
72
  public:
73
    static char ID;
74
75
405
    HexagonStoreWidening() : MachineFunctionPass(ID) {
76
405
      initializeHexagonStoreWideningPass(*PassRegistry::getPassRegistry());
77
405
    }
78
79
    bool runOnMachineFunction(MachineFunction &MF) override;
80
81
401
    StringRef getPassName() const override { return "Hexagon Store Widening"; }
82
83
401
    void getAnalysisUsage(AnalysisUsage &AU) const override {
84
401
      AU.addRequired<AAResultsWrapperPass>();
85
401
      AU.addPreserved<AAResultsWrapperPass>();
86
401
      MachineFunctionPass::getAnalysisUsage(AU);
87
401
    }
88
89
    static bool handledStoreType(const MachineInstr *MI);
90
91
  private:
92
    static const int MaxWideSize = 4;
93
94
    typedef std::vector<MachineInstr*> InstrGroup;
95
    typedef std::vector<InstrGroup> InstrGroupList;
96
97
    bool instrAliased(InstrGroup &Stores, const MachineMemOperand &MMO);
98
    bool instrAliased(InstrGroup &Stores, const MachineInstr *MI);
99
    void createStoreGroup(MachineInstr *BaseStore, InstrGroup::iterator Begin,
100
        InstrGroup::iterator End, InstrGroup &Group);
101
    void createStoreGroups(MachineBasicBlock &MBB,
102
        InstrGroupList &StoreGroups);
103
    bool processBasicBlock(MachineBasicBlock &MBB);
104
    bool processStoreGroup(InstrGroup &Group);
105
    bool selectStores(InstrGroup::iterator Begin, InstrGroup::iterator End,
106
        InstrGroup &OG, unsigned &TotalSize, unsigned MaxSize);
107
    bool createWideStores(InstrGroup &OG, InstrGroup &NG, unsigned TotalSize);
108
    bool replaceStores(InstrGroup &OG, InstrGroup &NG);
109
    bool storesAreAdjacent(const MachineInstr *S1, const MachineInstr *S2);
110
  };
111
112
char HexagonStoreWidening::ID = 0;
113
114
} // end anonymous namespace
115
116
// Some local helper functions...
117
66
static unsigned getBaseAddressRegister(const MachineInstr *MI) {
118
66
  const MachineOperand &MO = MI->getOperand(0);
119
66
  assert(MO.isReg() && "Expecting register operand");
120
66
  return MO.getReg();
121
66
}
122
123
246
static int64_t getStoreOffset(const MachineInstr *MI) {
124
246
  unsigned OpC = MI->getOpcode();
125
246
  assert(HexagonStoreWidening::handledStoreType(MI) && "Unhandled opcode");
126
246
127
246
  switch (OpC) {
128
246
    case Hexagon::S4_storeirb_io:
129
246
    case Hexagon::S4_storeirh_io:
130
246
    case Hexagon::S4_storeiri_io: {
131
246
      const MachineOperand &MO = MI->getOperand(1);
132
246
      assert(MO.isImm() && "Expecting immediate offset");
133
246
      return MO.getImm();
134
0
    }
135
0
  }
136
0
  dbgs() << *MI;
137
0
  llvm_unreachable("Store offset calculation missing for a handled opcode");
138
0
  return 0;
139
246
}
140
141
347
static const MachineMemOperand &getStoreTarget(const MachineInstr *MI) {
142
347
  assert(!MI->memoperands_empty() && "Expecting memory operands");
143
347
  return **MI->memoperands_begin();
144
347
}
145
146
405
INITIALIZE_PASS_BEGIN405
(HexagonStoreWidening, "hexagon-widen-stores",
147
405
                "Hexason Store Widening", false, false)
148
405
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
149
405
INITIALIZE_PASS_END(HexagonStoreWidening, "hexagon-widen-stores",
150
                "Hexagon Store Widening", false, false)
151
152
// Filtering function: any stores whose opcodes are not "approved" of by
153
// this function will not be subjected to widening.
154
13.4k
inline bool HexagonStoreWidening::handledStoreType(const MachineInstr *MI) {
155
13.4k
  // For now, only handle stores of immediate values.
156
13.4k
  // Also, reject stores to stack slots.
157
13.4k
  unsigned Opc = MI->getOpcode();
158
13.4k
  switch (Opc) {
159
104
    case Hexagon::S4_storeirb_io:
160
104
    case Hexagon::S4_storeirh_io:
161
104
    case Hexagon::S4_storeiri_io:
162
104
      // Base address must be a register. (Implement FI later.)
163
104
      return MI->getOperand(0).isReg();
164
13.3k
    default:
165
13.3k
      return false;
166
0
  }
167
0
}
168
169
// Check if the machine memory operand MMO is aliased with any of the
170
// stores in the store group Stores.
171
bool HexagonStoreWidening::instrAliased(InstrGroup &Stores,
172
83
      const MachineMemOperand &MMO) {
173
83
  if (!MMO.getValue())
174
1
    return true;
175
82
176
82
  MemoryLocation L(MMO.getValue(), MMO.getSize(), MMO.getAAInfo());
177
82
178
247
  for (auto SI : Stores) {
179
247
    const MachineMemOperand &SMO = getStoreTarget(SI);
180
247
    if (!SMO.getValue())
181
0
      return true;
182
247
183
247
    MemoryLocation SL(SMO.getValue(), SMO.getSize(), SMO.getAAInfo());
184
247
    if (AA->alias(L, SL))
185
12
      return true;
186
70
  }
187
70
188
70
  return false;
189
70
}
190
191
// Check if the machine instruction MI accesses any storage aliased with
192
// any store in the group Stores.
193
bool HexagonStoreWidening::instrAliased(InstrGroup &Stores,
194
13
      const MachineInstr *MI) {
195
13
  for (auto &I : MI->memoperands())
196
13
    
if (13
instrAliased(Stores, *I)13
)
197
4
      return true;
198
9
  return false;
199
9
}
200
201
// Inspect a machine basic block, and generate store groups out of stores
202
// encountered in the block.
203
//
204
// A store group is a group of stores that use the same base register,
205
// and which can be reordered within that group without altering the
206
// semantics of the program.  A single store group could be widened as
207
// a whole, if there existed a single store instruction with the same
208
// semantics as the entire group.  In many cases, a single store group
209
// may need more than one wide store.
210
void HexagonStoreWidening::createStoreGroups(MachineBasicBlock &MBB,
211
1.79k
      InstrGroupList &StoreGroups) {
212
1.79k
  InstrGroup AllInsns;
213
1.79k
214
1.79k
  // Copy all instruction pointers from the basic block to a temporary
215
1.79k
  // list.  This will allow operating on the list, and modifying its
216
1.79k
  // elements without affecting the basic block.
217
1.79k
  for (auto &I : MBB)
218
13.4k
    AllInsns.push_back(&I);
219
1.79k
220
1.79k
  // Traverse all instructions in the AllInsns list, and if we encounter
221
1.79k
  // a store, then try to create a store group starting at that instruction
222
1.79k
  // i.e. a sequence of independent stores that can be widened.
223
15.2k
  for (auto I = AllInsns.begin(), E = AllInsns.end(); 
I != E15.2k
;
++I13.4k
) {
224
13.4k
    MachineInstr *MI = *I;
225
13.4k
    // Skip null pointers (processed instructions).
226
13.4k
    if (
!MI || 13.4k
!handledStoreType(MI)13.3k
)
227
13.3k
      continue;
228
36
229
36
    // Found a store.  Try to create a store group.
230
36
    InstrGroup G;
231
36
    createStoreGroup(MI, I+1, E, G);
232
36
    if (G.size() > 1)
233
3
      StoreGroups.push_back(G);
234
13.4k
  }
235
1.79k
}
236
237
// Create a single store group.  The stores need to be independent between
238
// themselves, and also there cannot be other instructions between them
239
// that could read or modify storage being stored into.
240
void HexagonStoreWidening::createStoreGroup(MachineInstr *BaseStore,
241
36
      InstrGroup::iterator Begin, InstrGroup::iterator End, InstrGroup &Group) {
242
36
  assert(handledStoreType(BaseStore) && "Unexpected instruction");
243
36
  unsigned BaseReg = getBaseAddressRegister(BaseStore);
244
36
  InstrGroup Other;
245
36
246
36
  Group.push_back(BaseStore);
247
36
248
117
  for (auto I = Begin; 
I != End117
;
++I81
) {
249
98
    MachineInstr *MI = *I;
250
98
    if (!MI)
251
0
      continue;
252
98
253
98
    
if (98
handledStoreType(MI)98
) {
254
39
      // If this store instruction is aliased with anything already in the
255
39
      // group, terminate the group now.
256
39
      if (instrAliased(Group, getStoreTarget(MI)))
257
8
        return;
258
31
      // If this store is aliased to any of the memory instructions we have
259
31
      // seen so far (that are not a part of this group), terminate the group.
260
31
      
if (31
instrAliased(Other, getStoreTarget(MI))31
)
261
1
        return;
262
30
263
30
      unsigned BR = getBaseAddressRegister(MI);
264
30
      if (
BR == BaseReg30
) {
265
30
        Group.push_back(MI);
266
30
        *I = nullptr;
267
30
        continue;
268
30
      }
269
59
    }
270
59
271
59
    // Assume calls are aliased to everything.
272
59
    
if (59
MI->isCall() || 59
MI->hasUnmodeledSideEffects()55
)
273
4
      return;
274
55
275
55
    
if (55
MI->mayLoad() || 55
MI->mayStore()50
) {
276
13
      if (
MI->hasOrderedMemoryRef() || 13
instrAliased(Group, MI)13
)
277
4
        return;
278
9
      Other.push_back(MI);
279
9
    }
280
98
  } // for
281
36
}
282
283
// Check if store instructions S1 and S2 are adjacent.  More precisely,
284
// S2 has to access memory immediately following that accessed by S1.
285
bool HexagonStoreWidening::storesAreAdjacent(const MachineInstr *S1,
286
0
      const MachineInstr *S2) {
287
0
  if (
!handledStoreType(S1) || 0
!handledStoreType(S2)0
)
288
0
    return false;
289
0
290
0
  const MachineMemOperand &S1MO = getStoreTarget(S1);
291
0
292
0
  // Currently only handling immediate stores.
293
0
  int Off1 = S1->getOperand(1).getImm();
294
0
  int Off2 = S2->getOperand(1).getImm();
295
0
296
0
  return (Off1 >= 0) ? Off1+S1MO.getSize() == unsigned(Off2)
297
0
                     : int(Off1+S1MO.getSize()) == Off2;
298
0
}
299
300
/// Given a sequence of adjacent stores, and a maximum size of a single wide
301
/// store, pick a group of stores that  can be replaced by a single store
302
/// of size not exceeding MaxSize.  The selected sequence will be recorded
303
/// in OG ("old group" of instructions).
304
/// OG should be empty on entry, and should be left empty if the function
305
/// fails.
306
bool HexagonStoreWidening::selectStores(InstrGroup::iterator Begin,
307
      InstrGroup::iterator End, InstrGroup &OG, unsigned &TotalSize,
308
33
      unsigned MaxSize) {
309
33
  assert(Begin != End && "No instructions to analyze");
310
33
  assert(OG.empty() && "Old group not empty on entry");
311
33
312
33
  if (std::distance(Begin, End) <= 1)
313
3
    return false;
314
30
315
30
  MachineInstr *FirstMI = *Begin;
316
30
  assert(!FirstMI->memoperands_empty() && "Expecting some memory operands");
317
30
  const MachineMemOperand &FirstMMO = getStoreTarget(FirstMI);
318
30
  unsigned Alignment = FirstMMO.getAlignment();
319
30
  unsigned SizeAccum = FirstMMO.getSize();
320
30
  unsigned FirstOffset = getStoreOffset(FirstMI);
321
30
322
30
  // The initial value of SizeAccum should always be a power of 2.
323
30
  assert(isPowerOf2_32(SizeAccum) && "First store size not a power of 2");
324
30
325
30
  // If the size of the first store equals to or exceeds the limit, do nothing.
326
30
  if (SizeAccum >= MaxSize)
327
30
    return false;
328
0
329
0
  // If the size of the first store is greater than or equal to the address
330
0
  // stored to, then the store cannot be made any wider.
331
0
  
if (0
SizeAccum >= Alignment0
)
332
0
    return false;
333
0
334
0
  // The offset of a store will put restrictions on how wide the store can be.
335
0
  // Offsets in stores of size 2^n bytes need to have the n lowest bits be 0.
336
0
  // If the first store already exhausts the offset limits, quit.  Test this
337
0
  // by checking if the next wider size would exceed the limit.
338
0
  
if (0
(2*SizeAccum-1) & FirstOffset0
)
339
0
    return false;
340
0
341
0
  OG.push_back(FirstMI);
342
0
  MachineInstr *S1 = FirstMI, *S2 = *(Begin+1);
343
0
  InstrGroup::iterator I = Begin+1;
344
0
345
0
  // Pow2Num will be the largest number of elements in OG such that the sum
346
0
  // of sizes of stores 0...Pow2Num-1 will be a power of 2.
347
0
  unsigned Pow2Num = 1;
348
0
  unsigned Pow2Size = SizeAccum;
349
0
350
0
  // Be greedy: keep accumulating stores as long as they are to adjacent
351
0
  // memory locations, and as long as the total number of bytes stored
352
0
  // does not exceed the limit (MaxSize).
353
0
  // Keep track of when the total size covered is a power of 2, since
354
0
  // this is a size a single store can cover.
355
0
  while (
I != End0
) {
356
0
    S2 = *I;
357
0
    // Stores are sorted, so if S1 and S2 are not adjacent, there won't be
358
0
    // any other store to fill the "hole".
359
0
    if (!storesAreAdjacent(S1, S2))
360
0
      break;
361
0
362
0
    unsigned S2Size = getStoreTarget(S2).getSize();
363
0
    if (SizeAccum + S2Size > std::min(MaxSize, Alignment))
364
0
      break;
365
0
366
0
    OG.push_back(S2);
367
0
    SizeAccum += S2Size;
368
0
    if (
isPowerOf2_32(SizeAccum)0
) {
369
0
      Pow2Num = OG.size();
370
0
      Pow2Size = SizeAccum;
371
0
    }
372
0
    if ((2*Pow2Size-1) & FirstOffset)
373
0
      break;
374
0
375
0
    S1 = S2;
376
0
    ++I;
377
0
  }
378
0
379
0
  // The stores don't add up to anything that can be widened.  Clean up.
380
0
  if (
Pow2Num <= 10
) {
381
0
    OG.clear();
382
0
    return false;
383
0
  }
384
0
385
0
  // Only leave the stored being widened.
386
0
  OG.resize(Pow2Num);
387
0
  TotalSize = Pow2Size;
388
0
  return true;
389
0
}
390
391
/// Given an "old group" OG of stores, create a "new group" NG of instructions
392
/// to replace them.  Ideally, NG would only have a single instruction in it,
393
/// but that may only be possible for store-immediate.
394
bool HexagonStoreWidening::createWideStores(InstrGroup &OG, InstrGroup &NG,
395
0
      unsigned TotalSize) {
396
0
  // XXX Current limitations:
397
0
  // - only expect stores of immediate values in OG,
398
0
  // - only handle a TotalSize of up to 4.
399
0
400
0
  if (TotalSize > 4)
401
0
    return false;
402
0
403
0
  unsigned Acc = 0;  // Value accumulator.
404
0
  unsigned Shift = 0;
405
0
406
0
  for (InstrGroup::iterator I = OG.begin(), E = OG.end(); 
I != E0
;
++I0
) {
407
0
    MachineInstr *MI = *I;
408
0
    const MachineMemOperand &MMO = getStoreTarget(MI);
409
0
    MachineOperand &SO = MI->getOperand(2);  // Source.
410
0
    assert(SO.isImm() && "Expecting an immediate operand");
411
0
412
0
    unsigned NBits = MMO.getSize()*8;
413
0
    unsigned Mask = (0xFFFFFFFFU >> (32-NBits));
414
0
    unsigned Val = (SO.getImm() & Mask) << Shift;
415
0
    Acc |= Val;
416
0
    Shift += NBits;
417
0
  }
418
0
419
0
  MachineInstr *FirstSt = OG.front();
420
0
  DebugLoc DL = OG.back()->getDebugLoc();
421
0
  const MachineMemOperand &OldM = getStoreTarget(FirstSt);
422
0
  MachineMemOperand *NewM =
423
0
    MF->getMachineMemOperand(OldM.getPointerInfo(), OldM.getFlags(),
424
0
                             TotalSize, OldM.getAlignment(),
425
0
                             OldM.getAAInfo());
426
0
427
0
  if (
Acc < 0x100000
) {
428
0
    // Create mem[hw] = #Acc
429
0
    unsigned WOpc = (TotalSize == 2) ? Hexagon::S4_storeirh_io :
430
0
                    
(TotalSize == 4) ? 0
Hexagon::S4_storeiri_io0
:
00
;
431
0
    assert(WOpc && "Unexpected size");
432
0
433
0
    int Val = (TotalSize == 2) ? 
int16_t(Acc)0
:
int(Acc)0
;
434
0
    const MCInstrDesc &StD = TII->get(WOpc);
435
0
    MachineOperand &MR = FirstSt->getOperand(0);
436
0
    int64_t Off = FirstSt->getOperand(1).getImm();
437
0
    MachineInstr *StI = BuildMI(*MF, DL, StD)
438
0
                          .addReg(MR.getReg(), getKillRegState(MR.isKill()))
439
0
                          .addImm(Off)
440
0
                          .addImm(Val);
441
0
    StI->addMemOperand(*MF, NewM);
442
0
    NG.push_back(StI);
443
0
  } else {
444
0
    // Create vreg = A2_tfrsi #Acc; mem[hw] = vreg
445
0
    const MCInstrDesc &TfrD = TII->get(Hexagon::A2_tfrsi);
446
0
    const TargetRegisterClass *RC = TII->getRegClass(TfrD, 0, TRI, *MF);
447
0
    unsigned VReg = MF->getRegInfo().createVirtualRegister(RC);
448
0
    MachineInstr *TfrI = BuildMI(*MF, DL, TfrD, VReg)
449
0
                           .addImm(int(Acc));
450
0
    NG.push_back(TfrI);
451
0
452
0
    unsigned WOpc = (TotalSize == 2) ? Hexagon::S2_storerh_io :
453
0
                    
(TotalSize == 4) ? 0
Hexagon::S2_storeri_io0
:
00
;
454
0
    assert(WOpc && "Unexpected size");
455
0
456
0
    const MCInstrDesc &StD = TII->get(WOpc);
457
0
    MachineOperand &MR = FirstSt->getOperand(0);
458
0
    int64_t Off = FirstSt->getOperand(1).getImm();
459
0
    MachineInstr *StI = BuildMI(*MF, DL, StD)
460
0
                          .addReg(MR.getReg(), getKillRegState(MR.isKill()))
461
0
                          .addImm(Off)
462
0
                          .addReg(VReg, RegState::Kill);
463
0
    StI->addMemOperand(*MF, NewM);
464
0
    NG.push_back(StI);
465
0
  }
466
0
467
0
  return true;
468
0
}
469
470
// Replace instructions from the old group OG with instructions from the
471
// new group NG.  Conceptually, remove all instructions in OG, and then
472
// insert all instructions in NG, starting at where the first instruction
473
// from OG was (in the order in which they appeared in the basic block).
474
// (The ordering in OG does not have to match the order in the basic block.)
475
0
bool HexagonStoreWidening::replaceStores(InstrGroup &OG, InstrGroup &NG) {
476
0
  DEBUG({
477
0
    dbgs() << "Replacing:\n";
478
0
    for (auto I : OG)
479
0
      dbgs() << "  " << *I;
480
0
    dbgs() << "with\n";
481
0
    for (auto I : NG)
482
0
      dbgs() << "  " << *I;
483
0
  });
484
0
485
0
  MachineBasicBlock *MBB = OG.back()->getParent();
486
0
  MachineBasicBlock::iterator InsertAt = MBB->end();
487
0
488
0
  // Need to establish the insertion point.  The best one is right before
489
0
  // the first store in the OG, but in the order in which the stores occur
490
0
  // in the program list.  Since the ordering in OG does not correspond
491
0
  // to the order in the program list, we need to do some work to find
492
0
  // the insertion point.
493
0
494
0
  // Create a set of all instructions in OG (for quick lookup).
495
0
  SmallPtrSet<MachineInstr*, 4> InstrSet;
496
0
  for (auto I : OG)
497
0
    InstrSet.insert(I);
498
0
499
0
  // Traverse the block, until we hit an instruction from OG.
500
0
  for (auto &I : *MBB) {
501
0
    if (
InstrSet.count(&I)0
) {
502
0
      InsertAt = I;
503
0
      break;
504
0
    }
505
0
  }
506
0
507
0
  assert((InsertAt != MBB->end()) && "Cannot locate any store from the group");
508
0
509
0
  bool AtBBStart = false;
510
0
511
0
  // InsertAt points at the first instruction that will be removed.  We need
512
0
  // to move it out of the way, so it remains valid after removing all the
513
0
  // old stores, and so we are able to recover it back to the proper insertion
514
0
  // position.
515
0
  if (InsertAt != MBB->begin())
516
0
    --InsertAt;
517
0
  else
518
0
    AtBBStart = true;
519
0
520
0
  for (auto I : OG)
521
0
    I->eraseFromParent();
522
0
523
0
  if (!AtBBStart)
524
0
    ++InsertAt;
525
0
  else
526
0
    InsertAt = MBB->begin();
527
0
528
0
  for (auto I : NG)
529
0
    MBB->insert(InsertAt, I);
530
0
531
0
  return true;
532
0
}
533
534
// Break up the group into smaller groups, each of which can be replaced by
535
// a single wide store.  Widen each such smaller group and replace the old
536
// instructions with the widened ones.
537
3
bool HexagonStoreWidening::processStoreGroup(InstrGroup &Group) {
538
3
  bool Changed = false;
539
3
  InstrGroup::iterator I = Group.begin(), E = Group.end();
540
3
  InstrGroup OG, NG;   // Old and new groups.
541
3
  unsigned CollectedSize;
542
3
543
36
  while (
I != E36
) {
544
33
    OG.clear();
545
33
    NG.clear();
546
33
547
33
    bool Succ = selectStores(I++, E, OG, CollectedSize, MaxWideSize) &&
548
0
                createWideStores(OG, NG, CollectedSize)              &&
549
0
                replaceStores(OG, NG);
550
33
    if (!Succ)
551
33
      continue;
552
0
553
33
    assert(OG.size() > 1 && "Created invalid group");
554
0
    assert(distance(I, E)+1 >= int(OG.size()) && "Too many elements");
555
0
    I += OG.size()-1;
556
0
557
0
    Changed = true;
558
0
  }
559
3
560
3
  return Changed;
561
3
}
562
563
// Process a single basic block: create the store groups, and replace them
564
// with the widened stores, if possible.  Processing of each basic block
565
// is independent from processing of any other basic block.  This transfor-
566
// mation could be stopped after having processed any basic block without
567
// any ill effects (other than not having performed widening in the unpro-
568
// cessed blocks).  Also, the basic blocks can be processed in any order.
569
1.79k
bool HexagonStoreWidening::processBasicBlock(MachineBasicBlock &MBB) {
570
1.79k
  InstrGroupList SGs;
571
1.79k
  bool Changed = false;
572
1.79k
573
1.79k
  createStoreGroups(MBB, SGs);
574
1.79k
575
108
  auto Less = [] (const MachineInstr *A, const MachineInstr *B) -> bool {
576
108
    return getStoreOffset(A) < getStoreOffset(B);
577
108
  };
578
3
  for (auto &G : SGs) {
579
3
    assert(G.size() > 1 && "Store group with fewer than 2 elements");
580
3
    std::sort(G.begin(), G.end(), Less);
581
3
582
3
    Changed |= processStoreGroup(G);
583
3
  }
584
1.79k
585
1.79k
  return Changed;
586
1.79k
}
587
588
860
bool HexagonStoreWidening::runOnMachineFunction(MachineFunction &MFn) {
589
860
  if (skipFunction(*MFn.getFunction()))
590
0
    return false;
591
860
592
860
  MF = &MFn;
593
860
  auto &ST = MFn.getSubtarget<HexagonSubtarget>();
594
860
  TII = ST.getInstrInfo();
595
860
  TRI = ST.getRegisterInfo();
596
860
  MRI = &MFn.getRegInfo();
597
860
  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
598
860
599
860
  bool Changed = false;
600
860
601
860
  for (auto &B : MFn)
602
1.79k
    Changed |= processBasicBlock(B);
603
860
604
860
  return Changed;
605
860
}
606
607
405
FunctionPass *llvm::createHexagonStoreWidening() {
608
405
  return new HexagonStoreWidening();
609
405
}