BranchFolding.cpp 78 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036
  1. //===- BranchFolding.cpp - Fold machine code branch instructions ----------===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. // This pass forwards branches to unconditional branches to make them branch
  10. // directly to the target block. This pass often results in dead MBB's, which
  11. // it then removes.
  12. //
  13. // Note that this pass must be run after register allocation, it cannot handle
  14. // SSA form. It also must handle virtual registers for targets that emit virtual
  15. // ISA (e.g. NVPTX).
  16. //
  17. //===----------------------------------------------------------------------===//
  18. #include "BranchFolding.h"
  19. #include "llvm/ADT/BitVector.h"
  20. #include "llvm/ADT/STLExtras.h"
  21. #include "llvm/ADT/SmallSet.h"
  22. #include "llvm/ADT/SmallVector.h"
  23. #include "llvm/ADT/Statistic.h"
  24. #include "llvm/Analysis/ProfileSummaryInfo.h"
  25. #include "llvm/CodeGen/Analysis.h"
  26. #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  27. #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  28. #include "llvm/CodeGen/MachineFunction.h"
  29. #include "llvm/CodeGen/MachineFunctionPass.h"
  30. #include "llvm/CodeGen/MachineInstr.h"
  31. #include "llvm/CodeGen/MachineInstrBuilder.h"
  32. #include "llvm/CodeGen/MachineJumpTableInfo.h"
  33. #include "llvm/CodeGen/MachineLoopInfo.h"
  34. #include "llvm/CodeGen/MachineModuleInfo.h"
  35. #include "llvm/CodeGen/MachineOperand.h"
  36. #include "llvm/CodeGen/MachineRegisterInfo.h"
  37. #include "llvm/CodeGen/MachineSizeOpts.h"
  38. #include "llvm/CodeGen/MBFIWrapper.h"
  39. #include "llvm/CodeGen/TargetInstrInfo.h"
  40. #include "llvm/CodeGen/TargetOpcodes.h"
  41. #include "llvm/CodeGen/TargetPassConfig.h"
  42. #include "llvm/CodeGen/TargetRegisterInfo.h"
  43. #include "llvm/CodeGen/TargetSubtargetInfo.h"
  44. #include "llvm/IR/DebugInfoMetadata.h"
  45. #include "llvm/IR/DebugLoc.h"
  46. #include "llvm/IR/Function.h"
  47. #include "llvm/InitializePasses.h"
  48. #include "llvm/MC/LaneBitmask.h"
  49. #include "llvm/MC/MCRegisterInfo.h"
  50. #include "llvm/Pass.h"
  51. #include "llvm/Support/BlockFrequency.h"
  52. #include "llvm/Support/BranchProbability.h"
  53. #include "llvm/Support/CommandLine.h"
  54. #include "llvm/Support/Debug.h"
  55. #include "llvm/Support/ErrorHandling.h"
  56. #include "llvm/Support/raw_ostream.h"
  57. #include "llvm/Target/TargetMachine.h"
  58. #include <cassert>
  59. #include <cstddef>
  60. #include <iterator>
  61. #include <numeric>
  62. using namespace llvm;
  63. #define DEBUG_TYPE "branch-folder"
  64. STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
  65. STATISTIC(NumBranchOpts, "Number of branches optimized");
  66. STATISTIC(NumTailMerge , "Number of block tails merged");
  67. STATISTIC(NumHoist , "Number of times common instructions are hoisted");
  68. STATISTIC(NumTailCalls, "Number of tail calls optimized");
  69. static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
  70. cl::init(cl::BOU_UNSET), cl::Hidden);
  71. // Throttle for huge numbers of predecessors (compile speed problems)
  72. static cl::opt<unsigned>
  73. TailMergeThreshold("tail-merge-threshold",
  74. cl::desc("Max number of predecessors to consider tail merging"),
  75. cl::init(150), cl::Hidden);
  76. // Heuristic for tail merging (and, inversely, tail duplication).
  77. // TODO: This should be replaced with a target query.
  78. static cl::opt<unsigned>
  79. TailMergeSize("tail-merge-size",
  80. cl::desc("Min number of instructions to consider tail merging"),
  81. cl::init(3), cl::Hidden);
  82. namespace {
  83. /// BranchFolderPass - Wrap branch folder in a machine function pass.
  84. class BranchFolderPass : public MachineFunctionPass {
  85. public:
  86. static char ID;
  87. explicit BranchFolderPass(): MachineFunctionPass(ID) {}
  88. bool runOnMachineFunction(MachineFunction &MF) override;
  89. void getAnalysisUsage(AnalysisUsage &AU) const override {
  90. AU.addRequired<MachineBlockFrequencyInfo>();
  91. AU.addRequired<MachineBranchProbabilityInfo>();
  92. AU.addRequired<ProfileSummaryInfoWrapperPass>();
  93. AU.addRequired<TargetPassConfig>();
  94. MachineFunctionPass::getAnalysisUsage(AU);
  95. }
  96. };
  97. } // end anonymous namespace
  98. char BranchFolderPass::ID = 0;
  99. char &llvm::BranchFolderPassID = BranchFolderPass::ID;
  100. INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE,
  101. "Control Flow Optimizer", false, false)
  102. bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
  103. if (skipFunction(MF.getFunction()))
  104. return false;
  105. TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
  106. // TailMerge can create jump into if branches that make CFG irreducible for
  107. // HW that requires structurized CFG.
  108. bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
  109. PassConfig->getEnableTailMerge();
  110. MBFIWrapper MBBFreqInfo(
  111. getAnalysis<MachineBlockFrequencyInfo>());
  112. BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true, MBBFreqInfo,
  113. getAnalysis<MachineBranchProbabilityInfo>(),
  114. &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
  115. return Folder.OptimizeFunction(MF, MF.getSubtarget().getInstrInfo(),
  116. MF.getSubtarget().getRegisterInfo());
  117. }
  118. BranchFolder::BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,
  119. MBFIWrapper &FreqInfo,
  120. const MachineBranchProbabilityInfo &ProbInfo,
  121. ProfileSummaryInfo *PSI, unsigned MinTailLength)
  122. : EnableHoistCommonCode(CommonHoist), MinCommonTailLength(MinTailLength),
  123. MBBFreqInfo(FreqInfo), MBPI(ProbInfo), PSI(PSI) {
  124. if (MinCommonTailLength == 0)
  125. MinCommonTailLength = TailMergeSize;
  126. switch (FlagEnableTailMerge) {
  127. case cl::BOU_UNSET:
  128. EnableTailMerge = DefaultEnableTailMerge;
  129. break;
  130. case cl::BOU_TRUE: EnableTailMerge = true; break;
  131. case cl::BOU_FALSE: EnableTailMerge = false; break;
  132. }
  133. }
  134. void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
  135. assert(MBB->pred_empty() && "MBB must be dead!");
  136. LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
  137. MachineFunction *MF = MBB->getParent();
  138. // drop all successors.
  139. while (!MBB->succ_empty())
  140. MBB->removeSuccessor(MBB->succ_end()-1);
  141. // Avoid matching if this pointer gets reused.
  142. TriedMerging.erase(MBB);
  143. // Update call site info.
  144. std::for_each(MBB->begin(), MBB->end(), [MF](const MachineInstr &MI) {
  145. if (MI.shouldUpdateCallSiteInfo())
  146. MF->eraseCallSiteInfo(&MI);
  147. });
  148. // Remove the block.
  149. MF->erase(MBB);
  150. EHScopeMembership.erase(MBB);
  151. if (MLI)
  152. MLI->removeBlock(MBB);
  153. }
  154. bool BranchFolder::OptimizeFunction(MachineFunction &MF,
  155. const TargetInstrInfo *tii,
  156. const TargetRegisterInfo *tri,
  157. MachineLoopInfo *mli, bool AfterPlacement) {
  158. if (!tii) return false;
  159. TriedMerging.clear();
  160. MachineRegisterInfo &MRI = MF.getRegInfo();
  161. AfterBlockPlacement = AfterPlacement;
  162. TII = tii;
  163. TRI = tri;
  164. MLI = mli;
  165. this->MRI = &MRI;
  166. UpdateLiveIns = MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF);
  167. if (!UpdateLiveIns)
  168. MRI.invalidateLiveness();
  169. bool MadeChange = false;
  170. // Recalculate EH scope membership.
  171. EHScopeMembership = getEHScopeMembership(MF);
  172. bool MadeChangeThisIteration = true;
  173. while (MadeChangeThisIteration) {
  174. MadeChangeThisIteration = TailMergeBlocks(MF);
  175. // No need to clean up if tail merging does not change anything after the
  176. // block placement.
  177. if (!AfterBlockPlacement || MadeChangeThisIteration)
  178. MadeChangeThisIteration |= OptimizeBranches(MF);
  179. if (EnableHoistCommonCode)
  180. MadeChangeThisIteration |= HoistCommonCode(MF);
  181. MadeChange |= MadeChangeThisIteration;
  182. }
  183. // See if any jump tables have become dead as the code generator
  184. // did its thing.
  185. MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
  186. if (!JTI)
  187. return MadeChange;
  188. // Walk the function to find jump tables that are live.
  189. BitVector JTIsLive(JTI->getJumpTables().size());
  190. for (const MachineBasicBlock &BB : MF) {
  191. for (const MachineInstr &I : BB)
  192. for (const MachineOperand &Op : I.operands()) {
  193. if (!Op.isJTI()) continue;
  194. // Remember that this JT is live.
  195. JTIsLive.set(Op.getIndex());
  196. }
  197. }
  198. // Finally, remove dead jump tables. This happens when the
  199. // indirect jump was unreachable (and thus deleted).
  200. for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
  201. if (!JTIsLive.test(i)) {
  202. JTI->RemoveJumpTable(i);
  203. MadeChange = true;
  204. }
  205. return MadeChange;
  206. }
  207. //===----------------------------------------------------------------------===//
  208. // Tail Merging of Blocks
  209. //===----------------------------------------------------------------------===//
  210. /// HashMachineInstr - Compute a hash value for MI and its operands.
  211. static unsigned HashMachineInstr(const MachineInstr &MI) {
  212. unsigned Hash = MI.getOpcode();
  213. for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
  214. const MachineOperand &Op = MI.getOperand(i);
  215. // Merge in bits from the operand if easy. We can't use MachineOperand's
  216. // hash_code here because it's not deterministic and we sort by hash value
  217. // later.
  218. unsigned OperandHash = 0;
  219. switch (Op.getType()) {
  220. case MachineOperand::MO_Register:
  221. OperandHash = Op.getReg();
  222. break;
  223. case MachineOperand::MO_Immediate:
  224. OperandHash = Op.getImm();
  225. break;
  226. case MachineOperand::MO_MachineBasicBlock:
  227. OperandHash = Op.getMBB()->getNumber();
  228. break;
  229. case MachineOperand::MO_FrameIndex:
  230. case MachineOperand::MO_ConstantPoolIndex:
  231. case MachineOperand::MO_JumpTableIndex:
  232. OperandHash = Op.getIndex();
  233. break;
  234. case MachineOperand::MO_GlobalAddress:
  235. case MachineOperand::MO_ExternalSymbol:
  236. // Global address / external symbol are too hard, don't bother, but do
  237. // pull in the offset.
  238. OperandHash = Op.getOffset();
  239. break;
  240. default:
  241. break;
  242. }
  243. Hash += ((OperandHash << 3) | Op.getType()) << (i & 31);
  244. }
  245. return Hash;
  246. }
  247. /// HashEndOfMBB - Hash the last instruction in the MBB.
  248. static unsigned HashEndOfMBB(const MachineBasicBlock &MBB) {
  249. MachineBasicBlock::const_iterator I = MBB.getLastNonDebugInstr();
  250. if (I == MBB.end())
  251. return 0;
  252. return HashMachineInstr(*I);
  253. }
  254. /// Whether MI should be counted as an instruction when calculating common tail.
  255. static bool countsAsInstruction(const MachineInstr &MI) {
  256. return !(MI.isDebugInstr() || MI.isCFIInstruction());
  257. }
  258. /// Iterate backwards from the given iterator \p I, towards the beginning of the
  259. /// block. If a MI satisfying 'countsAsInstruction' is found, return an iterator
  260. /// pointing to that MI. If no such MI is found, return the end iterator.
  261. static MachineBasicBlock::iterator
  262. skipBackwardPastNonInstructions(MachineBasicBlock::iterator I,
  263. MachineBasicBlock *MBB) {
  264. while (I != MBB->begin()) {
  265. --I;
  266. if (countsAsInstruction(*I))
  267. return I;
  268. }
  269. return MBB->end();
  270. }
  271. /// Given two machine basic blocks, return the number of instructions they
  272. /// actually have in common together at their end. If a common tail is found (at
  273. /// least by one instruction), then iterators for the first shared instruction
  274. /// in each block are returned as well.
  275. ///
  276. /// Non-instructions according to countsAsInstruction are ignored.
  277. static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
  278. MachineBasicBlock *MBB2,
  279. MachineBasicBlock::iterator &I1,
  280. MachineBasicBlock::iterator &I2) {
  281. MachineBasicBlock::iterator MBBI1 = MBB1->end();
  282. MachineBasicBlock::iterator MBBI2 = MBB2->end();
  283. unsigned TailLen = 0;
  284. while (true) {
  285. MBBI1 = skipBackwardPastNonInstructions(MBBI1, MBB1);
  286. MBBI2 = skipBackwardPastNonInstructions(MBBI2, MBB2);
  287. if (MBBI1 == MBB1->end() || MBBI2 == MBB2->end())
  288. break;
  289. if (!MBBI1->isIdenticalTo(*MBBI2) ||
  290. // FIXME: This check is dubious. It's used to get around a problem where
  291. // people incorrectly expect inline asm directives to remain in the same
  292. // relative order. This is untenable because normal compiler
  293. // optimizations (like this one) may reorder and/or merge these
  294. // directives.
  295. MBBI1->isInlineAsm()) {
  296. break;
  297. }
  298. if (MBBI1->getFlag(MachineInstr::NoMerge) ||
  299. MBBI2->getFlag(MachineInstr::NoMerge))
  300. break;
  301. ++TailLen;
  302. I1 = MBBI1;
  303. I2 = MBBI2;
  304. }
  305. return TailLen;
  306. }
  307. void BranchFolder::replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
  308. MachineBasicBlock &NewDest) {
  309. if (UpdateLiveIns) {
  310. // OldInst should always point to an instruction.
  311. MachineBasicBlock &OldMBB = *OldInst->getParent();
  312. LiveRegs.clear();
  313. LiveRegs.addLiveOuts(OldMBB);
  314. // Move backward to the place where will insert the jump.
  315. MachineBasicBlock::iterator I = OldMBB.end();
  316. do {
  317. --I;
  318. LiveRegs.stepBackward(*I);
  319. } while (I != OldInst);
  320. // Merging the tails may have switched some undef operand to non-undef ones.
  321. // Add IMPLICIT_DEFS into OldMBB as necessary to have a definition of the
  322. // register.
  323. for (MachineBasicBlock::RegisterMaskPair P : NewDest.liveins()) {
  324. // We computed the liveins with computeLiveIn earlier and should only see
  325. // full registers:
  326. assert(P.LaneMask == LaneBitmask::getAll() &&
  327. "Can only handle full register.");
  328. MCPhysReg Reg = P.PhysReg;
  329. if (!LiveRegs.available(*MRI, Reg))
  330. continue;
  331. DebugLoc DL;
  332. BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);
  333. }
  334. }
  335. TII->ReplaceTailWithBranchTo(OldInst, &NewDest);
  336. ++NumTailMerge;
  337. }
  338. MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
  339. MachineBasicBlock::iterator BBI1,
  340. const BasicBlock *BB) {
  341. if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
  342. return nullptr;
  343. MachineFunction &MF = *CurMBB.getParent();
  344. // Create the fall-through block.
  345. MachineFunction::iterator MBBI = CurMBB.getIterator();
  346. MachineBasicBlock *NewMBB = MF.CreateMachineBasicBlock(BB);
  347. CurMBB.getParent()->insert(++MBBI, NewMBB);
  348. // Move all the successors of this block to the specified block.
  349. NewMBB->transferSuccessors(&CurMBB);
  350. // Add an edge from CurMBB to NewMBB for the fall-through.
  351. CurMBB.addSuccessor(NewMBB);
  352. // Splice the code over.
  353. NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
  354. // NewMBB belongs to the same loop as CurMBB.
  355. if (MLI)
  356. if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))
  357. ML->addBasicBlockToLoop(NewMBB, MLI->getBase());
  358. // NewMBB inherits CurMBB's block frequency.
  359. MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
  360. if (UpdateLiveIns)
  361. computeAndAddLiveIns(LiveRegs, *NewMBB);
  362. // Add the new block to the EH scope.
  363. const auto &EHScopeI = EHScopeMembership.find(&CurMBB);
  364. if (EHScopeI != EHScopeMembership.end()) {
  365. auto n = EHScopeI->second;
  366. EHScopeMembership[NewMBB] = n;
  367. }
  368. return NewMBB;
  369. }
  370. /// EstimateRuntime - Make a rough estimate for how long it will take to run
  371. /// the specified code.
  372. static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
  373. MachineBasicBlock::iterator E) {
  374. unsigned Time = 0;
  375. for (; I != E; ++I) {
  376. if (!countsAsInstruction(*I))
  377. continue;
  378. if (I->isCall())
  379. Time += 10;
  380. else if (I->mayLoadOrStore())
  381. Time += 2;
  382. else
  383. ++Time;
  384. }
  385. return Time;
  386. }
  387. // CurMBB needs to add an unconditional branch to SuccMBB (we removed these
  388. // branches temporarily for tail merging). In the case where CurMBB ends
  389. // with a conditional branch to the next block, optimize by reversing the
  390. // test and conditionally branching to SuccMBB instead.
  391. static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
  392. const TargetInstrInfo *TII) {
  393. MachineFunction *MF = CurMBB->getParent();
  394. MachineFunction::iterator I = std::next(MachineFunction::iterator(CurMBB));
  395. MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
  396. SmallVector<MachineOperand, 4> Cond;
  397. DebugLoc dl = CurMBB->findBranchDebugLoc();
  398. if (I != MF->end() && !TII->analyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
  399. MachineBasicBlock *NextBB = &*I;
  400. if (TBB == NextBB && !Cond.empty() && !FBB) {
  401. if (!TII->reverseBranchCondition(Cond)) {
  402. TII->removeBranch(*CurMBB);
  403. TII->insertBranch(*CurMBB, SuccBB, nullptr, Cond, dl);
  404. return;
  405. }
  406. }
  407. }
  408. TII->insertBranch(*CurMBB, SuccBB, nullptr,
  409. SmallVector<MachineOperand, 0>(), dl);
  410. }
  411. bool
  412. BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {
  413. if (getHash() < o.getHash())
  414. return true;
  415. if (getHash() > o.getHash())
  416. return false;
  417. if (getBlock()->getNumber() < o.getBlock()->getNumber())
  418. return true;
  419. if (getBlock()->getNumber() > o.getBlock()->getNumber())
  420. return false;
  421. // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
  422. // an object with itself.
  423. #ifndef _GLIBCXX_DEBUG
  424. llvm_unreachable("Predecessor appears twice");
  425. #else
  426. return false;
  427. #endif
  428. }
  429. /// CountTerminators - Count the number of terminators in the given
  430. /// block and set I to the position of the first non-terminator, if there
  431. /// is one, or MBB->end() otherwise.
  432. static unsigned CountTerminators(MachineBasicBlock *MBB,
  433. MachineBasicBlock::iterator &I) {
  434. I = MBB->end();
  435. unsigned NumTerms = 0;
  436. while (true) {
  437. if (I == MBB->begin()) {
  438. I = MBB->end();
  439. break;
  440. }
  441. --I;
  442. if (!I->isTerminator()) break;
  443. ++NumTerms;
  444. }
  445. return NumTerms;
  446. }
  447. /// A no successor, non-return block probably ends in unreachable and is cold.
  448. /// Also consider a block that ends in an indirect branch to be a return block,
  449. /// since many targets use plain indirect branches to return.
  450. static bool blockEndsInUnreachable(const MachineBasicBlock *MBB) {
  451. if (!MBB->succ_empty())
  452. return false;
  453. if (MBB->empty())
  454. return true;
  455. return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());
  456. }
  457. /// ProfitableToMerge - Check if two machine basic blocks have a common tail
  458. /// and decide if it would be profitable to merge those tails. Return the
  459. /// length of the common tail and iterators to the first common instruction
  460. /// in each block.
  461. /// MBB1, MBB2 The blocks to check
  462. /// MinCommonTailLength Minimum size of tail block to be merged.
  463. /// CommonTailLen Out parameter to record the size of the shared tail between
  464. /// MBB1 and MBB2
  465. /// I1, I2 Iterator references that will be changed to point to the first
  466. /// instruction in the common tail shared by MBB1,MBB2
  467. /// SuccBB A common successor of MBB1, MBB2 which are in a canonical form
  468. /// relative to SuccBB
  469. /// PredBB The layout predecessor of SuccBB, if any.
  470. /// EHScopeMembership map from block to EH scope #.
  471. /// AfterPlacement True if we are merging blocks after layout. Stricter
  472. /// thresholds apply to prevent undoing tail-duplication.
  473. static bool
  474. ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
  475. unsigned MinCommonTailLength, unsigned &CommonTailLen,
  476. MachineBasicBlock::iterator &I1,
  477. MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB,
  478. MachineBasicBlock *PredBB,
  479. DenseMap<const MachineBasicBlock *, int> &EHScopeMembership,
  480. bool AfterPlacement,
  481. MBFIWrapper &MBBFreqInfo,
  482. ProfileSummaryInfo *PSI) {
  483. // It is never profitable to tail-merge blocks from two different EH scopes.
  484. if (!EHScopeMembership.empty()) {
  485. auto EHScope1 = EHScopeMembership.find(MBB1);
  486. assert(EHScope1 != EHScopeMembership.end());
  487. auto EHScope2 = EHScopeMembership.find(MBB2);
  488. assert(EHScope2 != EHScopeMembership.end());
  489. if (EHScope1->second != EHScope2->second)
  490. return false;
  491. }
  492. CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
  493. if (CommonTailLen == 0)
  494. return false;
  495. LLVM_DEBUG(dbgs() << "Common tail length of " << printMBBReference(*MBB1)
  496. << " and " << printMBBReference(*MBB2) << " is "
  497. << CommonTailLen << '\n');
  498. // Move the iterators to the beginning of the MBB if we only got debug
  499. // instructions before the tail. This is to avoid splitting a block when we
  500. // only got debug instructions before the tail (to be invariant on -g).
  501. if (skipDebugInstructionsForward(MBB1->begin(), MBB1->end()) == I1)
  502. I1 = MBB1->begin();
  503. if (skipDebugInstructionsForward(MBB2->begin(), MBB2->end()) == I2)
  504. I2 = MBB2->begin();
  505. bool FullBlockTail1 = I1 == MBB1->begin();
  506. bool FullBlockTail2 = I2 == MBB2->begin();
  507. // It's almost always profitable to merge any number of non-terminator
  508. // instructions with the block that falls through into the common successor.
  509. // This is true only for a single successor. For multiple successors, we are
  510. // trading a conditional branch for an unconditional one.
  511. // TODO: Re-visit successor size for non-layout tail merging.
  512. if ((MBB1 == PredBB || MBB2 == PredBB) &&
  513. (!AfterPlacement || MBB1->succ_size() == 1)) {
  514. MachineBasicBlock::iterator I;
  515. unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
  516. if (CommonTailLen > NumTerms)
  517. return true;
  518. }
  519. // If these are identical non-return blocks with no successors, merge them.
  520. // Such blocks are typically cold calls to noreturn functions like abort, and
  521. // are unlikely to become a fallthrough target after machine block placement.
  522. // Tail merging these blocks is unlikely to create additional unconditional
  523. // branches, and will reduce the size of this cold code.
  524. if (FullBlockTail1 && FullBlockTail2 &&
  525. blockEndsInUnreachable(MBB1) && blockEndsInUnreachable(MBB2))
  526. return true;
  527. // If one of the blocks can be completely merged and happens to be in
  528. // a position where the other could fall through into it, merge any number
  529. // of instructions, because it can be done without a branch.
  530. // TODO: If the blocks are not adjacent, move one of them so that they are?
  531. if (MBB1->isLayoutSuccessor(MBB2) && FullBlockTail2)
  532. return true;
  533. if (MBB2->isLayoutSuccessor(MBB1) && FullBlockTail1)
  534. return true;
  535. // If both blocks are identical and end in a branch, merge them unless they
  536. // both have a fallthrough predecessor and successor.
  537. // We can only do this after block placement because it depends on whether
  538. // there are fallthroughs, and we don't know until after layout.
  539. if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {
  540. auto BothFallThrough = [](MachineBasicBlock *MBB) {
  541. if (MBB->succ_size() != 0 && !MBB->canFallThrough())
  542. return false;
  543. MachineFunction::iterator I(MBB);
  544. MachineFunction *MF = MBB->getParent();
  545. return (MBB != &*MF->begin()) && std::prev(I)->canFallThrough();
  546. };
  547. if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))
  548. return true;
  549. }
  550. // If both blocks have an unconditional branch temporarily stripped out,
  551. // count that as an additional common instruction for the following
  552. // heuristics. This heuristic is only accurate for single-succ blocks, so to
  553. // make sure that during layout merging and duplicating don't crash, we check
  554. // for that when merging during layout.
  555. unsigned EffectiveTailLen = CommonTailLen;
  556. if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
  557. (MBB1->succ_size() == 1 || !AfterPlacement) &&
  558. !MBB1->back().isBarrier() &&
  559. !MBB2->back().isBarrier())
  560. ++EffectiveTailLen;
  561. // Check if the common tail is long enough to be worthwhile.
  562. if (EffectiveTailLen >= MinCommonTailLength)
  563. return true;
  564. // If we are optimizing for code size, 2 instructions in common is enough if
  565. // we don't have to split a block. At worst we will be introducing 1 new
  566. // branch instruction, which is likely to be smaller than the 2
  567. // instructions that would be deleted in the merge.
  568. MachineFunction *MF = MBB1->getParent();
  569. bool OptForSize =
  570. MF->getFunction().hasOptSize() ||
  571. (llvm::shouldOptimizeForSize(MBB1, PSI, &MBBFreqInfo) &&
  572. llvm::shouldOptimizeForSize(MBB2, PSI, &MBBFreqInfo));
  573. return EffectiveTailLen >= 2 && OptForSize &&
  574. (FullBlockTail1 || FullBlockTail2);
  575. }
  576. unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
  577. unsigned MinCommonTailLength,
  578. MachineBasicBlock *SuccBB,
  579. MachineBasicBlock *PredBB) {
  580. unsigned maxCommonTailLength = 0U;
  581. SameTails.clear();
  582. MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
  583. MPIterator HighestMPIter = std::prev(MergePotentials.end());
  584. for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
  585. B = MergePotentials.begin();
  586. CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
  587. for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
  588. unsigned CommonTailLen;
  589. if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
  590. MinCommonTailLength,
  591. CommonTailLen, TrialBBI1, TrialBBI2,
  592. SuccBB, PredBB,
  593. EHScopeMembership,
  594. AfterBlockPlacement, MBBFreqInfo, PSI)) {
  595. if (CommonTailLen > maxCommonTailLength) {
  596. SameTails.clear();
  597. maxCommonTailLength = CommonTailLen;
  598. HighestMPIter = CurMPIter;
  599. SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
  600. }
  601. if (HighestMPIter == CurMPIter &&
  602. CommonTailLen == maxCommonTailLength)
  603. SameTails.push_back(SameTailElt(I, TrialBBI2));
  604. }
  605. if (I == B)
  606. break;
  607. }
  608. }
  609. return maxCommonTailLength;
  610. }
  611. void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
  612. MachineBasicBlock *SuccBB,
  613. MachineBasicBlock *PredBB) {
  614. MPIterator CurMPIter, B;
  615. for (CurMPIter = std::prev(MergePotentials.end()),
  616. B = MergePotentials.begin();
  617. CurMPIter->getHash() == CurHash; --CurMPIter) {
  618. // Put the unconditional branch back, if we need one.
  619. MachineBasicBlock *CurMBB = CurMPIter->getBlock();
  620. if (SuccBB && CurMBB != PredBB)
  621. FixTail(CurMBB, SuccBB, TII);
  622. if (CurMPIter == B)
  623. break;
  624. }
  625. if (CurMPIter->getHash() != CurHash)
  626. CurMPIter++;
  627. MergePotentials.erase(CurMPIter, MergePotentials.end());
  628. }
  629. bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
  630. MachineBasicBlock *SuccBB,
  631. unsigned maxCommonTailLength,
  632. unsigned &commonTailIndex) {
  633. commonTailIndex = 0;
  634. unsigned TimeEstimate = ~0U;
  635. for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
  636. // Use PredBB if possible; that doesn't require a new branch.
  637. if (SameTails[i].getBlock() == PredBB) {
  638. commonTailIndex = i;
  639. break;
  640. }
  641. // Otherwise, make a (fairly bogus) choice based on estimate of
  642. // how long it will take the various blocks to execute.
  643. unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),
  644. SameTails[i].getTailStartPos());
  645. if (t <= TimeEstimate) {
  646. TimeEstimate = t;
  647. commonTailIndex = i;
  648. }
  649. }
  650. MachineBasicBlock::iterator BBI =
  651. SameTails[commonTailIndex].getTailStartPos();
  652. MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
  653. LLVM_DEBUG(dbgs() << "\nSplitting " << printMBBReference(*MBB) << ", size "
  654. << maxCommonTailLength);
  655. // If the split block unconditionally falls-thru to SuccBB, it will be
  656. // merged. In control flow terms it should then take SuccBB's name. e.g. If
  657. // SuccBB is an inner loop, the common tail is still part of the inner loop.
  658. const BasicBlock *BB = (SuccBB && MBB->succ_size() == 1) ?
  659. SuccBB->getBasicBlock() : MBB->getBasicBlock();
  660. MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI, BB);
  661. if (!newMBB) {
  662. LLVM_DEBUG(dbgs() << "... failed!");
  663. return false;
  664. }
  665. SameTails[commonTailIndex].setBlock(newMBB);
  666. SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
  667. // If we split PredBB, newMBB is the new predecessor.
  668. if (PredBB == MBB)
  669. PredBB = newMBB;
  670. return true;
  671. }
  672. static void
  673. mergeOperations(MachineBasicBlock::iterator MBBIStartPos,
  674. MachineBasicBlock &MBBCommon) {
  675. MachineBasicBlock *MBB = MBBIStartPos->getParent();
  676. // Note CommonTailLen does not necessarily matches the size of
  677. // the common BB nor all its instructions because of debug
  678. // instructions differences.
  679. unsigned CommonTailLen = 0;
  680. for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)
  681. ++CommonTailLen;
  682. MachineBasicBlock::reverse_iterator MBBI = MBB->rbegin();
  683. MachineBasicBlock::reverse_iterator MBBIE = MBB->rend();
  684. MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin();
  685. MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend();
  686. while (CommonTailLen--) {
  687. assert(MBBI != MBBIE && "Reached BB end within common tail length!");
  688. (void)MBBIE;
  689. if (!countsAsInstruction(*MBBI)) {
  690. ++MBBI;
  691. continue;
  692. }
  693. while ((MBBICommon != MBBIECommon) && !countsAsInstruction(*MBBICommon))
  694. ++MBBICommon;
  695. assert(MBBICommon != MBBIECommon &&
  696. "Reached BB end within common tail length!");
  697. assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!");
  698. // Merge MMOs from memory operations in the common block.
  699. if (MBBICommon->mayLoadOrStore())
  700. MBBICommon->cloneMergedMemRefs(*MBB->getParent(), {&*MBBICommon, &*MBBI});
  701. // Drop undef flags if they aren't present in all merged instructions.
  702. for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {
  703. MachineOperand &MO = MBBICommon->getOperand(I);
  704. if (MO.isReg() && MO.isUndef()) {
  705. const MachineOperand &OtherMO = MBBI->getOperand(I);
  706. if (!OtherMO.isUndef())
  707. MO.setIsUndef(false);
  708. }
  709. }
  710. ++MBBI;
  711. ++MBBICommon;
  712. }
  713. }
  714. void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {
  715. MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
  716. std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
  717. for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
  718. if (i != commonTailIndex) {
  719. NextCommonInsts[i] = SameTails[i].getTailStartPos();
  720. mergeOperations(SameTails[i].getTailStartPos(), *MBB);
  721. } else {
  722. assert(SameTails[i].getTailStartPos() == MBB->begin() &&
  723. "MBB is not a common tail only block");
  724. }
  725. }
  726. for (auto &MI : *MBB) {
  727. if (!countsAsInstruction(MI))
  728. continue;
  729. DebugLoc DL = MI.getDebugLoc();
  730. for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
  731. if (i == commonTailIndex)
  732. continue;
  733. auto &Pos = NextCommonInsts[i];
  734. assert(Pos != SameTails[i].getBlock()->end() &&
  735. "Reached BB end within common tail");
  736. while (!countsAsInstruction(*Pos)) {
  737. ++Pos;
  738. assert(Pos != SameTails[i].getBlock()->end() &&
  739. "Reached BB end within common tail");
  740. }
  741. assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
  742. DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
  743. NextCommonInsts[i] = ++Pos;
  744. }
  745. MI.setDebugLoc(DL);
  746. }
  747. if (UpdateLiveIns) {
  748. LivePhysRegs NewLiveIns(*TRI);
  749. computeLiveIns(NewLiveIns, *MBB);
  750. LiveRegs.init(*TRI);
  751. // The flag merging may lead to some register uses no longer using the
  752. // <undef> flag, add IMPLICIT_DEFs in the predecessors as necessary.
  753. for (MachineBasicBlock *Pred : MBB->predecessors()) {
  754. LiveRegs.clear();
  755. LiveRegs.addLiveOuts(*Pred);
  756. MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();
  757. for (Register Reg : NewLiveIns) {
  758. if (!LiveRegs.available(*MRI, Reg))
  759. continue;
  760. DebugLoc DL;
  761. BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
  762. Reg);
  763. }
  764. }
  765. MBB->clearLiveIns();
  766. addLiveIns(*MBB, NewLiveIns);
  767. }
  768. }
  769. // See if any of the blocks in MergePotentials (which all have SuccBB as a
  770. // successor, or all have no successor if it is null) can be tail-merged.
  771. // If there is a successor, any blocks in MergePotentials that are not
  772. // tail-merged and are not immediately before Succ must have an unconditional
  773. // branch to Succ added (but the predecessor/successor lists need no
  774. // adjustment). The lone predecessor of Succ that falls through into Succ,
  775. // if any, is given in PredBB.
  776. // MinCommonTailLength - Except for the special cases below, tail-merge if
  777. // there are at least this many instructions in common.
  778. bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
  779. MachineBasicBlock *PredBB,
  780. unsigned MinCommonTailLength) {
  781. bool MadeChange = false;
  782. LLVM_DEBUG(
  783. dbgs() << "\nTryTailMergeBlocks: ";
  784. for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()
  785. << printMBBReference(*MergePotentials[i].getBlock())
  786. << (i == e - 1 ? "" : ", ");
  787. dbgs() << "\n"; if (SuccBB) {
  788. dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';
  789. if (PredBB)
  790. dbgs() << " which has fall-through from "
  791. << printMBBReference(*PredBB) << "\n";
  792. } dbgs() << "Looking for common tails of at least "
  793. << MinCommonTailLength << " instruction"
  794. << (MinCommonTailLength == 1 ? "" : "s") << '\n';);
  795. // Sort by hash value so that blocks with identical end sequences sort
  796. // together.
  797. array_pod_sort(MergePotentials.begin(), MergePotentials.end());
  798. // Walk through equivalence sets looking for actual exact matches.
  799. while (MergePotentials.size() > 1) {
  800. unsigned CurHash = MergePotentials.back().getHash();
  801. // Build SameTails, identifying the set of blocks with this hash code
  802. // and with the maximum number of instructions in common.
  803. unsigned maxCommonTailLength = ComputeSameTails(CurHash,
  804. MinCommonTailLength,
  805. SuccBB, PredBB);
  806. // If we didn't find any pair that has at least MinCommonTailLength
  807. // instructions in common, remove all blocks with this hash code and retry.
  808. if (SameTails.empty()) {
  809. RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
  810. continue;
  811. }
  812. // If one of the blocks is the entire common tail (and is not the entry
  813. // block/an EH pad, which we can't jump to), we can treat all blocks with
  814. // this same tail at once. Use PredBB if that is one of the possibilities,
  815. // as that will not introduce any extra branches.
  816. MachineBasicBlock *EntryBB =
  817. &MergePotentials.front().getBlock()->getParent()->front();
  818. unsigned commonTailIndex = SameTails.size();
  819. // If there are two blocks, check to see if one can be made to fall through
  820. // into the other.
  821. if (SameTails.size() == 2 &&
  822. SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
  823. SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
  824. commonTailIndex = 1;
  825. else if (SameTails.size() == 2 &&
  826. SameTails[1].getBlock()->isLayoutSuccessor(
  827. SameTails[0].getBlock()) &&
  828. SameTails[0].tailIsWholeBlock() &&
  829. !SameTails[0].getBlock()->isEHPad())
  830. commonTailIndex = 0;
  831. else {
  832. // Otherwise just pick one, favoring the fall-through predecessor if
  833. // there is one.
  834. for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
  835. MachineBasicBlock *MBB = SameTails[i].getBlock();
  836. if ((MBB == EntryBB || MBB->isEHPad()) &&
  837. SameTails[i].tailIsWholeBlock())
  838. continue;
  839. if (MBB == PredBB) {
  840. commonTailIndex = i;
  841. break;
  842. }
  843. if (SameTails[i].tailIsWholeBlock())
  844. commonTailIndex = i;
  845. }
  846. }
  847. if (commonTailIndex == SameTails.size() ||
  848. (SameTails[commonTailIndex].getBlock() == PredBB &&
  849. !SameTails[commonTailIndex].tailIsWholeBlock())) {
  850. // None of the blocks consist entirely of the common tail.
  851. // Split a block so that one does.
  852. if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
  853. maxCommonTailLength, commonTailIndex)) {
  854. RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
  855. continue;
  856. }
  857. }
  858. MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
  859. // Recompute common tail MBB's edge weights and block frequency.
  860. setCommonTailEdgeWeights(*MBB);
  861. // Merge debug locations, MMOs and undef flags across identical instructions
  862. // for common tail.
  863. mergeCommonTails(commonTailIndex);
  864. // MBB is common tail. Adjust all other BB's to jump to this one.
  865. // Traversal must be forwards so erases work.
  866. LLVM_DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)
  867. << " for ");
  868. for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
  869. if (commonTailIndex == i)
  870. continue;
  871. LLVM_DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())
  872. << (i == e - 1 ? "" : ", "));
  873. // Hack the end off BB i, making it jump to BB commonTailIndex instead.
  874. replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
  875. // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
  876. MergePotentials.erase(SameTails[i].getMPIter());
  877. }
  878. LLVM_DEBUG(dbgs() << "\n");
  879. // We leave commonTailIndex in the worklist in case there are other blocks
  880. // that match it with a smaller number of instructions.
  881. MadeChange = true;
  882. }
  883. return MadeChange;
  884. }
  885. bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
  886. bool MadeChange = false;
  887. if (!EnableTailMerge)
  888. return MadeChange;
  889. // First find blocks with no successors.
  890. // Block placement may create new tail merging opportunities for these blocks.
  891. MergePotentials.clear();
  892. for (MachineBasicBlock &MBB : MF) {
  893. if (MergePotentials.size() == TailMergeThreshold)
  894. break;
  895. if (!TriedMerging.count(&MBB) && MBB.succ_empty())
  896. MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
  897. }
  898. // If this is a large problem, avoid visiting the same basic blocks
  899. // multiple times.
  900. if (MergePotentials.size() == TailMergeThreshold)
  901. for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
  902. TriedMerging.insert(MergePotentials[i].getBlock());
  903. // See if we can do any tail merging on those.
  904. if (MergePotentials.size() >= 2)
  905. MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);
  906. // Look at blocks (IBB) with multiple predecessors (PBB).
  907. // We change each predecessor to a canonical form, by
  908. // (1) temporarily removing any unconditional branch from the predecessor
  909. // to IBB, and
  910. // (2) alter conditional branches so they branch to the other block
  911. // not IBB; this may require adding back an unconditional branch to IBB
  912. // later, where there wasn't one coming in. E.g.
  913. // Bcc IBB
  914. // fallthrough to QBB
  915. // here becomes
  916. // Bncc QBB
  917. // with a conceptual B to IBB after that, which never actually exists.
  918. // With those changes, we see whether the predecessors' tails match,
  919. // and merge them if so. We change things out of canonical form and
  920. // back to the way they were later in the process. (OptimizeBranches
  921. // would undo some of this, but we can't use it, because we'd get into
  922. // a compile-time infinite loop repeatedly doing and undoing the same
  923. // transformations.)
  924. for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
  925. I != E; ++I) {
  926. if (I->pred_size() < 2) continue;
  927. SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
  928. MachineBasicBlock *IBB = &*I;
  929. MachineBasicBlock *PredBB = &*std::prev(I);
  930. MergePotentials.clear();
  931. MachineLoop *ML;
  932. // Bail if merging after placement and IBB is the loop header because
  933. // -- If merging predecessors that belong to the same loop as IBB, the
  934. // common tail of merged predecessors may become the loop top if block
  935. // placement is called again and the predecessors may branch to this common
  936. // tail and require more branches. This can be relaxed if
  937. // MachineBlockPlacement::findBestLoopTop is more flexible.
  938. // --If merging predecessors that do not belong to the same loop as IBB, the
  939. // loop info of IBB's loop and the other loops may be affected. Calling the
  940. // block placement again may make big change to the layout and eliminate the
  941. // reason to do tail merging here.
  942. if (AfterBlockPlacement && MLI) {
  943. ML = MLI->getLoopFor(IBB);
  944. if (ML && IBB == ML->getHeader())
  945. continue;
  946. }
  947. for (MachineBasicBlock *PBB : I->predecessors()) {
  948. if (MergePotentials.size() == TailMergeThreshold)
  949. break;
  950. if (TriedMerging.count(PBB))
  951. continue;
  952. // Skip blocks that loop to themselves, can't tail merge these.
  953. if (PBB == IBB)
  954. continue;
  955. // Visit each predecessor only once.
  956. if (!UniquePreds.insert(PBB).second)
  957. continue;
  958. // Skip blocks which may jump to a landing pad or jump from an asm blob.
  959. // Can't tail merge these.
  960. if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
  961. continue;
  962. // After block placement, only consider predecessors that belong to the
  963. // same loop as IBB. The reason is the same as above when skipping loop
  964. // header.
  965. if (AfterBlockPlacement && MLI)
  966. if (ML != MLI->getLoopFor(PBB))
  967. continue;
  968. MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
  969. SmallVector<MachineOperand, 4> Cond;
  970. if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {
  971. // Failing case: IBB is the target of a cbr, and we cannot reverse the
  972. // branch.
  973. SmallVector<MachineOperand, 4> NewCond(Cond);
  974. if (!Cond.empty() && TBB == IBB) {
  975. if (TII->reverseBranchCondition(NewCond))
  976. continue;
  977. // This is the QBB case described above
  978. if (!FBB) {
  979. auto Next = ++PBB->getIterator();
  980. if (Next != MF.end())
  981. FBB = &*Next;
  982. }
  983. }
  984. // Remove the unconditional branch at the end, if any.
  985. if (TBB && (Cond.empty() || FBB)) {
  986. DebugLoc dl = PBB->findBranchDebugLoc();
  987. TII->removeBranch(*PBB);
  988. if (!Cond.empty())
  989. // reinsert conditional branch only, for now
  990. TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,
  991. NewCond, dl);
  992. }
  993. MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(*PBB), PBB));
  994. }
  995. }
  996. // If this is a large problem, avoid visiting the same basic blocks multiple
  997. // times.
  998. if (MergePotentials.size() == TailMergeThreshold)
  999. for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
  1000. TriedMerging.insert(MergePotentials[i].getBlock());
  1001. if (MergePotentials.size() >= 2)
  1002. MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
  1003. // Reinsert an unconditional branch if needed. The 1 below can occur as a
  1004. // result of removing blocks in TryTailMergeBlocks.
  1005. PredBB = &*std::prev(I); // this may have been changed in TryTailMergeBlocks
  1006. if (MergePotentials.size() == 1 &&
  1007. MergePotentials.begin()->getBlock() != PredBB)
  1008. FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
  1009. }
  1010. return MadeChange;
  1011. }
  1012. void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {
  1013. SmallVector<BlockFrequency, 2> EdgeFreqLs(TailMBB.succ_size());
  1014. BlockFrequency AccumulatedMBBFreq;
  1015. // Aggregate edge frequency of successor edge j:
  1016. // edgeFreq(j) = sum (freq(bb) * edgeProb(bb, j)),
  1017. // where bb is a basic block that is in SameTails.
  1018. for (const auto &Src : SameTails) {
  1019. const MachineBasicBlock *SrcMBB = Src.getBlock();
  1020. BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB);
  1021. AccumulatedMBBFreq += BlockFreq;
  1022. // It is not necessary to recompute edge weights if TailBB has less than two
  1023. // successors.
  1024. if (TailMBB.succ_size() <= 1)
  1025. continue;
  1026. auto EdgeFreq = EdgeFreqLs.begin();
  1027. for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
  1028. SuccI != SuccE; ++SuccI, ++EdgeFreq)
  1029. *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);
  1030. }
  1031. MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);
  1032. if (TailMBB.succ_size() <= 1)
  1033. return;
  1034. auto SumEdgeFreq =
  1035. std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
  1036. .getFrequency();
  1037. auto EdgeFreq = EdgeFreqLs.begin();
  1038. if (SumEdgeFreq > 0) {
  1039. for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
  1040. SuccI != SuccE; ++SuccI, ++EdgeFreq) {
  1041. auto Prob = BranchProbability::getBranchProbability(
  1042. EdgeFreq->getFrequency(), SumEdgeFreq);
  1043. TailMBB.setSuccProbability(SuccI, Prob);
  1044. }
  1045. }
  1046. }
  1047. //===----------------------------------------------------------------------===//
  1048. // Branch Optimization
  1049. //===----------------------------------------------------------------------===//
  1050. bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
  1051. bool MadeChange = false;
  1052. // Make sure blocks are numbered in order
  1053. MF.RenumberBlocks();
  1054. // Renumbering blocks alters EH scope membership, recalculate it.
  1055. EHScopeMembership = getEHScopeMembership(MF);
  1056. for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
  1057. I != E; ) {
  1058. MachineBasicBlock *MBB = &*I++;
  1059. MadeChange |= OptimizeBlock(MBB);
  1060. // If it is dead, remove it.
  1061. if (MBB->pred_empty()) {
  1062. RemoveDeadBlock(MBB);
  1063. MadeChange = true;
  1064. ++NumDeadBlocks;
  1065. }
  1066. }
  1067. return MadeChange;
  1068. }
  1069. // Blocks should be considered empty if they contain only debug info;
  1070. // else the debug info would affect codegen.
  1071. static bool IsEmptyBlock(MachineBasicBlock *MBB) {
  1072. return MBB->getFirstNonDebugInstr() == MBB->end();
  1073. }
  1074. // Blocks with only debug info and branches should be considered the same
  1075. // as blocks with only branches.
  1076. static bool IsBranchOnlyBlock(MachineBasicBlock *MBB) {
  1077. MachineBasicBlock::iterator I = MBB->getFirstNonDebugInstr();
  1078. assert(I != MBB->end() && "empty block!");
  1079. return I->isBranch();
  1080. }
  1081. /// IsBetterFallthrough - Return true if it would be clearly better to
  1082. /// fall-through to MBB1 than to fall through into MBB2. This has to return
  1083. /// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
  1084. /// result in infinite loops.
  1085. static bool IsBetterFallthrough(MachineBasicBlock *MBB1,
  1086. MachineBasicBlock *MBB2) {
  1087. assert(MBB1 && MBB2 && "Unknown MachineBasicBlock");
  1088. // Right now, we use a simple heuristic. If MBB2 ends with a call, and
  1089. // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
  1090. // optimize branches that branch to either a return block or an assert block
  1091. // into a fallthrough to the return.
  1092. MachineBasicBlock::iterator MBB1I = MBB1->getLastNonDebugInstr();
  1093. MachineBasicBlock::iterator MBB2I = MBB2->getLastNonDebugInstr();
  1094. if (MBB1I == MBB1->end() || MBB2I == MBB2->end())
  1095. return false;
  1096. // If there is a clear successor ordering we make sure that one block
  1097. // will fall through to the next
  1098. if (MBB1->isSuccessor(MBB2)) return true;
  1099. if (MBB2->isSuccessor(MBB1)) return false;
  1100. return MBB2I->isCall() && !MBB1I->isCall();
  1101. }
  1102. /// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
  1103. /// instructions on the block.
  1104. static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB) {
  1105. MachineBasicBlock::iterator I = MBB.getLastNonDebugInstr();
  1106. if (I != MBB.end() && I->isBranch())
  1107. return I->getDebugLoc();
  1108. return DebugLoc();
  1109. }
  1110. static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII,
  1111. MachineBasicBlock &MBB,
  1112. MachineBasicBlock &PredMBB) {
  1113. auto InsertBefore = PredMBB.getFirstTerminator();
  1114. for (MachineInstr &MI : MBB.instrs())
  1115. if (MI.isDebugInstr()) {
  1116. TII->duplicate(PredMBB, InsertBefore, MI);
  1117. LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "
  1118. << MI);
  1119. }
  1120. }
  1121. static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII,
  1122. MachineBasicBlock &MBB,
  1123. MachineBasicBlock &SuccMBB) {
  1124. auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
  1125. for (MachineInstr &MI : MBB.instrs())
  1126. if (MI.isDebugInstr()) {
  1127. TII->duplicate(SuccMBB, InsertBefore, MI);
  1128. LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "
  1129. << MI);
  1130. }
  1131. }
  1132. // Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
  1133. // a basic block is removed we would lose the debug information unless we have
  1134. // copied the information to a predecessor/successor.
  1135. //
  1136. // TODO: This function only handles some simple cases. An alternative would be
  1137. // to run a heavier analysis, such as the LiveDebugValues pass, before we do
  1138. // branch folding.
  1139. static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII,
  1140. MachineBasicBlock &MBB) {
  1141. assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).");
  1142. // If this MBB is the only predecessor of a successor it is legal to copy
  1143. // DBG_VALUE instructions to the beginning of the successor.
  1144. for (MachineBasicBlock *SuccBB : MBB.successors())
  1145. if (SuccBB->pred_size() == 1)
  1146. copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
  1147. // If this MBB is the only successor of a predecessor it is legal to copy the
  1148. // DBG_VALUE instructions to the end of the predecessor (just before the
  1149. // terminators, assuming that the terminator isn't affecting the DBG_VALUE).
  1150. for (MachineBasicBlock *PredBB : MBB.predecessors())
  1151. if (PredBB->succ_size() == 1)
  1152. copyDebugInfoToPredecessor(TII, MBB, *PredBB);
  1153. }
  1154. bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
  1155. bool MadeChange = false;
  1156. MachineFunction &MF = *MBB->getParent();
  1157. ReoptimizeBlock:
  1158. MachineFunction::iterator FallThrough = MBB->getIterator();
  1159. ++FallThrough;
  1160. // Make sure MBB and FallThrough belong to the same EH scope.
  1161. bool SameEHScope = true;
  1162. if (!EHScopeMembership.empty() && FallThrough != MF.end()) {
  1163. auto MBBEHScope = EHScopeMembership.find(MBB);
  1164. assert(MBBEHScope != EHScopeMembership.end());
  1165. auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
  1166. assert(FallThroughEHScope != EHScopeMembership.end());
  1167. SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
  1168. }
  1169. // Analyze the branch in the current block. As a side-effect, this may cause
  1170. // the block to become empty.
  1171. MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
  1172. SmallVector<MachineOperand, 4> CurCond;
  1173. bool CurUnAnalyzable =
  1174. TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
  1175. // If this block is empty, make everyone use its fall-through, not the block
  1176. // explicitly. Landing pads should not do this since the landing-pad table
  1177. // points to this block. Blocks with their addresses taken shouldn't be
  1178. // optimized away.
  1179. if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
  1180. SameEHScope) {
  1181. salvageDebugInfoFromEmptyBlock(TII, *MBB);
  1182. // Dead block? Leave for cleanup later.
  1183. if (MBB->pred_empty()) return MadeChange;
  1184. if (FallThrough == MF.end()) {
  1185. // TODO: Simplify preds to not branch here if possible!
  1186. } else if (FallThrough->isEHPad()) {
  1187. // Don't rewrite to a landing pad fallthough. That could lead to the case
  1188. // where a BB jumps to more than one landing pad.
  1189. // TODO: Is it ever worth rewriting predecessors which don't already
  1190. // jump to a landing pad, and so can safely jump to the fallthrough?
  1191. } else if (MBB->isSuccessor(&*FallThrough)) {
  1192. // Rewrite all predecessors of the old block to go to the fallthrough
  1193. // instead.
  1194. while (!MBB->pred_empty()) {
  1195. MachineBasicBlock *Pred = *(MBB->pred_end()-1);
  1196. Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
  1197. }
  1198. // If MBB was the target of a jump table, update jump tables to go to the
  1199. // fallthrough instead.
  1200. if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
  1201. MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
  1202. MadeChange = true;
  1203. }
  1204. return MadeChange;
  1205. }
  1206. // Check to see if we can simplify the terminator of the block before this
  1207. // one.
  1208. MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
  1209. MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
  1210. SmallVector<MachineOperand, 4> PriorCond;
  1211. bool PriorUnAnalyzable =
  1212. TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
  1213. if (!PriorUnAnalyzable) {
  1214. // If the previous branch is conditional and both conditions go to the same
  1215. // destination, remove the branch, replacing it with an unconditional one or
  1216. // a fall-through.
  1217. if (PriorTBB && PriorTBB == PriorFBB) {
  1218. DebugLoc dl = getBranchDebugLoc(PrevBB);
  1219. TII->removeBranch(PrevBB);
  1220. PriorCond.clear();
  1221. if (PriorTBB != MBB)
  1222. TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
  1223. MadeChange = true;
  1224. ++NumBranchOpts;
  1225. goto ReoptimizeBlock;
  1226. }
  1227. // If the previous block unconditionally falls through to this block and
  1228. // this block has no other predecessors, move the contents of this block
  1229. // into the prior block. This doesn't usually happen when SimplifyCFG
  1230. // has been used, but it can happen if tail merging splits a fall-through
  1231. // predecessor of a block.
  1232. // This has to check PrevBB->succ_size() because EH edges are ignored by
  1233. // analyzeBranch.
  1234. if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
  1235. PrevBB.succ_size() == 1 &&
  1236. !MBB->hasAddressTaken() && !MBB->isEHPad()) {
  1237. LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBB
  1238. << "From MBB: " << *MBB);
  1239. // Remove redundant DBG_VALUEs first.
  1240. if (!PrevBB.empty()) {
  1241. MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
  1242. --PrevBBIter;
  1243. MachineBasicBlock::iterator MBBIter = MBB->begin();
  1244. // Check if DBG_VALUE at the end of PrevBB is identical to the
  1245. // DBG_VALUE at the beginning of MBB.
  1246. while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
  1247. && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
  1248. if (!MBBIter->isIdenticalTo(*PrevBBIter))
  1249. break;
  1250. MachineInstr &DuplicateDbg = *MBBIter;
  1251. ++MBBIter; -- PrevBBIter;
  1252. DuplicateDbg.eraseFromParent();
  1253. }
  1254. }
  1255. PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
  1256. PrevBB.removeSuccessor(PrevBB.succ_begin());
  1257. assert(PrevBB.succ_empty());
  1258. PrevBB.transferSuccessors(MBB);
  1259. MadeChange = true;
  1260. return MadeChange;
  1261. }
  1262. // If the previous branch *only* branches to *this* block (conditional or
  1263. // not) remove the branch.
  1264. if (PriorTBB == MBB && !PriorFBB) {
  1265. TII->removeBranch(PrevBB);
  1266. MadeChange = true;
  1267. ++NumBranchOpts;
  1268. goto ReoptimizeBlock;
  1269. }
  1270. // If the prior block branches somewhere else on the condition and here if
  1271. // the condition is false, remove the uncond second branch.
  1272. if (PriorFBB == MBB) {
  1273. DebugLoc dl = getBranchDebugLoc(PrevBB);
  1274. TII->removeBranch(PrevBB);
  1275. TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
  1276. MadeChange = true;
  1277. ++NumBranchOpts;
  1278. goto ReoptimizeBlock;
  1279. }
  1280. // If the prior block branches here on true and somewhere else on false, and
  1281. // if the branch condition is reversible, reverse the branch to create a
  1282. // fall-through.
  1283. if (PriorTBB == MBB) {
  1284. SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
  1285. if (!TII->reverseBranchCondition(NewPriorCond)) {
  1286. DebugLoc dl = getBranchDebugLoc(PrevBB);
  1287. TII->removeBranch(PrevBB);
  1288. TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
  1289. MadeChange = true;
  1290. ++NumBranchOpts;
  1291. goto ReoptimizeBlock;
  1292. }
  1293. }
  1294. // If this block has no successors (e.g. it is a return block or ends with
  1295. // a call to a no-return function like abort or __cxa_throw) and if the pred
  1296. // falls through into this block, and if it would otherwise fall through
  1297. // into the block after this, move this block to the end of the function.
  1298. //
  1299. // We consider it more likely that execution will stay in the function (e.g.
  1300. // due to loops) than it is to exit it. This asserts in loops etc, moving
  1301. // the assert condition out of the loop body.
  1302. if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
  1303. MachineFunction::iterator(PriorTBB) == FallThrough &&
  1304. !MBB->canFallThrough()) {
  1305. bool DoTransform = true;
  1306. // We have to be careful that the succs of PredBB aren't both no-successor
  1307. // blocks. If neither have successors and if PredBB is the second from
  1308. // last block in the function, we'd just keep swapping the two blocks for
  1309. // last. Only do the swap if one is clearly better to fall through than
  1310. // the other.
  1311. if (FallThrough == --MF.end() &&
  1312. !IsBetterFallthrough(PriorTBB, MBB))
  1313. DoTransform = false;
  1314. if (DoTransform) {
  1315. // Reverse the branch so we will fall through on the previous true cond.
  1316. SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
  1317. if (!TII->reverseBranchCondition(NewPriorCond)) {
  1318. LLVM_DEBUG(dbgs() << "\nMoving MBB: " << *MBB
  1319. << "To make fallthrough to: " << *PriorTBB << "\n");
  1320. DebugLoc dl = getBranchDebugLoc(PrevBB);
  1321. TII->removeBranch(PrevBB);
  1322. TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
  1323. // Move this block to the end of the function.
  1324. MBB->moveAfter(&MF.back());
  1325. MadeChange = true;
  1326. ++NumBranchOpts;
  1327. return MadeChange;
  1328. }
  1329. }
  1330. }
  1331. }
  1332. bool OptForSize =
  1333. MF.getFunction().hasOptSize() ||
  1334. llvm::shouldOptimizeForSize(MBB, PSI, &MBBFreqInfo);
  1335. if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1 && OptForSize) {
  1336. // Changing "Jcc foo; foo: jmp bar;" into "Jcc bar;" might change the branch
  1337. // direction, thereby defeating careful block placement and regressing
  1338. // performance. Therefore, only consider this for optsize functions.
  1339. MachineInstr &TailCall = *MBB->getFirstNonDebugInstr();
  1340. if (TII->isUnconditionalTailCall(TailCall)) {
  1341. MachineBasicBlock *Pred = *MBB->pred_begin();
  1342. MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
  1343. SmallVector<MachineOperand, 4> PredCond;
  1344. bool PredAnalyzable =
  1345. !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
  1346. if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&
  1347. PredTBB != PredFBB) {
  1348. // The predecessor has a conditional branch to this block which consists
  1349. // of only a tail call. Try to fold the tail call into the conditional
  1350. // branch.
  1351. if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
  1352. // TODO: It would be nice if analyzeBranch() could provide a pointer
  1353. // to the branch instruction so replaceBranchWithTailCall() doesn't
  1354. // have to search for it.
  1355. TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
  1356. ++NumTailCalls;
  1357. Pred->removeSuccessor(MBB);
  1358. MadeChange = true;
  1359. return MadeChange;
  1360. }
  1361. }
  1362. // If the predecessor is falling through to this block, we could reverse
  1363. // the branch condition and fold the tail call into that. However, after
  1364. // that we might have to re-arrange the CFG to fall through to the other
  1365. // block and there is a high risk of regressing code size rather than
  1366. // improving it.
  1367. }
  1368. }
  1369. if (!CurUnAnalyzable) {
  1370. // If this is a two-way branch, and the FBB branches to this block, reverse
  1371. // the condition so the single-basic-block loop is faster. Instead of:
  1372. // Loop: xxx; jcc Out; jmp Loop
  1373. // we want:
  1374. // Loop: xxx; jncc Loop; jmp Out
  1375. if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
  1376. SmallVector<MachineOperand, 4> NewCond(CurCond);
  1377. if (!TII->reverseBranchCondition(NewCond)) {
  1378. DebugLoc dl = getBranchDebugLoc(*MBB);
  1379. TII->removeBranch(*MBB);
  1380. TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
  1381. MadeChange = true;
  1382. ++NumBranchOpts;
  1383. goto ReoptimizeBlock;
  1384. }
  1385. }
  1386. // If this branch is the only thing in its block, see if we can forward
  1387. // other blocks across it.
  1388. if (CurTBB && CurCond.empty() && !CurFBB &&
  1389. IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
  1390. !MBB->hasAddressTaken() && !MBB->isEHPad()) {
  1391. DebugLoc dl = getBranchDebugLoc(*MBB);
  1392. // This block may contain just an unconditional branch. Because there can
  1393. // be 'non-branch terminators' in the block, try removing the branch and
  1394. // then seeing if the block is empty.
  1395. TII->removeBranch(*MBB);
  1396. // If the only things remaining in the block are debug info, remove these
  1397. // as well, so this will behave the same as an empty block in non-debug
  1398. // mode.
  1399. if (IsEmptyBlock(MBB)) {
  1400. // Make the block empty, losing the debug info (we could probably
  1401. // improve this in some cases.)
  1402. MBB->erase(MBB->begin(), MBB->end());
  1403. }
  1404. // If this block is just an unconditional branch to CurTBB, we can
  1405. // usually completely eliminate the block. The only case we cannot
  1406. // completely eliminate the block is when the block before this one
  1407. // falls through into MBB and we can't understand the prior block's branch
  1408. // condition.
  1409. if (MBB->empty()) {
  1410. bool PredHasNoFallThrough = !PrevBB.canFallThrough();
  1411. if (PredHasNoFallThrough || !PriorUnAnalyzable ||
  1412. !PrevBB.isSuccessor(MBB)) {
  1413. // If the prior block falls through into us, turn it into an
  1414. // explicit branch to us to make updates simpler.
  1415. if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
  1416. PriorTBB != MBB && PriorFBB != MBB) {
  1417. if (!PriorTBB) {
  1418. assert(PriorCond.empty() && !PriorFBB &&
  1419. "Bad branch analysis");
  1420. PriorTBB = MBB;
  1421. } else {
  1422. assert(!PriorFBB && "Machine CFG out of date!");
  1423. PriorFBB = MBB;
  1424. }
  1425. DebugLoc pdl = getBranchDebugLoc(PrevBB);
  1426. TII->removeBranch(PrevBB);
  1427. TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
  1428. }
  1429. // Iterate through all the predecessors, revectoring each in-turn.
  1430. size_t PI = 0;
  1431. bool DidChange = false;
  1432. bool HasBranchToSelf = false;
  1433. while(PI != MBB->pred_size()) {
  1434. MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
  1435. if (PMBB == MBB) {
  1436. // If this block has an uncond branch to itself, leave it.
  1437. ++PI;
  1438. HasBranchToSelf = true;
  1439. } else {
  1440. DidChange = true;
  1441. PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
  1442. // If this change resulted in PMBB ending in a conditional
  1443. // branch where both conditions go to the same destination,
  1444. // change this to an unconditional branch.
  1445. MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
  1446. SmallVector<MachineOperand, 4> NewCurCond;
  1447. bool NewCurUnAnalyzable = TII->analyzeBranch(
  1448. *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);
  1449. if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
  1450. DebugLoc pdl = getBranchDebugLoc(*PMBB);
  1451. TII->removeBranch(*PMBB);
  1452. NewCurCond.clear();
  1453. TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
  1454. MadeChange = true;
  1455. ++NumBranchOpts;
  1456. }
  1457. }
  1458. }
  1459. // Change any jumptables to go to the new MBB.
  1460. if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
  1461. MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
  1462. if (DidChange) {
  1463. ++NumBranchOpts;
  1464. MadeChange = true;
  1465. if (!HasBranchToSelf) return MadeChange;
  1466. }
  1467. }
  1468. }
  1469. // Add the branch back if the block is more than just an uncond branch.
  1470. TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
  1471. }
  1472. }
  1473. // If the prior block doesn't fall through into this block, and if this
  1474. // block doesn't fall through into some other block, see if we can find a
  1475. // place to move this block where a fall-through will happen.
  1476. if (!PrevBB.canFallThrough()) {
  1477. // Now we know that there was no fall-through into this block, check to
  1478. // see if it has a fall-through into its successor.
  1479. bool CurFallsThru = MBB->canFallThrough();
  1480. if (!MBB->isEHPad()) {
  1481. // Check all the predecessors of this block. If one of them has no fall
  1482. // throughs, and analyzeBranch thinks it _could_ fallthrough to this
  1483. // block, move this block right after it.
  1484. for (MachineBasicBlock *PredBB : MBB->predecessors()) {
  1485. // Analyze the branch at the end of the pred.
  1486. MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
  1487. SmallVector<MachineOperand, 4> PredCond;
  1488. if (PredBB != MBB && !PredBB->canFallThrough() &&
  1489. !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&
  1490. (PredTBB == MBB || PredFBB == MBB) &&
  1491. (!CurFallsThru || !CurTBB || !CurFBB) &&
  1492. (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
  1493. // If the current block doesn't fall through, just move it.
  1494. // If the current block can fall through and does not end with a
  1495. // conditional branch, we need to append an unconditional jump to
  1496. // the (current) next block. To avoid a possible compile-time
  1497. // infinite loop, move blocks only backward in this case.
  1498. // Also, if there are already 2 branches here, we cannot add a third;
  1499. // this means we have the case
  1500. // Bcc next
  1501. // B elsewhere
  1502. // next:
  1503. if (CurFallsThru) {
  1504. MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
  1505. CurCond.clear();
  1506. TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
  1507. }
  1508. MBB->moveAfter(PredBB);
  1509. MadeChange = true;
  1510. goto ReoptimizeBlock;
  1511. }
  1512. }
  1513. }
  1514. if (!CurFallsThru) {
  1515. // Check analyzable branch-successors to see if we can move this block
  1516. // before one.
  1517. if (!CurUnAnalyzable) {
  1518. for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {
  1519. if (!SuccBB)
  1520. continue;
  1521. // Analyze the branch at the end of the block before the succ.
  1522. MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
  1523. // If this block doesn't already fall-through to that successor, and
  1524. // if the succ doesn't already have a block that can fall through into
  1525. // it, we can arrange for the fallthrough to happen.
  1526. if (SuccBB != MBB && &*SuccPrev != MBB &&
  1527. !SuccPrev->canFallThrough()) {
  1528. MBB->moveBefore(SuccBB);
  1529. MadeChange = true;
  1530. goto ReoptimizeBlock;
  1531. }
  1532. }
  1533. }
  1534. // Okay, there is no really great place to put this block. If, however,
  1535. // the block before this one would be a fall-through if this block were
  1536. // removed, move this block to the end of the function. There is no real
  1537. // advantage in "falling through" to an EH block, so we don't want to
  1538. // perform this transformation for that case.
  1539. //
  1540. // Also, Windows EH introduced the possibility of an arbitrary number of
  1541. // successors to a given block. The analyzeBranch call does not consider
  1542. // exception handling and so we can get in a state where a block
  1543. // containing a call is followed by multiple EH blocks that would be
  1544. // rotated infinitely at the end of the function if the transformation
  1545. // below were performed for EH "FallThrough" blocks. Therefore, even if
  1546. // that appears not to be happening anymore, we should assume that it is
  1547. // possible and not remove the "!FallThrough()->isEHPad" condition below.
  1548. MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
  1549. SmallVector<MachineOperand, 4> PrevCond;
  1550. if (FallThrough != MF.end() &&
  1551. !FallThrough->isEHPad() &&
  1552. !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
  1553. PrevBB.isSuccessor(&*FallThrough)) {
  1554. MBB->moveAfter(&MF.back());
  1555. MadeChange = true;
  1556. return MadeChange;
  1557. }
  1558. }
  1559. }
  1560. return MadeChange;
  1561. }
  1562. //===----------------------------------------------------------------------===//
  1563. // Hoist Common Code
  1564. //===----------------------------------------------------------------------===//
  1565. bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
  1566. bool MadeChange = false;
  1567. for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ) {
  1568. MachineBasicBlock *MBB = &*I++;
  1569. MadeChange |= HoistCommonCodeInSuccs(MBB);
  1570. }
  1571. return MadeChange;
  1572. }
  1573. /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
  1574. /// its 'true' successor.
  1575. static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
  1576. MachineBasicBlock *TrueBB) {
  1577. for (MachineBasicBlock *SuccBB : BB->successors())
  1578. if (SuccBB != TrueBB)
  1579. return SuccBB;
  1580. return nullptr;
  1581. }
  1582. template <class Container>
  1583. static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI,
  1584. Container &Set) {
  1585. if (Reg.isPhysical()) {
  1586. for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
  1587. Set.insert(*AI);
  1588. } else {
  1589. Set.insert(Reg);
  1590. }
  1591. }
  1592. /// findHoistingInsertPosAndDeps - Find the location to move common instructions
  1593. /// in successors to. The location is usually just before the terminator,
  1594. /// however if the terminator is a conditional branch and its previous
  1595. /// instruction is the flag setting instruction, the previous instruction is
  1596. /// the preferred location. This function also gathers uses and defs of the
  1597. /// instructions from the insertion point to the end of the block. The data is
  1598. /// used by HoistCommonCodeInSuccs to ensure safety.
  1599. static
  1600. MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
  1601. const TargetInstrInfo *TII,
  1602. const TargetRegisterInfo *TRI,
  1603. SmallSet<Register, 4> &Uses,
  1604. SmallSet<Register, 4> &Defs) {
  1605. MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
  1606. if (!TII->isUnpredicatedTerminator(*Loc))
  1607. return MBB->end();
  1608. for (const MachineOperand &MO : Loc->operands()) {
  1609. if (!MO.isReg())
  1610. continue;
  1611. Register Reg = MO.getReg();
  1612. if (!Reg)
  1613. continue;
  1614. if (MO.isUse()) {
  1615. addRegAndItsAliases(Reg, TRI, Uses);
  1616. } else {
  1617. if (!MO.isDead())
  1618. // Don't try to hoist code in the rare case the terminator defines a
  1619. // register that is later used.
  1620. return MBB->end();
  1621. // If the terminator defines a register, make sure we don't hoist
  1622. // the instruction whose def might be clobbered by the terminator.
  1623. addRegAndItsAliases(Reg, TRI, Defs);
  1624. }
  1625. }
  1626. if (Uses.empty())
  1627. return Loc;
  1628. // If the terminator is the only instruction in the block and Uses is not
  1629. // empty (or we would have returned above), we can still safely hoist
  1630. // instructions just before the terminator as long as the Defs/Uses are not
  1631. // violated (which is checked in HoistCommonCodeInSuccs).
  1632. if (Loc == MBB->begin())
  1633. return Loc;
  1634. // The terminator is probably a conditional branch, try not to separate the
  1635. // branch from condition setting instruction.
  1636. MachineBasicBlock::iterator PI = prev_nodbg(Loc, MBB->begin());
  1637. bool IsDef = false;
  1638. for (const MachineOperand &MO : PI->operands()) {
  1639. // If PI has a regmask operand, it is probably a call. Separate away.
  1640. if (MO.isRegMask())
  1641. return Loc;
  1642. if (!MO.isReg() || MO.isUse())
  1643. continue;
  1644. Register Reg = MO.getReg();
  1645. if (!Reg)
  1646. continue;
  1647. if (Uses.count(Reg)) {
  1648. IsDef = true;
  1649. break;
  1650. }
  1651. }
  1652. if (!IsDef)
  1653. // The condition setting instruction is not just before the conditional
  1654. // branch.
  1655. return Loc;
  1656. // Be conservative, don't insert instruction above something that may have
  1657. // side-effects. And since it's potentially bad to separate flag setting
  1658. // instruction from the conditional branch, just abort the optimization
  1659. // completely.
  1660. // Also avoid moving code above predicated instruction since it's hard to
  1661. // reason about register liveness with predicated instruction.
  1662. bool DontMoveAcrossStore = true;
  1663. if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
  1664. return MBB->end();
  1665. // Find out what registers are live. Note this routine is ignoring other live
  1666. // registers which are only used by instructions in successor blocks.
  1667. for (const MachineOperand &MO : PI->operands()) {
  1668. if (!MO.isReg())
  1669. continue;
  1670. Register Reg = MO.getReg();
  1671. if (!Reg)
  1672. continue;
  1673. if (MO.isUse()) {
  1674. addRegAndItsAliases(Reg, TRI, Uses);
  1675. } else {
  1676. if (Uses.erase(Reg)) {
  1677. if (Register::isPhysicalRegister(Reg)) {
  1678. for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
  1679. Uses.erase(*SubRegs); // Use sub-registers to be conservative
  1680. }
  1681. }
  1682. addRegAndItsAliases(Reg, TRI, Defs);
  1683. }
  1684. }
  1685. return PI;
  1686. }
  1687. bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
  1688. MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
  1689. SmallVector<MachineOperand, 4> Cond;
  1690. if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
  1691. return false;
  1692. if (!FBB) FBB = findFalseBlock(MBB, TBB);
  1693. if (!FBB)
  1694. // Malformed bcc? True and false blocks are the same?
  1695. return false;
  1696. // Restrict the optimization to cases where MBB is the only predecessor,
  1697. // it is an obvious win.
  1698. if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
  1699. return false;
  1700. // Find a suitable position to hoist the common instructions to. Also figure
  1701. // out which registers are used or defined by instructions from the insertion
  1702. // point to the end of the block.
  1703. SmallSet<Register, 4> Uses, Defs;
  1704. MachineBasicBlock::iterator Loc =
  1705. findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
  1706. if (Loc == MBB->end())
  1707. return false;
  1708. bool HasDups = false;
  1709. SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;
  1710. MachineBasicBlock::iterator TIB = TBB->begin();
  1711. MachineBasicBlock::iterator FIB = FBB->begin();
  1712. MachineBasicBlock::iterator TIE = TBB->end();
  1713. MachineBasicBlock::iterator FIE = FBB->end();
  1714. while (TIB != TIE && FIB != FIE) {
  1715. // Skip dbg_value instructions. These do not count.
  1716. TIB = skipDebugInstructionsForward(TIB, TIE);
  1717. FIB = skipDebugInstructionsForward(FIB, FIE);
  1718. if (TIB == TIE || FIB == FIE)
  1719. break;
  1720. if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
  1721. break;
  1722. if (TII->isPredicated(*TIB))
  1723. // Hard to reason about register liveness with predicated instruction.
  1724. break;
  1725. bool IsSafe = true;
  1726. for (MachineOperand &MO : TIB->operands()) {
  1727. // Don't attempt to hoist instructions with register masks.
  1728. if (MO.isRegMask()) {
  1729. IsSafe = false;
  1730. break;
  1731. }
  1732. if (!MO.isReg())
  1733. continue;
  1734. Register Reg = MO.getReg();
  1735. if (!Reg)
  1736. continue;
  1737. if (MO.isDef()) {
  1738. if (Uses.count(Reg)) {
  1739. // Avoid clobbering a register that's used by the instruction at
  1740. // the point of insertion.
  1741. IsSafe = false;
  1742. break;
  1743. }
  1744. if (Defs.count(Reg) && !MO.isDead()) {
  1745. // Don't hoist the instruction if the def would be clobber by the
  1746. // instruction at the point insertion. FIXME: This is overly
  1747. // conservative. It should be possible to hoist the instructions
  1748. // in BB2 in the following example:
  1749. // BB1:
  1750. // r1, eflag = op1 r2, r3
  1751. // brcc eflag
  1752. //
  1753. // BB2:
  1754. // r1 = op2, ...
  1755. // = op3, killed r1
  1756. IsSafe = false;
  1757. break;
  1758. }
  1759. } else if (!ActiveDefsSet.count(Reg)) {
  1760. if (Defs.count(Reg)) {
  1761. // Use is defined by the instruction at the point of insertion.
  1762. IsSafe = false;
  1763. break;
  1764. }
  1765. if (MO.isKill() && Uses.count(Reg))
  1766. // Kills a register that's read by the instruction at the point of
  1767. // insertion. Remove the kill marker.
  1768. MO.setIsKill(false);
  1769. }
  1770. }
  1771. if (!IsSafe)
  1772. break;
  1773. bool DontMoveAcrossStore = true;
  1774. if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
  1775. break;
  1776. // Remove kills from ActiveDefsSet, these registers had short live ranges.
  1777. for (const MachineOperand &MO : TIB->operands()) {
  1778. if (!MO.isReg() || !MO.isUse() || !MO.isKill())
  1779. continue;
  1780. Register Reg = MO.getReg();
  1781. if (!Reg)
  1782. continue;
  1783. if (!AllDefsSet.count(Reg)) {
  1784. continue;
  1785. }
  1786. if (Reg.isPhysical()) {
  1787. for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
  1788. ActiveDefsSet.erase(*AI);
  1789. } else {
  1790. ActiveDefsSet.erase(Reg);
  1791. }
  1792. }
  1793. // Track local defs so we can update liveins.
  1794. for (const MachineOperand &MO : TIB->operands()) {
  1795. if (!MO.isReg() || !MO.isDef() || MO.isDead())
  1796. continue;
  1797. Register Reg = MO.getReg();
  1798. if (!Reg || Reg.isVirtual())
  1799. continue;
  1800. addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
  1801. addRegAndItsAliases(Reg, TRI, AllDefsSet);
  1802. }
  1803. HasDups = true;
  1804. ++TIB;
  1805. ++FIB;
  1806. }
  1807. if (!HasDups)
  1808. return false;
  1809. MBB->splice(Loc, TBB, TBB->begin(), TIB);
  1810. FBB->erase(FBB->begin(), FIB);
  1811. if (UpdateLiveIns) {
  1812. recomputeLiveIns(*TBB);
  1813. recomputeLiveIns(*FBB);
  1814. }
  1815. ++NumHoist;
  1816. return true;
  1817. }