Coverage Report

Created: 2019-07-24 05:18

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