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// 10f7af396c9571e4efe944c5bf739bce667f99556aCameron Zwarich// This file implements the pass that optimizes code placement and aligns loop 11f7af396c9571e4efe944c5bf739bce667f99556aCameron Zwarich// headers to target-specific alignment boundaries. 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); 42fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 43fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng virtual void getAnalysisUsage(AnalysisUsage &AU) const { 44fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng AU.addRequired<MachineLoopInfo>(); 458b56a90bec639665fc024896d2fc2bdd095c76a3Evan Cheng AU.addPreservedID(MachineDominatorsID); 46fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng MachineFunctionPass::getAnalysisUsage(AU); 47fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng } 487132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 497132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng private: 5007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool HasFallthrough(MachineBasicBlock *MBB); 5107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool HasAnalyzableTerminator(MachineBasicBlock *MBB); 5207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman void Splice(MachineFunction &MF, 5307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator InsertPt, 5407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin, 5507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator End); 5607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool EliminateUnconditionalJumpsToTop(MachineFunction &MF, 5707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L); 5807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool MoveDiscontiguousLoopBlocks(MachineFunction &MF, 5907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L); 6007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L); 6107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool OptimizeIntraLoopEdges(MachineFunction &MF); 627132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng bool AlignLoops(MachineFunction &MF); 63cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align); 64fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng }; 65fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 66bbf1db72133e9cf986e4da6260736335533067dbEvan Cheng char CodePlacementOpt::ID = 0; 67fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng} // end anonymous namespace 68fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 691dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::CodePlacementOptID = CodePlacementOpt::ID; 701dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew TrickINITIALIZE_PASS(CodePlacementOpt, "code-placement", 711dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trick "Code Placement Optimizer", false, false) 72fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 7307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// HasFallthrough - Test whether the given branch has a fallthrough, either as 7407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// a plain fallthrough or as a fallthrough case of a conditional branch. 7545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 7607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) { 7707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 7807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman SmallVector<MachineOperand, 4> Cond; 7907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) 8007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 8107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // This conditional branch has no fallthrough. 8207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (FBB) 8307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 8407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // An unconditional branch has no fallthrough. 8507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Cond.empty() && TBB) 8607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 8707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // It has a fallthrough. 8807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return true; 8907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 9007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 9107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB. 9207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// This is called before major changes are begun to test whether it will be 9307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// possible to complete the changes. 9445e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 9507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// Target-specific code is hereby encouraged to make AnalyzeBranch succeed 9607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// whenever possible. 9745e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 9807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) { 9907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Conservatively ignore EH landing pads. 10007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (MBB->isLandingPad()) return false; 10107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 10207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Aggressively handle return blocks and similar constructs. 10307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (MBB->succ_empty()) return true; 10407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 10507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Ask the target's AnalyzeBranch if it can handle this block. 10607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 10707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman SmallVector<MachineOperand, 4> Cond; 108f3b11aa6a72e0c31066a60c2e888e7a5eb5f2399Dan Gohman // Make sure the terminator is understood. 10907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) 11007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 11149d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // Ignore blocks which look like they might have EH-related control flow. 11249d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // AnalyzeBranch thinks it knows how to analyze such things, but it doesn't 11349d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // recognize the possibility of a control transfer through an unwind. 11449d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // Such blocks contain EH_LABEL instructions, however they may be in the 11549d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // middle of the block. Instead of searching for them, just check to see 11649d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman // if the CFG disagrees with AnalyzeBranch. 11749d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman if (1u + !Cond.empty() != MBB->succ_size()) 11849d7f8d341a7b4137c674ce0f08f5b18e8195f4aDan Gohman return false; 11907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Make sure we have the option of reversing the condition. 12007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!Cond.empty() && TII->ReverseBranchCondition(Cond)) 12107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return false; 12207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return true; 12307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 12407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 12507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// Splice - Move the sequence of instructions [Begin,End) to just before 12607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// InsertPt. Update branch instructions as needed to account for broken 12707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// fallthrough edges and to take advantage of newly exposed fallthrough 12807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// opportunities. 12945e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng/// 13007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanvoid CodePlacementOpt::Splice(MachineFunction &MF, 13107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator InsertPt, 13207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin, 13307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator End) { 13407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() && 13507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman "Splice can't change the entry block!"); 13607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator OldBeginPrior = prior(Begin); 13707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator OldEndPrior = prior(End); 13807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 13907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MF.splice(InsertPt, Begin, End); 14007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 1417707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach prior(Begin)->updateTerminator(); 1427707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach OldBeginPrior->updateTerminator(); 1437707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach OldEndPrior->updateTerminator(); 14407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 1456ebf7bc7405ee79d27d50b70f0c1a474cbea820dEvan Cheng 14607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump 14707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// to the loop top to the top of the loop so that they have a fall through. 14807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// This can introduce a branch on entry to the loop, but it can eliminate a 14907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// branch within the loop. See the @simple case in 15007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// test/CodeGen/X86/loop_blocks.ll for an example of this. 15107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF, 15207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L) { 15345e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng bool Changed = false; 15407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TopMBB = L->getTopBlock(); 15507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 15607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool BotHasFallthrough = HasFallthrough(L->getBottomBlock()); 15707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 15807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TopMBB == MF.begin() || 15907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) { 16007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman new_top: 16107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(), 16207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman PE = TopMBB->pred_end(); PI != PE; ++PI) { 16307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *Pred = *PI; 16407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Pred == TopMBB) continue; 16507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (HasFallthrough(Pred)) continue; 16607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!L->contains(Pred)) continue; 16707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 16807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Verify that we can analyze all the loop entry edges before beginning 16907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // any changes which will require us to be able to analyze them. 17007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Pred == MF.begin()) 1713bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman continue; 17207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(Pred)) 17307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 17407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred)))) 1753bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman continue; 1763bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman 17707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the block. 178ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << Pred->getNumber() 179ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman << " to top of loop.\n"); 1803bdd8de2806e47f34369c1e6ce6e6b44a135bd29Dan Gohman Changed = true; 181766fc1db1640499c6affce80e7337d8c22dc8cb1Anton Korobeynikov 18207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move it and all the blocks that can reach it via fallthrough edges 18307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // exclusively, to keep existing fallthrough edges intact. 18407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin = Pred; 1857896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator End = llvm::next(Begin); 18607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman while (Begin != MF.begin()) { 18707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Prior = prior(Begin); 18807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Prior == MF.begin()) 18907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 19007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Stop when a non-fallthrough edge is found. 19107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasFallthrough(Prior)) 19207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 19307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Stop if a block which could fall-through out of the loop is found. 19407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Prior->isSuccessor(End)) 19507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 19607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If we've reached the top, stop scanning. 19707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Prior == MachineFunction::iterator(TopMBB)) { 19807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // We know top currently has a fall through (because we just checked 19907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // it) which would be lost if we do the transformation, so it isn't 20007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // worthwhile to do the transformation unless it would expose a new 20107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // fallthrough edge. 20207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!Prior->isSuccessor(End)) 20307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman goto next_pred; 204d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // Otherwise we can stop scanning and proceed to move the blocks. 20545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng break; 20645e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 20707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If we hit a switch or something complicated, don't move anything 20807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // for this predecessor. 20907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior)))) 21007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman break; 21107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Ok, the block prior to Begin will be moved along with the rest. 21207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Extend the range to include it. 21307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Begin = Prior; 21407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ++NumIntraMoved; 21545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 21607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 21707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the blocks. 21807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Splice(MF, TopMBB, Begin, End); 21907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 22007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Update TopMBB. 22107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman TopMBB = L->getTopBlock(); 22207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 22307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // We have a new loop top. Iterate on it. We shouldn't have to do this 22407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // too many times if BranchFolding has done a reasonable job. 22507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman goto new_top; 22607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman next_pred:; 22745e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 22807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman } 22907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 23007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If the loop previously didn't exit with a fall-through and it now does, 23107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // we eliminated a branch. 23207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (Changed && 23307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman !BotHasFallthrough && 23407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman HasFallthrough(L->getBottomBlock())) { 23507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ++NumIntraElim; 23607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman } 23707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 23807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 23907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 24007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 24107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the 24207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// portion of the loop contiguous with the header. This usually makes the loop 24307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// contiguous, provided that AnalyzeBranch can handle all the relevant 24407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll 24507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// for an example of this. 24607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF, 24707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L) { 24807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = false; 24907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *TopMBB = L->getTopBlock(); 25007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *BotMBB = L->getBottomBlock(); 25107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 25207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Determine a position to move orphaned loop blocks to. If TopMBB is not 25307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // entered via fallthrough and BotMBB is exited via fallthrough, prepend them 2547a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // to the top of the loop to avoid losing that fallthrough. Otherwise append 25507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // them to the bottom, even if it previously had a fallthrough, on the theory 25607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // that it's worth an extra branch to keep the loop contiguous. 2577896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator InsertPt = 2587896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner llvm::next(MachineFunction::iterator(BotMBB)); 25907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool InsertAtTop = false; 26007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (TopMBB != MF.begin() && 26107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) && 26207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman HasFallthrough(BotMBB)) { 26307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman InsertPt = TopMBB; 26407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman InsertAtTop = true; 26507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman } 26607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 26707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Keep a record of which blocks are in the portion of the loop contiguous 26807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // with the loop header. 26907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks; 27007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineFunction::iterator I = TopMBB, 2717896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I) 27207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ContiguousBlocks.insert(I); 27307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 27407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Find non-contigous blocks and fix them. 27507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt))) 27607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end(); 27707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman BI != BE; ++BI) { 27807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineBasicBlock *BB = *BI; 27907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 28007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Verify that we can analyze all the loop entry edges before beginning 28107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // any changes which will require us to be able to analyze them. 28207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(BB)) 28307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 28407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB)))) 28507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 28607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 28707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If the layout predecessor is part of the loop, this block will be 28807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // processed along with it. This keeps them in their relative order. 28907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (BB != MF.begin() && 29007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman L->contains(prior(MachineFunction::iterator(BB)))) 29107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 29245e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 29307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Check to see if this block is already contiguous with the main 29407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // portion of the loop. 29507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!ContiguousBlocks.insert(BB)) 29607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman continue; 29707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 29807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the block. 299ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << BB->getNumber() 300ba1fe142450f46b44deccb21c8b422bc02b32d8bDan Gohman << " to be contiguous with loop.\n"); 30107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed = true; 30207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 30307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Process this block and all loop blocks contiguous with it, to keep 30407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // them in their relative order. 30507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineFunction::iterator Begin = BB; 3067896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB)); 30707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (; End != MF.end(); ++End) { 30807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!L->contains(End)) break; 30907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(End)) break; 31007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ContiguousBlocks.insert(End); 31107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman ++NumIntraMoved; 31245e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 31345e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 31407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // If we're inserting at the bottom of the loop, and the code we're 31507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // moving originally had fall-through successors, bring the sucessors 31607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // up with the loop blocks to preserve the fall-through edges. 31707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!InsertAtTop) 31807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (; End != MF.end(); ++End) { 31907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (L->contains(End)) break; 32007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasAnalyzableTerminator(End)) break; 32107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!HasFallthrough(prior(End))) break; 32245e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng } 32307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 32407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Move the blocks. This may invalidate TopMBB and/or BotMBB, but 32507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // we don't need them anymore at this point. 32607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Splice(MF, InsertPt, Begin, End); 327766fc1db1640499c6affce80e7337d8c22dc8cb1Anton Korobeynikov } 32845e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 32907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 33007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 33107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 33207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize 33307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// intra-loop branching and to form contiguous loops. 33407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 33507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// This code takes the approach of making minor changes to the existing 33607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// layout to fix specific loop-oriented problems. Also, it depends on 33707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// AnalyzeBranch, which can't understand complex control instructions. 33807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 33907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, 34007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman MachineLoop *L) { 34107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = false; 34207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 34307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Do optimization for nested loops. 34407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 34507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I); 34607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 34707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Do optimization for this loop. 34807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= EliminateUnconditionalJumpsToTop(MF, L); 34907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= MoveDiscontiguousLoopBlocks(MF, L); 35007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 35107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 35207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman} 35307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 35407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// OptimizeIntraLoopEdges - Reposition loop blocks to minimize 35507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// intra-loop branching and to form contiguous loops. 35607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 35707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohmanbool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) { 35807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = false; 35907adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 36007adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!TLI->shouldOptimizeCodePlacement()) 36107adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman return Changed; 36207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 36307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman // Do optimization for each loop in the function. 36407adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 36507adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman I != E; ++I) 36607adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman if (!(*I)->getParentLoop()) 36707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I); 36807adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman 36945e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng return Changed; 37045e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng} 37145e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 3727132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng/// AlignLoops - Align loop headers to target preferred alignments. 3737132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng/// 3747132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Chengbool CodePlacementOpt::AlignLoops(MachineFunction &MF) { 37545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng const Function *F = MF.getFunction(); 37645e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng if (F->hasFnAttr(Attribute::OptimizeForSize)) 3774f658e9e4b2c7c25779c304a90f460615d35e555Evan Cheng return false; 3784f658e9e4b2c7c25779c304a90f460615d35e555Evan Cheng 3794f658e9e4b2c7c25779c304a90f460615d35e555Evan Cheng unsigned Align = TLI->getPrefLoopAlignment(); 380fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng if (!Align) 381fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng return false; // Don't care about loop alignment. 382fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 383cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman bool Changed = false; 384cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 385cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 386cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman I != E; ++I) 387cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman Changed |= AlignLoop(MF, *I, Align); 3884ae641f4d12c60ee1aaca5e42b6de231c6a02c40Devang Patel 389cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman return Changed; 390cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman} 391cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 39207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// AlignLoop - Align loop headers to target preferred alignments. 39307adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman/// 394cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohmanbool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L, 395cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman unsigned Align) { 3967132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng bool Changed = false; 397cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 398cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman // Do alignment for nested loops. 399cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 400cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman Changed |= AlignLoop(MF, *I, Align); 401cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 40207adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman L->getTopBlock()->setAlignment(Align); 403cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman Changed = true; 404cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman ++NumLoopsAligned; 405cd2ae14ce3f16f0cef162aa85707f32295c4ee3dDan Gohman 4067132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng return Changed; 4077132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng} 4087132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 4097132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Chengbool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) { 4107132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng MLI = &getAnalysis<MachineLoopInfo>(); 4117132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng if (MLI->empty()) 4127132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng return false; // No loops. 4137132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 41445e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng TLI = MF.getTarget().getTargetLowering(); 41545e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng TII = MF.getTarget().getInstrInfo(); 41645e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 41707adb85cb7f97968b3b9a102e5fa504a5f6ac682Dan Gohman bool Changed = OptimizeIntraLoopEdges(MF); 41845e0010e14d419ebeca9266b9b705867fd251b83Evan Cheng 4197132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng Changed |= AlignLoops(MF); 4207132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng 4217132e12ee5658aa2b8ba6cdd81adb7944ddcb33eEvan Cheng return Changed; 422fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng} 423