TailDuplication.cpp 35 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970
  1. //===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // This pass duplicates basic blocks ending in unconditional branches into
  11. // the tails of their predecessors.
  12. //
  13. //===----------------------------------------------------------------------===//
  14. #define DEBUG_TYPE "tailduplication"
  15. #include "llvm/CodeGen/Passes.h"
  16. #include "llvm/ADT/DenseSet.h"
  17. #include "llvm/ADT/OwningPtr.h"
  18. #include "llvm/ADT/SetVector.h"
  19. #include "llvm/ADT/SmallSet.h"
  20. #include "llvm/ADT/Statistic.h"
  21. #include "llvm/CodeGen/MachineFunctionPass.h"
  22. #include "llvm/CodeGen/MachineInstrBuilder.h"
  23. #include "llvm/CodeGen/MachineModuleInfo.h"
  24. #include "llvm/CodeGen/MachineRegisterInfo.h"
  25. #include "llvm/CodeGen/MachineSSAUpdater.h"
  26. #include "llvm/CodeGen/RegisterScavenging.h"
  27. #include "llvm/Function.h"
  28. #include "llvm/Support/CommandLine.h"
  29. #include "llvm/Support/Debug.h"
  30. #include "llvm/Support/ErrorHandling.h"
  31. #include "llvm/Support/raw_ostream.h"
  32. #include "llvm/Target/TargetInstrInfo.h"
  33. #include "llvm/Target/TargetRegisterInfo.h"
  34. using namespace llvm;
  35. STATISTIC(NumTails , "Number of tails duplicated");
  36. STATISTIC(NumTailDups , "Number of tail duplicated blocks");
  37. STATISTIC(NumInstrDups , "Additional instructions due to tail duplication");
  38. STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
  39. STATISTIC(NumAddedPHIs , "Number of phis added");
  40. // Heuristic for tail duplication.
  41. static cl::opt<unsigned>
  42. TailDuplicateSize("tail-dup-size",
  43. cl::desc("Maximum instructions to consider tail duplicating"),
  44. cl::init(2), cl::Hidden);
  45. static cl::opt<bool>
  46. TailDupVerify("tail-dup-verify",
  47. cl::desc("Verify sanity of PHI instructions during taildup"),
  48. cl::init(false), cl::Hidden);
  49. static cl::opt<unsigned>
  50. TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden);
  51. typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy;
  52. namespace {
  53. /// TailDuplicatePass - Perform tail duplication.
  54. class TailDuplicatePass : public MachineFunctionPass {
  55. const TargetInstrInfo *TII;
  56. const TargetRegisterInfo *TRI;
  57. MachineModuleInfo *MMI;
  58. MachineRegisterInfo *MRI;
  59. OwningPtr<RegScavenger> RS;
  60. bool PreRegAlloc;
  61. // SSAUpdateVRs - A list of virtual registers for which to update SSA form.
  62. SmallVector<unsigned, 16> SSAUpdateVRs;
  63. // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of
  64. // source virtual registers.
  65. DenseMap<unsigned, AvailableValsTy> SSAUpdateVals;
  66. public:
  67. static char ID;
  68. explicit TailDuplicatePass() :
  69. MachineFunctionPass(ID), PreRegAlloc(false) {}
  70. virtual bool runOnMachineFunction(MachineFunction &MF);
  71. private:
  72. void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
  73. MachineBasicBlock *BB);
  74. void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
  75. MachineBasicBlock *PredBB,
  76. DenseMap<unsigned, unsigned> &LocalVRMap,
  77. SmallVector<std::pair<unsigned,unsigned>, 4> &Copies,
  78. const DenseSet<unsigned> &UsedByPhi,
  79. bool Remove);
  80. void DuplicateInstruction(MachineInstr *MI,
  81. MachineBasicBlock *TailBB,
  82. MachineBasicBlock *PredBB,
  83. MachineFunction &MF,
  84. DenseMap<unsigned, unsigned> &LocalVRMap,
  85. const DenseSet<unsigned> &UsedByPhi);
  86. void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
  87. SmallVector<MachineBasicBlock*, 8> &TDBBs,
  88. SmallSetVector<MachineBasicBlock*, 8> &Succs);
  89. bool TailDuplicateBlocks(MachineFunction &MF);
  90. bool shouldTailDuplicate(const MachineFunction &MF,
  91. bool IsSimple, MachineBasicBlock &TailBB);
  92. bool isSimpleBB(MachineBasicBlock *TailBB);
  93. bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
  94. bool duplicateSimpleBB(MachineBasicBlock *TailBB,
  95. SmallVector<MachineBasicBlock*, 8> &TDBBs,
  96. const DenseSet<unsigned> &RegsUsedByPhi,
  97. SmallVector<MachineInstr*, 16> &Copies);
  98. bool TailDuplicate(MachineBasicBlock *TailBB,
  99. bool IsSimple,
  100. MachineFunction &MF,
  101. SmallVector<MachineBasicBlock*, 8> &TDBBs,
  102. SmallVector<MachineInstr*, 16> &Copies);
  103. bool TailDuplicateAndUpdate(MachineBasicBlock *MBB,
  104. bool IsSimple,
  105. MachineFunction &MF);
  106. void RemoveDeadBlock(MachineBasicBlock *MBB);
  107. };
  108. char TailDuplicatePass::ID = 0;
  109. }
  110. char &llvm::TailDuplicateID = TailDuplicatePass::ID;
  111. INITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication",
  112. false, false)
  113. bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) {
  114. TII = MF.getTarget().getInstrInfo();
  115. TRI = MF.getTarget().getRegisterInfo();
  116. MRI = &MF.getRegInfo();
  117. MMI = getAnalysisIfAvailable<MachineModuleInfo>();
  118. PreRegAlloc = MRI->isSSA();
  119. RS.reset();
  120. if (MRI->tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF))
  121. RS.reset(new RegScavenger());
  122. bool MadeChange = false;
  123. while (TailDuplicateBlocks(MF))
  124. MadeChange = true;
  125. return MadeChange;
  126. }
  127. static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
  128. for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {
  129. MachineBasicBlock *MBB = I;
  130. SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(),
  131. MBB->pred_end());
  132. MachineBasicBlock::iterator MI = MBB->begin();
  133. while (MI != MBB->end()) {
  134. if (!MI->isPHI())
  135. break;
  136. for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
  137. PE = Preds.end(); PI != PE; ++PI) {
  138. MachineBasicBlock *PredBB = *PI;
  139. bool Found = false;
  140. for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
  141. MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB();
  142. if (PHIBB == PredBB) {
  143. Found = true;
  144. break;
  145. }
  146. }
  147. if (!Found) {
  148. dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
  149. dbgs() << " missing input from predecessor BB#"
  150. << PredBB->getNumber() << '\n';
  151. llvm_unreachable(0);
  152. }
  153. }
  154. for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
  155. MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB();
  156. if (CheckExtra && !Preds.count(PHIBB)) {
  157. dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber()
  158. << ": " << *MI;
  159. dbgs() << " extra input from predecessor BB#"
  160. << PHIBB->getNumber() << '\n';
  161. llvm_unreachable(0);
  162. }
  163. if (PHIBB->getNumber() < 0) {
  164. dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
  165. dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n';
  166. llvm_unreachable(0);
  167. }
  168. }
  169. ++MI;
  170. }
  171. }
  172. }
  173. /// TailDuplicateAndUpdate - Tail duplicate the block and cleanup.
  174. bool
  175. TailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB,
  176. bool IsSimple,
  177. MachineFunction &MF) {
  178. // Save the successors list.
  179. SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(),
  180. MBB->succ_end());
  181. SmallVector<MachineBasicBlock*, 8> TDBBs;
  182. SmallVector<MachineInstr*, 16> Copies;
  183. if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies))
  184. return false;
  185. ++NumTails;
  186. SmallVector<MachineInstr*, 8> NewPHIs;
  187. MachineSSAUpdater SSAUpdate(MF, &NewPHIs);
  188. // TailBB's immediate successors are now successors of those predecessors
  189. // which duplicated TailBB. Add the predecessors as sources to the PHI
  190. // instructions.
  191. bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken();
  192. if (PreRegAlloc)
  193. UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);
  194. // If it is dead, remove it.
  195. if (isDead) {
  196. NumInstrDups -= MBB->size();
  197. RemoveDeadBlock(MBB);
  198. ++NumDeadBlocks;
  199. }
  200. // Update SSA form.
  201. if (!SSAUpdateVRs.empty()) {
  202. for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {
  203. unsigned VReg = SSAUpdateVRs[i];
  204. SSAUpdate.Initialize(VReg);
  205. // If the original definition is still around, add it as an available
  206. // value.
  207. MachineInstr *DefMI = MRI->getVRegDef(VReg);
  208. MachineBasicBlock *DefBB = 0;
  209. if (DefMI) {
  210. DefBB = DefMI->getParent();
  211. SSAUpdate.AddAvailableValue(DefBB, VReg);
  212. }
  213. // Add the new vregs as available values.
  214. DenseMap<unsigned, AvailableValsTy>::iterator LI =
  215. SSAUpdateVals.find(VReg);
  216. for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
  217. MachineBasicBlock *SrcBB = LI->second[j].first;
  218. unsigned SrcReg = LI->second[j].second;
  219. SSAUpdate.AddAvailableValue(SrcBB, SrcReg);
  220. }
  221. // Rewrite uses that are outside of the original def's block.
  222. MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);
  223. while (UI != MRI->use_end()) {
  224. MachineOperand &UseMO = UI.getOperand();
  225. MachineInstr *UseMI = &*UI;
  226. ++UI;
  227. if (UseMI->isDebugValue()) {
  228. // SSAUpdate can replace the use with an undef. That creates
  229. // a debug instruction that is a kill.
  230. // FIXME: Should it SSAUpdate job to delete debug instructions
  231. // instead of replacing the use with undef?
  232. UseMI->eraseFromParent();
  233. continue;
  234. }
  235. if (UseMI->getParent() == DefBB && !UseMI->isPHI())
  236. continue;
  237. SSAUpdate.RewriteUse(UseMO);
  238. }
  239. }
  240. SSAUpdateVRs.clear();
  241. SSAUpdateVals.clear();
  242. }
  243. // Eliminate some of the copies inserted by tail duplication to maintain
  244. // SSA form.
  245. for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
  246. MachineInstr *Copy = Copies[i];
  247. if (!Copy->isCopy())
  248. continue;
  249. unsigned Dst = Copy->getOperand(0).getReg();
  250. unsigned Src = Copy->getOperand(1).getReg();
  251. if (MRI->hasOneNonDBGUse(Src) &&
  252. MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) {
  253. // Copy is the only use. Do trivial copy propagation here.
  254. MRI->replaceRegWith(Dst, Src);
  255. Copy->eraseFromParent();
  256. }
  257. }
  258. if (NewPHIs.size())
  259. NumAddedPHIs += NewPHIs.size();
  260. return true;
  261. }
  262. /// TailDuplicateBlocks - Look for small blocks that are unconditionally
  263. /// branched to and do not fall through. Tail-duplicate their instructions
  264. /// into their predecessors to eliminate (dynamic) branches.
  265. bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) {
  266. bool MadeChange = false;
  267. if (PreRegAlloc && TailDupVerify) {
  268. DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
  269. VerifyPHIs(MF, true);
  270. }
  271. for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
  272. MachineBasicBlock *MBB = I++;
  273. if (NumTails == TailDupLimit)
  274. break;
  275. bool IsSimple = isSimpleBB(MBB);
  276. if (!shouldTailDuplicate(MF, IsSimple, *MBB))
  277. continue;
  278. MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF);
  279. }
  280. if (PreRegAlloc && TailDupVerify)
  281. VerifyPHIs(MF, false);
  282. return MadeChange;
  283. }
  284. static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,
  285. const MachineRegisterInfo *MRI) {
  286. for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
  287. UE = MRI->use_end(); UI != UE; ++UI) {
  288. MachineInstr *UseMI = &*UI;
  289. if (UseMI->isDebugValue())
  290. continue;
  291. if (UseMI->getParent() != BB)
  292. return true;
  293. }
  294. return false;
  295. }
  296. static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) {
  297. for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)
  298. if (MI->getOperand(i+1).getMBB() == SrcBB)
  299. return i;
  300. return 0;
  301. }
  302. // Remember which registers are used by phis in this block. This is
  303. // used to determine which registers are liveout while modifying the
  304. // block (which is why we need to copy the information).
  305. static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
  306. DenseSet<unsigned> *UsedByPhi) {
  307. for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end();
  308. I != E; ++I) {
  309. const MachineInstr &MI = *I;
  310. if (!MI.isPHI())
  311. break;
  312. for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
  313. unsigned SrcReg = MI.getOperand(i).getReg();
  314. UsedByPhi->insert(SrcReg);
  315. }
  316. }
  317. }
  318. /// AddSSAUpdateEntry - Add a definition and source virtual registers pair for
  319. /// SSA update.
  320. void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
  321. MachineBasicBlock *BB) {
  322. DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg);
  323. if (LI != SSAUpdateVals.end())
  324. LI->second.push_back(std::make_pair(BB, NewReg));
  325. else {
  326. AvailableValsTy Vals;
  327. Vals.push_back(std::make_pair(BB, NewReg));
  328. SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));
  329. SSAUpdateVRs.push_back(OrigReg);
  330. }
  331. }
  332. /// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB.
  333. /// Remember the source register that's contributed by PredBB and update SSA
  334. /// update map.
  335. void TailDuplicatePass::ProcessPHI(MachineInstr *MI,
  336. MachineBasicBlock *TailBB,
  337. MachineBasicBlock *PredBB,
  338. DenseMap<unsigned, unsigned> &LocalVRMap,
  339. SmallVector<std::pair<unsigned,unsigned>, 4> &Copies,
  340. const DenseSet<unsigned> &RegsUsedByPhi,
  341. bool Remove) {
  342. unsigned DefReg = MI->getOperand(0).getReg();
  343. unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);
  344. assert(SrcOpIdx && "Unable to find matching PHI source?");
  345. unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg();
  346. const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
  347. LocalVRMap.insert(std::make_pair(DefReg, SrcReg));
  348. // Insert a copy from source to the end of the block. The def register is the
  349. // available value liveout of the block.
  350. unsigned NewDef = MRI->createVirtualRegister(RC);
  351. Copies.push_back(std::make_pair(NewDef, SrcReg));
  352. if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg))
  353. AddSSAUpdateEntry(DefReg, NewDef, PredBB);
  354. if (!Remove)
  355. return;
  356. // Remove PredBB from the PHI node.
  357. MI->RemoveOperand(SrcOpIdx+1);
  358. MI->RemoveOperand(SrcOpIdx);
  359. if (MI->getNumOperands() == 1)
  360. MI->eraseFromParent();
  361. }
  362. /// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update
  363. /// the source operands due to earlier PHI translation.
  364. void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI,
  365. MachineBasicBlock *TailBB,
  366. MachineBasicBlock *PredBB,
  367. MachineFunction &MF,
  368. DenseMap<unsigned, unsigned> &LocalVRMap,
  369. const DenseSet<unsigned> &UsedByPhi) {
  370. MachineInstr *NewMI = TII->duplicate(MI, MF);
  371. for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
  372. MachineOperand &MO = NewMI->getOperand(i);
  373. if (!MO.isReg())
  374. continue;
  375. unsigned Reg = MO.getReg();
  376. if (!TargetRegisterInfo::isVirtualRegister(Reg))
  377. continue;
  378. if (MO.isDef()) {
  379. const TargetRegisterClass *RC = MRI->getRegClass(Reg);
  380. unsigned NewReg = MRI->createVirtualRegister(RC);
  381. MO.setReg(NewReg);
  382. LocalVRMap.insert(std::make_pair(Reg, NewReg));
  383. if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg))
  384. AddSSAUpdateEntry(Reg, NewReg, PredBB);
  385. } else {
  386. DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg);
  387. if (VI != LocalVRMap.end()) {
  388. MO.setReg(VI->second);
  389. MRI->constrainRegClass(VI->second, MRI->getRegClass(Reg));
  390. }
  391. }
  392. }
  393. PredBB->insert(PredBB->instr_end(), NewMI);
  394. }
  395. /// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor
  396. /// blocks, the successors have gained new predecessors. Update the PHI
  397. /// instructions in them accordingly.
  398. void
  399. TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
  400. SmallVector<MachineBasicBlock*, 8> &TDBBs,
  401. SmallSetVector<MachineBasicBlock*,8> &Succs) {
  402. for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(),
  403. SE = Succs.end(); SI != SE; ++SI) {
  404. MachineBasicBlock *SuccBB = *SI;
  405. for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end();
  406. II != EE; ++II) {
  407. if (!II->isPHI())
  408. break;
  409. MachineInstrBuilder MIB(*FromBB->getParent(), II);
  410. unsigned Idx = 0;
  411. for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) {
  412. MachineOperand &MO = II->getOperand(i+1);
  413. if (MO.getMBB() == FromBB) {
  414. Idx = i;
  415. break;
  416. }
  417. }
  418. assert(Idx != 0);
  419. MachineOperand &MO0 = II->getOperand(Idx);
  420. unsigned Reg = MO0.getReg();
  421. if (isDead) {
  422. // Folded into the previous BB.
  423. // There could be duplicate phi source entries. FIXME: Should sdisel
  424. // or earlier pass fixed this?
  425. for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) {
  426. MachineOperand &MO = II->getOperand(i+1);
  427. if (MO.getMBB() == FromBB) {
  428. II->RemoveOperand(i+1);
  429. II->RemoveOperand(i);
  430. }
  431. }
  432. } else
  433. Idx = 0;
  434. // If Idx is set, the operands at Idx and Idx+1 must be removed.
  435. // We reuse the location to avoid expensive RemoveOperand calls.
  436. DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg);
  437. if (LI != SSAUpdateVals.end()) {
  438. // This register is defined in the tail block.
  439. for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
  440. MachineBasicBlock *SrcBB = LI->second[j].first;
  441. // If we didn't duplicate a bb into a particular predecessor, we
  442. // might still have added an entry to SSAUpdateVals to correcly
  443. // recompute SSA. If that case, avoid adding a dummy extra argument
  444. // this PHI.
  445. if (!SrcBB->isSuccessor(SuccBB))
  446. continue;
  447. unsigned SrcReg = LI->second[j].second;
  448. if (Idx != 0) {
  449. II->getOperand(Idx).setReg(SrcReg);
  450. II->getOperand(Idx+1).setMBB(SrcBB);
  451. Idx = 0;
  452. } else {
  453. MIB.addReg(SrcReg).addMBB(SrcBB);
  454. }
  455. }
  456. } else {
  457. // Live in tail block, must also be live in predecessors.
  458. for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) {
  459. MachineBasicBlock *SrcBB = TDBBs[j];
  460. if (Idx != 0) {
  461. II->getOperand(Idx).setReg(Reg);
  462. II->getOperand(Idx+1).setMBB(SrcBB);
  463. Idx = 0;
  464. } else {
  465. MIB.addReg(Reg).addMBB(SrcBB);
  466. }
  467. }
  468. }
  469. if (Idx != 0) {
  470. II->RemoveOperand(Idx+1);
  471. II->RemoveOperand(Idx);
  472. }
  473. }
  474. }
  475. }
  476. /// shouldTailDuplicate - Determine if it is profitable to duplicate this block.
  477. bool
  478. TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF,
  479. bool IsSimple,
  480. MachineBasicBlock &TailBB) {
  481. // Only duplicate blocks that end with unconditional branches.
  482. if (TailBB.canFallThrough())
  483. return false;
  484. // Don't try to tail-duplicate single-block loops.
  485. if (TailBB.isSuccessor(&TailBB))
  486. return false;
  487. // Set the limit on the cost to duplicate. When optimizing for size,
  488. // duplicate only one, because one branch instruction can be eliminated to
  489. // compensate for the duplication.
  490. unsigned MaxDuplicateCount;
  491. if (TailDuplicateSize.getNumOccurrences() == 0 &&
  492. MF.getFunction()->getFnAttributes().
  493. hasAttribute(Attribute::OptimizeForSize))
  494. MaxDuplicateCount = 1;
  495. else
  496. MaxDuplicateCount = TailDuplicateSize;
  497. // If the target has hardware branch prediction that can handle indirect
  498. // branches, duplicating them can often make them predictable when there
  499. // are common paths through the code. The limit needs to be high enough
  500. // to allow undoing the effects of tail merging and other optimizations
  501. // that rearrange the predecessors of the indirect branch.
  502. bool HasIndirectbr = false;
  503. if (!TailBB.empty())
  504. HasIndirectbr = TailBB.back().isIndirectBranch();
  505. if (HasIndirectbr && PreRegAlloc)
  506. MaxDuplicateCount = 20;
  507. // Check the instructions in the block to determine whether tail-duplication
  508. // is invalid or unlikely to be profitable.
  509. unsigned InstrCount = 0;
  510. for (MachineBasicBlock::iterator I = TailBB.begin(); I != TailBB.end(); ++I) {
  511. // Non-duplicable things shouldn't be tail-duplicated.
  512. if (I->isNotDuplicable())
  513. return false;
  514. // Do not duplicate 'return' instructions if this is a pre-regalloc run.
  515. // A return may expand into a lot more instructions (e.g. reload of callee
  516. // saved registers) after PEI.
  517. if (PreRegAlloc && I->isReturn())
  518. return false;
  519. // Avoid duplicating calls before register allocation. Calls presents a
  520. // barrier to register allocation so duplicating them may end up increasing
  521. // spills.
  522. if (PreRegAlloc && I->isCall())
  523. return false;
  524. if (!I->isPHI() && !I->isDebugValue())
  525. InstrCount += 1;
  526. if (InstrCount > MaxDuplicateCount)
  527. return false;
  528. }
  529. if (HasIndirectbr && PreRegAlloc)
  530. return true;
  531. if (IsSimple)
  532. return true;
  533. if (!PreRegAlloc)
  534. return true;
  535. return canCompletelyDuplicateBB(TailBB);
  536. }
  537. /// isSimpleBB - True if this BB has only one unconditional jump.
  538. bool
  539. TailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) {
  540. if (TailBB->succ_size() != 1)
  541. return false;
  542. if (TailBB->pred_empty())
  543. return false;
  544. MachineBasicBlock::iterator I = TailBB->begin();
  545. MachineBasicBlock::iterator E = TailBB->end();
  546. while (I != E && I->isDebugValue())
  547. ++I;
  548. if (I == E)
  549. return true;
  550. return I->isUnconditionalBranch();
  551. }
  552. static bool
  553. bothUsedInPHI(const MachineBasicBlock &A,
  554. SmallPtrSet<MachineBasicBlock*, 8> SuccsB) {
  555. for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(),
  556. SE = A.succ_end(); SI != SE; ++SI) {
  557. MachineBasicBlock *BB = *SI;
  558. if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
  559. return true;
  560. }
  561. return false;
  562. }
  563. bool
  564. TailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
  565. SmallPtrSet<MachineBasicBlock*, 8> Succs(BB.succ_begin(), BB.succ_end());
  566. for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(),
  567. PE = BB.pred_end(); PI != PE; ++PI) {
  568. MachineBasicBlock *PredBB = *PI;
  569. if (PredBB->succ_size() > 1)
  570. return false;
  571. MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL;
  572. SmallVector<MachineOperand, 4> PredCond;
  573. if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true))
  574. return false;
  575. if (!PredCond.empty())
  576. return false;
  577. }
  578. return true;
  579. }
  580. bool
  581. TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB,
  582. SmallVector<MachineBasicBlock*, 8> &TDBBs,
  583. const DenseSet<unsigned> &UsedByPhi,
  584. SmallVector<MachineInstr*, 16> &Copies) {
  585. SmallPtrSet<MachineBasicBlock*, 8> Succs(TailBB->succ_begin(),
  586. TailBB->succ_end());
  587. SmallVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(),
  588. TailBB->pred_end());
  589. bool Changed = false;
  590. for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
  591. PE = Preds.end(); PI != PE; ++PI) {
  592. MachineBasicBlock *PredBB = *PI;
  593. if (PredBB->getLandingPadSuccessor())
  594. continue;
  595. if (bothUsedInPHI(*PredBB, Succs))
  596. continue;
  597. MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL;
  598. SmallVector<MachineOperand, 4> PredCond;
  599. if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true))
  600. continue;
  601. Changed = true;
  602. DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
  603. << "From simple Succ: " << *TailBB);
  604. MachineBasicBlock *NewTarget = *TailBB->succ_begin();
  605. MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(PredBB));
  606. // Make PredFBB explicit.
  607. if (PredCond.empty())
  608. PredFBB = PredTBB;
  609. // Make fall through explicit.
  610. if (!PredTBB)
  611. PredTBB = NextBB;
  612. if (!PredFBB)
  613. PredFBB = NextBB;
  614. // Redirect
  615. if (PredFBB == TailBB)
  616. PredFBB = NewTarget;
  617. if (PredTBB == TailBB)
  618. PredTBB = NewTarget;
  619. // Make the branch unconditional if possible
  620. if (PredTBB == PredFBB) {
  621. PredCond.clear();
  622. PredFBB = NULL;
  623. }
  624. // Avoid adding fall through branches.
  625. if (PredFBB == NextBB)
  626. PredFBB = NULL;
  627. if (PredTBB == NextBB && PredFBB == NULL)
  628. PredTBB = NULL;
  629. TII->RemoveBranch(*PredBB);
  630. if (PredTBB)
  631. TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc());
  632. PredBB->removeSuccessor(TailBB);
  633. unsigned NumSuccessors = PredBB->succ_size();
  634. assert(NumSuccessors <= 1);
  635. if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget)
  636. PredBB->addSuccessor(NewTarget);
  637. TDBBs.push_back(PredBB);
  638. }
  639. return Changed;
  640. }
  641. /// TailDuplicate - If it is profitable, duplicate TailBB's contents in each
  642. /// of its predecessors.
  643. bool
  644. TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
  645. bool IsSimple,
  646. MachineFunction &MF,
  647. SmallVector<MachineBasicBlock*, 8> &TDBBs,
  648. SmallVector<MachineInstr*, 16> &Copies) {
  649. DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n');
  650. DenseSet<unsigned> UsedByPhi;
  651. getRegsUsedByPHIs(*TailBB, &UsedByPhi);
  652. if (IsSimple)
  653. return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies);
  654. // Iterate through all the unique predecessors and tail-duplicate this
  655. // block into them, if possible. Copying the list ahead of time also
  656. // avoids trouble with the predecessor list reallocating.
  657. bool Changed = false;
  658. SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(),
  659. TailBB->pred_end());
  660. for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
  661. PE = Preds.end(); PI != PE; ++PI) {
  662. MachineBasicBlock *PredBB = *PI;
  663. assert(TailBB != PredBB &&
  664. "Single-block loop should have been rejected earlier!");
  665. // EH edges are ignored by AnalyzeBranch.
  666. if (PredBB->succ_size() > 1)
  667. continue;
  668. MachineBasicBlock *PredTBB, *PredFBB;
  669. SmallVector<MachineOperand, 4> PredCond;
  670. if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true))
  671. continue;
  672. if (!PredCond.empty())
  673. continue;
  674. // Don't duplicate into a fall-through predecessor (at least for now).
  675. if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
  676. continue;
  677. DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
  678. << "From Succ: " << *TailBB);
  679. TDBBs.push_back(PredBB);
  680. // Remove PredBB's unconditional branch.
  681. TII->RemoveBranch(*PredBB);
  682. if (RS && !TailBB->livein_empty()) {
  683. // Update PredBB livein.
  684. RS->enterBasicBlock(PredBB);
  685. if (!PredBB->empty())
  686. RS->forward(prior(PredBB->end()));
  687. BitVector RegsLiveAtExit(TRI->getNumRegs());
  688. RS->getRegsUsed(RegsLiveAtExit, false);
  689. for (MachineBasicBlock::livein_iterator I = TailBB->livein_begin(),
  690. E = TailBB->livein_end(); I != E; ++I) {
  691. if (!RegsLiveAtExit[*I])
  692. // If a register is previously livein to the tail but it's not live
  693. // at the end of predecessor BB, then it should be added to its
  694. // livein list.
  695. PredBB->addLiveIn(*I);
  696. }
  697. }
  698. // Clone the contents of TailBB into PredBB.
  699. DenseMap<unsigned, unsigned> LocalVRMap;
  700. SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos;
  701. // Use instr_iterator here to properly handle bundles, e.g.
  702. // ARM Thumb2 IT block.
  703. MachineBasicBlock::instr_iterator I = TailBB->instr_begin();
  704. while (I != TailBB->instr_end()) {
  705. MachineInstr *MI = &*I;
  706. ++I;
  707. if (MI->isPHI()) {
  708. // Replace the uses of the def of the PHI with the register coming
  709. // from PredBB.
  710. ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
  711. } else {
  712. // Replace def of virtual registers with new registers, and update
  713. // uses with PHI source register or the new registers.
  714. DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi);
  715. }
  716. }
  717. MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator();
  718. for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) {
  719. Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(),
  720. TII->get(TargetOpcode::COPY),
  721. CopyInfos[i].first).addReg(CopyInfos[i].second));
  722. }
  723. // Simplify
  724. TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true);
  725. NumInstrDups += TailBB->size() - 1; // subtract one for removed branch
  726. // Update the CFG.
  727. PredBB->removeSuccessor(PredBB->succ_begin());
  728. assert(PredBB->succ_empty() &&
  729. "TailDuplicate called on block with multiple successors!");
  730. for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(),
  731. E = TailBB->succ_end(); I != E; ++I)
  732. PredBB->addSuccessor(*I);
  733. Changed = true;
  734. ++NumTailDups;
  735. }
  736. // If TailBB was duplicated into all its predecessors except for the prior
  737. // block, which falls through unconditionally, move the contents of this
  738. // block into the prior block.
  739. MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB));
  740. MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
  741. SmallVector<MachineOperand, 4> PriorCond;
  742. // This has to check PrevBB->succ_size() because EH edges are ignored by
  743. // AnalyzeBranch.
  744. if (PrevBB->succ_size() == 1 &&
  745. !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) &&
  746. PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 &&
  747. !TailBB->hasAddressTaken()) {
  748. DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
  749. << "From MBB: " << *TailBB);
  750. if (PreRegAlloc) {
  751. DenseMap<unsigned, unsigned> LocalVRMap;
  752. SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos;
  753. MachineBasicBlock::iterator I = TailBB->begin();
  754. // Process PHI instructions first.
  755. while (I != TailBB->end() && I->isPHI()) {
  756. // Replace the uses of the def of the PHI with the register coming
  757. // from PredBB.
  758. MachineInstr *MI = &*I++;
  759. ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true);
  760. if (MI->getParent())
  761. MI->eraseFromParent();
  762. }
  763. // Now copy the non-PHI instructions.
  764. while (I != TailBB->end()) {
  765. // Replace def of virtual registers with new registers, and update
  766. // uses with PHI source register or the new registers.
  767. MachineInstr *MI = &*I++;
  768. assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
  769. DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi);
  770. MI->eraseFromParent();
  771. }
  772. MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator();
  773. for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) {
  774. Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(),
  775. TII->get(TargetOpcode::COPY),
  776. CopyInfos[i].first)
  777. .addReg(CopyInfos[i].second));
  778. }
  779. } else {
  780. // No PHIs to worry about, just splice the instructions over.
  781. PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
  782. }
  783. PrevBB->removeSuccessor(PrevBB->succ_begin());
  784. assert(PrevBB->succ_empty());
  785. PrevBB->transferSuccessors(TailBB);
  786. TDBBs.push_back(PrevBB);
  787. Changed = true;
  788. }
  789. // If this is after register allocation, there are no phis to fix.
  790. if (!PreRegAlloc)
  791. return Changed;
  792. // If we made no changes so far, we are safe.
  793. if (!Changed)
  794. return Changed;
  795. // Handle the nasty case in that we duplicated a block that is part of a loop
  796. // into some but not all of its predecessors. For example:
  797. // 1 -> 2 <-> 3 |
  798. // \ |
  799. // \---> rest |
  800. // if we duplicate 2 into 1 but not into 3, we end up with
  801. // 12 -> 3 <-> 2 -> rest |
  802. // \ / |
  803. // \----->-----/ |
  804. // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced
  805. // with a phi in 3 (which now dominates 2).
  806. // What we do here is introduce a copy in 3 of the register defined by the
  807. // phi, just like when we are duplicating 2 into 3, but we don't copy any
  808. // real instructions or remove the 3 -> 2 edge from the phi in 2.
  809. for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
  810. PE = Preds.end(); PI != PE; ++PI) {
  811. MachineBasicBlock *PredBB = *PI;
  812. if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end())
  813. continue;
  814. // EH edges
  815. if (PredBB->succ_size() != 1)
  816. continue;
  817. DenseMap<unsigned, unsigned> LocalVRMap;
  818. SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos;
  819. MachineBasicBlock::iterator I = TailBB->begin();
  820. // Process PHI instructions first.
  821. while (I != TailBB->end() && I->isPHI()) {
  822. // Replace the uses of the def of the PHI with the register coming
  823. // from PredBB.
  824. MachineInstr *MI = &*I++;
  825. ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
  826. }
  827. MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator();
  828. for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) {
  829. Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(),
  830. TII->get(TargetOpcode::COPY),
  831. CopyInfos[i].first).addReg(CopyInfos[i].second));
  832. }
  833. }
  834. return Changed;
  835. }
  836. /// RemoveDeadBlock - Remove the specified dead machine basic block from the
  837. /// function, updating the CFG.
  838. void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) {
  839. assert(MBB->pred_empty() && "MBB must be dead!");
  840. DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
  841. // Remove all successors.
  842. while (!MBB->succ_empty())
  843. MBB->removeSuccessor(MBB->succ_end()-1);
  844. // Remove the block.
  845. MBB->eraseFromParent();
  846. }