Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonGenMux.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- HexagonGenMux.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
9
// During instruction selection, MUX instructions are generated for
10
// conditional assignments. Since such assignments often present an
11
// opportunity to predicate instructions, HexagonExpandCondsets
12
// expands MUXes into pairs of conditional transfers, and then proceeds
13
// with predication of the producers/consumers of the registers involved.
14
// This happens after exiting from the SSA form, but before the machine
15
// instruction scheduler. After the scheduler and after the register
16
// allocation there can be cases of pairs of conditional transfers
17
// resulting from a MUX where neither of them was further predicated. If
18
// these transfers are now placed far enough from the instruction defining
19
// the predicate register, they cannot use the .new form. In such cases it
20
// is better to collapse them back to a single MUX instruction.
21
22
#define DEBUG_TYPE "hexmux"
23
24
#include "HexagonInstrInfo.h"
25
#include "HexagonRegisterInfo.h"
26
#include "HexagonSubtarget.h"
27
#include "llvm/ADT/BitVector.h"
28
#include "llvm/ADT/DenseMap.h"
29
#include "llvm/ADT/SmallVector.h"
30
#include "llvm/ADT/StringRef.h"
31
#include "llvm/CodeGen/LivePhysRegs.h"
32
#include "llvm/CodeGen/MachineBasicBlock.h"
33
#include "llvm/CodeGen/MachineFunction.h"
34
#include "llvm/CodeGen/MachineFunctionPass.h"
35
#include "llvm/CodeGen/MachineInstr.h"
36
#include "llvm/CodeGen/MachineInstrBuilder.h"
37
#include "llvm/CodeGen/MachineOperand.h"
38
#include "llvm/IR/DebugLoc.h"
39
#include "llvm/MC/MCInstrDesc.h"
40
#include "llvm/MC/MCRegisterInfo.h"
41
#include "llvm/Pass.h"
42
#include "llvm/Support/CommandLine.h"
43
#include "llvm/Support/MathExtras.h"
44
#include <algorithm>
45
#include <cassert>
46
#include <iterator>
47
#include <limits>
48
#include <utility>
49
50
using namespace llvm;
51
52
namespace llvm {
53
54
  FunctionPass *createHexagonGenMux();
55
  void initializeHexagonGenMuxPass(PassRegistry& Registry);
56
57
} // end namespace llvm
58
59
// Initialize this to 0 to always prefer generating mux by default.
60
static cl::opt<unsigned> MinPredDist("hexagon-gen-mux-threshold", cl::Hidden,
61
  cl::init(0), cl::desc("Minimum distance between predicate definition and "
62
  "farther of the two predicated uses"));
63
64
namespace {
65
66
  class HexagonGenMux : public MachineFunctionPass {
67
  public:
68
    static char ID;
69
70
865
    HexagonGenMux() : MachineFunctionPass(ID) {}
71
72
4.22k
    StringRef getPassName() const override {
73
4.22k
      return "Hexagon generate mux instructions";
74
4.22k
    }
75
76
861
    void getAnalysisUsage(AnalysisUsage &AU) const override {
77
861
      MachineFunctionPass::getAnalysisUsage(AU);
78
861
    }
79
80
    bool runOnMachineFunction(MachineFunction &MF) override;
81
82
861
    MachineFunctionProperties getRequiredProperties() const override {
83
861
      return MachineFunctionProperties().set(
84
861
          MachineFunctionProperties::Property::NoVRegs);
85
861
    }
86
87
  private:
88
    const HexagonInstrInfo *HII = nullptr;
89
    const HexagonRegisterInfo *HRI = nullptr;
90
91
    struct CondsetInfo {
92
      unsigned PredR = 0;
93
      unsigned TrueX = std::numeric_limits<unsigned>::max();
94
      unsigned FalseX = std::numeric_limits<unsigned>::max();
95
96
314
      CondsetInfo() = default;
97
    };
98
99
    struct DefUseInfo {
100
      BitVector Defs, Uses;
101
102
0
      DefUseInfo() = default;
103
28.1k
      DefUseInfo(const BitVector &D, const BitVector &U) : Defs(D), Uses(U) {}
104
    };
105
106
    struct MuxInfo {
107
      MachineBasicBlock::iterator At;
108
      unsigned DefR, PredR;
109
      MachineOperand *SrcT, *SrcF;
110
      MachineInstr *Def1, *Def2;
111
112
      MuxInfo(MachineBasicBlock::iterator It, unsigned DR, unsigned PR,
113
              MachineOperand *TOp, MachineOperand *FOp, MachineInstr &D1,
114
              MachineInstr &D2)
115
          : At(It), DefR(DR), PredR(PR), SrcT(TOp), SrcF(FOp), Def1(&D1),
116
140
            Def2(&D2) {}
117
    };
118
119
    using InstrIndexMap = DenseMap<MachineInstr *, unsigned>;
120
    using DefUseInfoMap = DenseMap<unsigned, DefUseInfo>;
121
    using MuxInfoList = SmallVector<MuxInfo, 4>;
122
123
67.0k
    bool isRegPair(unsigned Reg) const {
124
67.0k
      return Hexagon::DoubleRegsRegClass.contains(Reg);
125
67.0k
    }
126
127
    void getSubRegs(unsigned Reg, BitVector &SRs) const;
128
    void expandReg(unsigned Reg, BitVector &Set) const;
129
    void getDefsUses(const MachineInstr *MI, BitVector &Defs,
130
          BitVector &Uses) const;
131
    void buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
132
          DefUseInfoMap &DUM);
133
    bool isCondTransfer(unsigned Opc) const;
134
    unsigned getMuxOpcode(const MachineOperand &Src1,
135
          const MachineOperand &Src2) const;
136
    bool genMuxInBlock(MachineBasicBlock &B);
137
  };
138
139
} // end anonymous namespace
140
141
char HexagonGenMux::ID = 0;
142
143
INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux",
144
  "Hexagon generate mux instructions", false, false)
145
146
4.68k
void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const {
147
14.0k
  for (MCSubRegIterator I(Reg, HRI); I.isValid(); 
++I9.36k
)
148
9.36k
    SRs[*I] = true;
149
4.68k
}
150
151
66.5k
void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const {
152
66.5k
  if (isRegPair(Reg))
153
4.68k
    getSubRegs(Reg, Set);
154
61.8k
  else
155
61.8k
    Set[Reg] = true;
156
66.5k
}
157
158
void HexagonGenMux::getDefsUses(const MachineInstr *MI, BitVector &Defs,
159
28.1k
      BitVector &Uses) const {
160
28.1k
  // First, get the implicit defs and uses for this instruction.
161
28.1k
  unsigned Opc = MI->getOpcode();
162
28.1k
  const MCInstrDesc &D = HII->get(Opc);
163
28.1k
  if (const MCPhysReg *R = D.ImplicitDefs)
164
13.3k
    
while (5.84k
*R)
165
7.46k
      expandReg(*R++, Defs);
166
28.1k
  if (const MCPhysReg *R = D.ImplicitUses)
167
5.42k
    
while (2.15k
*R)
168
3.27k
      expandReg(*R++, Uses);
169
28.1k
170
28.1k
  // Look over all operands, and collect explicit defs and uses.
171
90.2k
  for (const MachineOperand &MO : MI->operands()) {
172
90.2k
    if (!MO.isReg() || 
MO.isImplicit()72.3k
)
173
34.4k
      continue;
174
55.7k
    unsigned R = MO.getReg();
175
55.7k
    BitVector &Set = MO.isDef() ? 
Defs20.1k
:
Uses35.5k
;
176
55.7k
    expandReg(R, Set);
177
55.7k
  }
178
28.1k
}
179
180
void HexagonGenMux::buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
181
5.00k
      DefUseInfoMap &DUM) {
182
5.00k
  unsigned Index = 0;
183
5.00k
  unsigned NR = HRI->getNumRegs();
184
5.00k
  BitVector Defs(NR), Uses(NR);
185
5.00k
186
33.1k
  for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; 
++I28.1k
) {
187
28.1k
    MachineInstr *MI = &*I;
188
28.1k
    I2X.insert(std::make_pair(MI, Index));
189
28.1k
    Defs.reset();
190
28.1k
    Uses.reset();
191
28.1k
    getDefsUses(MI, Defs, Uses);
192
28.1k
    DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses)));
193
28.1k
    Index++;
194
28.1k
  }
195
5.00k
}
196
197
28.1k
bool HexagonGenMux::isCondTransfer(unsigned Opc) const {
198
28.1k
  switch (Opc) {
199
28.1k
    case Hexagon::A2_tfrt:
200
510
    case Hexagon::A2_tfrf:
201
510
    case Hexagon::C2_cmoveit:
202
510
    case Hexagon::C2_cmoveif:
203
510
      return true;
204
27.6k
  }
205
27.6k
  return false;
206
27.6k
}
207
208
unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1,
209
140
      const MachineOperand &Src2) const {
210
140
  bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg();
211
140
  if (IsReg1)
212
59
    return IsReg2 ? 
Hexagon::C2_mux12
:
Hexagon::C2_muxir47
;
213
81
  if (IsReg2)
214
11
    return Hexagon::C2_muxri;
215
70
216
70
  // Neither is a register. The first source is extendable, but the second
217
70
  // is not (s8).
218
70
  if (Src2.isImm() && isInt<8>(Src2.getImm()))
219
66
    return Hexagon::C2_muxii;
220
4
221
4
  return 0;
222
4
}
223
224
5.00k
bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) {
225
5.00k
  bool Changed = false;
226
5.00k
  InstrIndexMap I2X;
227
5.00k
  DefUseInfoMap DUM;
228
5.00k
  buildMaps(B, I2X, DUM);
229
5.00k
230
5.00k
  using CondsetMap = DenseMap<unsigned, CondsetInfo>;
231
5.00k
232
5.00k
  CondsetMap CM;
233
5.00k
  MuxInfoList ML;
234
5.00k
235
5.00k
  MachineBasicBlock::iterator NextI, End = B.end();
236
33.1k
  for (MachineBasicBlock::iterator I = B.begin(); I != End; 
I = NextI28.1k
) {
237
28.1k
    MachineInstr *MI = &*I;
238
28.1k
    NextI = std::next(I);
239
28.1k
    unsigned Opc = MI->getOpcode();
240
28.1k
    if (!isCondTransfer(Opc))
241
27.6k
      continue;
242
510
    unsigned DR = MI->getOperand(0).getReg();
243
510
    if (isRegPair(DR))
244
0
      continue;
245
510
    MachineOperand &PredOp = MI->getOperand(1);
246
510
    if (PredOp.isUndef())
247
3
      continue;
248
507
249
507
    unsigned PR = PredOp.getReg();
250
507
    unsigned Idx = I2X.lookup(MI);
251
507
    CondsetMap::iterator F = CM.find(DR);
252
507
    bool IfTrue = HII->isPredicatedTrue(Opc);
253
507
254
507
    // If there is no record of a conditional transfer for this register,
255
507
    // or the predicate register differs, create a new record for it.
256
507
    if (F != CM.end() && 
F->second.PredR != PR262
) {
257
69
      CM.erase(F);
258
69
      F = CM.end();
259
69
    }
260
507
    if (F == CM.end()) {
261
314
      auto It = CM.insert(std::make_pair(DR, CondsetInfo()));
262
314
      F = It.first;
263
314
      F->second.PredR = PR;
264
314
    }
265
507
    CondsetInfo &CI = F->second;
266
507
    if (IfTrue)
267
227
      CI.TrueX = Idx;
268
280
    else
269
280
      CI.FalseX = Idx;
270
507
    if (CI.TrueX == std::numeric_limits<unsigned>::max() ||
271
507
        
CI.FalseX == std::numeric_limits<unsigned>::max()396
)
272
318
      continue;
273
189
274
189
    // There is now a complete definition of DR, i.e. we have the predicate
275
189
    // register, the definition if-true, and definition if-false.
276
189
277
189
    // First, check if the definitions are far enough from the definition
278
189
    // of the predicate register.
279
189
    unsigned MinX = std::min(CI.TrueX, CI.FalseX);
280
189
    unsigned MaxX = std::max(CI.TrueX, CI.FalseX);
281
189
    // Specifically, check if the predicate definition is within a prescribed
282
189
    // distance from the farther of the two predicated instructions.
283
189
    unsigned SearchX = (MaxX >= MinPredDist) ? 
MaxX-MinPredDist168
:
021
;
284
189
    bool NearDef = false;
285
193
    for (unsigned X = SearchX; X < MaxX; 
++X4
) {
286
25
      const DefUseInfo &DU = DUM.lookup(X);
287
25
      if (!DU.Defs[PR])
288
4
        continue;
289
21
      NearDef = true;
290
21
      break;
291
21
    }
292
189
    if (NearDef)
293
21
      continue;
294
168
295
168
    // The predicate register is not defined in the last few instructions.
296
168
    // Check if the conversion to MUX is possible (either "up", i.e. at the
297
168
    // place of the earlier partial definition, or "down", where the later
298
168
    // definition is located). Examine all defs and uses between these two
299
168
    // definitions.
300
168
    // SR1, SR2 - source registers from the first and the second definition.
301
168
    MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin();
302
168
    std::advance(It1, MinX);
303
168
    std::advance(It2, MaxX);
304
168
    MachineInstr &Def1 = *It1, &Def2 = *It2;
305
168
    MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2);
306
168
    Register SR1 = Src1->isReg() ? 
Src1->getReg()62
:
Register()106
;
307
168
    Register SR2 = Src2->isReg() ? 
Src2->getReg()38
:
Register()130
;
308
168
    bool Failure = false, CanUp = true, CanDown = true;
309
437
    for (unsigned X = MinX+1; X < MaxX; 
X++269
) {
310
296
      const DefUseInfo &DU = DUM.lookup(X);
311
296
      if (DU.Defs[PR] || 
DU.Defs[DR]284
||
DU.Uses[DR]277
) {
312
27
        Failure = true;
313
27
        break;
314
27
      }
315
269
      if (CanDown && 
DU.Defs[SR1]265
)
316
10
        CanDown = false;
317
269
      if (CanUp && 
DU.Defs[SR2]265
)
318
3
        CanUp = false;
319
269
    }
320
168
    if (Failure || 
(141
!CanUp141
&&
!CanDown1
))
321
28
      continue;
322
140
323
140
    MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : 
Src20
;
324
140
    MachineOperand *SrcF = (MinX == CI.FalseX) ? 
Src10
: Src2;
325
140
    // Prefer "down", since this will move the MUX farther away from the
326
140
    // predicate definition.
327
140
    MachineBasicBlock::iterator At = CanDown ? 
Def2131
:
Def19
;
328
140
    ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2));
329
140
  }
330
5.00k
331
5.00k
  for (MuxInfo &MX : ML) {
332
140
    unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF);
333
140
    if (!MxOpc)
334
4
      continue;
335
136
    MachineBasicBlock &B = *MX.At->getParent();
336
136
    const DebugLoc &DL = B.findDebugLoc(MX.At);
337
136
    auto NewMux = BuildMI(B, MX.At, DL, HII->get(MxOpc), MX.DefR)
338
136
                      .addReg(MX.PredR)
339
136
                      .add(*MX.SrcT)
340
136
                      .add(*MX.SrcF);
341
136
    NewMux->clearKillInfo();
342
136
    B.erase(MX.Def1);
343
136
    B.erase(MX.Def2);
344
136
    Changed = true;
345
136
  }
346
5.00k
347
5.00k
  // Fix up kill flags.
348
5.00k
349
5.00k
  LivePhysRegs LPR(*HRI);
350
5.00k
  LPR.addLiveOuts(B);
351
42.7k
  auto IsLive = [&LPR,this] (unsigned Reg) -> bool {
352
71.6k
    for (MCSubRegIterator S(Reg, HRI, true); S.isValid(); 
++S28.8k
)
353
48.8k
      if (LPR.contains(*S))
354
20.0k
        return true;
355
42.7k
    
return false22.7k
;
356
42.7k
  };
357
33.0k
  for (auto I = B.rbegin(), E = B.rend(); I != E; 
++I28.0k
) {
358
28.0k
    if (I->isDebugInstr())
359
21
      continue;
360
27.9k
    // This isn't 100% accurate, but it's safe.
361
27.9k
    // It won't detect (as a kill) a case like this
362
27.9k
    //   r0 = add r0, 1    <-- r0 should be "killed"
363
27.9k
    //   ... = r0
364
89.7k
    
for (MachineOperand &Op : I->operands())27.9k
{
365
89.7k
      if (!Op.isReg() || 
!Op.isUse()71.9k
)
366
46.9k
        continue;
367
42.7k
      assert(Op.getSubReg() == 0 && "Should have physical registers only");
368
42.7k
      bool Live = IsLive(Op.getReg());
369
42.7k
      Op.setIsKill(!Live);
370
42.7k
    }
371
27.9k
    LPR.stepBackward(*I);
372
27.9k
  }
373
5.00k
374
5.00k
  return Changed;
375
5.00k
}
376
377
3.36k
bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) {
378
3.36k
  if (skipFunction(MF.getFunction()))
379
10
    return false;
380
3.35k
  HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
381
3.35k
  HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
382
3.35k
  bool Changed = false;
383
3.35k
  for (auto &I : MF)
384
5.00k
    Changed |= genMuxInBlock(I);
385
3.35k
  return Changed;
386
3.35k
}
387
388
862
FunctionPass *llvm::createHexagonGenMux() {
389
862
  return new HexagonGenMux();
390
862
}