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