1
2//===----- HexagonGlobalScheduler.cpp - Global Scheduler ------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9//
10// Basic infrastructure for the global scheduling + Hexagon pull-up pass.
11// Currently run at the very end of code generation for Hexagon, cleans
12// up lost scheduling opportunities. Currently breaks liveness, so no passes
13// that rely on liveness info should run afterwards. Will be fixed in future
14// versions.
15//
16//===----------------------------------------------------------------------===//
17#include "Hexagon.h"
18#include "HexagonGlobalRegion.h"
19#include "HexagonRegisterInfo.h"
20#include "HexagonSubtarget.h"
21#include "HexagonVLIWPacketizer.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/SmallSet.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/Analysis/AliasAnalysis.h"
26#include "llvm/Analysis/ValueTracking.h"
27#include "llvm/CodeGen/DFAPacketizer.h"
28#include "llvm/CodeGen/LiveIntervals.h"
29#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
30#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
31#include "llvm/CodeGen/MachineDominators.h"
32#include "llvm/CodeGen/MachineFrameInfo.h"
33#include "llvm/CodeGen/MachineFunctionPass.h"
34#include "llvm/CodeGen/MachineInstrBuilder.h"
35#include "llvm/CodeGen/MachineLoopInfo.h"
36#include "llvm/CodeGen/MachineRegisterInfo.h"
37#include "llvm/CodeGen/Passes.h"
38#include "llvm/CodeGen/PseudoSourceValue.h"
39#include "llvm/CodeGen/TargetInstrInfo.h"
40#include "llvm/CodeGen/TargetRegisterInfo.h"
41#include "llvm/CodeGen/TargetSchedule.h"
42#include "llvm/InitializePasses.h"
43#include "llvm/MC/MCInstrItineraries.h"
44#include "llvm/Support/CommandLine.h"
45#include "llvm/Support/Compiler.h"
46#include "llvm/Support/Debug.h"
47#include "llvm/Target/TargetMachine.h"
48#include "llvm/Transforms/Utils/BasicBlockUtils.h"
49
50#include <list>
51#include <map>
52
53#define DEBUG_TYPE "global_sched"
54
55using namespace llvm;
56
57STATISTIC(HexagonNumPullUps, "Number of instructions pull-ups");
58STATISTIC(HexagonNumDualJumps, "Number of dual jumps formed");
59
60static cl::opt<bool> DisablePullUp("disable-pull-up", cl::Hidden,
61 cl::desc("Disable Hexagon pull-up pass"));
62
63static cl::opt<bool> EnableSpeculativePullUp(
64 "enable-speculative-pull-up", cl::Hidden,
65 cl::desc("Enable speculation during Hexagon pull-up pass"));
66
67static cl::opt<bool> EnableLocalPullUp(
68 "enable-local-pull-up", cl::Hidden, cl::init(Val: true),
69 cl::desc("Enable same BB pull during Hexagon pull-up pass"));
70
71static cl::opt<bool> AllowSpeculateLoads(
72 "speculate-loads-on-pull-up", cl::Hidden, cl::init(Val: true),
73 cl::desc("Allow speculative loads during Hexagon pull-up pass"));
74
75static cl::opt<bool> AllowCmpBranchLoads(
76 "cmp-branch-loads-pull-up", cl::Hidden, cl::init(Val: true),
77 cl::desc("Allow compare-branch loads during Hexagon pull-up pass"));
78
79static cl::opt<bool> AllowUnlikelyPath("unlikely-path-pull-up", cl::Hidden,
80 cl::init(Val: true),
81 cl::desc("Allow unlikely path pull up"));
82
83static cl::opt<bool>
84 PerformDualJumps("dual-jump-in-pull-up", cl::Hidden, cl::init(Val: true),
85 cl::desc("Perform dual jump formation during pull up"));
86
87static cl::opt<bool> AllowDependentPullUp(
88 "enable-dependent-pull-up", cl::Hidden, cl::init(Val: true),
89 cl::desc("Perform dual jump formation during pull up"));
90
91static cl::opt<bool>
92 AllowBBPeelPullUp("enable-bb-peel-pull-up", cl::Hidden, cl::init(Val: true),
93 cl::desc("Peel a reg copy out of a BBloop"));
94
95static cl::opt<bool> PreventCompoundSeparation(
96 "prevent-compound-separation", cl::Hidden,
97 cl::desc("Do not destroy existing compounds during pull up"));
98
99static cl::opt<bool> PreventDuplexSeparation(
100 "prevent-duplex-separation", cl::Hidden, cl::init(Val: true),
101 cl::desc("Do not destroy existing duplexes during pull up"));
102
103static cl::opt<unsigned> MainCandidateQueueSize("pull-up-main-queue-size",
104 cl::Hidden, cl::init(Val: 8));
105
106static cl::opt<unsigned> SecondaryCandidateQueueSize("pull-up-sec-queue-size",
107 cl::Hidden, cl::init(Val: 2));
108
109static cl::opt<bool> PostPullUpOpt(
110 "post-pull-up-opt", cl::Hidden, cl::init(Val: true),
111 cl::desc("Enable opt. exposed by pull-up e.g., remove redundant jumps"));
112
113static cl::opt<bool> SpeculateNonPredInsn(
114 "speculate-non-pred-insn", cl::Hidden, cl::init(Val: true),
115 cl::desc("Speculate non-predicable instructions in parent BB"));
116
117static cl::opt<bool>
118 DisableCheckBundles("disable-hexagon-check-bundles", cl::Hidden,
119 cl::init(Val: true),
120 cl::desc("Disable Hexagon check bundles pass"));
121
122static cl::opt<bool>
123 WarnOnBundleSize("warn-on-bundle-size", cl::Hidden,
124 cl::desc("Hexagon check bundles and warn on size"));
125
126static cl::opt<bool>
127 ForceNoopHazards("force-noop-hazards", cl::Hidden, cl::init(Val: false),
128 cl::desc("Force noop hazards in scheduler"));
129static cl::opt<bool> OneFloatPerPacket(
130 "single-float-packet", cl::Hidden,
131 cl::desc("Allow only one single floating point instruction in a packet"));
132static cl::opt<bool> OneComplexPerPacket(
133 "single-complex-packet", cl::Hidden,
134 cl::desc("Allow only one complex instruction in a packet"));
135
136namespace llvm {
137FunctionPass *createHexagonGlobalScheduler();
138void initializeHexagonGlobalSchedulerPass(PassRegistry &);
139} // namespace llvm
140
141namespace {
142class HexagonGlobalSchedulerImpl;
143
144class HexagonGlobalScheduler : public MachineFunctionPass {
145public:
146 static char ID;
147 HexagonGlobalScheduler() : MachineFunctionPass(ID) {
148 initializeHexagonGlobalSchedulerPass(*PassRegistry::getPassRegistry());
149 }
150
151 void getAnalysisUsage(AnalysisUsage &AU) const override {
152 AU.addRequiredID(ID&: MachineDominatorsID);
153 AU.addRequired<MachineLoopInfoWrapperPass>();
154 AU.addRequired<AAResultsWrapperPass>();
155 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
156 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
157 AU.addRequired<MachineDominatorTreeWrapperPass>();
158 MachineFunctionPass::getAnalysisUsage(AU);
159 }
160
161 StringRef getPassName() const override { return "Hexagon Global Scheduler"; }
162
163 bool runOnMachineFunction(MachineFunction &Fn) override;
164};
165char HexagonGlobalScheduler::ID = 0;
166
167// Describes a single pull-up candidate.
168class PullUpCandidate {
169 MachineBasicBlock::instr_iterator CandidateLocation;
170 MachineBasicBlock::iterator HomeBundle;
171 bool DependentOp;
172 signed BenefitCost;
173 std::vector<MachineInstr *> Backtrack;
174
175public:
176 PullUpCandidate(MachineBasicBlock::instr_iterator MII) {
177 CandidateLocation = MII;
178 BenefitCost = 0;
179 }
180
181 PullUpCandidate(MachineBasicBlock::instr_iterator MII,
182 MachineBasicBlock::iterator HomeBundle,
183 std::vector<MachineInstr *> &backtrack, bool DependentOp,
184 signed Cost)
185 : CandidateLocation(MII), HomeBundle(HomeBundle),
186 DependentOp(DependentOp), BenefitCost(Cost) {
187 // Copy of the backtrack.
188 Backtrack = backtrack;
189 }
190
191 void populate(MachineBasicBlock::instr_iterator &MII,
192 MachineBasicBlock::iterator &WorkPoint,
193 std::vector<MachineInstr *> &backtrack, bool &dependentOp) {
194 MII = CandidateLocation;
195 WorkPoint = HomeBundle;
196 backtrack = Backtrack;
197 dependentOp = DependentOp;
198 }
199
200 signed getCost() { return BenefitCost; }
201
202 MachineInstr *getCandidate() { return &*CandidateLocation; }
203
204 void dump() {
205 dbgs() << "Cost(" << BenefitCost;
206 dbgs() << ") Dependent(" << DependentOp;
207 dbgs() << ") backtrack size(" << Backtrack.size() << ")\t";
208 CandidateLocation->dump();
209 }
210};
211
212/// PullUpCandidateSorter - A Sort utility for pull-up candidates.
213struct PullUpCandidateSorter {
214 PullUpCandidateSorter() {}
215 bool operator()(PullUpCandidate *LHS, PullUpCandidate *RHS) {
216 return LHS->getCost() > RHS->getCost();
217 }
218};
219
220// Describes a single pull-up opportunity: location to which
221// pull-up is possible with additional information about it.
222// Also contains a list of pull-up candidates for this location.
223class PullUpState {
224 friend class HexagonGlobalSchedulerImpl;
225 // Available opportunity for pull-up.
226 // FAIAP a bundle with an empty slot.
227 MachineBasicBlock::iterator HomeLocation;
228 // Home bundle copy. This is here for speed of iteration.
229 SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> HomeBundle;
230 // Multiple candidates for the Home location.
231 SmallVector<PullUpCandidate *, 8> PullUpCandidates;
232
233 const HexagonInstrInfo *QII;
234
235public:
236 PullUpState(const HexagonInstrInfo *QII) : HomeLocation(NULL), QII(QII) {}
237
238 ~PullUpState() { reset(); }
239
240 void addPullUpCandidate(MachineBasicBlock::instr_iterator MII,
241 MachineBasicBlock::iterator HomeBundle,
242 std::vector<MachineInstr *> &backtrack,
243 bool DependentOp, signed Cost) {
244 LLVM_DEBUG(dbgs() << "\t[addPullUpCandidate]: "; (*MII).dump());
245 PullUpCandidate *PUI =
246 new PullUpCandidate(MII, HomeBundle, backtrack, DependentOp, Cost);
247 PullUpCandidates.push_back(Elt: PUI);
248 }
249
250 void dump() {
251 unsigned element = 0;
252 for (unsigned i = 0; i < HomeBundle.size(); i++) {
253 dbgs() << "[" << element++;
254 dbgs() << "] Home Duplex("
255 << QII->getDuplexCandidateGroup(MI: *HomeBundle[i]);
256 dbgs() << ") Compound (" << QII->getCompoundCandidateGroup(MI: *HomeBundle[i])
257 << ") ";
258 HomeBundle[i]->dump();
259 }
260 dbgs() << "\n";
261 element = 0;
262 for (SmallVector<PullUpCandidate *, 4>::iterator
263 I = PullUpCandidates.begin(),
264 E = PullUpCandidates.end();
265 I != E; ++I) {
266 dbgs() << "[" << element++ << "] Cand: Compound(";
267 dbgs() << QII->getCompoundCandidateGroup(MI: *(*I)->getCandidate()) << ") ";
268 (*I)->dump();
269 }
270 }
271
272 void reset() {
273 HomeLocation = NULL;
274 for (SmallVector<PullUpCandidate *, 4>::iterator
275 I = PullUpCandidates.begin(),
276 E = PullUpCandidates.end();
277 I != E; ++I)
278 delete *I;
279 PullUpCandidates.clear();
280 HomeBundle.clear();
281 }
282
283 void addHomeLocation(MachineBasicBlock::iterator WorkPoint) {
284 reset();
285 HomeLocation = WorkPoint;
286 }
287
288 unsigned haveCandidates() { return PullUpCandidates.size(); }
289};
290
291class HexagonGlobalSchedulerImpl : public HexagonPacketizerList {
292 // List of PullUp regions for this function.
293 std::vector<BasicBlockRegion *> PullUpRegions;
294 // Map of approximate distance for each BB from the
295 // function base.
296 DenseMap<MachineBasicBlock *, unsigned> BlockToInstOffset;
297 // Keep track of multiple pull-up candidates.
298 PullUpState CurrentState;
299 // Empty basic blocks as a result of pull-up.
300 std::vector<MachineBasicBlock *> EmptyBBs;
301 // Save all the Speculated MachineInstr that were moved
302 // FROM MachineBasicBlock because we don't want to have
303 // more than one speculated instructions pulled into one packet.
304 // TODO: This can be removed once we have a use-def dependency chain
305 // for all the instructions in a function.
306 std::map<MachineInstr *, MachineBasicBlock *> SpeculatedIns;
307 // All the regs and their aliases used by an instruction.
308 std::map<MachineInstr *, std::vector<unsigned>> MIUseSet;
309 // All the regs and their aliases defined by an instruction.
310 std::map<MachineInstr *, std::vector<unsigned>> MIDefSet;
311
312 AliasAnalysis *AA;
313 const MachineBranchProbabilityInfo *MBPI;
314 const MachineBlockFrequencyInfo *MBFI;
315 const MachineRegisterInfo *MRI;
316 const MachineFrameInfo &MFI;
317 const HexagonRegisterInfo *QRI;
318 const HexagonInstrInfo *QII;
319 MachineLoopInfo &MLI;
320 MachineDominatorTree &MDT;
321 MachineInstrBuilder Ext;
322 MachineInstrBuilder Nop;
323 const unsigned PacketSize;
324 TargetSchedModel TSchedModel;
325
326public:
327 // Ctor.
328 HexagonGlobalSchedulerImpl(MachineFunction &MF, MachineLoopInfo &MLI,
329 MachineDominatorTree &MDT, AliasAnalysis *AA,
330 const MachineBranchProbabilityInfo *MBPI,
331 const MachineBlockFrequencyInfo *MBFI,
332 const MachineRegisterInfo *MRI,
333 const MachineFrameInfo &MFI,
334 const HexagonRegisterInfo *QRI);
335 HexagonGlobalSchedulerImpl(const HexagonGlobalSchedulerImpl &) = delete;
336 HexagonGlobalSchedulerImpl &
337 operator=(const HexagonGlobalSchedulerImpl &) = delete;
338
339 ~HexagonGlobalSchedulerImpl() {
340 // Free regions.
341 for (std::vector<BasicBlockRegion *>::iterator I = PullUpRegions.begin(),
342 E = PullUpRegions.end();
343 I != E; ++I)
344 delete *I;
345 MF.deleteMachineInstr(MI: Ext);
346 MF.deleteMachineInstr(MI: Nop);
347 }
348
349 // initPacketizerState - initialize some internal flags.
350 void initPacketizerState() override;
351
352 // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
353 bool ignoreInstruction(MachineInstr *MI);
354
355 // isSoloInstruction - return true if instruction MI can not be packetized
356 // with any other instruction, which means that MI itself is a packet.
357 bool isSoloInstruction(const MachineInstr &MI) override;
358
359 // Add MI to packetizer state. Returns false if it cannot fit in the packet.
360 bool incrementalAddToPacket(MachineInstr &MI);
361
362 // formPullUpRegions - Top level call to form regions.
363 bool formPullUpRegions(MachineFunction &Fn);
364
365 // performPullUp - Top level call for pull-up.
366 bool performPullUp();
367
368 // performPullUpCFG - Top level call for pull-up CFG.
369 bool performPullUpCFG(MachineFunction &Fn);
370
371 // performExposedOptimizations -
372 // Look for optimization opportunities after pullup.
373 bool performExposedOptimizations(MachineFunction &Fn);
374
375 // optimizeBranching -
376 // 1. A conditional-jump transfers control to a BB with
377 // jump as the only instruction.
378 // if(p0) jump t1
379 // // ...
380 // t1: jump t2
381 // 2. When a BB with a single conditional jump, jumps to succ-of-succ and
382 // falls-through BB with only jump instruction.
383 // { if(p0) jump t1 }
384 // { jump t2 }
385 // t1: { ... }
386 MachineBasicBlock *optimizeBranches(MachineBasicBlock *MBB,
387 MachineBasicBlock *TBB,
388 MachineInstr *FirstTerm,
389 MachineBasicBlock *FBB);
390
391 // removeRedundantBranches -
392 // 1. Remove jump to the layout successor.
393 // 2. Remove multiple (dual) jump to the same target.
394 bool removeRedundantBranches(MachineBasicBlock *MBB, MachineBasicBlock *TBB,
395 MachineInstr *FirstTerm, MachineBasicBlock *FBB,
396 MachineInstr *SecondTerm);
397
398 // optimizeDualJumps - optimize dual jumps in a packet
399 // For now: Replace dual jump by single jump in case of a fall through.
400 bool optimizeDualJumps(MachineBasicBlock *MBB, MachineBasicBlock *TBB,
401 MachineInstr *FirstTerm, MachineBasicBlock *FBB,
402 MachineInstr *SecondTerm);
403
404 void GenUseDefChain(MachineFunction &Fn);
405
406 // Return region pointer or null if none found.
407 BasicBlockRegion *getRegionForMBB(std::vector<BasicBlockRegion *> &Regions,
408 MachineBasicBlock *MBB);
409
410 // Saves all the used-regs and their aliases in Uses.
411 // Saves all the defined-regs and their aliases in Defs.
412 void MIUseDefSet(MachineInstr *MI, std::vector<unsigned> &Defs,
413 std::vector<unsigned> &Uses);
414
415 // This is a very useful debug utility.
416 unsigned countCompounds(MachineFunction &Fn);
417
418 // Check bundle counts
419 void checkBundleCounts(MachineFunction &Fn);
420
421private:
422 // Get next BB to be included into the region.
423 MachineBasicBlock *getNextPURBB(MachineBasicBlock *MBB, bool SecondBest);
424
425 void setUsedRegs(BitVector &Set, unsigned Reg);
426 bool AliasingRegs(unsigned RegA, unsigned RegB);
427
428 // Test is true if the two MIs cannot be safely reordered.
429 bool ReorderDependencyTest(MachineInstr *MIa, MachineInstr *MIb);
430
431 bool canAddMIToThisPacket(
432 MachineInstr *MI,
433 SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> &Bundle);
434
435 bool pullUpPeelBBLoop(MachineBasicBlock *PredBB, MachineBasicBlock *LoopBB);
436
437 MachineInstr *findBundleAndBranch(MachineBasicBlock *BB,
438 MachineBasicBlock::iterator &Bundle);
439
440 // Does this bundle have any slots left?
441 bool ResourcesAvailableInBundle(BasicBlockRegion *CurrentRegion,
442 MachineBasicBlock::iterator &TargetPacket);
443
444 // Perform the actual move.
445 MachineInstr *MoveAndUpdateLiveness(
446 BasicBlockRegion *CurrentRegion, MachineBasicBlock *HomeBB,
447 MachineInstr *InstrToMove, bool NeedToNewify, unsigned DepReg,
448 bool MovingDependentOp, MachineBasicBlock *OriginBB,
449 MachineInstr *OriginalInstruction, SmallVector<MachineOperand, 4> &Cond,
450 MachineBasicBlock::iterator &SourceLocation,
451 MachineBasicBlock::iterator &TargetPacket,
452 MachineBasicBlock::iterator &NextMI,
453 std::vector<MachineInstr *> &backtrack);
454
455 // Updates incremental kill patterns along the backtrack.
456 void updateKillAlongThePath(MachineBasicBlock *HomeBB,
457 MachineBasicBlock *OriginBB,
458 MachineBasicBlock::instr_iterator &Head,
459 MachineBasicBlock::instr_iterator &Tail,
460 MachineBasicBlock::iterator &SourcePacket,
461 MachineBasicBlock::iterator &TargetPacket,
462 std::vector<MachineInstr *> &backtrack);
463
464 // Gather list of pull-up candidates.
465 bool findPullUpCandidates(MachineBasicBlock::iterator &WorkPoint,
466 MachineBasicBlock::iterator &FromHere,
467 std::vector<MachineInstr *> &backtrack,
468 unsigned MaxCandidates);
469
470 // See if the instruction could be pulled up.
471 bool tryMultipleInstructions(
472 MachineBasicBlock::iterator &RetVal, /* output parameter */
473 std::vector<BasicBlockRegion *>::iterator &CurrentRegion,
474 MachineBasicBlock::iterator &NextMI,
475 MachineBasicBlock::iterator &ToThisBBEnd,
476 MachineBasicBlock::iterator &FromThisBBEnd, bool PathInRegion = true);
477
478 // Try to move MI into existing bundle.
479 bool MoveMItoBundle(BasicBlockRegion *CurrentRegion,
480 MachineBasicBlock::instr_iterator &InstrToMove,
481 MachineBasicBlock::iterator &NextMI,
482 MachineBasicBlock::iterator &TargetPacket,
483 MachineBasicBlock::iterator &SourceLocation,
484 std::vector<MachineInstr *> &backtrack,
485 bool MovingDependentOp, bool PathInRegion);
486
487 // Insert temporary MI copy into MBB.
488 MachineBasicBlock::instr_iterator
489 insertTempCopy(MachineBasicBlock *MBB,
490 MachineBasicBlock::iterator &TargetPacket, MachineInstr *MI,
491 bool DeleteOldCopy);
492
493 MachineBasicBlock::instr_iterator
494 findInsertPositionInBundle(MachineBasicBlock::iterator &Bundle,
495 MachineInstr *MI, bool &LastInBundle);
496
497 bool NeedToNewify(MachineBasicBlock::instr_iterator NewMI, unsigned *DepReg,
498 MachineInstr *TargetPacket);
499
500 bool CanNewifiedBeUsedInBundle(MachineBasicBlock::instr_iterator NewMI,
501 unsigned DepReg, MachineInstr *TargetPacket);
502
503 void addInstructionToExistingBundle(MachineBasicBlock *HomeBB,
504 MachineBasicBlock::instr_iterator &Head,
505 MachineBasicBlock::instr_iterator &Tail,
506 MachineBasicBlock::instr_iterator &NewMI,
507 MachineBasicBlock::iterator &TargetPacket,
508 MachineBasicBlock::iterator &NextMI,
509 std::vector<MachineInstr *> &backtrack);
510
511 void removeInstructionFromExistingBundle(
512 MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
513 MachineBasicBlock::instr_iterator &Tail,
514 MachineBasicBlock::iterator &SourceLocation,
515 MachineBasicBlock::iterator &NextMI, bool MovingDependentOp,
516 std::vector<MachineInstr *> &backtrack);
517
518 // Check for conditional register operaton.
519 bool MIsCondAssign(MachineInstr *BMI, MachineInstr *MI,
520 SmallVector<unsigned, 4> &Defs);
521
522 // Test all the conditions required for instruction to be
523 // speculative. These are just required conditions, cost
524 // or benefit should be computed elsewhere.
525 bool canMIBeSpeculated(MachineInstr *MI, MachineBasicBlock *ToBB,
526 MachineBasicBlock *FromBB,
527 std::vector<MachineInstr *> &backtrack);
528
529 // See if this branch target belongs to the current region.
530 bool isBranchWithinRegion(BasicBlockRegion *CurrentRegion, MachineInstr *MI);
531
532 // A collection of low level utilities.
533 bool MIsAreDependent(MachineInstr *MIa, MachineInstr *MIb);
534 bool MIsHaveTrueDependency(MachineInstr *MIa, MachineInstr *MIb);
535 bool canReorderMIs(MachineInstr *MIa, MachineInstr *MIb);
536 bool canCauseStall(MachineInstr *MI, MachineInstr *MJ);
537 bool canThisMIBeMoved(MachineInstr *MI,
538 MachineBasicBlock::iterator &WorkPoint,
539 bool &MovingDependentOp, int &Cost);
540 bool MIisDualJumpCandidate(MachineInstr *MI,
541 MachineBasicBlock::iterator &WorkPoint);
542 bool DemoteToDotOld(MachineInstr *MI);
543 bool isNewifiable(MachineBasicBlock::instr_iterator MII, unsigned DepReg,
544 MachineInstr *TargetPacket);
545 bool IsNewifyStore(MachineInstr *MI);
546 bool isJumpOutOfRange(MachineInstr *MI);
547 bool IsDualJumpFirstCandidate(MachineInstr *MI);
548 bool IsDualJumpFirstCandidate(MachineBasicBlock *MBB);
549 bool IsDualJumpFirstCandidate(MachineBasicBlock::iterator &TargetPacket);
550 bool IsNotDualJumpFirstCandidate(MachineInstr *MI);
551 bool isJumpOutOfRange(MachineInstr *UnCond, MachineInstr *Cond);
552 bool IsDualJumpSecondCandidate(MachineInstr *MI);
553 bool tryAllocateResourcesForConstExt(MachineInstr *MI, bool UpdateState);
554 bool isCompoundPair(MachineInstr *MIa, MachineInstr *MIb);
555 bool doesMIDefinesPredicate(MachineInstr *MI, SmallVector<unsigned, 4> &Defs);
556 bool AnalyzeBBBranches(MachineBasicBlock *MBB, MachineBasicBlock *&TBB,
557 MachineInstr *&FirstTerm, MachineBasicBlock *&FBB,
558 MachineInstr *&SecondTerm);
559 inline bool multipleBranchesFromToBB(MachineBasicBlock *BB) const;
560};
561} // namespace
562
563INITIALIZE_PASS_BEGIN(HexagonGlobalScheduler, "global-sched",
564 "Hexagon Global Scheduler", false, false)
565INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
566INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
567INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
568INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
569INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
570INITIALIZE_PASS_END(HexagonGlobalScheduler, "global-sched",
571 "Hexagon Global Scheduler", false, false)
572
573/// HexagonGlobalSchedulerImpl Ctor.
574HexagonGlobalSchedulerImpl::HexagonGlobalSchedulerImpl(
575 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
576 AliasAnalysis *AA, const MachineBranchProbabilityInfo *MBPI,
577 const MachineBlockFrequencyInfo *MBFI, const MachineRegisterInfo *MRI,
578 const MachineFrameInfo &MFI, const HexagonRegisterInfo *QRI)
579 : HexagonPacketizerList(MF, MLI, AA, nullptr, false), PullUpRegions(0),
580 CurrentState((const HexagonInstrInfo *)TII), AA(AA), MBPI(MBPI),
581 MBFI(MBFI), MRI(MRI), MFI(MFI), QRI(QRI), MLI(MLI), MDT(MDT),
582 PacketSize(MF.getSubtarget().getSchedModel().IssueWidth) {
583 QII = (const HexagonInstrInfo *)TII;
584 Ext = BuildMI(MF, MIMD: DebugLoc(), MCID: QII->get(Opcode: Hexagon::A4_ext));
585 Nop = BuildMI(MF, MIMD: DebugLoc(), MCID: QII->get(Opcode: Hexagon::A2_nop));
586 TSchedModel.init(TSInfo: &MF.getSubtarget());
587}
588
589// Return bundle size without debug instructions.
590static unsigned nonDbgBundleSize(MachineBasicBlock::iterator &TargetPacket) {
591 MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
592 MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
593 unsigned count = 0;
594 for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
595 if (MII->isDebugInstr())
596 continue;
597 count++;
598 }
599 return count;
600}
601
602/// The pass main entry point.
603bool HexagonGlobalScheduler::runOnMachineFunction(MachineFunction &Fn) {
604 auto &HST = Fn.getSubtarget<HexagonSubtarget>();
605 if (DisablePullUp || !HST.usePackets() || skipFunction(F: Fn.getFunction()))
606 return false;
607
608 const MachineRegisterInfo *MRI = &Fn.getRegInfo();
609 const MachineFrameInfo &MFI = Fn.getFrameInfo();
610 const HexagonRegisterInfo *QRI = HST.getRegisterInfo();
611 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
612 MachineDominatorTree &MDT =
613 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
614 const MachineBranchProbabilityInfo *MBPI =
615 &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
616 const MachineBlockFrequencyInfo *MBFI =
617 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
618 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
619
620 // Preserve comounds if Opt Size.
621 const Function &F = Fn.getFunction();
622 if (F.hasOptSize() && PreventCompoundSeparation.getNumOccurrences() == 0)
623 PreventCompoundSeparation = true;
624
625 // Instantiate the Scheduler.
626 HexagonGlobalSchedulerImpl GlobalSchedulerState(Fn, MLI, MDT, AA, MBPI, MBFI,
627 MRI, MFI, QRI);
628
629 // DFA state table should not be empty.
630 assert(GlobalSchedulerState.getResourceTracker() && "Empty DFA table!");
631
632 // Loop over all of the basic blocks.
633 // PullUp regions are basically traces with no side entrances.
634 // Might want to traverse BB by frequency.
635 GlobalSchedulerState.checkBundleCounts(Fn);
636
637 // Pullup does not handle hazards yet.
638 if (!DisablePullUp.getPosition() && ForceNoopHazards)
639 return true;
640
641 LLVM_DEBUG(GlobalSchedulerState.countCompounds(Fn));
642 GlobalSchedulerState.GenUseDefChain(Fn);
643 GlobalSchedulerState.formPullUpRegions(Fn);
644 GlobalSchedulerState.performPullUp();
645 GlobalSchedulerState.performPullUpCFG(Fn);
646 if (PostPullUpOpt) {
647 GlobalSchedulerState.formPullUpRegions(Fn);
648 GlobalSchedulerState.performExposedOptimizations(Fn);
649 }
650 LLVM_DEBUG(GlobalSchedulerState.countCompounds(Fn));
651
652 return true;
653}
654
655/// Allocate resources (i.e. 4 bytes) for constant extender. If succeess, return
656/// true, otherwise, return false.
657bool HexagonGlobalSchedulerImpl::tryAllocateResourcesForConstExt(
658 MachineInstr *MI, bool UpdateState = true) {
659 if (ResourceTracker->canReserveResources(MI&: *Ext)) {
660 // We do not always want to change the state of ResourceTracker.
661 // When we do not want to change it, we need to test for additional
662 // corner cases.
663 if (UpdateState)
664 ResourceTracker->reserveResources(MI&: *Ext);
665 else if (CurrentPacketMIs.size() >= PacketSize - 1)
666 return false;
667 return true;
668 }
669
670 return false;
671}
672
673static bool IsSchedBarrier(const MachineInstr *MI) {
674 return MI->getOpcode() == Hexagon::Y2_barrier;
675}
676
677static bool IsIndirectCall(const MachineInstr *MI) {
678 return MI->getOpcode() == Hexagon::J2_callr;
679}
680
681#ifndef NDEBUG
682static void DumpLinked(MachineInstr *MI) {
683 if (MI->isBundledWithPred())
684 dbgs() << "^";
685 else
686 dbgs() << " ";
687 if (MI->isBundledWithSucc())
688 dbgs() << "v";
689 else
690 dbgs() << " ";
691 MI->dump();
692}
693
694static void DumpPacket(MachineBasicBlock::instr_iterator MII) {
695 if (MII == MachineBasicBlock::instr_iterator()) {
696 dbgs() << "\tNULL\n";
697 return;
698 }
699 MachineInstr *MI = &*MII;
700 MachineBasicBlock *MBB = MI->getParent();
701 // Uninserted instruction.
702 if (!MBB) {
703 dbgs() << "\tUnattached: ";
704 DumpLinked(MI);
705 return;
706 }
707 dbgs() << "\t";
708 DumpLinked(MI);
709 if (MI->isBundle()) {
710 MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
711 for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
712 ++MII) {
713 dbgs() << "\t\t*";
714 DumpLinked(&*MII);
715 }
716 }
717}
718
719static void DumpPacket(MachineBasicBlock::instr_iterator MII,
720 MachineBasicBlock::instr_iterator BBEnd) {
721 if (MII == BBEnd) {
722 dbgs() << "\tBBEnd\n";
723 return;
724 }
725
726 DumpPacket(MII);
727}
728#endif
729
730static bool isBranch(MachineInstr *MI) {
731 if (MI->isBundle()) {
732 MachineBasicBlock::instr_iterator MII = MI->getIterator();
733 MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
734 for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
735 ++MII) {
736 if (MII->isBranch())
737 return true;
738 }
739 } else
740 return MI->isBranch();
741 return false;
742}
743
744/// Any of those must not be first dual jump. Everything else is OK.
745bool HexagonGlobalSchedulerImpl::IsNotDualJumpFirstCandidate(MachineInstr *MI) {
746 if (MI->isCall() || (MI->isBranch() && !QII->isPredicated(MI: *MI)) ||
747 MI->isReturn() || QII->isEndLoopN(Opcode: MI->getOpcode()))
748 return true;
749 return false;
750}
751
752/// These four functions clearly belong in HexagonInstrInfo.cpp.
753/// Is this MI could be first dual jump instruction?
754bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(MachineInstr *MI) {
755 if (!PerformDualJumps)
756 return false;
757 if (MI->isBranch() && QII->isPredicated(MI: *MI) && !QII->isNewValueJump(MI: *MI) &&
758 !MI->isIndirectBranch() && !QII->isEndLoopN(Opcode: MI->getOpcode()))
759 return true;
760 // Missing loopN here, but not sure if there will be any benefit from it.
761 return false;
762}
763
764/// This version covers the whole packet.
765bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(
766 MachineBasicBlock::iterator &TargetPacket) {
767 if (!PerformDualJumps)
768 return false;
769 MachineInstr *MI = &*TargetPacket;
770
771 if (MI->isBundle()) {
772 // If this is a bundle, it must be the last bundle in BB.
773 if (&(*MI->getParent()->rbegin()) != MI)
774 return false;
775
776 MachineBasicBlock::instr_iterator MII = MI->getIterator();
777 MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
778 // If there is a control flow op in this packet, this is the case
779 // we look for, even if they are dependent on other members.
780 for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
781 ++MII)
782 if (IsNotDualJumpFirstCandidate(MI: &*MII))
783 return false;
784 } else
785 return IsDualJumpFirstCandidate(MI);
786
787 return true;
788}
789
790/// This version cover whole BB. There could be a BB
791/// with no control flow in it. In this case we can still pull-up a jump
792/// into it. Negative proof.
793bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(
794 MachineBasicBlock *MBB) {
795 if (!PerformDualJumps)
796 return false;
797
798 for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
799 MBBEnd = MBB->instr_end();
800 MII != MBBEnd; ++MII) {
801 MachineInstr *MI = &*MII;
802 if (MI->isDebugInstr())
803 continue;
804 if (!MI->isBundle() && IsNotDualJumpFirstCandidate(MI))
805 return false;
806 }
807 return true;
808}
809
810/// Is this MI could be second dual jump instruction?
811bool HexagonGlobalSchedulerImpl::IsDualJumpSecondCandidate(MachineInstr *MI) {
812 if (!PerformDualJumps)
813 return false;
814 if ((MI->isBranch() && !QII->isNewValueJump(MI: *MI) && !MI->isIndirectBranch() &&
815 !QII->isEndLoopN(Opcode: MI->getOpcode())) ||
816 (MI->isCall() && !IsIndirectCall(MI)))
817 return true;
818 return false;
819}
820
821// Since we have no exact knowledge of code layout,
822// allow some safety buffer for jump target.
823// This is measured in bytes.
824static const unsigned SafetyBuffer = 200;
825
826static MachineBasicBlock::instr_iterator
827getHexagonFirstInstrTerminator(MachineBasicBlock *MBB) {
828 MachineBasicBlock::instr_iterator MIB = MBB->instr_begin();
829 MachineBasicBlock::instr_iterator MIE = MBB->instr_end();
830 MachineBasicBlock::instr_iterator MII = MIB;
831 while (MII != MIE) {
832 if (!MII->isBundle() && MII->isTerminator())
833 return MII;
834 ++MII;
835 }
836 return MIE;
837}
838
839/// Check if a given instruction is:
840/// - a jump to a distant target
841/// - that exceeds its immediate range
842/// If both conditions are true, it requires constant extension.
843bool HexagonGlobalSchedulerImpl::isJumpOutOfRange(MachineInstr *MI) {
844 if (!MI || !MI->isBranch())
845 return false;
846 MachineBasicBlock *MBB = MI->getParent();
847 auto FirstTerm = getHexagonFirstInstrTerminator(MBB);
848 if (FirstTerm == MBB->instr_end())
849 return false;
850
851 unsigned InstOffset = BlockToInstOffset[MBB];
852 unsigned Distance = 0;
853 MachineBasicBlock::instr_iterator FTMII = FirstTerm;
854
855 // To save time, estimate exact position of a branch instruction
856 // as one at the end of the MBB.
857 // Number of instructions times typical instruction size.
858 InstOffset += (QII->nonDbgBBSize(BB: MBB) * HEXAGON_INSTR_SIZE);
859
860 MachineBasicBlock *TBB = NULL, *FBB = NULL;
861 SmallVector<MachineOperand, 4> Cond;
862
863 // Try to analyze this branch.
864 if (QII->analyzeBranch(MBB&: *MBB, TBB, FBB, Cond, AllowModify: false)) {
865 // Could not analyze it. See if this is something we can recognize.
866 // If it is a NVJ, it should always have its target in
867 // a fixed location.
868 if (QII->isNewValueJump(MI: *FirstTerm))
869 TBB = FirstTerm->getOperand(i: QII->getCExtOpNum(MI: *FirstTerm)).getMBB();
870 }
871 if (TBB && (MI == &*FirstTerm)) {
872 Distance =
873 (unsigned)std::abs(x: (long long)InstOffset - BlockToInstOffset[TBB]) +
874 SafetyBuffer;
875 LLVM_DEBUG(dbgs() << "\tFirst term offset(" << Distance << "): ";
876 FirstTerm->dump());
877 return !QII->isJumpWithinBranchRange(MI: *FirstTerm, offset: Distance);
878 }
879 if (FBB) {
880 // Look for second terminator.
881 FTMII++;
882 MachineInstr *SecondTerm = &*FTMII;
883 assert(FTMII != MBB->instr_end() &&
884 (SecondTerm->isBranch() || SecondTerm->isCall()) &&
885 "Bad second terminator");
886 if (MI != SecondTerm)
887 return false;
888 // Analyze the second branch in the BB.
889 Distance =
890 (unsigned)std::abs(x: (long long)InstOffset - BlockToInstOffset[FBB]) +
891 SafetyBuffer;
892 LLVM_DEBUG(dbgs() << "\tSecond term offset(" << Distance << "): ";
893 FirstTerm->dump());
894 return !QII->isJumpWithinBranchRange(MI: *SecondTerm, offset: Distance);
895 }
896 return false;
897}
898
899/// Returns true if an instruction can be promoted to .new predicate
900/// or new-value store.
901/// Performs implicit version checking.
902bool HexagonGlobalSchedulerImpl::isNewifiable(
903 MachineBasicBlock::instr_iterator MII, unsigned DepReg,
904 MachineInstr *TargetPacket) {
905 MachineInstr *MI = &*MII;
906 if (QII->isDotNewInst(MI: *MI) ||
907 !CanNewifiedBeUsedInBundle(NewMI: MII, DepReg, TargetPacket))
908 return false;
909 return (QII->isPredicated(MI: *MI) && QII->getDotNewPredOp(MI: *MI, MBPI: nullptr) > 0) ||
910 QII->mayBeNewStore(MI: *MI);
911}
912
913bool HexagonGlobalSchedulerImpl::DemoteToDotOld(MachineInstr *MI) {
914 int NewOpcode = QII->getDotOldOp(MI: *MI);
915 MI->setDesc(QII->get(Opcode: NewOpcode));
916 return true;
917}
918
919// initPacketizerState - Initialize packetizer flags
920void HexagonGlobalSchedulerImpl::initPacketizerState(void) {
921 CurrentPacketMIs.clear();
922 return;
923}
924
925// ignorePseudoInstruction - Ignore bundling of pseudo instructions.
926bool HexagonGlobalSchedulerImpl::ignoreInstruction(MachineInstr *MI) {
927 if (MI->isDebugInstr())
928 return true;
929
930 // We must print out inline assembly
931 if (MI->isInlineAsm())
932 return false;
933
934 // We check if MI has any functional units mapped to it.
935 // If it doesn't, we ignore the instruction.
936 const MCInstrDesc &TID = MI->getDesc();
937 unsigned SchedClass = TID.getSchedClass();
938 const InstrStage *IS =
939 ResourceTracker->getInstrItins()->beginStage(ItinClassIndx: SchedClass);
940 unsigned FuncUnits = IS->getUnits();
941 return !FuncUnits;
942}
943
944// isSoloInstruction: - Returns true for instructions that must be
945// scheduled in their own packet.
946bool HexagonGlobalSchedulerImpl::isSoloInstruction(const MachineInstr &MI) {
947 if (MI.isInlineAsm())
948 return true;
949
950 if (MI.isEHLabel())
951 return true;
952
953 // From Hexagon V4 Programmer's Reference Manual 3.4.4 Grouping constraints:
954 // trap, pause, barrier, icinva, isync, and syncht are solo instructions.
955 // They must not be grouped with other instructions in a packet.
956 if (IsSchedBarrier(MI: &MI))
957 return true;
958
959 if (MI.getOpcode() == Hexagon::A2_nop)
960 return true;
961
962 return false;
963}
964
965/// Return region ptr or null if non found.
966BasicBlockRegion *HexagonGlobalSchedulerImpl::getRegionForMBB(
967 std::vector<BasicBlockRegion *> &Regions, MachineBasicBlock *MBB) {
968 for (std::vector<BasicBlockRegion *>::iterator I = Regions.begin(),
969 E = Regions.end();
970 I != E; ++I) {
971 if ((*I)->findMBB(MBB))
972 return *I;
973 }
974 return NULL;
975}
976
977/// Select best candidate to form regions.
978static inline bool selectBestBB(BlockFrequency &BBaFreq, unsigned BBaSize,
979 BlockFrequency &BBbFreq, unsigned BBbSize) {
980 if (BBaFreq.getFrequency() > BBbFreq.getFrequency())
981 return true;
982 // TODO: This needs fine tuning.
983 // if (BBaSize < BBbSize)
984 // return true;
985 if (BBaFreq.getFrequency() == BBbFreq.getFrequency())
986 return true;
987 return false;
988}
989
990/// Returns BB pointer if one of MBB successors should be added to the
991/// current PullUp Region, NULL otherwise.
992/// If SecondBest is defined, get next one after Best match.
993/// Most of the time, since we practically always have only two successors,
994/// this is "the other" BB successor which still matches original
995/// selection criterion.
996MachineBasicBlock *
997HexagonGlobalSchedulerImpl::getNextPURBB(MachineBasicBlock *MBB,
998 bool SecondBest = false) {
999 if (!MBB)
1000 return NULL;
1001
1002 BlockFrequency BestBlockFreq = BlockFrequency(0);
1003 unsigned BestBlockSize = 0;
1004 MachineBasicBlock *BestBB = NULL;
1005 MachineBasicBlock *SecondBestBB = NULL;
1006
1007 // Catch single BB loops.
1008 for (MachineBasicBlock *Succ : MBB->successors())
1009 if (Succ == MBB)
1010 return NULL;
1011
1012 // Iterate through successors to MBB.
1013 for (MachineBasicBlock *Succ : MBB->successors()) {
1014 BlockFrequency BlockFreq = MBFI->getBlockFreq(MBB: Succ);
1015
1016 LLVM_DEBUG(dbgs() << "\tsucc BB(" << Succ->getNumber() << ") freq("
1017 << BlockFreq.getFrequency() << ")");
1018
1019 if (!SecondBest && getRegionForMBB(Regions&: PullUpRegions, MBB: Succ))
1020 continue;
1021
1022 // If there is more then one predecessor to this block, do not include it.
1023 // It means there is a side entrance to it.
1024 if (Succ->pred_size() > 1)
1025 continue;
1026
1027 // If this block is a target of an indirect branch, it should
1028 // also not be included.
1029 if (Succ->isEHPad() || Succ->hasAddressTaken())
1030 continue;
1031
1032 // Get BB edge frequency.
1033 BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(Src: MBB, Dst: Succ);
1034 LLVM_DEBUG(dbgs() << "\tedge with freq(" << EdgeFreq.getFrequency()
1035 << ")\n");
1036
1037 if (selectBestBB(BBaFreq&: EdgeFreq, BBaSize: QII->nonDbgBBSize(BB: Succ), BBbFreq&: BestBlockFreq,
1038 BBbSize: BestBlockSize)) {
1039 BestBlockFreq = EdgeFreq;
1040 BestBlockSize = QII->nonDbgBBSize(BB: Succ);
1041 SecondBestBB = BestBB;
1042 BestBB = Succ;
1043 } else if (!SecondBestBB) {
1044 SecondBestBB = Succ;
1045 }
1046 }
1047 if (SecondBest)
1048 return SecondBestBB;
1049 else
1050 return BestBB;
1051}
1052
1053/// Form region to perform pull-up.
1054bool HexagonGlobalSchedulerImpl::formPullUpRegions(MachineFunction &Fn) {
1055 const Function &F = Fn.getFunction();
1056 // Check for single-block functions and skip them.
1057 if (std::next(x: F.begin()) == F.end())
1058 return false;
1059
1060 // Compute map for BB distances.
1061 // Offset of the current instruction from the start.
1062 unsigned InstOffset = 0;
1063
1064 LLVM_DEBUG(dbgs() << "****** Form PullUpRegions **************\n");
1065 // Loop over all basic blocks.
1066 // PullUp regions are basically traces with no side entrances.
1067 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
1068 ++MBB) {
1069 if (MBB->getAlignment() > llvm::Align(1)) {
1070 // Although we don't know the exact layout of the final code, we need
1071 // to account for alignment padding somehow. This heuristic pads each
1072 // aligned basic block according to the alignment value.
1073 int ByteAlign = MBB->getAlignment().value() - 1;
1074 InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
1075 }
1076 // Remember BB layout offset.
1077 BlockToInstOffset[&*MBB] = InstOffset;
1078 for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
1079 MIE = MBB->instr_end();
1080 MII != MIE; ++MII)
1081 if (!MII->isBundle())
1082 InstOffset += QII->getSize(MI: *MII);
1083
1084 // If this BB is already in a region, move on.
1085 if (getRegionForMBB(Regions&: PullUpRegions, MBB: &*MBB))
1086 continue;
1087
1088 LLVM_DEBUG(dbgs() << "\nRoot BB(" << MBB->getNumber() << ") name("
1089 << MBB->getName() << ") size(" << QII->nonDbgBBSize(&*MBB)
1090 << ") freq(" << printBlockFreq(*MBFI, *MBB)
1091 << ") pred_size(" << MBB->pred_size() << ") in_func("
1092 << MBB->getParent()->getFunction().getName() << ")\n");
1093
1094 BasicBlockRegion *PUR = new BasicBlockRegion(TII, QRI, &*MBB);
1095 PullUpRegions.push_back(x: PUR);
1096
1097 for (MachineBasicBlock *MBBR = getNextPURBB(MBB: &*MBB); MBBR;
1098 MBBR = getNextPURBB(MBB: MBBR)) {
1099 LLVM_DEBUG(dbgs() << "Add BB(" << MBBR->getNumber() << ") name("
1100 << MBBR->getName() << ") size("
1101 << QII->nonDbgBBSize(MBBR) << ") freq("
1102 << printBlockFreq(*MBFI, *MBBR) << ") in_func("
1103 << MBBR->getParent()->getFunction().getName() << ")\n");
1104 PUR->addBBtoRegion(MBB: MBBR);
1105 }
1106 }
1107 return true;
1108}
1109
1110/// Return true if MI is an instruction we are unable to reason about
1111/// (like something with unmodeled memory side effects).
1112static inline bool isGlobalMemoryObject(MachineInstr *MI) {
1113 if (MI->hasUnmodeledSideEffects() || MI->hasOrderedMemoryRef() ||
1114 MI->isCall() ||
1115 (MI->getOpcode() == Hexagon::J2_jump && !MI->getOperand(i: 0).isMBB()))
1116 return true;
1117 return false;
1118}
1119
1120// This MI might have either incomplete info, or known to be unsafe
1121// to deal with (i.e. volatile object).
1122static inline bool isUnsafeMemoryObject(MachineInstr *MI) {
1123 if (!MI || MI->memoperands_empty())
1124 return true;
1125
1126 // We purposefully do no check for hasOneMemOperand() here
1127 // in hope to trigger an assert downstream in order to
1128 // finish implementation.
1129 if ((*MI->memoperands_begin())->isVolatile() || MI->hasUnmodeledSideEffects())
1130 return true;
1131
1132 if (!(*MI->memoperands_begin())->getValue())
1133 return true;
1134
1135 return false;
1136}
1137
1138/// This returns true if the two MIs could be memory dependent.
1139static bool MIsNeedChainEdge(AliasAnalysis *AA, const TargetInstrInfo *TII,
1140 MachineInstr *MIa, MachineInstr *MIb) {
1141 // Cover a trivial case - no edge is need to itself.
1142 if (MIa == MIb)
1143 return false;
1144
1145 if (TII->areMemAccessesTriviallyDisjoint(MIa: *MIa, MIb: *MIb))
1146 return false;
1147
1148 if (isUnsafeMemoryObject(MI: MIa) || isUnsafeMemoryObject(MI: MIb))
1149 return true;
1150
1151 // If we are dealing with two "normal" loads, we do not need an edge
1152 // between them - they could be reordered.
1153 if (!MIa->mayStore() && !MIb->mayStore())
1154 return false;
1155
1156 // To this point analysis is generic. From here on we do need AA.
1157 if (!AA)
1158 return true;
1159
1160 MachineMemOperand *MMOa = *MIa->memoperands_begin();
1161 MachineMemOperand *MMOb = *MIb->memoperands_begin();
1162
1163 // TODO: Need to handle multiple memory operands.
1164 // if either instruction has more than one memory operand, punt.
1165 if (!(MIa->hasOneMemOperand() && MIb->hasOneMemOperand()))
1166 return true;
1167
1168 if (!MMOa->getSize().hasValue() || !MMOb->getSize().hasValue())
1169 return true;
1170
1171 assert((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset");
1172 assert((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset");
1173 assert((MMOa->getSize().hasValue() && MMOb->getSize().hasValue()) &&
1174 "Size 0 memory access");
1175
1176 // If the base address of the two memoperands is the same. For instance,
1177 // x and x+4, then we can easily reason about them using the offset and size
1178 // of access.
1179 if (MMOa->getValue() == MMOb->getValue()) {
1180 if (MMOa->getOffset() > MMOb->getOffset()) {
1181 uint64_t offDiff = MMOa->getOffset() - MMOb->getOffset();
1182 return !(MMOb->getSize().getValue() <= offDiff);
1183 } else if (MMOa->getOffset() < MMOb->getOffset()) {
1184 uint64_t offDiff = MMOb->getOffset() - MMOa->getOffset();
1185 return !(MMOa->getSize().getValue() <= offDiff);
1186 }
1187 // MMOa->getOffset() == MMOb->getOffset()
1188 return true;
1189 }
1190
1191 int64_t MinOffset = std::min(a: MMOa->getOffset(), b: MMOb->getOffset());
1192 int64_t Overlapa = MMOa->getSize().getValue() + MMOa->getOffset() - MinOffset;
1193 int64_t Overlapb = MMOb->getSize().getValue() + MMOb->getOffset() - MinOffset;
1194
1195 AliasResult AAResult =
1196 AA->alias(LocA: MemoryLocation(MMOa->getValue(), Overlapa, MMOa->getAAInfo()),
1197 LocB: MemoryLocation(MMOb->getValue(), Overlapb, MMOb->getAAInfo()));
1198
1199 return (AAResult != AliasResult::NoAlias);
1200}
1201
1202/// Gather register def/uses from MI.
1203/// This treats possible (predicated) defs
1204/// as actually happening ones (conservatively).
1205static inline void parseOperands(MachineInstr *MI,
1206 SmallVector<unsigned, 4> &Defs,
1207 SmallVector<unsigned, 8> &Uses) {
1208 Defs.clear();
1209 Uses.clear();
1210
1211 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1212 const MachineOperand &MO = MI->getOperand(i);
1213
1214 if (MO.isReg()) {
1215 unsigned Reg = MO.getReg();
1216 if (!Reg)
1217 continue;
1218 assert(Register::isPhysicalRegister(Reg));
1219 if (MO.isUse())
1220 Uses.push_back(Elt: MO.getReg());
1221 if (MO.isDef())
1222 Defs.push_back(Elt: MO.getReg());
1223 } else if (MO.isRegMask()) {
1224 for (unsigned R = 1, NR = Hexagon::NUM_TARGET_REGS; R != NR; ++R)
1225 if (MO.clobbersPhysReg(PhysReg: R))
1226 Defs.push_back(Elt: R);
1227 }
1228 }
1229}
1230
1231void HexagonGlobalSchedulerImpl::MIUseDefSet(MachineInstr *MI,
1232 std::vector<unsigned> &Defs,
1233 std::vector<unsigned> &Uses) {
1234 Defs.clear();
1235 Uses.clear();
1236 assert(!MI->isBundle() && "Cannot parse regs of a bundle.");
1237 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1238 const MachineOperand &MO = MI->getOperand(i);
1239
1240 if (MO.isReg()) {
1241 unsigned Reg = MO.getReg();
1242 if (!Reg)
1243 continue;
1244 assert(Register::isPhysicalRegister(Reg));
1245 std::vector<unsigned> &Refs = MO.isUse() ? Uses : Defs;
1246 for (MCRegAliasIterator AI(MO.getReg(), QRI, true); AI.isValid(); ++AI)
1247 Refs.push_back(x: *AI);
1248 } else if (MO.isRegMask()) {
1249 for (unsigned R = 1, NR = Hexagon::NUM_TARGET_REGS; R != NR; ++R)
1250 if (MO.clobbersPhysReg(PhysReg: R))
1251 Defs.push_back(x: R);
1252 }
1253 }
1254}
1255
1256/// Some apparent dependencies are not actually restricting us since there
1257/// is a delay between assignment and actual usage, like in case of a call.
1258/// There could be more cases here, but this one seems the most obvious.
1259static bool isDelayedUseException(MachineInstr *MIa, MachineInstr *MIb) {
1260 if (MIa->isCall() && !MIb->isCall())
1261 return true;
1262 if (!MIa->isCall() && MIb->isCall())
1263 return true;
1264 return false;
1265}
1266
1267/// This is a check for resources availability and dependency
1268/// for an MI being tried for an existing bundle.
1269/// This is needed because we can:
1270/// - save time by filtering out trivial cases
1271/// - we want to reuse infrastructure that does not really knows
1272/// how to deal with parallel semantics of a bundle that already
1273/// exists. For instance, the following case:
1274/// SI %R6<def> = L2_ploadrif_io %P0<kill>, %R7, 4;
1275/// SJ %R6<def> = A2_tfr %R0;
1276/// will be happily allowed by isLegalToPacketizeTogether since in serial
1277/// semantics it never happens, and even if it does, it is legal. Not so
1278/// for when we __speculatively__ trying and MI for a bundle.
1279///
1280/// Note: This is not equivalent to MIsAreDependent().
1281/// MIsAreDependent only understands serial semantics.
1282/// These are OK to packetize together:
1283/// %R0<def> = L2_loadri_io %R18, 76; mem:LD4[%sunkaddr226](tbaa=!"int")
1284/// %R2<def> = ASL %R0<kill>, 3; flags: Inside bundle
1285///
1286bool HexagonGlobalSchedulerImpl::canAddMIToThisPacket(
1287 MachineInstr *MI,
1288 SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> &Bundle) {
1289 if (!MI)
1290 return false;
1291 LLVM_DEBUG(dbgs() << "\n\t[canAddMIToThisPacket]: "; MI->dump());
1292
1293 // Const extenders need custom resource checking...
1294 // Should be OK if we can update the check everywhere.
1295 if ((QII->isConstExtended(MI: *MI) || QII->isExtended(MI: *MI) ||
1296 isJumpOutOfRange(MI)) &&
1297 !tryAllocateResourcesForConstExt(MI, UpdateState: false))
1298 return false;
1299
1300 // Ask DFA if machine resource is available for MI.
1301 if (!ResourceTracker->canReserveResources(MI&: *MI) || !shouldAddToPacket(MI: *MI)) {
1302 LLVM_DEBUG(dbgs() << "\tNo DFA resources.\n");
1303 return false;
1304 }
1305
1306 SmallVector<unsigned, 4> BundleDefs;
1307 SmallVector<unsigned, 8> BundleUses;
1308 SmallVector<unsigned, 4> Defs;
1309 SmallVector<unsigned, 8> Uses;
1310 MachineInstr *FirstCompound = NULL, *SecondCompound = NULL;
1311 MachineInstr *FirstDuplex = NULL, *SecondDuplex = NULL;
1312
1313 parseOperands(MI, Defs, Uses);
1314 for (SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE>::iterator
1315 BI = Bundle.begin(),
1316 BE = Bundle.end();
1317 BI != BE; ++BI) {
1318 BundleDefs.clear();
1319 BundleUses.clear();
1320 parseOperands(MI: *BI, Defs&: BundleDefs, Uses&: BundleUses);
1321
1322 MachineInstr *Inst1 = *BI;
1323 MachineInstr *Inst2 = MI;
1324
1325 if (Inst1->getParent() && OneFloatPerPacket && QII->isFloat(MI: *Inst1) &&
1326 QII->isFloat(MI: *Inst2))
1327 return false;
1328
1329 if (Inst1->getParent() && OneComplexPerPacket && QII->isComplex(MI: *Inst1) &&
1330 QII->isComplex(MI: *Inst2))
1331 return false;
1332
1333 if (PreventCompoundSeparation)
1334 if (QII->getCompoundCandidateGroup(MI: **BI)) {
1335 if (!FirstCompound)
1336 FirstCompound = *BI;
1337 else {
1338 SecondCompound = *BI;
1339 if (isCompoundPair(MIa: FirstCompound, MIb: SecondCompound)) {
1340 if (MI->mayLoad() || MI->mayStore()) {
1341 LLVM_DEBUG(dbgs() << "\tPrevent compound destruction.\n");
1342 return false;
1343 }
1344 }
1345 }
1346 }
1347 if (PreventDuplexSeparation)
1348 if (QII->getDuplexCandidateGroup(MI: **BI)) {
1349 if (!FirstDuplex)
1350 FirstDuplex = *BI;
1351 else {
1352 SecondDuplex = *BI;
1353 if (QII->isDuplexPair(MIa: *FirstDuplex, MIb: *SecondDuplex)) {
1354 if (MI->mayLoad() || MI->mayStore()) {
1355 LLVM_DEBUG(dbgs() << "\tPrevent duplex destruction.\n");
1356 return false;
1357 }
1358 }
1359 }
1360 }
1361
1362 for (unsigned i = 0; i < Defs.size(); i++) {
1363 // Check for multiple definitions in the same packet.
1364 for (unsigned j = 0; j < BundleDefs.size(); j++)
1365 // Multiple defs in the same packet.
1366 // Calls are OK here.
1367 // Also if we have multiple defs of PC, this simply means we are
1368 // dealing with dual jumps.
1369 if (AliasingRegs(RegA: Defs[i], RegB: BundleDefs[j]) &&
1370 !isDelayedUseException(MIa: MI, MIb: *BI) &&
1371 !(IsDualJumpFirstCandidate(MI: *BI) && IsDualJumpSecondCandidate(MI))) {
1372 LLVM_DEBUG(dbgs() << "\tMultiple defs.\n\t"; MI->dump();
1373 dbgs() << "\t"; (*BI)->dump());
1374 return false;
1375 }
1376
1377 // See if we are creating a swap case as we go, and disallow
1378 // it for now.
1379 // Also, this is not OK:
1380 // if (!p0) r7 = r5
1381 // if (!p0) r5 = #0
1382 // But this is fine:
1383 // if (!p0) r7 = r5
1384 // if (p0) r5 = #0
1385 // Aslo - this is not a swap, but an opportunity to newify:
1386 // %P1<def> = C2_cmpeqi %R0, 0; flags:
1387 // %R0<def> = L2_ploadrif_io %P1<kill>, %R29, 8;
1388 // TODO: Handle this.
1389 for (unsigned j = 0; j < BundleUses.size(); j++)
1390 if (AliasingRegs(RegA: Defs[i], RegB: BundleUses[j])) {
1391 for (unsigned k = 0; k < BundleDefs.size(); k++)
1392 for (unsigned l = 0; l < Uses.size(); l++) {
1393 if (AliasingRegs(RegA: BundleDefs[k], RegB: Uses[l]) &&
1394 !isDelayedUseException(MIa: MI, MIb: *BI)) {
1395 LLVM_DEBUG(dbgs() << "\tSwap detected:\n\t"; MI->dump();
1396 dbgs() << "\t"; (*BI)->dump());
1397 return false;
1398 }
1399 }
1400 }
1401 }
1402
1403 for (unsigned i = 0; i < Uses.size(); i++) {
1404 // Check for true data dependency.
1405 for (unsigned j = 0; j < BundleDefs.size(); j++)
1406 if (AliasingRegs(RegA: Uses[i], RegB: BundleDefs[j]) &&
1407 !isDelayedUseException(MIa: MI, MIb: *BI)) {
1408 LLVM_DEBUG(dbgs() << "\tImmediate Use detected on reg("
1409 << printReg(Uses[i], QRI) << ")\n\t";
1410 MI->dump(); dbgs() << "\t"; (*BI)->dump());
1411 // TODO: This could be an opportunity for newifying:
1412 // %P0<def> = C2_cmpeqi %R26, 0
1413 // %R26<def> = A2_tfr %R0<kill>
1414 // if (CanPromoteToDotNew(MI, Uses[i]))
1415 // LLVM_DEBUG(dbgs() << "\tCan promoto to .new form.\n");
1416 // else
1417 return false;
1418 }
1419 }
1420
1421 // For calls we also check callee save regs.
1422 if ((*BI)->isCall()) {
1423 for (const uint16_t *I = QRI->getCalleeSavedRegs(MF: &MF); *I; ++I) {
1424 for (unsigned i = 0; i < Defs.size(); i++) {
1425 if (AliasingRegs(RegA: Defs[i], RegB: *I)) {
1426 LLVM_DEBUG(dbgs() << "\tAlias with call.\n");
1427 return false;
1428 }
1429 }
1430 }
1431 }
1432
1433 // If this is return, we are probably speculating (otherwise
1434 // we could not pull in there) and will not win from pulling
1435 // into this location anyhow.
1436 // Example: a side exit.
1437 // if (!p0) dealloc_return
1438 // TODO: Can check that we do not overwrite return value
1439 // and proceed.
1440 if ((*BI)->isBarrier()) {
1441 LLVM_DEBUG(dbgs() << "\tBarrier interference.\n");
1442 return false;
1443 }
1444
1445 // \ref-manual (7.3.4) A loop setup packet in loopN or spNloop0 cannot
1446 // contain a speculative indirect jump,
1447 // a new-value compare jump or a dealloc_return.
1448 // Speculative indirect jumps (predicate + .new + indirect):
1449 // if ([!]Ps.new) jumpr:t Rs
1450 // if ([!]Ps.new) jumpr:nt Rs
1451 // @note: We don't want to pull across a call to be on the safe side.
1452 if (QII->isLoopN(MI: *MI) &&
1453 ((QII->isPredicated(MI: **BI) && QII->isPredicatedNew(MI: **BI) &&
1454 QII->isJumpR(MI: **BI)) ||
1455 QII->isNewValueJump(MI: **BI) || QII->isDeallocRet(MI: **BI) ||
1456 (*BI)->isCall())) {
1457 LLVM_DEBUG(dbgs() << "\tLoopN pull interference.\n");
1458 return false;
1459 }
1460
1461 // The opposite is also true.
1462 if (QII->isLoopN(MI: **BI) &&
1463 ((QII->isPredicated(MI: *MI) && QII->isPredicatedNew(MI: *MI) &&
1464 QII->isJumpR(MI: *MI)) ||
1465 QII->isNewValueJump(MI: *MI) || QII->isDeallocRet(MI: *MI) || MI->isCall())) {
1466 LLVM_DEBUG(dbgs() << "\tResident LoopN.\n");
1467 return false;
1468 }
1469
1470 // @todo \ref-manual 7.6.1
1471 // Presence of NVJ adds more restrictions.
1472 if (QII->isNewValueJump(MI: **BI) &&
1473 (MI->mayStore() || MI->getOpcode() == Hexagon::S2_allocframe ||
1474 MI->isCall())) {
1475 LLVM_DEBUG(dbgs() << "\tNew val Jump.\n");
1476 return false;
1477 }
1478
1479 // For memory operations, check aliasing.
1480 // First, be conservative on these objects. Might be overly constraining,
1481 // so recheck.
1482 if (isGlobalMemoryObject(MI: *BI) || isGlobalMemoryObject(MI))
1483 // Currently it catches things like this:
1484 // S2_storerinew_io %R29, 32, %R16
1485 // S2_storeri_io %R29, 68, %R0
1486 // which we can reason about.
1487 // TODO: revisit.
1488 return false;
1489
1490 // If packet has a new-value store, MI can't be a store instruction.
1491 if (QII->isNewValueStore(MI: **BI) && MI->mayStore()) {
1492 LLVM_DEBUG(dbgs() << "\tNew Value Store to store.\n");
1493 return false;
1494 }
1495
1496 if ((QII->isMemOp(MI: **BI) && MI->mayStore()) ||
1497 (QII->isMemOp(MI: *MI) && (*BI)->mayStore())) {
1498 LLVM_DEBUG(
1499 dbgs() << "\tSlot 0 not available for store because of memop.\n");
1500 return false;
1501 }
1502
1503 // If any of these is true, check aliasing.
1504 if ((MI->mayLoad() && (*BI)->mayStore()) ||
1505 (MI->mayStore() && (*BI)->mayLoad()) ||
1506 (MI->mayStore() && (*BI)->mayStore())) {
1507 if (MIsNeedChainEdge(AA, TII, MIa: MI, MIb: *BI)) {
1508 LLVM_DEBUG(dbgs() << "\tAliasing detected:\n\t"; MI->dump();
1509 dbgs() << "\t"; (*BI)->dump());
1510 return false;
1511 }
1512 }
1513 // Do not move an instruction to this packet if this packet
1514 // already contains a speculated instruction.
1515 std::map<MachineInstr *, MachineBasicBlock *>::iterator MIMoved;
1516 MIMoved = SpeculatedIns.find(x: *BI);
1517 if ((MIMoved != SpeculatedIns.end()) &&
1518 (MIMoved->second != (*BI)->getParent())) {
1519 LLVM_DEBUG(
1520 dbgs() << "This packet already contains a speculated instruction";
1521 (*BI)->dump(););
1522 return false;
1523 }
1524 }
1525
1526 // Do not pull-up vector instructions because these instructions have
1527 // multi-cycle latencies, and the pull-up pass doesn't correctly account
1528 // for instructions that stall for more than one cycle.
1529 if (QII->isHVXVec(MI: *MI))
1530 return false;
1531
1532 return true;
1533}
1534
1535/// Test is true if the two MIs cannot be safely reordered.
1536bool HexagonGlobalSchedulerImpl::ReorderDependencyTest(MachineInstr *MIa,
1537 MachineInstr *MIb) {
1538 SmallVector<unsigned, 4> DefsA;
1539 SmallVector<unsigned, 4> DefsB;
1540 SmallVector<unsigned, 8> UsesA;
1541 SmallVector<unsigned, 8> UsesB;
1542
1543 parseOperands(MI: MIa, Defs&: DefsA, Uses&: UsesA);
1544 parseOperands(MI: MIb, Defs&: DefsB, Uses&: UsesB);
1545
1546 for (SmallVector<unsigned, 4>::iterator IDA = DefsA.begin(),
1547 IDAE = DefsA.end();
1548 IDA != IDAE; ++IDA) {
1549 for (SmallVector<unsigned, 8>::iterator IUB = UsesB.begin(),
1550 IUBE = UsesB.end();
1551 IUB != IUBE; ++IUB)
1552 // True data dependency.
1553 if (AliasingRegs(RegA: *IDA, RegB: *IUB))
1554 return true;
1555
1556 for (SmallVector<unsigned, 4>::iterator IDB = DefsB.begin(),
1557 IDBE = DefsB.end();
1558 IDB != IDBE; ++IDB)
1559 // Output dependency.
1560 if (AliasingRegs(RegA: *IDA, RegB: *IDB))
1561 return true;
1562 }
1563
1564 for (SmallVector<unsigned, 4>::iterator IDB = DefsB.begin(),
1565 IDBE = DefsB.end();
1566 IDB != IDBE; ++IDB) {
1567 for (SmallVector<unsigned, 8>::iterator IUA = UsesA.begin(),
1568 IUAE = UsesA.end();
1569 IUA != IUAE; ++IUA)
1570 // True data dependency.
1571 if (AliasingRegs(RegA: *IDB, RegB: *IUA))
1572 return true;
1573 }
1574
1575 // Do not reorder two calls...
1576 if (MIa->isCall() && MIb->isCall())
1577 return true;
1578
1579 // For calls we also check callee save regs.
1580 if (MIa->isCall())
1581 for (const uint16_t *I = QRI->getCalleeSavedRegs(MF: &MF); *I; ++I) {
1582 for (unsigned i = 0; i < DefsB.size(); i++) {
1583 if (AliasingRegs(RegA: DefsB[i], RegB: *I))
1584 return true;
1585 }
1586 }
1587
1588 if (MIb->isCall())
1589 for (const uint16_t *I = QRI->getCalleeSavedRegs(MF: &MF); *I; ++I) {
1590 for (unsigned i = 0; i < DefsA.size(); i++) {
1591 if (AliasingRegs(RegA: DefsA[i], RegB: *I))
1592 return true;
1593 }
1594 }
1595
1596 // For memory operations, check aliasing.
1597 // First, be conservative on these objects.
1598 // Might be overly constraining, so recheck.
1599 if ((isGlobalMemoryObject(MI: MIa)) || (isGlobalMemoryObject(MI: MIb)))
1600 return true;
1601
1602 // If any of these is true, check aliasing.
1603 if (((MIa->mayLoad() && MIb->mayStore()) ||
1604 (MIa->mayStore() && MIb->mayLoad()) ||
1605 (MIa->mayStore() && MIb->mayStore())) &&
1606 MIsNeedChainEdge(AA, TII, MIa, MIb))
1607 return true;
1608
1609 return false;
1610}
1611
1612/// Serial semantics.
1613bool HexagonGlobalSchedulerImpl::MIsAreDependent(MachineInstr *MIa,
1614 MachineInstr *MIb) {
1615 if (MIa == MIb)
1616 return false;
1617
1618 if (ReorderDependencyTest(MIa, MIb)) {
1619 LLVM_DEBUG(dbgs() << "\t\t[MIsAreDependent]:\n\t\t"; MIa->dump();
1620 dbgs() << "\t\t"; MIb->dump());
1621 return true;
1622 }
1623 return false;
1624}
1625
1626/// Serial semantics.
1627bool HexagonGlobalSchedulerImpl::MIsHaveTrueDependency(MachineInstr *MIa,
1628 MachineInstr *MIb) {
1629 if (MIa == MIb)
1630 return false;
1631
1632 SmallVector<unsigned, 4> DefsA;
1633 SmallVector<unsigned, 4> DefsB;
1634 SmallVector<unsigned, 8> UsesA;
1635 SmallVector<unsigned, 8> UsesB;
1636
1637 parseOperands(MI: MIa, Defs&: DefsA, Uses&: UsesA);
1638 parseOperands(MI: MIb, Defs&: DefsB, Uses&: UsesB);
1639
1640 for (SmallVector<unsigned, 4>::iterator IDA = DefsA.begin(),
1641 IDAE = DefsA.end();
1642 IDA != IDAE; ++IDA) {
1643 for (SmallVector<unsigned, 8>::iterator IUB = UsesB.begin(),
1644 IUBE = UsesB.end();
1645 IUB != IUBE; ++IUB)
1646 // True data dependency.
1647 if (AliasingRegs(RegA: *IDA, RegB: *IUB))
1648 return true;
1649 }
1650 return false;
1651}
1652
1653/// Sequential semantics. Can these two MIs be reordered?
1654/// Moving MIa from "behind" to "in front" of MIb.
1655bool HexagonGlobalSchedulerImpl::canReorderMIs(MachineInstr *MIa,
1656 MachineInstr *MIb) {
1657 if (!MIa || !MIb)
1658 return false;
1659
1660 // Within bundle semantics are parallel.
1661 if (MIa->isBundle()) {
1662 MachineBasicBlock::instr_iterator MII = MIa->getIterator();
1663 MachineBasicBlock::instr_iterator MIIE = MIa->getParent()->instr_end();
1664 for (++MII; MII != MIIE && MII->isInsideBundle(); ++MII) {
1665 if (MII->isDebugInstr())
1666 continue;
1667 if (MIsAreDependent(MIa: &*MII, MIb))
1668 return false;
1669 }
1670 return true;
1671 }
1672 return !MIsAreDependent(MIa, MIb);
1673}
1674
1675static inline bool MIMustNotBePulledUp(MachineInstr *MI) {
1676 if (MI->isInlineAsm() || MI->isEHLabel() || IsSchedBarrier(MI))
1677 return true;
1678 return false;
1679}
1680
1681static inline bool MIShouldNotBePulledUp(MachineInstr *MI) {
1682 if (MI->isBranch() || MI->isReturn() || MI->isCall() || MI->isBarrier() ||
1683 MI->isTerminator() || MIMustNotBePulledUp(MI))
1684 return true;
1685 return false;
1686}
1687
1688// Only approve dual jump candidate:
1689// It is a branch, and we move it to last packet of the target location.
1690bool HexagonGlobalSchedulerImpl::MIisDualJumpCandidate(
1691 MachineInstr *MI, MachineBasicBlock::iterator &WorkPoint) {
1692 if (!PerformDualJumps || !IsDualJumpSecondCandidate(MI) ||
1693 MIMustNotBePulledUp(MI) || ignoreInstruction(MI))
1694 return false;
1695
1696 MachineBasicBlock *FromThisBB = MI->getParent();
1697 MachineBasicBlock *ToThisBB = WorkPoint->getParent();
1698
1699 LLVM_DEBUG(dbgs() << "\t\t[MIisDualJumpCandidate] To BB("
1700 << ToThisBB->getNumber() << ") From BB("
1701 << FromThisBB->getNumber() << ")\n");
1702 // If the question is about the same BB, we do not want to get
1703 // dual jump involved - it is a different case.
1704 if (FromThisBB == ToThisBB)
1705 return false;
1706
1707 // Dual jump could only be done on neigboring BBs.
1708 // The FromThisBB must only have one predecessor - the basic
1709 // block we are trying to merge.
1710 if ((*(FromThisBB->pred_begin()) != ToThisBB) ||
1711 (std::next(x: FromThisBB->pred_begin()) != FromThisBB->pred_end()))
1712 return false;
1713
1714 // If this block is a target of an indirect branch, it should
1715 // also not be included.
1716 if (FromThisBB->isEHPad() || FromThisBB->hasAddressTaken())
1717 return false;
1718
1719 // Now we must preserve original fall through paths. In fact we
1720 // might be dealing with 3way branching.
1721 MachineBasicBlock *ToTBB = NULL, *ToFBB = NULL;
1722
1723 if (ToThisBB->succ_size() == 2) {
1724 // Check the branch from target block.
1725 // If we have two successors, we must understand the branch.
1726 SmallVector<MachineOperand, 4> ToCond;
1727 if (!QII->analyzeBranch(MBB&: *ToThisBB, TBB&: ToTBB, FBB&: ToFBB, Cond&: ToCond, AllowModify: false)) {
1728 // Have the branch. Check the topology.
1729 LLVM_DEBUG(dbgs() << "\t\tToThisBB has two successors: TBB("
1730 << ToTBB->getNumber() << ") and FBB(";
1731 if (ToFBB) dbgs() << ToFBB->getNumber() << ").\n";
1732 else dbgs() << "None"
1733 << ").\n";);
1734 if (ToTBB == FromThisBB) {
1735 // If the from BB is not the fall through, we can only handle case
1736 // when second branch is unconditional jump.
1737 return false;
1738 } else if (ToFBB == FromThisBB || !ToFBB) {
1739 // If the fall through path of ToBB is our FromBB, we have more freedom
1740 // of operation.
1741 LLVM_DEBUG(dbgs() << "\t\tFall through jump target.\n");
1742 }
1743 } else {
1744 LLVM_DEBUG(dbgs() << "\t\tUnable to analyze first branch.\n");
1745 return false;
1746 }
1747 } else if (ToThisBB->succ_size() == 1) {
1748 ToFBB = *ToThisBB->succ_begin();
1749 assert(ToFBB == FromThisBB && "Bad CFG layout");
1750 } else
1751 return false;
1752
1753 // First unbundled control flow instruction in the BB.
1754 if (!MI->isBundled() && MI == &*FromThisBB->getFirstNonDebugInstr())
1755 return IsDualJumpFirstCandidate(TargetPacket&: WorkPoint);
1756
1757 return false;
1758}
1759
1760// Check whether moving MI to MJ's packet would cause a stall from a previous
1761// packet.
1762bool HexagonGlobalSchedulerImpl::canCauseStall(MachineInstr *MI,
1763 MachineInstr *MJ) {
1764 SmallVector<unsigned, 4> DefsMJI;
1765 SmallVector<unsigned, 8> UsesMJI;
1766 SmallVector<unsigned, 4> DefsMI;
1767 SmallVector<unsigned, 8> UsesMI;
1768 parseOperands(MI, Defs&: DefsMI, Uses&: UsesMI);
1769
1770 for (auto Use : UsesMI) {
1771 int UseIdx = MI->findRegisterUseOperandIdx(Reg: Use, /*TRI=*/nullptr);
1772 if (UseIdx == -1)
1773 continue;
1774 bool ShouldBreak = false;
1775 int BundleCount = 0;
1776 for (MachineBasicBlock::instr_iterator
1777 Begin = MJ->getParent()->instr_begin(),
1778 MJI = MJ->getIterator();
1779 MJI != Begin; --MJI) {
1780 if (MJI->isBundle()) {
1781 ++BundleCount;
1782 continue;
1783 }
1784 parseOperands(MI: &*MJI, Defs&: DefsMJI, Uses&: UsesMJI);
1785 for (auto Def : DefsMJI) {
1786 if (Def == Use || AliasingRegs(RegA: Def, RegB: Use)) {
1787 int DefIdx = MJI->findRegisterDefOperandIdx(Reg: Def, /*TRI=*/nullptr);
1788 if (DefIdx >= 0) {
1789 int Latency =
1790 TSchedModel.computeOperandLatency(DefMI: &*MJI, DefOperIdx: DefIdx, UseMI: MI, UseOperIdx: UseIdx);
1791 if (Latency > BundleCount)
1792 // There will be a stall if MI is moved to MJ's packet.
1793 return true;
1794 // We found the def for the use and it does not cause a stall.
1795 // Continue checking the next use for a potential stall.
1796 ShouldBreak = true;
1797 break;
1798 }
1799 }
1800 }
1801 if (ShouldBreak)
1802 break;
1803 if (!MJI->isBundled() && !MJI->isDebugInstr())
1804 ++BundleCount;
1805 }
1806 }
1807 return false;
1808}
1809
1810/// Analyze this instruction. If this is an unbundled instruction, see
1811/// if it in theory could be packetized.
1812/// If it is already part of a packet, see if it has internal
1813/// dependencies to this packet.
1814bool HexagonGlobalSchedulerImpl::canThisMIBeMoved(
1815 MachineInstr *MI, MachineBasicBlock::iterator &WorkPoint,
1816 bool &MovingDependentOp, int &Cost) {
1817 if (!MI)
1818 return false;
1819 // By default, it is a normal move.
1820 MovingDependentOp = false;
1821 Cost = 0;
1822 // If MI is a 'formed' compound not potential compound, bail out.
1823 if (QII->isCompoundBranchInstr(MI: *MI))
1824 return false;
1825 // See if we can potentially break potential compound candidates,
1826 // and do not do it.
1827 if (PreventCompoundSeparation && MI->isBundled()) {
1828 enum HexagonII::CompoundGroup MICG = QII->getCompoundCandidateGroup(MI: *MI);
1829 if (MICG != HexagonII::HCG_None) {
1830 // Check internal dependencies in the bundle.
1831 // First, find the bundle header.
1832 MachineBasicBlock::instr_iterator MII = MI->getIterator();
1833 for (--MII; MII->isBundled(); --MII)
1834 if (MII->isBundle())
1835 break;
1836
1837 MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
1838 for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
1839 ++MII) {
1840 if (&(*MII) == MI)
1841 continue;
1842 if (isCompoundPair(MIa: &*MII, MIb: MI)) {
1843 LLVM_DEBUG(dbgs() << "\tPrevent Compound separation.\n");
1844 return false;
1845 }
1846 }
1847 }
1848 }
1849 // Same thing for duplex candidates.
1850 if (PreventDuplexSeparation && MI->isBundled()) {
1851 if (QII->getDuplexCandidateGroup(MI: *MI) != HexagonII::HSIG_None) {
1852 // Check internal dependencies in the bundle.
1853 // First, find the bundle header.
1854 MachineBasicBlock::instr_iterator MII = MI->getIterator();
1855 for (--MII; MII->isBundled(); --MII)
1856 if (MII->isBundle())
1857 break;
1858
1859 MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
1860 for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
1861 ++MII) {
1862 if ((&(*MII) != MI) && QII->isDuplexPair(MIa: *MII, MIb: *MI)) {
1863 LLVM_DEBUG(dbgs() << "\tPrevent Duplex separation.\n");
1864 return false;
1865 }
1866 }
1867 }
1868 }
1869
1870 // If we perform dual jump formation during the pull-up,
1871 // then we want to consider several additional situations.
1872 // a) Allow moving of dependent instruction from a packet
1873 // b) Allow moving some control flow instructions if they meet
1874 // dual jump criteria.
1875 if (MIisDualJumpCandidate(MI, WorkPoint)) {
1876 LLVM_DEBUG(dbgs() << "\t\tDual jump candidate:\t"; MI->dump());
1877 // Here we are breaking our general assumption about not moving dependent
1878 // instructions. To save us two more expensive checks down the line,
1879 // propagate the information directly.
1880 MovingDependentOp = true;
1881 return true;
1882 }
1883
1884 // Any of these should not even be tried.
1885 if (MIShouldNotBePulledUp(MI) || ignoreInstruction(MI))
1886 return false;
1887 // Pulling up these instructions could put them
1888 // out of jump range/offset size.
1889 if (QII->isLoopN(MI: *MI)) {
1890 unsigned dist_looplabel =
1891 BlockToInstOffset.find(Val: MI->getOperand(i: 0).getMBB())->second;
1892 unsigned dist_newloop0 =
1893 BlockToInstOffset.find(Val: WorkPoint->getParent())->second;
1894 // Check if the jump in the last instruction is within range.
1895 unsigned Distance =
1896 (unsigned)std::abs(x: (long long)dist_looplabel - dist_newloop0) +
1897 QII->nonDbgBBSize(BB: WorkPoint->getParent()) * 4 + SafetyBuffer;
1898 const HexagonInstrInfo *HII = (const HexagonInstrInfo *)TII;
1899 if (!HII->isJumpWithinBranchRange(MI: *MI, offset: Distance)) {
1900 LLVM_DEBUG(dbgs() << "\nloopN cannot be moved since Distance: "
1901 << Distance << " outside branch range.";);
1902 return false;
1903 }
1904 LLVM_DEBUG(dbgs() << "\nloopN can be moved since Distance: " << Distance
1905 << " within branch range.";);
1906 }
1907 // If the def-set of an MI is one of the live-ins then MI should
1908 // kill that reg and no instruction before MI should use it.
1909 // For simplicity, allow only if MI is the first instruction in the MBB.
1910 std::map<MachineInstr *, std::vector<unsigned>>::const_iterator DefIter =
1911 MIDefSet.find(x: MI);
1912 MachineBasicBlock *MBB = MI->getParent();
1913 for (unsigned i = 0; DefIter != MIDefSet.end() && i < DefIter->second.size();
1914 ++i) {
1915 if (MBB->isLiveIn(Reg: DefIter->second[i]) &&
1916 &*MBB->getFirstNonDebugInstr() != MI)
1917 return false;
1918 }
1919 // If it is part of a bundle, analyze it.
1920 if (MI->isBundled()) {
1921 // Cannot move bundle header itself. This function is about
1922 // individual MI move.
1923 if (MI->isBundle())
1924 return false;
1925
1926 // Check internal dependencies in the bundle.
1927 // First, find the bundle header.
1928 MachineBasicBlock::instr_iterator MII = MI->getIterator();
1929 for (--MII; MII->isBundled(); --MII)
1930 if (MII->isBundle())
1931 break;
1932
1933 MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
1934 for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
1935 ++MII) {
1936 if (MII->isDebugInstr())
1937 continue;
1938 if (MIsAreDependent(MIa: &*MII, MIb: MI)) {
1939 if (!AllowDependentPullUp) {
1940 LLVM_DEBUG(dbgs() << "\t\tDependent.\n");
1941 return false;
1942 } else {
1943 // There are a few cases that we can safely move a dependent
1944 // instruction away from this packet.
1945 // One example is an instruction setting a call operands.
1946 if ((MII->isCall() && !IsIndirectCall(MI: &*MII)) ||
1947 IsDualJumpSecondCandidate(MI: &*MII) || MI->isBranch()) {
1948 LLVM_DEBUG(dbgs() << "\t\tDependent, but allow to move.\n");
1949 MovingDependentOp = true;
1950 Cost -= 10;
1951 continue;
1952 } else {
1953 LLVM_DEBUG(dbgs() << "\t\tDependent, and do not allow for now.\n");
1954 return false;
1955 }
1956 }
1957 }
1958 }
1959 }
1960 return true;
1961}
1962
1963/// Return true if MI defines a predicate and parse all defs.
1964bool HexagonGlobalSchedulerImpl::doesMIDefinesPredicate(
1965 MachineInstr *MI, SmallVector<unsigned, 4> &Defs) {
1966 bool defsPredicate = false;
1967 Defs.clear();
1968
1969 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1970 const MachineOperand &MO = MI->getOperand(i);
1971
1972 // Regmasks are considered "implicit".
1973 if (!MO.isReg())
1974 continue;
1975 unsigned Reg = MO.getReg();
1976
1977 if (!Reg || QRI->isFakeReg(Reg))
1978 continue;
1979
1980 assert(Register::isPhysicalRegister(Reg));
1981
1982 if (MO.isDef() && !MO.isImplicit()) {
1983 const TargetRegisterClass *RC = QRI->getMinimalPhysRegClass(Reg);
1984 if (RC == &Hexagon::PredRegsRegClass) {
1985 defsPredicate = true;
1986 Defs.push_back(Elt: MO.getReg());
1987 }
1988 }
1989 }
1990 return defsPredicate;
1991}
1992
1993/// We have just tentatively added a predicated MI to an existing packet.
1994/// Now we need to determine if it needs to be changed to .new form.
1995/// It only handles compare/predicate right now.
1996/// TODO - clean this logic up.
1997/// TODO - generalize to handle any .new
1998bool HexagonGlobalSchedulerImpl::NeedToNewify(
1999 MachineBasicBlock::instr_iterator NewMI, unsigned *DepReg,
2000 MachineInstr *TargetPacket = NULL) {
2001 MachineBasicBlock::instr_iterator MII = NewMI;
2002 SmallVector<unsigned, 4> DefsA;
2003 SmallVector<unsigned, 4> DefsB;
2004 SmallVector<unsigned, 8> UsesB;
2005
2006 // If this is not a normal bundle, we are probably
2007 // trying to size two lonesome instructions together,
2008 // and trying to say if one of them will need to be
2009 // newified. In this is the case we have something like this:
2010 // BB#5:
2011 // %P0<def> = CMPGEri %R4, 2
2012 // S2_pstorerif_io %P0<kill>, %R29, 16, %R21<kill>
2013 // BUNDLE %R7<imp-def>, %R4<imp-def>, %R7<imp-use>
2014 parseOperands(MI: &*NewMI, Defs&: DefsB, Uses&: UsesB);
2015 if (TargetPacket && !TargetPacket->isBundled()) {
2016 if (doesMIDefinesPredicate(MI: TargetPacket, Defs&: DefsA)) {
2017 for (SmallVector<unsigned, 4>::iterator IA = DefsA.begin(),
2018 IAE = DefsA.end();
2019 IA != IAE; ++IA)
2020 for (SmallVector<unsigned, 8>::iterator IB = UsesB.begin(),
2021 IBE = UsesB.end();
2022 IB != IBE; ++IB)
2023 if (*IA == *IB) {
2024 *DepReg = *IA;
2025 return true;
2026 }
2027 }
2028 return false;
2029 }
2030
2031 // Find bundle header.
2032 for (--MII; MII->isBundled(); --MII)
2033 if (MII->isBundle())
2034 break;
2035
2036 // Iterate down, if there is data dependent cmp found, need to .newify.
2037 // Also, we can have the following:
2038 // {
2039 // p0 = r7
2040 // if (!p0.new) jump:t .LBB4_18
2041 // if (p0.new) r8 = zxth(r12)
2042 // }
2043 MachineBasicBlock::instr_iterator BBEnd = MII->getParent()->instr_end();
2044 for (++MII; MII != BBEnd && MII->isBundled() && !MII->isBundle(); ++MII) {
2045 if (MII == NewMI)
2046 continue;
2047 if (doesMIDefinesPredicate(MI: &*MII, Defs&: DefsA)) {
2048 for (SmallVector<unsigned, 4>::iterator IA = DefsA.begin(),
2049 IAE = DefsA.end();
2050 IA != IAE; ++IA)
2051 for (SmallVector<unsigned, 8>::iterator IB = UsesB.begin(),
2052 IBE = UsesB.end();
2053 IB != IBE; ++IB)
2054 // We do not have multiple predicate regs defined in any instruction,
2055 // if we ever will, this needs to be generalized.
2056 if (*IA == *IB) {
2057 *DepReg = *IA;
2058 return true;
2059 }
2060 DefsA.clear();
2061 }
2062 }
2063 LLVM_DEBUG(dbgs() << "\nNo need to newify:"; NewMI->dump());
2064 return false;
2065}
2066
2067/// We know this instruction needs to be newified to be added to the packet,
2068/// but not all combinations are legal.
2069/// It is a complimentary check to NeedToNewify().
2070/// The packet actually contains the new instruction during the check.
2071bool HexagonGlobalSchedulerImpl::CanNewifiedBeUsedInBundle(
2072 MachineBasicBlock::instr_iterator NewMI, unsigned DepReg,
2073 MachineInstr *TargetPacket) {
2074 MachineBasicBlock::instr_iterator MII = NewMI;
2075 if (!TargetPacket || !TargetPacket->isBundled())
2076 return true;
2077
2078 // Find the bundle header.
2079 for (--MII; MII->isBundled(); --MII)
2080 if (MII->isBundle())
2081 break;
2082
2083 MachineBasicBlock::instr_iterator BBEnd = MII->getParent()->instr_end();
2084 for (++MII; MII != BBEnd && MII->isBundled() && !MII->isBundle(); ++MII) {
2085 // Effectively we look for the case of late predicates.
2086 // No additional checks at the time.
2087 if (MII == NewMI || !QII->isPredicateLate(Opcode: MII->getOpcode()))
2088 continue;
2089 SmallVector<unsigned, 4> DefsA;
2090 if (!doesMIDefinesPredicate(MI: &*MII, Defs&: DefsA))
2091 continue;
2092 for (auto &IA : DefsA)
2093 if (IA == DepReg)
2094 return false;
2095 }
2096 return true;
2097}
2098
2099/// setUsed - Set the register and its sub-registers as being used.
2100/// Similar to RegScavenger::setUsed().
2101void HexagonGlobalSchedulerImpl::setUsedRegs(BitVector &Set, unsigned Reg) {
2102 Set.reset(Idx: Reg);
2103 for (MCSubRegIterator SubRegs(Reg, QRI); SubRegs.isValid(); ++SubRegs)
2104 Set.reset(Idx: *SubRegs);
2105}
2106
2107/// Are these two registers overlaping?
2108bool HexagonGlobalSchedulerImpl::AliasingRegs(unsigned RegA, unsigned RegB) {
2109 if (RegA == RegB)
2110 return true;
2111
2112 for (MCSubRegIterator SubRegs(RegA, QRI); SubRegs.isValid(); ++SubRegs)
2113 if (RegB == *SubRegs)
2114 return true;
2115
2116 for (MCSubRegIterator SubRegs(RegB, QRI); SubRegs.isValid(); ++SubRegs)
2117 if (RegA == *SubRegs)
2118 return true;
2119
2120 return false;
2121}
2122
2123/// Find use with this reg, and unmark the kill flag.
2124static inline void unmarkKillReg(MachineInstr *MI, unsigned Reg) {
2125 if (MI->isDebugInstr())
2126 return;
2127
2128 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2129 MachineOperand &MO = MI->getOperand(i);
2130
2131 if (!MO.isReg())
2132 continue;
2133
2134 if (MO.isKill() && (MO.getReg() == Reg))
2135 MO.setIsKill(false);
2136 }
2137}
2138
2139/// Find use with this reg, and unmark the kill flag.
2140static inline void markKillReg(MachineInstr *MI, unsigned Reg) {
2141 if (MI->isDebugInstr())
2142 return;
2143
2144 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2145 MachineOperand &MO = MI->getOperand(i);
2146
2147 if (!MO.isReg())
2148 continue;
2149
2150 if (MO.isUse() && (MO.getReg() == Reg))
2151 MO.setIsKill(true);
2152 }
2153}
2154
2155/// We have just moved an instruction that could have changed kill patterns
2156/// along the path it was moved. We need to update it.
2157void HexagonGlobalSchedulerImpl::updateKillAlongThePath(
2158 MachineBasicBlock *HomeBB, MachineBasicBlock *OriginBB,
2159 MachineBasicBlock::instr_iterator &Head,
2160 MachineBasicBlock::instr_iterator &Tail,
2161 MachineBasicBlock::iterator &SourcePacket,
2162 MachineBasicBlock::iterator &TargetPacket,
2163 std::vector<MachineInstr *> &backtrack) {
2164 // This is the instruction being moved.
2165 MachineInstr *MI = &*Head;
2166 MachineBasicBlock *CurrentBB = OriginBB;
2167 SmallSet<unsigned, 8> KilledUseSet;
2168
2169 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2170 const MachineOperand &MO = MI->getOperand(i);
2171 if (!MO.isReg())
2172 continue;
2173 unsigned Reg = MO.getReg();
2174 if (!Reg)
2175 continue;
2176
2177 if (MO.isKill())
2178 KilledUseSet.insert(V: Reg);
2179 }
2180
2181 // If there are no kills here, we are done.
2182 if (KilledUseSet.empty())
2183 return;
2184
2185 LLVM_DEBUG(dbgs() << "\n[updateKillAlongThePath]\n");
2186 LLVM_DEBUG(dbgs() << "\t\tInstrToMove :\t"; MI->dump());
2187 LLVM_DEBUG(dbgs() << "\t\tSourceLocation:\n";
2188 DumpPacket(SourcePacket.getInstrIterator()));
2189 LLVM_DEBUG(dbgs() << "\t\tTargetPacket :\n";
2190 DumpPacket(TargetPacket.getInstrIterator()));
2191 LLVM_DEBUG(dbgs() << "\tUpdate Kills. Need to update (" << KilledUseSet.size()
2192 << ")kills. From BB (" << OriginBB->getNumber() << ")\n");
2193 LLVM_DEBUG(dbgs() << "\tMove path:\n");
2194 assert(!backtrack.empty() && "Empty back track");
2195
2196 // We have pulled up an instruction, with one of its uses marked as kill.
2197 // If there is any other use of the same register along the move path,
2198 // and there are no side exits with killed register live-in along them,
2199 // we need to mark last use of that reg as kill.
2200 for (signed i = backtrack.size() - 1; i >= 0; --i) {
2201 LLVM_DEBUG(dbgs() << "\t\t[" << i << "]BB("
2202 << backtrack[i]->getParent()->getNumber() << ")\t";
2203 backtrack[i]->dump());
2204 if (CurrentBB != backtrack[i]->getParent()) {
2205 LLVM_DEBUG(dbgs() << "\t\tChange BB from (" << CurrentBB->getNumber()
2206 << ") to(" << backtrack[i]->getParent()->getNumber()
2207 << ")\n");
2208 for (MachineBasicBlock::const_succ_iterator
2209 SI = backtrack[i]->getParent()->succ_begin(),
2210 SE = backtrack[i]->getParent()->succ_end();
2211 SI != SE; ++SI) {
2212 if (*SI == CurrentBB)
2213 continue;
2214
2215 LLVM_DEBUG(dbgs() << "\t\tSide Exit:\n\t"; (*SI)->dump());
2216 // If any reg kill is live along this side exit, it is not
2217 // a kill any more.
2218 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
2219 E = (*SI)->livein_end();
2220 I != E; ++I) {
2221 if (KilledUseSet.count(V: (*I).PhysReg)) {
2222 LLVM_DEBUG(dbgs() << "\t\tReg (" << printReg((*I).PhysReg, QRI)
2223 << ") is LiveIn along side exit.\n");
2224 KilledUseSet.erase(V: (*I).PhysReg);
2225 unmarkKillReg(MI, Reg: (*I).PhysReg);
2226 }
2227 if (KilledUseSet.empty())
2228 return;
2229 }
2230 }
2231 CurrentBB = backtrack[i]->getParent();
2232 }
2233
2234 // Done with the whole path.
2235 if (backtrack[i] == &*TargetPacket)
2236 return;
2237
2238 // Starting the tracking. Do not update source bundle.
2239 // If TargetPacket == SourcePacket we have returned
2240 // in the previous check.
2241 if (backtrack[i] == &*SourcePacket)
2242 continue;
2243
2244 // Ignore DBG_VALUE.
2245 if (backtrack[i]->isDebugInstr())
2246 continue;
2247
2248 // Encountered an intermediary bundle. Process it.
2249 // Beware, sometimes check for backtrack[i] == TargetPacket
2250 // does not work, so this instruction could be one from the target bundle.
2251 SmallVector<unsigned, 4> Defs;
2252 SmallVector<unsigned, 8> Uses;
2253 MachineInstr *MIU = backtrack[i];
2254 parseOperands(MI: MIU, Defs, Uses);
2255
2256 for (SmallVector<unsigned, 8>::iterator IA = Uses.begin(), IAE = Uses.end();
2257 IA != IAE; ++IA) {
2258 if (KilledUseSet.count(V: *IA)) {
2259 // Now this is new kill point for this Reg.
2260 // Update the bundle, and any local uses.
2261 markKillReg(MI: MIU, Reg: *IA);
2262
2263 // Unmark the current MI.
2264 unmarkKillReg(MI, Reg: *IA);
2265
2266 if (MIU->isBundle()) {
2267 // TODO: Can do this cleaner and faster.
2268 MachineBasicBlock::instr_iterator MII = MIU->getIterator();
2269 MachineBasicBlock::instr_iterator End = CurrentBB->instr_end();
2270 for (++MII; MII != End && MII->isInsideBundle(); ++MII)
2271 markKillReg(MI: &*MII, Reg: *IA);
2272 }
2273
2274 // We have updated this kill reg, if there are more, keep on going.
2275 KilledUseSet.erase(V: *IA);
2276
2277 // If the set is exhausted, just leave.
2278 if (KilledUseSet.empty())
2279 return;
2280 }
2281 }
2282 }
2283}
2284
2285/// This is houskeeping for bundle with instruction just added to it.
2286void HexagonGlobalSchedulerImpl::addInstructionToExistingBundle(
2287 MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
2288 MachineBasicBlock::instr_iterator &Tail,
2289 MachineBasicBlock::instr_iterator &NewMI,
2290 MachineBasicBlock::iterator &TargetPacket,
2291 MachineBasicBlock::iterator &NextMI,
2292 std::vector<MachineInstr *> &backtrack) {
2293 Tail = getBundleEnd(I: Head);
2294 LLVM_DEBUG(dbgs() << "\t\t\t[Add] Head home: "; DumpPacket(Head));
2295
2296 // Old header to be deleted shortly.
2297 MachineBasicBlock::instr_iterator Outcast = Head;
2298 // Unbundle old header.
2299 if (Outcast->isBundle() && Outcast->isBundledWithSucc())
2300 Outcast->unbundleFromSucc();
2301
2302 bool memShufDisabled = QII->getBundleNoShuf(MIB: *Outcast);
2303
2304 // Create new bundle header and update MI flags.
2305 finalizeBundle(MBB&: *HomeBB, FirstMI: ++Head, LastMI: Tail);
2306 MachineBasicBlock::instr_iterator BundleMII = std::prev(x: Head);
2307 if (memShufDisabled)
2308 QII->setBundleNoShuf(BundleMII);
2309 --Head;
2310
2311 LLVM_DEBUG(dbgs() << "\t\t\t[Add] New Head : "; DumpPacket(Head));
2312
2313 // The old header could be listed in the back tracking,
2314 // so if it is, we need to update it.
2315 for (unsigned i = 0; i < backtrack.size(); ++i)
2316 if (backtrack[i] == &*Outcast)
2317 backtrack[i] = &*Head;
2318
2319 // Same for top MI iterator.
2320 if (NextMI == Outcast)
2321 NextMI = Head;
2322
2323 TargetPacket = Head;
2324 HomeBB->erase(I: Outcast);
2325}
2326
2327/// This handles houskeeping for bundle with instruction just deleted from it.
2328/// We do not see the original moved instruction in here.
2329void HexagonGlobalSchedulerImpl::removeInstructionFromExistingBundle(
2330 MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
2331 MachineBasicBlock::instr_iterator &Tail,
2332 MachineBasicBlock::iterator &SourceLocation,
2333 MachineBasicBlock::iterator &NextMI, bool MovingDependentOp,
2334 std::vector<MachineInstr *> &backtrack) {
2335 // Empty BBs will be deleted shortly.
2336 if (HomeBB->empty()) {
2337 Head = MachineBasicBlock::instr_iterator();
2338 Tail = MachineBasicBlock::instr_iterator();
2339 return;
2340 }
2341
2342 if (!SourceLocation->isBundle()) {
2343 LLVM_DEBUG(dbgs() << "\t\t\tOriginal instruction was not bundled.\n\t\t\t";
2344 SourceLocation->dump());
2345 // If original instruction was not bundled, and we have moved it
2346 // and it is in the back track, we probably want to remove it from there.
2347 LLVM_DEBUG(dbgs() << "\t\t\t[Rem] New head: "; backtrack.back()->dump());
2348
2349 for (unsigned i = 0; i < backtrack.size(); ++i) {
2350 if (backtrack[i] == &*SourceLocation) {
2351 // By definition, this should be the last instruction in the backtrack.
2352 assert((backtrack[i] == backtrack.back()) && "Lost back track");
2353 backtrack.pop_back();
2354 }
2355 // Point the main iterator to the next instruction.
2356 if (NextMI == SourceLocation)
2357 NextMI++;
2358 }
2359 SourceLocation = MachineBasicBlock::iterator();
2360 Head = MachineBasicBlock::instr_iterator();
2361 Tail = MachineBasicBlock::instr_iterator();
2362 return;
2363 }
2364
2365 // The old header, soon to be deleted.
2366 MachineBasicBlock::instr_iterator Outcast = SourceLocation.getInstrIterator();
2367 LLVM_DEBUG(dbgs() << "\t\t\t[Rem] SourceLocation after bundle update: ";
2368 DumpPacket(Outcast));
2369
2370 // If bundle has been already destroyed. BB->splat seems to do it some times
2371 // but not the other.
2372 // We already know that SourceLocation is bundle header.
2373 if (!SourceLocation->isBundledWithSucc()) {
2374 assert(!Head->isBundledWithSucc() && !Head->isBundledWithPred() &&
2375 "Bad bundle");
2376 } else {
2377 Head = SourceLocation.getInstrIterator();
2378 Tail = getBundleEnd(I: Head);
2379 unsigned Size = 0;
2380 unsigned BBSizeWithDbg = 0;
2381 MachineBasicBlock::const_instr_iterator I(Head);
2382 MachineBasicBlock::const_instr_iterator E = Head->getParent()->instr_end();
2383
2384 for (++I; I != E && I->isBundledWithPred(); ++I) {
2385 ++BBSizeWithDbg;
2386 if (!I->isDebugInstr())
2387 ++Size;
2388 }
2389
2390 LLVM_DEBUG(dbgs() << "\t\t\t[Rem] Size(" << Size << ") Head orig: ";
2391 DumpPacket(Head));
2392 // The old header, soon to be deleted.
2393 Outcast = Head;
2394
2395 // The old Header is still counted here.
2396 if (Size > 1) {
2397 if (Outcast->isBundle() && Outcast->isBundledWithSucc())
2398 Outcast->unbundleFromSucc();
2399
2400 bool memShufDisabled = QII->getBundleNoShuf(MIB: *Outcast);
2401 // The finalizeBundle() assumes that "original" sequence
2402 // it is finalizing is sequentially correct. That basically
2403 // means that swap case might not be handled properly.
2404 // I find insert point for the pull-up instruction myself,
2405 // and I should try to catch that swap case there, and refuse
2406 // to insert if I cannot guarantee correct serial semantics.
2407 // In the future, I need my own incremental "inserToBundle"
2408 // function.
2409 finalizeBundle(MBB&: *HomeBB, FirstMI: ++Head, LastMI: Tail);
2410 MachineBasicBlock::instr_iterator BundleMII = std::prev(x: Head);
2411 if (memShufDisabled)
2412 QII->setBundleNoShuf(BundleMII);
2413
2414 --Head;
2415 } else if (Size == 1) {
2416 // There is only one non-debug instruction in the bundle.
2417 if (BBSizeWithDbg > 1) {
2418 // There are some debug instructions that should be unbundled too.
2419 MachineBasicBlock::instr_iterator I(Head);
2420 MachineBasicBlock::instr_iterator E = Head->getParent()->instr_end();
2421 for (++I; I != E && I->isBundledWithPred(); ++I) {
2422 I->unbundleFromPred();
2423 // Set Head to the non-debug instruction.
2424 if (!I->isDebugInstr())
2425 Head = I;
2426 }
2427 } else {
2428 // This means that only one original instruction is
2429 // left in the bundle. We need to "unbundle" it because the
2430 // rest of API will not like it.
2431 ++Head;
2432 if (Head->isBundledWithPred())
2433 Head->unbundleFromPred();
2434 if (Head->isBundledWithSucc())
2435 Head->unbundleFromSucc();
2436 }
2437 } else
2438 llvm_unreachable("Corrupt bundle");
2439 }
2440
2441 LLVM_DEBUG(dbgs() << "\t\t\t[Rem] New Head : "; DumpPacket(Head));
2442 SourceLocation = Head;
2443
2444 // The old header could be listed in the back tracking,
2445 // so if it is, we need to update it.
2446 for (unsigned i = 0; i < backtrack.size(); ++i)
2447 if (backtrack[i] == &*Outcast)
2448 backtrack[i] = &*Head;
2449
2450 // Same for top MI iterator.
2451 if (NextMI == Outcast)
2452 NextMI = Head;
2453
2454 HomeBB->erase(I: Outcast);
2455}
2456
2457#ifndef NDEBUG
2458static void debugLivenessForBB(const MachineBasicBlock *MBB,
2459 const TargetRegisterInfo *TRI) {
2460 LLVM_DEBUG(dbgs() << "\tLiveness for BB:\n"; MBB->dump());
2461 for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
2462 SE = MBB->succ_end();
2463 SI != SE; ++SI) {
2464 LLVM_DEBUG(dbgs() << "\tSuccessor BB (" << (*SI)->getNumber() << "):");
2465 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
2466 E = (*SI)->livein_end();
2467 I != E; ++I)
2468 LLVM_DEBUG(dbgs() << "\t" << printReg((*I).PhysReg, TRI));
2469 LLVM_DEBUG(dbgs() << "\n");
2470 }
2471}
2472#endif
2473
2474// Blocks should be considered empty if they contain only debug info;
2475// else the debug info would affect codegen.
2476static bool IsEmptyBlock(MachineBasicBlock *MBB) {
2477 if (MBB->empty())
2478 return true;
2479 for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
2480 MBBI != MBBE; ++MBBI) {
2481 if (!MBBI->isDebugInstr())
2482 return false;
2483 }
2484 return true;
2485}
2486
2487/// Treat given instruction as a branch, go through its operands
2488/// and see if any of them is a BB address. If so, return it.
2489/// Return NULL otherwise.
2490static inline MachineBasicBlock *getBranchDestination(MachineInstr *MI) {
2491 if (!MI || !MI->isBranch() || MI->isBundle())
2492 return NULL;
2493
2494 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2495 const MachineOperand &MO = MI->getOperand(i);
2496 if (MO.isMBB())
2497 return MO.getMBB();
2498 }
2499 return NULL;
2500}
2501
2502/// Similar to HexagonInstrInfo::analyzeBranch but handles
2503/// serveral more general cases including parsing empty BBs when possible.
2504bool HexagonGlobalSchedulerImpl::AnalyzeBBBranches(MachineBasicBlock *MBB,
2505 MachineBasicBlock *&TBB,
2506 MachineInstr *&FirstTerm,
2507 MachineBasicBlock *&FBB,
2508 MachineInstr *&SecondTerm) {
2509 // Hexagon allowes up to two jumps in MBB.
2510 FirstTerm = NULL;
2511 SecondTerm = NULL;
2512
2513 LLVM_DEBUG(dbgs() << "\n\t\tAnalyze Branches in BB(" << MBB->getNumber()
2514 << ")\n");
2515 if (MBB->succ_size() == 0) {
2516 LLVM_DEBUG(dbgs() << "\n\t\tBlock has no successors.\n");
2517 return true;
2518 }
2519 // Find both jumps.
2520 // We largely rely on implied assumption that BB branching always
2521 // looks like this:
2522 // J2_jumpf %P0, <BB#60>, %PC<imp-def>;
2523 // J2_jump <BB#49>
2524 // Branches also could be in different packets.
2525 MachineBasicBlock::instr_iterator MIB = MBB->instr_begin();
2526 MachineBasicBlock::instr_iterator MIE = MBB->instr_end();
2527 MachineBasicBlock::instr_iterator MII = MIB;
2528
2529 if (QII->nonDbgBBSize(BB: MBB) == 1) {
2530 MII = MBB->getFirstNonDebugInstr().getInstrIterator();
2531 if (MII->isBranch())
2532 FirstTerm = &*MII;
2533 } else {
2534 // We have already eliminated the case when MIB == MIE.
2535 while (MII != MIE) {
2536 if (!MII->isBundle() && MII->isBranch()) {
2537 if (!FirstTerm)
2538 FirstTerm = &*MII;
2539 else
2540 SecondTerm = &*MII;
2541 }
2542 ++MII;
2543 }
2544 }
2545 if ((FirstTerm && FirstTerm->isIndirectBranch()) ||
2546 (SecondTerm && SecondTerm->isIndirectBranch())) {
2547 LLVM_DEBUG(dbgs() << "\n\t\tCannot analyze BB with indirect branch.");
2548 return true;
2549 }
2550 if ((FirstTerm && FirstTerm->getOpcode() == Hexagon::J2_jump &&
2551 !FirstTerm->getOperand(i: 0).isMBB()) ||
2552 (SecondTerm && SecondTerm->getOpcode() == Hexagon::J2_jump &&
2553 !SecondTerm->getOperand(i: 0).isMBB())) {
2554 LLVM_DEBUG(
2555 dbgs() << "\n\t\tCannot analyze BB with a branch out of function.");
2556 return true;
2557 }
2558
2559 // Now try to analyze this branch.
2560 SmallVector<MachineOperand, 4> Cond;
2561 if (QII->analyzeBranch(MBB&: *MBB, TBB, FBB, Cond, AllowModify: false)) {
2562 LLVM_DEBUG(dbgs() << "\t\tFail to analyze with analyzeBranch.\n");
2563 LLVM_DEBUG(dbgs() << "\t\tFirst term: "; if (FirstTerm) FirstTerm->dump();
2564 else dbgs() << "None\n";);
2565 // Could not analyze it. See if this is something we can recognize.
2566 TBB = getBranchDestination(MI: FirstTerm);
2567 }
2568 // There are several cases not handled by HexagonInstrInfo::analyzeBranch.
2569 if (!TBB) {
2570 LLVM_DEBUG(dbgs() << "\t\tMissing TBB.\n");
2571 // There is a branch, but TBB is not found.
2572 // The BB could also be empty at this point. See if it is a trivial
2573 // layout case.
2574 if (MBB->succ_size() == 1) {
2575 TBB = *MBB->succ_begin();
2576 LLVM_DEBUG(dbgs() << "\t\tFall through TBB(" << TBB->getNumber()
2577 << ").\n");
2578 return false;
2579 } else if (MBB->succ_size() == 2) {
2580 // This should cover majority of remaining cases.
2581 if (FirstTerm && SecondTerm &&
2582 (QII->isPredicated(MI: *FirstTerm) || QII->isNewValueJump(MI: *FirstTerm)) &&
2583 !QII->isPredicated(MI: *SecondTerm)) {
2584 TBB = getBranchDestination(MI: FirstTerm);
2585 FBB = getBranchDestination(MI: SecondTerm);
2586 LLVM_DEBUG(dbgs() << "\t\tCanonical dual jump layout: TBB("
2587 << TBB->getNumber() << ") FBB(" << FBB->getNumber()
2588 << ").\n");
2589 return false;
2590 } else if (SecondTerm && SecondTerm->getOpcode() == Hexagon::J2_jump &&
2591 SecondTerm->getOperand(i: 0).isMBB()) {
2592 // Look at the second term if I know it, to find out what is the fall
2593 // through for this BB.
2594 FBB = SecondTerm->getOperand(i: 0).getMBB();
2595 assert(MBB->succ_size() == 2 && "Expected exactly 2 successors");
2596 MachineBasicBlock *Succ0 = *MBB->succ_begin();
2597 MachineBasicBlock *Succ1 = *std::next(x: MBB->succ_begin());
2598 if (FBB == Succ0)
2599 TBB = Succ1;
2600 else
2601 TBB = Succ0;
2602 LLVM_DEBUG(dbgs() << "\t\tSecond br is J2_jump TBB(" << TBB->getNumber()
2603 << ") FBB(" << FBB->getNumber() << ").\n");
2604 return false;
2605 } else {
2606 // This might be an empty BB but still with two
2607 // successors set. Try to use CFG layout to sort it out.
2608 // This could happen when last jump was pulled up from a BB, and
2609 // CFG is being updated. At that point this method is called and
2610 // returns best guess possible for TBB/FBB. Fortunately order of those
2611 // is irrelevant, and rather used a worklist for CFG update.
2612 MachineFunction::iterator MBBIter = MBB->getIterator();
2613 MachineFunction &MF = *MBB->getParent();
2614 (void)MF; // supress compiler warning
2615 // If there are no other clues, assume next sequential BB
2616 // in CFG as FBB.
2617 ++MBBIter;
2618 assert(MBBIter != MF.end() && "I give up.");
2619 FBB = &(*MBBIter);
2620 assert(MBB->succ_size() == 2 && "Expected exactly 2 successors");
2621 MachineBasicBlock *S0 = *MBB->succ_begin();
2622 MachineBasicBlock *S1 = *std::next(x: MBB->succ_begin());
2623 if (FBB == S0)
2624 TBB = S1;
2625 else if (FBB == S1) {
2626 TBB = S0;
2627 } else {
2628 // This case can arise when the layout successor basic block (++IMBB)
2629 // got empty during pull-up.
2630 // As a result, ++IMBB is not one of MBB's successors.
2631 MBBIter = MF.begin();
2632 while (!MBB->isSuccessor(MBB: &*MBBIter) && (MBBIter != MF.end()))
2633 ++MBBIter;
2634 assert(MBBIter != MF.end() && "Malformed BB with invalid successors");
2635 FBB = &*MBBIter;
2636 if (FBB == S0)
2637 TBB = S1;
2638 else
2639 TBB = S0;
2640 }
2641 LLVM_DEBUG(dbgs() << "\t\tUse layout TBB(" << TBB->getNumber()
2642 << ") FBB(" << FBB->getNumber() << ").\n");
2643 return false;
2644 }
2645 }
2646 assert(!FirstTerm && "Bad BB");
2647 return true;
2648 }
2649 // Ok, we have TBB, but maybe missing FBB.
2650 if (!FBB && SecondTerm) {
2651 LLVM_DEBUG(dbgs() << "\t\tMissing FBB.\n");
2652 // analyzeBranch could lie to us, ignore it in this case.
2653 // For the canonical case simply take known branch targets.
2654 if ((QII->isPredicated(MI: *FirstTerm) || QII->isNewValueJump(MI: *FirstTerm)) &&
2655 !QII->isPredicated(MI: *SecondTerm)) {
2656 FBB = getBranchDestination(MI: SecondTerm);
2657 } else {
2658 // Second term is also predicated.
2659 // Use CFG layout. Assign layout successor as FBB.
2660 for (MachineBasicBlock *Succ : MBB->successors()) {
2661 if (MBB->isLayoutSuccessor(MBB: Succ))
2662 FBB = Succ;
2663 }
2664 if (FBB == NULL) {
2665 LLVM_DEBUG(dbgs() << "\nNo layout successor found.");
2666 LLVM_DEBUG(dbgs() << "Possibly the layout successor is an empty BB");
2667 return true;
2668 }
2669 if (TBB == FBB)
2670 LLVM_DEBUG(dbgs() << "Malformed branch with useless branch condition";);
2671 }
2672 LLVM_DEBUG(dbgs() << "\t\tSecond term: "; SecondTerm->dump());
2673 } else if (TBB && !FBB) {
2674 // If BB ends in endloop, and it is a single BB hw loop,
2675 // we will have a single terminator, but we can figure FBB
2676 // easily from CFG.
2677 if (MBB->succ_size() == 2) {
2678 MachineBasicBlock *S0 = *MBB->succ_begin();
2679 MachineBasicBlock *S1 = *std::next(x: MBB->succ_begin());
2680 if (TBB == S0)
2681 FBB = S1;
2682 else
2683 FBB = S0;
2684 }
2685 }
2686
2687 LLVM_DEBUG(dbgs() << "\t\tFinal TBB(" << TBB->getNumber() << ").\n";
2688 if (FBB) dbgs() << "\t\tFinal FBB(" << FBB->getNumber() << ").\n";
2689 else dbgs() << "\t\tFinal FBB(None)\n";);
2690 return false;
2691}
2692
2693/// updateBranches - Updates all branches to \p From in the basic block \p
2694/// InBlock to branches to \p To.
2695static void updateBranches(MachineBasicBlock &InBlock, MachineBasicBlock *From,
2696 MachineBasicBlock *To) {
2697 for (MachineBasicBlock::instr_iterator BI = InBlock.instr_begin(),
2698 E = InBlock.instr_end();
2699 BI != E; ++BI) {
2700 MachineInstr *Inst = &*BI;
2701 // Ignore anything that is not a branch.
2702 if (!Inst->isBranch())
2703 continue;
2704 for (MachineInstr::mop_iterator OI = Inst->operands_begin(),
2705 OE = Inst->operands_end();
2706 OI != OE; ++OI) {
2707 MachineOperand &Opd = *OI;
2708 // Look for basic block "From".
2709 if (!Opd.isMBB() || Opd.getMBB() != From)
2710 continue;
2711 // Update it.
2712 Opd.setMBB(To);
2713 }
2714 }
2715}
2716
2717/// Rewrite all predecessors of the old block to go to the fallthrough
2718/// instead.
2719/// NB: Collect predecessors into a snapshot vector before iterating to
2720/// avoid iterator invalidation on MBB's predecessor list. Each call to
2721/// ReplaceUsesOfBlockWith modifies both the successor list of Pred and
2722/// the predecessor list of MBB, which invalidates debug-mode iterators
2723/// (detected by _GLIBCXX_DEBUG).
2724static void updatePredecessors(MachineBasicBlock &MBB,
2725 MachineBasicBlock *MFBB) {
2726 MachineFunction &MF = *MBB.getParent();
2727
2728 if (MFBB->getIterator() == MF.end())
2729 return;
2730
2731 // Snapshot the predecessor list to avoid iterator invalidation.
2732 SmallVector<MachineBasicBlock *, 4> Preds(MBB.pred_begin(), MBB.pred_end());
2733 for (MachineBasicBlock *Pred : Preds) {
2734 if (!Pred->isSuccessor(MBB: &MBB))
2735 continue;
2736 Pred->ReplaceUsesOfBlockWith(Old: &MBB, New: MFBB);
2737 updateBranches(InBlock&: *Pred, From: &MBB, To: MFBB);
2738 }
2739}
2740
2741static void UpdateCFG(MachineBasicBlock *HomeBB, MachineBasicBlock *OriginBB,
2742 MachineInstr *MII, MachineBasicBlock *HomeTBB,
2743 MachineBasicBlock *HomeFBB, MachineInstr *FTA,
2744 MachineInstr *STA,
2745 const MachineBranchProbabilityInfo *MBPI) {
2746 MachineBasicBlock *S2Add = NULL, *S2Remove = NULL;
2747 bool RemoveLSIfPresent = false;
2748 if ((&*MII == FTA) && MII->isConditionalBranch()) {
2749 LLVM_DEBUG(dbgs() << "\nNew firstterm conditional jump added to HomeBB";);
2750 S2Add = HomeTBB;
2751 S2Remove = HomeTBB;
2752 } else if ((&*MII == STA) && MII->isConditionalBranch()) {
2753 LLVM_DEBUG(dbgs() << "\nNew secondterm conditional jump added to HomeBB";);
2754 // AnalyzeBBBranches might not give correct information in this case.
2755 // The branch destination may be a symbol, not necessarily a block.
2756 if (MachineBasicBlock *Dest = getBranchDestination(MI: MII)) {
2757 LLVM_DEBUG(dbgs() << "\nBranch destination for pulled instruction is BB#"
2758 << Dest->getNumber(););
2759 S2Add = Dest;
2760 S2Remove = Dest;
2761 }
2762 } else if ((&*MII == FTA) && MII->isUnconditionalBranch()) {
2763 LLVM_DEBUG(dbgs() << "\nNew firstterm unconditional jump added to HomeBB";);
2764 S2Add = HomeTBB;
2765 S2Remove = HomeTBB;
2766 RemoveLSIfPresent = true;
2767 } else if ((&*MII == STA) && MII->isUnconditionalBranch()) {
2768 LLVM_DEBUG(
2769 dbgs() << "\nNew secondterm unconditional jump added to HomeBB";);
2770 S2Add = HomeFBB;
2771 S2Remove = HomeFBB;
2772 RemoveLSIfPresent = true;
2773 }
2774 if (S2Add && !HomeBB->isSuccessor(MBB: S2Add)) {
2775 HomeBB->addSuccessor(Succ: S2Add, Prob: MBPI->getEdgeProbability(Src: OriginBB, Dst: S2Add));
2776 }
2777 if (S2Remove)
2778 OriginBB->removeSuccessor(Succ: S2Remove);
2779 if (RemoveLSIfPresent) {
2780 MachineFunction::iterator HomeBBLS = HomeBB->getIterator();
2781 ++HomeBBLS;
2782 if (HomeBBLS != HomeBB->getParent()->end() &&
2783 HomeBB->isLayoutSuccessor(MBB: &*HomeBBLS)) {
2784 LLVM_DEBUG(dbgs() << "\nRemoving LayoutSucc BB#" << HomeBBLS->getNumber()
2785 << "from list of successors";);
2786 HomeBB->removeSuccessor(Succ: &*HomeBBLS);
2787 }
2788 }
2789}
2790
2791/// Move instruction from/to BB, Update liveness info,
2792/// return pointer to the newly inserted and modified
2793/// instruction.
2794MachineInstr *HexagonGlobalSchedulerImpl::MoveAndUpdateLiveness(
2795 BasicBlockRegion *CurrentRegion, MachineBasicBlock *HomeBB,
2796 MachineInstr *InstrToMove, bool NeedToNewify, unsigned DepReg,
2797 bool MovingDependentOp, MachineBasicBlock *OriginBB,
2798 MachineInstr *OriginalInstruction, SmallVector<MachineOperand, 4> &Cond,
2799 MachineBasicBlock::iterator &SourceLocation,
2800 MachineBasicBlock::iterator &TargetPacket,
2801 MachineBasicBlock::iterator &NextMI,
2802 std::vector<MachineInstr *> &backtrack) {
2803 LLVM_DEBUG(
2804 dbgs() << "\n...............[MoveAndUpdateLiveness]..............\n");
2805 LLVM_DEBUG(dbgs() << "\t\tInstrToMove :\t"; InstrToMove->dump());
2806 LLVM_DEBUG(dbgs() << "\t\tOriginalInstruction:\t";
2807 OriginalInstruction->dump());
2808 LLVM_DEBUG(dbgs() << "\t\tSourceLocation :\t";
2809 DumpPacket(SourceLocation.getInstrIterator()));
2810 LLVM_DEBUG(dbgs() << "\t\tTargetPacket :\t";
2811 DumpPacket(TargetPacket.getInstrIterator()));
2812
2813 MachineBasicBlock::instr_iterator OriginalHead =
2814 SourceLocation.getInstrIterator();
2815 MachineBasicBlock::instr_iterator OriginalTail = getBundleEnd(I: OriginalHead);
2816 MachineBasicBlock::instr_iterator OutcastFrom =
2817 OriginalInstruction->getIterator();
2818
2819 // Remove our temporary instruction.
2820 MachineBasicBlock::instr_iterator kill_it(InstrToMove);
2821 HomeBB->erase(I: kill_it);
2822
2823 MachineBasicBlock::instr_iterator TargetHead(TargetPacket.getInstrIterator());
2824 MachineBasicBlock::instr_iterator TargetTail = getBundleEnd(I: TargetHead);
2825
2826 LLVM_DEBUG(dbgs() << "\n\tTo BB before:\n"; debugLivenessForBB(HomeBB, QRI));
2827 LLVM_DEBUG(dbgs() << "\n\tFrom BB before:\n";
2828 debugLivenessForBB(OriginBB, QRI));
2829
2830 // Before we perform the move, we need to collect the worklist
2831 // of BBs for liveness updated.
2832 std::list<MachineBasicBlock *> WorkList;
2833
2834 // Insert into the work list all BBs along the backtrace.
2835 for (std::vector<MachineInstr *>::iterator RI = backtrack.begin(),
2836 RIE = backtrack.end();
2837 RI != RIE; RI++)
2838 WorkList.push_back(x: (*RI)->getParent());
2839
2840 // Only keep unique entries.
2841 // TODO: Use a different container here.
2842 WorkList.unique();
2843
2844 // Move the original instruction.
2845 // If this instruction is inside a bundle, update the bundle.
2846 MachineBasicBlock::instr_iterator BBEnd =
2847 TargetHead->getParent()->instr_end();
2848 bool LastInstructionInBundle = false;
2849 MachineBasicBlock::instr_iterator MII = findInsertPositionInBundle(
2850 Bundle&: TargetPacket, MI: &*OutcastFrom, LastInBundle&: LastInstructionInBundle);
2851
2852 (void)BBEnd;
2853 LLVM_DEBUG(dbgs() << "\n\t\t\tHead target : "; DumpPacket(TargetHead));
2854 LLVM_DEBUG(dbgs() << "\t\t\tTail target : ";
2855 DumpPacket(TargetTail, BBEnd));
2856 LLVM_DEBUG(dbgs() << "\t\t\tInsert right before: "; DumpPacket(MII, BBEnd));
2857
2858 MIBundleBuilder Bundle(&*TargetHead);
2859
2860 // Actual move. One day liveness might be updated here.
2861 if (OriginalInstruction->isBundled()) {
2862 Bundle.insert(I: MII, MI: OriginalInstruction->removeFromBundle());
2863 --MII;
2864 } else {
2865 // This is one case currently unhandled by Bundle.insert
2866 // and needs to be fixed upstream. Meanwhile use old way to handle
2867 // this odd case.
2868 if (OriginalInstruction->getIterator() == TargetTail) {
2869 LLVM_DEBUG(dbgs() << "\t\t\tSpecial case move.\n");
2870 MachineBasicBlock::instr_iterator MIIToPred = MII;
2871 --MIIToPred;
2872 LLVM_DEBUG(dbgs() << "\t\t\tInser after : ";
2873 DumpPacket(MIIToPred, BBEnd));
2874 // Unbundle it in its current location.
2875 if (OutcastFrom->isBundledWithSucc()) {
2876 OutcastFrom->clearFlag(Flag: MachineInstr::BundledSucc);
2877 OutcastFrom->clearFlag(Flag: MachineInstr::BundledPred);
2878 } else if (OutcastFrom->isBundledWithPred()) {
2879 OutcastFrom->unbundleFromPred();
2880 }
2881 HomeBB->splice(Where: MII, Other: OriginBB, From: OutcastFrom);
2882 if (!MII->isBundledWithPred())
2883 MII->bundleWithPred();
2884 if (!LastInstructionInBundle && !MII->isBundledWithSucc())
2885 MII->bundleWithSucc();
2886 // This is the instruction after which we have inserted.
2887 if (!MIIToPred->isBundledWithSucc())
2888 MIIToPred->bundleWithSucc();
2889 } else {
2890 Bundle.insert(I: MII, MI: OriginalInstruction->removeFromParent());
2891 --MII;
2892 }
2893 }
2894 // Source location bundle is updated later in the
2895 // removeInstructionFromExistingBundle().
2896
2897 LLVM_DEBUG(dbgs() << "\t\t\tNew packet head: "; DumpPacket(TargetHead));
2898 LLVM_DEBUG(dbgs() << "\t\t\tInserted op : "; MII->dump());
2899 LLVM_DEBUG(dbgs() << "\n\tTo BB after move:\n";
2900 debugLivenessForBB(HomeBB, QRI));
2901 LLVM_DEBUG(dbgs() << "\n\tFrom BB after:\n";
2902 debugLivenessForBB(OriginBB, QRI));
2903
2904 // Update kill patterns. Do it before we have predicated the moved
2905 // instruction.
2906 updateKillAlongThePath(HomeBB, OriginBB, Head&: MII, Tail&: TargetTail, SourcePacket&: SourceLocation,
2907 TargetPacket, backtrack);
2908 // I need to know:
2909 // - true/false predication
2910 // - do I need to .new it?
2911 // - do I need to .old it?
2912 // If the original instruction used new value operands,
2913 // it might need to be changed to the generic form
2914 // before further processing.
2915 if (QII->isDotNewInst(MI: *MII)) {
2916 DemoteToDotOld(MI: &*MII);
2917 LLVM_DEBUG(dbgs() << "\t\t\tDemoted to .old\t:"; MII->dump());
2918 }
2919
2920 // We have previously checked whether this instruction could
2921 // be placed in this packet, including all possible transformations
2922 // it might need, so if any request will fail now, something is wrong.
2923 //
2924 // Need for predication and the exact condition is determined by
2925 // the path between original and current instruction location.
2926 if (!Cond.empty()) { // To be predicated
2927 LLVM_DEBUG(dbgs() << "\t\t\tPredicating:"; MII->dump());
2928 assert(TII->isPredicable(*MII) && "MII is not predicable");
2929 TII->PredicateInstruction(MI&: *MII, Pred: Cond);
2930 if (NeedToNewify) {
2931 assert((DepReg < std::numeric_limits<unsigned>::max()) &&
2932 "Invalid pred reg value");
2933 LLVM_DEBUG(dbgs() << "\t\t\tNeeds to NEWify on Reg("
2934 << printReg(DepReg, QRI) << ").\n");
2935 int NewOpcode = QII->getDotNewPredOp(MI: *MII, MBPI);
2936 MII->setDesc(QII->get(Opcode: NewOpcode));
2937
2938 // Now we need to mark newly created predicate operand as
2939 // internal read.
2940 // TODO: Better look for predicate operand.
2941 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
2942 MachineOperand &MO = MII->getOperand(i);
2943 if (!MO.isReg())
2944 continue;
2945 if (MO.isDef())
2946 continue;
2947 if (DepReg == MO.getReg())
2948 MO.setIsInternalRead();
2949 }
2950 }
2951 LLVM_DEBUG(dbgs() << "\t\t\tNew predicated form:\t"; MII->dump());
2952 // If the predicate has changed kill pattern, now we need to propagate
2953 // that again. This is important for liveness computation.
2954 updateKillAlongThePath(HomeBB, OriginBB, Head&: MII, Tail&: TargetTail, SourcePacket&: SourceLocation,
2955 TargetPacket, backtrack);
2956 }
2957
2958 // Create new bundle header, remove the old one.
2959 addInstructionToExistingBundle(HomeBB, Head&: TargetHead, Tail&: TargetTail, NewMI&: MII,
2960 TargetPacket, NextMI, backtrack);
2961
2962 // If moved instruction was inside a bundle, update that bundle.
2963 removeInstructionFromExistingBundle(HomeBB: OriginBB, Head&: ++OriginalHead, Tail&: OriginalTail,
2964 SourceLocation, NextMI, MovingDependentOp,
2965 backtrack);
2966
2967 // If removed instruction could have been dependent on any
2968 // of the remaining ops, we need to oldify possible affected ones.
2969 LLVM_DEBUG(dbgs() << "\t\tTargetHead:\t"; DumpPacket(TargetHead, BBEnd));
2970 LLVM_DEBUG(dbgs() << "\t\tOriginalHead:\t"; DumpPacket(OriginalHead, BBEnd));
2971 LLVM_DEBUG(dbgs() << "\t\tOriginalInstruction:\t";
2972 DumpPacket(OriginalInstruction->getIterator(), BBEnd));
2973 LLVM_DEBUG(dbgs() << "\t\tOutcastFrom:\t"; DumpPacket(OutcastFrom, BBEnd));
2974
2975 // Clean up the original source bundle on a global scope.
2976 if (OriginalHead != MachineBasicBlock::instr_iterator() &&
2977 QII->isEndLoopN(Opcode: OriginalHead->getOpcode())) {
2978 // Single endloop left. Since it is not a real instruction,
2979 // we can simply add it to a non empty previous bundle, if one exist,
2980 // or let assembler to produce a fake bundle for it.
2981 LLVM_DEBUG(dbgs() << "\t\tOnly endloop in packet.\n");
2982 MachineBasicBlock::instr_iterator I(OriginalHead);
2983 if (OriginBB->begin() != I) {
2984 --I;
2985 if (I->isBundled()) {
2986 if (!I->isBundledWithSucc())
2987 I->bundleWithSucc();
2988 if (!OriginalHead->isBundledWithPred())
2989 OriginalHead->bundleWithPred();
2990 }
2991 // else we probably need to create a new bundle here.
2992 // SourceLocation = NULL;
2993 }
2994 } else if (MovingDependentOp &&
2995 OriginalHead != MachineBasicBlock::instr_iterator()) {
2996 if (OriginalHead->isBundled()) {
2997 for (MachineBasicBlock::instr_iterator J = ++OriginalHead;
2998 J != OriginalTail && J->isInsideBundle() && !J->isBundle(); ++J) {
2999 // Need to oldify it.
3000 if (MIsHaveTrueDependency(MIa: OriginalInstruction, MIb: &*J) &&
3001 QII->isDotNewInst(MI: *J)) {
3002 LLVM_DEBUG(dbgs() << "\t\tDemoting to .old:\t"; J->dump());
3003 DemoteToDotOld(MI: &*J);
3004 }
3005 }
3006 } else {
3007 // Single instruction left.
3008 if (MIsHaveTrueDependency(MIa: OriginalInstruction, MIb: &*OriginalHead) &&
3009 QII->isDotNewInst(MI: *OriginalHead)) {
3010 LLVM_DEBUG(dbgs() << "\t\tDemoting to .old op:\t";
3011 OriginalHead->dump());
3012 DemoteToDotOld(MI: &*OriginalHead);
3013 }
3014 }
3015 }
3016
3017 // Now we need to update liveness to all BBs involved
3018 // including those we might have "passed" through on the way here.
3019 LLVM_DEBUG(dbgs() << "\n\tTo BB after bundle update:\n"; HomeBB->dump());
3020 LLVM_DEBUG(dbgs() << "\n\n\tFrom BB after bundle update:\n";
3021 OriginBB->dump());
3022
3023 // Update global liveness.
3024 LLVM_DEBUG(dbgs() << "\n\tWorkList:\t");
3025 for (std::list<MachineBasicBlock *>::iterator BBI = WorkList.begin(),
3026 BBIE = WorkList.end();
3027 BBI != BBIE; BBI++) {
3028 LLVM_DEBUG(dbgs() << "BB#" << (*BBI)->getNumber() << " ");
3029 }
3030 LLVM_DEBUG(dbgs() << "\n");
3031
3032 do {
3033 MachineBasicBlock *BB = WorkList.back();
3034 WorkList.pop_back();
3035 CurrentRegion->getLivenessInfoForBB(MBB: BB)->UpdateLiveness(MBB: BB);
3036 } while (!WorkList.empty());
3037
3038 // No need to analyze for empty BB or update CFG for same BB pullup.
3039 if (OriginBB == HomeBB)
3040 return &*TargetHead;
3041 // If the instruction moved was a branch we need to update the
3042 // successor/predecessor of OriginBB and HomeBB accordingly.
3043 MachineBasicBlock *HomeTBB, *HomeFBB;
3044 MachineInstr *FTA = NULL, *STA = NULL;
3045 bool HomeBBAnalyzed = !AnalyzeBBBranches(MBB: HomeBB, TBB&: HomeTBB, FirstTerm&: FTA, FBB&: HomeFBB, SecondTerm&: STA);
3046 if (MII->isBranch()) {
3047 if (HomeBBAnalyzed) {
3048 UpdateCFG(HomeBB, OriginBB, MII: &*MII, HomeTBB, HomeFBB, FTA, STA, MBPI);
3049 } else {
3050 llvm_unreachable("Underimplememted AnalyzeBBBranches");
3051 }
3052 }
3053 // If we have exhausted the OriginBB clean it up.
3054 // Beware that we could have created dual conditional jumps, which
3055 // ultimately means we can have three way jumps.
3056 if (IsEmptyBlock(MBB: OriginBB) && !OriginBB->isEHPad() &&
3057 !OriginBB->hasAddressTaken() && !OriginBB->succ_empty()) {
3058 // Dead block? Unlikely, but check.
3059 LLVM_DEBUG(dbgs() << "Empty BB(" << OriginBB->getNumber() << ").\n");
3060 // Update region map.
3061 CurrentRegion->RemoveBBFromRegion(MBB: OriginBB);
3062 // Keep the list of empty basic blocks to be freed later.
3063 EmptyBBs.push_back(x: OriginBB);
3064 if (OriginBB->pred_empty() || OriginBB->succ_empty())
3065 return &*TargetHead;
3066
3067 if (OriginBB->succ_size() == 1) {
3068 // Find empty block's successor.
3069 MachineBasicBlock *CommonFBB = *OriginBB->succ_begin();
3070 updatePredecessors(MBB&: *OriginBB, MFBB: CommonFBB);
3071 // Remove the only successor entry for empty BB.
3072 OriginBB->removeSuccessor(Succ: CommonFBB);
3073 } else {
3074 // Three way branching is not yet fully supported.
3075 assert((OriginBB->succ_size() == 2) && "Underimplemented 3way branch.");
3076 MachineBasicBlock *OriginTBB, *OriginFBB;
3077 MachineInstr *FTB = NULL, *STB = NULL;
3078
3079 LLVM_DEBUG(dbgs() << "\tComplex case.\n");
3080 if (HomeBBAnalyzed &&
3081 !AnalyzeBBBranches(MBB: OriginBB, TBB&: OriginTBB, FirstTerm&: FTB, FBB&: OriginFBB, SecondTerm&: STB)) {
3082 assert(OriginFBB && "Missing Origin FBB");
3083 if (HomeFBB == OriginBB) {
3084 // OriginBB is FBB for HomeBB.
3085 if (HomeTBB == OriginTBB) {
3086 // Shared TBB target, common FBB.
3087 updatePredecessors(MBB&: *OriginBB, MFBB: OriginFBB);
3088 } else if (HomeTBB == OriginFBB) {
3089 // Shared TBB target, common FBB.
3090 updatePredecessors(MBB&: *OriginBB, MFBB: OriginTBB);
3091 } else {
3092 // Three way branch. Add new successor to HomeBB.
3093 updatePredecessors(MBB&: *OriginBB, MFBB: OriginFBB);
3094 // TODO: Update the weight as well.
3095 // Adding the successor to make updatePredecessor happy.
3096 HomeBB->addSuccessor(Succ: OriginBB);
3097 updatePredecessors(MBB&: *OriginBB, MFBB: OriginTBB);
3098 }
3099 } else if (HomeTBB == OriginBB) {
3100 // OriginBB is TBB for HomeBB.
3101 if (HomeFBB == OriginTBB) {
3102 // Shared TBB target, common FBB.
3103 updatePredecessors(MBB&: *OriginBB, MFBB: OriginFBB);
3104 } else if (HomeFBB == OriginFBB) {
3105 // Shared TBB target, common FBB.
3106 updatePredecessors(MBB&: *OriginBB, MFBB: OriginTBB);
3107 } else {
3108 // Three way branch. Add new successor to HomeBB.
3109 updatePredecessors(MBB&: *OriginBB, MFBB: OriginFBB);
3110 // TODO: Update the weight as well.
3111 // Adding the successor to make updatePredecessor happy.
3112 HomeBB->addSuccessor(Succ: OriginBB);
3113 updatePredecessors(MBB&: *OriginBB, MFBB: OriginTBB);
3114 }
3115 } else
3116 llvm_unreachable("CFG update failed");
3117 // The empty BB can now be relieved of its successors.
3118 OriginBB->removeSuccessor(Succ: OriginFBB);
3119 OriginBB->removeSuccessor(Succ: OriginTBB);
3120 } else
3121 llvm_unreachable("Underimplemented analyzeBranch");
3122 }
3123 LLVM_DEBUG(dbgs() << "Updated BB(" << HomeBB->getNumber() << ").\n";
3124 HomeBB->dump());
3125 }
3126 return &*TargetHead;
3127}
3128
3129// Find where inside a given bundle current instruction should be inserted.
3130// Instruction will be inserted _before_ this position.
3131MachineBasicBlock::instr_iterator
3132HexagonGlobalSchedulerImpl::findInsertPositionInBundle(
3133 MachineBasicBlock::iterator &Bundle, MachineInstr *MI, bool &LastInBundle) {
3134 MachineBasicBlock::instr_iterator MII = Bundle.getInstrIterator();
3135 MachineBasicBlock *MBB = MII->getParent();
3136 MachineBasicBlock::instr_iterator BBEnd = MBB->instr_end();
3137 MachineBasicBlock::instr_iterator FirstBranch = BBEnd;
3138 MachineBasicBlock::instr_iterator LastBundledInstruction = BBEnd;
3139 MachineBasicBlock::instr_iterator DualJumpFirstCandidate = BBEnd;
3140
3141 assert(MII->isBundle() && "Missing insert location");
3142 bool isDualJumpSecondCandidate = IsDualJumpSecondCandidate(MI);
3143 LastInBundle = false;
3144
3145 for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
3146 ++MII) {
3147 if (MII->isBranch() && (FirstBranch == BBEnd))
3148 FirstBranch = MII;
3149 // If what we insert is a dual jump, we need to find
3150 // first jump, and insert new instruction after it.
3151 if (isDualJumpSecondCandidate && IsDualJumpFirstCandidate(MI: &*MII))
3152 DualJumpFirstCandidate = MII;
3153 LastBundledInstruction = MII;
3154 }
3155
3156 if (DualJumpFirstCandidate != BBEnd) {
3157 // First respect dual jumps.
3158 ++DualJumpFirstCandidate;
3159 if (DualJumpFirstCandidate == BBEnd ||
3160 DualJumpFirstCandidate == LastBundledInstruction)
3161 LastInBundle = true;
3162 return DualJumpFirstCandidate;
3163 } else if (FirstBranch != BBEnd) {
3164 // If we have no dual jumps, but do have a single
3165 // branch in the bundle, add our new instruction
3166 // right before it.
3167 return FirstBranch;
3168 } else if (LastBundledInstruction != BBEnd) {
3169 LastInBundle = true;
3170 return ++LastBundledInstruction;
3171 } else
3172 llvm_unreachable("Lost in bundle");
3173 return MBB->instr_begin();
3174}
3175
3176/// This function for now needs to try to insert new instruction
3177/// in correct serial semantics fashion - i.e. find "correct" insert
3178/// point for instruction as if inserting in serial sequence.
3179MachineBasicBlock::instr_iterator HexagonGlobalSchedulerImpl::insertTempCopy(
3180 MachineBasicBlock *MBB, MachineBasicBlock::iterator &TargetPacket,
3181 MachineInstr *MI, bool DeleteOldCopy) {
3182 MachineBasicBlock::instr_iterator MII;
3183 MachineBasicBlock *CurrentBB = MI->getParent();
3184
3185 assert(CurrentBB && "Corrupt instruction");
3186 // Create a temporary copy of the instruction we are considering.
3187 // LLVM refuses to deal with an instruction which was not inserted
3188 // to any BB. We can visit multiple BBs on the way "up", so we
3189 // create a temp copy of the original instruction and delete it later.
3190 // It is way cheaper than using splice and then
3191 // needing to undo it most of the time.
3192 MachineInstr *NewMI = MI->getParent()->getParent()->CloneMachineInstr(Orig: MI);
3193 // Make sure all bundling flags are cleared.
3194 if (NewMI->isBundledWithPred())
3195 NewMI->unbundleFromPred();
3196 if (NewMI->isBundledWithSucc())
3197 NewMI->unbundleFromSucc();
3198
3199 if (DeleteOldCopy) {
3200 // Remove our temporary instruction.
3201 // MachineBasicBlock::erase method calls unbundleSingleMI()
3202 // prior to deletion, so we do not have to do it here.
3203 MachineBasicBlock::instr_iterator kill_it(MI);
3204 CurrentBB->erase(I: kill_it);
3205 }
3206
3207 // If the original instruction used new value operands,
3208 // it might need to be changed to generic form
3209 // before further processing.
3210 if (QII->isDotNewInst(MI: *NewMI))
3211 DemoteToDotOld(MI: NewMI);
3212
3213 // Insert new temporary instruction.
3214 // If this is the destination packet, insert the tmp after
3215 // its header. Otherwise, as second instr in BB.
3216 if (TargetPacket->getParent() == MBB) {
3217 MII = TargetPacket.getInstrIterator();
3218
3219 if (MII->isBundled()) {
3220 bool LastInBundle = false;
3221 MachineBasicBlock::instr_iterator InsertBefore =
3222 findInsertPositionInBundle(Bundle&: TargetPacket, MI: NewMI, LastInBundle);
3223 MIBundleBuilder Bundle(&*TargetPacket);
3224 Bundle.insert(I: InsertBefore, MI: NewMI);
3225 } else
3226 MBB->insertAfter(I: MII, MI: NewMI);
3227 } else {
3228 MII = MBB->instr_begin();
3229
3230 // Skip debug instructions.
3231 while (MII->isDebugInstr())
3232 MII++;
3233
3234 if (MII->isBundled()) {
3235 MIBundleBuilder Bundle(&*MII);
3236 Bundle.insert(I: ++MII, MI: NewMI);
3237 } else
3238 MBB->insertAfter(I: MII, MI: NewMI);
3239 }
3240 return NewMI->getIterator();
3241}
3242
3243// Check for a conditionally assigned register within the block.
3244bool HexagonGlobalSchedulerImpl::MIsCondAssign(MachineInstr *BMI,
3245 MachineInstr *MI,
3246 SmallVector<unsigned, 4> &Defs) {
3247 if (!QII->isPredicated(MI: *BMI))
3248 return false;
3249 // Its a conditional instruction, now is it the same registers as MI?
3250 SmallVector<unsigned, 4> CondDefs;
3251 SmallVector<unsigned, 8> CondUses;
3252 parseOperands(MI: BMI, Defs&: CondDefs, Uses&: CondUses);
3253
3254 for (SmallVector<unsigned, 4>::iterator ID = Defs.begin(), IDE = Defs.end();
3255 ID != IDE; ++ID) {
3256 for (SmallVector<unsigned, 4>::iterator CID = CondDefs.begin(),
3257 CIDE = CondDefs.end();
3258 CID != CIDE; ++CID) {
3259 if (AliasingRegs(RegA: *CID, RegB: *ID)) {
3260 LLVM_DEBUG(dbgs() << "\tFound conditional def, can't move\n";
3261 BMI->dump());
3262 return true;
3263 }
3264 }
3265 }
3266 return false;
3267}
3268
3269// Returns the Union of all the elements in Set1 and
3270// Union of all the elements in Set2 separately.
3271// Constraints:
3272// Set1 and Set2 should contain an entry for each element in Range.
3273template <typename ElemType, typename IndexType>
3274void Unify(std::vector<ElemType> Range,
3275 std::map<ElemType, std::vector<IndexType>> &Set1,
3276 std::map<ElemType, std::vector<IndexType>> &Set2,
3277 std::pair<std::vector<IndexType>, std::vector<IndexType>> &UnionSet,
3278 unsigned union_size = 100) {
3279 typedef
3280 typename std::map<ElemType, std::vector<IndexType>>::iterator PosIter_t;
3281 typedef typename std::vector<IndexType>::iterator IndexIter_t;
3282 std::vector<IndexType> &Union1 = UnionSet.first;
3283 std::vector<IndexType> &Union2 = UnionSet.second;
3284 Union1.resize(union_size, 0);
3285 Union2.resize(union_size, 0);
3286 LLVM_DEBUG(dbgs() << "\n\t\tElements in the range:\n";);
3287 typename std::vector<ElemType>::iterator iter = Range.begin();
3288 while (iter != Range.end()) {
3289 if ((*iter)->isDebugInstr()) {
3290 ++iter;
3291 continue;
3292 }
3293 LLVM_DEBUG((*iter)->dump());
3294 PosIter_t set1_pos = Set1.find(*iter);
3295 assert(set1_pos != Set1.end() &&
3296 "Set1 should contain an entry for each element in Range.");
3297 IndexIter_t set1idx = set1_pos->second.begin();
3298 while (set1idx != set1_pos->second.end()) {
3299 Union1[*set1idx] = 1;
3300 ++set1idx;
3301 }
3302 PosIter_t set2_pos = Set2.find(*iter);
3303 assert(set2_pos != Set2.end() &&
3304 "Set2 should contain an entry for each element in Range.");
3305 IndexIter_t set2idx = set2_pos->second.begin();
3306 while (set2idx != set2_pos->second.end()) {
3307 Union2[*set2idx] = 1;
3308 ++set2idx;
3309 }
3310 ++iter;
3311 }
3312}
3313
3314static void UpdateBundle(MachineInstr *BundleHead) {
3315 assert(BundleHead->isBundle() && "Not a bundle header");
3316 if (!BundleHead)
3317 return;
3318 unsigned Size = BundleHead->getBundleSize();
3319 if (Size >= 2)
3320 return;
3321 if (Size == 1) {
3322 MachineBasicBlock::instr_iterator MIter = BundleHead->getIterator();
3323 MachineInstr *MI = &*(++MIter);
3324 MI->unbundleFromPred();
3325 }
3326 BundleHead->eraseFromParent();
3327}
3328
3329/// Gatekeeper for instruction speculation.
3330/// If all MI defs are dead (not live-in) to any other
3331/// BB but the one we are moving into, and it could not cause
3332/// exception by early execution, allow it to be pulled up.
3333bool HexagonGlobalSchedulerImpl::canMIBeSpeculated(
3334 MachineInstr *MI, MachineBasicBlock *ToBB, MachineBasicBlock *FromBB,
3335 std::vector<MachineInstr *> &backtrack) {
3336 // For now disallow memory accesses from speculation.
3337 // Generally we can check if they potentially may trap/cause an exception.
3338 if (!EnableSpeculativePullUp || !MI || MI->mayStore())
3339 return false;
3340
3341 LLVM_DEBUG(dbgs() << "\t[canMIBeSpeculated] From BB(" << FromBB->getNumber()
3342 << "):\t";
3343 MI->dump());
3344 LLVM_DEBUG(dbgs() << "\tTo this BB:\n"; ToBB->dump());
3345
3346 if (!ToBB->isSuccessor(MBB: FromBB))
3347 return false;
3348
3349 // This is a very tricky topic. Speculating arithmetic instructions with
3350 // results dead out of a loop more times then required by number of
3351 // iterations is safe, while speculating loads can cause an exception.
3352 // Simplest of checks is to not cross loop exit edge, or in our case
3353 // do not pull-in to a loop exit BB, but there are implications for
3354 // non-natural loops (not recognized by LLVM as loops) and multi-threaded
3355 // code.
3356 if (AllowSpeculateLoads && MI->mayLoad()) {
3357 // Invariant loads should always be safe.
3358 if (!MI->isDereferenceableInvariantLoad())
3359 return false;
3360 LLVM_DEBUG(dbgs() << "\tSpeculating a Load.\n");
3361 }
3362
3363 SmallVector<unsigned, 4> Defs;
3364 SmallVector<unsigned, 8> Uses;
3365 parseOperands(MI, Defs, Uses);
3366
3367 // Do not speculate instructions that modify reserved global registers.
3368 for (unsigned R : Defs)
3369 if (MRI->isReserved(PhysReg: R) && QRI->isGlobalReg(Reg: R))
3370 return false;
3371
3372 for (MachineBasicBlock::const_succ_iterator SI = ToBB->succ_begin(),
3373 SE = ToBB->succ_end();
3374 SI != SE; ++SI) {
3375 // TODO: Allow an instruction (I) which 'defines' the live-in reg (R)
3376 // along the path when I is the first instruction to use the R.
3377 // i.e., I kills R before any other instruction in the BB uses it.
3378 // TODO: We have already parsed live sets - reuse them.
3379 if (*SI == FromBB)
3380 continue;
3381 LLVM_DEBUG(dbgs() << "\tTarget succesor BB to check:\n"; (*SI)->dump());
3382 LLVM_DEBUG(
3383 for (MachineBasicBlock::const_succ_iterator SII = (*SI)->succ_begin(),
3384 SIE = (*SI)->succ_end();
3385 SII != SIE; ++SII)(*SII)
3386 ->dump());
3387 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
3388 E = (*SI)->livein_end();
3389 I != E; ++I)
3390 for (SmallVector<unsigned, 4>::iterator ID = Defs.begin(),
3391 IDE = Defs.end();
3392 ID != IDE; ++ID) {
3393 if (AliasingRegs(RegA: (*I).PhysReg, RegB: *ID))
3394 return false;
3395 }
3396
3397 // Check the successor blocks for conditional define.
3398 // TODO: We should really test the whole path here.
3399 for (MachineBasicBlock::instr_iterator BI = (*SI)->instr_begin(),
3400 E = (*SI)->instr_end();
3401 BI != E; ++BI) {
3402 if (BI->isBundle() || BI->isDebugInstr())
3403 continue;
3404 LLVM_DEBUG(dbgs() << "\t\tcheck against:\t"; BI->dump());
3405 if (MIsCondAssign(BMI: &*BI, MI, Defs))
3406 return false;
3407 }
3408 }
3409 // Taking a very conservative approach during speculation.
3410 // Traverse the path (FromBB, ToBB] and make sure
3411 // that the def-use set of the instruction to be moved
3412 // are not modified.
3413 std::vector<MachineBasicBlock *> PathBB;
3414 for (unsigned i = 0; i < backtrack.size(); ++i) {
3415 // Insert unique BB along the path but skip FromBB
3416 MachineBasicBlock *MBB = backtrack[i]->getParent();
3417 if ((MBB != FromBB) &&
3418 (std::find(first: PathBB.begin(), last: PathBB.end(), val: MBB) == PathBB.end()))
3419 PathBB.push_back(x: MBB);
3420 }
3421 bool WaitingForTargetPacket = true;
3422 MachineBasicBlock::instr_iterator MII;
3423 std::vector<MachineInstr *> TraversalRange;
3424 LLVM_DEBUG(dbgs() << "\n\tElements in the range:");
3425 // TODO: Use just the backtrack to get TraversalRange because it
3426 // contains the path (only when speculated from a path in region).
3427 // Note: We check the dependency of instruction-to-move with
3428 // all the instructions (starting from backtrack[0]) in the parent BBs
3429 // because a BB might have a branching from in between due to packetization
3430 // and just checking packets in the backtrack won't be comprehensive.
3431 for (unsigned i = 0; i < PathBB.size(); ++i) {
3432 for (MII = PathBB[i]->instr_begin(); MII != PathBB[i]->instr_end(); ++MII) {
3433 // Skip instructions until the target packet is found.
3434 // although target packet is already checked for correctness,
3435 // it is good to check here to validate intermediate pullups.
3436 if (backtrack[0] == &*MII)
3437 WaitingForTargetPacket = false;
3438 if (WaitingForTargetPacket)
3439 continue;
3440 if (MII->isBundle())
3441 continue;
3442 // TODO: Ideally we should check that there is a `linear' control flow
3443 // in the TraversalRange in all possible manner. For e.g.,
3444 // BB0 { packet1: if(p0) indirect_jump BB1;
3445 // packet2: jump BB2 }
3446 // BB1 { i1 }. In this case we should not pull `i1' into packet2.
3447 if (MII->isCall() || MII->isReturn() ||
3448 (MII->getOpcode() == Hexagon::J2_jump && !MII->getOperand(i: 0).isMBB()))
3449 return false;
3450 if (MI != &*MII) {
3451 TraversalRange.push_back(x: &*MII);
3452 LLVM_DEBUG(MII->dump(););
3453 }
3454 }
3455 }
3456 // Get the union of def/use set of all the instructions along TraversalRange.
3457 std::pair<std::vector<unsigned>, std::vector<unsigned>> RangeDefUse;
3458 Unify(Range: TraversalRange, Set1&: MIDefSet, Set2&: MIUseSet, UnionSet&: RangeDefUse, union_size: QRI->getNumRegs());
3459 // No instruction (along TraversalRange) should 'define' the use set of MI
3460 for (unsigned j = 0; j < Uses.size(); ++j)
3461 if (RangeDefUse.first[Uses[j]]) {
3462 LLVM_DEBUG(dbgs() << "\n\t\tUnresolved dependency along path to HOME for "
3463 << printReg(Uses[j], QRI););
3464 return false;
3465 }
3466 // No instruction (along TraversalRange) should 'define' or 'use'
3467 // the def set of MI
3468 for (unsigned j = 0; j < Defs.size(); ++j)
3469 if (RangeDefUse.first[Defs[j]] || RangeDefUse.second[Defs[j]]) {
3470 LLVM_DEBUG(dbgs() << "\n\t\tUnresolved dependency along path to HOME for "
3471 << printReg(Defs[j], QRI););
3472 return false;
3473 }
3474 return true;
3475}
3476
3477/// Try to move InstrToMove to TargetPacket using path stored in backtrack.
3478/// SourceLocation is current iterator point. It must be updated to the new
3479/// iteration location after all updates.
3480/// Alogrithm:
3481/// To move an instruction (I) from OriginBB through HomeBB via backtrack.
3482/// for each packet (i) in backtrack, analyzeBranch
3483/// case 1 (success)
3484/// case Pulling from conditional branch:
3485/// if I is predicable
3486/// Try to predicate on the branch condition
3487/// else
3488/// Try to speculate I to backtrack[i].
3489/// case Pulling from unconditional branch:
3490/// Just pullup. (TODO: Speculate here as well)
3491/// case 2 (fails)
3492/// Try to speculate I backtrack[i].
3493bool HexagonGlobalSchedulerImpl::MoveMItoBundle(
3494 BasicBlockRegion *CurrentRegion,
3495 MachineBasicBlock::instr_iterator &InstrToMove,
3496 MachineBasicBlock::iterator &NextMI,
3497 MachineBasicBlock::iterator &TargetPacket,
3498 MachineBasicBlock::iterator &SourceLocation,
3499 std::vector<MachineInstr *> &backtrack, bool MovingDependentOp,
3500 bool PathInRegion) {
3501 MachineBasicBlock *HomeBB = TargetPacket->getParent();
3502 MachineBasicBlock *OriginBB = InstrToMove->getParent();
3503 MachineBasicBlock *CurrentBB = OriginBB;
3504 MachineBasicBlock *CleanupBB = OriginBB;
3505 MachineBasicBlock *PreviousBB = OriginBB;
3506 MachineInstr *OriginalInstructionToMove = &*InstrToMove;
3507
3508 assert(HomeBB && "Missing HomeBB");
3509 assert(OriginBB && "Missing OriginBB");
3510
3511 LLVM_DEBUG(dbgs() << "\n.........[MoveMItoBundle]..............\n");
3512 LLVM_DEBUG(dbgs() << "\t\tInstrToMove :\t"; InstrToMove->dump());
3513 LLVM_DEBUG(dbgs() << "\t\tTargetPacket :\t";
3514 DumpPacket(TargetPacket.getInstrIterator()));
3515 LLVM_DEBUG(dbgs() << "\t\tSourceLocation:\t";
3516 DumpPacket(SourceLocation.getInstrIterator()));
3517
3518 // We do not allow to move instructions in the same BB.
3519 if (HomeBB == OriginBB) {
3520 LLVM_DEBUG(dbgs() << "\t\tSame BB pull-up.\n");
3521 if (!EnableLocalPullUp)
3522 return false;
3523 }
3524
3525 if (OneFloatPerPacket && QII->isFloat(MI: *TargetPacket) &&
3526 QII->isFloat(MI: *InstrToMove))
3527 return false;
3528
3529 if (OneComplexPerPacket && QII->isComplex(MI: *TargetPacket) &&
3530 QII->isComplex(MI: *InstrToMove))
3531 return false;
3532
3533 LLVM_DEBUG(dbgs() << "\t\tWay home:\n");
3534 // Test integrity of the back track.
3535 for (unsigned i = 0; i < backtrack.size(); ++i) {
3536 assert(backtrack[i]->getParent() && "Messed back track.");
3537 LLVM_DEBUG(dbgs() << "\t\t[" << i << "] BB("
3538 << backtrack[i]->getParent()->getNumber() << ")\t";
3539 backtrack[i]->dump());
3540 }
3541 LLVM_DEBUG(dbgs() << "\n");
3542
3543 bool NeedCleanup = false;
3544 bool NeedToPredicate = false;
3545 bool MINeedToNewify = false;
3546 unsigned DepReg = std::numeric_limits<unsigned>::max();
3547 bool isDualJump = false;
3548 SmallVector<MachineOperand, 4> Cond;
3549 SmallVector<MachineOperand, 4> PredCond;
3550 std::vector<MachineInstr *> PullUpPath;
3551 if (PathInRegion)
3552 PullUpPath = backtrack;
3553 else {
3554 PullUpPath.push_back(x: &*TargetPacket);
3555 PullUpPath.push_back(x: &*InstrToMove);
3556 }
3557
3558 // Now start iterating over all instructions
3559 // preceeding the one we are trying to move,
3560 // and see if they could be reodered/bypassed.
3561 for (std::vector<MachineInstr *>::reverse_iterator RI = backtrack.rbegin(),
3562 RIE = backtrack.rend();
3563 RI < RIE; ++RI) {
3564 // Once most of debug will be gone, this will be a real assert.
3565 // assert((backtrack.front() == ToThisBundle) && "Lost my way home.");
3566 MachineInstr *MIWH = *RI;
3567 if (QII->isDotNewInst(MI: *InstrToMove)) {
3568 LLVM_DEBUG(dbgs() << "Cannot move a dot new instruction:";
3569 InstrToMove->dump());
3570 if (NeedCleanup)
3571 CleanupBB->erase(I: InstrToMove);
3572 return false;
3573 }
3574 if (canCauseStall(MI: &*InstrToMove, MJ: MIWH)) {
3575 if (NeedCleanup)
3576 CleanupBB->erase(I: InstrToMove);
3577 return false;
3578 }
3579 LLVM_DEBUG(dbgs() << "\t> Step home BB(" << MIWH->getParent()->getNumber()
3580 << "):\t";
3581 DumpPacket(MIWH->getIterator()));
3582
3583 // See if we cross a jump, and possibly change the form of instruction.
3584 // Passing through BBs with dual jumps in different packets
3585 // takes extra care.
3586 bool isBranchMIWH = isBranch(MI: MIWH);
3587 if (((&*SourceLocation != MIWH) && isBranchMIWH) ||
3588 (CurrentBB != MIWH->getParent())) {
3589 LLVM_DEBUG(dbgs() << "\tChange BB from(" << CurrentBB->getNumber()
3590 << ") to (" << MIWH->getParent()->getNumber() << ")\n");
3591 PreviousBB = CurrentBB;
3592 CurrentBB = MIWH->getParent();
3593
3594 // See what kind of branch we are dealing with.
3595 MachineBasicBlock *PredTBB = NULL;
3596 MachineBasicBlock *PredFBB = NULL;
3597
3598 if (QII->analyzeBranch(MBB&: *CurrentBB, TBB&: PredTBB, FBB&: PredFBB, Cond, AllowModify: false)) {
3599 // We currently do not handle NV jumps of this kind:
3600 // if (cmp.eq(r0.new, #0)) jump:t .LBB12_69
3601 // TODO: Need to handle them.
3602 LLVM_DEBUG(dbgs() << "\tCould not analyze branch.\n");
3603
3604 // This is the main point of lost performance.
3605 // We could try to speculate here, but for that we need accurate
3606 // liveness info, and it is not ready yet.
3607 if (!canMIBeSpeculated(MI: &*InstrToMove, ToBB: CurrentBB, FromBB: PreviousBB,
3608 backtrack&: PullUpPath)) {
3609 if (NeedCleanup)
3610 CleanupBB->erase(I: InstrToMove);
3611 return false;
3612 } else {
3613 // Save speculated instruction moved.
3614 SpeculatedIns.insert(
3615 x: std::make_pair(x&: OriginalInstructionToMove, y&: OriginBB));
3616 LLVM_DEBUG(dbgs() << "\nSpeculatedInsToMove"; InstrToMove->dump());
3617 }
3618
3619 LLVM_DEBUG(dbgs() << "\tSpeculating.\n");
3620 // If we are speculating, we can come through a predication
3621 // into an unconditional branch...
3622 // For now simply bail out.
3623 // TODO: See if this ever happens.
3624 if (NeedToPredicate) {
3625 LLVM_DEBUG(dbgs()
3626 << "\tUnderimplemented pred for speculative move.\n");
3627 if (NeedCleanup)
3628 CleanupBB->erase(I: InstrToMove);
3629 return false;
3630 }
3631 InstrToMove =
3632 insertTempCopy(MBB: CurrentBB, TargetPacket, MI: &*InstrToMove, DeleteOldCopy: NeedCleanup);
3633 NeedCleanup = true;
3634 NeedToPredicate = false;
3635 assert(!NeedToPredicate && "Need to handle predication for this case");
3636 CleanupBB = CurrentBB;
3637 // No need to recheck for resources - instruction did not change.
3638 LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
3639 } else {
3640 bool LocalNeedPredication = true;
3641 // We were able to analyze the branch.
3642 if (!isBranchMIWH && !PredTBB) {
3643 LLVM_DEBUG(dbgs() << "\tDo not need predicate for this case.\n");
3644 LocalNeedPredication = false;
3645 }
3646 // First see if this is a potential dual jump situation.
3647 if (IsDualJumpSecondCandidate(MI: &*InstrToMove) &&
3648 IsDualJumpFirstCandidate(TargetPacket)) {
3649 LLVM_DEBUG(dbgs() << "\tPerforming unrestricted dual jump.\n");
3650 isDualJump = true;
3651 } else if (LocalNeedPredication && (PredFBB != PreviousBB)) {
3652 // Predicate instruction based on condition feeding it.
3653 // This is generally a statefull pull-up path.
3654 // Can this insn be predicated? If so, try to do it.
3655 if (TII->isPredicable(MI: *InstrToMove)) {
3656 if (PredTBB) {
3657 if (PreviousBB != PredTBB) {
3658 // If we "came" not from TBB, we need to invert condition.
3659 if (TII->reverseBranchCondition(Cond)) {
3660 LLVM_DEBUG(dbgs() << "\tUnable to invert condition.\n");
3661 if (NeedCleanup)
3662 CleanupBB->erase(I: InstrToMove);
3663 return false;
3664 }
3665 }
3666 LLVM_DEBUG(dbgs() << "\tTBB(" << PredTBB->getNumber()
3667 << ")InvertCondition("
3668 << (PreviousBB != PredTBB) << ")\n");
3669 }
3670 // Create a new copy of the instruction we are trying to move.
3671 // It changes enough (new BB, predicated form) and untill we
3672 // reach home, we do not even know if it is going to work.
3673 InstrToMove = insertTempCopy(MBB: CurrentBB, TargetPacket, MI: &*InstrToMove,
3674 DeleteOldCopy: NeedCleanup);
3675 NeedCleanup = true;
3676 NeedToPredicate = true;
3677 CleanupBB = CurrentBB;
3678
3679 if (PredCond.empty() && // If not already predicated.
3680 TII->PredicateInstruction(MI&: *InstrToMove, Pred: Cond)) {
3681 LLVM_DEBUG(dbgs() << "\tNew predicated insn:\t";
3682 InstrToMove->dump());
3683 // After predication some instruction could become const extended:
3684 // L2_loadrigp == "$dst=memw(#$global)"
3685 // L4_ploadrit_abs == "if ($src1) $dst=memw(##$global)"
3686 // Resource checking for those is different.
3687 if ((QII->isExtended(MI: *InstrToMove) ||
3688 QII->isConstExtended(MI: *InstrToMove) ||
3689 isJumpOutOfRange(MI: &*InstrToMove)) &&
3690 !tryAllocateResourcesForConstExt(MI: &*InstrToMove, UpdateState: false)) {
3691 // If we cannot, do not modify the state.
3692 LLVM_DEBUG(dbgs()
3693 << "\tEI Could not be added to the packet.\n");
3694 CleanupBB->erase(I: InstrToMove);
3695 return false;
3696 }
3697
3698 if (!ResourceTracker->canReserveResources(MI&: *InstrToMove) ||
3699 !shouldAddToPacket(MI: *InstrToMove)) {
3700 // It will not fit in its new form...
3701 LLVM_DEBUG(dbgs() << "\tCould not be added in its new form.\n");
3702 CurrentBB->erase(I: InstrToMove);
3703 return false;
3704 }
3705
3706 // Need also verify that we can newify it if we want to.
3707 if (NeedToNewify(NewMI: InstrToMove, DepReg: &DepReg, TargetPacket: &*TargetPacket)) {
3708 if (isNewifiable(MII: InstrToMove, DepReg, TargetPacket: &*TargetPacket)) {
3709 MINeedToNewify = true;
3710 LLVM_DEBUG(dbgs() << "\t\t\tNeeds to NEWify on Reg("
3711 << printReg(DepReg, QRI) << ").\n");
3712 } else {
3713 LLVM_DEBUG(dbgs() << "\tNon newifiable in this bundle: ";
3714 InstrToMove->dump());
3715 CleanupBB->erase(I: InstrToMove);
3716 return false;
3717 }
3718 }
3719
3720 LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
3721 PredCond = Cond;
3722 // Now the instruction uses the pred-reg as well.
3723 if (!Cond.empty() && (Cond.size() == 2)) {
3724 MIUseSet[OriginalInstructionToMove].push_back(x: Cond[1].getReg());
3725 }
3726 assert(((Cond.size() <= 2) &&
3727 !(QII->isNewValueJump(Cond[0].getImm()))) &&
3728 "Update MIUseSet for new-value compare jumps");
3729 } else {
3730 LLVM_DEBUG(dbgs() << "\tCould not predicate it\n");
3731 LLVM_DEBUG(dbgs() << "\tTrying to speculate!\t";
3732 InstrToMove->dump());
3733 bool DistantSpeculation = false;
3734 std::vector<MachineInstr *> NonPredPullUpPath;
3735 unsigned btidx = 0;
3736 // Generate a backtrack path for instruction to be speculated.
3737 // Original backtrack may start from a different (ancestor)
3738 // target packet.
3739 while (btidx < backtrack.size()) {
3740 const MachineBasicBlock *btBB = backtrack[btidx]->getParent();
3741 if ((btBB == PreviousBB) || (btBB == CurrentBB))
3742 NonPredPullUpPath.push_back(x: backtrack[btidx]);
3743 ++btidx;
3744 }
3745 // Speculate only to immediate predecessor.
3746 if (PreviousBB != CurrentBB) {
3747 if (*(PreviousBB->pred_begin()) != CurrentBB) {
3748 // In a region there are no side entries.
3749 DistantSpeculation = true;
3750 LLVM_DEBUG(dbgs()
3751 << "\n\tMI not in immediate successor of BB#"
3752 << CurrentBB->getNumber() << ", MI is in BB#"
3753 << PreviousBB->getNumber(););
3754 }
3755 assert((PreviousBB->pred_size() < 2) &&
3756 "Region with a side entry");
3757 }
3758 // TODO: Speculate ins. when pulled from unlikely path.
3759 if (DistantSpeculation || /*!PathInRegion ||*/
3760 InstrToMove->mayLoad() || InstrToMove->mayStore() ||
3761 InstrToMove->hasUnmodeledSideEffects() ||
3762 !canMIBeSpeculated(MI: &*InstrToMove, ToBB: CurrentBB, FromBB: PreviousBB,
3763 backtrack&: NonPredPullUpPath)) {
3764 CleanupBB->erase(I: InstrToMove);
3765 return false;
3766 } else {
3767 // Save speculated instruction moved.
3768 NeedToPredicate = false;
3769 SpeculatedIns.insert(
3770 x: std::make_pair(x&: OriginalInstructionToMove, y&: OriginBB));
3771 LLVM_DEBUG(dbgs() << "\nPredicable+SpeculatedInsToMove";
3772 InstrToMove->dump());
3773 }
3774 }
3775 } else {
3776 // This is a non-predicable instruction. We still can try to
3777 // speculate it here.
3778 LLVM_DEBUG(dbgs() << "\tNon predicable insn!\t";
3779 InstrToMove->dump());
3780 // TODO: Speculate ins. when pulled from unlikely path.
3781 if (!SpeculateNonPredInsn || !PathInRegion ||
3782 InstrToMove->mayLoad() || InstrToMove->mayStore() ||
3783 InstrToMove->hasUnmodeledSideEffects() ||
3784 !canMIBeSpeculated(MI: &*InstrToMove, ToBB: CurrentBB, FromBB: PreviousBB,
3785 backtrack&: PullUpPath)) {
3786 if (NeedCleanup)
3787 CleanupBB->erase(I: InstrToMove);
3788 return false;
3789 } else {
3790 // Save speculated instruction moved.
3791 SpeculatedIns.insert(
3792 x: std::make_pair(x&: OriginalInstructionToMove, y&: OriginBB));
3793 LLVM_DEBUG(dbgs() << "\nNonPredicable+SpeculatedInsToMove";
3794 InstrToMove->dump());
3795 }
3796
3797 InstrToMove = insertTempCopy(MBB: CurrentBB, TargetPacket, MI: &*InstrToMove,
3798 DeleteOldCopy: NeedCleanup);
3799 NeedCleanup = true;
3800 CleanupBB = CurrentBB;
3801 }
3802 } else {
3803 // No branch. Fall through.
3804 LLVM_DEBUG(dbgs() << "\tFall through BB.\n"
3805 << "\tCurrentBB:" << CurrentBB->getNumber()
3806 << "\tPreviousBB:" << PreviousBB->getNumber();
3807 if (PredFBB) dbgs()
3808 << "\tPredFBB:" << PredFBB->getNumber(););
3809 // Even though this is a fall though case, we still can
3810 // have a dual jump situation here with a CALL involved.
3811 // For now simply avoid it.
3812 if (IsDualJumpSecondCandidate(MI: &*InstrToMove)) {
3813 llvm_unreachable("Dual jumps with known?");
3814 LLVM_DEBUG(dbgs() << "\tUnderimplemented dual jump formation.\n");
3815 if (NeedCleanup)
3816 CleanupBB->erase(I: InstrToMove);
3817 return false;
3818 }
3819
3820 if (!CurrentBB->isSuccessor(MBB: PreviousBB)) {
3821 LLVM_DEBUG(dbgs() << "\tNon-successor fall through.\n");
3822 if (NeedCleanup)
3823 CleanupBB->erase(I: InstrToMove);
3824 return false;
3825 }
3826 SpeculatedIns.insert(
3827 x: std::make_pair(x&: OriginalInstructionToMove, y&: OriginBB));
3828 LLVM_DEBUG(dbgs() << "\nSpeculatedInsToMove+FallThroughBB";
3829 InstrToMove->dump());
3830 // Create a temp copy.
3831 InstrToMove = insertTempCopy(MBB: CurrentBB, TargetPacket, MI: &*InstrToMove,
3832 DeleteOldCopy: NeedCleanup);
3833 NeedCleanup = true;
3834 NeedToPredicate = false;
3835 CleanupBB = CurrentBB;
3836 LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
3837 }
3838 }
3839 }
3840 // If we have reached Home, great.
3841 // Original check should have verified that instruction could be added
3842 // to the target packet, so here we do nothing for deps.
3843 if (MIWH == backtrack.front()) {
3844 LLVM_DEBUG(dbgs() << "\tHOME!\n");
3845 break;
3846 }
3847
3848 // Test if we can reorder the two MIs.
3849 // The exception is when we are forming dual jumps - we can pull up
3850 // dependent instruction to the last bundle of an immediate predecesor
3851 // of the current BB if control flow permits it.
3852 // In this special case we also need to update the bundle we are moving
3853 // from.
3854 if (!(MovingDependentOp && (MIWH == &*SourceLocation)) &&
3855 !canReorderMIs(MIa: MIWH, MIb: &*InstrToMove)) {
3856 if (NeedCleanup)
3857 CleanupBB->erase(I: InstrToMove);
3858 return false;
3859 }
3860 }
3861 // We have previously tested this instruction, but has not updated the state
3862 // for it. Do it now.
3863 if (QII->isExtended(MI: *InstrToMove) || QII->isConstExtended(MI: *InstrToMove) ||
3864 isJumpOutOfRange(MI: &*InstrToMove)) {
3865 if (!tryAllocateResourcesForConstExt(MI: &*InstrToMove))
3866 llvm_unreachable("Missed dependency test");
3867 }
3868
3869 // Ok. We can safely move this instruction all the way up.
3870 // We also potentially have a slot for it.
3871 // During move original instruction could have changed (becoming predicated).
3872 // Now try to place the final instance of it into the current packet.
3873 LLVM_DEBUG(dbgs() << "\nWant to move ";
3874 if (MovingDependentOp) dbgs() << "dependent op"; dbgs() << ": ";
3875 InstrToMove->dump(); dbgs() << "To BB:\n"; HomeBB->dump();
3876 dbgs() << "From BB:\n"; OriginBB->dump());
3877
3878 // Keep these two statistics separately.
3879 if (!isDualJump)
3880 HexagonNumPullUps++;
3881 else
3882 HexagonNumDualJumps++;
3883
3884 // This means we have not yet inserted the temp copy of InstrToMove
3885 // in the target bundle. We are probably inside the same BB.
3886 if (!NeedCleanup) {
3887 InstrToMove =
3888 insertTempCopy(MBB: HomeBB, TargetPacket, MI: &*InstrToMove, DeleteOldCopy: NeedCleanup);
3889 NeedCleanup = true;
3890 }
3891
3892 // No problems detected. Add it.
3893 // If we were adding InstrToMove to a single, not yet packetized
3894 // instruction, we need to create bundle header for it before proceeding.
3895 // Be carefull since endPacket also resets the DFA state.
3896 if (!TargetPacket->isBundle()) {
3897 LLVM_DEBUG(dbgs() << "\tForm a new bundle.\n");
3898 finalizeBundle(MBB&: *HomeBB, FirstMI: TargetPacket.getInstrIterator(),
3899 LastMI: std::next(x: InstrToMove));
3900 LLVM_DEBUG(HomeBB->dump());
3901 // Now we need to adjust pointer to the newly created packet header.
3902 MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
3903 MII--;
3904
3905 // Is it also on the way home?
3906 for (unsigned i = 0; i < backtrack.size(); ++i)
3907 if (backtrack[i] == &*TargetPacket)
3908 backtrack[i] = &*MII;
3909
3910 // Is it where our next MI is pointing?
3911 if (NextMI == TargetPacket)
3912 NextMI = MII;
3913 TargetPacket = MII;
3914 }
3915
3916 // Move and Update Liveness info.
3917 MoveAndUpdateLiveness(CurrentRegion, HomeBB, InstrToMove: &*InstrToMove, NeedToNewify: MINeedToNewify,
3918 DepReg, MovingDependentOp, OriginBB,
3919 OriginalInstruction: OriginalInstructionToMove, Cond&: PredCond, SourceLocation,
3920 TargetPacket, NextMI, backtrack);
3921
3922 LLVM_DEBUG(dbgs() << "\n______Updated______\n"; HomeBB->dump();
3923 OriginBB->dump());
3924
3925 return true;
3926}
3927
3928/// Verify that we respect CFG layout during pull-up.
3929bool HexagonGlobalSchedulerImpl::isBranchWithinRegion(
3930 BasicBlockRegion *CurrentRegion, MachineInstr *MI) {
3931 assert(MI && MI->isBranch() && "Missing call info");
3932
3933 MachineBasicBlock *MBB = MI->getParent();
3934 LLVM_DEBUG(dbgs() << "\t[isBranchWithinRegion] BB(" << MBB->getNumber()
3935 << ") Branch instr:\t";
3936 MI->dump());
3937 // If there is only one successor, it is safe to pull.
3938 if (MBB->succ_size() <= 1)
3939 return true;
3940 // If there are multiple successors (jump table), we should
3941 // not allow pull up over this instruction.
3942 if (MBB->succ_size() > 2)
3943 return false;
3944
3945 MachineBasicBlock *NextRegionBB;
3946 MachineBasicBlock *TBB, *FBB;
3947 MachineInstr *FirstTerm = NULL;
3948 MachineInstr *SecondTerm = NULL;
3949
3950 if (AnalyzeBBBranches(MBB, TBB, FirstTerm, FBB, SecondTerm)) {
3951 LLVM_DEBUG(dbgs() << "\t\tAnalyzeBBBranches failed!\n");
3952 return false;
3953 }
3954
3955 // If there is no jump in this BB, it simply falls through.
3956 if (!FirstTerm) {
3957 LLVM_DEBUG(dbgs() << "\t\tNo FirstTerm\n");
3958 return true;
3959 } else if (QII->isEndLoopN(Opcode: FirstTerm->getOpcode())) {
3960 // We can easily analyze where endloop would take us
3961 // but here it would be pointless either way since
3962 // the region will not cross it.
3963 LLVM_DEBUG(dbgs() << "\t\tEndloop terminator\n");
3964 return false;
3965 }
3966 // On some occasions we see code like this:
3967 // BB#142: derived from LLVM BB %init, Align 4 (16 bytes)
3968 // Live Ins: %R17 %R18
3969 // Predecessors according to CFG: BB#2
3970 // EH_LABEL <MCSym=.Ltmp35>
3971 // J2_jump <BB#3>, %PC<imp-def>
3972 // Successors according to CFG: BB#3(1048575) BB#138(1)
3973 // It breaks most assumptions about CFG layout, so untill we know
3974 // the source of it, let's have a safeguard.
3975 if (MBB->succ_size() > 1 && !TII->isPredicated(MI: *FirstTerm) &&
3976 !QII->isNewValueJump(MI: *FirstTerm)) {
3977 LLVM_DEBUG(dbgs() << "\t\tBadly formed BB.\n");
3978 return false;
3979 }
3980
3981 LLVM_DEBUG(dbgs() << "\t\tFirstTerm: "; FirstTerm->dump());
3982 LLVM_DEBUG(dbgs() << "\t\tSecondTerm: "; if (SecondTerm) SecondTerm->dump();
3983 else dbgs() << "None\n";);
3984
3985 // All cases where there is only one branch in BB are OK to proceed.
3986 if (!SecondTerm)
3987 return true;
3988
3989 assert(!QII->isEndLoopN(SecondTerm->getOpcode()) && "Found endloop.");
3990
3991 // Find next BB in this region - if there is none, we will likely
3992 // stop pulling in the next check outside of this function.
3993 // This largely is don't care.
3994 NextRegionBB = CurrentRegion->findNextMBB(MBB);
3995 if (!NextRegionBB) {
3996 LLVM_DEBUG(dbgs() << "\t\tNo next BB in the region...\n");
3997 return true;
3998 }
3999 LLVM_DEBUG(dbgs() << "\t\tNextRegionBB(" << NextRegionBB->getNumber()
4000 << ")\n");
4001 assert(TBB && "Corrupt BB layout");
4002 // This means we are trying to pull into a packet _before_ the first
4003 // branch in the MBB.
4004 if (MI == FirstTerm) {
4005 LLVM_DEBUG(dbgs() << "\t\tTBB(" << TBB->getNumber()
4006 << ") NextBB in the region(" << NextRegionBB->getNumber()
4007 << ")\n");
4008 return (TBB == NextRegionBB);
4009 }
4010 assert(FBB && "Corrupt BB layout");
4011 // This means we are trying to pull into the packet _after_ first branch,
4012 // and it is OK if we pull from the second branch target.
4013 // This pull is always speculative.
4014 if ((MI != SecondTerm)) {
4015 LLVM_DEBUG(dbgs() << "\t\tDual terminator not matching SecondTerm.\n");
4016 return false;
4017 }
4018 // Analyze the second branch in the BB.
4019 LLVM_DEBUG(dbgs() << "\t\tFBB(" << FBB->getNumber()
4020 << ") NextBB in the region(" << NextRegionBB->getNumber()
4021 << ")\n");
4022 return (FBB == NextRegionBB);
4023}
4024
4025/// Check if a given instruction is:
4026/// - a jump to a distant target
4027/// - that exceeds its immediate range
4028/// If both conditions are true, it requires constant extension.
4029bool HexagonGlobalSchedulerImpl::isJumpOutOfRange(MachineInstr *UnCond,
4030 MachineInstr *Cond) {
4031 if (!UnCond || !UnCond->isBranch())
4032 return false;
4033
4034 MachineBasicBlock *UnCondBB = UnCond->getParent();
4035 MachineBasicBlock *CondBB = Cond->getParent();
4036 MachineInstr *FirstTerm = &*(CondBB->getFirstInstrTerminator());
4037 // This might be worth an assert.
4038 if (FirstTerm == &*CondBB->instr_end())
4039 return false;
4040
4041 unsigned InstOffset = BlockToInstOffset[UnCondBB];
4042 unsigned Distance = 0;
4043
4044 // To save time, estimate exact position of a branch instruction
4045 // as one at the end of the UnCondBB.
4046 // Number of instructions times typical instruction size.
4047 InstOffset += (QII->nonDbgBBSize(BB: UnCondBB) * HEXAGON_INSTR_SIZE);
4048
4049 MachineBasicBlock *TBB = NULL, *FBB = NULL;
4050 SmallVector<MachineOperand, 4> CondList;
4051
4052 // Find the target of the unconditional branch in UnCondBB, which is returned
4053 // in TBB. Then use the CondBB to extract the FirsTerm. We desire to replace
4054 // the branch target in FirstTerm with the branch location from the UnCondBB,
4055 // provided it is within the distance of the opcode in FirstTerm.
4056 if (QII->analyzeBranch(MBB&: *UnCondBB, TBB, FBB, Cond&: CondList, AllowModify: false))
4057 // Could not analyze it. give up.
4058 return false;
4059
4060 if (TBB && (Cond == FirstTerm)) {
4061 Distance =
4062 (unsigned)std::abs(x: (long long)InstOffset - BlockToInstOffset[TBB]) +
4063 SafetyBuffer;
4064 return !QII->isJumpWithinBranchRange(MI: *FirstTerm, offset: Distance);
4065 }
4066 return false;
4067}
4068
4069// findBundleAndBranch returns the branch instruction and the
4070// bundle which contains it. Null is returned if not found.
4071MachineInstr *HexagonGlobalSchedulerImpl::findBundleAndBranch(
4072 MachineBasicBlock *BB, MachineBasicBlock::iterator &Bundle) {
4073 // Find the conditional branch out of BB.
4074 if (!BB)
4075 return NULL;
4076 MachineInstr *CondBranch = NULL;
4077 Bundle = BB->end();
4078 for (MachineBasicBlock::instr_iterator MII = BB->getFirstInstrTerminator(),
4079 MBBEnd = BB->instr_end();
4080 MII != MBBEnd; ++MII) {
4081 MachineInstr *MI = &*MII;
4082 if (MII->isConditionalBranch()) {
4083 CondBranch = MI;
4084 }
4085 }
4086 if (!CondBranch)
4087 return NULL;
4088 MachineBasicBlock::instr_iterator MII = CondBranch->getIterator();
4089 if (!MII->isBundled())
4090 return NULL;
4091 // Find bundle header.
4092 for (--MII; MII->isBundled(); --MII)
4093 if (MII->isBundle()) {
4094 Bundle = MII;
4095 break;
4096 }
4097 return CondBranch;
4098}
4099
4100// pullUpPeelBBLoop
4101// A single BB loop with a register copy at the beginning in its
4102// own bundle, benefits from eliminating the extra bundle. We do
4103// this by predicating the register copy in the predecessor BB, and
4104// again in the last bundle of the loop.
4105bool HexagonGlobalSchedulerImpl::pullUpPeelBBLoop(MachineBasicBlock *PredBB,
4106 MachineBasicBlock *LoopBB) {
4107 if (!AllowBBPeelPullUp)
4108 return false;
4109 if (!LoopBB || !PredBB)
4110 return false;
4111
4112 // We consider single BB loops only. Check for it here.
4113 if (LoopBB->isEHPad() || LoopBB->hasAddressTaken())
4114 return false;
4115 if (LoopBB->succ_size() != 2)
4116 return false;
4117 if (LoopBB->pred_size() != 2)
4118 return false;
4119 // Make sure one of the successors and one of the predecssors is to self.
4120 if (!(LoopBB->isSuccessor(MBB: LoopBB) && LoopBB->isPredecessor(MBB: LoopBB)))
4121 return false;
4122
4123 // Find the none self successor block. We know we only have 2 successors.
4124 MachineBasicBlock *SuccBB = NULL;
4125 for (MachineBasicBlock::succ_iterator SI = LoopBB->succ_begin(),
4126 SE = LoopBB->succ_end();
4127 SI != SE; ++SI)
4128 if (*SI != LoopBB) {
4129 SuccBB = *SI;
4130 break;
4131 }
4132 if (!SuccBB)
4133 return false;
4134
4135 // Find the conditional branch and its bundle inside PredBB.
4136 MachineBasicBlock::iterator PredBundle;
4137 MachineInstr *PredCondBranch = NULL;
4138 PredCondBranch = findBundleAndBranch(BB: PredBB, Bundle&: PredBundle);
4139 if (!PredCondBranch)
4140 return false;
4141 if (PredBundle == PredBB->end())
4142 return false;
4143 LLVM_DEBUG(dbgs() << "PredBB's Branch: ");
4144 LLVM_DEBUG(dbgs() << *PredCondBranch);
4145
4146 // Look for leading reg copy as single bundle and make sure its live in.
4147 MachineBasicBlock::instr_iterator FMI = LoopBB->instr_begin();
4148 // Skip debug instructions.
4149 while (FMI->isDebugInstr())
4150 FMI++;
4151
4152 MachineInstr *RegMI = &*FMI;
4153 if (RegMI->isBundle())
4154 return false;
4155 if (RegMI->getOpcode() != Hexagon::A2_tfr)
4156 return false;
4157 if (!(RegMI->getOperand(i: 0).isReg() && RegMI->getOperand(i: 1).isReg()))
4158 return false;
4159 unsigned InLoopReg = RegMI->getOperand(i: 1).getReg();
4160 if (!LoopBB->isLiveIn(Reg: InLoopReg))
4161 return false;
4162
4163 // Create a region to pass to ResourcesAvailableInBundle.
4164 BasicBlockRegion PUR(BasicBlockRegion(TII, QRI, PredBB));
4165 PUR.addBBtoRegion(MBB: LoopBB);
4166 PUR.addBBtoRegion(MBB: SuccBB);
4167
4168 // Make sure we have space in PredBB's last bundle.
4169 if (!ResourcesAvailableInBundle(CurrentRegion: &PUR, TargetPacket&: PredBundle))
4170 return false;
4171 SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> PredBundlePkt(
4172 CurrentState.HomeBundle);
4173
4174 // Find condition to use for predicating the reg copy into PredBB.
4175 MachineBasicBlock *TBB = NULL, *FBB = NULL;
4176 SmallVector<MachineOperand, 4> Cond;
4177 if (QII->analyzeBranch(MBB&: *PredBB, TBB, FBB, Cond, AllowModify: false))
4178 return false;
4179 if (Cond.empty())
4180 return false;
4181
4182 // Find condition to use for predicating the reg copy at the end of LoopBB.
4183 MachineBasicBlock *LTBB = NULL, *LFBB = NULL;
4184 SmallVector<MachineOperand, 4> LCond;
4185 if (QII->analyzeBranch(MBB&: *LoopBB, TBB&: LTBB, FBB&: LFBB, Cond&: LCond, AllowModify: false))
4186 return false;
4187 if (LCond.empty())
4188 return false;
4189
4190 // Move predicated reg copy to previous BB's last bundle.
4191 if (!TII->isPredicable(MI: *RegMI))
4192 return false;
4193 MachineInstr *InstrToMove =
4194 &*insertTempCopy(MBB: PredBB, TargetPacket&: PredBundle, MI: RegMI, DeleteOldCopy: false);
4195 if (!canAddMIToThisPacket(MI: InstrToMove, Bundle&: PredBundlePkt)) {
4196 PredBB->erase_instr(I: InstrToMove);
4197 return false;
4198 }
4199
4200 if (!TII->PredicateInstruction(MI&: *InstrToMove, Pred: Cond)) {
4201 // Failed to predicate the copy reg.
4202 PredBB->erase_instr(I: InstrToMove);
4203 return false;
4204 }
4205
4206 // Can we newify this instruction?
4207 unsigned DepReg = 0;
4208 if (NeedToNewify(NewMI: InstrToMove->getIterator(), DepReg: &DepReg, TargetPacket: &*PredBundle) &&
4209 !isNewifiable(MII: InstrToMove->getIterator(), DepReg, TargetPacket: &*PredBundle)) {
4210 PredBB->erase_instr(I: InstrToMove);
4211 return false;
4212 }
4213 // Newify it, and then undo it if we determine we are using a .old.
4214 int NewOpcode = QII->getDotNewPredOp(MI: *InstrToMove, MBPI);
4215 // Undo newify if we have a non .new predicated jump we are matching.
4216 if (!QII->isDotNewInst(MI: *PredCondBranch))
4217 NewOpcode = QII->getDotOldOp(MI: *InstrToMove);
4218 NewOpcode = QII->getInvertedPredicatedOpcode(Opc: NewOpcode);
4219 // Properly set the opcode on the new hoisted reg copy instruction.
4220 InstrToMove->setDesc(QII->get(Opcode: NewOpcode));
4221 if (!incrementalAddToPacket(MI&: *InstrToMove)) {
4222 PredBB->erase_instr(I: InstrToMove);
4223 return false;
4224 }
4225
4226 // Find the conditional branch and its bundle for LoopBB.
4227 MachineBasicBlock::iterator LoopBundle;
4228 MachineInstr *LoopCondBranch = NULL;
4229 LoopCondBranch = findBundleAndBranch(BB: LoopBB, Bundle&: LoopBundle);
4230 if (!LoopCondBranch)
4231 return false;
4232 if (LoopBundle == LoopBB->end())
4233 return false;
4234 LLVM_DEBUG(dbgs() << "LoopBB's Branch: ");
4235 LLVM_DEBUG(dbgs() << *LoopCondBranch);
4236
4237 // Make sure we have space in LoopBB's last bundle.
4238 if (!ResourcesAvailableInBundle(CurrentRegion: &PUR, TargetPacket&: LoopBundle))
4239 return false;
4240 SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> LoopBundlePkt(
4241 CurrentState.HomeBundle);
4242
4243 // Move predicated reg copy to last bundle of LoopBB.
4244 MachineInstr *InstrToSink =
4245 &*insertTempCopy(MBB: LoopBB, TargetPacket&: LoopBundle, MI: RegMI, DeleteOldCopy: false);
4246 if (!canAddMIToThisPacket(MI: InstrToSink, Bundle&: LoopBundlePkt)) {
4247 // Get rid of previous instruction as well.
4248 PredBB->erase_instr(I: InstrToMove);
4249 LoopBB->erase_instr(I: InstrToSink);
4250 return false;
4251 }
4252
4253 if (!TII->PredicateInstruction(MI&: *InstrToSink, Pred: LCond)) {
4254 // Get rid of previous instruction as well.
4255 PredBB->erase_instr(I: InstrToMove);
4256 LoopBB->erase_instr(I: InstrToSink);
4257 return false;
4258 }
4259 // Can we newify this instruction?
4260 if (NeedToNewify(NewMI: InstrToSink->getIterator(), DepReg: &DepReg, TargetPacket: &*LoopBundle) &&
4261 !isNewifiable(MII: InstrToSink->getIterator(), DepReg, TargetPacket: &*LoopBundle)) {
4262 // Get rid of previous instruction as well.
4263 PredBB->erase_instr(I: InstrToMove);
4264 PredBB->erase_instr(I: InstrToSink);
4265 return false;
4266 }
4267 NewOpcode = QII->getDotNewPredOp(MI: *InstrToSink, MBPI);
4268 // Undo newify if we have a non .new predicated jump we are matching.
4269 if (!QII->isDotNewInst(MI: *LoopCondBranch))
4270 NewOpcode = QII->getDotOldOp(MI: *InstrToSink);
4271 InstrToSink->setDesc(QII->get(Opcode: NewOpcode));
4272 if (!incrementalAddToPacket(MI&: *InstrToSink)) {
4273 // Get rid of previous instruction as well.
4274 PredBB->erase_instr(I: InstrToMove);
4275 LoopBB->erase_instr(I: InstrToSink);
4276 return false;
4277 }
4278
4279 // Remove old instruction.
4280 LoopBB->erase_instr(I: RegMI);
4281 // Set loop alignment to 32.
4282 LoopBB->setAlignment(llvm::Align(32));
4283
4284 LLVM_DEBUG(dbgs() << "Peeled Single BBLoop copy\n");
4285 LLVM_DEBUG(dbgs() << *InstrToMove);
4286 LLVM_DEBUG(dbgs() << *InstrToSink);
4287 LLVM_DEBUG(dbgs() << *PredBB);
4288 LLVM_DEBUG(dbgs() << *LoopBB);
4289 LLVM_DEBUG(dbgs() << *SuccBB);
4290 LLVM_DEBUG(dbgs() << "--- BBLoop ---\n\n");
4291 return true;
4292}
4293
4294bool HexagonGlobalSchedulerImpl::performPullUpCFG(MachineFunction &Fn) {
4295 const Function &F = Fn.getFunction();
4296 // Check for single-block functions and skip them.
4297 if (std::next(x: F.begin()) == F.end())
4298 return false;
4299 bool Changed = false;
4300 LLVM_DEBUG(dbgs() << "****** PullUpCFG **************\n");
4301
4302 // Loop over all basic blocks, asking if 3 consecutive blocks are
4303 // the jump opportunity.
4304 MachineBasicBlock *PrevBlock = NULL;
4305 MachineBasicBlock *JumpBlock = NULL;
4306 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
4307 ++MBB) {
4308 MachineBasicBlock *FallBlock = &*MBB;
4309 if (PrevBlock && JumpBlock) {
4310 Changed |= pullUpPeelBBLoop(PredBB: PrevBlock, LoopBB: JumpBlock);
4311 }
4312 PrevBlock = JumpBlock;
4313 JumpBlock = FallBlock;
4314 }
4315 return Changed;
4316}
4317
4318void HexagonGlobalSchedulerImpl::GenUseDefChain(MachineFunction &Fn) {
4319 std::vector<unsigned> Defs;
4320 std::vector<unsigned> Uses;
4321 for (MachineFunction::iterator MBBIter = Fn.begin(); MBBIter != Fn.end();
4322 ++MBBIter) {
4323 for (MachineBasicBlock::instr_iterator MIter = MBBIter->instr_begin();
4324 MIter != MBBIter->instr_end(); ++MIter) {
4325 if (MIter->isBundle() || MIter->isDebugInstr())
4326 continue;
4327 LLVM_DEBUG(dbgs() << "\n\nInserted Ins:"; MIter->dump());
4328 MIUseDefSet(MI: &*MIter, Defs, Uses);
4329 LLVM_DEBUG(dbgs() << "\n\tDefs:";
4330 for (unsigned i = 0; i < Defs.size(); ++i) dbgs()
4331 << printReg(Defs[i], QRI) << ",");
4332 LLVM_DEBUG(dbgs() << "\n\tUses:";
4333 for (unsigned i = 0; i < Uses.size(); ++i) dbgs()
4334 << printReg(Uses[i], QRI) << ",");
4335 MIDefSet[&*MIter] = Defs;
4336 MIUseSet[&*MIter] = Uses;
4337 }
4338 }
4339}
4340
4341// optimizeBranching -
4342// 1. A conditional-jump transfers control to a BB with
4343// jump as the only instruction.
4344// if(p0) jump t1
4345// // ...
4346// t1: jump t2
4347// 2. When a BB with a single conditional jump, jumps to succ-of-succ and
4348// falls-through BB with only jump instruction.
4349// { if(p0) jump t1 }
4350// { jump t2 }
4351// t1: { ... }
4352MachineBasicBlock *HexagonGlobalSchedulerImpl::optimizeBranches(
4353 MachineBasicBlock *MBB, MachineBasicBlock *TBB, MachineInstr *FirstTerm,
4354 MachineBasicBlock *FBB) {
4355 LLVM_DEBUG(dbgs() << "\n\t\t[optimizeBranching]\n");
4356 if ((TBB == MBB) || (FBB == MBB))
4357 LLVM_DEBUG(dbgs() << "Cannot deal with loops in BB#" << MBB->getNumber(););
4358
4359 // LLVM_DEBUG(dbgs() << "\n\t\tTBBMIb:"; MII->dump(););
4360 // { if(p) jump t1; }
4361 // t1: { jump t2; }
4362 // --> { if(p) jump t2
4363 // remove t1: { jump t2; }, if it's address is not taken/not a landing pad.
4364 if (QII->nonDbgBBSize(BB: TBB) == 1) {
4365 MachineInstr *TBBMIb = &*TBB->getFirstNonDebugInstr();
4366 if (TBBMIb->getOpcode() == Hexagon::J2_jump &&
4367 TBBMIb->getOperand(i: 0).isMBB()) {
4368 MachineBasicBlock *NewTarget = TBBMIb->getOperand(i: 0).getMBB();
4369 if (TBB == NewTarget) // Infinite loop.
4370 return NULL;
4371
4372 LLVM_DEBUG(dbgs() << "\nSuboptimal branching in TBB");
4373 // Check if the jump in the last instruction is within range.
4374 int64_t InstOffset =
4375 BlockToInstOffset.find(Val: MBB)->second + QII->nonDbgBBSize(BB: MBB) * 4;
4376 unsigned Distance = (unsigned)std::abs(
4377 i: InstOffset - BlockToInstOffset.find(Val: NewTarget)->second);
4378 if (!QII->isJumpWithinBranchRange(MI: *FirstTerm, offset: Distance)) {
4379 LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
4380 << " out of range.");
4381 return NULL;
4382 }
4383 // We need to make sure that the TBB is _not_ also a target for another
4384 // branch. This is suboptimal since theoretically we can update both
4385 // branches.
4386 if (!TBB->hasAddressTaken() && !TBB->isEHPad() && TBB->pred_size() == 1) {
4387 updatePredecessors(MBB&: *TBB, MFBB: NewTarget);
4388 // TBB has only one successor since only one J2_jump instr.
4389 TBB->removeSuccessor(I: TBB->succ_begin());
4390 TBBMIb->removeFromParent();
4391 if (!TBB->empty()) {
4392 // There are only debug instructions in TBB now. Move them to
4393 // the beginning of NewTarget.
4394 NewTarget->splice(Where: NewTarget->getFirstNonPHI(), Other: TBB, From: TBB->begin(),
4395 To: TBB->end());
4396 }
4397 return TBB;
4398 } else {
4399 MBB->ReplaceUsesOfBlockWith(Old: TBB, New: NewTarget);
4400 return NULL;
4401 }
4402 }
4403 }
4404 // { if(p) jump t1; } may contain more instructions
4405 // { jump t2; } --only one instruction
4406 // t1: {...}
4407 // TBB is layout successor of FBB, then we can change the branch target
4408 // for conditional jump and invert the predicate to remove jump t2.
4409 // { if(!p) jump t2; }
4410 // t1: {...}
4411 if (QII->nonDbgBBSize(BB: FBB) == 1) {
4412 MachineInstr *FBBMIb = &*FBB->getFirstNonDebugInstr();
4413 if (FBBMIb->getOpcode() == Hexagon::J2_jump &&
4414 FBBMIb->getOperand(i: 0).isMBB()) {
4415 MachineBasicBlock *NewTarget = FBBMIb->getOperand(i: 0).getMBB();
4416 if (FBB->hasAddressTaken() || FBB->isEHPad() ||
4417 !FBB->isLayoutSuccessor(MBB: TBB) || (FBB == NewTarget /*Infinite loop*/))
4418 return NULL;
4419
4420 LLVM_DEBUG(dbgs() << "\nSuboptimal branching in FBB");
4421 // Check if the jump in the last instruction is within range.
4422 int64_t InstOffset =
4423 BlockToInstOffset.find(Val: MBB)->second + QII->nonDbgBBSize(BB: MBB) * 4;
4424 unsigned Distance = (unsigned)std::abs(
4425 i: InstOffset - BlockToInstOffset.find(Val: NewTarget)->second);
4426 if (!QII->isJumpWithinBranchRange(MI: *FirstTerm, offset: Distance)) {
4427 LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
4428 << " out of range.");
4429 return NULL;
4430 }
4431 if (!QII->invertAndChangeJumpTarget(MI&: *FirstTerm, NewTarget))
4432 return NULL;
4433 LLVM_DEBUG(dbgs() << "\nNew instruction:"; FirstTerm->dump(););
4434 updatePredecessors(MBB&: *FBB, MFBB: NewTarget);
4435 // Only one successor remains for FBB
4436 FBB->removeSuccessor(I: FBB->succ_begin());
4437 FBBMIb->removeFromParent();
4438 return FBB;
4439 }
4440 }
4441 return NULL;
4442}
4443
4444// performExposedOptimizations -
4445// look for optimization opportunities after pullup.
4446// e.g. jump to adjacent targets
4447bool HexagonGlobalSchedulerImpl::performExposedOptimizations(
4448 MachineFunction &Fn) {
4449 // Check for single-block functions and skip them.
4450 if (std::next(x: Fn.getFunction().begin()) == Fn.getFunction().end())
4451 return true;
4452 LLVM_DEBUG(dbgs() << "\n\t\t[performExposedOptimizations]\n");
4453 // Erasing the empty basic blocks formed during pullup.
4454 std::vector<MachineBasicBlock *>::iterator ebb = EmptyBBs.begin();
4455 while (ebb != EmptyBBs.end()) {
4456 assert(IsEmptyBlock(*ebb) && "Pullup inserted packets into an empty BB");
4457 LLVM_DEBUG(dbgs() << "Removing BB(" << (*ebb)->getNumber()
4458 << ") from parent.\n");
4459 (*ebb)->eraseFromParent();
4460 ++ebb;
4461 }
4462 MachineBasicBlock *TBB = NULL, *FBB = NULL;
4463 MachineInstr *FirstTerm = NULL, *SecondTerm = NULL;
4464
4465 SmallVector<MachineBasicBlock *, 4> Erase;
4466
4467 for (MachineBasicBlock &MBB : Fn) {
4468 if (MBB.succ_size() > 2 ||
4469 AnalyzeBBBranches(MBB: &MBB, TBB, FirstTerm, FBB, SecondTerm)) {
4470 LLVM_DEBUG(dbgs() << "\nAnalyzeBBBranches failed in BB#"
4471 << MBB.getNumber() << "\n";);
4472 continue;
4473 }
4474 if (FirstTerm && QII->isCompoundBranchInstr(MI: *FirstTerm))
4475 continue;
4476 if (TBB && FirstTerm &&
4477 removeRedundantBranches(MBB: &MBB, TBB, FirstTerm, FBB, SecondTerm)) {
4478 LLVM_DEBUG(dbgs() << "\nRemoved redundant branches in BB#"
4479 << MBB.getNumber(););
4480 continue;
4481 }
4482 if (FirstTerm && SecondTerm &&
4483 optimizeDualJumps(MBB: &MBB, TBB, FirstTerm, FBB, SecondTerm)) {
4484 LLVM_DEBUG(dbgs() << "\nRemoved dual jumps in in BB#"
4485 << MBB.getNumber(););
4486 continue;
4487 }
4488 if (TBB && FBB && FirstTerm && !SecondTerm) {
4489 MachineBasicBlock *MBBToErase =
4490 optimizeBranches(MBB: &MBB, TBB, FirstTerm, FBB);
4491 if (MBBToErase) {
4492 assert(IsEmptyBlock(MBBToErase) && "Erasing non-empty BB");
4493 Erase.push_back(Elt: MBBToErase);
4494 LLVM_DEBUG(dbgs() << "\nOptimized jump from BB#" << MBB.getNumber());
4495 }
4496 }
4497 }
4498 for (MachineBasicBlock *MBB : Erase)
4499 MBB->eraseFromParent();
4500
4501 return false;
4502}
4503
4504// 1. Remove jump to the layout successor.
4505// 2. Remove multiple (dual) jump to the same target.
4506bool HexagonGlobalSchedulerImpl::removeRedundantBranches(
4507 MachineBasicBlock *MBB, MachineBasicBlock *TBB, MachineInstr *FirstTerm,
4508 MachineBasicBlock *FBB, MachineInstr *SecondTerm) {
4509 bool Analyzed = false;
4510 LLVM_DEBUG(dbgs() << "\n\t\t[removeRedundantBranches]\n");
4511 MachineInstr *Head = NULL, *ToErase = NULL;
4512 if (!FBB && (FirstTerm->getOpcode() == Hexagon::J2_jump) &&
4513 MBB->isLayoutSuccessor(MBB: TBB)) {
4514 // Jmp layout_succ_basic_block <-- Remove
4515 LLVM_DEBUG(
4516 dbgs() << "\nRemoving Uncond. jump to the layout successor in BB#"
4517 << MBB->getNumber());
4518 ToErase = FirstTerm;
4519 } else if (SecondTerm && (TBB == FBB) &&
4520 (SecondTerm->getOpcode() == Hexagon::J2_jump)) {
4521 // If both branching instructions in same packet or are consecutive.
4522 // Jmp_c t1 <-- Remove
4523 // Jmp t1
4524 // @Note: If they are in different packets or if they are separated
4525 // by packet(s), this opt. cannot be done.
4526 MachineBasicBlock::instr_iterator FirstTermIter = FirstTerm->getIterator();
4527 MachineBasicBlock::instr_iterator SecondTermIter =
4528 SecondTerm->getIterator();
4529 if (++FirstTermIter == SecondTermIter) {
4530 LLVM_DEBUG(dbgs() << "\nRemoving multiple branching to same target in BB#"
4531 << MBB->getNumber());
4532 // TODO: This might make the `p' register assignment instruction dead.
4533 // and can be removed.
4534 ToErase = FirstTerm;
4535 }
4536 } else if (SecondTerm && (SecondTerm->getOpcode() == Hexagon::J2_jump) &&
4537 FBB && MBB->isLayoutSuccessor(MBB: FBB)) {
4538 // Jmp_c t1
4539 // Jmp layout_succ_basic_block <-- Remove
4540 LLVM_DEBUG(dbgs() << "\nRemoving fall through branch in BB#"
4541 << MBB->getNumber());
4542 ToErase = SecondTerm;
4543 } else if (SecondTerm && QII->PredOpcodeHasJMP_c(Opcode: SecondTerm->getOpcode()) &&
4544 MBB->isLayoutSuccessor(MBB: getBranchDestination(MI: SecondTerm))) {
4545 // Jmp_c t1
4546 // Jmp_c layout_succ_basic_block <-- Remove
4547 // In this case AnalyzeBBBranches might assign FBB to some other BB.
4548 // So using the jump target of SecondTerm to check.
4549 LLVM_DEBUG(dbgs() << "\nRemoving Cond. jump to the layout successor in BB#"
4550 << MBB->getNumber());
4551 ToErase = SecondTerm;
4552 }
4553 // Remove the instruction from the BB
4554 if (ToErase) {
4555 if (ToErase->isBundled()) {
4556 Head = &*getBundleStart(I: ToErase->getIterator());
4557 ToErase->eraseFromBundle();
4558 UpdateBundle(BundleHead: Head);
4559 } else
4560 ToErase->eraseFromParent();
4561 Analyzed = true;
4562 }
4563 return Analyzed;
4564}
4565
4566// ----- convert
4567// p = <expr>
4568// if(p) jump layout_succ_basic_block
4569// jump t
4570// ----- to
4571// p = <expr>
4572// if(!p) jump t
4573// for now only looking at the dual jump
4574bool HexagonGlobalSchedulerImpl::optimizeDualJumps(MachineBasicBlock *MBB,
4575 MachineBasicBlock *TBB,
4576 MachineInstr *FirstTerm,
4577 MachineBasicBlock *FBB,
4578 MachineInstr *SecondTerm) {
4579 LLVM_DEBUG(dbgs() << "\n******* optimizeDualJumps *******");
4580
4581 bool Analyzed = false;
4582
4583 if (QII->PredOpcodeHasJMP_c(Opcode: FirstTerm->getOpcode()) &&
4584 (SecondTerm->getOpcode() == Hexagon::J2_jump)) {
4585
4586 if (TBB == FBB) {
4587 LLVM_DEBUG(dbgs() << "\nBoth successors are the same.");
4588 return Analyzed;
4589 }
4590
4591 // Do not optimize for dual jumps if this MBB
4592 // contains a speculatively pulled-up instruction.
4593 // A speculated instruction is more likely to be at the end of MBB.
4594 MachineBasicBlock::reverse_instr_iterator SII = MBB->instr_rbegin();
4595 while (SII != MBB->instr_rend()) {
4596 MachineInstr *SI = &*SII;
4597 std::map<MachineInstr *, MachineBasicBlock *>::iterator MIMoved;
4598 MIMoved = SpeculatedIns.find(x: SI);
4599 if ((MIMoved != SpeculatedIns.end()) &&
4600 (MIMoved->second != SI->getParent())) {
4601 return Analyzed;
4602 }
4603 ++SII;
4604 }
4605
4606 LLVM_DEBUG(dbgs() << "\nCandidate for jump optimization in BB("
4607 << MBB->getNumber() << ").\n";);
4608
4609 // Predicated jump to layout successor followed by an unconditional jump.
4610 if (MBB->isLayoutSuccessor(MBB: TBB)) {
4611
4612 // Check if the jump in the last instruction is within range.
4613 int64_t InstOffset =
4614 BlockToInstOffset.find(Val: &*MBB)->second + QII->nonDbgBBSize(BB: MBB) * 4;
4615 unsigned Distance =
4616 (unsigned)std::abs(i: InstOffset - BlockToInstOffset.find(Val: FBB)->second) +
4617 SafetyBuffer;
4618 if (!QII->isJumpWithinBranchRange(MI: *FirstTerm, offset: Distance)) {
4619 LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
4620 << " out of range.");
4621 return Analyzed;
4622 }
4623
4624 // modify the second last -predicated- instruction (sense and target)
4625 LLVM_DEBUG(dbgs() << "\nFirst Instr:" << *FirstTerm;);
4626 LLVM_DEBUG(dbgs() << "\nSecond Instr:" << *SecondTerm;);
4627 LLVM_DEBUG(dbgs() << "\nOld Succ BB(" << TBB->getNumber() << ").";);
4628
4629 QII->invertAndChangeJumpTarget(MI&: *FirstTerm, NewTarget: FBB);
4630
4631 LLVM_DEBUG(dbgs() << "\nNew First Instruction:" << *FirstTerm;);
4632
4633 // unbundle if there is only one instruction left
4634 MachineInstr *SecondHead, *FirstHead;
4635 FirstHead = FirstTerm->isBundled()
4636 ? &*getBundleStart(I: FirstTerm->getIterator())
4637 : nullptr;
4638 SecondHead = SecondTerm->isBundled()
4639 ? &*getBundleStart(I: SecondTerm->getIterator())
4640 : nullptr;
4641
4642 // 1. Both unbundled, 2. FirstTerm inside bundle, second outside.
4643 if (!SecondHead)
4644 SecondTerm->eraseFromParent();
4645 else if (!FirstHead) {
4646 // 3. FirstHead outside, SecondHead inside.
4647 SecondTerm->eraseFromBundle();
4648 UpdateBundle(BundleHead: SecondHead);
4649 } else if (FirstHead == SecondHead) {
4650 // 4. Both are in the same bundle
4651 assert((FirstHead && SecondHead) && "Unbundled Instruction");
4652 SecondTerm->eraseFromBundle();
4653 if (SecondHead->getBundleSize() < 2)
4654 UpdateBundle(BundleHead: SecondHead);
4655 } else {
4656 // 5. Both are in different bundles
4657 SecondTerm->eraseFromBundle();
4658 UpdateBundle(BundleHead: SecondHead);
4659 }
4660 Analyzed = true;
4661 }
4662 }
4663 return Analyzed;
4664}
4665
4666/// Are there any resources left in this bundle?
4667bool HexagonGlobalSchedulerImpl::ResourcesAvailableInBundle(
4668 BasicBlockRegion *CurrentRegion,
4669 MachineBasicBlock::iterator &TargetPacket) {
4670 MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
4671
4672 // If this is a single instruction, form new packet around it.
4673 if (!TargetPacket->isBundle()) {
4674 if (ignoreInstruction(MI: &*MII) || isSoloInstruction(MI: *MII))
4675 return false;
4676
4677 // Before we begin, we need to make sure that we do not
4678 // look at an unconditional jump outside the current region.
4679 if (MII->isBranch() && !isBranchWithinRegion(CurrentRegion, MI: &*MII))
4680 return false;
4681
4682 // Build up state for this new packet.
4683 // Note, we cannot create a bundle header for it,
4684 // so this "bundle" only exist in DFA state, and not in code.
4685 initPacketizerState();
4686 ResourceTracker->clearResources();
4687 CurrentState.addHomeLocation(WorkPoint: MII);
4688 return incrementalAddToPacket(MI&: *MII);
4689 }
4690
4691 MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
4692
4693 // Build up state for this packet.
4694 initPacketizerState();
4695 ResourceTracker->clearResources();
4696 CurrentState.addHomeLocation(WorkPoint: MII);
4697
4698 for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
4699 if (MII->getOpcode() == TargetOpcode::DBG_VALUE ||
4700 MII->getOpcode() == TargetOpcode::IMPLICIT_DEF ||
4701 MII->getOpcode() == TargetOpcode::CFI_INSTRUCTION || MII->isEHLabel())
4702 continue;
4703
4704 // Before we begin, we need to make sure that we do not
4705 // look at an unconditional jump outside the current region.
4706 // TODO: See if we can profit from handling this kind of cases:
4707 // B#15: derived from LLVM BB %if.then22
4708 // Predecessors according to CFG: BB#13
4709 // BUNDLE %PC<imp-def>, %P2<imp-use,kill>
4710 // * J2_jumpf %P2<kill,internal>, <BB#17>, %PC<imp-def>; flags:
4711 // * J2_jump <BB#18>, %PC<imp-def>; flags:
4712 // Successors according to CFG: BB#18(62) BB#17(62)
4713 // Curently we do not allow them.
4714 if (MII->isBranch() && !isBranchWithinRegion(CurrentRegion, MI: &*MII))
4715 return false;
4716
4717 if (!incrementalAddToPacket(MI&: *MII))
4718 return false;
4719 }
4720 return ResourceTracker->canReserveResources(MI&: *Nop);
4721}
4722
4723/// Symmetrical. See if these two instructions are fit for compound pair.
4724bool HexagonGlobalSchedulerImpl::isCompoundPair(MachineInstr *MIa,
4725 MachineInstr *MIb) {
4726 enum HexagonII::CompoundGroup MIaG = QII->getCompoundCandidateGroup(MI: *MIa),
4727 MIbG = QII->getCompoundCandidateGroup(MI: *MIb);
4728 // We have two candidates - check that this is the same register
4729 // we are talking about.
4730 unsigned Opcb = MIb->getOpcode();
4731 if (MIaG == HexagonII::HCG_C && MIbG == HexagonII::HCG_A &&
4732 (Opcb == Hexagon::A2_tfr || Opcb == Hexagon::A2_tfrsi))
4733 return true;
4734 unsigned Opca = MIa->getOpcode();
4735 if (MIbG == HexagonII::HCG_C && MIaG == HexagonII::HCG_A &&
4736 (Opca == Hexagon::A2_tfr || Opca == Hexagon::A2_tfrsi))
4737 return true;
4738 return (((MIaG == HexagonII::HCG_A && MIbG == HexagonII::HCG_B) ||
4739 (MIbG == HexagonII::HCG_A && MIaG == HexagonII::HCG_B)) &&
4740 (MIa->getOperand(i: 0).getReg() == MIb->getOperand(i: 0).getReg()));
4741}
4742
4743// This is a weird situation when BB conditionally branches + falls through
4744// to layout successor. \ref bug17792
4745inline bool HexagonGlobalSchedulerImpl::multipleBranchesFromToBB(
4746 MachineBasicBlock *BB) const {
4747 if (BB->succ_size() != 1)
4748 return false;
4749 SmallVector<MachineInstr *, 2> Jumpers = QII->getBranchingInstrs(MBB&: *BB);
4750 return ((Jumpers.size() == 1) && !Jumpers[0]->isUnconditionalBranch());
4751}
4752
4753/// Gather a worklist of MaxCandidates pull-up candidates.
4754/// Compute relative cost.
4755bool HexagonGlobalSchedulerImpl::findPullUpCandidates(
4756 MachineBasicBlock::iterator &WorkPoint,
4757 MachineBasicBlock::iterator &FromHere,
4758 std::vector<MachineInstr *> &backtrack, unsigned MaxCandidates = 1) {
4759
4760 const HexagonInstrInfo *QII = (const HexagonInstrInfo *)TII;
4761 MachineBasicBlock *FromThisBB = FromHere->getParent();
4762 bool MovingDependentOp = false;
4763 signed CostBenefit = 0;
4764
4765 // Do not collect more than that many candidates.
4766 if (CurrentState.haveCandidates() >= MaxCandidates)
4767 return false;
4768
4769 LLVM_DEBUG(dbgs() << "\n\tTry from BB(" << FromThisBB->getNumber() << "):\n";
4770 DumpPacket(FromHere.getInstrIterator()));
4771
4772 if (FromHere->isBundle()) {
4773 MachineBasicBlock::instr_iterator MII = FromHere.getInstrIterator();
4774 for (++MII; MII != FromThisBB->instr_end() && MII->isInsideBundle();
4775 ++MII) {
4776 if (MII->isDebugInstr())
4777 continue;
4778 LLVM_DEBUG(dbgs() << "\tCandidate from BB("
4779 << MII->getParent()->getNumber() << "): ";
4780 MII->dump());
4781
4782 // See if this instruction could be moved.
4783 if (!canThisMIBeMoved(MI: &*MII, WorkPoint, MovingDependentOp, Cost&: CostBenefit))
4784 continue;
4785
4786 MachineBasicBlock::instr_iterator InstrToMove = MII;
4787 if (canAddMIToThisPacket(MI: &*InstrToMove, Bundle&: CurrentState.HomeBundle)) {
4788 CostBenefit -= (backtrack.size() * 4);
4789 // Prefer instructions in empty packets.
4790 CostBenefit += (PacketSize - nonDbgBundleSize(TargetPacket&: FromHere)) * 2;
4791 // Prefer Compares.
4792 if (MII->isCompare())
4793 CostBenefit += 10;
4794 // Check duplex conditions;
4795 for (unsigned i = 0; i < CurrentState.HomeBundle.size(); i++) {
4796 if (QII->isDuplexPair(MIa: *CurrentState.HomeBundle[i], MIb: *MII)) {
4797 LLVM_DEBUG(dbgs() << "\tGot real Duplex (bundle).\n");
4798 CostBenefit += 20;
4799 }
4800 if (isCompoundPair(MIa: CurrentState.HomeBundle[i], MIb: &*MII)) {
4801 LLVM_DEBUG(dbgs() << "\tGot compound (bundle).\n");
4802 CostBenefit += 40;
4803 }
4804 }
4805 // Create a record for this location.
4806 CurrentState.addPullUpCandidate(MII: InstrToMove, HomeBundle: WorkPoint, backtrack,
4807 DependentOp: MovingDependentOp, Cost: CostBenefit);
4808 } else
4809 LLVM_DEBUG(dbgs() << "\tNo resources in the target packet.\n");
4810 }
4811 }
4812 // This is a standalone instruction.
4813 // First see if this MI can even be moved. Cost model for a single instruction
4814 // should be rather different from moving something out of a bundle.
4815 else if (canThisMIBeMoved(MI: &*FromHere, WorkPoint, MovingDependentOp,
4816 Cost&: CostBenefit)) {
4817 MachineBasicBlock::instr_iterator InstrToMove = FromHere.getInstrIterator();
4818 if (canAddMIToThisPacket(MI: &*InstrToMove, Bundle&: CurrentState.HomeBundle)) {
4819 CostBenefit -= (backtrack.size() * 4);
4820 // Prefer Compares.
4821 if (InstrToMove->isCompare())
4822 CostBenefit += 10;
4823 // It is better to pull a single instruction in to a bundle - save
4824 // a cycle immediately.
4825 CostBenefit += 10;
4826 // Search for duplex match.
4827 for (unsigned i = 0; i < CurrentState.HomeBundle.size(); i++) {
4828 if (QII->isDuplexPair(MIa: *CurrentState.HomeBundle[i], MIb: *InstrToMove)) {
4829 LLVM_DEBUG(dbgs() << "\tGot real Duplex (single).\n");
4830 CostBenefit += 30;
4831 }
4832 if (isCompoundPair(MIa: CurrentState.HomeBundle[i], MIb: &*InstrToMove)) {
4833 LLVM_DEBUG(dbgs() << "\tGot compound (single).\n");
4834 CostBenefit += 50;
4835 }
4836 }
4837 // Create a record for this location.
4838 CurrentState.addPullUpCandidate(MII: InstrToMove, HomeBundle: WorkPoint, backtrack,
4839 DependentOp: MovingDependentOp, Cost: CostBenefit);
4840 } else
4841 LLVM_DEBUG(dbgs() << "\tNo resources for single in the target packet.\n");
4842 }
4843 return true;
4844}
4845
4846/// Try to move a candidate MI.
4847/// The move can destroy all iterator system, so we have to drag them
4848/// around to keep them up to date.
4849bool HexagonGlobalSchedulerImpl::tryMultipleInstructions(
4850 MachineBasicBlock::iterator &RetVal, /* output parameter */
4851 std::vector<BasicBlockRegion *>::iterator &CurrentRegion,
4852 MachineBasicBlock::iterator &NextMI,
4853 MachineBasicBlock::iterator &ToThisBBEnd,
4854 MachineBasicBlock::iterator &FromThisBBEnd, bool PathInRegion) {
4855
4856 MachineBasicBlock::instr_iterator MII;
4857 MachineBasicBlock::iterator WorkPoint;
4858 bool MovingDependentOp = false;
4859 std::vector<MachineInstr *> backtrack;
4860
4861 LLVM_DEBUG(dbgs() << "\n\tTry Multiple candidates: \n");
4862
4863 std::sort(first: CurrentState.PullUpCandidates.begin(),
4864 last: CurrentState.PullUpCandidates.end(), comp: PullUpCandidateSorter());
4865 LLVM_DEBUG(CurrentState.dump());
4866 // Iterate through candidates in sorted order.
4867 for (SmallVector<PullUpCandidate *, 4>::iterator
4868 I = CurrentState.PullUpCandidates.begin(),
4869 E = CurrentState.PullUpCandidates.end();
4870 I != E; ++I) {
4871 (*I)->populate(MII, WorkPoint, backtrack, dependentOp&: MovingDependentOp);
4872
4873 MachineBasicBlock *FromThisBB = MII->getParent();
4874 MachineBasicBlock *ToThisBB = WorkPoint->getParent();
4875
4876 LLVM_DEBUG(dbgs() << "\n\tCandidate: "; MII->dump());
4877 LLVM_DEBUG(dbgs() << "\tDependent(" << MovingDependentOp << ") FromBB("
4878 << FromThisBB->getNumber() << ") ToBB("
4879 << ToThisBB->getNumber() << ") to this packet:\n";
4880 DumpPacket(WorkPoint.getInstrIterator()));
4881
4882 MachineBasicBlock::instr_iterator FromHereII = MII;
4883 if (MII->isInsideBundle()) {
4884 while (!FromHereII->isBundle())
4885 --FromHereII;
4886 LLVM_DEBUG(dbgs() << "\tFrom here:\n"; DumpPacket(FromHereII));
4887
4888 MachineBasicBlock::iterator FromHere(FromHereII);
4889 // We have instruction that could be moved from its current position.
4890 if (MoveMItoBundle(CurrentRegion: *CurrentRegion, InstrToMove&: MII, NextMI, TargetPacket&: WorkPoint, SourceLocation&: FromHere,
4891 backtrack, MovingDependentOp, PathInRegion)) {
4892 // If BB from which we pull is now empty, move on.
4893 if (IsEmptyBlock(MBB: FromThisBB)) {
4894 LLVM_DEBUG(dbgs() << "\n\tExhosted BB (bundle).\n");
4895 return false;
4896 }
4897 FromThisBBEnd = FromThisBB->end();
4898 ToThisBBEnd = ToThisBB->end();
4899
4900 LLVM_DEBUG(dbgs() << "\n\tAfter updates(bundle to bundle):\n");
4901 LLVM_DEBUG(dbgs() << "\t\tWorkPoint: ";
4902 DumpPacket(WorkPoint.getInstrIterator()));
4903
4904 // We should not increment current position,
4905 // but rather try one more time to pull from the same bundle.
4906 RetVal = WorkPoint;
4907 return true;
4908 } else
4909 LLVM_DEBUG(dbgs() << "\tCould not move packetized instr.\n");
4910 } else {
4911 MachineBasicBlock::iterator FromHere(FromHereII);
4912 if (MoveMItoBundle(CurrentRegion: *CurrentRegion, InstrToMove&: MII, NextMI, TargetPacket&: WorkPoint, SourceLocation&: FromHere,
4913 backtrack, MovingDependentOp, PathInRegion)) {
4914
4915 // If BB from which we pull is now empty, move on.
4916 if (IsEmptyBlock(MBB: FromThisBB)) {
4917 LLVM_DEBUG(dbgs() << "\n\tExhosted BB (single).\n");
4918 return false;
4919 }
4920 FromThisBBEnd = FromThisBB->end();
4921 ToThisBBEnd = ToThisBB->end();
4922
4923 LLVM_DEBUG(dbgs() << "\tAfter updates (single to bundle):\n");
4924 LLVM_DEBUG(dbgs() << "\t\tWorkPoint: ";
4925 DumpPacket(WorkPoint.getInstrIterator()));
4926 // We should not increment current position,
4927 // but rather try one more time to pull from the same bundle.
4928 RetVal = WorkPoint;
4929 return true;
4930 } else
4931 LLVM_DEBUG(dbgs() << "\tCould not move single.\n");
4932 }
4933 }
4934 LLVM_DEBUG(dbgs() << "\tNot a single candidate fit.\n");
4935 return false;
4936}
4937
4938/// Main function. Iterate all current regions one at a time,
4939/// and look for pull-up opportunities.
4940/// Pseudo sequence:
4941/// - for all bundles and single instructions in region:
4942/// - see if resources are available (in the same cycle) - this is HOME.
4943/// - Starting from next BB in region, find an instruction that could be:
4944/// - removed from its current location
4945/// - added to underutilized bundle (including bundles with only one op)
4946/// - If so, trace path back to HOME and check that candidate could be
4947/// reordered with all the intermediate instructions.
4948bool HexagonGlobalSchedulerImpl::performPullUp() {
4949 std::vector<MachineInstr *> backtrack;
4950 MachineBasicBlock::iterator FromHere;
4951 MachineBasicBlock::iterator FromThisBBEnd;
4952
4953 LLVM_DEBUG(dbgs() << "****** PullUpRegions ***********\n");
4954 // For all regions...
4955 for (std::vector<BasicBlockRegion *>::iterator
4956 CurrentRegion = PullUpRegions.begin(),
4957 E = PullUpRegions.end();
4958 CurrentRegion != E; ++CurrentRegion) {
4959
4960 LLVM_DEBUG(dbgs() << "\n\nRegion with(" << (*CurrentRegion)->size()
4961 << ")BBs\n");
4962
4963 if (!EnableLocalPullUp && (*CurrentRegion)->size() < 2)
4964 continue;
4965
4966 // For all MBB in the region... except the last one.
4967 // ...except when we want to allow local pull-up.
4968 for (auto ToThisBB = (*CurrentRegion)->getRootMBB(),
4969 LastBBInRegion = (*CurrentRegion)->getLastMBB();
4970 ToThisBB != LastBBInRegion; ++ToThisBB) {
4971 // If we do not want to allow same BB pull-up, take an early exit.
4972 if (!EnableLocalPullUp && (std::next(x: ToThisBB) == LastBBInRegion))
4973 break;
4974 if (multipleBranchesFromToBB(BB: *ToThisBB))
4975 break;
4976
4977 auto FromThisBB = ToThisBB;
4978 MachineBasicBlock::iterator ToThisBBEnd = (*ToThisBB)->end();
4979 MachineBasicBlock::iterator MI = (*ToThisBB)->begin();
4980
4981 LLVM_DEBUG(dbgs() << "\n\tHome iterator moved to new BB("
4982 << (*ToThisBB)->getNumber() << ")\n";
4983 (*ToThisBB)->dump());
4984
4985 // For all instructions in the BB.
4986 while (MI != ToThisBBEnd) {
4987 MachineBasicBlock::iterator WorkPoint = MI;
4988 ++MI;
4989
4990 // Trivial check that there are unused resources
4991 // in the current location (cycle).
4992 while (ResourcesAvailableInBundle(CurrentRegion: *CurrentRegion, TargetPacket&: WorkPoint)) {
4993 LLVM_DEBUG(dbgs() << "\nxxxx Next Home in BB("
4994 << (*ToThisBB)->getNumber() << "):\n";
4995 DumpPacket(WorkPoint.getInstrIterator()));
4996 // Keep the path to the candidate.
4997 // It is the traveled path between home and work point.
4998 // Reset it for the new iteration.
4999 backtrack.clear();
5000
5001 // The point of pull-up source (WorkPoint) could begin from the
5002 // current BB, but only if we allow pull-up in the same BB.
5003 // At the moment we do not.
5004 // We also do not process last block in the region,
5005 // so it is safe to always begin with the next BB in the region.
5006 // Start from "next" BB in the region.
5007 if (EnableLocalPullUp) {
5008 FromThisBB = ToThisBB;
5009 FromHere = WorkPoint;
5010 ++FromHere;
5011 FromThisBBEnd = (*FromThisBB)->end();
5012
5013 // Initialize backtrack.
5014 // These are instructions between Home location
5015 // and the WorkPoint.
5016 for (MachineBasicBlock::iterator I = WorkPoint, IE = FromHere;
5017 I != IE; ++I)
5018 backtrack.push_back(x: &*I);
5019 } else {
5020 FromThisBB = ToThisBB;
5021 ++FromThisBB;
5022 FromHere = (*FromThisBB)->begin();
5023 FromThisBBEnd = (*FromThisBB)->end();
5024
5025 // Initialize backtrack.
5026 // These are instructions between Home location
5027 // and the end of the home BB.
5028 for (MachineBasicBlock::iterator I = WorkPoint, IE = ToThisBBEnd;
5029 I != IE; ++I)
5030 backtrack.push_back(x: &*I);
5031 }
5032
5033 // Search for pull-up candidate.
5034 while (true) {
5035 // If this BB is over, move onto the next one
5036 // in this region.
5037 if (FromHere == FromThisBBEnd) {
5038 ++FromThisBB;
5039 // Refresh LastBBInRegion in case tryMultipleInstructions modified
5040 // the regions Elements vector, invalidating the iterator.
5041 LastBBInRegion = (*CurrentRegion)->getLastMBB();
5042 if (FromThisBB == LastBBInRegion)
5043 break;
5044 else {
5045 LLVM_DEBUG(dbgs() << "\n\tNext BB in this region\n";
5046 (*FromThisBB)->dump());
5047 FromThisBBEnd = (*FromThisBB)->end();
5048 FromHere = (*FromThisBB)->begin();
5049 if (FromThisBBEnd == FromHere)
5050 break;
5051 }
5052 }
5053 if ((*FromHere).isDebugInstr()) {
5054 ++FromHere;
5055 continue;
5056 }
5057 // This is a step Home.
5058 backtrack.push_back(x: &*FromHere);
5059 if (!findPullUpCandidates(WorkPoint, FromHere, backtrack,
5060 MaxCandidates: MainCandidateQueueSize))
5061 break;
5062 ++FromHere;
5063 }
5064 // Try to pull-up one of the selected candidates.
5065 if (!tryMultipleInstructions(/*output*/ RetVal&: WorkPoint, CurrentRegion, NextMI&: MI,
5066 ToThisBBEnd, FromThisBBEnd))
5067 break;
5068 }
5069 }
5070 // Refresh LastBBInRegion after potential CFG modifications.
5071 LastBBInRegion = (*CurrentRegion)->getLastMBB();
5072 }
5073 // AllowUnlikelyPath is on by default,
5074 // if we wish to disable it, we can do so here.
5075 if (!AllowUnlikelyPath)
5076 continue;
5077
5078 // We have parsed the likely path through the region.
5079 // Now traverse the other (unlikely) path.
5080 //
5081 // Note: BasicBlockRegion uses a vector for MBB storage, so adding BBs to
5082 // the region while iterating could invalidate iterators. Collect the work
5083 // items first, then process them.
5084 std::vector<std::pair<MachineBasicBlock *, MachineBasicBlock *>>
5085 UnlikelyWork;
5086 UnlikelyWork.reserve(n: (*CurrentRegion)->size());
5087 for (auto ToIt = (*CurrentRegion)->getRootMBB(),
5088 End = (*CurrentRegion)->getLastMBB();
5089 ToIt != End; ++ToIt) {
5090 MachineBasicBlock *ToBB = *ToIt;
5091 MachineBasicBlock *SecondBest = getNextPURBB(MBB: ToBB, SecondBest: true);
5092 if (SecondBest)
5093 UnlikelyWork.emplace_back(args&: ToBB, args&: SecondBest);
5094 }
5095
5096 for (auto [ToBB, SecondBest] : UnlikelyWork) {
5097 LLVM_DEBUG(dbgs() << "\tFor BB:\n"; ToBB->dump());
5098 LLVM_DEBUG(dbgs() << "\tHave SecondBest:\n"; SecondBest->dump());
5099 // Adding this BB to the region should not be done if we
5100 // plan to reuse it(the region) again. For now it is OK.
5101 (*CurrentRegion)->addBBtoRegion(MBB: SecondBest);
5102 LLVM_DEBUG(dbgs() << "\tHome iterator moved to new BB("
5103 << ToBB->getNumber() << ")\n";
5104 ToBB->dump());
5105 MachineBasicBlock::iterator ToThisBBEnd = ToBB->end();
5106 MachineBasicBlock::iterator MI = ToBB->begin();
5107
5108 // For all instructions in the BB.
5109 while (MI != ToThisBBEnd) {
5110 MachineBasicBlock::iterator WorkPoint = MI;
5111 ++MI;
5112
5113 // Trivial check that there are unused resources
5114 // in the current location (cycle).
5115 while (ResourcesAvailableInBundle(CurrentRegion: *CurrentRegion, TargetPacket&: WorkPoint)) {
5116 LLVM_DEBUG(dbgs() << "\nxxxx Second visit Home in BB("
5117 << ToBB->getNumber() << "):\n";
5118 DumpPacket(WorkPoint.getInstrIterator()));
5119
5120 FromHere = SecondBest->begin();
5121 FromThisBBEnd = SecondBest->end();
5122
5123 // Keep the path to the candidate.
5124 backtrack.clear();
5125
5126 // This is Home location.
5127 for (MachineBasicBlock::iterator I = WorkPoint, IE = ToThisBBEnd;
5128 I != IE; ++I)
5129 backtrack.push_back(x: &*I);
5130
5131 while (true) {
5132 // If this BB is over, move onto the next one
5133 // in this region.
5134 if (FromHere == FromThisBBEnd) {
5135 LLVM_DEBUG(dbgs()
5136 << "\tOnly do one successor for the second try\n");
5137 break;
5138 }
5139 if ((*FromHere).isDebugInstr()) {
5140 ++FromHere;
5141 continue;
5142 }
5143 // This is a step Home.
5144 backtrack.push_back(x: &*FromHere);
5145 if (!findPullUpCandidates(WorkPoint, FromHere, backtrack,
5146 MaxCandidates: SecondaryCandidateQueueSize))
5147 break;
5148 ++FromHere;
5149 }
5150 // Try to pull-up one of selected candidate.
5151 if (!tryMultipleInstructions(/*output*/ RetVal&: WorkPoint, CurrentRegion, NextMI&: MI,
5152 ToThisBBEnd, FromThisBBEnd, PathInRegion: false))
5153 break;
5154 }
5155 }
5156 }
5157 }
5158 return true;
5159}
5160
5161bool HexagonGlobalSchedulerImpl::incrementalAddToPacket(MachineInstr &MI) {
5162
5163 LLVM_DEBUG(dbgs() << "\t[AddToPacket] (" << CurrentPacketMIs.size()
5164 << ") adding:\t";
5165 MI.dump());
5166
5167 if (!ResourceTracker->canReserveResources(MI) || !shouldAddToPacket(MI))
5168 return false;
5169
5170 ResourceTracker->reserveResources(MI);
5171 CurrentPacketMIs.push_back(x: &MI);
5172 CurrentState.HomeBundle.push_back(Elt: &MI);
5173
5174 if (QII->isExtended(MI) || QII->isConstExtended(MI) ||
5175 isJumpOutOfRange(MI: &MI)) {
5176 // If at this point of time we cannot reserve resources,
5177 // this might mean that the packet came into the pull-up
5178 // pass already in danger of overflowing.
5179 // Nevertheless, since this is only a possibility of overflow
5180 // no error should be issued here.
5181 if (ResourceTracker->canReserveResources(MI&: *Ext)) {
5182 ResourceTracker->reserveResources(MI&: *Ext);
5183 LLVM_DEBUG(dbgs() << "\t[AddToPacket] (" << CurrentPacketMIs.size()
5184 << ") adding:\t immext_i\n");
5185 CurrentPacketMIs.push_back(x: Ext);
5186 CurrentState.HomeBundle.push_back(Elt: Ext);
5187 return true;
5188 } else {
5189 LLVM_DEBUG(dbgs() << "\t Previous overflow possible.\n");
5190 return false;
5191 }
5192 }
5193 return true;
5194}
5195
5196void HexagonGlobalSchedulerImpl::checkBundleCounts(MachineFunction &Fn) {
5197 if (DisableCheckBundles)
5198 return;
5199
5200 unsigned BundleLimit = 4;
5201
5202 for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end();
5203 MBBi != MBBe; ++MBBi) {
5204
5205 for (MachineBasicBlock::iterator MI = MBBi->instr_begin(),
5206 ME = MBBi->instr_end();
5207 MI != ME; ++MI) {
5208 if (MI->isBundle()) {
5209 MachineBasicBlock::instr_iterator MII = MI.getInstrIterator();
5210 MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
5211
5212 unsigned InstrCount = 0;
5213
5214 for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
5215 if (MII->getOpcode() == TargetOpcode::DBG_VALUE ||
5216 MII->getOpcode() == TargetOpcode::IMPLICIT_DEF ||
5217 MII->getOpcode() == TargetOpcode::CFI_INSTRUCTION ||
5218 MII->isEHLabel() || QII->isEndLoopN(Opcode: MII->getOpcode())) {
5219 continue;
5220 } else {
5221 InstrCount++;
5222 }
5223 }
5224 if (InstrCount > BundleLimit) {
5225 if (WarnOnBundleSize) {
5226 LLVM_DEBUG(dbgs() << "Warning bundle size exceeded " << *MI);
5227 } else {
5228 assert(0 && "Bundle size exceeded");
5229 }
5230 }
5231 }
5232 }
5233 }
5234}
5235
5236/// Debugging only. Count compound and duplex opportunities.
5237unsigned HexagonGlobalSchedulerImpl::countCompounds(MachineFunction &Fn) {
5238 unsigned CompoundCount = 0;
5239 [[maybe_unused]] unsigned DuplexCount = 0;
5240 [[maybe_unused]] unsigned InstOffset = 0;
5241
5242 // Loop over all basic blocks.
5243 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
5244 ++MBB) {
5245 LLVM_DEBUG(dbgs() << "\n BB#" << MBB->getNumber() << " " << MBB->getName()
5246 << " in_func "
5247 << MBB->getParent()->getFunction().getName() << " \n");
5248 for (MachineBasicBlock::iterator MI = MBB->instr_begin(),
5249 ME = MBB->instr_end();
5250 MI != ME; ++MI) {
5251 if (MI->isDebugInstr())
5252 continue;
5253 if (MI->isBundle()) {
5254 MachineBasicBlock::instr_iterator MII = MI.getInstrIterator();
5255 MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
5256 MachineInstr *FirstCompound = NULL, *SecondCompound = NULL;
5257 MachineInstr *FirstDuplex = NULL, *SecondDuplex = NULL;
5258 LLVM_DEBUG(dbgs() << "{\n");
5259
5260 for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
5261 ++MII) {
5262 if (MII->isDebugInstr())
5263 continue;
5264 LLVM_DEBUG(dbgs() << "(" << InstOffset << ")\t");
5265 InstOffset += QII->getSize(MI: *MII);
5266 if (QII->getCompoundCandidateGroup(MI: *MII)) {
5267 if (!FirstCompound) {
5268 FirstCompound = &*MII;
5269 LLVM_DEBUG(dbgs() << "XX ");
5270 } else {
5271 SecondCompound = &*MII;
5272 LLVM_DEBUG(dbgs() << "YY ");
5273 }
5274 }
5275 if (QII->getDuplexCandidateGroup(MI: *MII)) {
5276 if (!FirstDuplex) {
5277 FirstDuplex = &*MII;
5278 LLVM_DEBUG(dbgs() << "AA ");
5279 } else {
5280 SecondDuplex = &*MII;
5281 LLVM_DEBUG(dbgs() << "VV ");
5282 }
5283 }
5284 LLVM_DEBUG(MII->dump());
5285 }
5286 LLVM_DEBUG(dbgs() << "}\n");
5287 if (SecondCompound) {
5288 if (isCompoundPair(MIa: FirstCompound, MIb: SecondCompound)) {
5289 LLVM_DEBUG(dbgs() << "Compound pair (" << CompoundCount << ")\n");
5290 CompoundCount++;
5291 }
5292 }
5293 if (SecondDuplex) {
5294 if (QII->isDuplexPair(MIa: *FirstDuplex, MIb: *SecondDuplex)) {
5295 LLVM_DEBUG(dbgs() << "Duplex pair (" << DuplexCount << ")\n");
5296 DuplexCount++;
5297 }
5298 }
5299 } else {
5300 LLVM_DEBUG(dbgs() << "(" << InstOffset << ")\t");
5301 if (QII->getCompoundCandidateGroup(MI: *MI))
5302 LLVM_DEBUG(dbgs() << "XX ");
5303 if (QII->getDuplexCandidateGroup(MI: *MI))
5304 LLVM_DEBUG(dbgs() << "AA ");
5305 InstOffset += QII->getSize(MI: *MI);
5306 LLVM_DEBUG(MI->dump());
5307 }
5308 }
5309 }
5310 LLVM_DEBUG(dbgs() << "Total compound(" << CompoundCount << ") duplex("
5311 << DuplexCount << ")\n");
5312 return CompoundCount;
5313}
5314
5315//===----------------------------------------------------------------------===//
5316// Public Constructor Functions
5317//===----------------------------------------------------------------------===//
5318
5319FunctionPass *llvm::createHexagonGlobalScheduler() {
5320 return new HexagonGlobalScheduler();
5321}
5322