derek.holloway
7502bf64a4
CodeQL / Analyze (actions) (push) Canceled after 0s
CodeQL / Analyze (python) (push) Canceled after 0s
pre-commit / pre-commit (push) Canceled after 0s
Multi-Arch CI / setup (push) Canceled after 0s
Publish build_manylinux_x86_64 images / publish_build_manylinux_x86_64 (push) Canceled after 0s
Setup (Multi-Arch) / setup (push) Canceled after 0s
Multi-Arch CI / Linux::${{ fromJSON(needs.setup.outputs.linux_build_config || '{}').build_variant_label || 'skip' }} (push) Canceled after 0s
Publish TheRock Docker image / build-and-push-image (push) Canceled after 0s
Publish no_rocm_image_ubi10 image / publish_no_rocm_image_ubi10 (push) Canceled after 0s
Multi-Arch CI / Windows::${{ fromJSON(needs.setup.outputs.windows_build_config || '{}').build_variant_label || 'skip' }} (push) Canceled after 0s
Publish TheRock Docker image / build-and-push-image (push) Canceled after 0s
Multi-Arch CI / Manifest Diff (push) Canceled after 0s
TheRock Manifest Diff Report / Generate Manifest Diff Report (push) Canceled after 0s
Multi-Arch CI / CI Summary (push) Canceled after 0s
Publish no_rocm_image_ubuntu24_04 images / publish_no_rocm_image_ubuntu24_04 (push) Canceled after 0s
Publish no_rocm_image_ubuntu24_04_ocl_rt images / publish_no_rocm_image_ubuntu24_04_ocl_rt (push) Canceled after 0s
Publish TheRock Docker image / build-and-push-image (push) Canceled after 0s
Publish TheRock Docker image / build-and-push-image (push) Canceled after 0s
Publish no_rocm_image_ubuntu24_04 images / publish_no_rocm_image_ubuntu24_04_rocgdb (push) Canceled after 0s
Publish no_rocm_image_ubuntu24_04_rocgdb images / publish_no_rocm_image_ubuntu24_04_rocgdb (push) Canceled after 0s
Publish no_rocm_image_ubuntu24_04 images / publish_no_rocm_image_ubuntu24_04_ocl_rt (push) Canceled after 0s
Publish TheRock Docker image / build-and-push-image (push) Canceled after 0s
Unit Tests / Unit Tests :: ubuntu-24.04 (push) Canceled after 0s
Unit Tests / Unit Tests :: windows-2022 (push) Canceled after 0s
Publish no_rocm_image_ubuntu24_04 images / publish_no_rocm_image_ubuntu24_04_media (push) Canceled after 0s
Unit Tests / Unit Tests Summary (push) Canceled after 0s
Publish no_rocm_image_ubuntu24_04 images / publish_no_rocm_image_ubuntu24_04_openmpi (push) Canceled after 0s
5331 lines
202 KiB
C++
5331 lines
202 KiB
C++
|
|
//===----- HexagonGlobalScheduler.cpp - Global Scheduler ------------------===//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// Basic infrastructure for the global scheduling + Hexagon pull-up pass.
|
|
// Currently run at the very end of code generation for Hexagon, cleans
|
|
// up lost scheduling opportunities. Currently breaks liveness, so no passes
|
|
// that rely on liveness info should run afterwards. Will be fixed in future
|
|
// versions.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
#include "Hexagon.h"
|
|
#include "HexagonGlobalRegion.h"
|
|
#include "HexagonMachineFunctionInfo.h"
|
|
#include "HexagonRegisterInfo.h"
|
|
#include "HexagonSubtarget.h"
|
|
#include "HexagonTargetMachine.h"
|
|
#include "HexagonVLIWPacketizer.h"
|
|
#include "llvm/ADT/DenseMap.h"
|
|
#include "llvm/ADT/SmallSet.h"
|
|
#include "llvm/ADT/Statistic.h"
|
|
#include "llvm/Analysis/AliasAnalysis.h"
|
|
#include "llvm/Analysis/ValueTracking.h"
|
|
#include "llvm/CodeGen/DFAPacketizer.h"
|
|
#include "llvm/CodeGen/LatencyPriorityQueue.h"
|
|
#include "llvm/CodeGen/LiveIntervals.h"
|
|
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
|
|
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
|
|
#include "llvm/CodeGen/MachineDominators.h"
|
|
#include "llvm/CodeGen/MachineFrameInfo.h"
|
|
#include "llvm/CodeGen/MachineFunctionPass.h"
|
|
#include "llvm/CodeGen/MachineInstrBuilder.h"
|
|
#include "llvm/CodeGen/MachineLoopInfo.h"
|
|
#include "llvm/CodeGen/MachineRegisterInfo.h"
|
|
#include "llvm/CodeGen/Passes.h"
|
|
#include "llvm/CodeGen/PseudoSourceValue.h"
|
|
#include "llvm/CodeGen/SchedulerRegistry.h"
|
|
#include "llvm/CodeGen/TargetInstrInfo.h"
|
|
#include "llvm/CodeGen/TargetRegisterInfo.h"
|
|
#include "llvm/CodeGen/TargetSchedule.h"
|
|
#include "llvm/IR/Operator.h"
|
|
#include "llvm/InitializePasses.h"
|
|
#include "llvm/MC/MCInstrItineraries.h"
|
|
#include "llvm/Support/CommandLine.h"
|
|
#include "llvm/Support/Compiler.h"
|
|
#include "llvm/Support/Debug.h"
|
|
#include "llvm/Support/MathExtras.h"
|
|
#include "llvm/Target/TargetMachine.h"
|
|
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
|
|
|
|
#include <list>
|
|
#include <map>
|
|
|
|
#define DEBUG_TYPE "global_sched"
|
|
|
|
using namespace llvm;
|
|
|
|
STATISTIC(HexagonNumPullUps, "Number of instructions pull-ups");
|
|
STATISTIC(HexagonNumDualJumps, "Number of dual jumps formed");
|
|
|
|
static cl::opt<bool> DisablePullUp("disable-pull-up", cl::Hidden,
|
|
cl::desc("Disable Hexagon pull-up pass"));
|
|
|
|
static cl::opt<bool> EnableSpeculativePullUp(
|
|
"enable-speculative-pull-up", cl::Hidden,
|
|
cl::desc("Enable speculation during Hexagon pull-up pass"));
|
|
|
|
static cl::opt<bool> EnableLocalPullUp(
|
|
"enable-local-pull-up", cl::Hidden, cl::init(true),
|
|
cl::desc("Enable same BB pull during Hexagon pull-up pass"));
|
|
|
|
static cl::opt<bool> AllowSpeculateLoads(
|
|
"speculate-loads-on-pull-up", cl::Hidden, cl::init(true),
|
|
cl::desc("Allow speculative loads during Hexagon pull-up pass"));
|
|
|
|
static cl::opt<bool> AllowCmpBranchLoads(
|
|
"cmp-branch-loads-pull-up", cl::Hidden, cl::init(true),
|
|
cl::desc("Allow compare-branch loads during Hexagon pull-up pass"));
|
|
|
|
static cl::opt<bool> AllowUnlikelyPath("unlikely-path-pull-up", cl::Hidden,
|
|
cl::init(true),
|
|
cl::desc("Allow unlikely path pull up"));
|
|
|
|
static cl::opt<bool>
|
|
PerformDualJumps("dual-jump-in-pull-up", cl::Hidden, cl::init(true),
|
|
cl::desc("Perform dual jump formation during pull up"));
|
|
|
|
static cl::opt<bool> AllowDependentPullUp(
|
|
"enable-dependent-pull-up", cl::Hidden, cl::init(true),
|
|
cl::desc("Perform dual jump formation during pull up"));
|
|
|
|
static cl::opt<bool>
|
|
AllowBBPeelPullUp("enable-bb-peel-pull-up", cl::Hidden, cl::init(true),
|
|
cl::desc("Peel a reg copy out of a BBloop"));
|
|
|
|
static cl::opt<bool> PreventCompoundSeparation(
|
|
"prevent-compound-separation", cl::Hidden,
|
|
cl::desc("Do not destroy existing compounds during pull up"));
|
|
|
|
static cl::opt<bool> PreventDuplexSeparation(
|
|
"prevent-duplex-separation", cl::Hidden, cl::init(true),
|
|
cl::desc("Do not destroy existing duplexes during pull up"));
|
|
|
|
static cl::opt<unsigned> MainCandidateQueueSize("pull-up-main-queue-size",
|
|
cl::Hidden, cl::init(8));
|
|
|
|
static cl::opt<unsigned> SecondaryCandidateQueueSize("pull-up-sec-queue-size",
|
|
cl::Hidden, cl::init(2));
|
|
|
|
static cl::opt<bool> PostPullUpOpt(
|
|
"post-pull-up-opt", cl::Hidden, cl::Optional, cl::init(true),
|
|
cl::desc("Enable opt. exposed by pull-up e.g., remove redundant jumps"));
|
|
|
|
static cl::opt<bool> SpeculateNonPredInsn(
|
|
"speculate-non-pred-insn", cl::Hidden, cl::Optional, cl::init(true),
|
|
cl::desc("Speculate non-predicable instructions in parent BB"));
|
|
|
|
static cl::opt<bool>
|
|
DisableCheckBundles("disable-hexagon-check-bundles", cl::Hidden,
|
|
cl::init(true),
|
|
cl::desc("Disable Hexagon check bundles pass"));
|
|
|
|
static cl::opt<bool>
|
|
WarnOnBundleSize("warn-on-bundle-size", cl::Hidden,
|
|
cl::desc("Hexagon check bundles and warn on size"));
|
|
|
|
static cl::opt<bool>
|
|
ForceNoopHazards("force-noop-hazards", cl::Hidden, cl::init(false),
|
|
cl::desc("Force noop hazards in scheduler"));
|
|
static cl::opt<bool> OneFloatPerPacket(
|
|
"single-float-packet", cl::Hidden,
|
|
cl::desc("Allow only one single floating point instruction in a packet"));
|
|
static cl::opt<bool> OneComplexPerPacket(
|
|
"single-complex-packet", cl::Hidden,
|
|
cl::desc("Allow only one complex instruction in a packet"));
|
|
|
|
namespace llvm {
|
|
FunctionPass *createHexagonGlobalScheduler();
|
|
void initializeHexagonGlobalSchedulerPass(PassRegistry &);
|
|
} // namespace llvm
|
|
|
|
namespace {
|
|
class HexagonGlobalSchedulerImpl;
|
|
|
|
class HexagonGlobalScheduler : public MachineFunctionPass {
|
|
public:
|
|
static char ID;
|
|
HexagonGlobalScheduler() : MachineFunctionPass(ID) {
|
|
initializeHexagonGlobalSchedulerPass(*PassRegistry::getPassRegistry());
|
|
}
|
|
|
|
void getAnalysisUsage(AnalysisUsage &AU) const override {
|
|
AU.addRequiredID(MachineDominatorsID);
|
|
AU.addRequired<MachineLoopInfoWrapperPass>();
|
|
AU.addRequired<AAResultsWrapperPass>();
|
|
AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
|
|
AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
|
|
AU.addRequired<MachineDominatorTreeWrapperPass>();
|
|
MachineFunctionPass::getAnalysisUsage(AU);
|
|
}
|
|
|
|
StringRef getPassName() const override { return "Hexagon Global Scheduler"; }
|
|
|
|
bool runOnMachineFunction(MachineFunction &Fn) override;
|
|
};
|
|
char HexagonGlobalScheduler::ID = 0;
|
|
|
|
// Describes a single pull-up candidate.
|
|
class PullUpCandidate {
|
|
MachineBasicBlock::instr_iterator CandidateLocation;
|
|
MachineBasicBlock::iterator HomeBundle;
|
|
bool DependentOp;
|
|
signed BenefitCost;
|
|
std::vector<MachineInstr *> Backtrack;
|
|
|
|
public:
|
|
PullUpCandidate(MachineBasicBlock::instr_iterator MII) {
|
|
CandidateLocation = MII;
|
|
BenefitCost = 0;
|
|
}
|
|
|
|
PullUpCandidate(MachineBasicBlock::instr_iterator MII,
|
|
MachineBasicBlock::iterator HomeBundle,
|
|
std::vector<MachineInstr *> &backtrack, bool DependentOp,
|
|
signed Cost)
|
|
: CandidateLocation(MII), HomeBundle(HomeBundle),
|
|
DependentOp(DependentOp), BenefitCost(Cost) {
|
|
// Copy of the backtrack.
|
|
Backtrack = backtrack;
|
|
}
|
|
|
|
void populate(MachineBasicBlock::instr_iterator &MII,
|
|
MachineBasicBlock::iterator &WorkPoint,
|
|
std::vector<MachineInstr *> &backtrack, bool &dependentOp) {
|
|
MII = CandidateLocation;
|
|
WorkPoint = HomeBundle;
|
|
backtrack = Backtrack;
|
|
dependentOp = DependentOp;
|
|
}
|
|
|
|
signed getCost() { return BenefitCost; }
|
|
|
|
MachineInstr *getCandidate() { return &*CandidateLocation; }
|
|
|
|
void dump() {
|
|
dbgs() << "Cost(" << BenefitCost;
|
|
dbgs() << ") Dependent(" << DependentOp;
|
|
dbgs() << ") backtrack size(" << Backtrack.size() << ")\t";
|
|
CandidateLocation->dump();
|
|
}
|
|
};
|
|
|
|
/// PullUpCandidateSorter - A Sort utility for pull-up candidates.
|
|
struct PullUpCandidateSorter {
|
|
PullUpCandidateSorter() {}
|
|
bool operator()(PullUpCandidate *LHS, PullUpCandidate *RHS) {
|
|
return LHS->getCost() > RHS->getCost();
|
|
}
|
|
};
|
|
|
|
// Describes a single pull-up opportunity: location to which
|
|
// pull-up is possible with additional information about it.
|
|
// Also contains a list of pull-up candidates for this location.
|
|
class PullUpState {
|
|
friend class HexagonGlobalSchedulerImpl;
|
|
// Available opportunity for pull-up.
|
|
// FAIAP a bundle with an empty slot.
|
|
MachineBasicBlock::iterator HomeLocation;
|
|
// Home bundle copy. This is here for speed of iteration.
|
|
SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> HomeBundle;
|
|
// Multiple candidates for the Home location.
|
|
SmallVector<PullUpCandidate *, 8> PullUpCandidates;
|
|
|
|
const HexagonInstrInfo *QII;
|
|
|
|
public:
|
|
PullUpState(const HexagonInstrInfo *QII) : HomeLocation(NULL), QII(QII) {}
|
|
|
|
~PullUpState() { reset(); }
|
|
|
|
void addPullUpCandidate(MachineBasicBlock::instr_iterator MII,
|
|
MachineBasicBlock::iterator HomeBundle,
|
|
std::vector<MachineInstr *> &backtrack,
|
|
bool DependentOp, signed Cost) {
|
|
LLVM_DEBUG(dbgs() << "\t[addPullUpCandidate]: "; (*MII).dump());
|
|
PullUpCandidate *PUI =
|
|
new PullUpCandidate(MII, HomeBundle, backtrack, DependentOp, Cost);
|
|
PullUpCandidates.push_back(PUI);
|
|
}
|
|
|
|
void dump() {
|
|
unsigned element = 0;
|
|
for (unsigned i = 0; i < HomeBundle.size(); i++) {
|
|
dbgs() << "[" << element++;
|
|
dbgs() << "] Home Duplex("
|
|
<< QII->getDuplexCandidateGroup(*HomeBundle[i]);
|
|
dbgs() << ") Compound (" << QII->getCompoundCandidateGroup(*HomeBundle[i])
|
|
<< ") ";
|
|
HomeBundle[i]->dump();
|
|
}
|
|
dbgs() << "\n";
|
|
element = 0;
|
|
for (SmallVector<PullUpCandidate *, 4>::iterator
|
|
I = PullUpCandidates.begin(),
|
|
E = PullUpCandidates.end();
|
|
I != E; ++I) {
|
|
dbgs() << "[" << element++ << "] Cand: Compound(";
|
|
dbgs() << QII->getCompoundCandidateGroup(*(*I)->getCandidate()) << ") ";
|
|
(*I)->dump();
|
|
}
|
|
}
|
|
|
|
void reset() {
|
|
HomeLocation = NULL;
|
|
for (SmallVector<PullUpCandidate *, 4>::iterator
|
|
I = PullUpCandidates.begin(),
|
|
E = PullUpCandidates.end();
|
|
I != E; ++I)
|
|
delete *I;
|
|
PullUpCandidates.clear();
|
|
HomeBundle.clear();
|
|
}
|
|
|
|
void addHomeLocation(MachineBasicBlock::iterator WorkPoint) {
|
|
reset();
|
|
HomeLocation = WorkPoint;
|
|
}
|
|
|
|
unsigned haveCandidates() { return PullUpCandidates.size(); }
|
|
};
|
|
|
|
class HexagonGlobalSchedulerImpl : public HexagonPacketizerList {
|
|
// List of PullUp regions for this function.
|
|
std::vector<BasicBlockRegion *> PullUpRegions;
|
|
// Map of approximate distance for each BB from the
|
|
// function base.
|
|
DenseMap<MachineBasicBlock *, unsigned> BlockToInstOffset;
|
|
// Keep track of multiple pull-up candidates.
|
|
PullUpState CurrentState;
|
|
// Empty basic blocks as a result of pull-up.
|
|
std::vector<MachineBasicBlock *> EmptyBBs;
|
|
// Save all the Speculated MachineInstr that were moved
|
|
// FROM MachineBasicBlock because we don't want to have
|
|
// more than one speculated instructions pulled into one packet.
|
|
// TODO: This can be removed once we have a use-def dependency chain
|
|
// for all the instructions in a function.
|
|
std::map<MachineInstr *, MachineBasicBlock *> SpeculatedIns;
|
|
// All the regs and their aliases used by an instruction.
|
|
std::map<MachineInstr *, std::vector<unsigned>> MIUseSet;
|
|
// All the regs and their aliases defined by an instruction.
|
|
std::map<MachineInstr *, std::vector<unsigned>> MIDefSet;
|
|
|
|
AliasAnalysis *AA;
|
|
const MachineBranchProbabilityInfo *MBPI;
|
|
const MachineBlockFrequencyInfo *MBFI;
|
|
const MachineRegisterInfo *MRI;
|
|
const MachineFrameInfo &MFI;
|
|
const HexagonRegisterInfo *QRI;
|
|
const HexagonInstrInfo *QII;
|
|
MachineLoopInfo &MLI;
|
|
MachineDominatorTree &MDT;
|
|
MachineInstrBuilder Ext;
|
|
MachineInstrBuilder Nop;
|
|
const unsigned PacketSize;
|
|
TargetSchedModel TSchedModel;
|
|
|
|
public:
|
|
// Ctor.
|
|
HexagonGlobalSchedulerImpl(MachineFunction &MF, MachineLoopInfo &MLI,
|
|
MachineDominatorTree &MDT, AliasAnalysis *AA,
|
|
const MachineBranchProbabilityInfo *MBPI,
|
|
const MachineBlockFrequencyInfo *MBFI,
|
|
const MachineRegisterInfo *MRI,
|
|
const MachineFrameInfo &MFI,
|
|
const HexagonRegisterInfo *QRI);
|
|
HexagonGlobalSchedulerImpl(const HexagonGlobalSchedulerImpl &) = delete;
|
|
HexagonGlobalSchedulerImpl &
|
|
operator=(const HexagonGlobalSchedulerImpl &) = delete;
|
|
|
|
~HexagonGlobalSchedulerImpl() {
|
|
// Free regions.
|
|
for (std::vector<BasicBlockRegion *>::iterator I = PullUpRegions.begin(),
|
|
E = PullUpRegions.end();
|
|
I != E; ++I)
|
|
delete *I;
|
|
MF.deleteMachineInstr(Ext);
|
|
MF.deleteMachineInstr(Nop);
|
|
}
|
|
|
|
// initPacketizerState - initialize some internal flags.
|
|
void initPacketizerState() override;
|
|
|
|
// ignorePseudoInstruction - Ignore bundling of pseudo instructions.
|
|
bool ignoreInstruction(MachineInstr *MI);
|
|
|
|
// isSoloInstruction - return true if instruction MI can not be packetized
|
|
// with any other instruction, which means that MI itself is a packet.
|
|
bool isSoloInstruction(const MachineInstr &MI) override;
|
|
|
|
// Add MI to packetizer state. Returns false if it cannot fit in the packet.
|
|
bool incrementalAddToPacket(MachineInstr &MI);
|
|
|
|
// formPullUpRegions - Top level call to form regions.
|
|
bool formPullUpRegions(MachineFunction &Fn);
|
|
|
|
// performPullUp - Top level call for pull-up.
|
|
bool performPullUp();
|
|
|
|
// performPullUpCFG - Top level call for pull-up CFG.
|
|
bool performPullUpCFG(MachineFunction &Fn);
|
|
|
|
// performExposedOptimizations -
|
|
// Look for optimization opportunities after pullup.
|
|
bool performExposedOptimizations(MachineFunction &Fn);
|
|
|
|
// optimizeBranching -
|
|
// 1. A conditional-jump transfers control to a BB with
|
|
// jump as the only instruction.
|
|
// if(p0) jump t1
|
|
// // ...
|
|
// t1: jump t2
|
|
// 2. When a BB with a single conditional jump, jumps to succ-of-succ and
|
|
// falls-through BB with only jump instruction.
|
|
// { if(p0) jump t1 }
|
|
// { jump t2 }
|
|
// t1: { ... }
|
|
MachineBasicBlock *optimizeBranches(MachineBasicBlock *MBB,
|
|
MachineBasicBlock *TBB,
|
|
MachineInstr *FirstTerm,
|
|
MachineBasicBlock *FBB);
|
|
|
|
// removeRedundantBranches -
|
|
// 1. Remove jump to the layout successor.
|
|
// 2. Remove multiple (dual) jump to the same target.
|
|
bool removeRedundantBranches(MachineBasicBlock *MBB, MachineBasicBlock *TBB,
|
|
MachineInstr *FirstTerm, MachineBasicBlock *FBB,
|
|
MachineInstr *SecondTerm);
|
|
|
|
// optimizeDualJumps - optimize dual jumps in a packet
|
|
// For now: Replace dual jump by single jump in case of a fall through.
|
|
bool optimizeDualJumps(MachineBasicBlock *MBB, MachineBasicBlock *TBB,
|
|
MachineInstr *FirstTerm, MachineBasicBlock *FBB,
|
|
MachineInstr *SecondTerm);
|
|
|
|
void GenUseDefChain(MachineFunction &Fn);
|
|
|
|
// Return region pointer or null if none found.
|
|
BasicBlockRegion *getRegionForMBB(std::vector<BasicBlockRegion *> &Regions,
|
|
MachineBasicBlock *MBB);
|
|
|
|
// Saves all the used-regs and their aliases in Uses.
|
|
// Saves all the defined-regs and their aliases in Defs.
|
|
void MIUseDefSet(MachineInstr *MI, std::vector<unsigned> &Defs,
|
|
std::vector<unsigned> &Uses);
|
|
|
|
// This is a very useful debug utility.
|
|
unsigned countCompounds(MachineFunction &Fn);
|
|
|
|
// Check bundle counts
|
|
void checkBundleCounts(MachineFunction &Fn);
|
|
|
|
private:
|
|
// Get next BB to be included into the region.
|
|
MachineBasicBlock *getNextPURBB(MachineBasicBlock *MBB, bool SecondBest);
|
|
|
|
void setUsedRegs(BitVector &Set, unsigned Reg);
|
|
bool AliasingRegs(unsigned RegA, unsigned RegB);
|
|
|
|
// Test is true if the two MIs cannot be safely reordered.
|
|
bool ReorderDependencyTest(MachineInstr *MIa, MachineInstr *MIb);
|
|
|
|
bool canAddMIToThisPacket(
|
|
MachineInstr *MI,
|
|
SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> &Bundle);
|
|
|
|
bool CanPromoteToDotNew(MachineInstr *MI, unsigned Reg);
|
|
|
|
bool pullUpPeelBBLoop(MachineBasicBlock *PredBB, MachineBasicBlock *LoopBB);
|
|
|
|
MachineInstr *findBundleAndBranch(MachineBasicBlock *BB,
|
|
MachineBasicBlock::iterator &Bundle);
|
|
|
|
// Does this bundle have any slots left?
|
|
bool ResourcesAvailableInBundle(BasicBlockRegion *CurrentRegion,
|
|
MachineBasicBlock::iterator &TargetPacket);
|
|
|
|
// Perform the actual move.
|
|
MachineInstr *MoveAndUpdateLiveness(
|
|
BasicBlockRegion *CurrentRegion, MachineBasicBlock *HomeBB,
|
|
MachineInstr *InstrToMove, bool NeedToNewify, unsigned DepReg,
|
|
bool MovingDependentOp, MachineBasicBlock *OriginBB,
|
|
MachineInstr *OriginalInstruction, SmallVector<MachineOperand, 4> &Cond,
|
|
MachineBasicBlock::iterator &SourceLocation,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
std::vector<MachineInstr *> &backtrack);
|
|
|
|
// Updates incremental kill patterns along the backtrack.
|
|
void updateKillAlongThePath(MachineBasicBlock *HomeBB,
|
|
MachineBasicBlock *OriginBB,
|
|
MachineBasicBlock::instr_iterator &Head,
|
|
MachineBasicBlock::instr_iterator &Tail,
|
|
MachineBasicBlock::iterator &SourcePacket,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
std::vector<MachineInstr *> &backtrack);
|
|
|
|
// Gather list of pull-up candidates.
|
|
bool findPullUpCandidates(MachineBasicBlock::iterator &WorkPoint,
|
|
MachineBasicBlock::iterator &FromHere,
|
|
std::vector<MachineInstr *> &backtrack,
|
|
unsigned MaxCandidates);
|
|
|
|
// See if the instruction could be pulled up.
|
|
bool tryMultipleInstructions(
|
|
MachineBasicBlock::iterator &RetVal, /* output parameter */
|
|
std::vector<BasicBlockRegion *>::iterator &CurrentRegion,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
MachineBasicBlock::iterator &ToThisBBEnd,
|
|
MachineBasicBlock::iterator &FromThisBBEnd, bool PathInRegion = true);
|
|
|
|
// Try to move MI into existing bundle.
|
|
bool MoveMItoBundle(BasicBlockRegion *CurrentRegion,
|
|
MachineBasicBlock::instr_iterator &InstrToMove,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
MachineBasicBlock::iterator &SourceLocation,
|
|
std::vector<MachineInstr *> &backtrack,
|
|
bool MovingDependentOp, bool PathInRegion);
|
|
|
|
// Insert temporary MI copy into MBB.
|
|
MachineBasicBlock::instr_iterator
|
|
insertTempCopy(MachineBasicBlock *MBB,
|
|
MachineBasicBlock::iterator &TargetPacket, MachineInstr *MI,
|
|
bool DeleteOldCopy);
|
|
|
|
MachineBasicBlock::instr_iterator
|
|
findInsertPositionInBundle(MachineBasicBlock::iterator &Bundle,
|
|
MachineInstr *MI, bool &LastInBundle);
|
|
|
|
bool NeedToNewify(MachineBasicBlock::instr_iterator NewMI, unsigned *DepReg,
|
|
MachineInstr *TargetPacket);
|
|
|
|
bool CanNewifiedBeUsedInBundle(MachineBasicBlock::instr_iterator NewMI,
|
|
unsigned DepReg, MachineInstr *TargetPacket);
|
|
|
|
void addInstructionToExistingBundle(MachineBasicBlock *HomeBB,
|
|
MachineBasicBlock::instr_iterator &Head,
|
|
MachineBasicBlock::instr_iterator &Tail,
|
|
MachineBasicBlock::instr_iterator &NewMI,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
std::vector<MachineInstr *> &backtrack);
|
|
|
|
void removeInstructionFromExistingBundle(
|
|
MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
|
|
MachineBasicBlock::instr_iterator &Tail,
|
|
MachineBasicBlock::iterator &SourceLocation,
|
|
MachineBasicBlock::iterator &NextMI, bool MovingDependentOp,
|
|
std::vector<MachineInstr *> &backtrack);
|
|
|
|
// Check for conditional register operaton.
|
|
bool MIsCondAssign(MachineInstr *BMI, MachineInstr *MI,
|
|
SmallVector<unsigned, 4> &Defs);
|
|
|
|
// Test all the conditions required for instruction to be
|
|
// speculative. These are just required conditions, cost
|
|
// or benefit should be computed elsewhere.
|
|
bool canMIBeSpeculated(MachineInstr *MI, MachineBasicBlock *ToBB,
|
|
MachineBasicBlock *FromBB,
|
|
std::vector<MachineInstr *> &backtrack);
|
|
|
|
// See if this branch target belongs to the current region.
|
|
bool isBranchWithinRegion(BasicBlockRegion *CurrentRegion, MachineInstr *MI);
|
|
|
|
// A collection of low level utilities.
|
|
bool MIsAreDependent(MachineInstr *MIa, MachineInstr *MIb);
|
|
bool MIsHaveTrueDependency(MachineInstr *MIa, MachineInstr *MIb);
|
|
bool canReorderMIs(MachineInstr *MIa, MachineInstr *MIb);
|
|
bool canCauseStall(MachineInstr *MI, MachineInstr *MJ);
|
|
bool canThisMIBeMoved(MachineInstr *MI,
|
|
MachineBasicBlock::iterator &WorkPoint,
|
|
bool &MovingDependentOp, int &Cost);
|
|
bool MIisDualJumpCandidate(MachineInstr *MI,
|
|
MachineBasicBlock::iterator &WorkPoint);
|
|
bool DemoteToDotOld(MachineInstr *MI);
|
|
bool isNewifiable(MachineBasicBlock::instr_iterator MII, unsigned DepReg,
|
|
MachineInstr *TargetPacket);
|
|
bool IsNewifyStore(MachineInstr *MI);
|
|
bool isJumpOutOfRange(MachineInstr *MI);
|
|
bool IsDualJumpFirstCandidate(MachineInstr *MI);
|
|
bool IsDualJumpFirstCandidate(MachineBasicBlock *MBB);
|
|
bool IsDualJumpFirstCandidate(MachineBasicBlock::iterator &TargetPacket);
|
|
bool IsNotDualJumpFirstCandidate(MachineInstr *MI);
|
|
bool isJumpOutOfRange(MachineInstr *UnCond, MachineInstr *Cond);
|
|
bool IsDualJumpSecondCandidate(MachineInstr *MI);
|
|
bool tryAllocateResourcesForConstExt(MachineInstr *MI, bool UpdateState);
|
|
bool isCompoundPair(MachineInstr *MIa, MachineInstr *MIb);
|
|
bool doesMIDefinesPredicate(MachineInstr *MI, SmallVector<unsigned, 4> &Defs);
|
|
bool AnalyzeBBBranches(MachineBasicBlock *MBB, MachineBasicBlock *&TBB,
|
|
MachineInstr *&FirstTerm, MachineBasicBlock *&FBB,
|
|
MachineInstr *&SecondTerm);
|
|
inline bool multipleBranchesFromToBB(MachineBasicBlock *BB) const;
|
|
};
|
|
} // namespace
|
|
|
|
INITIALIZE_PASS_BEGIN(HexagonGlobalScheduler, "global-sched",
|
|
"Hexagon Global Scheduler", false, false)
|
|
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
|
|
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
|
|
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
|
|
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
|
|
INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
|
|
INITIALIZE_PASS_END(HexagonGlobalScheduler, "global-sched",
|
|
"Hexagon Global Scheduler", false, false)
|
|
|
|
/// HexagonGlobalSchedulerImpl Ctor.
|
|
HexagonGlobalSchedulerImpl::HexagonGlobalSchedulerImpl(
|
|
MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
|
|
AliasAnalysis *AA, const MachineBranchProbabilityInfo *MBPI,
|
|
const MachineBlockFrequencyInfo *MBFI, const MachineRegisterInfo *MRI,
|
|
const MachineFrameInfo &MFI, const HexagonRegisterInfo *QRI)
|
|
: HexagonPacketizerList(MF, MLI, AA, nullptr, false), PullUpRegions(0),
|
|
CurrentState((const HexagonInstrInfo *)TII), AA(AA), MBPI(MBPI),
|
|
MBFI(MBFI), MRI(MRI), MFI(MFI), QRI(QRI), MLI(MLI), MDT(MDT),
|
|
PacketSize(MF.getSubtarget().getSchedModel().IssueWidth) {
|
|
QII = (const HexagonInstrInfo *)TII;
|
|
Ext = BuildMI(MF, DebugLoc(), QII->get(Hexagon::A4_ext));
|
|
Nop = BuildMI(MF, DebugLoc(), QII->get(Hexagon::A2_nop));
|
|
TSchedModel.init(&MF.getSubtarget());
|
|
}
|
|
|
|
// Return bundle size without debug instructions.
|
|
static unsigned nonDbgBundleSize(MachineBasicBlock::iterator &TargetPacket) {
|
|
MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
|
|
MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
|
|
unsigned count = 0;
|
|
for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
|
|
if (MII->isDebugInstr())
|
|
continue;
|
|
count++;
|
|
}
|
|
return count;
|
|
}
|
|
|
|
/// The pass main entry point.
|
|
bool HexagonGlobalScheduler::runOnMachineFunction(MachineFunction &Fn) {
|
|
auto &HST = Fn.getSubtarget<HexagonSubtarget>();
|
|
if (DisablePullUp || !HST.usePackets() || skipFunction(Fn.getFunction()))
|
|
return false;
|
|
|
|
const MachineRegisterInfo *MRI = &Fn.getRegInfo();
|
|
const MachineFrameInfo &MFI = Fn.getFrameInfo();
|
|
const HexagonRegisterInfo *QRI = HST.getRegisterInfo();
|
|
MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
|
|
MachineDominatorTree &MDT =
|
|
getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
|
|
const MachineBranchProbabilityInfo *MBPI =
|
|
&getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
|
|
const MachineBlockFrequencyInfo *MBFI =
|
|
&getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
|
|
AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
|
|
|
|
// Preserve comounds if Opt Size.
|
|
const Function &F = Fn.getFunction();
|
|
if (F.hasOptSize() && PreventCompoundSeparation.getNumOccurrences() == 0)
|
|
PreventCompoundSeparation = true;
|
|
|
|
// Instantiate the Scheduler.
|
|
HexagonGlobalSchedulerImpl GlobalSchedulerState(Fn, MLI, MDT, AA, MBPI, MBFI,
|
|
MRI, MFI, QRI);
|
|
|
|
// DFA state table should not be empty.
|
|
assert(GlobalSchedulerState.getResourceTracker() && "Empty DFA table!");
|
|
|
|
// Loop over all of the basic blocks.
|
|
// PullUp regions are basically traces with no side entrances.
|
|
// Might want to traverse BB by frequency.
|
|
GlobalSchedulerState.checkBundleCounts(Fn);
|
|
|
|
// Pullup does not handle hazards yet.
|
|
if (!DisablePullUp.getPosition() && ForceNoopHazards)
|
|
return true;
|
|
|
|
LLVM_DEBUG(GlobalSchedulerState.countCompounds(Fn));
|
|
GlobalSchedulerState.GenUseDefChain(Fn);
|
|
GlobalSchedulerState.formPullUpRegions(Fn);
|
|
GlobalSchedulerState.performPullUp();
|
|
GlobalSchedulerState.performPullUpCFG(Fn);
|
|
if (PostPullUpOpt) {
|
|
GlobalSchedulerState.formPullUpRegions(Fn);
|
|
GlobalSchedulerState.performExposedOptimizations(Fn);
|
|
}
|
|
LLVM_DEBUG(GlobalSchedulerState.countCompounds(Fn));
|
|
|
|
return true;
|
|
}
|
|
|
|
/// Allocate resources (i.e. 4 bytes) for constant extender. If succeess, return
|
|
/// true, otherwise, return false.
|
|
bool HexagonGlobalSchedulerImpl::tryAllocateResourcesForConstExt(
|
|
MachineInstr *MI, bool UpdateState = true) {
|
|
if (ResourceTracker->canReserveResources(*Ext)) {
|
|
// We do not always want to change the state of ResourceTracker.
|
|
// When we do not want to change it, we need to test for additional
|
|
// corner cases.
|
|
if (UpdateState)
|
|
ResourceTracker->reserveResources(*Ext);
|
|
else if (CurrentPacketMIs.size() >= PacketSize - 1)
|
|
return false;
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
static bool IsSchedBarrier(const MachineInstr *MI) {
|
|
return MI->getOpcode() == Hexagon::Y2_barrier;
|
|
}
|
|
|
|
static bool IsIndirectCall(const MachineInstr *MI) {
|
|
return MI->getOpcode() == Hexagon::J2_callr;
|
|
}
|
|
|
|
#ifndef NDEBUG
|
|
static void DumpLinked(MachineInstr *MI) {
|
|
if (MI->isBundledWithPred())
|
|
dbgs() << "^";
|
|
else
|
|
dbgs() << " ";
|
|
if (MI->isBundledWithSucc())
|
|
dbgs() << "v";
|
|
else
|
|
dbgs() << " ";
|
|
MI->dump();
|
|
}
|
|
|
|
static void DumpPacket(MachineBasicBlock::instr_iterator MII) {
|
|
if (MII == MachineBasicBlock::instr_iterator()) {
|
|
dbgs() << "\tNULL\n";
|
|
return;
|
|
}
|
|
MachineInstr *MI = &*MII;
|
|
MachineBasicBlock *MBB = MI->getParent();
|
|
// Uninserted instruction.
|
|
if (!MBB) {
|
|
dbgs() << "\tUnattached: ";
|
|
DumpLinked(MI);
|
|
return;
|
|
}
|
|
dbgs() << "\t";
|
|
DumpLinked(MI);
|
|
if (MI->isBundle()) {
|
|
MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
|
|
for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII) {
|
|
dbgs() << "\t\t*";
|
|
DumpLinked(&*MII);
|
|
}
|
|
}
|
|
}
|
|
|
|
static void DumpPacket(MachineBasicBlock::instr_iterator MII,
|
|
MachineBasicBlock::instr_iterator BBEnd) {
|
|
if (MII == BBEnd) {
|
|
dbgs() << "\tBBEnd\n";
|
|
return;
|
|
}
|
|
|
|
DumpPacket(MII);
|
|
}
|
|
#endif
|
|
|
|
static bool isBranch(MachineInstr *MI) {
|
|
if (MI->isBundle()) {
|
|
MachineBasicBlock::instr_iterator MII = MI->getIterator();
|
|
MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
|
|
for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII) {
|
|
if (MII->isBranch())
|
|
return true;
|
|
}
|
|
} else
|
|
return MI->isBranch();
|
|
return false;
|
|
}
|
|
|
|
/// Any of those must not be first dual jump. Everything else is OK.
|
|
bool HexagonGlobalSchedulerImpl::IsNotDualJumpFirstCandidate(MachineInstr *MI) {
|
|
if (MI->isCall() || (MI->isBranch() && !QII->isPredicated(*MI)) ||
|
|
MI->isReturn() || QII->isEndLoopN(MI->getOpcode()))
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
/// These four functions clearly belong in HexagonInstrInfo.cpp.
|
|
/// Is this MI could be first dual jump instruction?
|
|
bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(MachineInstr *MI) {
|
|
if (!PerformDualJumps)
|
|
return false;
|
|
if (MI->isBranch() && QII->isPredicated(*MI) && !QII->isNewValueJump(*MI) &&
|
|
!MI->isIndirectBranch() && !QII->isEndLoopN(MI->getOpcode()))
|
|
return true;
|
|
// Missing loopN here, but not sure if there will be any benefit from it.
|
|
return false;
|
|
}
|
|
|
|
/// This version covers the whole packet.
|
|
bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(
|
|
MachineBasicBlock::iterator &TargetPacket) {
|
|
if (!PerformDualJumps)
|
|
return false;
|
|
MachineInstr *MI = &*TargetPacket;
|
|
|
|
if (MI->isBundle()) {
|
|
// If this is a bundle, it must be the last bundle in BB.
|
|
if (&(*MI->getParent()->rbegin()) != MI)
|
|
return false;
|
|
|
|
MachineBasicBlock::instr_iterator MII = MI->getIterator();
|
|
MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
|
|
// If there is a control flow op in this packet, this is the case
|
|
// we look for, even if they are dependent on other members.
|
|
for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII)
|
|
if (IsNotDualJumpFirstCandidate(&*MII))
|
|
return false;
|
|
} else
|
|
return IsDualJumpFirstCandidate(MI);
|
|
|
|
return true;
|
|
}
|
|
|
|
/// This version cover whole BB. There could be a BB
|
|
/// with no control flow in it. In this case we can still pull-up a jump
|
|
/// into it. Negative proof.
|
|
bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(
|
|
MachineBasicBlock *MBB) {
|
|
if (!PerformDualJumps)
|
|
return false;
|
|
|
|
for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
|
|
MBBEnd = MBB->instr_end();
|
|
MII != MBBEnd; ++MII) {
|
|
MachineInstr *MI = &*MII;
|
|
if (MI->isDebugInstr())
|
|
continue;
|
|
if (!MI->isBundle() && IsNotDualJumpFirstCandidate(MI))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Is this MI could be second dual jump instruction?
|
|
bool HexagonGlobalSchedulerImpl::IsDualJumpSecondCandidate(MachineInstr *MI) {
|
|
if (!PerformDualJumps)
|
|
return false;
|
|
if ((MI->isBranch() && !QII->isNewValueJump(*MI) && !MI->isIndirectBranch() &&
|
|
!QII->isEndLoopN(MI->getOpcode())) ||
|
|
(MI->isCall() && !IsIndirectCall(MI)))
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
// Since we have no exact knowledge of code layout,
|
|
// allow some safety buffer for jump target.
|
|
// This is measured in bytes.
|
|
static const unsigned SafetyBuffer = 200;
|
|
|
|
static MachineBasicBlock::instr_iterator
|
|
getHexagonFirstInstrTerminator(MachineBasicBlock *MBB) {
|
|
MachineBasicBlock::instr_iterator MIB = MBB->instr_begin();
|
|
MachineBasicBlock::instr_iterator MIE = MBB->instr_end();
|
|
MachineBasicBlock::instr_iterator MII = MIB;
|
|
while (MII != MIE) {
|
|
if (!MII->isBundle() && MII->isTerminator())
|
|
return MII;
|
|
++MII;
|
|
}
|
|
return MIE;
|
|
}
|
|
|
|
/// Check if a given instruction is:
|
|
/// - a jump to a distant target
|
|
/// - that exceeds its immediate range
|
|
/// If both conditions are true, it requires constant extension.
|
|
bool HexagonGlobalSchedulerImpl::isJumpOutOfRange(MachineInstr *MI) {
|
|
if (!MI || !MI->isBranch())
|
|
return false;
|
|
MachineBasicBlock *MBB = MI->getParent();
|
|
auto FirstTerm = getHexagonFirstInstrTerminator(MBB);
|
|
if (FirstTerm == MBB->instr_end())
|
|
return false;
|
|
|
|
unsigned InstOffset = BlockToInstOffset[MBB];
|
|
unsigned Distance = 0;
|
|
MachineBasicBlock::instr_iterator FTMII = FirstTerm;
|
|
|
|
// To save time, estimate exact position of a branch instruction
|
|
// as one at the end of the MBB.
|
|
// Number of instructions times typical instruction size.
|
|
InstOffset += (QII->nonDbgBBSize(MBB) * HEXAGON_INSTR_SIZE);
|
|
|
|
MachineBasicBlock *TBB = NULL, *FBB = NULL;
|
|
SmallVector<MachineOperand, 4> Cond;
|
|
|
|
// Try to analyze this branch.
|
|
if (QII->analyzeBranch(*MBB, TBB, FBB, Cond, false)) {
|
|
// Could not analyze it. See if this is something we can recognize.
|
|
// If it is a NVJ, it should always have its target in
|
|
// a fixed location.
|
|
if (QII->isNewValueJump(*FirstTerm))
|
|
TBB = FirstTerm->getOperand(QII->getCExtOpNum(*FirstTerm)).getMBB();
|
|
}
|
|
if (TBB && (MI == &*FirstTerm)) {
|
|
Distance =
|
|
(unsigned)std::abs((long long)InstOffset - BlockToInstOffset[TBB]) +
|
|
SafetyBuffer;
|
|
LLVM_DEBUG(dbgs() << "\tFirst term offset(" << Distance << "): ";
|
|
FirstTerm->dump());
|
|
return !QII->isJumpWithinBranchRange(*FirstTerm, Distance);
|
|
}
|
|
if (FBB) {
|
|
// Look for second terminator.
|
|
FTMII++;
|
|
MachineInstr *SecondTerm = &*FTMII;
|
|
assert(FTMII != MBB->instr_end() &&
|
|
(SecondTerm->isBranch() || SecondTerm->isCall()) &&
|
|
"Bad second terminator");
|
|
if (MI != SecondTerm)
|
|
return false;
|
|
// Analyze the second branch in the BB.
|
|
Distance =
|
|
(unsigned)std::abs((long long)InstOffset - BlockToInstOffset[FBB]) +
|
|
SafetyBuffer;
|
|
LLVM_DEBUG(dbgs() << "\tSecond term offset(" << Distance << "): ";
|
|
FirstTerm->dump());
|
|
return !QII->isJumpWithinBranchRange(*SecondTerm, Distance);
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/// Returns true if an instruction can be promoted to .new predicate
|
|
/// or new-value store.
|
|
/// Performs implicit version checking.
|
|
bool HexagonGlobalSchedulerImpl::isNewifiable(
|
|
MachineBasicBlock::instr_iterator MII, unsigned DepReg,
|
|
MachineInstr *TargetPacket) {
|
|
MachineInstr *MI = &*MII;
|
|
if (QII->isDotNewInst(*MI) ||
|
|
!CanNewifiedBeUsedInBundle(MII, DepReg, TargetPacket))
|
|
return false;
|
|
return (QII->isPredicated(*MI) && QII->getDotNewPredOp(*MI, nullptr) > 0) ||
|
|
QII->mayBeNewStore(*MI);
|
|
}
|
|
|
|
bool HexagonGlobalSchedulerImpl::DemoteToDotOld(MachineInstr *MI) {
|
|
int NewOpcode = QII->getDotOldOp(*MI);
|
|
MI->setDesc(QII->get(NewOpcode));
|
|
return true;
|
|
}
|
|
|
|
// initPacketizerState - Initialize packetizer flags
|
|
void HexagonGlobalSchedulerImpl::initPacketizerState(void) {
|
|
CurrentPacketMIs.clear();
|
|
return;
|
|
}
|
|
|
|
// ignorePseudoInstruction - Ignore bundling of pseudo instructions.
|
|
bool HexagonGlobalSchedulerImpl::ignoreInstruction(MachineInstr *MI) {
|
|
if (MI->isDebugInstr())
|
|
return true;
|
|
|
|
// We must print out inline assembly
|
|
if (MI->isInlineAsm())
|
|
return false;
|
|
|
|
// We check if MI has any functional units mapped to it.
|
|
// If it doesn't, we ignore the instruction.
|
|
const MCInstrDesc &TID = MI->getDesc();
|
|
unsigned SchedClass = TID.getSchedClass();
|
|
const InstrStage *IS =
|
|
ResourceTracker->getInstrItins()->beginStage(SchedClass);
|
|
unsigned FuncUnits = IS->getUnits();
|
|
return !FuncUnits;
|
|
}
|
|
|
|
// isSoloInstruction: - Returns true for instructions that must be
|
|
// scheduled in their own packet.
|
|
bool HexagonGlobalSchedulerImpl::isSoloInstruction(const MachineInstr &MI) {
|
|
if (MI.isInlineAsm())
|
|
return true;
|
|
|
|
if (MI.isEHLabel())
|
|
return true;
|
|
|
|
// From Hexagon V4 Programmer's Reference Manual 3.4.4 Grouping constraints:
|
|
// trap, pause, barrier, icinva, isync, and syncht are solo instructions.
|
|
// They must not be grouped with other instructions in a packet.
|
|
if (IsSchedBarrier(&MI))
|
|
return true;
|
|
|
|
if (MI.getOpcode() == Hexagon::A2_nop)
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
|
|
/// Return region ptr or null if non found.
|
|
BasicBlockRegion *HexagonGlobalSchedulerImpl::getRegionForMBB(
|
|
std::vector<BasicBlockRegion *> &Regions, MachineBasicBlock *MBB) {
|
|
for (std::vector<BasicBlockRegion *>::iterator I = Regions.begin(),
|
|
E = Regions.end();
|
|
I != E; ++I) {
|
|
if ((*I)->findMBB(MBB))
|
|
return *I;
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
/// Select best candidate to form regions.
|
|
static inline bool selectBestBB(BlockFrequency &BBaFreq, unsigned BBaSize,
|
|
BlockFrequency &BBbFreq, unsigned BBbSize) {
|
|
if (BBaFreq.getFrequency() > BBbFreq.getFrequency())
|
|
return true;
|
|
// TODO: This needs fine tuning.
|
|
// if (BBaSize < BBbSize)
|
|
// return true;
|
|
if (BBaFreq.getFrequency() == BBbFreq.getFrequency())
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
/// Returns BB pointer if one of MBB successors should be added to the
|
|
/// current PullUp Region, NULL otherwise.
|
|
/// If SecondBest is defined, get next one after Best match.
|
|
/// Most of the time, since we practically always have only two successors,
|
|
/// this is "the other" BB successor which still matches original
|
|
/// selection criterion.
|
|
MachineBasicBlock *
|
|
HexagonGlobalSchedulerImpl::getNextPURBB(MachineBasicBlock *MBB,
|
|
bool SecondBest = false) {
|
|
if (!MBB)
|
|
return NULL;
|
|
|
|
BlockFrequency BestBlockFreq = BlockFrequency(0);
|
|
unsigned BestBlockSize = 0;
|
|
MachineBasicBlock *BestBB = NULL;
|
|
MachineBasicBlock *SecondBestBB = NULL;
|
|
|
|
// Catch single BB loops.
|
|
for (MachineBasicBlock *Succ : MBB->successors())
|
|
if (Succ == MBB)
|
|
return NULL;
|
|
|
|
// Iterate through successors to MBB.
|
|
for (MachineBasicBlock *Succ : MBB->successors()) {
|
|
BlockFrequency BlockFreq = MBFI->getBlockFreq(Succ);
|
|
|
|
LLVM_DEBUG(dbgs() << "\tsucc BB(" << Succ->getNumber() << ") freq("
|
|
<< BlockFreq.getFrequency() << ")");
|
|
|
|
if (!SecondBest && getRegionForMBB(PullUpRegions, Succ))
|
|
continue;
|
|
|
|
// If there is more then one predecessor to this block, do not include it.
|
|
// It means there is a side entrance to it.
|
|
if (Succ->pred_size() > 1)
|
|
continue;
|
|
|
|
// If this block is a target of an indirect branch, it should
|
|
// also not be included.
|
|
if (Succ->isEHPad() || Succ->hasAddressTaken())
|
|
continue;
|
|
|
|
// Get BB edge frequency.
|
|
BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(MBB, Succ);
|
|
LLVM_DEBUG(dbgs() << "\tedge with freq(" << EdgeFreq.getFrequency()
|
|
<< ")\n");
|
|
|
|
if (selectBestBB(EdgeFreq, QII->nonDbgBBSize(Succ), BestBlockFreq,
|
|
BestBlockSize)) {
|
|
BestBlockFreq = EdgeFreq;
|
|
BestBlockSize = QII->nonDbgBBSize(Succ);
|
|
SecondBestBB = BestBB;
|
|
BestBB = Succ;
|
|
} else if (!SecondBestBB) {
|
|
SecondBestBB = Succ;
|
|
}
|
|
}
|
|
if (SecondBest)
|
|
return SecondBestBB;
|
|
else
|
|
return BestBB;
|
|
}
|
|
|
|
/// Form region to perform pull-up.
|
|
bool HexagonGlobalSchedulerImpl::formPullUpRegions(MachineFunction &Fn) {
|
|
const Function &F = Fn.getFunction();
|
|
// Check for single-block functions and skip them.
|
|
if (std::next(F.begin()) == F.end())
|
|
return false;
|
|
|
|
// Compute map for BB distances.
|
|
// Offset of the current instruction from the start.
|
|
unsigned InstOffset = 0;
|
|
|
|
LLVM_DEBUG(dbgs() << "****** Form PullUpRegions **************\n");
|
|
// Loop over all basic blocks.
|
|
// PullUp regions are basically traces with no side entrances.
|
|
for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
|
|
++MBB) {
|
|
if (MBB->getAlignment() > llvm::Align(1)) {
|
|
// Although we don't know the exact layout of the final code, we need
|
|
// to account for alignment padding somehow. This heuristic pads each
|
|
// aligned basic block according to the alignment value.
|
|
int ByteAlign = MBB->getAlignment().value() - 1;
|
|
InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
|
|
}
|
|
// Remember BB layout offset.
|
|
BlockToInstOffset[&*MBB] = InstOffset;
|
|
for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
|
|
MIE = MBB->instr_end();
|
|
MII != MIE; ++MII)
|
|
if (!MII->isBundle())
|
|
InstOffset += QII->getSize(*MII);
|
|
|
|
// If this BB is already in a region, move on.
|
|
if (getRegionForMBB(PullUpRegions, &*MBB))
|
|
continue;
|
|
|
|
LLVM_DEBUG(dbgs() << "\nRoot BB(" << MBB->getNumber() << ") name("
|
|
<< MBB->getName() << ") size(" << QII->nonDbgBBSize(&*MBB)
|
|
<< ") freq(" << printBlockFreq(*MBFI, *MBB)
|
|
<< ") pred_size(" << MBB->pred_size() << ") in_func("
|
|
<< MBB->getParent()->getFunction().getName() << ")\n");
|
|
|
|
BasicBlockRegion *PUR = new BasicBlockRegion(TII, QRI, &*MBB);
|
|
PullUpRegions.push_back(PUR);
|
|
|
|
for (MachineBasicBlock *MBBR = getNextPURBB(&*MBB); MBBR;
|
|
MBBR = getNextPURBB(MBBR)) {
|
|
LLVM_DEBUG(dbgs() << "Add BB(" << MBBR->getNumber() << ") name("
|
|
<< MBBR->getName() << ") size("
|
|
<< QII->nonDbgBBSize(MBBR) << ") freq("
|
|
<< printBlockFreq(*MBFI, *MBBR) << ") in_func("
|
|
<< MBBR->getParent()->getFunction().getName() << ")\n");
|
|
PUR->addBBtoRegion(MBBR);
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Return true if MI is an instruction we are unable to reason about
|
|
/// (like something with unmodeled memory side effects).
|
|
static inline bool isGlobalMemoryObject(MachineInstr *MI) {
|
|
if (MI->hasUnmodeledSideEffects() || MI->hasOrderedMemoryRef() ||
|
|
MI->isCall() ||
|
|
(MI->getOpcode() == Hexagon::J2_jump && !MI->getOperand(0).isMBB()))
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
// This MI might have either incomplete info, or known to be unsafe
|
|
// to deal with (i.e. volatile object).
|
|
static inline bool isUnsafeMemoryObject(MachineInstr *MI) {
|
|
if (!MI || MI->memoperands_empty())
|
|
return true;
|
|
|
|
// We purposefully do no check for hasOneMemOperand() here
|
|
// in hope to trigger an assert downstream in order to
|
|
// finish implementation.
|
|
if ((*MI->memoperands_begin())->isVolatile() || MI->hasUnmodeledSideEffects())
|
|
return true;
|
|
|
|
if (!(*MI->memoperands_begin())->getValue())
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
|
|
/// This returns true if the two MIs could be memory dependent.
|
|
static bool MIsNeedChainEdge(AliasAnalysis *AA, const TargetInstrInfo *TII,
|
|
MachineInstr *MIa, MachineInstr *MIb) {
|
|
// Cover a trivial case - no edge is need to itself.
|
|
if (MIa == MIb)
|
|
return false;
|
|
|
|
if (TII->areMemAccessesTriviallyDisjoint(*MIa, *MIb))
|
|
return false;
|
|
|
|
if (isUnsafeMemoryObject(MIa) || isUnsafeMemoryObject(MIb))
|
|
return true;
|
|
|
|
// If we are dealing with two "normal" loads, we do not need an edge
|
|
// between them - they could be reordered.
|
|
if (!MIa->mayStore() && !MIb->mayStore())
|
|
return false;
|
|
|
|
// To this point analysis is generic. From here on we do need AA.
|
|
if (!AA)
|
|
return true;
|
|
|
|
MachineMemOperand *MMOa = *MIa->memoperands_begin();
|
|
MachineMemOperand *MMOb = *MIb->memoperands_begin();
|
|
|
|
// TODO: Need to handle multiple memory operands.
|
|
// if either instruction has more than one memory operand, punt.
|
|
if (!(MIa->hasOneMemOperand() && MIb->hasOneMemOperand()))
|
|
return true;
|
|
|
|
if (!MMOa->getSize().hasValue() || !MMOb->getSize().hasValue())
|
|
return true;
|
|
|
|
assert((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset");
|
|
assert((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset");
|
|
assert((MMOa->getSize().hasValue() && MMOb->getSize().hasValue()) &&
|
|
"Size 0 memory access");
|
|
|
|
// If the base address of the two memoperands is the same. For instance,
|
|
// x and x+4, then we can easily reason about them using the offset and size
|
|
// of access.
|
|
if (MMOa->getValue() == MMOb->getValue()) {
|
|
if (MMOa->getOffset() > MMOb->getOffset()) {
|
|
uint64_t offDiff = MMOa->getOffset() - MMOb->getOffset();
|
|
return !(MMOb->getSize().getValue() <= offDiff);
|
|
} else if (MMOa->getOffset() < MMOb->getOffset()) {
|
|
uint64_t offDiff = MMOb->getOffset() - MMOa->getOffset();
|
|
return !(MMOa->getSize().getValue() <= offDiff);
|
|
}
|
|
// MMOa->getOffset() == MMOb->getOffset()
|
|
return true;
|
|
}
|
|
|
|
int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset());
|
|
int64_t Overlapa = MMOa->getSize().getValue() + MMOa->getOffset() - MinOffset;
|
|
int64_t Overlapb = MMOb->getSize().getValue() + MMOb->getOffset() - MinOffset;
|
|
|
|
AliasResult AAResult =
|
|
AA->alias(MemoryLocation(MMOa->getValue(), Overlapa, MMOa->getAAInfo()),
|
|
MemoryLocation(MMOb->getValue(), Overlapb, MMOb->getAAInfo()));
|
|
|
|
return (AAResult != AliasResult::NoAlias);
|
|
}
|
|
|
|
/// Gather register def/uses from MI.
|
|
/// This treats possible (predicated) defs
|
|
/// as actually happening ones (conservatively).
|
|
static inline void parseOperands(MachineInstr *MI,
|
|
SmallVector<unsigned, 4> &Defs,
|
|
SmallVector<unsigned, 8> &Uses) {
|
|
Defs.clear();
|
|
Uses.clear();
|
|
|
|
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
|
const MachineOperand &MO = MI->getOperand(i);
|
|
|
|
if (MO.isReg()) {
|
|
unsigned Reg = MO.getReg();
|
|
if (!Reg)
|
|
continue;
|
|
assert(Register::isPhysicalRegister(Reg));
|
|
if (MO.isUse())
|
|
Uses.push_back(MO.getReg());
|
|
if (MO.isDef())
|
|
Defs.push_back(MO.getReg());
|
|
} else if (MO.isRegMask()) {
|
|
for (unsigned R = 1, NR = Hexagon::NUM_TARGET_REGS; R != NR; ++R)
|
|
if (MO.clobbersPhysReg(R))
|
|
Defs.push_back(R);
|
|
}
|
|
}
|
|
}
|
|
|
|
void HexagonGlobalSchedulerImpl::MIUseDefSet(MachineInstr *MI,
|
|
std::vector<unsigned> &Defs,
|
|
std::vector<unsigned> &Uses) {
|
|
Defs.clear();
|
|
Uses.clear();
|
|
assert(!MI->isBundle() && "Cannot parse regs of a bundle.");
|
|
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
|
const MachineOperand &MO = MI->getOperand(i);
|
|
|
|
if (MO.isReg()) {
|
|
unsigned Reg = MO.getReg();
|
|
if (!Reg)
|
|
continue;
|
|
assert(Register::isPhysicalRegister(Reg));
|
|
std::vector<unsigned> &Refs = MO.isUse() ? Uses : Defs;
|
|
for (MCRegAliasIterator AI(MO.getReg(), QRI, true); AI.isValid(); ++AI)
|
|
Refs.push_back(*AI);
|
|
} else if (MO.isRegMask()) {
|
|
for (unsigned R = 1, NR = Hexagon::NUM_TARGET_REGS; R != NR; ++R)
|
|
if (MO.clobbersPhysReg(R))
|
|
Defs.push_back(R);
|
|
}
|
|
}
|
|
}
|
|
|
|
/// Some apparent dependencies are not actually restricting us since there
|
|
/// is a delay between assignment and actual usage, like in case of a call.
|
|
/// There could be more cases here, but this one seems the most obvious.
|
|
static bool isDelayedUseException(MachineInstr *MIa, MachineInstr *MIb) {
|
|
if (MIa->isCall() && !MIb->isCall())
|
|
return true;
|
|
if (!MIa->isCall() && MIb->isCall())
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
/// This is a check for resources availability and dependency
|
|
/// for an MI being tried for an existing bundle.
|
|
/// This is needed because we can:
|
|
/// - save time by filtering out trivial cases
|
|
/// - we want to reuse infrastructure that does not really knows
|
|
/// how to deal with parallel semantics of a bundle that already
|
|
/// exists. For instance, the following case:
|
|
/// SI %R6<def> = L2_ploadrif_io %P0<kill>, %R7, 4;
|
|
/// SJ %R6<def> = A2_tfr %R0;
|
|
/// will be happily allowed by isLegalToPacketizeTogether since in serial
|
|
/// semantics it never happens, and even if it does, it is legal. Not so
|
|
/// for when we __speculatively__ trying and MI for a bundle.
|
|
///
|
|
/// Note: This is not equivalent to MIsAreDependent().
|
|
/// MIsAreDependent only understands serial semantics.
|
|
/// These are OK to packetize together:
|
|
/// %R0<def> = L2_loadri_io %R18, 76; mem:LD4[%sunkaddr226](tbaa=!"int")
|
|
/// %R2<def> = ASL %R0<kill>, 3; flags: Inside bundle
|
|
///
|
|
bool HexagonGlobalSchedulerImpl::canAddMIToThisPacket(
|
|
MachineInstr *MI,
|
|
SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> &Bundle) {
|
|
if (!MI)
|
|
return false;
|
|
LLVM_DEBUG(dbgs() << "\n\t[canAddMIToThisPacket]: "; MI->dump());
|
|
|
|
// Const extenders need custom resource checking...
|
|
// Should be OK if we can update the check everywhere.
|
|
if ((QII->isConstExtended(*MI) || QII->isExtended(*MI) ||
|
|
isJumpOutOfRange(MI)) &&
|
|
!tryAllocateResourcesForConstExt(MI, false))
|
|
return false;
|
|
|
|
// Ask DFA if machine resource is available for MI.
|
|
if (!ResourceTracker->canReserveResources(*MI) || !shouldAddToPacket(*MI)) {
|
|
LLVM_DEBUG(dbgs() << "\tNo DFA resources.\n");
|
|
return false;
|
|
}
|
|
|
|
SmallVector<unsigned, 4> BundleDefs;
|
|
SmallVector<unsigned, 8> BundleUses;
|
|
SmallVector<unsigned, 4> Defs;
|
|
SmallVector<unsigned, 8> Uses;
|
|
MachineInstr *FirstCompound = NULL, *SecondCompound = NULL;
|
|
MachineInstr *FirstDuplex = NULL, *SecondDuplex = NULL;
|
|
|
|
parseOperands(MI, Defs, Uses);
|
|
for (SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE>::iterator
|
|
BI = Bundle.begin(),
|
|
BE = Bundle.end();
|
|
BI != BE; ++BI) {
|
|
BundleDefs.clear();
|
|
BundleUses.clear();
|
|
parseOperands(*BI, BundleDefs, BundleUses);
|
|
|
|
MachineInstr *Inst1 = *BI;
|
|
MachineInstr *Inst2 = MI;
|
|
|
|
if (Inst1->getParent() && OneFloatPerPacket && QII->isFloat(*Inst1) &&
|
|
QII->isFloat(*Inst2))
|
|
return false;
|
|
|
|
if (Inst1->getParent() && OneComplexPerPacket && QII->isComplex(*Inst1) &&
|
|
QII->isComplex(*Inst2))
|
|
return false;
|
|
|
|
if (PreventCompoundSeparation)
|
|
if (QII->getCompoundCandidateGroup(**BI)) {
|
|
if (!FirstCompound)
|
|
FirstCompound = *BI;
|
|
else {
|
|
SecondCompound = *BI;
|
|
if (isCompoundPair(FirstCompound, SecondCompound)) {
|
|
if (MI->mayLoad() || MI->mayStore()) {
|
|
LLVM_DEBUG(dbgs() << "\tPrevent compound destruction.\n");
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
if (PreventDuplexSeparation)
|
|
if (QII->getDuplexCandidateGroup(**BI)) {
|
|
if (!FirstDuplex)
|
|
FirstDuplex = *BI;
|
|
else {
|
|
SecondDuplex = *BI;
|
|
if (QII->isDuplexPair(*FirstDuplex, *SecondDuplex)) {
|
|
if (MI->mayLoad() || MI->mayStore()) {
|
|
LLVM_DEBUG(dbgs() << "\tPrevent duplex destruction.\n");
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
for (unsigned i = 0; i < Defs.size(); i++) {
|
|
// Check for multiple definitions in the same packet.
|
|
for (unsigned j = 0; j < BundleDefs.size(); j++)
|
|
// Multiple defs in the same packet.
|
|
// Calls are OK here.
|
|
// Also if we have multiple defs of PC, this simply means we are
|
|
// dealing with dual jumps.
|
|
if (AliasingRegs(Defs[i], BundleDefs[j]) &&
|
|
!isDelayedUseException(MI, *BI) &&
|
|
!(IsDualJumpFirstCandidate(*BI) && IsDualJumpSecondCandidate(MI))) {
|
|
LLVM_DEBUG(dbgs() << "\tMultiple defs.\n\t"; MI->dump();
|
|
dbgs() << "\t"; (*BI)->dump());
|
|
return false;
|
|
}
|
|
|
|
// See if we are creating a swap case as we go, and disallow
|
|
// it for now.
|
|
// Also, this is not OK:
|
|
// if (!p0) r7 = r5
|
|
// if (!p0) r5 = #0
|
|
// But this is fine:
|
|
// if (!p0) r7 = r5
|
|
// if (p0) r5 = #0
|
|
// Aslo - this is not a swap, but an opportunity to newify:
|
|
// %P1<def> = C2_cmpeqi %R0, 0; flags:
|
|
// %R0<def> = L2_ploadrif_io %P1<kill>, %R29, 8;
|
|
// TODO: Handle this.
|
|
for (unsigned j = 0; j < BundleUses.size(); j++)
|
|
if (AliasingRegs(Defs[i], BundleUses[j])) {
|
|
for (unsigned k = 0; k < BundleDefs.size(); k++)
|
|
for (unsigned l = 0; l < Uses.size(); l++) {
|
|
if (AliasingRegs(BundleDefs[k], Uses[l]) &&
|
|
!isDelayedUseException(MI, *BI)) {
|
|
LLVM_DEBUG(dbgs() << "\tSwap detected:\n\t"; MI->dump();
|
|
dbgs() << "\t"; (*BI)->dump());
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
for (unsigned i = 0; i < Uses.size(); i++) {
|
|
// Check for true data dependency.
|
|
for (unsigned j = 0; j < BundleDefs.size(); j++)
|
|
if (AliasingRegs(Uses[i], BundleDefs[j]) &&
|
|
!isDelayedUseException(MI, *BI)) {
|
|
LLVM_DEBUG(dbgs() << "\tImmediate Use detected on reg("
|
|
<< printReg(Uses[i], QRI) << ")\n\t";
|
|
MI->dump(); dbgs() << "\t"; (*BI)->dump());
|
|
// TODO: This could be an opportunity for newifying:
|
|
// %P0<def> = C2_cmpeqi %R26, 0
|
|
// %R26<def> = A2_tfr %R0<kill>
|
|
// if (CanPromoteToDotNew(MI, Uses[i]))
|
|
// LLVM_DEBUG(dbgs() << "\tCan promoto to .new form.\n");
|
|
// else
|
|
return false;
|
|
}
|
|
}
|
|
|
|
// For calls we also check callee save regs.
|
|
if ((*BI)->isCall()) {
|
|
for (const uint16_t *I = QRI->getCalleeSavedRegs(&MF); *I; ++I) {
|
|
for (unsigned i = 0; i < Defs.size(); i++) {
|
|
if (AliasingRegs(Defs[i], *I)) {
|
|
LLVM_DEBUG(dbgs() << "\tAlias with call.\n");
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// If this is return, we are probably speculating (otherwise
|
|
// we could not pull in there) and will not win from pulling
|
|
// into this location anyhow.
|
|
// Example: a side exit.
|
|
// if (!p0) dealloc_return
|
|
// TODO: Can check that we do not overwrite return value
|
|
// and proceed.
|
|
if ((*BI)->isBarrier()) {
|
|
LLVM_DEBUG(dbgs() << "\tBarrier interference.\n");
|
|
return false;
|
|
}
|
|
|
|
// \ref-manual (7.3.4) A loop setup packet in loopN or spNloop0 cannot
|
|
// contain a speculative indirect jump,
|
|
// a new-value compare jump or a dealloc_return.
|
|
// Speculative indirect jumps (predicate + .new + indirect):
|
|
// if ([!]Ps.new) jumpr:t Rs
|
|
// if ([!]Ps.new) jumpr:nt Rs
|
|
// @note: We don't want to pull across a call to be on the safe side.
|
|
if (QII->isLoopN(*MI) &&
|
|
((QII->isPredicated(**BI) && QII->isPredicatedNew(**BI) &&
|
|
QII->isJumpR(**BI)) ||
|
|
QII->isNewValueJump(**BI) || QII->isDeallocRet(**BI) ||
|
|
(*BI)->isCall())) {
|
|
LLVM_DEBUG(dbgs() << "\tLoopN pull interference.\n");
|
|
return false;
|
|
}
|
|
|
|
// The opposite is also true.
|
|
if (QII->isLoopN(**BI) &&
|
|
((QII->isPredicated(*MI) && QII->isPredicatedNew(*MI) &&
|
|
QII->isJumpR(*MI)) ||
|
|
QII->isNewValueJump(*MI) || QII->isDeallocRet(*MI) || MI->isCall())) {
|
|
LLVM_DEBUG(dbgs() << "\tResident LoopN.\n");
|
|
return false;
|
|
}
|
|
|
|
// @todo \ref-manual 7.6.1
|
|
// Presence of NVJ adds more restrictions.
|
|
if (QII->isNewValueJump(**BI) &&
|
|
(MI->mayStore() || MI->getOpcode() == Hexagon::S2_allocframe ||
|
|
MI->isCall())) {
|
|
LLVM_DEBUG(dbgs() << "\tNew val Jump.\n");
|
|
return false;
|
|
}
|
|
|
|
// For memory operations, check aliasing.
|
|
// First, be conservative on these objects. Might be overly constraining,
|
|
// so recheck.
|
|
if (isGlobalMemoryObject(*BI) || isGlobalMemoryObject(MI))
|
|
// Currently it catches things like this:
|
|
// S2_storerinew_io %R29, 32, %R16
|
|
// S2_storeri_io %R29, 68, %R0
|
|
// which we can reason about.
|
|
// TODO: revisit.
|
|
return false;
|
|
|
|
// If packet has a new-value store, MI can't be a store instruction.
|
|
if (QII->isNewValueStore(**BI) && MI->mayStore()) {
|
|
LLVM_DEBUG(dbgs() << "\tNew Value Store to store.\n");
|
|
return false;
|
|
}
|
|
|
|
if ((QII->isMemOp(**BI) && MI->mayStore()) ||
|
|
(QII->isMemOp(*MI) && (*BI)->mayStore())) {
|
|
LLVM_DEBUG(
|
|
dbgs() << "\tSlot 0 not available for store because of memop.\n");
|
|
return false;
|
|
}
|
|
|
|
// If any of these is true, check aliasing.
|
|
if ((MI->mayLoad() && (*BI)->mayStore()) ||
|
|
(MI->mayStore() && (*BI)->mayLoad()) ||
|
|
(MI->mayStore() && (*BI)->mayStore())) {
|
|
if (MIsNeedChainEdge(AA, TII, MI, *BI)) {
|
|
LLVM_DEBUG(dbgs() << "\tAliasing detected:\n\t"; MI->dump();
|
|
dbgs() << "\t"; (*BI)->dump());
|
|
return false;
|
|
}
|
|
}
|
|
// Do not move an instruction to this packet if this packet
|
|
// already contains a speculated instruction.
|
|
std::map<MachineInstr *, MachineBasicBlock *>::iterator MIMoved;
|
|
MIMoved = SpeculatedIns.find(*BI);
|
|
if ((MIMoved != SpeculatedIns.end()) &&
|
|
(MIMoved->second != (*BI)->getParent())) {
|
|
LLVM_DEBUG(
|
|
dbgs() << "This packet already contains a speculated instruction";
|
|
(*BI)->dump(););
|
|
return false;
|
|
}
|
|
}
|
|
|
|
// Do not pull-up vector instructions because these instructions have
|
|
// multi-cycle latencies, and the pull-up pass doesn't correctly account
|
|
// for instructions that stall for more than one cycle.
|
|
if (QII->isHVXVec(*MI))
|
|
return false;
|
|
|
|
return true;
|
|
}
|
|
|
|
/// Test is true if the two MIs cannot be safely reordered.
|
|
bool HexagonGlobalSchedulerImpl::ReorderDependencyTest(MachineInstr *MIa,
|
|
MachineInstr *MIb) {
|
|
SmallVector<unsigned, 4> DefsA;
|
|
SmallVector<unsigned, 4> DefsB;
|
|
SmallVector<unsigned, 8> UsesA;
|
|
SmallVector<unsigned, 8> UsesB;
|
|
|
|
parseOperands(MIa, DefsA, UsesA);
|
|
parseOperands(MIb, DefsB, UsesB);
|
|
|
|
for (SmallVector<unsigned, 4>::iterator IDA = DefsA.begin(),
|
|
IDAE = DefsA.end();
|
|
IDA != IDAE; ++IDA) {
|
|
for (SmallVector<unsigned, 8>::iterator IUB = UsesB.begin(),
|
|
IUBE = UsesB.end();
|
|
IUB != IUBE; ++IUB)
|
|
// True data dependency.
|
|
if (AliasingRegs(*IDA, *IUB))
|
|
return true;
|
|
|
|
for (SmallVector<unsigned, 4>::iterator IDB = DefsB.begin(),
|
|
IDBE = DefsB.end();
|
|
IDB != IDBE; ++IDB)
|
|
// Output dependency.
|
|
if (AliasingRegs(*IDA, *IDB))
|
|
return true;
|
|
}
|
|
|
|
for (SmallVector<unsigned, 4>::iterator IDB = DefsB.begin(),
|
|
IDBE = DefsB.end();
|
|
IDB != IDBE; ++IDB) {
|
|
for (SmallVector<unsigned, 8>::iterator IUA = UsesA.begin(),
|
|
IUAE = UsesA.end();
|
|
IUA != IUAE; ++IUA)
|
|
// True data dependency.
|
|
if (AliasingRegs(*IDB, *IUA))
|
|
return true;
|
|
}
|
|
|
|
// Do not reorder two calls...
|
|
if (MIa->isCall() && MIb->isCall())
|
|
return true;
|
|
|
|
// For calls we also check callee save regs.
|
|
if (MIa->isCall())
|
|
for (const uint16_t *I = QRI->getCalleeSavedRegs(&MF); *I; ++I) {
|
|
for (unsigned i = 0; i < DefsB.size(); i++) {
|
|
if (AliasingRegs(DefsB[i], *I))
|
|
return true;
|
|
}
|
|
}
|
|
|
|
if (MIb->isCall())
|
|
for (const uint16_t *I = QRI->getCalleeSavedRegs(&MF); *I; ++I) {
|
|
for (unsigned i = 0; i < DefsA.size(); i++) {
|
|
if (AliasingRegs(DefsA[i], *I))
|
|
return true;
|
|
}
|
|
}
|
|
|
|
// For memory operations, check aliasing.
|
|
// First, be conservative on these objects.
|
|
// Might be overly constraining, so recheck.
|
|
if ((isGlobalMemoryObject(MIa)) || (isGlobalMemoryObject(MIb)))
|
|
return true;
|
|
|
|
// If any of these is true, check aliasing.
|
|
if (((MIa->mayLoad() && MIb->mayStore()) ||
|
|
(MIa->mayStore() && MIb->mayLoad()) ||
|
|
(MIa->mayStore() && MIb->mayStore())) &&
|
|
MIsNeedChainEdge(AA, TII, MIa, MIb))
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
|
|
/// Serial semantics.
|
|
bool HexagonGlobalSchedulerImpl::MIsAreDependent(MachineInstr *MIa,
|
|
MachineInstr *MIb) {
|
|
if (MIa == MIb)
|
|
return false;
|
|
|
|
if (ReorderDependencyTest(MIa, MIb)) {
|
|
LLVM_DEBUG(dbgs() << "\t\t[MIsAreDependent]:\n\t\t"; MIa->dump();
|
|
dbgs() << "\t\t"; MIb->dump());
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/// Serial semantics.
|
|
bool HexagonGlobalSchedulerImpl::MIsHaveTrueDependency(MachineInstr *MIa,
|
|
MachineInstr *MIb) {
|
|
if (MIa == MIb)
|
|
return false;
|
|
|
|
SmallVector<unsigned, 4> DefsA;
|
|
SmallVector<unsigned, 4> DefsB;
|
|
SmallVector<unsigned, 8> UsesA;
|
|
SmallVector<unsigned, 8> UsesB;
|
|
|
|
parseOperands(MIa, DefsA, UsesA);
|
|
parseOperands(MIb, DefsB, UsesB);
|
|
|
|
for (SmallVector<unsigned, 4>::iterator IDA = DefsA.begin(),
|
|
IDAE = DefsA.end();
|
|
IDA != IDAE; ++IDA) {
|
|
for (SmallVector<unsigned, 8>::iterator IUB = UsesB.begin(),
|
|
IUBE = UsesB.end();
|
|
IUB != IUBE; ++IUB)
|
|
// True data dependency.
|
|
if (AliasingRegs(*IDA, *IUB))
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/// Sequential semantics. Can these two MIs be reordered?
|
|
/// Moving MIa from "behind" to "in front" of MIb.
|
|
bool HexagonGlobalSchedulerImpl::canReorderMIs(MachineInstr *MIa,
|
|
MachineInstr *MIb) {
|
|
if (!MIa || !MIb)
|
|
return false;
|
|
|
|
// Within bundle semantics are parallel.
|
|
if (MIa->isBundle()) {
|
|
MachineBasicBlock::instr_iterator MII = MIa->getIterator();
|
|
MachineBasicBlock::instr_iterator MIIE = MIa->getParent()->instr_end();
|
|
for (++MII; MII != MIIE && MII->isInsideBundle(); ++MII) {
|
|
if (MII->isDebugInstr())
|
|
continue;
|
|
if (MIsAreDependent(&*MII, MIb))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
return !MIsAreDependent(MIa, MIb);
|
|
}
|
|
|
|
static inline bool MIMustNotBePulledUp(MachineInstr *MI) {
|
|
if (MI->isInlineAsm() || MI->isEHLabel() || IsSchedBarrier(MI))
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
static inline bool MIShouldNotBePulledUp(MachineInstr *MI) {
|
|
if (MI->isBranch() || MI->isReturn() || MI->isCall() || MI->isBarrier() ||
|
|
MI->isTerminator() || MIMustNotBePulledUp(MI))
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
// Only approve dual jump candidate:
|
|
// It is a branch, and we move it to last packet of the target location.
|
|
bool HexagonGlobalSchedulerImpl::MIisDualJumpCandidate(
|
|
MachineInstr *MI, MachineBasicBlock::iterator &WorkPoint) {
|
|
if (!PerformDualJumps || !IsDualJumpSecondCandidate(MI) ||
|
|
MIMustNotBePulledUp(MI) || ignoreInstruction(MI))
|
|
return false;
|
|
|
|
MachineBasicBlock *FromThisBB = MI->getParent();
|
|
MachineBasicBlock *ToThisBB = WorkPoint->getParent();
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\t[MIisDualJumpCandidate] To BB("
|
|
<< ToThisBB->getNumber() << ") From BB("
|
|
<< FromThisBB->getNumber() << ")\n");
|
|
// If the question is about the same BB, we do not want to get
|
|
// dual jump involved - it is a different case.
|
|
if (FromThisBB == ToThisBB)
|
|
return false;
|
|
|
|
// Dual jump could only be done on neigboring BBs.
|
|
// The FromThisBB must only have one predecessor - the basic
|
|
// block we are trying to merge.
|
|
if ((*(FromThisBB->pred_begin()) != ToThisBB) ||
|
|
(std::next(FromThisBB->pred_begin()) != FromThisBB->pred_end()))
|
|
return false;
|
|
|
|
// If this block is a target of an indirect branch, it should
|
|
// also not be included.
|
|
if (FromThisBB->isEHPad() || FromThisBB->hasAddressTaken())
|
|
return false;
|
|
|
|
// Now we must preserve original fall through paths. In fact we
|
|
// might be dealing with 3way branching.
|
|
MachineBasicBlock *ToTBB = NULL, *ToFBB = NULL;
|
|
|
|
if (ToThisBB->succ_size() == 2) {
|
|
// Check the branch from target block.
|
|
// If we have two successors, we must understand the branch.
|
|
SmallVector<MachineOperand, 4> ToCond;
|
|
if (!QII->analyzeBranch(*ToThisBB, ToTBB, ToFBB, ToCond, false)) {
|
|
// Have the branch. Check the topology.
|
|
LLVM_DEBUG(dbgs() << "\t\tToThisBB has two successors: TBB("
|
|
<< ToTBB->getNumber() << ") and FBB(";
|
|
if (ToFBB) dbgs() << ToFBB->getNumber() << ").\n";
|
|
else dbgs() << "None"
|
|
<< ").\n";);
|
|
if (ToTBB == FromThisBB) {
|
|
// If the from BB is not the fall through, we can only handle case
|
|
// when second branch is unconditional jump.
|
|
return false;
|
|
} else if (ToFBB == FromThisBB || !ToFBB) {
|
|
// If the fall through path of ToBB is our FromBB, we have more freedom
|
|
// of operation.
|
|
LLVM_DEBUG(dbgs() << "\t\tFall through jump target.\n");
|
|
}
|
|
} else {
|
|
LLVM_DEBUG(dbgs() << "\t\tUnable to analyze first branch.\n");
|
|
return false;
|
|
}
|
|
} else if (ToThisBB->succ_size() == 1) {
|
|
ToFBB = *ToThisBB->succ_begin();
|
|
assert(ToFBB == FromThisBB && "Bad CFG layout");
|
|
} else
|
|
return false;
|
|
|
|
// First unbundled control flow instruction in the BB.
|
|
if (!MI->isBundled() && MI == &*FromThisBB->getFirstNonDebugInstr())
|
|
return IsDualJumpFirstCandidate(WorkPoint);
|
|
|
|
return false;
|
|
}
|
|
|
|
// Check whether moving MI to MJ's packet would cause a stall from a previous
|
|
// packet.
|
|
bool HexagonGlobalSchedulerImpl::canCauseStall(MachineInstr *MI,
|
|
MachineInstr *MJ) {
|
|
SmallVector<unsigned, 4> DefsMJI;
|
|
SmallVector<unsigned, 8> UsesMJI;
|
|
SmallVector<unsigned, 4> DefsMI;
|
|
SmallVector<unsigned, 8> UsesMI;
|
|
parseOperands(MI, DefsMI, UsesMI);
|
|
|
|
for (auto Use : UsesMI) {
|
|
int UseIdx = MI->findRegisterUseOperandIdx(Use, /*TRI=*/nullptr);
|
|
if (UseIdx == -1)
|
|
continue;
|
|
bool ShouldBreak = false;
|
|
int BundleCount = 0;
|
|
for (MachineBasicBlock::instr_iterator
|
|
Begin = MJ->getParent()->instr_begin(),
|
|
MJI = MJ->getIterator();
|
|
MJI != Begin; --MJI) {
|
|
if (MJI->isBundle()) {
|
|
++BundleCount;
|
|
continue;
|
|
}
|
|
parseOperands(&*MJI, DefsMJI, UsesMJI);
|
|
for (auto Def : DefsMJI) {
|
|
if (Def == Use || AliasingRegs(Def, Use)) {
|
|
int DefIdx = MJI->findRegisterDefOperandIdx(Def, /*TRI=*/nullptr);
|
|
if (DefIdx >= 0) {
|
|
int Latency =
|
|
TSchedModel.computeOperandLatency(&*MJI, DefIdx, MI, UseIdx);
|
|
if (Latency > BundleCount)
|
|
// There will be a stall if MI is moved to MJ's packet.
|
|
return true;
|
|
// We found the def for the use and it does not cause a stall.
|
|
// Continue checking the next use for a potential stall.
|
|
ShouldBreak = true;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if (ShouldBreak)
|
|
break;
|
|
if (!MJI->isBundled() && !MJI->isDebugInstr())
|
|
++BundleCount;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/// Analyze this instruction. If this is an unbundled instruction, see
|
|
/// if it in theory could be packetized.
|
|
/// If it is already part of a packet, see if it has internal
|
|
/// dependencies to this packet.
|
|
bool HexagonGlobalSchedulerImpl::canThisMIBeMoved(
|
|
MachineInstr *MI, MachineBasicBlock::iterator &WorkPoint,
|
|
bool &MovingDependentOp, int &Cost) {
|
|
if (!MI)
|
|
return false;
|
|
// By default, it is a normal move.
|
|
MovingDependentOp = false;
|
|
Cost = 0;
|
|
// If MI is a 'formed' compound not potential compound, bail out.
|
|
if (QII->isCompoundBranchInstr(*MI))
|
|
return false;
|
|
// See if we can potentially break potential compound candidates,
|
|
// and do not do it.
|
|
if (PreventCompoundSeparation && MI->isBundled()) {
|
|
enum HexagonII::CompoundGroup MICG = QII->getCompoundCandidateGroup(*MI);
|
|
if (MICG != HexagonII::HCG_None) {
|
|
// Check internal dependencies in the bundle.
|
|
// First, find the bundle header.
|
|
MachineBasicBlock::instr_iterator MII = MI->getIterator();
|
|
for (--MII; MII->isBundled(); --MII)
|
|
if (MII->isBundle())
|
|
break;
|
|
|
|
MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
|
|
for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII) {
|
|
if (&(*MII) == MI)
|
|
continue;
|
|
if (isCompoundPair(&*MII, MI)) {
|
|
LLVM_DEBUG(dbgs() << "\tPrevent Compound separation.\n");
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
// Same thing for duplex candidates.
|
|
if (PreventDuplexSeparation && MI->isBundled()) {
|
|
if (QII->getDuplexCandidateGroup(*MI) != HexagonII::HSIG_None) {
|
|
// Check internal dependencies in the bundle.
|
|
// First, find the bundle header.
|
|
MachineBasicBlock::instr_iterator MII = MI->getIterator();
|
|
for (--MII; MII->isBundled(); --MII)
|
|
if (MII->isBundle())
|
|
break;
|
|
|
|
MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
|
|
for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII) {
|
|
if ((&(*MII) != MI) && QII->isDuplexPair(*MII, *MI)) {
|
|
LLVM_DEBUG(dbgs() << "\tPrevent Duplex separation.\n");
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// If we perform dual jump formation during the pull-up,
|
|
// then we want to consider several additional situations.
|
|
// a) Allow moving of dependent instruction from a packet
|
|
// b) Allow moving some control flow instructions if they meet
|
|
// dual jump criteria.
|
|
if (MIisDualJumpCandidate(MI, WorkPoint)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tDual jump candidate:\t"; MI->dump());
|
|
// Here we are breaking our general assumption about not moving dependent
|
|
// instructions. To save us two more expensive checks down the line,
|
|
// propagate the information directly.
|
|
MovingDependentOp = true;
|
|
return true;
|
|
}
|
|
|
|
// Any of these should not even be tried.
|
|
if (MIShouldNotBePulledUp(MI) || ignoreInstruction(MI))
|
|
return false;
|
|
// Pulling up these instructions could put them
|
|
// out of jump range/offset size.
|
|
if (QII->isLoopN(*MI)) {
|
|
unsigned dist_looplabel =
|
|
BlockToInstOffset.find(MI->getOperand(0).getMBB())->second;
|
|
unsigned dist_newloop0 =
|
|
BlockToInstOffset.find(WorkPoint->getParent())->second;
|
|
// Check if the jump in the last instruction is within range.
|
|
unsigned Distance =
|
|
(unsigned)std::abs((long long)dist_looplabel - dist_newloop0) +
|
|
QII->nonDbgBBSize(WorkPoint->getParent()) * 4 + SafetyBuffer;
|
|
const HexagonInstrInfo *HII = (const HexagonInstrInfo *)TII;
|
|
if (!HII->isJumpWithinBranchRange(*MI, Distance)) {
|
|
LLVM_DEBUG(dbgs() << "\nloopN cannot be moved since Distance: "
|
|
<< Distance << " outside branch range.";);
|
|
return false;
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\nloopN can be moved since Distance: " << Distance
|
|
<< " within branch range.";);
|
|
}
|
|
// If the def-set of an MI is one of the live-ins then MI should
|
|
// kill that reg and no instruction before MI should use it.
|
|
// For simplicity, allow only if MI is the first instruction in the MBB.
|
|
std::map<MachineInstr *, std::vector<unsigned>>::const_iterator DefIter =
|
|
MIDefSet.find(MI);
|
|
MachineBasicBlock *MBB = MI->getParent();
|
|
for (unsigned i = 0; DefIter != MIDefSet.end() && i < DefIter->second.size();
|
|
++i) {
|
|
if (MBB->isLiveIn(DefIter->second[i]) &&
|
|
&*MBB->getFirstNonDebugInstr() != MI)
|
|
return false;
|
|
}
|
|
// If it is part of a bundle, analyze it.
|
|
if (MI->isBundled()) {
|
|
// Cannot move bundle header itself. This function is about
|
|
// individual MI move.
|
|
if (MI->isBundle())
|
|
return false;
|
|
|
|
// Check internal dependencies in the bundle.
|
|
// First, find the bundle header.
|
|
MachineBasicBlock::instr_iterator MII = MI->getIterator();
|
|
for (--MII; MII->isBundled(); --MII)
|
|
if (MII->isBundle())
|
|
break;
|
|
|
|
MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
|
|
for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII) {
|
|
if (MII->isDebugInstr())
|
|
continue;
|
|
if (MIsAreDependent(&*MII, MI)) {
|
|
if (!AllowDependentPullUp) {
|
|
LLVM_DEBUG(dbgs() << "\t\tDependent.\n");
|
|
return false;
|
|
} else {
|
|
// There are a few cases that we can safely move a dependent
|
|
// instruction away from this packet.
|
|
// One example is an instruction setting a call operands.
|
|
if ((MII->isCall() && !IsIndirectCall(&*MII)) ||
|
|
IsDualJumpSecondCandidate(&*MII) || MI->isBranch()) {
|
|
LLVM_DEBUG(dbgs() << "\t\tDependent, but allow to move.\n");
|
|
MovingDependentOp = true;
|
|
Cost -= 10;
|
|
continue;
|
|
} else {
|
|
LLVM_DEBUG(dbgs() << "\t\tDependent, and do not allow for now.\n");
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Return true if MI defines a predicate and parse all defs.
|
|
bool HexagonGlobalSchedulerImpl::doesMIDefinesPredicate(
|
|
MachineInstr *MI, SmallVector<unsigned, 4> &Defs) {
|
|
bool defsPredicate = false;
|
|
Defs.clear();
|
|
|
|
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
|
const MachineOperand &MO = MI->getOperand(i);
|
|
|
|
// Regmasks are considered "implicit".
|
|
if (!MO.isReg())
|
|
continue;
|
|
unsigned Reg = MO.getReg();
|
|
|
|
if (!Reg || QRI->isFakeReg(Reg))
|
|
continue;
|
|
|
|
assert(Register::isPhysicalRegister(Reg));
|
|
|
|
if (MO.isDef() && !MO.isImplicit()) {
|
|
const TargetRegisterClass *RC = QRI->getMinimalPhysRegClass(Reg);
|
|
if (RC == &Hexagon::PredRegsRegClass) {
|
|
defsPredicate = true;
|
|
Defs.push_back(MO.getReg());
|
|
}
|
|
}
|
|
}
|
|
return defsPredicate;
|
|
}
|
|
|
|
/// We have just tentatively added a predicated MI to an existing packet.
|
|
/// Now we need to determine if it needs to be changed to .new form.
|
|
/// It only handles compare/predicate right now.
|
|
/// TODO - clean this logic up.
|
|
/// TODO - generalize to handle any .new
|
|
bool HexagonGlobalSchedulerImpl::NeedToNewify(
|
|
MachineBasicBlock::instr_iterator NewMI, unsigned *DepReg,
|
|
MachineInstr *TargetPacket = NULL) {
|
|
MachineBasicBlock::instr_iterator MII = NewMI;
|
|
SmallVector<unsigned, 4> DefsA;
|
|
SmallVector<unsigned, 4> DefsB;
|
|
SmallVector<unsigned, 8> UsesB;
|
|
|
|
// If this is not a normal bundle, we are probably
|
|
// trying to size two lonesome instructions together,
|
|
// and trying to say if one of them will need to be
|
|
// newified. In this is the case we have something like this:
|
|
// BB#5:
|
|
// %P0<def> = CMPGEri %R4, 2
|
|
// S2_pstorerif_io %P0<kill>, %R29, 16, %R21<kill>
|
|
// BUNDLE %R7<imp-def>, %R4<imp-def>, %R7<imp-use>
|
|
parseOperands(&*NewMI, DefsB, UsesB);
|
|
if (TargetPacket && !TargetPacket->isBundled()) {
|
|
if (doesMIDefinesPredicate(TargetPacket, DefsA)) {
|
|
for (SmallVector<unsigned, 4>::iterator IA = DefsA.begin(),
|
|
IAE = DefsA.end();
|
|
IA != IAE; ++IA)
|
|
for (SmallVector<unsigned, 8>::iterator IB = UsesB.begin(),
|
|
IBE = UsesB.end();
|
|
IB != IBE; ++IB)
|
|
if (*IA == *IB) {
|
|
*DepReg = *IA;
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// Find bundle header.
|
|
for (--MII; MII->isBundled(); --MII)
|
|
if (MII->isBundle())
|
|
break;
|
|
|
|
// Iterate down, if there is data dependent cmp found, need to .newify.
|
|
// Also, we can have the following:
|
|
// {
|
|
// p0 = r7
|
|
// if (!p0.new) jump:t .LBB4_18
|
|
// if (p0.new) r8 = zxth(r12)
|
|
// }
|
|
MachineBasicBlock::instr_iterator BBEnd = MII->getParent()->instr_end();
|
|
for (++MII; MII != BBEnd && MII->isBundled() && !MII->isBundle(); ++MII) {
|
|
if (MII == NewMI)
|
|
continue;
|
|
if (doesMIDefinesPredicate(&*MII, DefsA)) {
|
|
for (SmallVector<unsigned, 4>::iterator IA = DefsA.begin(),
|
|
IAE = DefsA.end();
|
|
IA != IAE; ++IA)
|
|
for (SmallVector<unsigned, 8>::iterator IB = UsesB.begin(),
|
|
IBE = UsesB.end();
|
|
IB != IBE; ++IB)
|
|
// We do not have multiple predicate regs defined in any instruction,
|
|
// if we ever will, this needs to be generalized.
|
|
if (*IA == *IB) {
|
|
*DepReg = *IA;
|
|
return true;
|
|
}
|
|
DefsA.clear();
|
|
}
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\nNo need to newify:"; NewMI->dump());
|
|
return false;
|
|
}
|
|
|
|
/// We know this instruction needs to be newified to be added to the packet,
|
|
/// but not all combinations are legal.
|
|
/// It is a complimentary check to NeedToNewify().
|
|
/// The packet actually contains the new instruction during the check.
|
|
bool HexagonGlobalSchedulerImpl::CanNewifiedBeUsedInBundle(
|
|
MachineBasicBlock::instr_iterator NewMI, unsigned DepReg,
|
|
MachineInstr *TargetPacket) {
|
|
MachineBasicBlock::instr_iterator MII = NewMI;
|
|
if (!TargetPacket || !TargetPacket->isBundled())
|
|
return true;
|
|
|
|
// Find the bundle header.
|
|
for (--MII; MII->isBundled(); --MII)
|
|
if (MII->isBundle())
|
|
break;
|
|
|
|
MachineBasicBlock::instr_iterator BBEnd = MII->getParent()->instr_end();
|
|
for (++MII; MII != BBEnd && MII->isBundled() && !MII->isBundle(); ++MII) {
|
|
// Effectively we look for the case of late predicates.
|
|
// No additional checks at the time.
|
|
if (MII == NewMI || !QII->isPredicateLate(MII->getOpcode()))
|
|
continue;
|
|
SmallVector<unsigned, 4> DefsA;
|
|
if (!doesMIDefinesPredicate(&*MII, DefsA))
|
|
continue;
|
|
for (auto &IA : DefsA)
|
|
if (IA == DepReg)
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// setUsed - Set the register and its sub-registers as being used.
|
|
/// Similar to RegScavenger::setUsed().
|
|
void HexagonGlobalSchedulerImpl::setUsedRegs(BitVector &Set, unsigned Reg) {
|
|
Set.reset(Reg);
|
|
for (MCSubRegIterator SubRegs(Reg, QRI); SubRegs.isValid(); ++SubRegs)
|
|
Set.reset(*SubRegs);
|
|
}
|
|
|
|
/// Are these two registers overlaping?
|
|
bool HexagonGlobalSchedulerImpl::AliasingRegs(unsigned RegA, unsigned RegB) {
|
|
if (RegA == RegB)
|
|
return true;
|
|
|
|
for (MCSubRegIterator SubRegs(RegA, QRI); SubRegs.isValid(); ++SubRegs)
|
|
if (RegB == *SubRegs)
|
|
return true;
|
|
|
|
for (MCSubRegIterator SubRegs(RegB, QRI); SubRegs.isValid(); ++SubRegs)
|
|
if (RegA == *SubRegs)
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
|
|
/// Find use with this reg, and unmark the kill flag.
|
|
static inline void unmarkKillReg(MachineInstr *MI, unsigned Reg) {
|
|
if (MI->isDebugInstr())
|
|
return;
|
|
|
|
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
|
MachineOperand &MO = MI->getOperand(i);
|
|
|
|
if (!MO.isReg())
|
|
continue;
|
|
|
|
if (MO.isKill() && (MO.getReg() == Reg))
|
|
MO.setIsKill(false);
|
|
}
|
|
}
|
|
|
|
/// Find use with this reg, and unmark the kill flag.
|
|
static inline void markKillReg(MachineInstr *MI, unsigned Reg) {
|
|
if (MI->isDebugInstr())
|
|
return;
|
|
|
|
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
|
MachineOperand &MO = MI->getOperand(i);
|
|
|
|
if (!MO.isReg())
|
|
continue;
|
|
|
|
if (MO.isUse() && (MO.getReg() == Reg))
|
|
MO.setIsKill(true);
|
|
}
|
|
}
|
|
|
|
/// We have just moved an instruction that could have changed kill patterns
|
|
/// along the path it was moved. We need to update it.
|
|
void HexagonGlobalSchedulerImpl::updateKillAlongThePath(
|
|
MachineBasicBlock *HomeBB, MachineBasicBlock *OriginBB,
|
|
MachineBasicBlock::instr_iterator &Head,
|
|
MachineBasicBlock::instr_iterator &Tail,
|
|
MachineBasicBlock::iterator &SourcePacket,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
std::vector<MachineInstr *> &backtrack) {
|
|
// This is the instruction being moved.
|
|
MachineInstr *MI = &*Head;
|
|
MachineBasicBlock *CurrentBB = OriginBB;
|
|
SmallSet<unsigned, 8> KilledUseSet;
|
|
|
|
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
|
const MachineOperand &MO = MI->getOperand(i);
|
|
if (!MO.isReg())
|
|
continue;
|
|
unsigned Reg = MO.getReg();
|
|
if (!Reg)
|
|
continue;
|
|
|
|
if (MO.isKill())
|
|
KilledUseSet.insert(Reg);
|
|
}
|
|
|
|
// If there are no kills here, we are done.
|
|
if (KilledUseSet.empty())
|
|
return;
|
|
|
|
LLVM_DEBUG(dbgs() << "\n[updateKillAlongThePath]\n");
|
|
LLVM_DEBUG(dbgs() << "\t\tInstrToMove :\t"; MI->dump());
|
|
LLVM_DEBUG(dbgs() << "\t\tSourceLocation:\n";
|
|
DumpPacket(SourcePacket.getInstrIterator()));
|
|
LLVM_DEBUG(dbgs() << "\t\tTargetPacket :\n";
|
|
DumpPacket(TargetPacket.getInstrIterator()));
|
|
LLVM_DEBUG(dbgs() << "\tUpdate Kills. Need to update (" << KilledUseSet.size()
|
|
<< ")kills. From BB (" << OriginBB->getNumber() << ")\n");
|
|
LLVM_DEBUG(dbgs() << "\tMove path:\n");
|
|
assert(!backtrack.empty() && "Empty back track");
|
|
|
|
// We have pulled up an instruction, with one of its uses marked as kill.
|
|
// If there is any other use of the same register along the move path,
|
|
// and there are no side exits with killed register live-in along them,
|
|
// we need to mark last use of that reg as kill.
|
|
for (signed i = backtrack.size() - 1; i >= 0; --i) {
|
|
LLVM_DEBUG(dbgs() << "\t\t[" << i << "]BB("
|
|
<< backtrack[i]->getParent()->getNumber() << ")\t";
|
|
backtrack[i]->dump());
|
|
if (CurrentBB != backtrack[i]->getParent()) {
|
|
LLVM_DEBUG(dbgs() << "\t\tChange BB from (" << CurrentBB->getNumber()
|
|
<< ") to(" << backtrack[i]->getParent()->getNumber()
|
|
<< ")\n");
|
|
for (MachineBasicBlock::const_succ_iterator
|
|
SI = backtrack[i]->getParent()->succ_begin(),
|
|
SE = backtrack[i]->getParent()->succ_end();
|
|
SI != SE; ++SI) {
|
|
if (*SI == CurrentBB)
|
|
continue;
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\tSide Exit:\n\t"; (*SI)->dump());
|
|
// If any reg kill is live along this side exit, it is not
|
|
// a kill any more.
|
|
for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
|
|
E = (*SI)->livein_end();
|
|
I != E; ++I) {
|
|
if (KilledUseSet.count((*I).PhysReg)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tReg (" << printReg((*I).PhysReg, QRI)
|
|
<< ") is LiveIn along side exit.\n");
|
|
KilledUseSet.erase((*I).PhysReg);
|
|
unmarkKillReg(MI, (*I).PhysReg);
|
|
}
|
|
if (KilledUseSet.empty())
|
|
return;
|
|
}
|
|
}
|
|
CurrentBB = backtrack[i]->getParent();
|
|
}
|
|
|
|
// Done with the whole path.
|
|
if (backtrack[i] == &*TargetPacket)
|
|
return;
|
|
|
|
// Starting the tracking. Do not update source bundle.
|
|
// If TargetPacket == SourcePacket we have returned
|
|
// in the previous check.
|
|
if (backtrack[i] == &*SourcePacket)
|
|
continue;
|
|
|
|
// Ignore DBG_VALUE.
|
|
if (backtrack[i]->isDebugInstr())
|
|
continue;
|
|
|
|
// Encountered an intermediary bundle. Process it.
|
|
// Beware, sometimes check for backtrack[i] == TargetPacket
|
|
// does not work, so this instruction could be one from the target bundle.
|
|
SmallVector<unsigned, 4> Defs;
|
|
SmallVector<unsigned, 8> Uses;
|
|
MachineInstr *MIU = backtrack[i];
|
|
parseOperands(MIU, Defs, Uses);
|
|
|
|
for (SmallVector<unsigned, 8>::iterator IA = Uses.begin(), IAE = Uses.end();
|
|
IA != IAE; ++IA) {
|
|
if (KilledUseSet.count(*IA)) {
|
|
// Now this is new kill point for this Reg.
|
|
// Update the bundle, and any local uses.
|
|
markKillReg(MIU, *IA);
|
|
|
|
// Unmark the current MI.
|
|
unmarkKillReg(MI, *IA);
|
|
|
|
if (MIU->isBundle()) {
|
|
// TODO: Can do this cleaner and faster.
|
|
MachineBasicBlock::instr_iterator MII = MIU->getIterator();
|
|
MachineBasicBlock::instr_iterator End = CurrentBB->instr_end();
|
|
for (++MII; MII != End && MII->isInsideBundle(); ++MII)
|
|
markKillReg(&*MII, *IA);
|
|
}
|
|
|
|
// We have updated this kill reg, if there are more, keep on going.
|
|
KilledUseSet.erase(*IA);
|
|
|
|
// If the set is exhausted, just leave.
|
|
if (KilledUseSet.empty())
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/// This is houskeeping for bundle with instruction just added to it.
|
|
void HexagonGlobalSchedulerImpl::addInstructionToExistingBundle(
|
|
MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
|
|
MachineBasicBlock::instr_iterator &Tail,
|
|
MachineBasicBlock::instr_iterator &NewMI,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
std::vector<MachineInstr *> &backtrack) {
|
|
Tail = getBundleEnd(Head);
|
|
LLVM_DEBUG(dbgs() << "\t\t\t[Add] Head home: "; DumpPacket(Head));
|
|
|
|
// Old header to be deleted shortly.
|
|
MachineBasicBlock::instr_iterator Outcast = Head;
|
|
// Unbundle old header.
|
|
if (Outcast->isBundle() && Outcast->isBundledWithSucc())
|
|
Outcast->unbundleFromSucc();
|
|
|
|
bool memShufDisabled = QII->getBundleNoShuf(*Outcast);
|
|
|
|
// Create new bundle header and update MI flags.
|
|
finalizeBundle(*HomeBB, ++Head, Tail);
|
|
MachineBasicBlock::instr_iterator BundleMII = std::prev(Head);
|
|
if (memShufDisabled)
|
|
QII->setBundleNoShuf(BundleMII);
|
|
--Head;
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\t\t[Add] New Head : "; DumpPacket(Head));
|
|
|
|
// The old header could be listed in the back tracking,
|
|
// so if it is, we need to update it.
|
|
for (unsigned i = 0; i < backtrack.size(); ++i)
|
|
if (backtrack[i] == &*Outcast)
|
|
backtrack[i] = &*Head;
|
|
|
|
// Same for top MI iterator.
|
|
if (NextMI == Outcast)
|
|
NextMI = Head;
|
|
|
|
TargetPacket = Head;
|
|
HomeBB->erase(Outcast);
|
|
}
|
|
|
|
/// This handles houskeeping for bundle with instruction just deleted from it.
|
|
/// We do not see the original moved instruction in here.
|
|
void HexagonGlobalSchedulerImpl::removeInstructionFromExistingBundle(
|
|
MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
|
|
MachineBasicBlock::instr_iterator &Tail,
|
|
MachineBasicBlock::iterator &SourceLocation,
|
|
MachineBasicBlock::iterator &NextMI, bool MovingDependentOp,
|
|
std::vector<MachineInstr *> &backtrack) {
|
|
// Empty BBs will be deleted shortly.
|
|
if (HomeBB->empty()) {
|
|
Head = MachineBasicBlock::instr_iterator();
|
|
Tail = MachineBasicBlock::instr_iterator();
|
|
return;
|
|
}
|
|
|
|
if (!SourceLocation->isBundle()) {
|
|
LLVM_DEBUG(dbgs() << "\t\t\tOriginal instruction was not bundled.\n\t\t\t";
|
|
SourceLocation->dump());
|
|
// If original instruction was not bundled, and we have moved it
|
|
// and it is in the back track, we probably want to remove it from there.
|
|
LLVM_DEBUG(dbgs() << "\t\t\t[Rem] New head: "; backtrack.back()->dump());
|
|
|
|
for (unsigned i = 0; i < backtrack.size(); ++i) {
|
|
if (backtrack[i] == &*SourceLocation) {
|
|
// By definition, this should be the last instruction in the backtrack.
|
|
assert((backtrack[i] == backtrack.back()) && "Lost back track");
|
|
backtrack.pop_back();
|
|
}
|
|
// Point the main iterator to the next instruction.
|
|
if (NextMI == SourceLocation)
|
|
NextMI++;
|
|
}
|
|
SourceLocation = MachineBasicBlock::iterator();
|
|
Head = MachineBasicBlock::instr_iterator();
|
|
Tail = MachineBasicBlock::instr_iterator();
|
|
return;
|
|
}
|
|
|
|
// The old header, soon to be deleted.
|
|
MachineBasicBlock::instr_iterator Outcast = SourceLocation.getInstrIterator();
|
|
LLVM_DEBUG(dbgs() << "\t\t\t[Rem] SourceLocation after bundle update: ";
|
|
DumpPacket(Outcast));
|
|
|
|
// If bundle has been already destroyed. BB->splat seems to do it some times
|
|
// but not the other.
|
|
// We already know that SourceLocation is bundle header.
|
|
if (!SourceLocation->isBundledWithSucc()) {
|
|
assert(!Head->isBundledWithSucc() && !Head->isBundledWithPred() &&
|
|
"Bad bundle");
|
|
} else {
|
|
Head = SourceLocation.getInstrIterator();
|
|
Tail = getBundleEnd(Head);
|
|
unsigned Size = 0;
|
|
unsigned BBSizeWithDbg = 0;
|
|
MachineBasicBlock::const_instr_iterator I(Head);
|
|
MachineBasicBlock::const_instr_iterator E = Head->getParent()->instr_end();
|
|
|
|
for (++I; I != E && I->isBundledWithPred(); ++I) {
|
|
++BBSizeWithDbg;
|
|
if (!I->isDebugInstr())
|
|
++Size;
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\t\t[Rem] Size(" << Size << ") Head orig: ";
|
|
DumpPacket(Head));
|
|
// The old header, soon to be deleted.
|
|
Outcast = Head;
|
|
|
|
// The old Header is still counted here.
|
|
if (Size > 1) {
|
|
if (Outcast->isBundle() && Outcast->isBundledWithSucc())
|
|
Outcast->unbundleFromSucc();
|
|
|
|
bool memShufDisabled = QII->getBundleNoShuf(*Outcast);
|
|
// The finalizeBundle() assumes that "original" sequence
|
|
// it is finalizing is sequentially correct. That basically
|
|
// means that swap case might not be handled properly.
|
|
// I find insert point for the pull-up instruction myself,
|
|
// and I should try to catch that swap case there, and refuse
|
|
// to insert if I cannot guarantee correct serial semantics.
|
|
// In the future, I need my own incremental "inserToBundle"
|
|
// function.
|
|
finalizeBundle(*HomeBB, ++Head, Tail);
|
|
MachineBasicBlock::instr_iterator BundleMII = std::prev(Head);
|
|
if (memShufDisabled)
|
|
QII->setBundleNoShuf(BundleMII);
|
|
|
|
--Head;
|
|
} else if (Size == 1) {
|
|
// There is only one non-debug instruction in the bundle.
|
|
if (BBSizeWithDbg > 1) {
|
|
// There are some debug instructions that should be unbundled too.
|
|
MachineBasicBlock::instr_iterator I(Head);
|
|
MachineBasicBlock::instr_iterator E = Head->getParent()->instr_end();
|
|
for (++I; I != E && I->isBundledWithPred(); ++I) {
|
|
I->unbundleFromPred();
|
|
// Set Head to the non-debug instruction.
|
|
if (!I->isDebugInstr())
|
|
Head = I;
|
|
}
|
|
} else {
|
|
// This means that only one original instruction is
|
|
// left in the bundle. We need to "unbundle" it because the
|
|
// rest of API will not like it.
|
|
++Head;
|
|
if (Head->isBundledWithPred())
|
|
Head->unbundleFromPred();
|
|
if (Head->isBundledWithSucc())
|
|
Head->unbundleFromSucc();
|
|
}
|
|
} else
|
|
llvm_unreachable("Corrupt bundle");
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\t\t[Rem] New Head : "; DumpPacket(Head));
|
|
SourceLocation = Head;
|
|
|
|
// The old header could be listed in the back tracking,
|
|
// so if it is, we need to update it.
|
|
for (unsigned i = 0; i < backtrack.size(); ++i)
|
|
if (backtrack[i] == &*Outcast)
|
|
backtrack[i] = &*Head;
|
|
|
|
// Same for top MI iterator.
|
|
if (NextMI == Outcast)
|
|
NextMI = Head;
|
|
|
|
HomeBB->erase(Outcast);
|
|
}
|
|
|
|
#ifndef NDEBUG
|
|
static void debugLivenessForBB(const MachineBasicBlock *MBB,
|
|
const TargetRegisterInfo *TRI) {
|
|
LLVM_DEBUG(dbgs() << "\tLiveness for BB:\n"; MBB->dump());
|
|
for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
|
|
SE = MBB->succ_end();
|
|
SI != SE; ++SI) {
|
|
LLVM_DEBUG(dbgs() << "\tSuccessor BB (" << (*SI)->getNumber() << "):");
|
|
for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
|
|
E = (*SI)->livein_end();
|
|
I != E; ++I)
|
|
LLVM_DEBUG(dbgs() << "\t" << printReg((*I).PhysReg, TRI));
|
|
LLVM_DEBUG(dbgs() << "\n");
|
|
}
|
|
}
|
|
#endif
|
|
|
|
// Blocks should be considered empty if they contain only debug info;
|
|
// else the debug info would affect codegen.
|
|
static bool IsEmptyBlock(MachineBasicBlock *MBB) {
|
|
if (MBB->empty())
|
|
return true;
|
|
for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
|
|
MBBI != MBBE; ++MBBI) {
|
|
if (!MBBI->isDebugInstr())
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Treat given instruction as a branch, go through its operands
|
|
/// and see if any of them is a BB address. If so, return it.
|
|
/// Return NULL otherwise.
|
|
static inline MachineBasicBlock *getBranchDestination(MachineInstr *MI) {
|
|
if (!MI || !MI->isBranch() || MI->isBundle())
|
|
return NULL;
|
|
|
|
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
|
const MachineOperand &MO = MI->getOperand(i);
|
|
if (MO.isMBB())
|
|
return MO.getMBB();
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
/// Similar to HexagonInstrInfo::analyzeBranch but handles
|
|
/// serveral more general cases including parsing empty BBs when possible.
|
|
bool HexagonGlobalSchedulerImpl::AnalyzeBBBranches(MachineBasicBlock *MBB,
|
|
MachineBasicBlock *&TBB,
|
|
MachineInstr *&FirstTerm,
|
|
MachineBasicBlock *&FBB,
|
|
MachineInstr *&SecondTerm) {
|
|
// Hexagon allowes up to two jumps in MBB.
|
|
FirstTerm = NULL;
|
|
SecondTerm = NULL;
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\t\tAnalyze Branches in BB(" << MBB->getNumber()
|
|
<< ")\n");
|
|
if (MBB->succ_size() == 0) {
|
|
LLVM_DEBUG(dbgs() << "\n\t\tBlock has no successors.\n");
|
|
return true;
|
|
}
|
|
// Find both jumps.
|
|
// We largely rely on implied assumption that BB branching always
|
|
// looks like this:
|
|
// J2_jumpf %P0, <BB#60>, %PC<imp-def>;
|
|
// J2_jump <BB#49>
|
|
// Branches also could be in different packets.
|
|
MachineBasicBlock::instr_iterator MIB = MBB->instr_begin();
|
|
MachineBasicBlock::instr_iterator MIE = MBB->instr_end();
|
|
MachineBasicBlock::instr_iterator MII = MIB;
|
|
|
|
if (QII->nonDbgBBSize(MBB) == 1) {
|
|
MII = MBB->getFirstNonDebugInstr().getInstrIterator();
|
|
if (MII->isBranch())
|
|
FirstTerm = &*MII;
|
|
} else {
|
|
// We have already eliminated the case when MIB == MIE.
|
|
while (MII != MIE) {
|
|
if (!MII->isBundle() && MII->isBranch()) {
|
|
if (!FirstTerm)
|
|
FirstTerm = &*MII;
|
|
else
|
|
SecondTerm = &*MII;
|
|
}
|
|
++MII;
|
|
}
|
|
}
|
|
if ((FirstTerm && FirstTerm->isIndirectBranch()) ||
|
|
(SecondTerm && SecondTerm->isIndirectBranch())) {
|
|
LLVM_DEBUG(dbgs() << "\n\t\tCannot analyze BB with indirect branch.");
|
|
return true;
|
|
}
|
|
if ((FirstTerm && FirstTerm->getOpcode() == Hexagon::J2_jump &&
|
|
!FirstTerm->getOperand(0).isMBB()) ||
|
|
(SecondTerm && SecondTerm->getOpcode() == Hexagon::J2_jump &&
|
|
!SecondTerm->getOperand(0).isMBB())) {
|
|
LLVM_DEBUG(
|
|
dbgs() << "\n\t\tCannot analyze BB with a branch out of function.");
|
|
return true;
|
|
}
|
|
|
|
// Now try to analyze this branch.
|
|
SmallVector<MachineOperand, 4> Cond;
|
|
if (QII->analyzeBranch(*MBB, TBB, FBB, Cond, false)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tFail to analyze with analyzeBranch.\n");
|
|
LLVM_DEBUG(dbgs() << "\t\tFirst term: "; if (FirstTerm) FirstTerm->dump();
|
|
else dbgs() << "None\n";);
|
|
// Could not analyze it. See if this is something we can recognize.
|
|
TBB = getBranchDestination(FirstTerm);
|
|
}
|
|
// There are several cases not handled by HexagonInstrInfo::analyzeBranch.
|
|
if (!TBB) {
|
|
LLVM_DEBUG(dbgs() << "\t\tMissing TBB.\n");
|
|
// There is a branch, but TBB is not found.
|
|
// The BB could also be empty at this point. See if it is a trivial
|
|
// layout case.
|
|
if (MBB->succ_size() == 1) {
|
|
TBB = *MBB->succ_begin();
|
|
LLVM_DEBUG(dbgs() << "\t\tFall through TBB(" << TBB->getNumber()
|
|
<< ").\n");
|
|
return false;
|
|
} else if (MBB->succ_size() == 2) {
|
|
// This should cover majority of remaining cases.
|
|
if (FirstTerm && SecondTerm &&
|
|
(QII->isPredicated(*FirstTerm) || QII->isNewValueJump(*FirstTerm)) &&
|
|
!QII->isPredicated(*SecondTerm)) {
|
|
TBB = getBranchDestination(FirstTerm);
|
|
FBB = getBranchDestination(SecondTerm);
|
|
LLVM_DEBUG(dbgs() << "\t\tCanonical dual jump layout: TBB("
|
|
<< TBB->getNumber() << ") FBB(" << FBB->getNumber()
|
|
<< ").\n");
|
|
return false;
|
|
} else if (SecondTerm && SecondTerm->getOpcode() == Hexagon::J2_jump &&
|
|
SecondTerm->getOperand(0).isMBB()) {
|
|
// Look at the second term if I know it, to find out what is the fall
|
|
// through for this BB.
|
|
FBB = SecondTerm->getOperand(0).getMBB();
|
|
assert(MBB->succ_size() == 2 && "Expected exactly 2 successors");
|
|
MachineBasicBlock *Succ0 = *MBB->succ_begin();
|
|
MachineBasicBlock *Succ1 = *std::next(MBB->succ_begin());
|
|
if (FBB == Succ0)
|
|
TBB = Succ1;
|
|
else
|
|
TBB = Succ0;
|
|
LLVM_DEBUG(dbgs() << "\t\tSecond br is J2_jump TBB(" << TBB->getNumber()
|
|
<< ") FBB(" << FBB->getNumber() << ").\n");
|
|
return false;
|
|
} else {
|
|
// This might be an empty BB but still with two
|
|
// successors set. Try to use CFG layout to sort it out.
|
|
// This could happen when last jump was pulled up from a BB, and
|
|
// CFG is being updated. At that point this method is called and
|
|
// returns best guess possible for TBB/FBB. Fortunately order of those
|
|
// is irrelevant, and rather used a worklist for CFG update.
|
|
MachineFunction::iterator MBBIter = MBB->getIterator();
|
|
MachineFunction &MF = *MBB->getParent();
|
|
(void)MF; // supress compiler warning
|
|
// If there are no other clues, assume next sequential BB
|
|
// in CFG as FBB.
|
|
++MBBIter;
|
|
assert(MBBIter != MF.end() && "I give up.");
|
|
FBB = &(*MBBIter);
|
|
assert(MBB->succ_size() == 2 && "Expected exactly 2 successors");
|
|
MachineBasicBlock *S0 = *MBB->succ_begin();
|
|
MachineBasicBlock *S1 = *std::next(MBB->succ_begin());
|
|
if (FBB == S0)
|
|
TBB = S1;
|
|
else if (FBB == S1) {
|
|
TBB = S0;
|
|
} else {
|
|
// This case can arise when the layout successor basic block (++IMBB)
|
|
// got empty during pull-up.
|
|
// As a result, ++IMBB is not one of MBB's successors.
|
|
MBBIter = MF.begin();
|
|
while (!MBB->isSuccessor(&*MBBIter) && (MBBIter != MF.end()))
|
|
++MBBIter;
|
|
assert(MBBIter != MF.end() && "Malformed BB with invalid successors");
|
|
FBB = &*MBBIter;
|
|
if (FBB == S0)
|
|
TBB = S1;
|
|
else
|
|
TBB = S0;
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\t\tUse layout TBB(" << TBB->getNumber()
|
|
<< ") FBB(" << FBB->getNumber() << ").\n");
|
|
return false;
|
|
}
|
|
}
|
|
assert(!FirstTerm && "Bad BB");
|
|
return true;
|
|
}
|
|
// Ok, we have TBB, but maybe missing FBB.
|
|
if (!FBB && SecondTerm) {
|
|
LLVM_DEBUG(dbgs() << "\t\tMissing FBB.\n");
|
|
// analyzeBranch could lie to us, ignore it in this case.
|
|
// For the canonical case simply take known branch targets.
|
|
if ((QII->isPredicated(*FirstTerm) || QII->isNewValueJump(*FirstTerm)) &&
|
|
!QII->isPredicated(*SecondTerm)) {
|
|
FBB = getBranchDestination(SecondTerm);
|
|
} else {
|
|
// Second term is also predicated.
|
|
// Use CFG layout. Assign layout successor as FBB.
|
|
for (MachineBasicBlock *Succ : MBB->successors()) {
|
|
if (MBB->isLayoutSuccessor(Succ))
|
|
FBB = Succ;
|
|
}
|
|
if (FBB == NULL) {
|
|
LLVM_DEBUG(dbgs() << "\nNo layout successor found.");
|
|
LLVM_DEBUG(dbgs() << "Possibly the layout successor is an empty BB");
|
|
return true;
|
|
}
|
|
if (TBB == FBB)
|
|
LLVM_DEBUG(dbgs() << "Malformed branch with useless branch condition";);
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\t\tSecond term: "; SecondTerm->dump());
|
|
} else if (TBB && !FBB) {
|
|
// If BB ends in endloop, and it is a single BB hw loop,
|
|
// we will have a single terminator, but we can figure FBB
|
|
// easily from CFG.
|
|
if (MBB->succ_size() == 2) {
|
|
MachineBasicBlock *S0 = *MBB->succ_begin();
|
|
MachineBasicBlock *S1 = *std::next(MBB->succ_begin());
|
|
if (TBB == S0)
|
|
FBB = S1;
|
|
else
|
|
FBB = S0;
|
|
}
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\tFinal TBB(" << TBB->getNumber() << ").\n";
|
|
if (FBB) dbgs() << "\t\tFinal FBB(" << FBB->getNumber() << ").\n";
|
|
else dbgs() << "\t\tFinal FBB(None)\n";);
|
|
return false;
|
|
}
|
|
|
|
/// updateBranches - Updates all branches to \p From in the basic block \p
|
|
/// InBlock to branches to \p To.
|
|
static void updateBranches(MachineBasicBlock &InBlock, MachineBasicBlock *From,
|
|
MachineBasicBlock *To) {
|
|
for (MachineBasicBlock::instr_iterator BI = InBlock.instr_begin(),
|
|
E = InBlock.instr_end();
|
|
BI != E; ++BI) {
|
|
MachineInstr *Inst = &*BI;
|
|
// Ignore anything that is not a branch.
|
|
if (!Inst->isBranch())
|
|
continue;
|
|
for (MachineInstr::mop_iterator OI = Inst->operands_begin(),
|
|
OE = Inst->operands_end();
|
|
OI != OE; ++OI) {
|
|
MachineOperand &Opd = *OI;
|
|
// Look for basic block "From".
|
|
if (!Opd.isMBB() || Opd.getMBB() != From)
|
|
continue;
|
|
// Update it.
|
|
Opd.setMBB(To);
|
|
}
|
|
}
|
|
}
|
|
|
|
/// Rewrite all predecessors of the old block to go to the fallthrough
|
|
/// instead.
|
|
/// NB: Collect predecessors into a snapshot vector before iterating to
|
|
/// avoid iterator invalidation on MBB's predecessor list. Each call to
|
|
/// ReplaceUsesOfBlockWith modifies both the successor list of Pred and
|
|
/// the predecessor list of MBB, which invalidates debug-mode iterators
|
|
/// (detected by _GLIBCXX_DEBUG).
|
|
static void updatePredecessors(MachineBasicBlock &MBB,
|
|
MachineBasicBlock *MFBB) {
|
|
MachineFunction &MF = *MBB.getParent();
|
|
|
|
if (MFBB->getIterator() == MF.end())
|
|
return;
|
|
|
|
// Snapshot the predecessor list to avoid iterator invalidation.
|
|
SmallVector<MachineBasicBlock *, 4> Preds(MBB.pred_begin(), MBB.pred_end());
|
|
for (MachineBasicBlock *Pred : Preds) {
|
|
if (!Pred->isSuccessor(&MBB))
|
|
continue;
|
|
Pred->ReplaceUsesOfBlockWith(&MBB, MFBB);
|
|
updateBranches(*Pred, &MBB, MFBB);
|
|
}
|
|
}
|
|
|
|
static void UpdateCFG(MachineBasicBlock *HomeBB, MachineBasicBlock *OriginBB,
|
|
MachineInstr *MII, MachineBasicBlock *HomeTBB,
|
|
MachineBasicBlock *HomeFBB, MachineInstr *FTA,
|
|
MachineInstr *STA,
|
|
const MachineBranchProbabilityInfo *MBPI) {
|
|
MachineBasicBlock *S2Add = NULL, *S2Remove = NULL;
|
|
bool RemoveLSIfPresent = false;
|
|
if ((&*MII == FTA) && MII->isConditionalBranch()) {
|
|
LLVM_DEBUG(dbgs() << "\nNew firstterm conditional jump added to HomeBB";);
|
|
S2Add = HomeTBB;
|
|
S2Remove = HomeTBB;
|
|
} else if ((&*MII == STA) && MII->isConditionalBranch()) {
|
|
LLVM_DEBUG(dbgs() << "\nNew secondterm conditional jump added to HomeBB";);
|
|
// AnalyzeBBBranches might not give correct information in this case.
|
|
// The branch destination may be a symbol, not necessarily a block.
|
|
if (MachineBasicBlock *Dest = getBranchDestination(MII)) {
|
|
LLVM_DEBUG(dbgs() << "\nBranch destination for pulled instruction is BB#"
|
|
<< Dest->getNumber(););
|
|
S2Add = Dest;
|
|
S2Remove = Dest;
|
|
}
|
|
} else if ((&*MII == FTA) && MII->isUnconditionalBranch()) {
|
|
LLVM_DEBUG(dbgs() << "\nNew firstterm unconditional jump added to HomeBB";);
|
|
S2Add = HomeTBB;
|
|
S2Remove = HomeTBB;
|
|
RemoveLSIfPresent = true;
|
|
} else if ((&*MII == STA) && MII->isUnconditionalBranch()) {
|
|
LLVM_DEBUG(
|
|
dbgs() << "\nNew secondterm unconditional jump added to HomeBB";);
|
|
S2Add = HomeFBB;
|
|
S2Remove = HomeFBB;
|
|
RemoveLSIfPresent = true;
|
|
}
|
|
if (S2Add && !HomeBB->isSuccessor(S2Add)) {
|
|
HomeBB->addSuccessor(S2Add, MBPI->getEdgeProbability(OriginBB, S2Add));
|
|
}
|
|
if (S2Remove)
|
|
OriginBB->removeSuccessor(S2Remove);
|
|
if (RemoveLSIfPresent) {
|
|
MachineFunction::iterator HomeBBLS = HomeBB->getIterator();
|
|
++HomeBBLS;
|
|
if (HomeBBLS != HomeBB->getParent()->end() &&
|
|
HomeBB->isLayoutSuccessor(&*HomeBBLS)) {
|
|
LLVM_DEBUG(dbgs() << "\nRemoving LayoutSucc BB#" << HomeBBLS->getNumber()
|
|
<< "from list of successors";);
|
|
HomeBB->removeSuccessor(&*HomeBBLS);
|
|
}
|
|
}
|
|
}
|
|
|
|
/// Move instruction from/to BB, Update liveness info,
|
|
/// return pointer to the newly inserted and modified
|
|
/// instruction.
|
|
MachineInstr *HexagonGlobalSchedulerImpl::MoveAndUpdateLiveness(
|
|
BasicBlockRegion *CurrentRegion, MachineBasicBlock *HomeBB,
|
|
MachineInstr *InstrToMove, bool NeedToNewify, unsigned DepReg,
|
|
bool MovingDependentOp, MachineBasicBlock *OriginBB,
|
|
MachineInstr *OriginalInstruction, SmallVector<MachineOperand, 4> &Cond,
|
|
MachineBasicBlock::iterator &SourceLocation,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
std::vector<MachineInstr *> &backtrack) {
|
|
LLVM_DEBUG(
|
|
dbgs() << "\n...............[MoveAndUpdateLiveness]..............\n");
|
|
LLVM_DEBUG(dbgs() << "\t\tInstrToMove :\t"; InstrToMove->dump());
|
|
LLVM_DEBUG(dbgs() << "\t\tOriginalInstruction:\t";
|
|
OriginalInstruction->dump());
|
|
LLVM_DEBUG(dbgs() << "\t\tSourceLocation :\t";
|
|
DumpPacket(SourceLocation.getInstrIterator()));
|
|
LLVM_DEBUG(dbgs() << "\t\tTargetPacket :\t";
|
|
DumpPacket(TargetPacket.getInstrIterator()));
|
|
|
|
MachineBasicBlock::instr_iterator OriginalHead =
|
|
SourceLocation.getInstrIterator();
|
|
MachineBasicBlock::instr_iterator OriginalTail = getBundleEnd(OriginalHead);
|
|
MachineBasicBlock::instr_iterator OutcastFrom =
|
|
OriginalInstruction->getIterator();
|
|
|
|
// Remove our temporary instruction.
|
|
MachineBasicBlock::instr_iterator kill_it(InstrToMove);
|
|
HomeBB->erase(kill_it);
|
|
|
|
MachineBasicBlock::instr_iterator TargetHead(TargetPacket.getInstrIterator());
|
|
MachineBasicBlock::instr_iterator TargetTail = getBundleEnd(TargetHead);
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\tTo BB before:\n"; debugLivenessForBB(HomeBB, QRI));
|
|
LLVM_DEBUG(dbgs() << "\n\tFrom BB before:\n";
|
|
debugLivenessForBB(OriginBB, QRI));
|
|
|
|
// Before we perform the move, we need to collect the worklist
|
|
// of BBs for liveness updated.
|
|
std::list<MachineBasicBlock *> WorkList;
|
|
|
|
// Insert into the work list all BBs along the backtrace.
|
|
for (std::vector<MachineInstr *>::iterator RI = backtrack.begin(),
|
|
RIE = backtrack.end();
|
|
RI != RIE; RI++)
|
|
WorkList.push_back((*RI)->getParent());
|
|
|
|
// Only keep unique entries.
|
|
// TODO: Use a different container here.
|
|
WorkList.unique();
|
|
|
|
// Move the original instruction.
|
|
// If this instruction is inside a bundle, update the bundle.
|
|
MachineBasicBlock::instr_iterator BBEnd =
|
|
TargetHead->getParent()->instr_end();
|
|
bool LastInstructionInBundle = false;
|
|
MachineBasicBlock::instr_iterator MII = findInsertPositionInBundle(
|
|
TargetPacket, &*OutcastFrom, LastInstructionInBundle);
|
|
|
|
(void)BBEnd;
|
|
LLVM_DEBUG(dbgs() << "\n\t\t\tHead target : "; DumpPacket(TargetHead));
|
|
LLVM_DEBUG(dbgs() << "\t\t\tTail target : ";
|
|
DumpPacket(TargetTail, BBEnd));
|
|
LLVM_DEBUG(dbgs() << "\t\t\tInsert right before: "; DumpPacket(MII, BBEnd));
|
|
|
|
MIBundleBuilder Bundle(&*TargetHead);
|
|
|
|
// Actual move. One day liveness might be updated here.
|
|
if (OriginalInstruction->isBundled()) {
|
|
Bundle.insert(MII, OriginalInstruction->removeFromBundle());
|
|
--MII;
|
|
} else {
|
|
// This is one case currently unhandled by Bundle.insert
|
|
// and needs to be fixed upstream. Meanwhile use old way to handle
|
|
// this odd case.
|
|
if (OriginalInstruction->getIterator() == TargetTail) {
|
|
LLVM_DEBUG(dbgs() << "\t\t\tSpecial case move.\n");
|
|
MachineBasicBlock::instr_iterator MIIToPred = MII;
|
|
--MIIToPred;
|
|
LLVM_DEBUG(dbgs() << "\t\t\tInser after : ";
|
|
DumpPacket(MIIToPred, BBEnd));
|
|
// Unbundle it in its current location.
|
|
if (OutcastFrom->isBundledWithSucc()) {
|
|
OutcastFrom->clearFlag(MachineInstr::BundledSucc);
|
|
OutcastFrom->clearFlag(MachineInstr::BundledPred);
|
|
} else if (OutcastFrom->isBundledWithPred()) {
|
|
OutcastFrom->unbundleFromPred();
|
|
}
|
|
HomeBB->splice(MII, OriginBB, OutcastFrom);
|
|
if (!MII->isBundledWithPred())
|
|
MII->bundleWithPred();
|
|
if (!LastInstructionInBundle && !MII->isBundledWithSucc())
|
|
MII->bundleWithSucc();
|
|
// This is the instruction after which we have inserted.
|
|
if (!MIIToPred->isBundledWithSucc())
|
|
MIIToPred->bundleWithSucc();
|
|
} else {
|
|
Bundle.insert(MII, OriginalInstruction->removeFromParent());
|
|
--MII;
|
|
}
|
|
}
|
|
// Source location bundle is updated later in the
|
|
// removeInstructionFromExistingBundle().
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\t\tNew packet head: "; DumpPacket(TargetHead));
|
|
LLVM_DEBUG(dbgs() << "\t\t\tInserted op : "; MII->dump());
|
|
LLVM_DEBUG(dbgs() << "\n\tTo BB after move:\n";
|
|
debugLivenessForBB(HomeBB, QRI));
|
|
LLVM_DEBUG(dbgs() << "\n\tFrom BB after:\n";
|
|
debugLivenessForBB(OriginBB, QRI));
|
|
|
|
// Update kill patterns. Do it before we have predicated the moved
|
|
// instruction.
|
|
updateKillAlongThePath(HomeBB, OriginBB, MII, TargetTail, SourceLocation,
|
|
TargetPacket, backtrack);
|
|
// I need to know:
|
|
// - true/false predication
|
|
// - do I need to .new it?
|
|
// - do I need to .old it?
|
|
// If the original instruction used new value operands,
|
|
// it might need to be changed to the generic form
|
|
// before further processing.
|
|
if (QII->isDotNewInst(*MII)) {
|
|
DemoteToDotOld(&*MII);
|
|
LLVM_DEBUG(dbgs() << "\t\t\tDemoted to .old\t:"; MII->dump());
|
|
}
|
|
|
|
// We have previously checked whether this instruction could
|
|
// be placed in this packet, including all possible transformations
|
|
// it might need, so if any request will fail now, something is wrong.
|
|
//
|
|
// Need for predication and the exact condition is determined by
|
|
// the path between original and current instruction location.
|
|
if (!Cond.empty()) { // To be predicated
|
|
LLVM_DEBUG(dbgs() << "\t\t\tPredicating:"; MII->dump());
|
|
assert(TII->isPredicable(*MII) && "MII is not predicable");
|
|
TII->PredicateInstruction(*MII, Cond);
|
|
if (NeedToNewify) {
|
|
assert((DepReg < std::numeric_limits<unsigned>::max()) &&
|
|
"Invalid pred reg value");
|
|
LLVM_DEBUG(dbgs() << "\t\t\tNeeds to NEWify on Reg("
|
|
<< printReg(DepReg, QRI) << ").\n");
|
|
int NewOpcode = QII->getDotNewPredOp(*MII, MBPI);
|
|
MII->setDesc(QII->get(NewOpcode));
|
|
|
|
// Now we need to mark newly created predicate operand as
|
|
// internal read.
|
|
// TODO: Better look for predicate operand.
|
|
for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
|
|
MachineOperand &MO = MII->getOperand(i);
|
|
if (!MO.isReg())
|
|
continue;
|
|
if (MO.isDef())
|
|
continue;
|
|
if (DepReg == MO.getReg())
|
|
MO.setIsInternalRead();
|
|
}
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\t\t\tNew predicated form:\t"; MII->dump());
|
|
// If the predicate has changed kill pattern, now we need to propagate
|
|
// that again. This is important for liveness computation.
|
|
updateKillAlongThePath(HomeBB, OriginBB, MII, TargetTail, SourceLocation,
|
|
TargetPacket, backtrack);
|
|
}
|
|
|
|
// Create new bundle header, remove the old one.
|
|
addInstructionToExistingBundle(HomeBB, TargetHead, TargetTail, MII,
|
|
TargetPacket, NextMI, backtrack);
|
|
|
|
// If moved instruction was inside a bundle, update that bundle.
|
|
removeInstructionFromExistingBundle(OriginBB, ++OriginalHead, OriginalTail,
|
|
SourceLocation, NextMI, MovingDependentOp,
|
|
backtrack);
|
|
|
|
// If removed instruction could have been dependent on any
|
|
// of the remaining ops, we need to oldify possible affected ones.
|
|
LLVM_DEBUG(dbgs() << "\t\tTargetHead:\t"; DumpPacket(TargetHead, BBEnd));
|
|
LLVM_DEBUG(dbgs() << "\t\tOriginalHead:\t"; DumpPacket(OriginalHead, BBEnd));
|
|
LLVM_DEBUG(dbgs() << "\t\tOriginalInstruction:\t";
|
|
DumpPacket(OriginalInstruction->getIterator(), BBEnd));
|
|
LLVM_DEBUG(dbgs() << "\t\tOutcastFrom:\t"; DumpPacket(OutcastFrom, BBEnd));
|
|
|
|
// Clean up the original source bundle on a global scope.
|
|
if (OriginalHead != MachineBasicBlock::instr_iterator() &&
|
|
QII->isEndLoopN(OriginalHead->getOpcode())) {
|
|
// Single endloop left. Since it is not a real instruction,
|
|
// we can simply add it to a non empty previous bundle, if one exist,
|
|
// or let assembler to produce a fake bundle for it.
|
|
LLVM_DEBUG(dbgs() << "\t\tOnly endloop in packet.\n");
|
|
MachineBasicBlock::instr_iterator I(OriginalHead);
|
|
if (OriginBB->begin() != I) {
|
|
--I;
|
|
if (I->isBundled()) {
|
|
if (!I->isBundledWithSucc())
|
|
I->bundleWithSucc();
|
|
if (!OriginalHead->isBundledWithPred())
|
|
OriginalHead->bundleWithPred();
|
|
}
|
|
// else we probably need to create a new bundle here.
|
|
// SourceLocation = NULL;
|
|
}
|
|
} else if (MovingDependentOp &&
|
|
OriginalHead != MachineBasicBlock::instr_iterator()) {
|
|
if (OriginalHead->isBundled()) {
|
|
for (MachineBasicBlock::instr_iterator J = ++OriginalHead;
|
|
J != OriginalTail && J->isInsideBundle() && !J->isBundle(); ++J) {
|
|
// Need to oldify it.
|
|
if (MIsHaveTrueDependency(OriginalInstruction, &*J) &&
|
|
QII->isDotNewInst(*J)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tDemoting to .old:\t"; J->dump());
|
|
DemoteToDotOld(&*J);
|
|
}
|
|
}
|
|
} else {
|
|
// Single instruction left.
|
|
if (MIsHaveTrueDependency(OriginalInstruction, &*OriginalHead) &&
|
|
QII->isDotNewInst(*OriginalHead)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tDemoting to .old op:\t";
|
|
OriginalHead->dump());
|
|
DemoteToDotOld(&*OriginalHead);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Now we need to update liveness to all BBs involved
|
|
// including those we might have "passed" through on the way here.
|
|
LLVM_DEBUG(dbgs() << "\n\tTo BB after bundle update:\n"; HomeBB->dump());
|
|
LLVM_DEBUG(dbgs() << "\n\n\tFrom BB after bundle update:\n";
|
|
OriginBB->dump());
|
|
|
|
// Update global liveness.
|
|
LLVM_DEBUG(dbgs() << "\n\tWorkList:\t");
|
|
for (std::list<MachineBasicBlock *>::iterator BBI = WorkList.begin(),
|
|
BBIE = WorkList.end();
|
|
BBI != BBIE; BBI++) {
|
|
LLVM_DEBUG(dbgs() << "BB#" << (*BBI)->getNumber() << " ");
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\n");
|
|
|
|
do {
|
|
MachineBasicBlock *BB = WorkList.back();
|
|
WorkList.pop_back();
|
|
CurrentRegion->getLivenessInfoForBB(BB)->UpdateLiveness(BB);
|
|
} while (!WorkList.empty());
|
|
|
|
// No need to analyze for empty BB or update CFG for same BB pullup.
|
|
if (OriginBB == HomeBB)
|
|
return &*TargetHead;
|
|
// If the instruction moved was a branch we need to update the
|
|
// successor/predecessor of OriginBB and HomeBB accordingly.
|
|
MachineBasicBlock *HomeTBB, *HomeFBB;
|
|
MachineInstr *FTA = NULL, *STA = NULL;
|
|
bool HomeBBAnalyzed = !AnalyzeBBBranches(HomeBB, HomeTBB, FTA, HomeFBB, STA);
|
|
if (MII->isBranch()) {
|
|
if (HomeBBAnalyzed) {
|
|
UpdateCFG(HomeBB, OriginBB, &*MII, HomeTBB, HomeFBB, FTA, STA, MBPI);
|
|
} else {
|
|
llvm_unreachable("Underimplememted AnalyzeBBBranches");
|
|
}
|
|
}
|
|
// If we have exhausted the OriginBB clean it up.
|
|
// Beware that we could have created dual conditional jumps, which
|
|
// ultimately means we can have three way jumps.
|
|
if (IsEmptyBlock(OriginBB) && !OriginBB->isEHPad() &&
|
|
!OriginBB->hasAddressTaken() && !OriginBB->succ_empty()) {
|
|
// Dead block? Unlikely, but check.
|
|
LLVM_DEBUG(dbgs() << "Empty BB(" << OriginBB->getNumber() << ").\n");
|
|
// Update region map.
|
|
CurrentRegion->RemoveBBFromRegion(OriginBB);
|
|
// Keep the list of empty basic blocks to be freed later.
|
|
EmptyBBs.push_back(OriginBB);
|
|
if (OriginBB->pred_empty() || OriginBB->succ_empty())
|
|
return &*TargetHead;
|
|
|
|
if (OriginBB->succ_size() == 1) {
|
|
// Find empty block's successor.
|
|
MachineBasicBlock *CommonFBB = *OriginBB->succ_begin();
|
|
updatePredecessors(*OriginBB, CommonFBB);
|
|
// Remove the only successor entry for empty BB.
|
|
OriginBB->removeSuccessor(CommonFBB);
|
|
} else {
|
|
// Three way branching is not yet fully supported.
|
|
assert((OriginBB->succ_size() == 2) && "Underimplemented 3way branch.");
|
|
MachineBasicBlock *OriginTBB, *OriginFBB;
|
|
MachineInstr *FTB = NULL, *STB = NULL;
|
|
|
|
LLVM_DEBUG(dbgs() << "\tComplex case.\n");
|
|
if (HomeBBAnalyzed &&
|
|
!AnalyzeBBBranches(OriginBB, OriginTBB, FTB, OriginFBB, STB)) {
|
|
assert(OriginFBB && "Missing Origin FBB");
|
|
if (HomeFBB == OriginBB) {
|
|
// OriginBB is FBB for HomeBB.
|
|
if (HomeTBB == OriginTBB) {
|
|
// Shared TBB target, common FBB.
|
|
updatePredecessors(*OriginBB, OriginFBB);
|
|
} else if (HomeTBB == OriginFBB) {
|
|
// Shared TBB target, common FBB.
|
|
updatePredecessors(*OriginBB, OriginTBB);
|
|
} else {
|
|
// Three way branch. Add new successor to HomeBB.
|
|
updatePredecessors(*OriginBB, OriginFBB);
|
|
// TODO: Update the weight as well.
|
|
// Adding the successor to make updatePredecessor happy.
|
|
HomeBB->addSuccessor(OriginBB);
|
|
updatePredecessors(*OriginBB, OriginTBB);
|
|
}
|
|
} else if (HomeTBB == OriginBB) {
|
|
// OriginBB is TBB for HomeBB.
|
|
if (HomeFBB == OriginTBB) {
|
|
// Shared TBB target, common FBB.
|
|
updatePredecessors(*OriginBB, OriginFBB);
|
|
} else if (HomeFBB == OriginFBB) {
|
|
// Shared TBB target, common FBB.
|
|
updatePredecessors(*OriginBB, OriginTBB);
|
|
} else {
|
|
// Three way branch. Add new successor to HomeBB.
|
|
updatePredecessors(*OriginBB, OriginFBB);
|
|
// TODO: Update the weight as well.
|
|
// Adding the successor to make updatePredecessor happy.
|
|
HomeBB->addSuccessor(OriginBB);
|
|
updatePredecessors(*OriginBB, OriginTBB);
|
|
}
|
|
} else
|
|
llvm_unreachable("CFG update failed");
|
|
// The empty BB can now be relieved of its successors.
|
|
OriginBB->removeSuccessor(OriginFBB);
|
|
OriginBB->removeSuccessor(OriginTBB);
|
|
} else
|
|
llvm_unreachable("Underimplemented analyzeBranch");
|
|
}
|
|
LLVM_DEBUG(dbgs() << "Updated BB(" << HomeBB->getNumber() << ").\n";
|
|
HomeBB->dump());
|
|
}
|
|
return &*TargetHead;
|
|
}
|
|
|
|
// Find where inside a given bundle current instruction should be inserted.
|
|
// Instruction will be inserted _before_ this position.
|
|
MachineBasicBlock::instr_iterator
|
|
HexagonGlobalSchedulerImpl::findInsertPositionInBundle(
|
|
MachineBasicBlock::iterator &Bundle, MachineInstr *MI, bool &LastInBundle) {
|
|
MachineBasicBlock::instr_iterator MII = Bundle.getInstrIterator();
|
|
MachineBasicBlock *MBB = MII->getParent();
|
|
MachineBasicBlock::instr_iterator BBEnd = MBB->instr_end();
|
|
MachineBasicBlock::instr_iterator FirstBranch = BBEnd;
|
|
MachineBasicBlock::instr_iterator LastBundledInstruction = BBEnd;
|
|
MachineBasicBlock::instr_iterator DualJumpFirstCandidate = BBEnd;
|
|
|
|
assert(MII->isBundle() && "Missing insert location");
|
|
bool isDualJumpSecondCandidate = IsDualJumpSecondCandidate(MI);
|
|
LastInBundle = false;
|
|
|
|
for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII) {
|
|
if (MII->isBranch() && (FirstBranch == BBEnd))
|
|
FirstBranch = MII;
|
|
// If what we insert is a dual jump, we need to find
|
|
// first jump, and insert new instruction after it.
|
|
if (isDualJumpSecondCandidate && IsDualJumpFirstCandidate(&*MII))
|
|
DualJumpFirstCandidate = MII;
|
|
LastBundledInstruction = MII;
|
|
}
|
|
|
|
if (DualJumpFirstCandidate != BBEnd) {
|
|
// First respect dual jumps.
|
|
++DualJumpFirstCandidate;
|
|
if (DualJumpFirstCandidate == BBEnd ||
|
|
DualJumpFirstCandidate == LastBundledInstruction)
|
|
LastInBundle = true;
|
|
return DualJumpFirstCandidate;
|
|
} else if (FirstBranch != BBEnd) {
|
|
// If we have no dual jumps, but do have a single
|
|
// branch in the bundle, add our new instruction
|
|
// right before it.
|
|
return FirstBranch;
|
|
} else if (LastBundledInstruction != BBEnd) {
|
|
LastInBundle = true;
|
|
return ++LastBundledInstruction;
|
|
} else
|
|
llvm_unreachable("Lost in bundle");
|
|
return MBB->instr_begin();
|
|
}
|
|
|
|
/// This function for now needs to try to insert new instruction
|
|
/// in correct serial semantics fashion - i.e. find "correct" insert
|
|
/// point for instruction as if inserting in serial sequence.
|
|
MachineBasicBlock::instr_iterator HexagonGlobalSchedulerImpl::insertTempCopy(
|
|
MachineBasicBlock *MBB, MachineBasicBlock::iterator &TargetPacket,
|
|
MachineInstr *MI, bool DeleteOldCopy) {
|
|
MachineBasicBlock::instr_iterator MII;
|
|
MachineBasicBlock *CurrentBB = MI->getParent();
|
|
|
|
assert(CurrentBB && "Corrupt instruction");
|
|
// Create a temporary copy of the instruction we are considering.
|
|
// LLVM refuses to deal with an instruction which was not inserted
|
|
// to any BB. We can visit multiple BBs on the way "up", so we
|
|
// create a temp copy of the original instruction and delete it later.
|
|
// It is way cheaper than using splice and then
|
|
// needing to undo it most of the time.
|
|
MachineInstr *NewMI = MI->getParent()->getParent()->CloneMachineInstr(MI);
|
|
// Make sure all bundling flags are cleared.
|
|
if (NewMI->isBundledWithPred())
|
|
NewMI->unbundleFromPred();
|
|
if (NewMI->isBundledWithSucc())
|
|
NewMI->unbundleFromSucc();
|
|
|
|
if (DeleteOldCopy) {
|
|
// Remove our temporary instruction.
|
|
// MachineBasicBlock::erase method calls unbundleSingleMI()
|
|
// prior to deletion, so we do not have to do it here.
|
|
MachineBasicBlock::instr_iterator kill_it(MI);
|
|
CurrentBB->erase(kill_it);
|
|
}
|
|
|
|
// If the original instruction used new value operands,
|
|
// it might need to be changed to generic form
|
|
// before further processing.
|
|
if (QII->isDotNewInst(*NewMI))
|
|
DemoteToDotOld(NewMI);
|
|
|
|
// Insert new temporary instruction.
|
|
// If this is the destination packet, insert the tmp after
|
|
// its header. Otherwise, as second instr in BB.
|
|
if (TargetPacket->getParent() == MBB) {
|
|
MII = TargetPacket.getInstrIterator();
|
|
|
|
if (MII->isBundled()) {
|
|
bool LastInBundle = false;
|
|
MachineBasicBlock::instr_iterator InsertBefore =
|
|
findInsertPositionInBundle(TargetPacket, NewMI, LastInBundle);
|
|
MIBundleBuilder Bundle(&*TargetPacket);
|
|
Bundle.insert(InsertBefore, NewMI);
|
|
} else
|
|
MBB->insertAfter(MII, NewMI);
|
|
} else {
|
|
MII = MBB->instr_begin();
|
|
|
|
// Skip debug instructions.
|
|
while (MII->isDebugInstr())
|
|
MII++;
|
|
|
|
if (MII->isBundled()) {
|
|
MIBundleBuilder Bundle(&*MII);
|
|
Bundle.insert(++MII, NewMI);
|
|
} else
|
|
MBB->insertAfter(MII, NewMI);
|
|
}
|
|
return NewMI->getIterator();
|
|
}
|
|
|
|
// Check for a conditionally assigned register within the block.
|
|
bool HexagonGlobalSchedulerImpl::MIsCondAssign(MachineInstr *BMI,
|
|
MachineInstr *MI,
|
|
SmallVector<unsigned, 4> &Defs) {
|
|
if (!QII->isPredicated(*BMI))
|
|
return false;
|
|
// Its a conditional instruction, now is it the same registers as MI?
|
|
SmallVector<unsigned, 4> CondDefs;
|
|
SmallVector<unsigned, 8> CondUses;
|
|
parseOperands(BMI, CondDefs, CondUses);
|
|
|
|
for (SmallVector<unsigned, 4>::iterator ID = Defs.begin(), IDE = Defs.end();
|
|
ID != IDE; ++ID) {
|
|
for (SmallVector<unsigned, 4>::iterator CID = CondDefs.begin(),
|
|
CIDE = CondDefs.end();
|
|
CID != CIDE; ++CID) {
|
|
if (AliasingRegs(*CID, *ID)) {
|
|
LLVM_DEBUG(dbgs() << "\tFound conditional def, can't move\n";
|
|
BMI->dump());
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// Returns the Union of all the elements in Set1 and
|
|
// Union of all the elements in Set2 separately.
|
|
// Constraints:
|
|
// Set1 and Set2 should contain an entry for each element in Range.
|
|
template <typename ElemType, typename IndexType>
|
|
void Unify(std::vector<ElemType> Range,
|
|
std::map<ElemType, std::vector<IndexType>> &Set1,
|
|
std::map<ElemType, std::vector<IndexType>> &Set2,
|
|
std::pair<std::vector<IndexType>, std::vector<IndexType>> &UnionSet,
|
|
unsigned union_size = 100) {
|
|
typedef
|
|
typename std::map<ElemType, std::vector<IndexType>>::iterator PosIter_t;
|
|
typedef typename std::vector<IndexType>::iterator IndexIter_t;
|
|
std::vector<IndexType> &Union1 = UnionSet.first;
|
|
std::vector<IndexType> &Union2 = UnionSet.second;
|
|
Union1.resize(union_size, 0);
|
|
Union2.resize(union_size, 0);
|
|
LLVM_DEBUG(dbgs() << "\n\t\tElements in the range:\n";);
|
|
typename std::vector<ElemType>::iterator iter = Range.begin();
|
|
while (iter != Range.end()) {
|
|
if ((*iter)->isDebugInstr()) {
|
|
++iter;
|
|
continue;
|
|
}
|
|
LLVM_DEBUG((*iter)->dump());
|
|
PosIter_t set1_pos = Set1.find(*iter);
|
|
assert(set1_pos != Set1.end() &&
|
|
"Set1 should contain an entry for each element in Range.");
|
|
IndexIter_t set1idx = set1_pos->second.begin();
|
|
while (set1idx != set1_pos->second.end()) {
|
|
Union1[*set1idx] = 1;
|
|
++set1idx;
|
|
}
|
|
PosIter_t set2_pos = Set2.find(*iter);
|
|
assert(set2_pos != Set2.end() &&
|
|
"Set2 should contain an entry for each element in Range.");
|
|
IndexIter_t set2idx = set2_pos->second.begin();
|
|
while (set2idx != set2_pos->second.end()) {
|
|
Union2[*set2idx] = 1;
|
|
++set2idx;
|
|
}
|
|
++iter;
|
|
}
|
|
}
|
|
|
|
static void UpdateBundle(MachineInstr *BundleHead) {
|
|
assert(BundleHead->isBundle() && "Not a bundle header");
|
|
if (!BundleHead)
|
|
return;
|
|
unsigned Size = BundleHead->getBundleSize();
|
|
if (Size >= 2)
|
|
return;
|
|
if (Size == 1) {
|
|
MachineBasicBlock::instr_iterator MIter = BundleHead->getIterator();
|
|
MachineInstr *MI = &*(++MIter);
|
|
MI->unbundleFromPred();
|
|
}
|
|
BundleHead->eraseFromParent();
|
|
}
|
|
|
|
/// Gatekeeper for instruction speculation.
|
|
/// If all MI defs are dead (not live-in) to any other
|
|
/// BB but the one we are moving into, and it could not cause
|
|
/// exception by early execution, allow it to be pulled up.
|
|
bool HexagonGlobalSchedulerImpl::canMIBeSpeculated(
|
|
MachineInstr *MI, MachineBasicBlock *ToBB, MachineBasicBlock *FromBB,
|
|
std::vector<MachineInstr *> &backtrack) {
|
|
// For now disallow memory accesses from speculation.
|
|
// Generally we can check if they potentially may trap/cause an exception.
|
|
if (!EnableSpeculativePullUp || !MI || MI->mayStore())
|
|
return false;
|
|
|
|
LLVM_DEBUG(dbgs() << "\t[canMIBeSpeculated] From BB(" << FromBB->getNumber()
|
|
<< "):\t";
|
|
MI->dump());
|
|
LLVM_DEBUG(dbgs() << "\tTo this BB:\n"; ToBB->dump());
|
|
|
|
if (!ToBB->isSuccessor(FromBB))
|
|
return false;
|
|
|
|
// This is a very tricky topic. Speculating arithmetic instructions with
|
|
// results dead out of a loop more times then required by number of
|
|
// iterations is safe, while speculating loads can cause an exception.
|
|
// Simplest of checks is to not cross loop exit edge, or in our case
|
|
// do not pull-in to a loop exit BB, but there are implications for
|
|
// non-natural loops (not recognized by LLVM as loops) and multi-threaded
|
|
// code.
|
|
if (AllowSpeculateLoads && MI->mayLoad()) {
|
|
// Invariant loads should always be safe.
|
|
if (!MI->isDereferenceableInvariantLoad())
|
|
return false;
|
|
LLVM_DEBUG(dbgs() << "\tSpeculating a Load.\n");
|
|
}
|
|
|
|
SmallVector<unsigned, 4> Defs;
|
|
SmallVector<unsigned, 8> Uses;
|
|
parseOperands(MI, Defs, Uses);
|
|
|
|
// Do not speculate instructions that modify reserved global registers.
|
|
for (unsigned R : Defs)
|
|
if (MRI->isReserved(R) && QRI->isGlobalReg(R))
|
|
return false;
|
|
|
|
for (MachineBasicBlock::const_succ_iterator SI = ToBB->succ_begin(),
|
|
SE = ToBB->succ_end();
|
|
SI != SE; ++SI) {
|
|
// TODO: Allow an instruction (I) which 'defines' the live-in reg (R)
|
|
// along the path when I is the first instruction to use the R.
|
|
// i.e., I kills R before any other instruction in the BB uses it.
|
|
// TODO: We have already parsed live sets - reuse them.
|
|
if (*SI == FromBB)
|
|
continue;
|
|
LLVM_DEBUG(dbgs() << "\tTarget succesor BB to check:\n"; (*SI)->dump());
|
|
LLVM_DEBUG(
|
|
for (MachineBasicBlock::const_succ_iterator SII = (*SI)->succ_begin(),
|
|
SIE = (*SI)->succ_end();
|
|
SII != SIE; ++SII)(*SII)
|
|
->dump());
|
|
for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
|
|
E = (*SI)->livein_end();
|
|
I != E; ++I)
|
|
for (SmallVector<unsigned, 4>::iterator ID = Defs.begin(),
|
|
IDE = Defs.end();
|
|
ID != IDE; ++ID) {
|
|
if (AliasingRegs((*I).PhysReg, *ID))
|
|
return false;
|
|
}
|
|
|
|
// Check the successor blocks for conditional define.
|
|
// TODO: We should really test the whole path here.
|
|
for (MachineBasicBlock::instr_iterator BI = (*SI)->instr_begin(),
|
|
E = (*SI)->instr_end();
|
|
BI != E; ++BI) {
|
|
if (BI->isBundle() || BI->isDebugInstr())
|
|
continue;
|
|
LLVM_DEBUG(dbgs() << "\t\tcheck against:\t"; BI->dump());
|
|
if (MIsCondAssign(&*BI, MI, Defs))
|
|
return false;
|
|
}
|
|
}
|
|
// Taking a very conservative approach during speculation.
|
|
// Traverse the path (FromBB, ToBB] and make sure
|
|
// that the def-use set of the instruction to be moved
|
|
// are not modified.
|
|
std::vector<MachineBasicBlock *> PathBB;
|
|
for (unsigned i = 0; i < backtrack.size(); ++i) {
|
|
// Insert unique BB along the path but skip FromBB
|
|
MachineBasicBlock *MBB = backtrack[i]->getParent();
|
|
if ((MBB != FromBB) &&
|
|
(std::find(PathBB.begin(), PathBB.end(), MBB) == PathBB.end()))
|
|
PathBB.push_back(MBB);
|
|
}
|
|
bool WaitingForTargetPacket = true;
|
|
MachineBasicBlock::instr_iterator MII;
|
|
std::vector<MachineInstr *> TraversalRange;
|
|
LLVM_DEBUG(dbgs() << "\n\tElements in the range:");
|
|
// TODO: Use just the backtrack to get TraversalRange because it
|
|
// contains the path (only when speculated from a path in region).
|
|
// Note: We check the dependency of instruction-to-move with
|
|
// all the instructions (starting from backtrack[0]) in the parent BBs
|
|
// because a BB might have a branching from in between due to packetization
|
|
// and just checking packets in the backtrack won't be comprehensive.
|
|
for (unsigned i = 0; i < PathBB.size(); ++i) {
|
|
for (MII = PathBB[i]->instr_begin(); MII != PathBB[i]->instr_end(); ++MII) {
|
|
// Skip instructions until the target packet is found.
|
|
// although target packet is already checked for correctness,
|
|
// it is good to check here to validate intermediate pullups.
|
|
if (backtrack[0] == &*MII)
|
|
WaitingForTargetPacket = false;
|
|
if (WaitingForTargetPacket)
|
|
continue;
|
|
if (MII->isBundle())
|
|
continue;
|
|
// TODO: Ideally we should check that there is a `linear' control flow
|
|
// in the TraversalRange in all possible manner. For e.g.,
|
|
// BB0 { packet1: if(p0) indirect_jump BB1;
|
|
// packet2: jump BB2 }
|
|
// BB1 { i1 }. In this case we should not pull `i1' into packet2.
|
|
if (MII->isCall() || MII->isReturn() ||
|
|
(MII->getOpcode() == Hexagon::J2_jump && !MII->getOperand(0).isMBB()))
|
|
return false;
|
|
if (MI != &*MII) {
|
|
TraversalRange.push_back(&*MII);
|
|
LLVM_DEBUG(MII->dump(););
|
|
}
|
|
}
|
|
}
|
|
// Get the union of def/use set of all the instructions along TraversalRange.
|
|
std::pair<std::vector<unsigned>, std::vector<unsigned>> RangeDefUse;
|
|
Unify(TraversalRange, MIDefSet, MIUseSet, RangeDefUse, QRI->getNumRegs());
|
|
// No instruction (along TraversalRange) should 'define' the use set of MI
|
|
for (unsigned j = 0; j < Uses.size(); ++j)
|
|
if (RangeDefUse.first[Uses[j]]) {
|
|
LLVM_DEBUG(dbgs() << "\n\t\tUnresolved dependency along path to HOME for "
|
|
<< printReg(Uses[j], QRI););
|
|
return false;
|
|
}
|
|
// No instruction (along TraversalRange) should 'define' or 'use'
|
|
// the def set of MI
|
|
for (unsigned j = 0; j < Defs.size(); ++j)
|
|
if (RangeDefUse.first[Defs[j]] || RangeDefUse.second[Defs[j]]) {
|
|
LLVM_DEBUG(dbgs() << "\n\t\tUnresolved dependency along path to HOME for "
|
|
<< printReg(Defs[j], QRI););
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Try to move InstrToMove to TargetPacket using path stored in backtrack.
|
|
/// SourceLocation is current iterator point. It must be updated to the new
|
|
/// iteration location after all updates.
|
|
/// Alogrithm:
|
|
/// To move an instruction (I) from OriginBB through HomeBB via backtrack.
|
|
/// for each packet (i) in backtrack, analyzeBranch
|
|
/// case 1 (success)
|
|
/// case Pulling from conditional branch:
|
|
/// if I is predicable
|
|
/// Try to predicate on the branch condition
|
|
/// else
|
|
/// Try to speculate I to backtrack[i].
|
|
/// case Pulling from unconditional branch:
|
|
/// Just pullup. (TODO: Speculate here as well)
|
|
/// case 2 (fails)
|
|
/// Try to speculate I backtrack[i].
|
|
bool HexagonGlobalSchedulerImpl::MoveMItoBundle(
|
|
BasicBlockRegion *CurrentRegion,
|
|
MachineBasicBlock::instr_iterator &InstrToMove,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
MachineBasicBlock::iterator &TargetPacket,
|
|
MachineBasicBlock::iterator &SourceLocation,
|
|
std::vector<MachineInstr *> &backtrack, bool MovingDependentOp,
|
|
bool PathInRegion) {
|
|
MachineBasicBlock *HomeBB = TargetPacket->getParent();
|
|
MachineBasicBlock *OriginBB = InstrToMove->getParent();
|
|
MachineBasicBlock *CurrentBB = OriginBB;
|
|
MachineBasicBlock *CleanupBB = OriginBB;
|
|
MachineBasicBlock *PreviousBB = OriginBB;
|
|
MachineInstr *OriginalInstructionToMove = &*InstrToMove;
|
|
|
|
assert(HomeBB && "Missing HomeBB");
|
|
assert(OriginBB && "Missing OriginBB");
|
|
|
|
LLVM_DEBUG(dbgs() << "\n.........[MoveMItoBundle]..............\n");
|
|
LLVM_DEBUG(dbgs() << "\t\tInstrToMove :\t"; InstrToMove->dump());
|
|
LLVM_DEBUG(dbgs() << "\t\tTargetPacket :\t";
|
|
DumpPacket(TargetPacket.getInstrIterator()));
|
|
LLVM_DEBUG(dbgs() << "\t\tSourceLocation:\t";
|
|
DumpPacket(SourceLocation.getInstrIterator()));
|
|
|
|
// We do not allow to move instructions in the same BB.
|
|
if (HomeBB == OriginBB) {
|
|
LLVM_DEBUG(dbgs() << "\t\tSame BB pull-up.\n");
|
|
if (!EnableLocalPullUp)
|
|
return false;
|
|
}
|
|
|
|
if (OneFloatPerPacket && QII->isFloat(*TargetPacket) &&
|
|
QII->isFloat(*InstrToMove))
|
|
return false;
|
|
|
|
if (OneComplexPerPacket && QII->isComplex(*TargetPacket) &&
|
|
QII->isComplex(*InstrToMove))
|
|
return false;
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\tWay home:\n");
|
|
// Test integrity of the back track.
|
|
for (unsigned i = 0; i < backtrack.size(); ++i) {
|
|
assert(backtrack[i]->getParent() && "Messed back track.");
|
|
LLVM_DEBUG(dbgs() << "\t\t[" << i << "] BB("
|
|
<< backtrack[i]->getParent()->getNumber() << ")\t";
|
|
backtrack[i]->dump());
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\n");
|
|
|
|
bool NeedCleanup = false;
|
|
bool NeedToPredicate = false;
|
|
bool MINeedToNewify = false;
|
|
unsigned DepReg = std::numeric_limits<unsigned>::max();
|
|
bool isDualJump = false;
|
|
SmallVector<MachineOperand, 4> Cond;
|
|
SmallVector<MachineOperand, 4> PredCond;
|
|
std::vector<MachineInstr *> PullUpPath;
|
|
if (PathInRegion)
|
|
PullUpPath = backtrack;
|
|
else {
|
|
PullUpPath.push_back(&*TargetPacket);
|
|
PullUpPath.push_back(&*InstrToMove);
|
|
}
|
|
|
|
// Now start iterating over all instructions
|
|
// preceeding the one we are trying to move,
|
|
// and see if they could be reodered/bypassed.
|
|
for (std::vector<MachineInstr *>::reverse_iterator RI = backtrack.rbegin(),
|
|
RIE = backtrack.rend();
|
|
RI < RIE; ++RI) {
|
|
// Once most of debug will be gone, this will be a real assert.
|
|
// assert((backtrack.front() == ToThisBundle) && "Lost my way home.");
|
|
MachineInstr *MIWH = *RI;
|
|
if (QII->isDotNewInst(*InstrToMove)) {
|
|
LLVM_DEBUG(dbgs() << "Cannot move a dot new instruction:";
|
|
InstrToMove->dump());
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
if (canCauseStall(&*InstrToMove, MIWH)) {
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\t> Step home BB(" << MIWH->getParent()->getNumber()
|
|
<< "):\t";
|
|
DumpPacket(MIWH->getIterator()));
|
|
|
|
// See if we cross a jump, and possibly change the form of instruction.
|
|
// Passing through BBs with dual jumps in different packets
|
|
// takes extra care.
|
|
bool isBranchMIWH = isBranch(MIWH);
|
|
if (((&*SourceLocation != MIWH) && isBranchMIWH) ||
|
|
(CurrentBB != MIWH->getParent())) {
|
|
LLVM_DEBUG(dbgs() << "\tChange BB from(" << CurrentBB->getNumber()
|
|
<< ") to (" << MIWH->getParent()->getNumber() << ")\n");
|
|
PreviousBB = CurrentBB;
|
|
CurrentBB = MIWH->getParent();
|
|
|
|
// See what kind of branch we are dealing with.
|
|
MachineBasicBlock *PredTBB = NULL;
|
|
MachineBasicBlock *PredFBB = NULL;
|
|
|
|
if (QII->analyzeBranch(*CurrentBB, PredTBB, PredFBB, Cond, false)) {
|
|
// We currently do not handle NV jumps of this kind:
|
|
// if (cmp.eq(r0.new, #0)) jump:t .LBB12_69
|
|
// TODO: Need to handle them.
|
|
LLVM_DEBUG(dbgs() << "\tCould not analyze branch.\n");
|
|
|
|
// This is the main point of lost performance.
|
|
// We could try to speculate here, but for that we need accurate
|
|
// liveness info, and it is not ready yet.
|
|
if (!canMIBeSpeculated(&*InstrToMove, CurrentBB, PreviousBB,
|
|
PullUpPath)) {
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
} else {
|
|
// Save speculated instruction moved.
|
|
SpeculatedIns.insert(
|
|
std::make_pair(OriginalInstructionToMove, OriginBB));
|
|
LLVM_DEBUG(dbgs() << "\nSpeculatedInsToMove"; InstrToMove->dump());
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "\tSpeculating.\n");
|
|
// If we are speculating, we can come through a predication
|
|
// into an unconditional branch...
|
|
// For now simply bail out.
|
|
// TODO: See if this ever happens.
|
|
if (NeedToPredicate) {
|
|
LLVM_DEBUG(dbgs()
|
|
<< "\tUnderimplemented pred for speculative move.\n");
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
InstrToMove =
|
|
insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove, NeedCleanup);
|
|
NeedCleanup = true;
|
|
NeedToPredicate = false;
|
|
assert(!NeedToPredicate && "Need to handle predication for this case");
|
|
CleanupBB = CurrentBB;
|
|
// No need to recheck for resources - instruction did not change.
|
|
LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
|
|
} else {
|
|
bool LocalNeedPredication = true;
|
|
// We were able to analyze the branch.
|
|
if (!isBranchMIWH && !PredTBB) {
|
|
LLVM_DEBUG(dbgs() << "\tDo not need predicate for this case.\n");
|
|
LocalNeedPredication = false;
|
|
}
|
|
// First see if this is a potential dual jump situation.
|
|
if (IsDualJumpSecondCandidate(&*InstrToMove) &&
|
|
IsDualJumpFirstCandidate(TargetPacket)) {
|
|
LLVM_DEBUG(dbgs() << "\tPerforming unrestricted dual jump.\n");
|
|
isDualJump = true;
|
|
} else if (LocalNeedPredication && (PredFBB != PreviousBB)) {
|
|
// Predicate instruction based on condition feeding it.
|
|
// This is generally a statefull pull-up path.
|
|
// Can this insn be predicated? If so, try to do it.
|
|
if (TII->isPredicable(*InstrToMove)) {
|
|
if (PredTBB) {
|
|
if (PreviousBB != PredTBB) {
|
|
// If we "came" not from TBB, we need to invert condition.
|
|
if (TII->reverseBranchCondition(Cond)) {
|
|
LLVM_DEBUG(dbgs() << "\tUnable to invert condition.\n");
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\tTBB(" << PredTBB->getNumber()
|
|
<< ")InvertCondition("
|
|
<< (PreviousBB != PredTBB) << ")\n");
|
|
}
|
|
// Create a new copy of the instruction we are trying to move.
|
|
// It changes enough (new BB, predicated form) and untill we
|
|
// reach home, we do not even know if it is going to work.
|
|
InstrToMove = insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove,
|
|
NeedCleanup);
|
|
NeedCleanup = true;
|
|
NeedToPredicate = true;
|
|
CleanupBB = CurrentBB;
|
|
|
|
if (PredCond.empty() && // If not already predicated.
|
|
TII->PredicateInstruction(*InstrToMove, Cond)) {
|
|
LLVM_DEBUG(dbgs() << "\tNew predicated insn:\t";
|
|
InstrToMove->dump());
|
|
// After predication some instruction could become const extended:
|
|
// L2_loadrigp == "$dst=memw(#$global)"
|
|
// L4_ploadrit_abs == "if ($src1) $dst=memw(##$global)"
|
|
// Resource checking for those is different.
|
|
if ((QII->isExtended(*InstrToMove) ||
|
|
QII->isConstExtended(*InstrToMove) ||
|
|
isJumpOutOfRange(&*InstrToMove)) &&
|
|
!tryAllocateResourcesForConstExt(&*InstrToMove, false)) {
|
|
// If we cannot, do not modify the state.
|
|
LLVM_DEBUG(dbgs()
|
|
<< "\tEI Could not be added to the packet.\n");
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
|
|
if (!ResourceTracker->canReserveResources(*InstrToMove) ||
|
|
!shouldAddToPacket(*InstrToMove)) {
|
|
// It will not fit in its new form...
|
|
LLVM_DEBUG(dbgs() << "\tCould not be added in its new form.\n");
|
|
CurrentBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
|
|
// Need also verify that we can newify it if we want to.
|
|
if (NeedToNewify(InstrToMove, &DepReg, &*TargetPacket)) {
|
|
if (isNewifiable(InstrToMove, DepReg, &*TargetPacket)) {
|
|
MINeedToNewify = true;
|
|
LLVM_DEBUG(dbgs() << "\t\t\tNeeds to NEWify on Reg("
|
|
<< printReg(DepReg, QRI) << ").\n");
|
|
} else {
|
|
LLVM_DEBUG(dbgs() << "\tNon newifiable in this bundle: ";
|
|
InstrToMove->dump());
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
|
|
PredCond = Cond;
|
|
// Now the instruction uses the pred-reg as well.
|
|
if (!Cond.empty() && (Cond.size() == 2)) {
|
|
MIUseSet[OriginalInstructionToMove].push_back(Cond[1].getReg());
|
|
}
|
|
assert(((Cond.size() <= 2) &&
|
|
!(QII->isNewValueJump(Cond[0].getImm()))) &&
|
|
"Update MIUseSet for new-value compare jumps");
|
|
} else {
|
|
LLVM_DEBUG(dbgs() << "\tCould not predicate it\n");
|
|
LLVM_DEBUG(dbgs() << "\tTrying to speculate!\t";
|
|
InstrToMove->dump());
|
|
bool DistantSpeculation = false;
|
|
std::vector<MachineInstr *> NonPredPullUpPath;
|
|
unsigned btidx = 0;
|
|
// Generate a backtrack path for instruction to be speculated.
|
|
// Original backtrack may start from a different (ancestor)
|
|
// target packet.
|
|
while (btidx < backtrack.size()) {
|
|
const MachineBasicBlock *btBB = backtrack[btidx]->getParent();
|
|
if ((btBB == PreviousBB) || (btBB == CurrentBB))
|
|
NonPredPullUpPath.push_back(backtrack[btidx]);
|
|
++btidx;
|
|
}
|
|
// Speculate only to immediate predecessor.
|
|
if (PreviousBB != CurrentBB) {
|
|
if (*(PreviousBB->pred_begin()) != CurrentBB) {
|
|
// In a region there are no side entries.
|
|
DistantSpeculation = true;
|
|
LLVM_DEBUG(dbgs()
|
|
<< "\n\tMI not in immediate successor of BB#"
|
|
<< CurrentBB->getNumber() << ", MI is in BB#"
|
|
<< PreviousBB->getNumber(););
|
|
}
|
|
assert((PreviousBB->pred_size() < 2) &&
|
|
"Region with a side entry");
|
|
}
|
|
// TODO: Speculate ins. when pulled from unlikely path.
|
|
if (DistantSpeculation || /*!PathInRegion ||*/
|
|
InstrToMove->mayLoad() || InstrToMove->mayStore() ||
|
|
InstrToMove->hasUnmodeledSideEffects() ||
|
|
!canMIBeSpeculated(&*InstrToMove, CurrentBB, PreviousBB,
|
|
NonPredPullUpPath)) {
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
} else {
|
|
// Save speculated instruction moved.
|
|
NeedToPredicate = false;
|
|
SpeculatedIns.insert(
|
|
std::make_pair(OriginalInstructionToMove, OriginBB));
|
|
LLVM_DEBUG(dbgs() << "\nPredicable+SpeculatedInsToMove";
|
|
InstrToMove->dump());
|
|
}
|
|
}
|
|
} else {
|
|
// This is a non-predicable instruction. We still can try to
|
|
// speculate it here.
|
|
LLVM_DEBUG(dbgs() << "\tNon predicable insn!\t";
|
|
InstrToMove->dump());
|
|
// TODO: Speculate ins. when pulled from unlikely path.
|
|
if (!SpeculateNonPredInsn || !PathInRegion ||
|
|
InstrToMove->mayLoad() || InstrToMove->mayStore() ||
|
|
InstrToMove->hasUnmodeledSideEffects() ||
|
|
!canMIBeSpeculated(&*InstrToMove, CurrentBB, PreviousBB,
|
|
PullUpPath)) {
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
} else {
|
|
// Save speculated instruction moved.
|
|
SpeculatedIns.insert(
|
|
std::make_pair(OriginalInstructionToMove, OriginBB));
|
|
LLVM_DEBUG(dbgs() << "\nNonPredicable+SpeculatedInsToMove";
|
|
InstrToMove->dump());
|
|
}
|
|
|
|
InstrToMove = insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove,
|
|
NeedCleanup);
|
|
NeedCleanup = true;
|
|
CleanupBB = CurrentBB;
|
|
}
|
|
} else {
|
|
// No branch. Fall through.
|
|
LLVM_DEBUG(dbgs() << "\tFall through BB.\n"
|
|
<< "\tCurrentBB:" << CurrentBB->getNumber()
|
|
<< "\tPreviousBB:" << PreviousBB->getNumber();
|
|
if (PredFBB) dbgs()
|
|
<< "\tPredFBB:" << PredFBB->getNumber(););
|
|
// Even though this is a fall though case, we still can
|
|
// have a dual jump situation here with a CALL involved.
|
|
// For now simply avoid it.
|
|
if (IsDualJumpSecondCandidate(&*InstrToMove)) {
|
|
llvm_unreachable("Dual jumps with known?");
|
|
LLVM_DEBUG(dbgs() << "\tUnderimplemented dual jump formation.\n");
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
|
|
if (!CurrentBB->isSuccessor(PreviousBB)) {
|
|
LLVM_DEBUG(dbgs() << "\tNon-successor fall through.\n");
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
SpeculatedIns.insert(
|
|
std::make_pair(OriginalInstructionToMove, OriginBB));
|
|
LLVM_DEBUG(dbgs() << "\nSpeculatedInsToMove+FallThroughBB";
|
|
InstrToMove->dump());
|
|
// Create a temp copy.
|
|
InstrToMove = insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove,
|
|
NeedCleanup);
|
|
NeedCleanup = true;
|
|
NeedToPredicate = false;
|
|
CleanupBB = CurrentBB;
|
|
LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
|
|
}
|
|
}
|
|
}
|
|
// If we have reached Home, great.
|
|
// Original check should have verified that instruction could be added
|
|
// to the target packet, so here we do nothing for deps.
|
|
if (MIWH == backtrack.front()) {
|
|
LLVM_DEBUG(dbgs() << "\tHOME!\n");
|
|
break;
|
|
}
|
|
|
|
// Test if we can reorder the two MIs.
|
|
// The exception is when we are forming dual jumps - we can pull up
|
|
// dependent instruction to the last bundle of an immediate predecesor
|
|
// of the current BB if control flow permits it.
|
|
// In this special case we also need to update the bundle we are moving
|
|
// from.
|
|
if (!(MovingDependentOp && (MIWH == &*SourceLocation)) &&
|
|
!canReorderMIs(MIWH, &*InstrToMove)) {
|
|
if (NeedCleanup)
|
|
CleanupBB->erase(InstrToMove);
|
|
return false;
|
|
}
|
|
}
|
|
// We have previously tested this instruction, but has not updated the state
|
|
// for it. Do it now.
|
|
if (QII->isExtended(*InstrToMove) || QII->isConstExtended(*InstrToMove) ||
|
|
isJumpOutOfRange(&*InstrToMove)) {
|
|
if (!tryAllocateResourcesForConstExt(&*InstrToMove))
|
|
llvm_unreachable("Missed dependency test");
|
|
}
|
|
|
|
// Ok. We can safely move this instruction all the way up.
|
|
// We also potentially have a slot for it.
|
|
// During move original instruction could have changed (becoming predicated).
|
|
// Now try to place the final instance of it into the current packet.
|
|
LLVM_DEBUG(dbgs() << "\nWant to move ";
|
|
if (MovingDependentOp) dbgs() << "dependent op"; dbgs() << ": ";
|
|
InstrToMove->dump(); dbgs() << "To BB:\n"; HomeBB->dump();
|
|
dbgs() << "From BB:\n"; OriginBB->dump());
|
|
|
|
// Keep these two statistics separately.
|
|
if (!isDualJump)
|
|
HexagonNumPullUps++;
|
|
else
|
|
HexagonNumDualJumps++;
|
|
|
|
// This means we have not yet inserted the temp copy of InstrToMove
|
|
// in the target bundle. We are probably inside the same BB.
|
|
if (!NeedCleanup) {
|
|
InstrToMove =
|
|
insertTempCopy(HomeBB, TargetPacket, &*InstrToMove, NeedCleanup);
|
|
NeedCleanup = true;
|
|
}
|
|
|
|
// No problems detected. Add it.
|
|
// If we were adding InstrToMove to a single, not yet packetized
|
|
// instruction, we need to create bundle header for it before proceeding.
|
|
// Be carefull since endPacket also resets the DFA state.
|
|
if (!TargetPacket->isBundle()) {
|
|
LLVM_DEBUG(dbgs() << "\tForm a new bundle.\n");
|
|
finalizeBundle(*HomeBB, TargetPacket.getInstrIterator(),
|
|
std::next(InstrToMove));
|
|
LLVM_DEBUG(HomeBB->dump());
|
|
// Now we need to adjust pointer to the newly created packet header.
|
|
MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
|
|
MII--;
|
|
|
|
// Is it also on the way home?
|
|
for (unsigned i = 0; i < backtrack.size(); ++i)
|
|
if (backtrack[i] == &*TargetPacket)
|
|
backtrack[i] = &*MII;
|
|
|
|
// Is it where our next MI is pointing?
|
|
if (NextMI == TargetPacket)
|
|
NextMI = MII;
|
|
TargetPacket = MII;
|
|
}
|
|
|
|
// Move and Update Liveness info.
|
|
MoveAndUpdateLiveness(CurrentRegion, HomeBB, &*InstrToMove, MINeedToNewify,
|
|
DepReg, MovingDependentOp, OriginBB,
|
|
OriginalInstructionToMove, PredCond, SourceLocation,
|
|
TargetPacket, NextMI, backtrack);
|
|
|
|
LLVM_DEBUG(dbgs() << "\n______Updated______\n"; HomeBB->dump();
|
|
OriginBB->dump());
|
|
|
|
return true;
|
|
}
|
|
|
|
/// Verify that we respect CFG layout during pull-up.
|
|
bool HexagonGlobalSchedulerImpl::isBranchWithinRegion(
|
|
BasicBlockRegion *CurrentRegion, MachineInstr *MI) {
|
|
assert(MI && MI->isBranch() && "Missing call info");
|
|
|
|
MachineBasicBlock *MBB = MI->getParent();
|
|
LLVM_DEBUG(dbgs() << "\t[isBranchWithinRegion] BB(" << MBB->getNumber()
|
|
<< ") Branch instr:\t";
|
|
MI->dump());
|
|
// If there is only one successor, it is safe to pull.
|
|
if (MBB->succ_size() <= 1)
|
|
return true;
|
|
// If there are multiple successors (jump table), we should
|
|
// not allow pull up over this instruction.
|
|
if (MBB->succ_size() > 2)
|
|
return false;
|
|
|
|
MachineBasicBlock *NextRegionBB;
|
|
MachineBasicBlock *TBB, *FBB;
|
|
MachineInstr *FirstTerm = NULL;
|
|
MachineInstr *SecondTerm = NULL;
|
|
|
|
if (AnalyzeBBBranches(MBB, TBB, FirstTerm, FBB, SecondTerm)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tAnalyzeBBBranches failed!\n");
|
|
return false;
|
|
}
|
|
|
|
// If there is no jump in this BB, it simply falls through.
|
|
if (!FirstTerm) {
|
|
LLVM_DEBUG(dbgs() << "\t\tNo FirstTerm\n");
|
|
return true;
|
|
} else if (QII->isEndLoopN(FirstTerm->getOpcode())) {
|
|
// We can easily analyze where endloop would take us
|
|
// but here it would be pointless either way since
|
|
// the region will not cross it.
|
|
LLVM_DEBUG(dbgs() << "\t\tEndloop terminator\n");
|
|
return false;
|
|
}
|
|
// On some occasions we see code like this:
|
|
// BB#142: derived from LLVM BB %init, Align 4 (16 bytes)
|
|
// Live Ins: %R17 %R18
|
|
// Predecessors according to CFG: BB#2
|
|
// EH_LABEL <MCSym=.Ltmp35>
|
|
// J2_jump <BB#3>, %PC<imp-def>
|
|
// Successors according to CFG: BB#3(1048575) BB#138(1)
|
|
// It breaks most assumptions about CFG layout, so untill we know
|
|
// the source of it, let's have a safeguard.
|
|
if (MBB->succ_size() > 1 && !TII->isPredicated(*FirstTerm) &&
|
|
!QII->isNewValueJump(*FirstTerm)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tBadly formed BB.\n");
|
|
return false;
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "\t\tFirstTerm: "; FirstTerm->dump());
|
|
LLVM_DEBUG(dbgs() << "\t\tSecondTerm: "; if (SecondTerm) SecondTerm->dump();
|
|
else dbgs() << "None\n";);
|
|
|
|
// All cases where there is only one branch in BB are OK to proceed.
|
|
if (!SecondTerm)
|
|
return true;
|
|
|
|
assert(!QII->isEndLoopN(SecondTerm->getOpcode()) && "Found endloop.");
|
|
|
|
// Find next BB in this region - if there is none, we will likely
|
|
// stop pulling in the next check outside of this function.
|
|
// This largely is don't care.
|
|
NextRegionBB = CurrentRegion->findNextMBB(MBB);
|
|
if (!NextRegionBB) {
|
|
LLVM_DEBUG(dbgs() << "\t\tNo next BB in the region...\n");
|
|
return true;
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\t\tNextRegionBB(" << NextRegionBB->getNumber()
|
|
<< ")\n");
|
|
assert(TBB && "Corrupt BB layout");
|
|
// This means we are trying to pull into a packet _before_ the first
|
|
// branch in the MBB.
|
|
if (MI == FirstTerm) {
|
|
LLVM_DEBUG(dbgs() << "\t\tTBB(" << TBB->getNumber()
|
|
<< ") NextBB in the region(" << NextRegionBB->getNumber()
|
|
<< ")\n");
|
|
return (TBB == NextRegionBB);
|
|
}
|
|
assert(FBB && "Corrupt BB layout");
|
|
// This means we are trying to pull into the packet _after_ first branch,
|
|
// and it is OK if we pull from the second branch target.
|
|
// This pull is always speculative.
|
|
if ((MI != SecondTerm)) {
|
|
LLVM_DEBUG(dbgs() << "\t\tDual terminator not matching SecondTerm.\n");
|
|
return false;
|
|
}
|
|
// Analyze the second branch in the BB.
|
|
LLVM_DEBUG(dbgs() << "\t\tFBB(" << FBB->getNumber()
|
|
<< ") NextBB in the region(" << NextRegionBB->getNumber()
|
|
<< ")\n");
|
|
return (FBB == NextRegionBB);
|
|
}
|
|
|
|
/// Check if a given instruction is:
|
|
/// - a jump to a distant target
|
|
/// - that exceeds its immediate range
|
|
/// If both conditions are true, it requires constant extension.
|
|
bool HexagonGlobalSchedulerImpl::isJumpOutOfRange(MachineInstr *UnCond,
|
|
MachineInstr *Cond) {
|
|
if (!UnCond || !UnCond->isBranch())
|
|
return false;
|
|
|
|
MachineBasicBlock *UnCondBB = UnCond->getParent();
|
|
MachineBasicBlock *CondBB = Cond->getParent();
|
|
MachineInstr *FirstTerm = &*(CondBB->getFirstInstrTerminator());
|
|
// This might be worth an assert.
|
|
if (FirstTerm == &*CondBB->instr_end())
|
|
return false;
|
|
|
|
unsigned InstOffset = BlockToInstOffset[UnCondBB];
|
|
unsigned Distance = 0;
|
|
|
|
// To save time, estimate exact position of a branch instruction
|
|
// as one at the end of the UnCondBB.
|
|
// Number of instructions times typical instruction size.
|
|
InstOffset += (QII->nonDbgBBSize(UnCondBB) * HEXAGON_INSTR_SIZE);
|
|
|
|
MachineBasicBlock *TBB = NULL, *FBB = NULL;
|
|
SmallVector<MachineOperand, 4> CondList;
|
|
|
|
// Find the target of the unconditional branch in UnCondBB, which is returned
|
|
// in TBB. Then use the CondBB to extract the FirsTerm. We desire to replace
|
|
// the branch target in FirstTerm with the branch location from the UnCondBB,
|
|
// provided it is within the distance of the opcode in FirstTerm.
|
|
if (QII->analyzeBranch(*UnCondBB, TBB, FBB, CondList, false))
|
|
// Could not analyze it. give up.
|
|
return false;
|
|
|
|
if (TBB && (Cond == FirstTerm)) {
|
|
Distance =
|
|
(unsigned)std::abs((long long)InstOffset - BlockToInstOffset[TBB]) +
|
|
SafetyBuffer;
|
|
return !QII->isJumpWithinBranchRange(*FirstTerm, Distance);
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// findBundleAndBranch returns the branch instruction and the
|
|
// bundle which contains it. Null is returned if not found.
|
|
MachineInstr *HexagonGlobalSchedulerImpl::findBundleAndBranch(
|
|
MachineBasicBlock *BB, MachineBasicBlock::iterator &Bundle) {
|
|
// Find the conditional branch out of BB.
|
|
if (!BB)
|
|
return NULL;
|
|
MachineInstr *CondBranch = NULL;
|
|
Bundle = BB->end();
|
|
for (MachineBasicBlock::instr_iterator MII = BB->getFirstInstrTerminator(),
|
|
MBBEnd = BB->instr_end();
|
|
MII != MBBEnd; ++MII) {
|
|
MachineInstr *MI = &*MII;
|
|
if (MII->isConditionalBranch()) {
|
|
CondBranch = MI;
|
|
}
|
|
}
|
|
if (!CondBranch)
|
|
return NULL;
|
|
MachineBasicBlock::instr_iterator MII = CondBranch->getIterator();
|
|
if (!MII->isBundled())
|
|
return NULL;
|
|
// Find bundle header.
|
|
for (--MII; MII->isBundled(); --MII)
|
|
if (MII->isBundle()) {
|
|
Bundle = MII;
|
|
break;
|
|
}
|
|
return CondBranch;
|
|
}
|
|
|
|
// pullUpPeelBBLoop
|
|
// A single BB loop with a register copy at the beginning in its
|
|
// own bundle, benefits from eliminating the extra bundle. We do
|
|
// this by predicating the register copy in the predecessor BB, and
|
|
// again in the last bundle of the loop.
|
|
bool HexagonGlobalSchedulerImpl::pullUpPeelBBLoop(MachineBasicBlock *PredBB,
|
|
MachineBasicBlock *LoopBB) {
|
|
if (!AllowBBPeelPullUp)
|
|
return false;
|
|
if (!LoopBB || !PredBB)
|
|
return false;
|
|
|
|
// We consider single BB loops only. Check for it here.
|
|
if (LoopBB->isEHPad() || LoopBB->hasAddressTaken())
|
|
return false;
|
|
if (LoopBB->succ_size() != 2)
|
|
return false;
|
|
if (LoopBB->pred_size() != 2)
|
|
return false;
|
|
// Make sure one of the successors and one of the predecssors is to self.
|
|
if (!(LoopBB->isSuccessor(LoopBB) && LoopBB->isPredecessor(LoopBB)))
|
|
return false;
|
|
|
|
// Find the none self successor block. We know we only have 2 successors.
|
|
MachineBasicBlock *SuccBB = NULL;
|
|
for (MachineBasicBlock::succ_iterator SI = LoopBB->succ_begin(),
|
|
SE = LoopBB->succ_end();
|
|
SI != SE; ++SI)
|
|
if (*SI != LoopBB) {
|
|
SuccBB = *SI;
|
|
break;
|
|
}
|
|
if (!SuccBB)
|
|
return false;
|
|
|
|
// Find the conditional branch and its bundle inside PredBB.
|
|
MachineBasicBlock::iterator PredBundle;
|
|
MachineInstr *PredCondBranch = NULL;
|
|
PredCondBranch = findBundleAndBranch(PredBB, PredBundle);
|
|
if (!PredCondBranch)
|
|
return false;
|
|
if (PredBundle == PredBB->end())
|
|
return false;
|
|
LLVM_DEBUG(dbgs() << "PredBB's Branch: ");
|
|
LLVM_DEBUG(dbgs() << *PredCondBranch);
|
|
|
|
// Look for leading reg copy as single bundle and make sure its live in.
|
|
MachineBasicBlock::instr_iterator FMI = LoopBB->instr_begin();
|
|
// Skip debug instructions.
|
|
while (FMI->isDebugInstr())
|
|
FMI++;
|
|
|
|
MachineInstr *RegMI = &*FMI;
|
|
if (RegMI->isBundle())
|
|
return false;
|
|
int TfrOpcode = RegMI->getOpcode();
|
|
if (TfrOpcode != Hexagon::A2_tfr && TfrOpcode != Hexagon::A2_tfr)
|
|
return false;
|
|
if (!(RegMI->getOperand(0).isReg() && RegMI->getOperand(1).isReg()))
|
|
return false;
|
|
unsigned InLoopReg = RegMI->getOperand(1).getReg();
|
|
if (!LoopBB->isLiveIn(InLoopReg))
|
|
return false;
|
|
|
|
// Create a region to pass to ResourcesAvailableInBundle.
|
|
BasicBlockRegion PUR(BasicBlockRegion(TII, QRI, PredBB));
|
|
PUR.addBBtoRegion(LoopBB);
|
|
PUR.addBBtoRegion(SuccBB);
|
|
|
|
// Make sure we have space in PredBB's last bundle.
|
|
if (!ResourcesAvailableInBundle(&PUR, PredBundle))
|
|
return false;
|
|
SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> PredBundlePkt(
|
|
CurrentState.HomeBundle);
|
|
|
|
// Find condition to use for predicating the reg copy into PredBB.
|
|
MachineBasicBlock *TBB = NULL, *FBB = NULL;
|
|
SmallVector<MachineOperand, 4> Cond;
|
|
if (QII->analyzeBranch(*PredBB, TBB, FBB, Cond, false))
|
|
return false;
|
|
if (Cond.empty())
|
|
return false;
|
|
|
|
// Find condition to use for predicating the reg copy at the end of LoopBB.
|
|
MachineBasicBlock *LTBB = NULL, *LFBB = NULL;
|
|
SmallVector<MachineOperand, 4> LCond;
|
|
if (QII->analyzeBranch(*LoopBB, LTBB, LFBB, LCond, false))
|
|
return false;
|
|
if (LCond.empty())
|
|
return false;
|
|
|
|
// Move predicated reg copy to previous BB's last bundle.
|
|
if (!TII->isPredicable(*RegMI))
|
|
return false;
|
|
MachineInstr *InstrToMove =
|
|
&*insertTempCopy(PredBB, PredBundle, RegMI, false);
|
|
if (!canAddMIToThisPacket(InstrToMove, PredBundlePkt)) {
|
|
PredBB->erase_instr(InstrToMove);
|
|
return false;
|
|
}
|
|
|
|
if (!TII->PredicateInstruction(*InstrToMove, Cond)) {
|
|
// Failed to predicate the copy reg.
|
|
PredBB->erase_instr(InstrToMove);
|
|
return false;
|
|
}
|
|
|
|
// Can we newify this instruction?
|
|
unsigned DepReg = 0;
|
|
if (NeedToNewify(InstrToMove->getIterator(), &DepReg, &*PredBundle) &&
|
|
!isNewifiable(InstrToMove->getIterator(), DepReg, &*PredBundle)) {
|
|
PredBB->erase_instr(InstrToMove);
|
|
return false;
|
|
}
|
|
// Newify it, and then undo it if we determine we are using a .old.
|
|
int NewOpcode = QII->getDotNewPredOp(*InstrToMove, MBPI);
|
|
// Undo newify if we have a non .new predicated jump we are matching.
|
|
if (!QII->isDotNewInst(*PredCondBranch))
|
|
NewOpcode = QII->getDotOldOp(*InstrToMove);
|
|
NewOpcode = QII->getInvertedPredicatedOpcode(NewOpcode);
|
|
// Properly set the opcode on the new hoisted reg copy instruction.
|
|
InstrToMove->setDesc(QII->get(NewOpcode));
|
|
if (!incrementalAddToPacket(*InstrToMove)) {
|
|
PredBB->erase_instr(InstrToMove);
|
|
return false;
|
|
}
|
|
|
|
// Find the conditional branch and its bundle for LoopBB.
|
|
MachineBasicBlock::iterator LoopBundle;
|
|
MachineInstr *LoopCondBranch = NULL;
|
|
LoopCondBranch = findBundleAndBranch(LoopBB, LoopBundle);
|
|
if (!LoopCondBranch)
|
|
return false;
|
|
if (LoopBundle == LoopBB->end())
|
|
return false;
|
|
LLVM_DEBUG(dbgs() << "LoopBB's Branch: ");
|
|
LLVM_DEBUG(dbgs() << *LoopCondBranch);
|
|
|
|
// Make sure we have space in LoopBB's last bundle.
|
|
if (!ResourcesAvailableInBundle(&PUR, LoopBundle))
|
|
return false;
|
|
SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> LoopBundlePkt(
|
|
CurrentState.HomeBundle);
|
|
|
|
// Move predicated reg copy to last bundle of LoopBB.
|
|
MachineInstr *InstrToSink =
|
|
&*insertTempCopy(LoopBB, LoopBundle, RegMI, false);
|
|
if (!canAddMIToThisPacket(InstrToSink, LoopBundlePkt)) {
|
|
// Get rid of previous instruction as well.
|
|
PredBB->erase_instr(InstrToMove);
|
|
LoopBB->erase_instr(InstrToSink);
|
|
return false;
|
|
}
|
|
|
|
if (!TII->PredicateInstruction(*InstrToSink, LCond)) {
|
|
// Get rid of previous instruction as well.
|
|
PredBB->erase_instr(InstrToMove);
|
|
LoopBB->erase_instr(InstrToSink);
|
|
return false;
|
|
}
|
|
// Can we newify this instruction?
|
|
if (NeedToNewify(InstrToSink->getIterator(), &DepReg, &*LoopBundle) &&
|
|
!isNewifiable(InstrToSink->getIterator(), DepReg, &*LoopBundle)) {
|
|
// Get rid of previous instruction as well.
|
|
PredBB->erase_instr(InstrToMove);
|
|
PredBB->erase_instr(InstrToSink);
|
|
return false;
|
|
}
|
|
NewOpcode = QII->getDotNewPredOp(*InstrToSink, MBPI);
|
|
// Undo newify if we have a non .new predicated jump we are matching.
|
|
if (!QII->isDotNewInst(*LoopCondBranch))
|
|
NewOpcode = QII->getDotOldOp(*InstrToSink);
|
|
InstrToSink->setDesc(QII->get(NewOpcode));
|
|
if (!incrementalAddToPacket(*InstrToSink)) {
|
|
// Get rid of previous instruction as well.
|
|
PredBB->erase_instr(InstrToMove);
|
|
LoopBB->erase_instr(InstrToSink);
|
|
return false;
|
|
}
|
|
|
|
// Remove old instruction.
|
|
LoopBB->erase_instr(RegMI);
|
|
// Set loop alignment to 32.
|
|
LoopBB->setAlignment(llvm::Align(32));
|
|
|
|
LLVM_DEBUG(dbgs() << "Peeled Single BBLoop copy\n");
|
|
LLVM_DEBUG(dbgs() << *InstrToMove);
|
|
LLVM_DEBUG(dbgs() << *InstrToSink);
|
|
LLVM_DEBUG(dbgs() << *PredBB);
|
|
LLVM_DEBUG(dbgs() << *LoopBB);
|
|
LLVM_DEBUG(dbgs() << *SuccBB);
|
|
LLVM_DEBUG(dbgs() << "--- BBLoop ---\n\n");
|
|
return true;
|
|
}
|
|
|
|
bool HexagonGlobalSchedulerImpl::performPullUpCFG(MachineFunction &Fn) {
|
|
const Function &F = Fn.getFunction();
|
|
// Check for single-block functions and skip them.
|
|
if (std::next(F.begin()) == F.end())
|
|
return false;
|
|
bool Changed = false;
|
|
LLVM_DEBUG(dbgs() << "****** PullUpCFG **************\n");
|
|
|
|
// Loop over all basic blocks, asking if 3 consecutive blocks are
|
|
// the jump opportunity.
|
|
MachineBasicBlock *PrevBlock = NULL;
|
|
MachineBasicBlock *JumpBlock = NULL;
|
|
for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
|
|
++MBB) {
|
|
MachineBasicBlock *FallBlock = &*MBB;
|
|
if (PrevBlock && JumpBlock) {
|
|
Changed |= pullUpPeelBBLoop(PrevBlock, JumpBlock);
|
|
}
|
|
PrevBlock = JumpBlock;
|
|
JumpBlock = FallBlock;
|
|
}
|
|
return Changed;
|
|
}
|
|
|
|
void HexagonGlobalSchedulerImpl::GenUseDefChain(MachineFunction &Fn) {
|
|
std::vector<unsigned> Defs;
|
|
std::vector<unsigned> Uses;
|
|
for (MachineFunction::iterator MBBIter = Fn.begin(); MBBIter != Fn.end();
|
|
++MBBIter) {
|
|
for (MachineBasicBlock::instr_iterator MIter = MBBIter->instr_begin();
|
|
MIter != MBBIter->instr_end(); ++MIter) {
|
|
if (MIter->isBundle() || MIter->isDebugInstr())
|
|
continue;
|
|
LLVM_DEBUG(dbgs() << "\n\nInserted Ins:"; MIter->dump());
|
|
MIUseDefSet(&*MIter, Defs, Uses);
|
|
LLVM_DEBUG(dbgs() << "\n\tDefs:";
|
|
for (unsigned i = 0; i < Defs.size(); ++i) dbgs()
|
|
<< printReg(Defs[i], QRI) << ",");
|
|
LLVM_DEBUG(dbgs() << "\n\tUses:";
|
|
for (unsigned i = 0; i < Uses.size(); ++i) dbgs()
|
|
<< printReg(Uses[i], QRI) << ",");
|
|
MIDefSet[&*MIter] = Defs;
|
|
MIUseSet[&*MIter] = Uses;
|
|
}
|
|
}
|
|
}
|
|
|
|
// optimizeBranching -
|
|
// 1. A conditional-jump transfers control to a BB with
|
|
// jump as the only instruction.
|
|
// if(p0) jump t1
|
|
// // ...
|
|
// t1: jump t2
|
|
// 2. When a BB with a single conditional jump, jumps to succ-of-succ and
|
|
// falls-through BB with only jump instruction.
|
|
// { if(p0) jump t1 }
|
|
// { jump t2 }
|
|
// t1: { ... }
|
|
MachineBasicBlock *HexagonGlobalSchedulerImpl::optimizeBranches(
|
|
MachineBasicBlock *MBB, MachineBasicBlock *TBB, MachineInstr *FirstTerm,
|
|
MachineBasicBlock *FBB) {
|
|
LLVM_DEBUG(dbgs() << "\n\t\t[optimizeBranching]\n");
|
|
if ((TBB == MBB) || (FBB == MBB))
|
|
LLVM_DEBUG(dbgs() << "Cannot deal with loops in BB#" << MBB->getNumber(););
|
|
|
|
// LLVM_DEBUG(dbgs() << "\n\t\tTBBMIb:"; MII->dump(););
|
|
// { if(p) jump t1; }
|
|
// t1: { jump t2; }
|
|
// --> { if(p) jump t2
|
|
// remove t1: { jump t2; }, if it's address is not taken/not a landing pad.
|
|
if (QII->nonDbgBBSize(TBB) == 1) {
|
|
MachineInstr *TBBMIb = &*TBB->getFirstNonDebugInstr();
|
|
if (TBBMIb->getOpcode() == Hexagon::J2_jump &&
|
|
TBBMIb->getOperand(0).isMBB()) {
|
|
MachineBasicBlock *NewTarget = TBBMIb->getOperand(0).getMBB();
|
|
if (TBB == NewTarget) // Infinite loop.
|
|
return NULL;
|
|
|
|
LLVM_DEBUG(dbgs() << "\nSuboptimal branching in TBB");
|
|
// Check if the jump in the last instruction is within range.
|
|
int64_t InstOffset =
|
|
BlockToInstOffset.find(MBB)->second + QII->nonDbgBBSize(MBB) * 4;
|
|
unsigned Distance = (unsigned)std::abs(
|
|
InstOffset - BlockToInstOffset.find(NewTarget)->second);
|
|
if (!QII->isJumpWithinBranchRange(*FirstTerm, Distance)) {
|
|
LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
|
|
<< " out of range.");
|
|
return NULL;
|
|
}
|
|
// We need to make sure that the TBB is _not_ also a target for another
|
|
// branch. This is suboptimal since theoretically we can update both
|
|
// branches.
|
|
if (!TBB->hasAddressTaken() && !TBB->isEHPad() && TBB->pred_size() == 1) {
|
|
updatePredecessors(*TBB, NewTarget);
|
|
// TBB has only one successor since only one J2_jump instr.
|
|
TBB->removeSuccessor(TBB->succ_begin());
|
|
TBBMIb->removeFromParent();
|
|
if (!TBB->empty()) {
|
|
// There are only debug instructions in TBB now. Move them to
|
|
// the beginning of NewTarget.
|
|
NewTarget->splice(NewTarget->getFirstNonPHI(), TBB, TBB->begin(),
|
|
TBB->end());
|
|
}
|
|
return TBB;
|
|
} else {
|
|
MBB->ReplaceUsesOfBlockWith(TBB, NewTarget);
|
|
return NULL;
|
|
}
|
|
}
|
|
}
|
|
// { if(p) jump t1; } may contain more instructions
|
|
// { jump t2; } --only one instruction
|
|
// t1: {...}
|
|
// TBB is layout successor of FBB, then we can change the branch target
|
|
// for conditional jump and invert the predicate to remove jump t2.
|
|
// { if(!p) jump t2; }
|
|
// t1: {...}
|
|
if (QII->nonDbgBBSize(FBB) == 1) {
|
|
MachineInstr *FBBMIb = &*FBB->getFirstNonDebugInstr();
|
|
if (FBBMIb->getOpcode() == Hexagon::J2_jump &&
|
|
FBBMIb->getOperand(0).isMBB()) {
|
|
MachineBasicBlock *NewTarget = FBBMIb->getOperand(0).getMBB();
|
|
if (FBB->hasAddressTaken() || FBB->isEHPad() ||
|
|
!FBB->isLayoutSuccessor(TBB) || (FBB == NewTarget /*Infinite loop*/))
|
|
return NULL;
|
|
|
|
LLVM_DEBUG(dbgs() << "\nSuboptimal branching in FBB");
|
|
// Check if the jump in the last instruction is within range.
|
|
int64_t InstOffset =
|
|
BlockToInstOffset.find(MBB)->second + QII->nonDbgBBSize(MBB) * 4;
|
|
unsigned Distance = (unsigned)std::abs(
|
|
InstOffset - BlockToInstOffset.find(NewTarget)->second);
|
|
if (!QII->isJumpWithinBranchRange(*FirstTerm, Distance)) {
|
|
LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
|
|
<< " out of range.");
|
|
return NULL;
|
|
}
|
|
if (!QII->invertAndChangeJumpTarget(*FirstTerm, NewTarget))
|
|
return NULL;
|
|
LLVM_DEBUG(dbgs() << "\nNew instruction:"; FirstTerm->dump(););
|
|
updatePredecessors(*FBB, NewTarget);
|
|
// Only one successor remains for FBB
|
|
FBB->removeSuccessor(FBB->succ_begin());
|
|
FBBMIb->removeFromParent();
|
|
return FBB;
|
|
}
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
// performExposedOptimizations -
|
|
// look for optimization opportunities after pullup.
|
|
// e.g. jump to adjacent targets
|
|
bool HexagonGlobalSchedulerImpl::performExposedOptimizations(
|
|
MachineFunction &Fn) {
|
|
// Check for single-block functions and skip them.
|
|
if (std::next(Fn.getFunction().begin()) == Fn.getFunction().end())
|
|
return true;
|
|
LLVM_DEBUG(dbgs() << "\n\t\t[performExposedOptimizations]\n");
|
|
// Erasing the empty basic blocks formed during pullup.
|
|
std::vector<MachineBasicBlock *>::iterator ebb = EmptyBBs.begin();
|
|
while (ebb != EmptyBBs.end()) {
|
|
assert(IsEmptyBlock(*ebb) && "Pullup inserted packets into an empty BB");
|
|
LLVM_DEBUG(dbgs() << "Removing BB(" << (*ebb)->getNumber()
|
|
<< ") from parent.\n");
|
|
(*ebb)->eraseFromParent();
|
|
++ebb;
|
|
}
|
|
MachineBasicBlock *TBB = NULL, *FBB = NULL;
|
|
MachineInstr *FirstTerm = NULL, *SecondTerm = NULL;
|
|
|
|
SmallVector<MachineBasicBlock *, 4> Erase;
|
|
|
|
for (MachineBasicBlock &MBB : Fn) {
|
|
if (MBB.succ_size() > 2 ||
|
|
AnalyzeBBBranches(&MBB, TBB, FirstTerm, FBB, SecondTerm)) {
|
|
LLVM_DEBUG(dbgs() << "\nAnalyzeBBBranches failed in BB#"
|
|
<< MBB.getNumber() << "\n";);
|
|
continue;
|
|
}
|
|
if (FirstTerm && QII->isCompoundBranchInstr(*FirstTerm))
|
|
continue;
|
|
if (TBB && FirstTerm &&
|
|
removeRedundantBranches(&MBB, TBB, FirstTerm, FBB, SecondTerm)) {
|
|
LLVM_DEBUG(dbgs() << "\nRemoved redundant branches in BB#"
|
|
<< MBB.getNumber(););
|
|
continue;
|
|
}
|
|
if (FirstTerm && SecondTerm &&
|
|
optimizeDualJumps(&MBB, TBB, FirstTerm, FBB, SecondTerm)) {
|
|
LLVM_DEBUG(dbgs() << "\nRemoved dual jumps in in BB#"
|
|
<< MBB.getNumber(););
|
|
continue;
|
|
}
|
|
if (TBB && FBB && FirstTerm && !SecondTerm) {
|
|
MachineBasicBlock *MBBToErase =
|
|
optimizeBranches(&MBB, TBB, FirstTerm, FBB);
|
|
if (MBBToErase) {
|
|
assert(IsEmptyBlock(MBBToErase) && "Erasing non-empty BB");
|
|
Erase.push_back(MBBToErase);
|
|
LLVM_DEBUG(dbgs() << "\nOptimized jump from BB#" << MBB.getNumber());
|
|
}
|
|
}
|
|
}
|
|
for (MachineBasicBlock *MBB : Erase)
|
|
MBB->eraseFromParent();
|
|
|
|
return false;
|
|
}
|
|
|
|
// 1. Remove jump to the layout successor.
|
|
// 2. Remove multiple (dual) jump to the same target.
|
|
bool HexagonGlobalSchedulerImpl::removeRedundantBranches(
|
|
MachineBasicBlock *MBB, MachineBasicBlock *TBB, MachineInstr *FirstTerm,
|
|
MachineBasicBlock *FBB, MachineInstr *SecondTerm) {
|
|
bool Analyzed = false;
|
|
LLVM_DEBUG(dbgs() << "\n\t\t[removeRedundantBranches]\n");
|
|
MachineInstr *Head = NULL, *ToErase = NULL;
|
|
if (!FBB && (FirstTerm->getOpcode() == Hexagon::J2_jump) &&
|
|
MBB->isLayoutSuccessor(TBB)) {
|
|
// Jmp layout_succ_basic_block <-- Remove
|
|
LLVM_DEBUG(
|
|
dbgs() << "\nRemoving Uncond. jump to the layout successor in BB#"
|
|
<< MBB->getNumber());
|
|
ToErase = FirstTerm;
|
|
} else if (SecondTerm && (TBB == FBB) &&
|
|
(SecondTerm->getOpcode() == Hexagon::J2_jump)) {
|
|
// If both branching instructions in same packet or are consecutive.
|
|
// Jmp_c t1 <-- Remove
|
|
// Jmp t1
|
|
// @Note: If they are in different packets or if they are separated
|
|
// by packet(s), this opt. cannot be done.
|
|
MachineBasicBlock::instr_iterator FirstTermIter = FirstTerm->getIterator();
|
|
MachineBasicBlock::instr_iterator SecondTermIter =
|
|
SecondTerm->getIterator();
|
|
if (++FirstTermIter == SecondTermIter) {
|
|
LLVM_DEBUG(dbgs() << "\nRemoving multiple branching to same target in BB#"
|
|
<< MBB->getNumber());
|
|
// TODO: This might make the `p' register assignment instruction dead.
|
|
// and can be removed.
|
|
ToErase = FirstTerm;
|
|
}
|
|
} else if (SecondTerm && (SecondTerm->getOpcode() == Hexagon::J2_jump) &&
|
|
FBB && MBB->isLayoutSuccessor(FBB)) {
|
|
// Jmp_c t1
|
|
// Jmp layout_succ_basic_block <-- Remove
|
|
LLVM_DEBUG(dbgs() << "\nRemoving fall through branch in BB#"
|
|
<< MBB->getNumber());
|
|
ToErase = SecondTerm;
|
|
} else if (SecondTerm && QII->PredOpcodeHasJMP_c(SecondTerm->getOpcode()) &&
|
|
MBB->isLayoutSuccessor(getBranchDestination(SecondTerm))) {
|
|
// Jmp_c t1
|
|
// Jmp_c layout_succ_basic_block <-- Remove
|
|
// In this case AnalyzeBBBranches might assign FBB to some other BB.
|
|
// So using the jump target of SecondTerm to check.
|
|
LLVM_DEBUG(dbgs() << "\nRemoving Cond. jump to the layout successor in BB#"
|
|
<< MBB->getNumber());
|
|
ToErase = SecondTerm;
|
|
}
|
|
// Remove the instruction from the BB
|
|
if (ToErase) {
|
|
if (ToErase->isBundled()) {
|
|
Head = &*getBundleStart(ToErase->getIterator());
|
|
ToErase->eraseFromBundle();
|
|
UpdateBundle(Head);
|
|
} else
|
|
ToErase->eraseFromParent();
|
|
Analyzed = true;
|
|
}
|
|
return Analyzed;
|
|
}
|
|
|
|
// ----- convert
|
|
// p = <expr>
|
|
// if(p) jump layout_succ_basic_block
|
|
// jump t
|
|
// ----- to
|
|
// p = <expr>
|
|
// if(!p) jump t
|
|
// for now only looking at the dual jump
|
|
bool HexagonGlobalSchedulerImpl::optimizeDualJumps(MachineBasicBlock *MBB,
|
|
MachineBasicBlock *TBB,
|
|
MachineInstr *FirstTerm,
|
|
MachineBasicBlock *FBB,
|
|
MachineInstr *SecondTerm) {
|
|
LLVM_DEBUG(dbgs() << "\n******* optimizeDualJumps *******");
|
|
|
|
bool Analyzed = false;
|
|
|
|
if (QII->PredOpcodeHasJMP_c(FirstTerm->getOpcode()) &&
|
|
(SecondTerm->getOpcode() == Hexagon::J2_jump)) {
|
|
|
|
if (TBB == FBB) {
|
|
LLVM_DEBUG(dbgs() << "\nBoth successors are the same.");
|
|
return Analyzed;
|
|
}
|
|
|
|
// Do not optimize for dual jumps if this MBB
|
|
// contains a speculatively pulled-up instruction.
|
|
// A speculated instruction is more likely to be at the end of MBB.
|
|
MachineBasicBlock::reverse_instr_iterator SII = MBB->instr_rbegin();
|
|
while (SII != MBB->instr_rend()) {
|
|
MachineInstr *SI = &*SII;
|
|
std::map<MachineInstr *, MachineBasicBlock *>::iterator MIMoved;
|
|
MIMoved = SpeculatedIns.find(SI);
|
|
if ((MIMoved != SpeculatedIns.end()) &&
|
|
(MIMoved->second != SI->getParent())) {
|
|
return Analyzed;
|
|
}
|
|
++SII;
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "\nCandidate for jump optimization in BB("
|
|
<< MBB->getNumber() << ").\n";);
|
|
|
|
// Predicated jump to layout successor followed by an unconditional jump.
|
|
if (MBB->isLayoutSuccessor(TBB)) {
|
|
|
|
// Check if the jump in the last instruction is within range.
|
|
int64_t InstOffset =
|
|
BlockToInstOffset.find(&*MBB)->second + QII->nonDbgBBSize(MBB) * 4;
|
|
unsigned Distance =
|
|
(unsigned)std::abs(InstOffset - BlockToInstOffset.find(FBB)->second) +
|
|
SafetyBuffer;
|
|
if (!QII->isJumpWithinBranchRange(*FirstTerm, Distance)) {
|
|
LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
|
|
<< " out of range.");
|
|
return Analyzed;
|
|
}
|
|
|
|
// modify the second last -predicated- instruction (sense and target)
|
|
LLVM_DEBUG(dbgs() << "\nFirst Instr:" << *FirstTerm;);
|
|
LLVM_DEBUG(dbgs() << "\nSecond Instr:" << *SecondTerm;);
|
|
LLVM_DEBUG(dbgs() << "\nOld Succ BB(" << TBB->getNumber() << ").";);
|
|
|
|
QII->invertAndChangeJumpTarget(*FirstTerm, FBB);
|
|
|
|
LLVM_DEBUG(dbgs() << "\nNew First Instruction:" << *FirstTerm;);
|
|
|
|
// unbundle if there is only one instruction left
|
|
MachineInstr *SecondHead, *FirstHead;
|
|
FirstHead = FirstTerm->isBundled()
|
|
? &*getBundleStart(FirstTerm->getIterator())
|
|
: nullptr;
|
|
SecondHead = SecondTerm->isBundled()
|
|
? &*getBundleStart(SecondTerm->getIterator())
|
|
: nullptr;
|
|
|
|
// 1. Both unbundled, 2. FirstTerm inside bundle, second outside.
|
|
if (!SecondHead)
|
|
SecondTerm->eraseFromParent();
|
|
else if (!FirstHead) {
|
|
// 3. FirstHead outside, SecondHead inside.
|
|
SecondTerm->eraseFromBundle();
|
|
UpdateBundle(SecondHead);
|
|
} else if (FirstHead == SecondHead) {
|
|
// 4. Both are in the same bundle
|
|
assert((FirstHead && SecondHead) && "Unbundled Instruction");
|
|
SecondTerm->eraseFromBundle();
|
|
if (SecondHead->getBundleSize() < 2)
|
|
UpdateBundle(SecondHead);
|
|
} else {
|
|
// 5. Both are in different bundles
|
|
SecondTerm->eraseFromBundle();
|
|
UpdateBundle(SecondHead);
|
|
}
|
|
Analyzed = true;
|
|
}
|
|
}
|
|
return Analyzed;
|
|
}
|
|
|
|
/// Are there any resources left in this bundle?
|
|
bool HexagonGlobalSchedulerImpl::ResourcesAvailableInBundle(
|
|
BasicBlockRegion *CurrentRegion,
|
|
MachineBasicBlock::iterator &TargetPacket) {
|
|
MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
|
|
|
|
// If this is a single instruction, form new packet around it.
|
|
if (!TargetPacket->isBundle()) {
|
|
if (ignoreInstruction(&*MII) || isSoloInstruction(*MII))
|
|
return false;
|
|
|
|
// Before we begin, we need to make sure that we do not
|
|
// look at an unconditional jump outside the current region.
|
|
if (MII->isBranch() && !isBranchWithinRegion(CurrentRegion, &*MII))
|
|
return false;
|
|
|
|
// Build up state for this new packet.
|
|
// Note, we cannot create a bundle header for it,
|
|
// so this "bundle" only exist in DFA state, and not in code.
|
|
initPacketizerState();
|
|
ResourceTracker->clearResources();
|
|
CurrentState.addHomeLocation(MII);
|
|
return incrementalAddToPacket(*MII);
|
|
}
|
|
|
|
MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
|
|
|
|
// Build up state for this packet.
|
|
initPacketizerState();
|
|
ResourceTracker->clearResources();
|
|
CurrentState.addHomeLocation(MII);
|
|
|
|
for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
|
|
if (MII->getOpcode() == TargetOpcode::DBG_VALUE ||
|
|
MII->getOpcode() == TargetOpcode::IMPLICIT_DEF ||
|
|
MII->getOpcode() == TargetOpcode::CFI_INSTRUCTION || MII->isEHLabel())
|
|
continue;
|
|
|
|
// Before we begin, we need to make sure that we do not
|
|
// look at an unconditional jump outside the current region.
|
|
// TODO: See if we can profit from handling this kind of cases:
|
|
// B#15: derived from LLVM BB %if.then22
|
|
// Predecessors according to CFG: BB#13
|
|
// BUNDLE %PC<imp-def>, %P2<imp-use,kill>
|
|
// * J2_jumpf %P2<kill,internal>, <BB#17>, %PC<imp-def>; flags:
|
|
// * J2_jump <BB#18>, %PC<imp-def>; flags:
|
|
// Successors according to CFG: BB#18(62) BB#17(62)
|
|
// Curently we do not allow them.
|
|
if (MII->isBranch() && !isBranchWithinRegion(CurrentRegion, &*MII))
|
|
return false;
|
|
|
|
if (!incrementalAddToPacket(*MII))
|
|
return false;
|
|
}
|
|
return ResourceTracker->canReserveResources(*Nop);
|
|
}
|
|
|
|
/// Symmetrical. See if these two instructions are fit for compound pair.
|
|
bool HexagonGlobalSchedulerImpl::isCompoundPair(MachineInstr *MIa,
|
|
MachineInstr *MIb) {
|
|
enum HexagonII::CompoundGroup MIaG = QII->getCompoundCandidateGroup(*MIa),
|
|
MIbG = QII->getCompoundCandidateGroup(*MIb);
|
|
// We have two candidates - check that this is the same register
|
|
// we are talking about.
|
|
unsigned Opcb = MIb->getOpcode();
|
|
if (MIaG == HexagonII::HCG_C && MIbG == HexagonII::HCG_A &&
|
|
(Opcb == Hexagon::A2_tfr || Opcb == Hexagon::A2_tfrsi))
|
|
return true;
|
|
unsigned Opca = MIa->getOpcode();
|
|
if (MIbG == HexagonII::HCG_C && MIaG == HexagonII::HCG_A &&
|
|
(Opca == Hexagon::A2_tfr || Opca == Hexagon::A2_tfrsi))
|
|
return true;
|
|
return (((MIaG == HexagonII::HCG_A && MIbG == HexagonII::HCG_B) ||
|
|
(MIbG == HexagonII::HCG_A && MIaG == HexagonII::HCG_B)) &&
|
|
(MIa->getOperand(0).getReg() == MIb->getOperand(0).getReg()));
|
|
}
|
|
|
|
// This is a weird situation when BB conditionally branches + falls through
|
|
// to layout successor. \ref bug17792
|
|
inline bool HexagonGlobalSchedulerImpl::multipleBranchesFromToBB(
|
|
MachineBasicBlock *BB) const {
|
|
if (BB->succ_size() != 1)
|
|
return false;
|
|
SmallVector<MachineInstr *, 2> Jumpers = QII->getBranchingInstrs(*BB);
|
|
return ((Jumpers.size() == 1) && !Jumpers[0]->isUnconditionalBranch());
|
|
}
|
|
|
|
/// Gather a worklist of MaxCandidates pull-up candidates.
|
|
/// Compute relative cost.
|
|
bool HexagonGlobalSchedulerImpl::findPullUpCandidates(
|
|
MachineBasicBlock::iterator &WorkPoint,
|
|
MachineBasicBlock::iterator &FromHere,
|
|
std::vector<MachineInstr *> &backtrack, unsigned MaxCandidates = 1) {
|
|
|
|
const HexagonInstrInfo *QII = (const HexagonInstrInfo *)TII;
|
|
MachineBasicBlock *FromThisBB = FromHere->getParent();
|
|
bool MovingDependentOp = false;
|
|
signed CostBenefit = 0;
|
|
|
|
// Do not collect more than that many candidates.
|
|
if (CurrentState.haveCandidates() >= MaxCandidates)
|
|
return false;
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\tTry from BB(" << FromThisBB->getNumber() << "):\n";
|
|
DumpPacket(FromHere.getInstrIterator()));
|
|
|
|
if (FromHere->isBundle()) {
|
|
MachineBasicBlock::instr_iterator MII = FromHere.getInstrIterator();
|
|
for (++MII; MII != FromThisBB->instr_end() && MII->isInsideBundle();
|
|
++MII) {
|
|
if (MII->isDebugInstr())
|
|
continue;
|
|
LLVM_DEBUG(dbgs() << "\tCandidate from BB("
|
|
<< MII->getParent()->getNumber() << "): ";
|
|
MII->dump());
|
|
|
|
// See if this instruction could be moved.
|
|
if (!canThisMIBeMoved(&*MII, WorkPoint, MovingDependentOp, CostBenefit))
|
|
continue;
|
|
|
|
MachineBasicBlock::instr_iterator InstrToMove = MII;
|
|
if (canAddMIToThisPacket(&*InstrToMove, CurrentState.HomeBundle)) {
|
|
CostBenefit -= (backtrack.size() * 4);
|
|
// Prefer instructions in empty packets.
|
|
CostBenefit += (PacketSize - nonDbgBundleSize(FromHere)) * 2;
|
|
// Prefer Compares.
|
|
if (MII->isCompare())
|
|
CostBenefit += 10;
|
|
// Check duplex conditions;
|
|
for (unsigned i = 0; i < CurrentState.HomeBundle.size(); i++) {
|
|
if (QII->isDuplexPair(*CurrentState.HomeBundle[i], *MII)) {
|
|
LLVM_DEBUG(dbgs() << "\tGot real Duplex (bundle).\n");
|
|
CostBenefit += 20;
|
|
}
|
|
if (isCompoundPair(CurrentState.HomeBundle[i], &*MII)) {
|
|
LLVM_DEBUG(dbgs() << "\tGot compound (bundle).\n");
|
|
CostBenefit += 40;
|
|
}
|
|
}
|
|
// Create a record for this location.
|
|
CurrentState.addPullUpCandidate(InstrToMove, WorkPoint, backtrack,
|
|
MovingDependentOp, CostBenefit);
|
|
} else
|
|
LLVM_DEBUG(dbgs() << "\tNo resources in the target packet.\n");
|
|
}
|
|
}
|
|
// This is a standalone instruction.
|
|
// First see if this MI can even be moved. Cost model for a single instruction
|
|
// should be rather different from moving something out of a bundle.
|
|
else if (canThisMIBeMoved(&*FromHere, WorkPoint, MovingDependentOp,
|
|
CostBenefit)) {
|
|
MachineBasicBlock::instr_iterator InstrToMove = FromHere.getInstrIterator();
|
|
if (canAddMIToThisPacket(&*InstrToMove, CurrentState.HomeBundle)) {
|
|
CostBenefit -= (backtrack.size() * 4);
|
|
// Prefer Compares.
|
|
if (InstrToMove->isCompare())
|
|
CostBenefit += 10;
|
|
// It is better to pull a single instruction in to a bundle - save
|
|
// a cycle immediately.
|
|
CostBenefit += 10;
|
|
// Search for duplex match.
|
|
for (unsigned i = 0; i < CurrentState.HomeBundle.size(); i++) {
|
|
if (QII->isDuplexPair(*CurrentState.HomeBundle[i], *InstrToMove)) {
|
|
LLVM_DEBUG(dbgs() << "\tGot real Duplex (single).\n");
|
|
CostBenefit += 30;
|
|
}
|
|
if (isCompoundPair(CurrentState.HomeBundle[i], &*InstrToMove)) {
|
|
LLVM_DEBUG(dbgs() << "\tGot compound (single).\n");
|
|
CostBenefit += 50;
|
|
}
|
|
}
|
|
// Create a record for this location.
|
|
CurrentState.addPullUpCandidate(InstrToMove, WorkPoint, backtrack,
|
|
MovingDependentOp, CostBenefit);
|
|
} else
|
|
LLVM_DEBUG(dbgs() << "\tNo resources for single in the target packet.\n");
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Try to move a candidate MI.
|
|
/// The move can destroy all iterator system, so we have to drag them
|
|
/// around to keep them up to date.
|
|
bool HexagonGlobalSchedulerImpl::tryMultipleInstructions(
|
|
MachineBasicBlock::iterator &RetVal, /* output parameter */
|
|
std::vector<BasicBlockRegion *>::iterator &CurrentRegion,
|
|
MachineBasicBlock::iterator &NextMI,
|
|
MachineBasicBlock::iterator &ToThisBBEnd,
|
|
MachineBasicBlock::iterator &FromThisBBEnd, bool PathInRegion) {
|
|
|
|
MachineBasicBlock::instr_iterator MII;
|
|
MachineBasicBlock::iterator WorkPoint;
|
|
bool MovingDependentOp = false;
|
|
std::vector<MachineInstr *> backtrack;
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\tTry Multiple candidates: \n");
|
|
|
|
std::sort(CurrentState.PullUpCandidates.begin(),
|
|
CurrentState.PullUpCandidates.end(), PullUpCandidateSorter());
|
|
LLVM_DEBUG(CurrentState.dump());
|
|
// Iterate through candidates in sorted order.
|
|
for (SmallVector<PullUpCandidate *, 4>::iterator
|
|
I = CurrentState.PullUpCandidates.begin(),
|
|
E = CurrentState.PullUpCandidates.end();
|
|
I != E; ++I) {
|
|
(*I)->populate(MII, WorkPoint, backtrack, MovingDependentOp);
|
|
|
|
MachineBasicBlock *FromThisBB = MII->getParent();
|
|
MachineBasicBlock *ToThisBB = WorkPoint->getParent();
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\tCandidate: "; MII->dump());
|
|
LLVM_DEBUG(dbgs() << "\tDependent(" << MovingDependentOp << ") FromBB("
|
|
<< FromThisBB->getNumber() << ") ToBB("
|
|
<< ToThisBB->getNumber() << ") to this packet:\n";
|
|
DumpPacket(WorkPoint.getInstrIterator()));
|
|
|
|
MachineBasicBlock::instr_iterator FromHereII = MII;
|
|
if (MII->isInsideBundle()) {
|
|
while (!FromHereII->isBundle())
|
|
--FromHereII;
|
|
LLVM_DEBUG(dbgs() << "\tFrom here:\n"; DumpPacket(FromHereII));
|
|
|
|
MachineBasicBlock::iterator FromHere(FromHereII);
|
|
// We have instruction that could be moved from its current position.
|
|
if (MoveMItoBundle(*CurrentRegion, MII, NextMI, WorkPoint, FromHere,
|
|
backtrack, MovingDependentOp, PathInRegion)) {
|
|
// If BB from which we pull is now empty, move on.
|
|
if (IsEmptyBlock(FromThisBB)) {
|
|
LLVM_DEBUG(dbgs() << "\n\tExhosted BB (bundle).\n");
|
|
return false;
|
|
}
|
|
FromThisBBEnd = FromThisBB->end();
|
|
ToThisBBEnd = ToThisBB->end();
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\tAfter updates(bundle to bundle):\n");
|
|
LLVM_DEBUG(dbgs() << "\t\tWorkPoint: ";
|
|
DumpPacket(WorkPoint.getInstrIterator()));
|
|
|
|
// We should not increment current position,
|
|
// but rather try one more time to pull from the same bundle.
|
|
RetVal = WorkPoint;
|
|
return true;
|
|
} else
|
|
LLVM_DEBUG(dbgs() << "\tCould not move packetized instr.\n");
|
|
} else {
|
|
MachineBasicBlock::iterator FromHere(FromHereII);
|
|
if (MoveMItoBundle(*CurrentRegion, MII, NextMI, WorkPoint, FromHere,
|
|
backtrack, MovingDependentOp, PathInRegion)) {
|
|
|
|
// If BB from which we pull is now empty, move on.
|
|
if (IsEmptyBlock(FromThisBB)) {
|
|
LLVM_DEBUG(dbgs() << "\n\tExhosted BB (single).\n");
|
|
return false;
|
|
}
|
|
FromThisBBEnd = FromThisBB->end();
|
|
ToThisBBEnd = ToThisBB->end();
|
|
|
|
LLVM_DEBUG(dbgs() << "\tAfter updates (single to bundle):\n");
|
|
LLVM_DEBUG(dbgs() << "\t\tWorkPoint: ";
|
|
DumpPacket(WorkPoint.getInstrIterator()));
|
|
// We should not increment current position,
|
|
// but rather try one more time to pull from the same bundle.
|
|
RetVal = WorkPoint;
|
|
return true;
|
|
} else
|
|
LLVM_DEBUG(dbgs() << "\tCould not move single.\n");
|
|
}
|
|
}
|
|
LLVM_DEBUG(dbgs() << "\tNot a single candidate fit.\n");
|
|
return false;
|
|
}
|
|
|
|
/// Main function. Iterate all current regions one at a time,
|
|
/// and look for pull-up opportunities.
|
|
/// Pseudo sequence:
|
|
/// - for all bundles and single instructions in region:
|
|
/// - see if resources are available (in the same cycle) - this is HOME.
|
|
/// - Starting from next BB in region, find an instruction that could be:
|
|
/// - removed from its current location
|
|
/// - added to underutilized bundle (including bundles with only one op)
|
|
/// - If so, trace path back to HOME and check that candidate could be
|
|
/// reordered with all the intermediate instructions.
|
|
bool HexagonGlobalSchedulerImpl::performPullUp() {
|
|
std::vector<MachineInstr *> backtrack;
|
|
MachineBasicBlock::iterator FromHere;
|
|
MachineBasicBlock::iterator FromThisBBEnd;
|
|
|
|
LLVM_DEBUG(dbgs() << "****** PullUpRegions ***********\n");
|
|
// For all regions...
|
|
for (std::vector<BasicBlockRegion *>::iterator
|
|
CurrentRegion = PullUpRegions.begin(),
|
|
E = PullUpRegions.end();
|
|
CurrentRegion != E; ++CurrentRegion) {
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\nRegion with(" << (*CurrentRegion)->size()
|
|
<< ")BBs\n");
|
|
|
|
if (!EnableLocalPullUp && (*CurrentRegion)->size() < 2)
|
|
continue;
|
|
|
|
// For all MBB in the region... except the last one.
|
|
// ...except when we want to allow local pull-up.
|
|
for (auto ToThisBB = (*CurrentRegion)->getRootMBB(),
|
|
LastBBInRegion = (*CurrentRegion)->getLastMBB();
|
|
ToThisBB != LastBBInRegion; ++ToThisBB) {
|
|
// If we do not want to allow same BB pull-up, take an early exit.
|
|
if (!EnableLocalPullUp && (std::next(ToThisBB) == LastBBInRegion))
|
|
break;
|
|
if (multipleBranchesFromToBB(*ToThisBB))
|
|
break;
|
|
|
|
auto FromThisBB = ToThisBB;
|
|
MachineBasicBlock::iterator ToThisBBEnd = (*ToThisBB)->end();
|
|
MachineBasicBlock::iterator MI = (*ToThisBB)->begin();
|
|
|
|
LLVM_DEBUG(dbgs() << "\n\tHome iterator moved to new BB("
|
|
<< (*ToThisBB)->getNumber() << ")\n";
|
|
(*ToThisBB)->dump());
|
|
|
|
// For all instructions in the BB.
|
|
while (MI != ToThisBBEnd) {
|
|
MachineBasicBlock::iterator WorkPoint = MI;
|
|
++MI;
|
|
|
|
// Trivial check that there are unused resources
|
|
// in the current location (cycle).
|
|
while (ResourcesAvailableInBundle(*CurrentRegion, WorkPoint)) {
|
|
LLVM_DEBUG(dbgs() << "\nxxxx Next Home in BB("
|
|
<< (*ToThisBB)->getNumber() << "):\n";
|
|
DumpPacket(WorkPoint.getInstrIterator()));
|
|
// Keep the path to the candidate.
|
|
// It is the traveled path between home and work point.
|
|
// Reset it for the new iteration.
|
|
backtrack.clear();
|
|
|
|
// The point of pull-up source (WorkPoint) could begin from the
|
|
// current BB, but only if we allow pull-up in the same BB.
|
|
// At the moment we do not.
|
|
// We also do not process last block in the region,
|
|
// so it is safe to always begin with the next BB in the region.
|
|
// Start from "next" BB in the region.
|
|
if (EnableLocalPullUp) {
|
|
FromThisBB = ToThisBB;
|
|
FromHere = WorkPoint;
|
|
++FromHere;
|
|
FromThisBBEnd = (*FromThisBB)->end();
|
|
|
|
// Initialize backtrack.
|
|
// These are instructions between Home location
|
|
// and the WorkPoint.
|
|
for (MachineBasicBlock::iterator I = WorkPoint, IE = FromHere;
|
|
I != IE; ++I)
|
|
backtrack.push_back(&*I);
|
|
} else {
|
|
FromThisBB = ToThisBB;
|
|
++FromThisBB;
|
|
FromHere = (*FromThisBB)->begin();
|
|
FromThisBBEnd = (*FromThisBB)->end();
|
|
|
|
// Initialize backtrack.
|
|
// These are instructions between Home location
|
|
// and the end of the home BB.
|
|
for (MachineBasicBlock::iterator I = WorkPoint, IE = ToThisBBEnd;
|
|
I != IE; ++I)
|
|
backtrack.push_back(&*I);
|
|
}
|
|
|
|
// Search for pull-up candidate.
|
|
while (true) {
|
|
// If this BB is over, move onto the next one
|
|
// in this region.
|
|
if (FromHere == FromThisBBEnd) {
|
|
++FromThisBB;
|
|
// Refresh LastBBInRegion in case tryMultipleInstructions modified
|
|
// the regions Elements vector, invalidating the iterator.
|
|
LastBBInRegion = (*CurrentRegion)->getLastMBB();
|
|
if (FromThisBB == LastBBInRegion)
|
|
break;
|
|
else {
|
|
LLVM_DEBUG(dbgs() << "\n\tNext BB in this region\n";
|
|
(*FromThisBB)->dump());
|
|
FromThisBBEnd = (*FromThisBB)->end();
|
|
FromHere = (*FromThisBB)->begin();
|
|
if (FromThisBBEnd == FromHere)
|
|
break;
|
|
}
|
|
}
|
|
if ((*FromHere).isDebugInstr()) {
|
|
++FromHere;
|
|
continue;
|
|
}
|
|
// This is a step Home.
|
|
backtrack.push_back(&*FromHere);
|
|
if (!findPullUpCandidates(WorkPoint, FromHere, backtrack,
|
|
MainCandidateQueueSize))
|
|
break;
|
|
++FromHere;
|
|
}
|
|
// Try to pull-up one of the selected candidates.
|
|
if (!tryMultipleInstructions(/*output*/ WorkPoint, CurrentRegion, MI,
|
|
ToThisBBEnd, FromThisBBEnd))
|
|
break;
|
|
}
|
|
}
|
|
// Refresh LastBBInRegion after potential CFG modifications.
|
|
LastBBInRegion = (*CurrentRegion)->getLastMBB();
|
|
}
|
|
// AllowUnlikelyPath is on by default,
|
|
// if we wish to disable it, we can do so here.
|
|
if (!AllowUnlikelyPath)
|
|
continue;
|
|
|
|
// We have parsed the likely path through the region.
|
|
// Now traverse the other (unlikely) path.
|
|
//
|
|
// Note: BasicBlockRegion uses a vector for MBB storage, so adding BBs to
|
|
// the region while iterating could invalidate iterators. Collect the work
|
|
// items first, then process them.
|
|
std::vector<std::pair<MachineBasicBlock *, MachineBasicBlock *>>
|
|
UnlikelyWork;
|
|
UnlikelyWork.reserve((*CurrentRegion)->size());
|
|
for (auto ToIt = (*CurrentRegion)->getRootMBB(),
|
|
End = (*CurrentRegion)->getLastMBB();
|
|
ToIt != End; ++ToIt) {
|
|
MachineBasicBlock *ToBB = *ToIt;
|
|
MachineBasicBlock *SecondBest = getNextPURBB(ToBB, true);
|
|
if (SecondBest)
|
|
UnlikelyWork.emplace_back(ToBB, SecondBest);
|
|
}
|
|
|
|
for (auto [ToBB, SecondBest] : UnlikelyWork) {
|
|
LLVM_DEBUG(dbgs() << "\tFor BB:\n"; ToBB->dump());
|
|
LLVM_DEBUG(dbgs() << "\tHave SecondBest:\n"; SecondBest->dump());
|
|
// Adding this BB to the region should not be done if we
|
|
// plan to reuse it(the region) again. For now it is OK.
|
|
(*CurrentRegion)->addBBtoRegion(SecondBest);
|
|
LLVM_DEBUG(dbgs() << "\tHome iterator moved to new BB("
|
|
<< ToBB->getNumber() << ")\n";
|
|
ToBB->dump());
|
|
MachineBasicBlock::iterator ToThisBBEnd = ToBB->end();
|
|
MachineBasicBlock::iterator MI = ToBB->begin();
|
|
|
|
// For all instructions in the BB.
|
|
while (MI != ToThisBBEnd) {
|
|
MachineBasicBlock::iterator WorkPoint = MI;
|
|
++MI;
|
|
|
|
// Trivial check that there are unused resources
|
|
// in the current location (cycle).
|
|
while (ResourcesAvailableInBundle(*CurrentRegion, WorkPoint)) {
|
|
LLVM_DEBUG(dbgs() << "\nxxxx Second visit Home in BB("
|
|
<< ToBB->getNumber() << "):\n";
|
|
DumpPacket(WorkPoint.getInstrIterator()));
|
|
|
|
FromHere = SecondBest->begin();
|
|
FromThisBBEnd = SecondBest->end();
|
|
|
|
// Keep the path to the candidate.
|
|
backtrack.clear();
|
|
|
|
// This is Home location.
|
|
for (MachineBasicBlock::iterator I = WorkPoint, IE = ToThisBBEnd;
|
|
I != IE; ++I)
|
|
backtrack.push_back(&*I);
|
|
|
|
while (true) {
|
|
// If this BB is over, move onto the next one
|
|
// in this region.
|
|
if (FromHere == FromThisBBEnd) {
|
|
LLVM_DEBUG(dbgs()
|
|
<< "\tOnly do one successor for the second try\n");
|
|
break;
|
|
}
|
|
if ((*FromHere).isDebugInstr()) {
|
|
++FromHere;
|
|
continue;
|
|
}
|
|
// This is a step Home.
|
|
backtrack.push_back(&*FromHere);
|
|
if (!findPullUpCandidates(WorkPoint, FromHere, backtrack,
|
|
SecondaryCandidateQueueSize))
|
|
break;
|
|
++FromHere;
|
|
}
|
|
// Try to pull-up one of selected candidate.
|
|
if (!tryMultipleInstructions(/*output*/ WorkPoint, CurrentRegion, MI,
|
|
ToThisBBEnd, FromThisBBEnd, false))
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool HexagonGlobalSchedulerImpl::incrementalAddToPacket(MachineInstr &MI) {
|
|
|
|
LLVM_DEBUG(dbgs() << "\t[AddToPacket] (" << CurrentPacketMIs.size()
|
|
<< ") adding:\t";
|
|
MI.dump());
|
|
|
|
if (!ResourceTracker->canReserveResources(MI) || !shouldAddToPacket(MI))
|
|
return false;
|
|
|
|
ResourceTracker->reserveResources(MI);
|
|
CurrentPacketMIs.push_back(&MI);
|
|
CurrentState.HomeBundle.push_back(&MI);
|
|
|
|
if (QII->isExtended(MI) || QII->isConstExtended(MI) ||
|
|
isJumpOutOfRange(&MI)) {
|
|
// If at this point of time we cannot reserve resources,
|
|
// this might mean that the packet came into the pull-up
|
|
// pass already in danger of overflowing.
|
|
// Nevertheless, since this is only a possibility of overflow
|
|
// no error should be issued here.
|
|
if (ResourceTracker->canReserveResources(*Ext)) {
|
|
ResourceTracker->reserveResources(*Ext);
|
|
LLVM_DEBUG(dbgs() << "\t[AddToPacket] (" << CurrentPacketMIs.size()
|
|
<< ") adding:\t immext_i\n");
|
|
CurrentPacketMIs.push_back(Ext);
|
|
CurrentState.HomeBundle.push_back(Ext);
|
|
return true;
|
|
} else {
|
|
LLVM_DEBUG(dbgs() << "\t Previous overflow possible.\n");
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
void HexagonGlobalSchedulerImpl::checkBundleCounts(MachineFunction &Fn) {
|
|
if (DisableCheckBundles)
|
|
return;
|
|
|
|
unsigned BundleLimit = 4;
|
|
|
|
for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end();
|
|
MBBi != MBBe; ++MBBi) {
|
|
|
|
for (MachineBasicBlock::iterator MI = MBBi->instr_begin(),
|
|
ME = MBBi->instr_end();
|
|
MI != ME; ++MI) {
|
|
if (MI->isBundle()) {
|
|
MachineBasicBlock::instr_iterator MII = MI.getInstrIterator();
|
|
MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
|
|
|
|
unsigned InstrCount = 0;
|
|
|
|
for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
|
|
if (MII->getOpcode() == TargetOpcode::DBG_VALUE ||
|
|
MII->getOpcode() == TargetOpcode::IMPLICIT_DEF ||
|
|
MII->getOpcode() == TargetOpcode::CFI_INSTRUCTION ||
|
|
MII->isEHLabel() || QII->isEndLoopN(MII->getOpcode())) {
|
|
continue;
|
|
} else {
|
|
InstrCount++;
|
|
}
|
|
}
|
|
if (InstrCount > BundleLimit) {
|
|
if (WarnOnBundleSize) {
|
|
LLVM_DEBUG(dbgs() << "Warning bundle size exceeded " << *MI);
|
|
} else {
|
|
assert(0 && "Bundle size exceeded");
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/// Debugging only. Count compound and duplex opportunities.
|
|
unsigned HexagonGlobalSchedulerImpl::countCompounds(MachineFunction &Fn) {
|
|
unsigned CompoundCount = 0;
|
|
[[maybe_unused]] unsigned DuplexCount = 0;
|
|
[[maybe_unused]] unsigned InstOffset = 0;
|
|
|
|
// Loop over all basic blocks.
|
|
for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
|
|
++MBB) {
|
|
LLVM_DEBUG(dbgs() << "\n BB#" << MBB->getNumber() << " " << MBB->getName()
|
|
<< " in_func "
|
|
<< MBB->getParent()->getFunction().getName() << " \n");
|
|
for (MachineBasicBlock::iterator MI = MBB->instr_begin(),
|
|
ME = MBB->instr_end();
|
|
MI != ME; ++MI) {
|
|
if (MI->isDebugInstr())
|
|
continue;
|
|
if (MI->isBundle()) {
|
|
MachineBasicBlock::instr_iterator MII = MI.getInstrIterator();
|
|
MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
|
|
MachineInstr *FirstCompound = NULL, *SecondCompound = NULL;
|
|
MachineInstr *FirstDuplex = NULL, *SecondDuplex = NULL;
|
|
LLVM_DEBUG(dbgs() << "{\n");
|
|
|
|
for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
|
|
++MII) {
|
|
if (MII->isDebugInstr())
|
|
continue;
|
|
LLVM_DEBUG(dbgs() << "(" << InstOffset << ")\t");
|
|
InstOffset += QII->getSize(*MII);
|
|
if (QII->getCompoundCandidateGroup(*MII)) {
|
|
if (!FirstCompound) {
|
|
FirstCompound = &*MII;
|
|
LLVM_DEBUG(dbgs() << "XX ");
|
|
} else {
|
|
SecondCompound = &*MII;
|
|
LLVM_DEBUG(dbgs() << "YY ");
|
|
}
|
|
}
|
|
if (QII->getDuplexCandidateGroup(*MII)) {
|
|
if (!FirstDuplex) {
|
|
FirstDuplex = &*MII;
|
|
LLVM_DEBUG(dbgs() << "AA ");
|
|
} else {
|
|
SecondDuplex = &*MII;
|
|
LLVM_DEBUG(dbgs() << "VV ");
|
|
}
|
|
}
|
|
LLVM_DEBUG(MII->dump());
|
|
}
|
|
LLVM_DEBUG(dbgs() << "}\n");
|
|
if (SecondCompound) {
|
|
if (isCompoundPair(FirstCompound, SecondCompound)) {
|
|
LLVM_DEBUG(dbgs() << "Compound pair (" << CompoundCount << ")\n");
|
|
CompoundCount++;
|
|
}
|
|
}
|
|
if (SecondDuplex) {
|
|
if (QII->isDuplexPair(*FirstDuplex, *SecondDuplex)) {
|
|
LLVM_DEBUG(dbgs() << "Duplex pair (" << DuplexCount << ")\n");
|
|
DuplexCount++;
|
|
}
|
|
}
|
|
} else {
|
|
LLVM_DEBUG(dbgs() << "(" << InstOffset << ")\t");
|
|
if (QII->getCompoundCandidateGroup(*MI))
|
|
LLVM_DEBUG(dbgs() << "XX ");
|
|
if (QII->getDuplexCandidateGroup(*MI))
|
|
LLVM_DEBUG(dbgs() << "AA ");
|
|
InstOffset += QII->getSize(*MI);
|
|
LLVM_DEBUG(MI->dump());
|
|
}
|
|
}
|
|
}
|
|
LLVM_DEBUG(dbgs() << "Total compound(" << CompoundCount << ") duplex("
|
|
<< DuplexCount << ")\n");
|
|
return CompoundCount;
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// Public Constructor Functions
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
FunctionPass *llvm::createHexagonGlobalScheduler() {
|
|
return new HexagonGlobalScheduler();
|
|
}
|