ShrinkWrap.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390
  1. //===-- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ---===//
  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 looks for safe point where the prologue and epilogue can be
  11. // inserted.
  12. // The safe point for the prologue (resp. epilogue) is called Save
  13. // (resp. Restore).
  14. // A point is safe for prologue (resp. epilogue) if and only if
  15. // it 1) dominates (resp. post-dominates) all the frame related operations and
  16. // between 2) two executions of the Save (resp. Restore) point there is an
  17. // execution of the Restore (resp. Save) point.
  18. //
  19. // For instance, the following points are safe:
  20. // for (int i = 0; i < 10; ++i) {
  21. // Save
  22. // ...
  23. // Restore
  24. // }
  25. // Indeed, the execution looks like Save -> Restore -> Save -> Restore ...
  26. // And the following points are not:
  27. // for (int i = 0; i < 10; ++i) {
  28. // Save
  29. // ...
  30. // }
  31. // for (int i = 0; i < 10; ++i) {
  32. // ...
  33. // Restore
  34. // }
  35. // Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore.
  36. //
  37. // This pass also ensures that the safe points are 3) cheaper than the regular
  38. // entry and exits blocks.
  39. //
  40. // Property #1 is ensured via the use of MachineDominatorTree and
  41. // MachinePostDominatorTree.
  42. // Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both
  43. // points must be in the same loop.
  44. // Property #3 is ensured via the MachineBlockFrequencyInfo.
  45. //
  46. // If this pass found points matching all this properties, then
  47. // MachineFrameInfo is updated this that information.
  48. //===----------------------------------------------------------------------===//
  49. #include "llvm/ADT/Statistic.h"
  50. // To check for profitability.
  51. #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  52. // For property #1 for Save.
  53. #include "llvm/CodeGen/MachineDominators.h"
  54. #include "llvm/CodeGen/MachineFunctionPass.h"
  55. // To record the result of the analysis.
  56. #include "llvm/CodeGen/MachineFrameInfo.h"
  57. // For property #2.
  58. #include "llvm/CodeGen/MachineLoopInfo.h"
  59. // For property #1 for Restore.
  60. #include "llvm/CodeGen/MachinePostDominators.h"
  61. #include "llvm/CodeGen/Passes.h"
  62. // To know about callee-saved.
  63. #include "llvm/CodeGen/RegisterClassInfo.h"
  64. #include "llvm/Support/Debug.h"
  65. // To query the target about frame lowering.
  66. #include "llvm/Target/TargetFrameLowering.h"
  67. // To know about frame setup operation.
  68. #include "llvm/Target/TargetInstrInfo.h"
  69. // To access TargetInstrInfo.
  70. #include "llvm/Target/TargetSubtargetInfo.h"
  71. // //
  72. ///////////////////////////////////////////////////////////////////////////////
  73. #define DEBUG_TYPE "shrink-wrap"
  74. using namespace llvm;
  75. STATISTIC(NumFunc, "Number of functions");
  76. STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
  77. STATISTIC(NumCandidatesDropped,
  78. "Number of shrink-wrapping candidates dropped because of frequency");
  79. namespace {
  80. /// \brief Class to determine where the safe point to insert the
  81. /// prologue and epilogue are.
  82. /// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
  83. /// shrink-wrapping term for prologue/epilogue placement, this pass
  84. /// does not rely on expensive data-flow analysis. Instead we use the
  85. /// dominance properties and loop information to decide which point
  86. /// are safe for such insertion.
  87. class ShrinkWrap : public MachineFunctionPass {
  88. /// Hold callee-saved information.
  89. RegisterClassInfo RCI;
  90. MachineDominatorTree *MDT;
  91. MachinePostDominatorTree *MPDT;
  92. /// Current safe point found for the prologue.
  93. /// The prologue will be inserted before the first instruction
  94. /// in this basic block.
  95. MachineBasicBlock *Save;
  96. /// Current safe point found for the epilogue.
  97. /// The epilogue will be inserted before the first terminator instruction
  98. /// in this basic block.
  99. MachineBasicBlock *Restore;
  100. /// Hold the information of the basic block frequency.
  101. /// Use to check the profitability of the new points.
  102. MachineBlockFrequencyInfo *MBFI;
  103. /// Hold the loop information. Used to determine if Save and Restore
  104. /// are in the same loop.
  105. MachineLoopInfo *MLI;
  106. /// Frequency of the Entry block.
  107. uint64_t EntryFreq;
  108. /// Current opcode for frame setup.
  109. unsigned FrameSetupOpcode;
  110. /// Current opcode for frame destroy.
  111. unsigned FrameDestroyOpcode;
  112. /// Entry block.
  113. const MachineBasicBlock *Entry;
  114. /// \brief Check if \p MI uses or defines a callee-saved register or
  115. /// a frame index. If this is the case, this means \p MI must happen
  116. /// after Save and before Restore.
  117. bool useOrDefCSROrFI(const MachineInstr &MI) const;
  118. /// \brief Update the Save and Restore points such that \p MBB is in
  119. /// the region that is dominated by Save and post-dominated by Restore
  120. /// and Save and Restore still match the safe point definition.
  121. /// Such point may not exist and Save and/or Restore may be null after
  122. /// this call.
  123. void updateSaveRestorePoints(MachineBasicBlock &MBB);
  124. /// \brief Initialize the pass for \p MF.
  125. void init(MachineFunction &MF) {
  126. RCI.runOnMachineFunction(MF);
  127. MDT = &getAnalysis<MachineDominatorTree>();
  128. MPDT = &getAnalysis<MachinePostDominatorTree>();
  129. Save = nullptr;
  130. Restore = nullptr;
  131. MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
  132. MLI = &getAnalysis<MachineLoopInfo>();
  133. EntryFreq = MBFI->getEntryFreq();
  134. const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
  135. FrameSetupOpcode = TII.getCallFrameSetupOpcode();
  136. FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
  137. Entry = &MF.front();
  138. ++NumFunc;
  139. }
  140. /// Check whether or not Save and Restore points are still interesting for
  141. /// shrink-wrapping.
  142. bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
  143. public:
  144. static char ID;
  145. ShrinkWrap() : MachineFunctionPass(ID) {
  146. initializeShrinkWrapPass(*PassRegistry::getPassRegistry());
  147. }
  148. void getAnalysisUsage(AnalysisUsage &AU) const override {
  149. AU.setPreservesAll();
  150. AU.addRequired<MachineBlockFrequencyInfo>();
  151. AU.addRequired<MachineDominatorTree>();
  152. AU.addRequired<MachinePostDominatorTree>();
  153. AU.addRequired<MachineLoopInfo>();
  154. MachineFunctionPass::getAnalysisUsage(AU);
  155. }
  156. const char *getPassName() const override {
  157. return "Shrink Wrapping analysis";
  158. }
  159. /// \brief Perform the shrink-wrapping analysis and update
  160. /// the MachineFrameInfo attached to \p MF with the results.
  161. bool runOnMachineFunction(MachineFunction &MF) override;
  162. };
  163. } // End anonymous namespace.
  164. char ShrinkWrap::ID = 0;
  165. char &llvm::ShrinkWrapID = ShrinkWrap::ID;
  166. INITIALIZE_PASS_BEGIN(ShrinkWrap, "shrink-wrap", "Shrink Wrap Pass", false,
  167. false)
  168. INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
  169. INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  170. INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
  171. INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  172. INITIALIZE_PASS_END(ShrinkWrap, "shrink-wrap", "Shrink Wrap Pass", false, false)
  173. bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI) const {
  174. if (MI.getOpcode() == FrameSetupOpcode ||
  175. MI.getOpcode() == FrameDestroyOpcode) {
  176. DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
  177. return true;
  178. }
  179. for (const MachineOperand &MO : MI.operands()) {
  180. bool UseCSR = false;
  181. if (MO.isReg()) {
  182. unsigned PhysReg = MO.getReg();
  183. if (!PhysReg)
  184. continue;
  185. assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
  186. "Unallocated register?!");
  187. UseCSR = RCI.getLastCalleeSavedAlias(PhysReg);
  188. }
  189. // TODO: Handle regmask more accurately.
  190. // For now, be conservative about them.
  191. if (UseCSR || MO.isFI() || MO.isRegMask()) {
  192. DEBUG(dbgs() << "Use or define CSR(" << UseCSR << ") or FI(" << MO.isFI()
  193. << "): " << MI << '\n');
  194. return true;
  195. }
  196. }
  197. return false;
  198. }
  199. /// \brief Helper function to find the immediate (post) dominator.
  200. template <typename ListOfBBs, typename DominanceAnalysis>
  201. MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
  202. DominanceAnalysis &Dom) {
  203. MachineBasicBlock *IDom = &Block;
  204. for (MachineBasicBlock *BB : BBs) {
  205. IDom = Dom.findNearestCommonDominator(IDom, BB);
  206. if (!IDom)
  207. break;
  208. }
  209. return IDom;
  210. }
  211. void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB) {
  212. // Get rid of the easy cases first.
  213. if (!Save)
  214. Save = &MBB;
  215. else
  216. Save = MDT->findNearestCommonDominator(Save, &MBB);
  217. if (!Save) {
  218. DEBUG(dbgs() << "Found a block that is not reachable from Entry\n");
  219. return;
  220. }
  221. if (!Restore)
  222. Restore = &MBB;
  223. else
  224. Restore = MPDT->findNearestCommonDominator(Restore, &MBB);
  225. // Make sure we would be able to insert the restore code before the
  226. // terminator.
  227. if (Restore == &MBB) {
  228. for (const MachineInstr &Terminator : MBB.terminators()) {
  229. if (!useOrDefCSROrFI(Terminator))
  230. continue;
  231. // One of the terminator needs to happen before the restore point.
  232. if (MBB.succ_empty()) {
  233. Restore = nullptr;
  234. break;
  235. }
  236. // Look for a restore point that post-dominates all the successors.
  237. // The immediate post-dominator is what we are looking for.
  238. Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
  239. break;
  240. }
  241. }
  242. if (!Restore) {
  243. DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n");
  244. return;
  245. }
  246. // Make sure Save and Restore are suitable for shrink-wrapping:
  247. // 1. all path from Save needs to lead to Restore before exiting.
  248. // 2. all path to Restore needs to go through Save from Entry.
  249. // We achieve that by making sure that:
  250. // A. Save dominates Restore.
  251. // B. Restore post-dominates Save.
  252. // C. Save and Restore are in the same loop.
  253. bool SaveDominatesRestore = false;
  254. bool RestorePostDominatesSave = false;
  255. while (Save && Restore &&
  256. (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) ||
  257. !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) ||
  258. MLI->getLoopFor(Save) != MLI->getLoopFor(Restore))) {
  259. // Fix (A).
  260. if (!SaveDominatesRestore) {
  261. Save = MDT->findNearestCommonDominator(Save, Restore);
  262. continue;
  263. }
  264. // Fix (B).
  265. if (!RestorePostDominatesSave)
  266. Restore = MPDT->findNearestCommonDominator(Restore, Save);
  267. // Fix (C).
  268. if (Save && Restore && Save != Restore &&
  269. MLI->getLoopFor(Save) != MLI->getLoopFor(Restore)) {
  270. if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore))
  271. // Push Save outside of this loop.
  272. Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
  273. else
  274. // Push Restore outside of this loop.
  275. Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
  276. }
  277. }
  278. }
  279. bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
  280. if (MF.empty())
  281. return false;
  282. DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
  283. init(MF);
  284. for (MachineBasicBlock &MBB : MF) {
  285. DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName()
  286. << '\n');
  287. for (const MachineInstr &MI : MBB) {
  288. if (!useOrDefCSROrFI(MI))
  289. continue;
  290. // Save (resp. restore) point must dominate (resp. post dominate)
  291. // MI. Look for the proper basic block for those.
  292. updateSaveRestorePoints(MBB);
  293. // If we are at a point where we cannot improve the placement of
  294. // save/restore instructions, just give up.
  295. if (!ArePointsInteresting()) {
  296. DEBUG(dbgs() << "No Shrink wrap candidate found\n");
  297. return false;
  298. }
  299. // No need to look for other instructions, this basic block
  300. // will already be part of the handled region.
  301. break;
  302. }
  303. }
  304. if (!ArePointsInteresting()) {
  305. // If the points are not interesting at this point, then they must be null
  306. // because it means we did not encounter any frame/CSR related code.
  307. // Otherwise, we would have returned from the previous loop.
  308. assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
  309. DEBUG(dbgs() << "Nothing to shrink-wrap\n");
  310. return false;
  311. }
  312. DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
  313. << '\n');
  314. const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
  315. do {
  316. DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
  317. << Save->getNumber() << ' ' << Save->getName() << ' '
  318. << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: "
  319. << Restore->getNumber() << ' ' << Restore->getName() << ' '
  320. << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
  321. bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
  322. if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) &&
  323. EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) &&
  324. ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) &&
  325. TFI->canUseAsEpilogue(*Restore)))
  326. break;
  327. DEBUG(dbgs() << "New points are too expensive or invalid for the target\n");
  328. MachineBasicBlock *NewBB;
  329. if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
  330. Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
  331. if (!Save)
  332. break;
  333. NewBB = Save;
  334. } else {
  335. // Restore is expensive.
  336. Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
  337. if (!Restore)
  338. break;
  339. NewBB = Restore;
  340. }
  341. updateSaveRestorePoints(*NewBB);
  342. } while (Save && Restore);
  343. if (!ArePointsInteresting()) {
  344. ++NumCandidatesDropped;
  345. return false;
  346. }
  347. DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber()
  348. << ' ' << Save->getName() << "\nRestore: "
  349. << Restore->getNumber() << ' ' << Restore->getName() << '\n');
  350. MachineFrameInfo *MFI = MF.getFrameInfo();
  351. MFI->setSavePoint(Save);
  352. MFI->setRestorePoint(Restore);
  353. ++NumCandidates;
  354. return false;
  355. }