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