Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
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
/// \file
9
/// Finalize v8.1-m low-overhead loops by converting the associated pseudo
10
/// instructions into machine operations.
11
/// The expectation is that the loop contains three pseudo instructions:
12
/// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop
13
///   form should be in the preheader, whereas the while form should be in the
14
///   preheaders only predecessor. TODO: Could DoLoopStart get moved into the
15
///   pre-preheader?
16
/// - t2LoopDec - placed within in the loop body.
17
/// - t2LoopEnd - the loop latch terminator.
18
///
19
//===----------------------------------------------------------------------===//
20
21
#include "ARM.h"
22
#include "ARMBaseInstrInfo.h"
23
#include "ARMBaseRegisterInfo.h"
24
#include "ARMBasicBlockInfo.h"
25
#include "ARMSubtarget.h"
26
#include "llvm/CodeGen/MachineFunctionPass.h"
27
#include "llvm/CodeGen/MachineLoopInfo.h"
28
#include "llvm/CodeGen/MachineRegisterInfo.h"
29
30
using namespace llvm;
31
32
#define DEBUG_TYPE "arm-low-overhead-loops"
33
31.7k
#define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
34
35
namespace {
36
37
  class ARMLowOverheadLoops : public MachineFunctionPass {
38
    const ARMBaseInstrInfo    *TII = nullptr;
39
    MachineRegisterInfo       *MRI = nullptr;
40
    std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
41
42
  public:
43
    static char ID;
44
45
5.20k
    ARMLowOverheadLoops() : MachineFunctionPass(ID) { }
46
47
5.17k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
48
5.17k
      AU.setPreservesCFG();
49
5.17k
      AU.addRequired<MachineLoopInfo>();
50
5.17k
      MachineFunctionPass::getAnalysisUsage(AU);
51
5.17k
    }
52
53
    bool runOnMachineFunction(MachineFunction &MF) override;
54
55
    bool ProcessLoop(MachineLoop *ML);
56
57
    bool RevertNonLoops(MachineFunction &MF);
58
59
    void RevertWhile(MachineInstr *MI) const;
60
61
    void RevertLoopDec(MachineInstr *MI) const;
62
63
    void RevertLoopEnd(MachineInstr *MI) const;
64
65
    void Expand(MachineLoop *ML, MachineInstr *Start,
66
                MachineInstr *Dec, MachineInstr *End, bool Revert);
67
68
5.18k
    MachineFunctionProperties getRequiredProperties() const override {
69
5.18k
      return MachineFunctionProperties().set(
70
5.18k
          MachineFunctionProperties::Property::NoVRegs);
71
5.18k
    }
72
73
31.7k
    StringRef getPassName() const override {
74
31.7k
      return ARM_LOW_OVERHEAD_LOOPS_NAME;
75
31.7k
    }
76
  };
77
}
78
  
79
char ARMLowOverheadLoops::ID = 0;
80
81
INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
82
                false, false)
83
84
26.5k
bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &MF) {
85
26.5k
  if (!static_cast<const ARMSubtarget&>(MF.getSubtarget()).hasLOB())
86
25.4k
    return false;
87
1.09k
88
1.09k
  LLVM_DEBUG(dbgs() << "ARM Loops on " << MF.getName() << " ------------- \n");
89
1.09k
90
1.09k
  auto &MLI = getAnalysis<MachineLoopInfo>();
91
1.09k
  MRI = &MF.getRegInfo();
92
1.09k
  TII = static_cast<const ARMBaseInstrInfo*>(
93
1.09k
    MF.getSubtarget().getInstrInfo());
94
1.09k
  BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
95
1.09k
  BBUtils->computeAllBlockSizes();
96
1.09k
  BBUtils->adjustBBOffsetsAfter(&MF.front());
97
1.09k
98
1.09k
  bool Changed = false;
99
1.09k
  for (auto ML : MLI) {
100
68
    if (!ML->getParentLoop())
101
68
      Changed |= ProcessLoop(ML);
102
68
  }
103
1.09k
  Changed |= RevertNonLoops(MF);
104
1.09k
  return Changed;
105
1.09k
}
106
107
14.9k
static bool IsLoopStart(MachineInstr &MI) {
108
14.9k
  return MI.getOpcode() == ARM::t2DoLoopStart ||
109
14.9k
         
MI.getOpcode() == ARM::t2WhileLoopStart14.9k
;
110
14.9k
}
111
112
77
bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
113
77
114
77
  bool Changed = false;
115
77
116
77
  // Process inner loops first.
117
86
  for (auto I = ML->begin(), E = ML->end(); I != E; 
++I9
)
118
9
    Changed |= ProcessLoop(*I);
119
77
120
77
  LLVM_DEBUG(dbgs() << "ARM Loops: Processing " << *ML);
121
77
122
77
  // Search the given block for a loop start instruction. If one isn't found,
123
77
  // and there's only one predecessor block, search that one too.
124
77
  std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
125
112
    [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
126
739
    for (auto &MI : *MBB) {
127
739
      if (IsLoopStart(MI))
128
57
        return &MI;
129
739
    }
130
112
    
if (55
MBB->pred_size() == 155
)
131
35
      return SearchForStart(*MBB->pred_begin());
132
20
    return nullptr;
133
20
  };
134
77
135
77
  MachineInstr *Start = nullptr;
136
77
  MachineInstr *Dec = nullptr;
137
77
  MachineInstr *End = nullptr;
138
77
  bool Revert = false;
139
77
140
77
  // Search the preheader for the start intrinsic, or look through the
141
77
  // predecessors of the header to find exactly one set.iterations intrinsic.
142
77
  // FIXME: I don't see why we shouldn't be supporting multiple predecessors
143
77
  // with potentially multiple set.loop.iterations, so we need to enable this.
144
77
  if (auto *Preheader = ML->getLoopPreheader()) {
145
69
    Start = SearchForStart(Preheader);
146
69
  } else {
147
8
    LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find loop preheader!\n"
148
8
               << " - Performing manual predecessor search.\n");
149
8
    MachineBasicBlock *Pred = nullptr;
150
16
    for (auto *MBB : ML->getHeader()->predecessors()) {
151
16
      if (!ML->contains(MBB)) {
152
9
        if (Pred) {
153
1
          LLVM_DEBUG(dbgs() << " - Found multiple out-of-loop preds.\n");
154
1
          Start = nullptr;
155
1
          break;
156
1
        }
157
8
        Pred = MBB;
158
8
        Start = SearchForStart(MBB);
159
8
      }
160
16
    }
161
8
  }
162
77
163
77
  // Find the low-overhead loop components and decide whether or not to fall
164
77
  // back to a normal loop.
165
149
  for (auto *MBB : reverse(ML->getBlocks())) {
166
986
    for (auto &MI : *MBB) {
167
986
      if (MI.getOpcode() == ARM::t2LoopDec)
168
58
        Dec = &MI;
169
928
      else if (MI.getOpcode() == ARM::t2LoopEnd)
170
58
        End = &MI;
171
870
      else if (IsLoopStart(MI))
172
0
        Start = &MI;
173
870
      else if (MI.getDesc().isCall())
174
2
        // TODO: Though the call will require LE to execute again, does this
175
2
        // mean we should revert? Always executing LE hopefully should be
176
2
        // faster than performing a sub,cmp,br or even subs,br.
177
2
        Revert = true;
178
986
179
986
      if (!Dec)
180
621
        continue;
181
365
182
365
      // If we find that we load/store LR between LoopDec and LoopEnd, expect
183
365
      // that the decremented value has been spilled to the stack. Because
184
365
      // this value isn't actually going to be produced until the latch, by LE,
185
365
      // we would need to generate a real sub. The value is also likely to be
186
365
      // reloaded for use of LoopEnd - in which in case we'd need to perform
187
365
      // an add because it gets negated again by LE! The other option is to
188
365
      // then generate the other form of LE which doesn't perform the sub.
189
365
      if (MI.mayLoad() || 
MI.mayStore()323
)
190
138
        Revert =
191
138
          MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == ARM::LR;
192
365
    }
193
149
194
149
    if (Dec && 
End76
&&
Revert76
)
195
2
      break;
196
149
  }
197
77
198
77
  LLVM_DEBUG(if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
199
77
             if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
200
77
             if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;);
201
77
202
77
  if (!Start && 
!Dec20
&&
!End19
) {
203
19
    LLVM_DEBUG(dbgs() << "ARM Loops: Not a low-overhead loop.\n");
204
19
    return Changed;
205
58
  } else if (!(Start && 
Dec57
&&
End57
)) {
206
1
    LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find all loop components.\n");
207
1
    return false;
208
1
  }
209
57
210
57
  if (!End->getOperand(1).isMBB() ||
211
57
      End->getOperand(1).getMBB() != ML->getHeader())
212
0
    report_fatal_error("Expected LoopEnd to target Loop Header");
213
57
214
57
  // The WLS and LE instructions have 12-bits for the label offset. WLS
215
57
  // requires a positive offset, while LE uses negative.
216
57
  if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML->getHeader()) ||
217
57
      
!BBUtils->isBBInRange(End, ML->getHeader(), 4094)45
) {
218
14
    LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
219
14
    Revert = true;
220
14
  }
221
57
  if (Start->getOpcode() == ARM::t2WhileLoopStart &&
222
57
      
(17
BBUtils->getOffsetOf(Start) >
223
17
       BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
224
17
       
!BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094)16
)) {
225
2
    LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
226
2
    Revert = true;
227
2
  }
228
57
229
57
  Expand(ML, Start, Dec, End, Revert);
230
57
  return true;
231
57
}
232
233
// WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
234
// beq that branches to the exit branch.
235
// FIXME: Need to check that we're not trashing the CPSR when generating the
236
// cmp. We could also try to generate a cbz if the value in LR is also in
237
// another low register.
238
5
void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
239
5
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
240
5
  MachineBasicBlock *MBB = MI->getParent();
241
5
  MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
242
5
                                    TII->get(ARM::t2CMPri));
243
5
  MIB.addReg(ARM::LR);
244
5
  MIB.addImm(0);
245
5
  MIB.addImm(ARMCC::AL);
246
5
  MIB.addReg(ARM::CPSR);
247
5
248
5
  // TODO: Try to use tBcc instead
249
5
  MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2Bcc));
250
5
  MIB.add(MI->getOperand(1));   // branch target
251
5
  MIB.addImm(ARMCC::EQ);        // condition code
252
5
  MIB.addReg(ARM::CPSR);
253
5
  MI->eraseFromParent();
254
5
}
255
256
// TODO: Check flags so that we can possibly generate a tSubs or tSub.
257
18
void ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
258
18
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
259
18
  MachineBasicBlock *MBB = MI->getParent();
260
18
  MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
261
18
                                    TII->get(ARM::t2SUBri));
262
18
  MIB.addDef(ARM::LR);
263
18
  MIB.add(MI->getOperand(1));
264
18
  MIB.add(MI->getOperand(2));
265
18
  MIB.addImm(ARMCC::AL);
266
18
  MIB.addReg(0);
267
18
  MIB.addReg(0);
268
18
  MI->eraseFromParent();
269
18
}
270
271
// Generate a subs, or sub and cmp, and a branch instead of an LE.
272
// FIXME: Need to check that we're not trashing the CPSR when generating
273
// the cmp.
274
18
void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI) const {
275
18
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);
276
18
277
18
  // Create cmp
278
18
  MachineBasicBlock *MBB = MI->getParent();
279
18
  MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
280
18
                                    TII->get(ARM::t2CMPri));
281
18
  MIB.addReg(ARM::LR);
282
18
  MIB.addImm(0);
283
18
  MIB.addImm(ARMCC::AL);
284
18
  MIB.addReg(ARM::CPSR);
285
18
286
18
  // TODO Try to use tBcc instead.
287
18
  // Create bne
288
18
  MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2Bcc));
289
18
  MIB.add(MI->getOperand(1));   // branch target
290
18
  MIB.addImm(ARMCC::NE);        // condition code
291
18
  MIB.addReg(ARM::CPSR);
292
18
  MI->eraseFromParent();
293
18
}
294
295
void ARMLowOverheadLoops::Expand(MachineLoop *ML, MachineInstr *Start,
296
                                 MachineInstr *Dec, MachineInstr *End,
297
57
                                 bool Revert) {
298
57
299
57
  auto ExpandLoopStart = [this](MachineLoop *ML, MachineInstr *Start) {
300
40
    // The trip count should already been held in LR since the instructions
301
40
    // within the loop can only read and write to LR. So, there should be a
302
40
    // mov to setup the count. WLS/DLS perform this move, so find the original
303
40
    // and delete it - inserting WLS/DLS in its place.
304
40
    MachineBasicBlock *MBB = Start->getParent();
305
40
    MachineInstr *InsertPt = Start;
306
82
    for (auto &I : MRI->def_instructions(ARM::LR)) {
307
82
      if (I.getParent() != MBB)
308
59
        continue;
309
23
310
23
      // Always execute.
311
23
      if (!I.getOperand(2).isImm() || 
I.getOperand(2).getImm() != ARMCC::AL20
)
312
7
        continue;
313
16
314
16
      // Only handle move reg, if the trip count it will need moving into a reg
315
16
      // before the setup instruction anyway.
316
16
      if (!I.getDesc().isMoveReg() ||
317
16
          
!I.getOperand(1).isIdenticalTo(Start->getOperand(0))14
)
318
5
        continue;
319
11
      InsertPt = &I;
320
11
      break;
321
11
    }
322
40
323
40
    unsigned Opc = Start->getOpcode() == ARM::t2DoLoopStart ?
324
27
      ARM::t2DLS : 
ARM::t2WLS13
;
325
40
    MachineInstrBuilder MIB =
326
40
      BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc));
327
40
328
40
    MIB.addDef(ARM::LR);
329
40
    MIB.add(Start->getOperand(0));
330
40
    if (Opc == ARM::t2WLS)
331
13
      MIB.add(Start->getOperand(1));
332
40
333
40
    if (InsertPt != Start)
334
11
      InsertPt->eraseFromParent();
335
40
    Start->eraseFromParent();
336
40
    LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
337
40
    return &*MIB;
338
40
  };
339
57
340
57
  // Combine the LoopDec and LoopEnd instructions into LE(TP).
341
57
  auto ExpandLoopEnd = [this](MachineLoop *ML, MachineInstr *Dec,
342
57
                              MachineInstr *End) {
343
40
    MachineBasicBlock *MBB = End->getParent();
344
40
    MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
345
40
                                      TII->get(ARM::t2LEUpdate));
346
40
    MIB.addDef(ARM::LR);
347
40
    MIB.add(End->getOperand(0));
348
40
    MIB.add(End->getOperand(1));
349
40
    LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
350
40
351
40
    End->eraseFromParent();
352
40
    Dec->eraseFromParent();
353
40
    return &*MIB;
354
40
  };
355
57
356
57
  // TODO: We should be able to automatically remove these branches before we
357
57
  // get here - probably by teaching analyzeBranch about the pseudo
358
57
  // instructions.
359
57
  // If there is an unconditional branch, after I, that just branches to the
360
57
  // next block, remove it.
361
80
  auto RemoveDeadBranch = [](MachineInstr *I) {
362
80
    MachineBasicBlock *BB = I->getParent();
363
80
    MachineInstr *Terminator = &BB->instr_back();
364
80
    if (Terminator->isUnconditionalBranch() && 
I != Terminator53
) {
365
53
      MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
366
53
      if (BB->isLayoutSuccessor(Succ)) {
367
50
        LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
368
50
        Terminator->eraseFromParent();
369
50
      }
370
53
    }
371
80
  };
372
57
373
57
  if (Revert) {
374
17
    if (Start->getOpcode() == ARM::t2WhileLoopStart)
375
4
      RevertWhile(Start);
376
13
    else
377
13
      Start->eraseFromParent();
378
17
    RevertLoopDec(Dec);
379
17
    RevertLoopEnd(End);
380
40
  } else {
381
40
    Start = ExpandLoopStart(ML, Start);
382
40
    RemoveDeadBranch(Start);
383
40
    End = ExpandLoopEnd(ML, Dec, End);
384
40
    RemoveDeadBranch(End);
385
40
  }
386
57
}
387
388
1.09k
bool ARMLowOverheadLoops::RevertNonLoops(MachineFunction &MF) {
389
1.09k
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
390
1.09k
  bool Changed = false;
391
1.09k
392
1.42k
  for (auto &MBB : MF) {
393
1.42k
    SmallVector<MachineInstr*, 4> Starts;
394
1.42k
    SmallVector<MachineInstr*, 4> Decs;
395
1.42k
    SmallVector<MachineInstr*, 4> Ends;
396
1.42k
397
13.3k
    for (auto &I : MBB) {
398
13.3k
      if (IsLoopStart(I))
399
1
        Starts.push_back(&I);
400
13.3k
      else if (I.getOpcode() == ARM::t2LoopDec)
401
1
        Decs.push_back(&I);
402
13.3k
      else if (I.getOpcode() == ARM::t2LoopEnd)
403
1
        Ends.push_back(&I);
404
13.3k
    }
405
1.42k
406
1.42k
    if (Starts.empty() && 
Decs.empty()1.41k
&&
Ends.empty()1.41k
)
407
1.41k
      continue;
408
2
409
2
    Changed = true;
410
2
411
2
    for (auto *Start : Starts) {
412
1
      if (Start->getOpcode() == ARM::t2WhileLoopStart)
413
1
        RevertWhile(Start);
414
0
      else
415
0
        Start->eraseFromParent();
416
1
    }
417
2
    for (auto *Dec : Decs)
418
1
      RevertLoopDec(Dec);
419
2
420
2
    for (auto *End : Ends)
421
1
      RevertLoopEnd(End);
422
2
  }
423
1.09k
  return Changed;
424
1.09k
}
425
426
5.19k
FunctionPass *llvm::createARMLowOverheadLoopsPass() {
427
5.19k
  return new ARMLowOverheadLoops();
428
5.19k
}