1 //===- HexagonExpandCondsets.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 // Replace mux instructions with the corresponding legal instructions.
10 // It is meant to work post-SSA, but still on virtual registers. It was
11 // originally placed between register coalescing and machine instruction
12 // scheduler.
13 // In this place in the optimization sequence, live interval analysis had
14 // been performed, and the live intervals should be preserved. A large part
15 // of the code deals with preserving the liveness information.
16 //
17 // Liveness tracking aside, the main functionality of this pass is divided
18 // into two steps. The first step is to replace an instruction
19 // %0 = C2_mux %1, %2, %3
20 // with a pair of conditional transfers
21 // %0 = A2_tfrt %1, %2
22 // %0 = A2_tfrf %1, %3
23 // It is the intention that the execution of this pass could be terminated
24 // after this step, and the code generated would be functionally correct.
25 //
26 // If the uses of the source values %1 and %2 are kills, and their
27 // definitions are predicable, then in the second step, the conditional
28 // transfers will then be rewritten as predicated instructions. E.g.
29 // %0 = A2_or %1, %2
30 // %3 = A2_tfrt %99, killed %0
31 // will be rewritten as
32 // %3 = A2_port %99, %1, %2
33 //
34 // This replacement has two variants: "up" and "down". Consider this case:
35 // %0 = A2_or %1, %2
36 // ... [intervening instructions] ...
37 // %3 = A2_tfrt %99, killed %0
38 // variant "up":
39 // %3 = A2_port %99, %1, %2
40 // ... [intervening instructions, %0->vreg3] ...
41 // [deleted]
42 // variant "down":
43 // [deleted]
44 // ... [intervening instructions] ...
45 // %3 = A2_port %99, %1, %2
46 //
47 // Both, one or none of these variants may be valid, and checks are made
48 // to rule out inapplicable variants.
49 //
50 // As an additional optimization, before either of the two steps above is
51 // executed, the pass attempts to coalesce the target register with one of
52 // the source registers, e.g. given an instruction
53 // %3 = C2_mux %0, %1, %2
54 // %3 will be coalesced with either %1 or %2. If this succeeds,
55 // the instruction would then be (for example)
56 // %3 = C2_mux %0, %3, %2
57 // and, under certain circumstances, this could result in only one predicated
58 // instruction:
59 // %3 = A2_tfrf %0, %2
60 //
61
62 // Splitting a definition of a register into two predicated transfers
63 // creates a complication in liveness tracking. Live interval computation
64 // will see both instructions as actual definitions, and will mark the
65 // first one as dead. The definition is not actually dead, and this
66 // situation will need to be fixed. For example:
67 // dead %1 = A2_tfrt ... ; marked as dead
68 // %1 = A2_tfrf ...
69 //
70 // Since any of the individual predicated transfers may end up getting
71 // removed (in case it is an identity copy), some pre-existing def may
72 // be marked as dead after live interval recomputation:
73 // dead %1 = ... ; marked as dead
74 // ...
75 // %1 = A2_tfrf ... ; if A2_tfrt is removed
76 // This case happens if %1 was used as a source in A2_tfrt, which means
77 // that is it actually live at the A2_tfrf, and so the now dead definition
78 // of %1 will need to be updated to non-dead at some point.
79 //
80 // This issue could be remedied by adding implicit uses to the predicated
81 // transfers, but this will create a problem with subsequent predication,
82 // since the transfers will no longer be possible to reorder. To avoid
83 // that, the initial splitting will not add any implicit uses. These
84 // implicit uses will be added later, after predication. The extra price,
85 // however, is that finding the locations where the implicit uses need
86 // to be added, and updating the live ranges will be more involved.
87
88 #include "HexagonInstrInfo.h"
89 #include "HexagonRegisterInfo.h"
90 #include "llvm/ADT/DenseMap.h"
91 #include "llvm/ADT/SetVector.h"
92 #include "llvm/ADT/SmallVector.h"
93 #include "llvm/ADT/StringRef.h"
94 #include "llvm/CodeGen/LiveInterval.h"
95 #include "llvm/CodeGen/LiveIntervals.h"
96 #include "llvm/CodeGen/MachineBasicBlock.h"
97 #include "llvm/CodeGen/MachineDominators.h"
98 #include "llvm/CodeGen/MachineFunction.h"
99 #include "llvm/CodeGen/MachineFunctionPass.h"
100 #include "llvm/CodeGen/MachineInstr.h"
101 #include "llvm/CodeGen/MachineInstrBuilder.h"
102 #include "llvm/CodeGen/MachineOperand.h"
103 #include "llvm/CodeGen/MachineRegisterInfo.h"
104 #include "llvm/CodeGen/SlotIndexes.h"
105 #include "llvm/CodeGen/TargetRegisterInfo.h"
106 #include "llvm/CodeGen/TargetSubtargetInfo.h"
107 #include "llvm/IR/DebugLoc.h"
108 #include "llvm/IR/Function.h"
109 #include "llvm/InitializePasses.h"
110 #include "llvm/MC/LaneBitmask.h"
111 #include "llvm/Pass.h"
112 #include "llvm/Support/CommandLine.h"
113 #include "llvm/Support/Debug.h"
114 #include "llvm/Support/ErrorHandling.h"
115 #include "llvm/Support/raw_ostream.h"
116 #include <cassert>
117 #include <iterator>
118 #include <map>
119 #include <set>
120 #include <utility>
121
122 #define DEBUG_TYPE "expand-condsets"
123
124 using namespace llvm;
125
126 static cl::opt<unsigned> OptTfrLimit("expand-condsets-tfr-limit",
127 cl::init(~0U), cl::Hidden, cl::desc("Max number of mux expansions"));
128 static cl::opt<unsigned> OptCoaLimit("expand-condsets-coa-limit",
129 cl::init(~0U), cl::Hidden, cl::desc("Max number of segment coalescings"));
130
131 namespace llvm {
132
133 void initializeHexagonExpandCondsetsPass(PassRegistry&);
134 FunctionPass *createHexagonExpandCondsets();
135
136 } // end namespace llvm
137
138 namespace {
139
140 class HexagonExpandCondsets : public MachineFunctionPass {
141 public:
142 static char ID;
143
HexagonExpandCondsets()144 HexagonExpandCondsets() : MachineFunctionPass(ID) {
145 if (OptCoaLimit.getPosition())
146 CoaLimitActive = true, CoaLimit = OptCoaLimit;
147 if (OptTfrLimit.getPosition())
148 TfrLimitActive = true, TfrLimit = OptTfrLimit;
149 initializeHexagonExpandCondsetsPass(*PassRegistry::getPassRegistry());
150 }
151
getPassName() const152 StringRef getPassName() const override { return "Hexagon Expand Condsets"; }
153
getAnalysisUsage(AnalysisUsage & AU) const154 void getAnalysisUsage(AnalysisUsage &AU) const override {
155 AU.addRequired<LiveIntervals>();
156 AU.addPreserved<LiveIntervals>();
157 AU.addPreserved<SlotIndexes>();
158 AU.addRequired<MachineDominatorTree>();
159 AU.addPreserved<MachineDominatorTree>();
160 MachineFunctionPass::getAnalysisUsage(AU);
161 }
162
163 bool runOnMachineFunction(MachineFunction &MF) override;
164
165 private:
166 const HexagonInstrInfo *HII = nullptr;
167 const TargetRegisterInfo *TRI = nullptr;
168 MachineDominatorTree *MDT;
169 MachineRegisterInfo *MRI = nullptr;
170 LiveIntervals *LIS = nullptr;
171 bool CoaLimitActive = false;
172 bool TfrLimitActive = false;
173 unsigned CoaLimit;
174 unsigned TfrLimit;
175 unsigned CoaCounter = 0;
176 unsigned TfrCounter = 0;
177
178 // FIXME: Consolidate duplicate definitions of RegisterRef
179 struct RegisterRef {
RegisterRef__anon75a264340111::HexagonExpandCondsets::RegisterRef180 RegisterRef(const MachineOperand &Op) : Reg(Op.getReg()),
181 Sub(Op.getSubReg()) {}
RegisterRef__anon75a264340111::HexagonExpandCondsets::RegisterRef182 RegisterRef(unsigned R = 0, unsigned S = 0) : Reg(R), Sub(S) {}
183
operator ==__anon75a264340111::HexagonExpandCondsets::RegisterRef184 bool operator== (RegisterRef RR) const {
185 return Reg == RR.Reg && Sub == RR.Sub;
186 }
operator !=__anon75a264340111::HexagonExpandCondsets::RegisterRef187 bool operator!= (RegisterRef RR) const { return !operator==(RR); }
operator <__anon75a264340111::HexagonExpandCondsets::RegisterRef188 bool operator< (RegisterRef RR) const {
189 return Reg < RR.Reg || (Reg == RR.Reg && Sub < RR.Sub);
190 }
191
192 Register Reg;
193 unsigned Sub;
194 };
195
196 using ReferenceMap = DenseMap<unsigned, unsigned>;
197 enum { Sub_Low = 0x1, Sub_High = 0x2, Sub_None = (Sub_Low | Sub_High) };
198 enum { Exec_Then = 0x10, Exec_Else = 0x20 };
199
200 unsigned getMaskForSub(unsigned Sub);
201 bool isCondset(const MachineInstr &MI);
202 LaneBitmask getLaneMask(Register Reg, unsigned Sub);
203
204 void addRefToMap(RegisterRef RR, ReferenceMap &Map, unsigned Exec);
205 bool isRefInMap(RegisterRef, ReferenceMap &Map, unsigned Exec);
206
207 void updateDeadsInRange(Register Reg, LaneBitmask LM, LiveRange &Range);
208 void updateKillFlags(Register Reg);
209 void updateDeadFlags(Register Reg);
210 void recalculateLiveInterval(Register Reg);
211 void removeInstr(MachineInstr &MI);
212 void updateLiveness(const std::set<Register> &RegSet, bool Recalc,
213 bool UpdateKills, bool UpdateDeads);
214 void distributeLiveIntervals(const std::set<Register> &Regs);
215
216 unsigned getCondTfrOpcode(const MachineOperand &SO, bool Cond);
217 MachineInstr *genCondTfrFor(MachineOperand &SrcOp,
218 MachineBasicBlock::iterator At, unsigned DstR,
219 unsigned DstSR, const MachineOperand &PredOp, bool PredSense,
220 bool ReadUndef, bool ImpUse);
221 bool split(MachineInstr &MI, std::set<Register> &UpdRegs);
222
223 bool isPredicable(MachineInstr *MI);
224 MachineInstr *getReachingDefForPred(RegisterRef RD,
225 MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond);
226 bool canMoveOver(MachineInstr &MI, ReferenceMap &Defs, ReferenceMap &Uses);
227 bool canMoveMemTo(MachineInstr &MI, MachineInstr &ToI, bool IsDown);
228 void predicateAt(const MachineOperand &DefOp, MachineInstr &MI,
229 MachineBasicBlock::iterator Where,
230 const MachineOperand &PredOp, bool Cond,
231 std::set<Register> &UpdRegs);
232 void renameInRange(RegisterRef RO, RegisterRef RN, unsigned PredR,
233 bool Cond, MachineBasicBlock::iterator First,
234 MachineBasicBlock::iterator Last);
235 bool predicate(MachineInstr &TfrI, bool Cond, std::set<Register> &UpdRegs);
236 bool predicateInBlock(MachineBasicBlock &B, std::set<Register> &UpdRegs);
237
238 bool isIntReg(RegisterRef RR, unsigned &BW);
239 bool isIntraBlocks(LiveInterval &LI);
240 bool coalesceRegisters(RegisterRef R1, RegisterRef R2);
241 bool coalesceSegments(const SmallVectorImpl<MachineInstr *> &Condsets,
242 std::set<Register> &UpdRegs);
243 };
244
245 } // end anonymous namespace
246
247 char HexagonExpandCondsets::ID = 0;
248
249 namespace llvm {
250
251 char &HexagonExpandCondsetsID = HexagonExpandCondsets::ID;
252
253 } // end namespace llvm
254
255 INITIALIZE_PASS_BEGIN(HexagonExpandCondsets, "expand-condsets",
256 "Hexagon Expand Condsets", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)257 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
258 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
259 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
260 INITIALIZE_PASS_END(HexagonExpandCondsets, "expand-condsets",
261 "Hexagon Expand Condsets", false, false)
262
263 unsigned HexagonExpandCondsets::getMaskForSub(unsigned Sub) {
264 switch (Sub) {
265 case Hexagon::isub_lo:
266 case Hexagon::vsub_lo:
267 return Sub_Low;
268 case Hexagon::isub_hi:
269 case Hexagon::vsub_hi:
270 return Sub_High;
271 case Hexagon::NoSubRegister:
272 return Sub_None;
273 }
274 llvm_unreachable("Invalid subregister");
275 }
276
isCondset(const MachineInstr & MI)277 bool HexagonExpandCondsets::isCondset(const MachineInstr &MI) {
278 unsigned Opc = MI.getOpcode();
279 switch (Opc) {
280 case Hexagon::C2_mux:
281 case Hexagon::C2_muxii:
282 case Hexagon::C2_muxir:
283 case Hexagon::C2_muxri:
284 case Hexagon::PS_pselect:
285 return true;
286 break;
287 }
288 return false;
289 }
290
getLaneMask(Register Reg,unsigned Sub)291 LaneBitmask HexagonExpandCondsets::getLaneMask(Register Reg, unsigned Sub) {
292 assert(Reg.isVirtual());
293 return Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
294 : MRI->getMaxLaneMaskForVReg(Reg);
295 }
296
addRefToMap(RegisterRef RR,ReferenceMap & Map,unsigned Exec)297 void HexagonExpandCondsets::addRefToMap(RegisterRef RR, ReferenceMap &Map,
298 unsigned Exec) {
299 unsigned Mask = getMaskForSub(RR.Sub) | Exec;
300 ReferenceMap::iterator F = Map.find(RR.Reg);
301 if (F == Map.end())
302 Map.insert(std::make_pair(RR.Reg, Mask));
303 else
304 F->second |= Mask;
305 }
306
isRefInMap(RegisterRef RR,ReferenceMap & Map,unsigned Exec)307 bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map,
308 unsigned Exec) {
309 ReferenceMap::iterator F = Map.find(RR.Reg);
310 if (F == Map.end())
311 return false;
312 unsigned Mask = getMaskForSub(RR.Sub) | Exec;
313 if (Mask & F->second)
314 return true;
315 return false;
316 }
317
updateKillFlags(Register Reg)318 void HexagonExpandCondsets::updateKillFlags(Register Reg) {
319 auto KillAt = [this,Reg] (SlotIndex K, LaneBitmask LM) -> void {
320 // Set the <kill> flag on a use of Reg whose lane mask is contained in LM.
321 MachineInstr *MI = LIS->getInstructionFromIndex(K);
322 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
323 MachineOperand &Op = MI->getOperand(i);
324 if (!Op.isReg() || !Op.isUse() || Op.getReg() != Reg ||
325 MI->isRegTiedToDefOperand(i))
326 continue;
327 LaneBitmask SLM = getLaneMask(Reg, Op.getSubReg());
328 if ((SLM & LM) == SLM) {
329 // Only set the kill flag on the first encountered use of Reg in this
330 // instruction.
331 Op.setIsKill(true);
332 break;
333 }
334 }
335 };
336
337 LiveInterval &LI = LIS->getInterval(Reg);
338 for (auto I = LI.begin(), E = LI.end(); I != E; ++I) {
339 if (!I->end.isRegister())
340 continue;
341 // Do not mark the end of the segment as <kill>, if the next segment
342 // starts with a predicated instruction.
343 auto NextI = std::next(I);
344 if (NextI != E && NextI->start.isRegister()) {
345 MachineInstr *DefI = LIS->getInstructionFromIndex(NextI->start);
346 if (HII->isPredicated(*DefI))
347 continue;
348 }
349 bool WholeReg = true;
350 if (LI.hasSubRanges()) {
351 auto EndsAtI = [I] (LiveInterval::SubRange &S) -> bool {
352 LiveRange::iterator F = S.find(I->end);
353 return F != S.end() && I->end == F->end;
354 };
355 // Check if all subranges end at I->end. If so, make sure to kill
356 // the whole register.
357 for (LiveInterval::SubRange &S : LI.subranges()) {
358 if (EndsAtI(S))
359 KillAt(I->end, S.LaneMask);
360 else
361 WholeReg = false;
362 }
363 }
364 if (WholeReg)
365 KillAt(I->end, MRI->getMaxLaneMaskForVReg(Reg));
366 }
367 }
368
updateDeadsInRange(Register Reg,LaneBitmask LM,LiveRange & Range)369 void HexagonExpandCondsets::updateDeadsInRange(Register Reg, LaneBitmask LM,
370 LiveRange &Range) {
371 assert(Reg.isVirtual());
372 if (Range.empty())
373 return;
374
375 // Return two booleans: { def-modifes-reg, def-covers-reg }.
376 auto IsRegDef = [this,Reg,LM] (MachineOperand &Op) -> std::pair<bool,bool> {
377 if (!Op.isReg() || !Op.isDef())
378 return { false, false };
379 Register DR = Op.getReg(), DSR = Op.getSubReg();
380 if (!DR.isVirtual() || DR != Reg)
381 return { false, false };
382 LaneBitmask SLM = getLaneMask(DR, DSR);
383 LaneBitmask A = SLM & LM;
384 return { A.any(), A == SLM };
385 };
386
387 // The splitting step will create pairs of predicated definitions without
388 // any implicit uses (since implicit uses would interfere with predication).
389 // This can cause the reaching defs to become dead after live range
390 // recomputation, even though they are not really dead.
391 // We need to identify predicated defs that need implicit uses, and
392 // dead defs that are not really dead, and correct both problems.
393
394 auto Dominate = [this] (SetVector<MachineBasicBlock*> &Defs,
395 MachineBasicBlock *Dest) -> bool {
396 for (MachineBasicBlock *D : Defs) {
397 if (D != Dest && MDT->dominates(D, Dest))
398 return true;
399 }
400 MachineBasicBlock *Entry = &Dest->getParent()->front();
401 SetVector<MachineBasicBlock*> Work(Dest->pred_begin(), Dest->pred_end());
402 for (unsigned i = 0; i < Work.size(); ++i) {
403 MachineBasicBlock *B = Work[i];
404 if (Defs.count(B))
405 continue;
406 if (B == Entry)
407 return false;
408 for (auto *P : B->predecessors())
409 Work.insert(P);
410 }
411 return true;
412 };
413
414 // First, try to extend live range within individual basic blocks. This
415 // will leave us only with dead defs that do not reach any predicated
416 // defs in the same block.
417 SetVector<MachineBasicBlock*> Defs;
418 SmallVector<SlotIndex,4> PredDefs;
419 for (auto &Seg : Range) {
420 if (!Seg.start.isRegister())
421 continue;
422 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
423 Defs.insert(DefI->getParent());
424 if (HII->isPredicated(*DefI))
425 PredDefs.push_back(Seg.start);
426 }
427
428 SmallVector<SlotIndex,8> Undefs;
429 LiveInterval &LI = LIS->getInterval(Reg);
430 LI.computeSubRangeUndefs(Undefs, LM, *MRI, *LIS->getSlotIndexes());
431
432 for (auto &SI : PredDefs) {
433 MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
434 auto P = Range.extendInBlock(Undefs, LIS->getMBBStartIdx(BB), SI);
435 if (P.first != nullptr || P.second)
436 SI = SlotIndex();
437 }
438
439 // Calculate reachability for those predicated defs that were not handled
440 // by the in-block extension.
441 SmallVector<SlotIndex,4> ExtTo;
442 for (auto &SI : PredDefs) {
443 if (!SI.isValid())
444 continue;
445 MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
446 if (BB->pred_empty())
447 continue;
448 // If the defs from this range reach SI via all predecessors, it is live.
449 // It can happen that SI is reached by the defs through some paths, but
450 // not all. In the IR coming into this optimization, SI would not be
451 // considered live, since the defs would then not jointly dominate SI.
452 // That means that SI is an overwriting def, and no implicit use is
453 // needed at this point. Do not add SI to the extension points, since
454 // extendToIndices will abort if there is no joint dominance.
455 // If the abort was avoided by adding extra undefs added to Undefs,
456 // extendToIndices could actually indicate that SI is live, contrary
457 // to the original IR.
458 if (Dominate(Defs, BB))
459 ExtTo.push_back(SI);
460 }
461
462 if (!ExtTo.empty())
463 LIS->extendToIndices(Range, ExtTo, Undefs);
464
465 // Remove <dead> flags from all defs that are not dead after live range
466 // extension, and collect all def operands. They will be used to generate
467 // the necessary implicit uses.
468 // At the same time, add <dead> flag to all defs that are actually dead.
469 // This can happen, for example, when a mux with identical inputs is
470 // replaced with a COPY: the use of the predicate register disappears and
471 // the dead can become dead.
472 std::set<RegisterRef> DefRegs;
473 for (auto &Seg : Range) {
474 if (!Seg.start.isRegister())
475 continue;
476 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
477 for (auto &Op : DefI->operands()) {
478 auto P = IsRegDef(Op);
479 if (P.second && Seg.end.isDead()) {
480 Op.setIsDead(true);
481 } else if (P.first) {
482 DefRegs.insert(Op);
483 Op.setIsDead(false);
484 }
485 }
486 }
487
488 // Now, add implicit uses to each predicated def that is reached
489 // by other defs.
490 for (auto &Seg : Range) {
491 if (!Seg.start.isRegister() || !Range.liveAt(Seg.start.getPrevSlot()))
492 continue;
493 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
494 if (!HII->isPredicated(*DefI))
495 continue;
496 // Construct the set of all necessary implicit uses, based on the def
497 // operands in the instruction. We need to tie the implicit uses to
498 // the corresponding defs.
499 std::map<RegisterRef,unsigned> ImpUses;
500 for (unsigned i = 0, e = DefI->getNumOperands(); i != e; ++i) {
501 MachineOperand &Op = DefI->getOperand(i);
502 if (!Op.isReg() || !DefRegs.count(Op))
503 continue;
504 if (Op.isDef()) {
505 // Tied defs will always have corresponding uses, so no extra
506 // implicit uses are needed.
507 if (!Op.isTied())
508 ImpUses.insert({Op, i});
509 } else {
510 // This function can be called for the same register with different
511 // lane masks. If the def in this instruction was for the whole
512 // register, we can get here more than once. Avoid adding multiple
513 // implicit uses (or adding an implicit use when an explicit one is
514 // present).
515 if (Op.isTied())
516 ImpUses.erase(Op);
517 }
518 }
519 if (ImpUses.empty())
520 continue;
521 MachineFunction &MF = *DefI->getParent()->getParent();
522 for (auto [R, DefIdx] : ImpUses) {
523 MachineInstrBuilder(MF, DefI).addReg(R.Reg, RegState::Implicit, R.Sub);
524 DefI->tieOperands(DefIdx, DefI->getNumOperands()-1);
525 }
526 }
527 }
528
updateDeadFlags(Register Reg)529 void HexagonExpandCondsets::updateDeadFlags(Register Reg) {
530 LiveInterval &LI = LIS->getInterval(Reg);
531 if (LI.hasSubRanges()) {
532 for (LiveInterval::SubRange &S : LI.subranges()) {
533 updateDeadsInRange(Reg, S.LaneMask, S);
534 LIS->shrinkToUses(S, Reg);
535 }
536 LI.clear();
537 LIS->constructMainRangeFromSubranges(LI);
538 } else {
539 updateDeadsInRange(Reg, MRI->getMaxLaneMaskForVReg(Reg), LI);
540 }
541 }
542
recalculateLiveInterval(Register Reg)543 void HexagonExpandCondsets::recalculateLiveInterval(Register Reg) {
544 LIS->removeInterval(Reg);
545 LIS->createAndComputeVirtRegInterval(Reg);
546 }
547
removeInstr(MachineInstr & MI)548 void HexagonExpandCondsets::removeInstr(MachineInstr &MI) {
549 LIS->RemoveMachineInstrFromMaps(MI);
550 MI.eraseFromParent();
551 }
552
updateLiveness(const std::set<Register> & RegSet,bool Recalc,bool UpdateKills,bool UpdateDeads)553 void HexagonExpandCondsets::updateLiveness(const std::set<Register> &RegSet,
554 bool Recalc, bool UpdateKills,
555 bool UpdateDeads) {
556 UpdateKills |= UpdateDeads;
557 for (Register R : RegSet) {
558 if (!R.isVirtual()) {
559 assert(R.isPhysical());
560 // There shouldn't be any physical registers as operands, except
561 // possibly reserved registers.
562 assert(MRI->isReserved(R));
563 continue;
564 }
565 if (Recalc)
566 recalculateLiveInterval(R);
567 if (UpdateKills)
568 MRI->clearKillFlags(R);
569 if (UpdateDeads)
570 updateDeadFlags(R);
571 // Fixing <dead> flags may extend live ranges, so reset <kill> flags
572 // after that.
573 if (UpdateKills)
574 updateKillFlags(R);
575 LIS->getInterval(R).verify();
576 }
577 }
578
distributeLiveIntervals(const std::set<Register> & Regs)579 void HexagonExpandCondsets::distributeLiveIntervals(
580 const std::set<Register> &Regs) {
581 ConnectedVNInfoEqClasses EQC(*LIS);
582 for (Register R : Regs) {
583 if (!R.isVirtual())
584 continue;
585 LiveInterval &LI = LIS->getInterval(R);
586 unsigned NumComp = EQC.Classify(LI);
587 if (NumComp == 1)
588 continue;
589
590 SmallVector<LiveInterval*> NewLIs;
591 const TargetRegisterClass *RC = MRI->getRegClass(LI.reg());
592 for (unsigned I = 1; I < NumComp; ++I) {
593 Register NewR = MRI->createVirtualRegister(RC);
594 NewLIs.push_back(&LIS->createEmptyInterval(NewR));
595 }
596 EQC.Distribute(LI, NewLIs.begin(), *MRI);
597 }
598 }
599
600 /// Get the opcode for a conditional transfer of the value in SO (source
601 /// operand). The condition (true/false) is given in Cond.
getCondTfrOpcode(const MachineOperand & SO,bool IfTrue)602 unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO,
603 bool IfTrue) {
604 if (SO.isReg()) {
605 MCRegister PhysR;
606 RegisterRef RS = SO;
607 if (RS.Reg.isVirtual()) {
608 const TargetRegisterClass *VC = MRI->getRegClass(RS.Reg);
609 assert(VC->begin() != VC->end() && "Empty register class");
610 PhysR = *VC->begin();
611 } else {
612 PhysR = RS.Reg;
613 }
614 MCRegister PhysS = (RS.Sub == 0) ? PhysR : TRI->getSubReg(PhysR, RS.Sub);
615 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(PhysS);
616 switch (TRI->getRegSizeInBits(*RC)) {
617 case 32:
618 return IfTrue ? Hexagon::A2_tfrt : Hexagon::A2_tfrf;
619 case 64:
620 return IfTrue ? Hexagon::A2_tfrpt : Hexagon::A2_tfrpf;
621 }
622 llvm_unreachable("Invalid register operand");
623 }
624 switch (SO.getType()) {
625 case MachineOperand::MO_Immediate:
626 case MachineOperand::MO_FPImmediate:
627 case MachineOperand::MO_ConstantPoolIndex:
628 case MachineOperand::MO_TargetIndex:
629 case MachineOperand::MO_JumpTableIndex:
630 case MachineOperand::MO_ExternalSymbol:
631 case MachineOperand::MO_GlobalAddress:
632 case MachineOperand::MO_BlockAddress:
633 return IfTrue ? Hexagon::C2_cmoveit : Hexagon::C2_cmoveif;
634 default:
635 break;
636 }
637 llvm_unreachable("Unexpected source operand");
638 }
639
640 /// Generate a conditional transfer, copying the value SrcOp to the
641 /// destination register DstR:DstSR, and using the predicate register from
642 /// PredOp. The Cond argument specifies whether the predicate is to be
643 /// if(PredOp), or if(!PredOp).
genCondTfrFor(MachineOperand & SrcOp,MachineBasicBlock::iterator At,unsigned DstR,unsigned DstSR,const MachineOperand & PredOp,bool PredSense,bool ReadUndef,bool ImpUse)644 MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp,
645 MachineBasicBlock::iterator At,
646 unsigned DstR, unsigned DstSR, const MachineOperand &PredOp,
647 bool PredSense, bool ReadUndef, bool ImpUse) {
648 MachineInstr *MI = SrcOp.getParent();
649 MachineBasicBlock &B = *At->getParent();
650 const DebugLoc &DL = MI->getDebugLoc();
651
652 // Don't avoid identity copies here (i.e. if the source and the destination
653 // are the same registers). It is actually better to generate them here,
654 // since this would cause the copy to potentially be predicated in the next
655 // step. The predication will remove such a copy if it is unable to
656 /// predicate.
657
658 unsigned Opc = getCondTfrOpcode(SrcOp, PredSense);
659 unsigned DstState = RegState::Define | (ReadUndef ? RegState::Undef : 0);
660 unsigned PredState = getRegState(PredOp) & ~RegState::Kill;
661 MachineInstrBuilder MIB;
662
663 if (SrcOp.isReg()) {
664 unsigned SrcState = getRegState(SrcOp);
665 if (RegisterRef(SrcOp) == RegisterRef(DstR, DstSR))
666 SrcState &= ~RegState::Kill;
667 MIB = BuildMI(B, At, DL, HII->get(Opc))
668 .addReg(DstR, DstState, DstSR)
669 .addReg(PredOp.getReg(), PredState, PredOp.getSubReg())
670 .addReg(SrcOp.getReg(), SrcState, SrcOp.getSubReg());
671 } else {
672 MIB = BuildMI(B, At, DL, HII->get(Opc))
673 .addReg(DstR, DstState, DstSR)
674 .addReg(PredOp.getReg(), PredState, PredOp.getSubReg())
675 .add(SrcOp);
676 }
677
678 LLVM_DEBUG(dbgs() << "created an initial copy: " << *MIB);
679 return &*MIB;
680 }
681
682 /// Replace a MUX instruction MI with a pair A2_tfrt/A2_tfrf. This function
683 /// performs all necessary changes to complete the replacement.
split(MachineInstr & MI,std::set<Register> & UpdRegs)684 bool HexagonExpandCondsets::split(MachineInstr &MI,
685 std::set<Register> &UpdRegs) {
686 if (TfrLimitActive) {
687 if (TfrCounter >= TfrLimit)
688 return false;
689 TfrCounter++;
690 }
691 LLVM_DEBUG(dbgs() << "\nsplitting " << printMBBReference(*MI.getParent())
692 << ": " << MI);
693 MachineOperand &MD = MI.getOperand(0); // Definition
694 MachineOperand &MP = MI.getOperand(1); // Predicate register
695 assert(MD.isDef());
696 Register DR = MD.getReg(), DSR = MD.getSubReg();
697 bool ReadUndef = MD.isUndef();
698 MachineBasicBlock::iterator At = MI;
699
700 auto updateRegs = [&UpdRegs] (const MachineInstr &MI) -> void {
701 for (auto &Op : MI.operands()) {
702 if (Op.isReg())
703 UpdRegs.insert(Op.getReg());
704 }
705 };
706
707 // If this is a mux of the same register, just replace it with COPY.
708 // Ideally, this would happen earlier, so that register coalescing would
709 // see it.
710 MachineOperand &ST = MI.getOperand(2);
711 MachineOperand &SF = MI.getOperand(3);
712 if (ST.isReg() && SF.isReg()) {
713 RegisterRef RT(ST);
714 if (RT == RegisterRef(SF)) {
715 // Copy regs to update first.
716 updateRegs(MI);
717 MI.setDesc(HII->get(TargetOpcode::COPY));
718 unsigned S = getRegState(ST);
719 while (MI.getNumOperands() > 1)
720 MI.removeOperand(MI.getNumOperands()-1);
721 MachineFunction &MF = *MI.getParent()->getParent();
722 MachineInstrBuilder(MF, MI).addReg(RT.Reg, S, RT.Sub);
723 return true;
724 }
725 }
726
727 // First, create the two invididual conditional transfers, and add each
728 // of them to the live intervals information. Do that first and then remove
729 // the old instruction from live intervals.
730 MachineInstr *TfrT =
731 genCondTfrFor(ST, At, DR, DSR, MP, true, ReadUndef, false);
732 MachineInstr *TfrF =
733 genCondTfrFor(SF, At, DR, DSR, MP, false, ReadUndef, true);
734 LIS->InsertMachineInstrInMaps(*TfrT);
735 LIS->InsertMachineInstrInMaps(*TfrF);
736
737 // Will need to recalculate live intervals for all registers in MI.
738 updateRegs(MI);
739
740 removeInstr(MI);
741 return true;
742 }
743
isPredicable(MachineInstr * MI)744 bool HexagonExpandCondsets::isPredicable(MachineInstr *MI) {
745 if (HII->isPredicated(*MI) || !HII->isPredicable(*MI))
746 return false;
747 if (MI->hasUnmodeledSideEffects() || MI->mayStore())
748 return false;
749 // Reject instructions with multiple defs (e.g. post-increment loads).
750 bool HasDef = false;
751 for (auto &Op : MI->operands()) {
752 if (!Op.isReg() || !Op.isDef())
753 continue;
754 if (HasDef)
755 return false;
756 HasDef = true;
757 }
758 for (auto &Mo : MI->memoperands()) {
759 if (Mo->isVolatile() || Mo->isAtomic())
760 return false;
761 }
762 return true;
763 }
764
765 /// Find the reaching definition for a predicated use of RD. The RD is used
766 /// under the conditions given by PredR and Cond, and this function will ignore
767 /// definitions that set RD under the opposite conditions.
getReachingDefForPred(RegisterRef RD,MachineBasicBlock::iterator UseIt,unsigned PredR,bool Cond)768 MachineInstr *HexagonExpandCondsets::getReachingDefForPred(RegisterRef RD,
769 MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond) {
770 MachineBasicBlock &B = *UseIt->getParent();
771 MachineBasicBlock::iterator I = UseIt, S = B.begin();
772 if (I == S)
773 return nullptr;
774
775 bool PredValid = true;
776 do {
777 --I;
778 MachineInstr *MI = &*I;
779 // Check if this instruction can be ignored, i.e. if it is predicated
780 // on the complementary condition.
781 if (PredValid && HII->isPredicated(*MI)) {
782 if (MI->readsRegister(PredR) && (Cond != HII->isPredicatedTrue(*MI)))
783 continue;
784 }
785
786 // Check the defs. If the PredR is defined, invalidate it. If RD is
787 // defined, return the instruction or 0, depending on the circumstances.
788 for (auto &Op : MI->operands()) {
789 if (!Op.isReg() || !Op.isDef())
790 continue;
791 RegisterRef RR = Op;
792 if (RR.Reg == PredR) {
793 PredValid = false;
794 continue;
795 }
796 if (RR.Reg != RD.Reg)
797 continue;
798 // If the "Reg" part agrees, there is still the subregister to check.
799 // If we are looking for %1:loreg, we can skip %1:hireg, but
800 // not %1 (w/o subregisters).
801 if (RR.Sub == RD.Sub)
802 return MI;
803 if (RR.Sub == 0 || RD.Sub == 0)
804 return nullptr;
805 // We have different subregisters, so we can continue looking.
806 }
807 } while (I != S);
808
809 return nullptr;
810 }
811
812 /// Check if the instruction MI can be safely moved over a set of instructions
813 /// whose side-effects (in terms of register defs and uses) are expressed in
814 /// the maps Defs and Uses. These maps reflect the conditional defs and uses
815 /// that depend on the same predicate register to allow moving instructions
816 /// over instructions predicated on the opposite condition.
canMoveOver(MachineInstr & MI,ReferenceMap & Defs,ReferenceMap & Uses)817 bool HexagonExpandCondsets::canMoveOver(MachineInstr &MI, ReferenceMap &Defs,
818 ReferenceMap &Uses) {
819 // In order to be able to safely move MI over instructions that define
820 // "Defs" and use "Uses", no def operand from MI can be defined or used
821 // and no use operand can be defined.
822 for (auto &Op : MI.operands()) {
823 if (!Op.isReg())
824 continue;
825 RegisterRef RR = Op;
826 // For physical register we would need to check register aliases, etc.
827 // and we don't want to bother with that. It would be of little value
828 // before the actual register rewriting (from virtual to physical).
829 if (!RR.Reg.isVirtual())
830 return false;
831 // No redefs for any operand.
832 if (isRefInMap(RR, Defs, Exec_Then))
833 return false;
834 // For defs, there cannot be uses.
835 if (Op.isDef() && isRefInMap(RR, Uses, Exec_Then))
836 return false;
837 }
838 return true;
839 }
840
841 /// Check if the instruction accessing memory (TheI) can be moved to the
842 /// location ToI.
canMoveMemTo(MachineInstr & TheI,MachineInstr & ToI,bool IsDown)843 bool HexagonExpandCondsets::canMoveMemTo(MachineInstr &TheI, MachineInstr &ToI,
844 bool IsDown) {
845 bool IsLoad = TheI.mayLoad(), IsStore = TheI.mayStore();
846 if (!IsLoad && !IsStore)
847 return true;
848 if (HII->areMemAccessesTriviallyDisjoint(TheI, ToI))
849 return true;
850 if (TheI.hasUnmodeledSideEffects())
851 return false;
852
853 MachineBasicBlock::iterator StartI = IsDown ? TheI : ToI;
854 MachineBasicBlock::iterator EndI = IsDown ? ToI : TheI;
855 bool Ordered = TheI.hasOrderedMemoryRef();
856
857 // Search for aliased memory reference in (StartI, EndI).
858 for (MachineInstr &MI : llvm::make_range(std::next(StartI), EndI)) {
859 if (MI.hasUnmodeledSideEffects())
860 return false;
861 bool L = MI.mayLoad(), S = MI.mayStore();
862 if (!L && !S)
863 continue;
864 if (Ordered && MI.hasOrderedMemoryRef())
865 return false;
866
867 bool Conflict = (L && IsStore) || S;
868 if (Conflict)
869 return false;
870 }
871 return true;
872 }
873
874 /// Generate a predicated version of MI (where the condition is given via
875 /// PredR and Cond) at the point indicated by Where.
predicateAt(const MachineOperand & DefOp,MachineInstr & MI,MachineBasicBlock::iterator Where,const MachineOperand & PredOp,bool Cond,std::set<Register> & UpdRegs)876 void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp,
877 MachineInstr &MI,
878 MachineBasicBlock::iterator Where,
879 const MachineOperand &PredOp, bool Cond,
880 std::set<Register> &UpdRegs) {
881 // The problem with updating live intervals is that we can move one def
882 // past another def. In particular, this can happen when moving an A2_tfrt
883 // over an A2_tfrf defining the same register. From the point of view of
884 // live intervals, these two instructions are two separate definitions,
885 // and each one starts another live segment. LiveIntervals's "handleMove"
886 // does not allow such moves, so we need to handle it ourselves. To avoid
887 // invalidating liveness data while we are using it, the move will be
888 // implemented in 4 steps: (1) add a clone of the instruction MI at the
889 // target location, (2) update liveness, (3) delete the old instruction,
890 // and (4) update liveness again.
891
892 MachineBasicBlock &B = *MI.getParent();
893 DebugLoc DL = Where->getDebugLoc(); // "Where" points to an instruction.
894 unsigned Opc = MI.getOpcode();
895 unsigned PredOpc = HII->getCondOpcode(Opc, !Cond);
896 MachineInstrBuilder MB = BuildMI(B, Where, DL, HII->get(PredOpc));
897 unsigned Ox = 0, NP = MI.getNumOperands();
898 // Skip all defs from MI first.
899 while (Ox < NP) {
900 MachineOperand &MO = MI.getOperand(Ox);
901 if (!MO.isReg() || !MO.isDef())
902 break;
903 Ox++;
904 }
905 // Add the new def, then the predicate register, then the rest of the
906 // operands.
907 MB.addReg(DefOp.getReg(), getRegState(DefOp), DefOp.getSubReg());
908 MB.addReg(PredOp.getReg(), PredOp.isUndef() ? RegState::Undef : 0,
909 PredOp.getSubReg());
910 while (Ox < NP) {
911 MachineOperand &MO = MI.getOperand(Ox);
912 if (!MO.isReg() || !MO.isImplicit())
913 MB.add(MO);
914 Ox++;
915 }
916 MB.cloneMemRefs(MI);
917
918 MachineInstr *NewI = MB;
919 NewI->clearKillInfo();
920 LIS->InsertMachineInstrInMaps(*NewI);
921
922 for (auto &Op : NewI->operands()) {
923 if (Op.isReg())
924 UpdRegs.insert(Op.getReg());
925 }
926 }
927
928 /// In the range [First, Last], rename all references to the "old" register RO
929 /// to the "new" register RN, but only in instructions predicated on the given
930 /// condition.
renameInRange(RegisterRef RO,RegisterRef RN,unsigned PredR,bool Cond,MachineBasicBlock::iterator First,MachineBasicBlock::iterator Last)931 void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef RN,
932 unsigned PredR, bool Cond, MachineBasicBlock::iterator First,
933 MachineBasicBlock::iterator Last) {
934 MachineBasicBlock::iterator End = std::next(Last);
935 for (MachineInstr &MI : llvm::make_range(First, End)) {
936 // Do not touch instructions that are not predicated, or are predicated
937 // on the opposite condition.
938 if (!HII->isPredicated(MI))
939 continue;
940 if (!MI.readsRegister(PredR) || (Cond != HII->isPredicatedTrue(MI)))
941 continue;
942
943 for (auto &Op : MI.operands()) {
944 if (!Op.isReg() || RO != RegisterRef(Op))
945 continue;
946 Op.setReg(RN.Reg);
947 Op.setSubReg(RN.Sub);
948 // In practice, this isn't supposed to see any defs.
949 assert(!Op.isDef() && "Not expecting a def");
950 }
951 }
952 }
953
954 /// For a given conditional copy, predicate the definition of the source of
955 /// the copy under the given condition (using the same predicate register as
956 /// the copy).
predicate(MachineInstr & TfrI,bool Cond,std::set<Register> & UpdRegs)957 bool HexagonExpandCondsets::predicate(MachineInstr &TfrI, bool Cond,
958 std::set<Register> &UpdRegs) {
959 // TfrI - A2_tfr[tf] Instruction (not A2_tfrsi).
960 unsigned Opc = TfrI.getOpcode();
961 (void)Opc;
962 assert(Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf);
963 LLVM_DEBUG(dbgs() << "\nattempt to predicate if-" << (Cond ? "true" : "false")
964 << ": " << TfrI);
965
966 MachineOperand &MD = TfrI.getOperand(0);
967 MachineOperand &MP = TfrI.getOperand(1);
968 MachineOperand &MS = TfrI.getOperand(2);
969 // The source operand should be a <kill>. This is not strictly necessary,
970 // but it makes things a lot simpler. Otherwise, we would need to rename
971 // some registers, which would complicate the transformation considerably.
972 if (!MS.isKill())
973 return false;
974 // Avoid predicating instructions that define a subregister if subregister
975 // liveness tracking is not enabled.
976 if (MD.getSubReg() && !MRI->shouldTrackSubRegLiveness(MD.getReg()))
977 return false;
978
979 RegisterRef RT(MS);
980 Register PredR = MP.getReg();
981 MachineInstr *DefI = getReachingDefForPred(RT, TfrI, PredR, Cond);
982 if (!DefI || !isPredicable(DefI))
983 return false;
984
985 LLVM_DEBUG(dbgs() << "Source def: " << *DefI);
986
987 // Collect the information about registers defined and used between the
988 // DefI and the TfrI.
989 // Map: reg -> bitmask of subregs
990 ReferenceMap Uses, Defs;
991 MachineBasicBlock::iterator DefIt = DefI, TfrIt = TfrI;
992
993 // Check if the predicate register is valid between DefI and TfrI.
994 // If it is, we can then ignore instructions predicated on the negated
995 // conditions when collecting def and use information.
996 bool PredValid = true;
997 for (MachineInstr &MI : llvm::make_range(std::next(DefIt), TfrIt)) {
998 if (!MI.modifiesRegister(PredR, nullptr))
999 continue;
1000 PredValid = false;
1001 break;
1002 }
1003
1004 for (MachineInstr &MI : llvm::make_range(std::next(DefIt), TfrIt)) {
1005 // If this instruction is predicated on the same register, it could
1006 // potentially be ignored.
1007 // By default assume that the instruction executes on the same condition
1008 // as TfrI (Exec_Then), and also on the opposite one (Exec_Else).
1009 unsigned Exec = Exec_Then | Exec_Else;
1010 if (PredValid && HII->isPredicated(MI) && MI.readsRegister(PredR))
1011 Exec = (Cond == HII->isPredicatedTrue(MI)) ? Exec_Then : Exec_Else;
1012
1013 for (auto &Op : MI.operands()) {
1014 if (!Op.isReg())
1015 continue;
1016 // We don't want to deal with physical registers. The reason is that
1017 // they can be aliased with other physical registers. Aliased virtual
1018 // registers must share the same register number, and can only differ
1019 // in the subregisters, which we are keeping track of. Physical
1020 // registers ters no longer have subregisters---their super- and
1021 // subregisters are other physical registers, and we are not checking
1022 // that.
1023 RegisterRef RR = Op;
1024 if (!RR.Reg.isVirtual())
1025 return false;
1026
1027 ReferenceMap &Map = Op.isDef() ? Defs : Uses;
1028 if (Op.isDef() && Op.isUndef()) {
1029 assert(RR.Sub && "Expecting a subregister on <def,read-undef>");
1030 // If this is a <def,read-undef>, then it invalidates the non-written
1031 // part of the register. For the purpose of checking the validity of
1032 // the move, assume that it modifies the whole register.
1033 RR.Sub = 0;
1034 }
1035 addRefToMap(RR, Map, Exec);
1036 }
1037 }
1038
1039 // The situation:
1040 // RT = DefI
1041 // ...
1042 // RD = TfrI ..., RT
1043
1044 // If the register-in-the-middle (RT) is used or redefined between
1045 // DefI and TfrI, we may not be able proceed with this transformation.
1046 // We can ignore a def that will not execute together with TfrI, and a
1047 // use that will. If there is such a use (that does execute together with
1048 // TfrI), we will not be able to move DefI down. If there is a use that
1049 // executed if TfrI's condition is false, then RT must be available
1050 // unconditionally (cannot be predicated).
1051 // Essentially, we need to be able to rename RT to RD in this segment.
1052 if (isRefInMap(RT, Defs, Exec_Then) || isRefInMap(RT, Uses, Exec_Else))
1053 return false;
1054 RegisterRef RD = MD;
1055 // If the predicate register is defined between DefI and TfrI, the only
1056 // potential thing to do would be to move the DefI down to TfrI, and then
1057 // predicate. The reaching def (DefI) must be movable down to the location
1058 // of the TfrI.
1059 // If the target register of the TfrI (RD) is not used or defined between
1060 // DefI and TfrI, consider moving TfrI up to DefI.
1061 bool CanUp = canMoveOver(TfrI, Defs, Uses);
1062 bool CanDown = canMoveOver(*DefI, Defs, Uses);
1063 // The TfrI does not access memory, but DefI could. Check if it's safe
1064 // to move DefI down to TfrI.
1065 if (DefI->mayLoadOrStore()) {
1066 if (!canMoveMemTo(*DefI, TfrI, true))
1067 CanDown = false;
1068 }
1069
1070 LLVM_DEBUG(dbgs() << "Can move up: " << (CanUp ? "yes" : "no")
1071 << ", can move down: " << (CanDown ? "yes\n" : "no\n"));
1072 MachineBasicBlock::iterator PastDefIt = std::next(DefIt);
1073 if (CanUp)
1074 predicateAt(MD, *DefI, PastDefIt, MP, Cond, UpdRegs);
1075 else if (CanDown)
1076 predicateAt(MD, *DefI, TfrIt, MP, Cond, UpdRegs);
1077 else
1078 return false;
1079
1080 if (RT != RD) {
1081 renameInRange(RT, RD, PredR, Cond, PastDefIt, TfrIt);
1082 UpdRegs.insert(RT.Reg);
1083 }
1084
1085 removeInstr(TfrI);
1086 removeInstr(*DefI);
1087 return true;
1088 }
1089
1090 /// Predicate all cases of conditional copies in the specified block.
predicateInBlock(MachineBasicBlock & B,std::set<Register> & UpdRegs)1091 bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B,
1092 std::set<Register> &UpdRegs) {
1093 bool Changed = false;
1094 for (MachineInstr &MI : llvm::make_early_inc_range(B)) {
1095 unsigned Opc = MI.getOpcode();
1096 if (Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf) {
1097 bool Done = predicate(MI, (Opc == Hexagon::A2_tfrt), UpdRegs);
1098 if (!Done) {
1099 // If we didn't predicate I, we may need to remove it in case it is
1100 // an "identity" copy, e.g. %1 = A2_tfrt %2, %1.
1101 if (RegisterRef(MI.getOperand(0)) == RegisterRef(MI.getOperand(2))) {
1102 for (auto &Op : MI.operands()) {
1103 if (Op.isReg())
1104 UpdRegs.insert(Op.getReg());
1105 }
1106 removeInstr(MI);
1107 }
1108 }
1109 Changed |= Done;
1110 }
1111 }
1112 return Changed;
1113 }
1114
isIntReg(RegisterRef RR,unsigned & BW)1115 bool HexagonExpandCondsets::isIntReg(RegisterRef RR, unsigned &BW) {
1116 if (!RR.Reg.isVirtual())
1117 return false;
1118 const TargetRegisterClass *RC = MRI->getRegClass(RR.Reg);
1119 if (RC == &Hexagon::IntRegsRegClass) {
1120 BW = 32;
1121 return true;
1122 }
1123 if (RC == &Hexagon::DoubleRegsRegClass) {
1124 BW = (RR.Sub != 0) ? 32 : 64;
1125 return true;
1126 }
1127 return false;
1128 }
1129
isIntraBlocks(LiveInterval & LI)1130 bool HexagonExpandCondsets::isIntraBlocks(LiveInterval &LI) {
1131 for (LiveRange::Segment &LR : LI) {
1132 // Range must start at a register...
1133 if (!LR.start.isRegister())
1134 return false;
1135 // ...and end in a register or in a dead slot.
1136 if (!LR.end.isRegister() && !LR.end.isDead())
1137 return false;
1138 }
1139 return true;
1140 }
1141
coalesceRegisters(RegisterRef R1,RegisterRef R2)1142 bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) {
1143 if (CoaLimitActive) {
1144 if (CoaCounter >= CoaLimit)
1145 return false;
1146 CoaCounter++;
1147 }
1148 unsigned BW1, BW2;
1149 if (!isIntReg(R1, BW1) || !isIntReg(R2, BW2) || BW1 != BW2)
1150 return false;
1151 if (MRI->isLiveIn(R1.Reg))
1152 return false;
1153 if (MRI->isLiveIn(R2.Reg))
1154 return false;
1155
1156 LiveInterval &L1 = LIS->getInterval(R1.Reg);
1157 LiveInterval &L2 = LIS->getInterval(R2.Reg);
1158 if (L2.empty())
1159 return false;
1160 if (L1.hasSubRanges() || L2.hasSubRanges())
1161 return false;
1162 bool Overlap = L1.overlaps(L2);
1163
1164 LLVM_DEBUG(dbgs() << "compatible registers: ("
1165 << (Overlap ? "overlap" : "disjoint") << ")\n "
1166 << printReg(R1.Reg, TRI, R1.Sub) << " " << L1 << "\n "
1167 << printReg(R2.Reg, TRI, R2.Sub) << " " << L2 << "\n");
1168 if (R1.Sub || R2.Sub)
1169 return false;
1170 if (Overlap)
1171 return false;
1172
1173 // Coalescing could have a negative impact on scheduling, so try to limit
1174 // to some reasonable extent. Only consider coalescing segments, when one
1175 // of them does not cross basic block boundaries.
1176 if (!isIntraBlocks(L1) && !isIntraBlocks(L2))
1177 return false;
1178
1179 MRI->replaceRegWith(R2.Reg, R1.Reg);
1180
1181 // Move all live segments from L2 to L1.
1182 using ValueInfoMap = DenseMap<VNInfo *, VNInfo *>;
1183 ValueInfoMap VM;
1184 for (LiveRange::Segment &I : L2) {
1185 VNInfo *NewVN, *OldVN = I.valno;
1186 ValueInfoMap::iterator F = VM.find(OldVN);
1187 if (F == VM.end()) {
1188 NewVN = L1.getNextValue(I.valno->def, LIS->getVNInfoAllocator());
1189 VM.insert(std::make_pair(OldVN, NewVN));
1190 } else {
1191 NewVN = F->second;
1192 }
1193 L1.addSegment(LiveRange::Segment(I.start, I.end, NewVN));
1194 }
1195 while (!L2.empty())
1196 L2.removeSegment(*L2.begin());
1197 LIS->removeInterval(R2.Reg);
1198
1199 updateKillFlags(R1.Reg);
1200 LLVM_DEBUG(dbgs() << "coalesced: " << L1 << "\n");
1201 L1.verify();
1202
1203 return true;
1204 }
1205
1206 /// Attempt to coalesce one of the source registers to a MUX instruction with
1207 /// the destination register. This could lead to having only one predicated
1208 /// instruction in the end instead of two.
coalesceSegments(const SmallVectorImpl<MachineInstr * > & Condsets,std::set<Register> & UpdRegs)1209 bool HexagonExpandCondsets::coalesceSegments(
1210 const SmallVectorImpl<MachineInstr *> &Condsets,
1211 std::set<Register> &UpdRegs) {
1212 SmallVector<MachineInstr*,16> TwoRegs;
1213 for (MachineInstr *MI : Condsets) {
1214 MachineOperand &S1 = MI->getOperand(2), &S2 = MI->getOperand(3);
1215 if (!S1.isReg() && !S2.isReg())
1216 continue;
1217 TwoRegs.push_back(MI);
1218 }
1219
1220 bool Changed = false;
1221 for (MachineInstr *CI : TwoRegs) {
1222 RegisterRef RD = CI->getOperand(0);
1223 RegisterRef RP = CI->getOperand(1);
1224 MachineOperand &S1 = CI->getOperand(2), &S2 = CI->getOperand(3);
1225 bool Done = false;
1226 // Consider this case:
1227 // %1 = instr1 ...
1228 // %2 = instr2 ...
1229 // %0 = C2_mux ..., %1, %2
1230 // If %0 was coalesced with %1, we could end up with the following
1231 // code:
1232 // %0 = instr1 ...
1233 // %2 = instr2 ...
1234 // %0 = A2_tfrf ..., %2
1235 // which will later become:
1236 // %0 = instr1 ...
1237 // %0 = instr2_cNotPt ...
1238 // i.e. there will be an unconditional definition (instr1) of %0
1239 // followed by a conditional one. The output dependency was there before
1240 // and it unavoidable, but if instr1 is predicable, we will no longer be
1241 // able to predicate it here.
1242 // To avoid this scenario, don't coalesce the destination register with
1243 // a source register that is defined by a predicable instruction.
1244 if (S1.isReg()) {
1245 RegisterRef RS = S1;
1246 MachineInstr *RDef = getReachingDefForPred(RS, CI, RP.Reg, true);
1247 if (!RDef || !HII->isPredicable(*RDef)) {
1248 Done = coalesceRegisters(RD, RegisterRef(S1));
1249 if (Done) {
1250 UpdRegs.insert(RD.Reg);
1251 UpdRegs.insert(S1.getReg());
1252 }
1253 }
1254 }
1255 if (!Done && S2.isReg()) {
1256 RegisterRef RS = S2;
1257 MachineInstr *RDef = getReachingDefForPred(RS, CI, RP.Reg, false);
1258 if (!RDef || !HII->isPredicable(*RDef)) {
1259 Done = coalesceRegisters(RD, RegisterRef(S2));
1260 if (Done) {
1261 UpdRegs.insert(RD.Reg);
1262 UpdRegs.insert(S2.getReg());
1263 }
1264 }
1265 }
1266 Changed |= Done;
1267 }
1268 return Changed;
1269 }
1270
runOnMachineFunction(MachineFunction & MF)1271 bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) {
1272 if (skipFunction(MF.getFunction()))
1273 return false;
1274
1275 HII = static_cast<const HexagonInstrInfo*>(MF.getSubtarget().getInstrInfo());
1276 TRI = MF.getSubtarget().getRegisterInfo();
1277 MDT = &getAnalysis<MachineDominatorTree>();
1278 LIS = &getAnalysis<LiveIntervals>();
1279 MRI = &MF.getRegInfo();
1280
1281 LLVM_DEBUG(LIS->print(dbgs() << "Before expand-condsets\n",
1282 MF.getFunction().getParent()));
1283
1284 bool Changed = false;
1285 std::set<Register> CoalUpd, PredUpd;
1286
1287 SmallVector<MachineInstr*,16> Condsets;
1288 for (auto &B : MF) {
1289 for (auto &I : B) {
1290 if (isCondset(I))
1291 Condsets.push_back(&I);
1292 }
1293 }
1294
1295 // Try to coalesce the target of a mux with one of its sources.
1296 // This could eliminate a register copy in some circumstances.
1297 Changed |= coalesceSegments(Condsets, CoalUpd);
1298
1299 // Update kill flags on all source operands. This is done here because
1300 // at this moment (when expand-condsets runs), there are no kill flags
1301 // in the IR (they have been removed by live range analysis).
1302 // Updating them right before we split is the easiest, because splitting
1303 // adds definitions which would interfere with updating kills afterwards.
1304 std::set<Register> KillUpd;
1305 for (MachineInstr *MI : Condsets) {
1306 for (MachineOperand &Op : MI->operands()) {
1307 if (Op.isReg() && Op.isUse()) {
1308 if (!CoalUpd.count(Op.getReg()))
1309 KillUpd.insert(Op.getReg());
1310 }
1311 }
1312 }
1313 updateLiveness(KillUpd, false, true, false);
1314 LLVM_DEBUG(
1315 LIS->print(dbgs() << "After coalescing\n", MF.getFunction().getParent()));
1316
1317 // First, simply split all muxes into a pair of conditional transfers
1318 // and update the live intervals to reflect the new arrangement. The
1319 // goal is to update the kill flags, since predication will rely on
1320 // them.
1321 for (MachineInstr *MI : Condsets)
1322 Changed |= split(*MI, PredUpd);
1323 Condsets.clear(); // The contents of Condsets are invalid here anyway.
1324
1325 // Do not update live ranges after splitting. Recalculation of live
1326 // intervals removes kill flags, which were preserved by splitting on
1327 // the source operands of condsets. These kill flags are needed by
1328 // predication, and after splitting they are difficult to recalculate
1329 // (because of predicated defs), so make sure they are left untouched.
1330 // Predication does not use live intervals.
1331 LLVM_DEBUG(
1332 LIS->print(dbgs() << "After splitting\n", MF.getFunction().getParent()));
1333
1334 // Traverse all blocks and collapse predicable instructions feeding
1335 // conditional transfers into predicated instructions.
1336 // Walk over all the instructions again, so we may catch pre-existing
1337 // cases that were not created in the previous step.
1338 for (auto &B : MF)
1339 Changed |= predicateInBlock(B, PredUpd);
1340 LLVM_DEBUG(LIS->print(dbgs() << "After predicating\n",
1341 MF.getFunction().getParent()));
1342
1343 PredUpd.insert(CoalUpd.begin(), CoalUpd.end());
1344 updateLiveness(PredUpd, true, true, true);
1345
1346 if (Changed)
1347 distributeLiveIntervals(PredUpd);
1348
1349 LLVM_DEBUG({
1350 if (Changed)
1351 LIS->print(dbgs() << "After expand-condsets\n",
1352 MF.getFunction().getParent());
1353 });
1354
1355 return Changed;
1356 }
1357
1358 //===----------------------------------------------------------------------===//
1359 // Public Constructor Functions
1360 //===----------------------------------------------------------------------===//
createHexagonExpandCondsets()1361 FunctionPass *llvm::createHexagonExpandCondsets() {
1362 return new HexagonExpandCondsets();
1363 }
1364