90#define DEBUG_TYPE "hexagon-eif"
97 cl::desc(
"Size limit in Hexagon early if-conversion"));
110 return OS <<
"<none>";
111 return OS <<
'#' <<
P.MB->getNumber();
115 FlowPattern() =
default;
118 : SplitB(
B), TrueB(
TB), FalseB(FB), JoinB(JB), PredR(PR) {}
131 const FlowPattern &
FP;
138 OS <<
"{ SplitB:" << PrintMB(
P.FP.SplitB)
140 <<
", TrueB:" << PrintMB(
P.FP.TrueB)
141 <<
", FalseB:" << PrintMB(
P.FP.FalseB)
142 <<
", JoinB:" << PrintMB(
P.FP.JoinB) <<
" }";
153 return "Hexagon early if conversion";
179 bool isValid(
const FlowPattern &
FP)
const;
182 const FlowPattern &
FP)
const;
186 bool isPredicate(
unsigned R)
const;
188 unsigned getCondStoreOpcode(
unsigned Opc,
bool IfTrue)
const;
193 unsigned PredR,
bool IfTrue);
197 unsigned TSR,
unsigned FR,
unsigned FSR);
199 void convert(
const FlowPattern &
FP);
204 void simplifyFlowGraph(
const FlowPattern &
FP);
218char HexagonEarlyIfConversion::ID = 0;
221 "Hexagon early if conversion",
false,
false)
224 if (
B->succ_size() != 1)
228 return L && SB == L->getHeader() && MDT->dominates(
B, SB);
243 unsigned Opc = T1I->getOpcode();
244 if (
Opc != Hexagon::J2_jumpt &&
Opc != Hexagon::J2_jumpf)
246 Register PredR = T1I->getOperand(0).getReg();
255 assert(T2I ==
B->end() || T2I->getOpcode() == Hexagon::J2_jump);
257 : T2I->getOperand(0).getMBB();
266 if (
Opc == Hexagon::J2_jumpt)
271 if (!MDT->properlyDominates(
B, TB) || !MDT->properlyDominates(
B, FB))
278 assert(TB && FB &&
"Failed to find triangle control flow blocks");
279 unsigned TNP =
TB->pred_size(), FNP = FB->pred_size();
280 unsigned TNS =
TB->succ_size(), FNS = FB->succ_size();
287 bool TOk = (TNP == 1 && TNS == 1 && MLI->getLoopFor(TB) ==
L);
288 bool FOk = (FNP == 1 && FNS == 1 && MLI->getLoopFor(FB) ==
L);
321 if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) {
322 LLVM_DEBUG(
dbgs() <<
"One of blocks " << PrintMB(TB) <<
", " << PrintMB(FB)
323 <<
" is a loop preheader. Skipping.\n");
327 FP = FlowPattern(
B, PredR, TB, FB, JB);
358 if (
B->isEHPad() ||
B->hasAddressTaken())
363 for (
auto &
MI : *
B) {
364 if (
MI.isDebugInstr())
366 if (
MI.isConditionalBranch())
368 unsigned Opc =
MI.getOpcode();
369 bool IsJMP = (
Opc == Hexagon::J2_jump);
370 if (!isPredicableStore(&
MI) && !IsJMP && !isSafeToSpeculate(&
MI))
379 if (!MO.isReg() || !MO.isDef())
387 if (
U.getParent()->isPHI())
394bool HexagonEarlyIfConversion::usesUndefVReg(
const MachineInstr *
MI)
const {
396 if (!MO.isReg() || !MO.isUse())
403 assert(DefI &&
"Expecting a reaching def in MRI");
410bool HexagonEarlyIfConversion::isValid(
const FlowPattern &
FP)
const {
411 if (hasEHLabel(
FP.SplitB))
413 if (
FP.TrueB && !isValidCandidate(
FP.TrueB))
415 if (
FP.FalseB && !isValidCandidate(
FP.FalseB))
432 if (usesUndefVReg(&
MI))
435 if (isPredicate(DefR))
443 const FlowPattern &
FP)
const {
444 if (
B->pred_size() < 2)
456 for (
unsigned i = 1, e =
MI.getNumOperands(); i != e; i += 2) {
458 if (BB ==
FP.SplitB || BB ==
FP.TrueB || BB ==
FP.FalseB)
475 if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3))
481unsigned HexagonEarlyIfConversion::countPredicateDefs(
483 unsigned PredDefs = 0;
484 for (
auto &
MI : *
B) {
486 if (!MO.isReg() || !MO.isDef())
498bool HexagonEarlyIfConversion::isProfitable(
const FlowPattern &
FP)
const {
501 if (MBPI &&
FP.TrueB && !
FP.FalseB &&
502 (MBPI->getEdgeProbability(
FP.SplitB,
FP.TrueB) < JumpProb ||
503 MBPI->getEdgeProbability(
FP.SplitB,
FP.TrueB) > Prob))
506 if (MBPI && !
FP.TrueB &&
FP.FalseB &&
507 (MBPI->getEdgeProbability(
FP.SplitB,
FP.FalseB) < JumpProb ||
508 MBPI->getEdgeProbability(
FP.SplitB,
FP.FalseB) > Prob))
511 if (
FP.TrueB &&
FP.FalseB) {
514 if (MBPI->getEdgeProbability(
FP.SplitB,
FP.TrueB) > Prob)
516 if (MBPI->getEdgeProbability(
FP.SplitB,
FP.FalseB) > Prob)
538 unsigned T = std::count_if(
B->begin(),
B->getFirstTerminator(),
540 return !MI.isMetaInstruction();
547 unsigned TotalIn = TotalCount(
FP.TrueB, Spare) + TotalCount(
FP.FalseB, Spare);
549 dbgs() <<
"Total number of instructions to be predicated/speculated: "
550 << TotalIn <<
", spare room: " << Spare <<
"\n");
560 unsigned TotalPh = 0;
561 unsigned PredDefs = countPredicateDefs(
FP.SplitB);
563 TotalPh = computePhiCost(
FP.JoinB,
FP);
564 PredDefs += countPredicateDefs(
FP.JoinB);
566 if (
FP.TrueB && !
FP.TrueB->succ_empty()) {
568 TotalPh += computePhiCost(SB,
FP);
569 PredDefs += countPredicateDefs(SB);
571 if (
FP.FalseB && !
FP.FalseB->succ_empty()) {
573 TotalPh += computePhiCost(SB,
FP);
574 PredDefs += countPredicateDefs(SB);
577 LLVM_DEBUG(
dbgs() <<
"Total number of extra muxes from converted phis: "
582 LLVM_DEBUG(
dbgs() <<
"Total number of predicate registers: " << PredDefs
592 bool Changed =
false;
605 DTNodeVectType Cn(llvm::children<MachineDomTreeNode *>(
N));
609 Changed |= visitBlock(SB, L);
614 if (MLI->getLoopFor(
B) != L)
618 if (!matchFlowPattern(
B, L,
FP))
631 simplifyFlowGraph(
FP);
635bool HexagonEarlyIfConversion::visitLoop(
MachineLoop *L) {
638 :
dbgs() <<
"Visiting function")
640 bool Changed =
false;
643 Changed |= visitLoop(
I);
647 Changed |= visitBlock(L ? HB : EntryB, L);
651bool HexagonEarlyIfConversion::isPredicableStore(
const MachineInstr *
MI)
656 unsigned Opc =
MI->getOpcode();
658 case Hexagon::S2_storerb_io:
659 case Hexagon::S2_storerbnew_io:
660 case Hexagon::S2_storerh_io:
661 case Hexagon::S2_storerhnew_io:
662 case Hexagon::S2_storeri_io:
663 case Hexagon::S2_storerinew_io:
664 case Hexagon::S2_storerd_io:
665 case Hexagon::S4_storeirb_io:
666 case Hexagon::S4_storeirh_io:
667 case Hexagon::S4_storeiri_io:
675bool HexagonEarlyIfConversion::isSafeToSpeculate(
const MachineInstr *
MI)
677 if (
MI->mayLoadOrStore())
679 if (
MI->isCall() ||
MI->isBarrier() ||
MI->isBranch())
681 if (
MI->hasUnmodeledSideEffects())
683 if (
MI->getOpcode() == TargetOpcode::LIFETIME_END)
689bool HexagonEarlyIfConversion::isPredicate(
unsigned R)
const {
691 return RC == &Hexagon::PredRegsRegClass ||
692 RC == &Hexagon::HvxQRRegClass;
695unsigned HexagonEarlyIfConversion::getCondStoreOpcode(
unsigned Opc,
697 return HII->getCondOpcode(
Opc, !IfTrue);
702 unsigned PredR,
bool IfTrue) {
704 if (At != ToB->
end())
705 DL = At->getDebugLoc();
706 else if (!ToB->
empty())
709 unsigned Opc =
MI->getOpcode();
711 if (isPredicableStore(
MI)) {
712 unsigned COpc = getCondStoreOpcode(
Opc, IfTrue);
716 if (HII->isPostIncrement(*
MI)) {
727 MI->eraseFromParent();
731 if (
Opc == Hexagon::J2_jump) {
733 const MCInstrDesc &
D = HII->get(IfTrue ? Hexagon::J2_jumpt
734 : Hexagon::J2_jumpf);
738 MI->eraseFromParent();
753 unsigned PredR,
bool IfTrue) {
754 LLVM_DEBUG(
dbgs() <<
"Predicating block " << PrintMB(FromB) <<
"\n");
760 NextI = std::next(
I);
761 if (isSafeToSpeculate(&*
I))
764 predicateInstr(ToB, At, &*
I, PredR, IfTrue);
770 unsigned PredR,
unsigned TR,
unsigned TSR,
unsigned FR,
unsigned FSR) {
772 switch (DRC->
getID()) {
773 case Hexagon::IntRegsRegClassID:
774 case Hexagon::IntRegsLow8RegClassID:
775 Opc = Hexagon::C2_mux;
777 case Hexagon::DoubleRegsRegClassID:
778 case Hexagon::GeneralDoubleLow8RegsRegClassID:
779 Opc = Hexagon::PS_pselect;
781 case Hexagon::HvxVRRegClassID:
782 Opc = Hexagon::PS_vselect;
784 case Hexagon::HvxWRRegClassID:
785 Opc = Hexagon::PS_wselect;
802 const FlowPattern &
FP) {
806 for (
auto I = WhereB->
begin();
I != NonPHI; ++
I) {
809 unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0;
812 if (BO.getMBB() ==
FP.SplitB)
814 else if (BO.getMBB() ==
FP.TrueB)
816 else if (BO.getMBB() ==
FP.FalseB)
829 unsigned MuxR = 0, MuxSR = 0;
834 MuxR = buildMux(
FP.SplitB,
FP.SplitB->getFirstTerminator(), RC,
835 FP.PredR, TR, TSR, FR, FSR);
845 false,
false, MuxSR));
850void HexagonEarlyIfConversion::convert(
const FlowPattern &
FP) {
857 TSB = *
FP.TrueB->succ_begin();
858 predicateBlockNB(
FP.SplitB, OldTI,
FP.TrueB,
FP.PredR,
true);
861 FSB = *
FP.FalseB->succ_begin();
863 predicateBlockNB(
FP.SplitB, At,
FP.FalseB,
FP.PredR,
false);
870 FP.SplitB->erase(OldTI,
FP.SplitB->end());
871 while (!
FP.SplitB->succ_empty()) {
887 if (
T !=
FP.TrueB &&
T !=
FP.FalseB) {
891 FP.SplitB->removeSuccessor(
FP.SplitB->succ_begin());
900 BuildMI(*
FP.SplitB,
FP.SplitB->end(),
DL, HII->get(Hexagon::J2_jump))
902 FP.SplitB->addSuccessor(
FP.JoinB);
904 bool HasBranch =
false;
906 BuildMI(*
FP.SplitB,
FP.SplitB->end(),
DL, HII->get(Hexagon::J2_jumpt))
909 FP.SplitB->addSuccessor(TSB);
913 const MCInstrDesc &
D = HasBranch ? HII->get(Hexagon::J2_jump)
914 : HII->get(Hexagon::J2_jumpf);
919 FP.SplitB->addSuccessor(FSB);
926 BuildMI(*
FP.SplitB,
FP.SplitB->end(),
DL, HII->get(Hexagon::J2_jump))
928 FP.SplitB->addSuccessor(SSB);
957 DTNodeVectType Cn(GTN::child_begin(
N), GTN::child_end(
N));
960 MDT->changeImmediateDominator(SB, IDB);
964 while (!
B->succ_empty())
965 B->removeSuccessor(
B->succ_begin());
968 Pred->removeSuccessor(
B,
true);
972 MFN->erase(
B->getIterator());
976 LLVM_DEBUG(
dbgs() <<
"Removing phi nodes from block " << PrintMB(
B) <<
"\n");
978 for (
I =
B->begin();
I != NonPHI;
I = NextI) {
979 NextI = std::next(
I);
985 unsigned NewR = UseR;
992 NewR =
MRI->createVirtualRegister(RC);
993 NonPHI =
BuildMI(*
B, NonPHI,
DL, HII->get(TargetOpcode::COPY), NewR)
996 MRI->replaceRegWith(DefR, NewR);
1003 LLVM_DEBUG(
dbgs() <<
"Merging blocks " << PrintMB(PredB) <<
" and "
1004 << PrintMB(SuccB) <<
"\n");
1005 bool TermOk = hasUncondBranch(SuccB);
1006 eliminatePhis(SuccB);
1007 HII->removeBranch(*PredB);
1017void HexagonEarlyIfConversion::simplifyFlowGraph(
const FlowPattern &
FP) {
1020 removeBlock(
FP.TrueB);
1022 removeBlock(
FP.FalseB);
1024 FP.SplitB->updateTerminator(OldLayoutSuccessor);
1025 if (
FP.SplitB->succ_size() != 1)
1037 if (!hasEHLabel(SB) || hasUncondBranch(SB))
1038 mergeBlocks(
FP.SplitB, SB);
1041bool HexagonEarlyIfConversion::runOnMachineFunction(
MachineFunction &MF) {
1046 HII =
ST.getInstrInfo();
1047 TRI =
ST.getRegisterInfo();
1050 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1051 MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1053 ? &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI()
1057 bool Changed =
false;
1060 Changed |= visitLoop(L);
1061 Changed |= visitLoop(
nullptr);
1070 return new HexagonEarlyIfConversion();
unsigned const MachineRegisterInfo * MRI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_ATTRIBUTE_UNUSED
This file defines the DenseSet and SmallDenseSet classes.
static cl::opt< bool > EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden, cl::init(true), cl::desc("Enable branch probability info"))
static cl::opt< bool > SkipExitBranches("eif-no-loop-exit", cl::init(false), cl::Hidden, cl::desc("Do not convert branches that may exit the loop"))
static cl::opt< unsigned > SizeLimit("eif-limit", cl::init(6), cl::Hidden, cl::desc("Size limit in Hexagon early if-conversion"))
#define HEXAGON_PACKET_SIZE
Register const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
This file defines the SmallVector class.
static bool isProfitable(const StableFunctionMap::StableFunctionEntries &SFS)
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Implements a dense probed hash-table based set.
Base class for the actual dominator tree node.
FunctionPass class - This class is used to implement most global optimizations.
Describe properties that are true of each instruction in the target description file.
unsigned pred_size() const
LLVM_ABI void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
LLVM_ABI void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
succ_iterator succ_begin()
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
LLVM_ABI void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
LLVM_ABI iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
const MachineInstrBuilder & cloneMemRefs(const MachineInstr &OtherMI) const
Representation of each machine instruction.
bool isImplicitDef() const
unsigned getNumOperands() const
Retuns the total number of operands.
LLVM_ABI void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
LLVM_ABI void removeOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Wrapper class representing virtual and physical registers.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
unsigned getID() const
Return the register class ID number.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
This class implements an extremely fast bulk output stream that can only output to a stream.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
FunctionPass * createHexagonEarlyIfConversion()
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
LLVM_ABI void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *Until=nullptr)
Replaces all uses of OldPred with the NewPred block in all PHINodes in a block.
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.