CodePlacementOpt.cpp revision 90c579de5a383cee278acc3f7e7b9d0a656e6a35
1bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng//===-- CodePlacementOpt.cpp - Code Placement pass. -----------------------===// 2fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// 3fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// The LLVM Compiler Infrastructure 4fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// 5fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// This file is distributed under the University of Illinois Open Source 6fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// License. See LICENSE.TXT for details. 7fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// 8fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng//===----------------------------------------------------------------------===// 9fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// 10bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng// This file implements the pass that optimize code placement and align loop 11bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng// headers to target specific alignment boundary. 12fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng// 13fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng//===----------------------------------------------------------------------===// 14fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 15bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng#define DEBUG_TYPE "code-placement" 16fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 17fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng#include "llvm/CodeGen/MachineFunctionPass.h" 18fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng#include "llvm/CodeGen/Passes.h" 1945e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng#include "llvm/Target/TargetInstrInfo.h" 20fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng#include "llvm/Target/TargetLowering.h" 21fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng#include "llvm/Target/TargetMachine.h" 22fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng#include "llvm/Support/Compiler.h" 23fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng#include "llvm/Support/Debug.h" 2445e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng#include "llvm/ADT/Statistic.h" 25fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Chengusing namespace llvm; 26fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 27cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan GohmanSTATISTIC(NumLoopsAligned, "Number of loops aligned"); 2845e0010e14d419ebeca9266b9b705867fd251b83Evan ChengSTATISTIC(NumIntraElim, "Number of intra loop branches eliminated"); 2945e0010e14d419ebeca9266b9b705867fd251b83Evan ChengSTATISTIC(NumIntraMoved, "Number of intra loop branches moved"); 3045e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 31fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Chengnamespace { 32bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng class CodePlacementOpt : public MachineFunctionPass { 337132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng const MachineLoopInfo *MLI; 3445e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng const TargetInstrInfo *TII; 3545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng const TargetLowering *TLI; 3645e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 37fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng public: 38fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng static char ID; 3990c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson CodePlacementOpt() : MachineFunctionPass(ID) {} 40fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 41fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 42bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng virtual const char *getPassName() const { 43bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng return "Code Placement Optimizater"; 44bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng } 45fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 46fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng virtual void getAnalysisUsage(AnalysisUsage &AU) const { 47fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng AU.addRequired<MachineLoopInfo>(); 488b56a90bec639665fc024896d2fc2bdd095c76a3Evan Cheng AU.addPreservedID(MachineDominatorsID); 49fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng MachineFunctionPass::getAnalysisUsage(AU); 50fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng } 517132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 527132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng private: 5307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool HasFallthrough(MachineBasicBlock *MBB); 5407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool HasAnalyzableTerminator(MachineBasicBlock *MBB); 5507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman void Splice(MachineFunction &MF, 5607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator InsertPt, 5707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin, 5807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator End); 5907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool EliminateUnconditionalJumpsToTop(MachineFunction &MF, 6007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L); 6107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool MoveDiscontiguousLoopBlocks(MachineFunction &MF, 6207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L); 6307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L); 6407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool OptimizeIntraLoopEdges(MachineFunction &MF); 657132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng bool AlignLoops(MachineFunction &MF); 66cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align); 67fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng }; 68fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 69bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng char CodePlacementOpt::ID = 0; 70fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng} // end anonymous namespace 71fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 72bbf1db72133e9cf986e4da6260736335533067dbEvan ChengFunctionPass *llvm::createCodePlacementOptPass() { 73bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng return new CodePlacementOpt(); 74bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng} 75fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 7607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// HasFallthrough - Test whether the given branch has a fallthrough, either as 7707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// a plain fallthrough or as a fallthrough case of a conditional branch. 7845e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 7907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) { 8007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 8107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman SmallVector<MachineOperand, 4> Cond; 8207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) 8307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 8407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // This conditional branch has no fallthrough. 8507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (FBB) 8607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 8707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // An unconditional branch has no fallthrough. 8807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Cond.empty() && TBB) 8907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 9007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // It has a fallthrough. 9107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return true; 9207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 9307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 9407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB. 9507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// This is called before major changes are begun to test whether it will be 9607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// possible to complete the changes. 9745e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 9807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// Target-specific code is hereby encouraged to make AnalyzeBranch succeed 9907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// whenever possible. 10045e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 10107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) { 10207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Conservatively ignore EH landing pads. 10307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (MBB->isLandingPad()) return false; 10407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 10507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Aggressively handle return blocks and similar constructs. 10607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (MBB->succ_empty()) return true; 10707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 10807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Ask the target's AnalyzeBranch if it can handle this block. 10907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 11007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman SmallVector<MachineOperand, 4> Cond; 111f3b11aa6a72e0c31066a60c2e888e7a5eb5f2399Dan Gohman // Make sure the terminator is understood. 11207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) 11307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 11449d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // Ignore blocks which look like they might have EH-related control flow. 11549d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // AnalyzeBranch thinks it knows how to analyze such things, but it doesn't 11649d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // recognize the possibility of a control transfer through an unwind. 11749d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // Such blocks contain EH_LABEL instructions, however they may be in the 11849d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // middle of the block. Instead of searching for them, just check to see 11949d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // if the CFG disagrees with AnalyzeBranch. 12049d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman if (1u + !Cond.empty() != MBB->succ_size()) 12149d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman return false; 12207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Make sure we have the option of reversing the condition. 12307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!Cond.empty() && TII->ReverseBranchCondition(Cond)) 12407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 12507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return true; 12607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 12707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 12807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// Splice - Move the sequence of instructions [Begin,End) to just before 12907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// InsertPt. Update branch instructions as needed to account for broken 13007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// fallthrough edges and to take advantage of newly exposed fallthrough 13107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// opportunities. 13245e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 13307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanvoid CodePlacementOpt::Splice(MachineFunction &MF, 13407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator InsertPt, 13507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin, 13607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator End) { 13707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() && 13807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman "Splice can't change the entry block!"); 13907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator OldBeginPrior = prior(Begin); 14007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator OldEndPrior = prior(End); 14107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 14207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MF.splice(InsertPt, Begin, End); 14307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 1447707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach prior(Begin)->updateTerminator(); 1457707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach OldBeginPrior->updateTerminator(); 1467707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach OldEndPrior->updateTerminator(); 14707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 1486ebf7bc7405ee79d27d50b70f0c1a474cbea820dEvan Cheng 14907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump 15007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// to the loop top to the top of the loop so that they have a fall through. 15107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// This can introduce a branch on entry to the loop, but it can eliminate a 15207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// branch within the loop. See the @simple case in 15307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// test/CodeGen/X86/loop_blocks.ll for an example of this. 15407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF, 15507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L) { 15645e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng bool Changed = false; 15707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TopMBB = L->getTopBlock(); 15807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 15907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool BotHasFallthrough = HasFallthrough(L->getBottomBlock()); 16007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 16107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TopMBB == MF.begin() || 16207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) { 16307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman new_top: 16407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(), 16507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman PE = TopMBB->pred_end(); PI != PE; ++PI) { 16607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *Pred = *PI; 16707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Pred == TopMBB) continue; 16807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (HasFallthrough(Pred)) continue; 16907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!L->contains(Pred)) continue; 17007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 17107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Verify that we can analyze all the loop entry edges before beginning 17207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // any changes which will require us to be able to analyze them. 17307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Pred == MF.begin()) 1743bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman continue; 17507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(Pred)) 17607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 17707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred)))) 1783bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman continue; 1793bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman 18007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the block. 181ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << Pred->getNumber() 182ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman << " to top of loop.\n"); 1833bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman Changed = true; 184766fc1db1640499c6affce80e7337d8c22dc8cb1Anton Korobeynikov 18507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move it and all the blocks that can reach it via fallthrough edges 18607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // exclusively, to keep existing fallthrough edges intact. 18707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin = Pred; 1887896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator End = llvm::next(Begin); 18907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman while (Begin != MF.begin()) { 19007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Prior = prior(Begin); 19107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Prior == MF.begin()) 19207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 19307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Stop when a non-fallthrough edge is found. 19407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasFallthrough(Prior)) 19507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 19607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Stop if a block which could fall-through out of the loop is found. 19707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Prior->isSuccessor(End)) 19807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 19907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If we've reached the top, stop scanning. 20007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Prior == MachineFunction::iterator(TopMBB)) { 20107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // We know top currently has a fall through (because we just checked 20207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // it) which would be lost if we do the transformation, so it isn't 20307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // worthwhile to do the transformation unless it would expose a new 20407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // fallthrough edge. 20507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!Prior->isSuccessor(End)) 20607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman goto next_pred; 20707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Otherwise we can stop scanning and procede to move the blocks. 20845e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng break; 20945e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 21007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If we hit a switch or something complicated, don't move anything 21107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // for this predecessor. 21207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior)))) 21307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 21407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Ok, the block prior to Begin will be moved along with the rest. 21507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Extend the range to include it. 21607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Begin = Prior; 21707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ++NumIntraMoved; 21845e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 21907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 22007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the blocks. 22107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Splice(MF, TopMBB, Begin, End); 22207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 22307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Update TopMBB. 22407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman TopMBB = L->getTopBlock(); 22507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 22607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // We have a new loop top. Iterate on it. We shouldn't have to do this 22707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // too many times if BranchFolding has done a reasonable job. 22807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman goto new_top; 22907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman next_pred:; 23045e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 23107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman } 23207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 23307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If the loop previously didn't exit with a fall-through and it now does, 23407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // we eliminated a branch. 23507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Changed && 23607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman !BotHasFallthrough && 23707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman HasFallthrough(L->getBottomBlock())) { 23807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ++NumIntraElim; 23907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman } 24007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 24107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 24207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 24307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 24407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the 24507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// portion of the loop contiguous with the header. This usually makes the loop 24607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// contiguous, provided that AnalyzeBranch can handle all the relevant 24707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll 24807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// for an example of this. 24907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF, 25007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L) { 25107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = false; 25207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TopMBB = L->getTopBlock(); 25307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *BotMBB = L->getBottomBlock(); 25407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 25507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Determine a position to move orphaned loop blocks to. If TopMBB is not 25607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // entered via fallthrough and BotMBB is exited via fallthrough, prepend them 25707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // to the top of the loop to avoid loosing that fallthrough. Otherwise append 25807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // them to the bottom, even if it previously had a fallthrough, on the theory 25907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // that it's worth an extra branch to keep the loop contiguous. 2607896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator InsertPt = 2617896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner llvm::next(MachineFunction::iterator(BotMBB)); 26207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool InsertAtTop = false; 26307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TopMBB != MF.begin() && 26407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) && 26507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman HasFallthrough(BotMBB)) { 26607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman InsertPt = TopMBB; 26707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman InsertAtTop = true; 26807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman } 26907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 27007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Keep a record of which blocks are in the portion of the loop contiguous 27107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // with the loop header. 27207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks; 27307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineFunction::iterator I = TopMBB, 2747896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I) 27507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ContiguousBlocks.insert(I); 27607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 27707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Find non-contigous blocks and fix them. 27807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt))) 27907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end(); 28007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman BI != BE; ++BI) { 28107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *BB = *BI; 28207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 28307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Verify that we can analyze all the loop entry edges before beginning 28407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // any changes which will require us to be able to analyze them. 28507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(BB)) 28607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 28707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB)))) 28807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 28907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 29007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If the layout predecessor is part of the loop, this block will be 29107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // processed along with it. This keeps them in their relative order. 29207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (BB != MF.begin() && 29307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman L->contains(prior(MachineFunction::iterator(BB)))) 29407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 29545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 29607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Check to see if this block is already contiguous with the main 29707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // portion of the loop. 29807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!ContiguousBlocks.insert(BB)) 29907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 30007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 30107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the block. 302ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << BB->getNumber() 303ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman << " to be contiguous with loop.\n"); 30407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed = true; 30507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 30607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Process this block and all loop blocks contiguous with it, to keep 30707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // them in their relative order. 30807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin = BB; 3097896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB)); 31007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (; End != MF.end(); ++End) { 31107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!L->contains(End)) break; 31207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(End)) break; 31307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ContiguousBlocks.insert(End); 31407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ++NumIntraMoved; 31545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 31645e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 31707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If we're inserting at the bottom of the loop, and the code we're 31807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // moving originally had fall-through successors, bring the sucessors 31907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // up with the loop blocks to preserve the fall-through edges. 32007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!InsertAtTop) 32107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (; End != MF.end(); ++End) { 32207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (L->contains(End)) break; 32307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(End)) break; 32407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasFallthrough(prior(End))) break; 32545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 32607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 32707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the blocks. This may invalidate TopMBB and/or BotMBB, but 32807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // we don't need them anymore at this point. 32907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Splice(MF, InsertPt, Begin, End); 330766fc1db1640499c6affce80e7337d8c22dc8cb1Anton Korobeynikov } 33145e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 33207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 33307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 33407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 33507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize 33607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// intra-loop branching and to form contiguous loops. 33707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 33807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// This code takes the approach of making minor changes to the existing 33907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// layout to fix specific loop-oriented problems. Also, it depends on 34007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// AnalyzeBranch, which can't understand complex control instructions. 34107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 34207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, 34307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L) { 34407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = false; 34507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 34607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Do optimization for nested loops. 34707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 34807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I); 34907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 35007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Do optimization for this loop. 35107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= EliminateUnconditionalJumpsToTop(MF, L); 35207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= MoveDiscontiguousLoopBlocks(MF, L); 35307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 35407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 35507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 35607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 35707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// OptimizeIntraLoopEdges - Reposition loop blocks to minimize 35807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// intra-loop branching and to form contiguous loops. 35907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 36007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) { 36107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = false; 36207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 36307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!TLI->shouldOptimizeCodePlacement()) 36407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 36507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 36607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Do optimization for each loop in the function. 36707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 36807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman I != E; ++I) 36907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!(*I)->getParentLoop()) 37007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I); 37107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 37245e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng return Changed; 37345e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng} 37445e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 3757132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng/// AlignLoops - Align loop headers to target preferred alignments. 3767132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng/// 3777132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Chengbool CodePlacementOpt::AlignLoops(MachineFunction &MF) { 37845e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng const Function *F = MF.getFunction(); 37945e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng if (F->hasFnAttr(Attribute::OptimizeForSize)) 3804f658e9e4b2c7c25779c304a90f460615d35e555Evan Cheng return false; 3814f658e9e4b2c7c25779c304a90f460615d35e555Evan Cheng 3824f658e9e4b2c7c25779c304a90f460615d35e555Evan Cheng unsigned Align = TLI->getPrefLoopAlignment(); 383fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng if (!Align) 384fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng return false; // Don't care about loop alignment. 385fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 386cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman bool Changed = false; 387cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 388cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 389cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman I != E; ++I) 390cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman Changed |= AlignLoop(MF, *I, Align); 3914ae641f4d12c60ee1aaca5e42b6de231c6a02c40Devang Patel 392cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman return Changed; 393cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman} 394cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 39507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// AlignLoop - Align loop headers to target preferred alignments. 39607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 397cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohmanbool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L, 398cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman unsigned Align) { 3997132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng bool Changed = false; 400cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 401cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman // Do alignment for nested loops. 402cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 403cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman Changed |= AlignLoop(MF, *I, Align); 404cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 40507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman L->getTopBlock()->setAlignment(Align); 406cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman Changed = true; 407cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman ++NumLoopsAligned; 408cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 4097132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng return Changed; 4107132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng} 4117132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 4127132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Chengbool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) { 4137132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng MLI = &getAnalysis<MachineLoopInfo>(); 4147132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng if (MLI->empty()) 4157132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng return false; // No loops. 4167132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 41745e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng TLI = MF.getTarget().getTargetLowering(); 41845e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng TII = MF.getTarget().getInstrInfo(); 41945e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 42007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = OptimizeIntraLoopEdges(MF); 42145e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 4227132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng Changed |= AlignLoops(MF); 4237132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 4247132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng return Changed; 425fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng} 426