10f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling//===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===// 20f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 30f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// The LLVM Compiler Infrastructure 40f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 70f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 80f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling//===----------------------------------------------------------------------===// 90f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 100f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// This pass performs loop invariant code motion on machine instructions. We 110f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// attempt to remove as much code from the body of a loop as possible. 120f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 13c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// This pass does not attempt to throttle itself to limit register pressure. 14c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// The register allocation phases are expected to perform rematerialization 15c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// to recover when register pressure is high. 16c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// 17c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// This pass is not intended to be a replacement or a complete alternative 18c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// for the LLVM-IR-level LICM pass. It is only designed to hoist simple 19c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// constructs that are not exposed before lowering and instruction selection. 20c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// 210f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling//===----------------------------------------------------------------------===// 220f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 230f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling#define DEBUG_TYPE "machine-licm" 24ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/CodeGen/Passes.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 26d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 290f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling#include "llvm/CodeGen/MachineDominators.h" 30d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng#include "llvm/CodeGen/MachineFrameInfo.h" 310f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling#include "llvm/CodeGen/MachineLoopInfo.h" 32589f1f5a4321eeee2856baa5c8ab1139d6e0351eDan Gohman#include "llvm/CodeGen/MachineMemOperand.h" 339258cd3994e54aaec66f69a321032e071391dc90Bill Wendling#include "llvm/CodeGen/MachineRegisterInfo.h" 34589f1f5a4321eeee2856baa5c8ab1139d6e0351eDan Gohman#include "llvm/CodeGen/PseudoSourceValue.h" 35ab8be96fd30ca9396e6b84fdddf1ac6208984cadEvan Cheng#include "llvm/MC/MCInstrItineraries.h" 367007e4c5564f32fe4f06765a9740218039e7b492Evan Cheng#include "llvm/Support/CommandLine.h" 37ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/Support/Debug.h" 38ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 40d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLowering.h" 41d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 42d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 430f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingusing namespace llvm; 440f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 457007e4c5564f32fe4f06765a9740218039e7b492Evan Chengstatic cl::opt<bool> 467007e4c5564f32fe4f06765a9740218039e7b492Evan ChengAvoidSpeculation("avoid-speculation", 477007e4c5564f32fe4f06765a9740218039e7b492Evan Cheng cl::desc("MachineLICM should avoid speculation"), 4873b5bb38650a1a1441fcf210c79f188d08990946Evan Cheng cl::init(true), cl::Hidden); 497007e4c5564f32fe4f06765a9740218039e7b492Evan Cheng 5003a9fdf2e755c1cebdb8371d79b591d46daa9463Evan ChengSTATISTIC(NumHoisted, 5103a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng "Number of machine instructions hoisted out of loops"); 5203a9fdf2e755c1cebdb8371d79b591d46daa9463Evan ChengSTATISTIC(NumLowRP, 5303a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng "Number of instructions hoisted in low reg pressure situation"); 5403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan ChengSTATISTIC(NumHighLatency, 5503a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng "Number of high latency instructions hoisted"); 5603a9fdf2e755c1cebdb8371d79b591d46daa9463Evan ChengSTATISTIC(NumCSEed, 5703a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng "Number of hoisted machine instructions CSEed"); 58d94671a25e65918557a2c03c0fc12a60a5d138bfEvan ChengSTATISTIC(NumPostRAHoisted, 59d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng "Number of machine instructions hoisted out of loops post regalloc"); 60b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 610f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingnamespace { 626726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class MachineLICM : public MachineFunctionPass { 639258cd3994e54aaec66f69a321032e071391dc90Bill Wendling const TargetMachine *TM; 64efe2be797699d77dc3387969aa566c26d5c36d9dBill Wendling const TargetInstrInfo *TII; 6569e42dbd006c0afb732067ece7327988b1e24c01Benjamin Kramer const TargetLoweringBase *TLI; 66a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman const TargetRegisterInfo *TRI; 67d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng const MachineFrameInfo *MFI; 680e673919f0f02f39e2210c365f732299a21db49eEvan Cheng MachineRegisterInfo *MRI; 690e673919f0f02f39e2210c365f732299a21db49eEvan Cheng const InstrItineraryData *InstrItins; 709d41bd5c78b99750d820e01bcd4a4e479b713d4cAndrew Trick bool PreRegAlloc; 7112ebf14048f4a6489033f8468ba36424442140acBill Wendling 720f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // Various analyses that we use... 73e33f44cfc547359bc28526e4c5e1852b600b4448Dan Gohman AliasAnalysis *AA; // Alias analysis info. 744038f9c21b17378617c25f3092fe615326f8b874Evan Cheng MachineLoopInfo *MLI; // Current MachineLoopInfo 75e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineDominatorTree *DT; // Machine dominator tree for the cur loop 760f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 770f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // State that is updated as we process loops 78e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling bool Changed; // True if a loop is changed. 7982e0a1a1a81ad54452823a8eb1e8d743cf38f098Evan Cheng bool FirstInLoop; // True if it's the first LICM in the loop. 80e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineLoop *CurLoop; // The current loop we are working on. 81c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 82af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 838b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // Exit blocks for CurLoop. 848b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 8> ExitBlocks; 858b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen 868b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen bool isExitBlock(const MachineBasicBlock *MBB) const { 878b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen return std::find(ExitBlocks.begin(), ExitBlocks.end(), MBB) != 888b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen ExitBlocks.end(); 898b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen } 908b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen 910e673919f0f02f39e2210c365f732299a21db49eEvan Cheng // Track 'estimated' register pressure. 9203a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng SmallSet<unsigned, 32> RegSeen; 930e673919f0f02f39e2210c365f732299a21db49eEvan Cheng SmallVector<unsigned, 8> RegPressure; 9403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 9503a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng // Register pressure "limit" per register class. If the pressure 9603a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng // is higher than the limit, then it's considered high. 970e673919f0f02f39e2210c365f732299a21db49eEvan Cheng SmallVector<unsigned, 8> RegLimit; 980e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 9903a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng // Register pressure on path leading from loop preheader to current BB. 10003a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng SmallVector<SmallVector<unsigned, 8>, 16> BackTrace; 10103a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 102c46a5f20c5ab9c497a91d3227d6368e92069caceDale Johannesen // For each opcode, keep a list of potential CSE instructions. 103777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap; 104d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 105fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng enum { 106fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng SpeculateFalse = 0, 107fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng SpeculateTrue = 1, 108fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng SpeculateUnknown = 2 109fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng }; 110fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng 1112e350479478ccf809e2142a4f0ad8062342577ccDevang Patel // If a MBB does not dominate loop exiting blocks then it may not safe 1122e350479478ccf809e2142a4f0ad8062342577ccDevang Patel // to hoist loads from this block. 113fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng // Tri-state: 0 - false, 1 - true, 2 - unknown 114fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng unsigned SpeculationState; 1152e350479478ccf809e2142a4f0ad8062342577ccDevang Patel 1160f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling public: 1170f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling static char ID; // Pass identification, replacement for typeid 118d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng MachineLICM() : 119081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MachineFunctionPass(ID), PreRegAlloc(true) { 120081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineLICMPass(*PassRegistry::getPassRegistry()); 121081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 122d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 123d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng explicit MachineLICM(bool PreRA) : 124081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MachineFunctionPass(ID), PreRegAlloc(PreRA) { 125081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineLICMPass(*PassRegistry::getPassRegistry()); 126081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 1270f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1280f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling virtual bool runOnMachineFunction(MachineFunction &MF); 1290f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1300f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1310f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.addRequired<MachineLoopInfo>(); 1320f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.addRequired<MachineDominatorTree>(); 133e33f44cfc547359bc28526e4c5e1852b600b4448Dan Gohman AU.addRequired<AliasAnalysis>(); 134d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling AU.addPreserved<MachineLoopInfo>(); 135d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling AU.addPreserved<MachineDominatorTree>(); 136d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling MachineFunctionPass::getAnalysisUsage(AU); 1370f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 138af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 139af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng virtual void releaseMemory() { 14003a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng RegSeen.clear(); 1410e673919f0f02f39e2210c365f732299a21db49eEvan Cheng RegPressure.clear(); 1420e673919f0f02f39e2210c365f732299a21db49eEvan Cheng RegLimit.clear(); 1432312842de0c641107dd04d7e056d02491cc781caEvan Cheng BackTrace.clear(); 14403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng for (DenseMap<unsigned,std::vector<const MachineInstr*> >::iterator 14503a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng CI = CSEMap.begin(), CE = CSEMap.end(); CI != CE; ++CI) 14603a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng CI->second.clear(); 147af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng CSEMap.clear(); 148af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 149af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 1500f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling private: 1514038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// CandidateInfo - Keep track of information about hoisting candidates. 1524038f9c21b17378617c25f3092fe615326f8b874Evan Cheng struct CandidateInfo { 1534038f9c21b17378617c25f3092fe615326f8b874Evan Cheng MachineInstr *MI; 1544038f9c21b17378617c25f3092fe615326f8b874Evan Cheng unsigned Def; 1555dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng int FI; 1565dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng CandidateInfo(MachineInstr *mi, unsigned def, int fi) 1575dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng : MI(mi), Def(def), FI(fi) {} 1584038f9c21b17378617c25f3092fe615326f8b874Evan Cheng }; 1594038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 1604038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop 1614038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// invariants out to the preheader. 16294d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng void HoistRegionPostRA(); 1634038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 1644038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// HoistPostRA - When an instruction is found to only use loop invariant 1654038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// operands that is safe to hoist, this instruction is called to do the 1664038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// dirty work. 1674038f9c21b17378617c25f3092fe615326f8b874Evan Cheng void HoistPostRA(MachineInstr *MI, unsigned Def); 1684038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 1694038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// ProcessMI - Examine the instruction for potentai LICM candidate. Also 1704038f9c21b17378617c25f3092fe615326f8b874Evan Cheng /// gather register def and frame object update information. 171a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen void ProcessMI(MachineInstr *MI, 172a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen BitVector &PhysRegDefs, 173a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen BitVector &PhysRegClobbers, 1744038f9c21b17378617c25f3092fe615326f8b874Evan Cheng SmallSet<int, 32> &StoredFIs, 1754038f9c21b17378617c25f3092fe615326f8b874Evan Cheng SmallVector<CandidateInfo, 32> &Candidates); 1764038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 17794d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng /// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the 17894d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng /// current loop. 17994d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng void AddToLiveIns(unsigned Reg); 1804038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 1815dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng /// IsLICMCandidate - Returns true if the instruction may be a suitable 1827791080151a5a8bbda073551289469301d006fcbChris Lattner /// candidate for LICM. e.g. If the instruction is a call, then it's 1837791080151a5a8bbda073551289469301d006fcbChris Lattner /// obviously not safe to hoist it. 1845dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng bool IsLICMCandidate(MachineInstr &I); 1855dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng 186041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling /// IsLoopInvariantInst - Returns true if the instruction is loop 1870f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// invariant. I.e., all virtual register operands are defined outside of 1880f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// the loop, physical registers aren't accessed (explicitly or implicitly), 1890f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// and the instruction is hoistable. 1909f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick /// 191041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling bool IsLoopInvariantInst(MachineInstr &I); 1920f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1938b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen /// HasLoopPHIUse - Return true if the specified instruction is used by any 1948b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen /// phi node in the current loop. 1958b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen bool HasLoopPHIUse(const MachineInstr *MI) const; 196d67705faaa526a31feab831ac1e5e15ee37880a1Evan Cheng 1972312842de0c641107dd04d7e056d02491cc781caEvan Cheng /// HasHighOperandLatency - Compute operand latency between a def of 'Reg' 1982312842de0c641107dd04d7e056d02491cc781caEvan Cheng /// and an use in the current loop, return true if the target considered 1992312842de0c641107dd04d7e056d02491cc781caEvan Cheng /// it 'high'. 200c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, 201c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng unsigned Reg) const; 202c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng 203c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng bool IsCheapInstruction(MachineInstr &MI) const; 2040e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 205134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// CanCauseHighRegPressure - Visit BBs from header to current BB, 206134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// check if hoisting an instruction of the given cost matrix can cause high 20703a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng /// register pressure. 20871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen bool CanCauseHighRegPressure(DenseMap<unsigned, int> &Cost, bool Cheap); 209134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 210134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// UpdateBackTraceRegPressure - Traverse the back trace from header to 211134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// the current block and update their register pressures to reflect the 212134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// effect of hoisting MI from the current block to the preheader. 213134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng void UpdateBackTraceRegPressure(const MachineInstr *MI); 21403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 21545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng /// IsProfitableToHoist - Return true if it is potentially profitable to 21645e94d68d7c99235cf4decc72812445b214df40eEvan Cheng /// hoist the given loop invariant. 217c26abd94877eb1e2e00de8f9f927606e37e479d8Evan Cheng bool IsProfitableToHoist(MachineInstr &MI); 21845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 2192e350479478ccf809e2142a4f0ad8062342577ccDevang Patel /// IsGuaranteedToExecute - Check if this mbb is guaranteed to execute. 2202e350479478ccf809e2142a4f0ad8062342577ccDevang Patel /// If not then a load from this mbb may not be safe to hoist. 2212e350479478ccf809e2142a4f0ad8062342577ccDevang Patel bool IsGuaranteedToExecute(MachineBasicBlock *BB); 2222e350479478ccf809e2142a4f0ad8062342577ccDevang Patel 223acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper void EnterScope(MachineBasicBlock *MBB); 224acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 225acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper void ExitScope(MachineBasicBlock *MBB); 226acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 227acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to given 228acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// dominator tree node if its a leaf or all of its children are done. Walk 229acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// up the dominator tree to destroy ancestors which are now done. 230acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper void ExitScopeIfDone(MachineDomTreeNode *Node, 231acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 232acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap); 233acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 234acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// HoistOutOfLoop - Walk the specified loop in the CFG (defined by all 235acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// blocks dominated by the specified header block, and that are in the 236acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// current loop) in depth first order w.r.t the DominatorTree. This allows 237acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// us to visit definitions before uses, allowing us to hoist a loop body in 238acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper /// one pass without iteration. 2390f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 240acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper void HoistOutOfLoop(MachineDomTreeNode *LoopHeaderNode); 241acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper void HoistRegion(MachineDomTreeNode *N, bool IsHeader); 2420f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 24361560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng /// getRegisterClassIDAndCost - For a given MI, register, and the operand 24461560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng /// index, return the ID and cost of its representative register class by 24561560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng /// reference. 24661560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng void getRegisterClassIDAndCost(const MachineInstr *MI, 24761560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned Reg, unsigned OpIdx, 24861560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned &RCId, unsigned &RCCost) const; 24961560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng 25003a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng /// InitRegPressure - Find all virtual register references that are liveout 25103a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng /// of the preheader to initialize the starting "register pressure". Note 25203a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng /// this does not count live through (livein but not used) registers. 2530e673919f0f02f39e2210c365f732299a21db49eEvan Cheng void InitRegPressure(MachineBasicBlock *BB); 2540e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 255134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// UpdateRegPressure - Update estimate of register pressure after the 256134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// specified instruction. 257134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng void UpdateRegPressure(const MachineInstr *MI); 2580e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 2595c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman /// ExtractHoistableLoad - Unfold a load from the given machineinstr if 2605c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman /// the load itself could be hoisted. Return the unfolded and hoistable 2615c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman /// load, or null if the load couldn't be unfolded or if it wouldn't 2625c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman /// be hoistable. 2635c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman MachineInstr *ExtractHoistableLoad(MachineInstr *MI); 2645c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman 26578e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng /// LookForDuplicate - Find an instruction amount PrevMIs that is a 26678e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng /// duplicate of MI. Return this instruction if it's found. 26778e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng const MachineInstr *LookForDuplicate(const MachineInstr *MI, 26878e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng std::vector<const MachineInstr*> &PrevMIs); 26978e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng 2709fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng /// EliminateCSE - Given a LICM'ed instruction, look for an instruction on 2719fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng /// the preheader that compute the same value. If it's found, do a RAU on 2729fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng /// with the definition of the existing instruction rather than hoisting 2739fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng /// the instruction to the preheader. 2749fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng bool EliminateCSE(MachineInstr *MI, 2759fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI); 2769fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng 2777efba85d414949febe51100e298077233526787cEvan Cheng /// MayCSE - Return true if the given instruction will be CSE'd if it's 2787efba85d414949febe51100e298077233526787cEvan Cheng /// hoisted out of the loop. 2797efba85d414949febe51100e298077233526787cEvan Cheng bool MayCSE(MachineInstr *MI); 2807efba85d414949febe51100e298077233526787cEvan Cheng 2810f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// Hoist - When an instruction is found to only use loop invariant operands 2820f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// that is safe to hoist, this instruction is called to do the dirty work. 283134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng /// It returns true if the instruction is hoisted. 284134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader); 285777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng 286777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng /// InitCSEMap - Initialize the CSE map with instructions that are in the 287777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng /// current loop preheader that may become duplicates of instructions that 288777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng /// are hoisted out of the loop. 289777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng void InitCSEMap(MachineBasicBlock *BB); 290853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 291853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// getCurPreheader - Get the preheader for the current loop, splitting 292853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// a critical edge if needed. 293853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *getCurPreheader(); 2940f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling }; 2950f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} // end anonymous namespace 2960f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 297844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar MachineLICM::ID = 0; 2981dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineLICMID = MachineLICM::ID; 2992ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MachineLICM, "machinelicm", 3002ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Machine Loop Invariant Code Motion", false, false) 3012ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 3022ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 3032ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 3042ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MachineLICM, "machinelicm", 305ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Machine Loop Invariant Code Motion", false, false) 306844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 307853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman/// LoopIsOuterMostWithPredecessor - Test if the given loop is the outer-most 308853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman/// loop that has a unique predecessor. 309853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohmanstatic bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) { 310aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman // Check whether this loop even has a unique predecessor. 311aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman if (!CurLoop->getLoopPredecessor()) 312aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman return false; 313aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman // Ok, now check to see if any of its outer loops do. 314c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 315853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (L->getLoopPredecessor()) 316c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return false; 317aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman // None of them did, so this is the outermost with a unique predecessor. 318c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return true; 319c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman} 320c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 3210f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingbool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 32282e0a1a1a81ad54452823a8eb1e8d743cf38f098Evan Cheng Changed = FirstInLoop = false; 323acb04ec4273516242fe87cb0a57a43136805deddBill Wendling TM = &MF.getTarget(); 3249258cd3994e54aaec66f69a321032e071391dc90Bill Wendling TII = TM->getInstrInfo(); 3250e673919f0f02f39e2210c365f732299a21db49eEvan Cheng TLI = TM->getTargetLowering(); 326a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman TRI = TM->getRegisterInfo(); 327d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng MFI = MF.getFrameInfo(); 3280e673919f0f02f39e2210c365f732299a21db49eEvan Cheng MRI = &MF.getRegInfo(); 3290e673919f0f02f39e2210c365f732299a21db49eEvan Cheng InstrItins = TM->getInstrItineraryData(); 3300f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 3319d41bd5c78b99750d820e01bcd4a4e479b713d4cAndrew Trick PreRegAlloc = MRI->isSSA(); 3329d41bd5c78b99750d820e01bcd4a4e479b713d4cAndrew Trick 333fd3d4cf0ef5237bd517559703bea2310f1841a5dJakob Stoklund Olesen if (PreRegAlloc) 334fd3d4cf0ef5237bd517559703bea2310f1841a5dJakob Stoklund Olesen DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: "); 335fd3d4cf0ef5237bd517559703bea2310f1841a5dJakob Stoklund Olesen else 336fd3d4cf0ef5237bd517559703bea2310f1841a5dJakob Stoklund Olesen DEBUG(dbgs() << "******** Post-regalloc Machine LICM: "); 33796601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << MF.getName() << " ********\n"); 338fd3d4cf0ef5237bd517559703bea2310f1841a5dJakob Stoklund Olesen 3390e673919f0f02f39e2210c365f732299a21db49eEvan Cheng if (PreRegAlloc) { 3400e673919f0f02f39e2210c365f732299a21db49eEvan Cheng // Estimate register pressure during pre-regalloc pass. 3410e673919f0f02f39e2210c365f732299a21db49eEvan Cheng unsigned NumRC = TRI->getNumRegClasses(); 3420e673919f0f02f39e2210c365f732299a21db49eEvan Cheng RegPressure.resize(NumRC); 3430e673919f0f02f39e2210c365f732299a21db49eEvan Cheng std::fill(RegPressure.begin(), RegPressure.end(), 0); 34403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng RegLimit.resize(NumRC); 3450e673919f0f02f39e2210c365f732299a21db49eEvan Cheng for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 3460e673919f0f02f39e2210c365f732299a21db49eEvan Cheng E = TRI->regclass_end(); I != E; ++I) 347be2119e8e2bc7006cfd638a24367acbfda625d16Cameron Zwarich RegLimit[(*I)->getID()] = TRI->getRegPressureLimit(*I, MF); 3480e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 3490e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 3500f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // Get our Loop information... 3514038f9c21b17378617c25f3092fe615326f8b874Evan Cheng MLI = &getAnalysis<MachineLoopInfo>(); 3524038f9c21b17378617c25f3092fe615326f8b874Evan Cheng DT = &getAnalysis<MachineDominatorTree>(); 3534038f9c21b17378617c25f3092fe615326f8b874Evan Cheng AA = &getAnalysis<AliasAnalysis>(); 3540f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 355aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end()); 356aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman while (!Worklist.empty()) { 357aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman CurLoop = Worklist.pop_back_val(); 358853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman CurPreheader = 0; 3598b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen ExitBlocks.clear(); 3600f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 3614038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // If this is done before regalloc, only visit outer-most preheader-sporting 3624038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // loops. 363aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) { 364aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman Worklist.append(CurLoop->begin(), CurLoop->end()); 365c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 366aa7426070da3b74d60186763bb7c53af3e095427Dan Gohman } 367c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 3688b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen CurLoop->getExitBlocks(ExitBlocks); 3698b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen 370d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng if (!PreRegAlloc) 37194d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng HoistRegionPostRA(); 372d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng else { 37394d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng // CSEMap is initialized for loop header when the first instruction is 37494d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng // being hoisted. 37594d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader()); 37682e0a1a1a81ad54452823a8eb1e8d743cf38f098Evan Cheng FirstInLoop = true; 377acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper HoistOutOfLoop(N); 378d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng CSEMap.clear(); 379d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng } 3800f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 3810f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 3820f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return Changed; 3830f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 3840f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 3854038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// InstructionStoresToFI - Return true if instruction stores to the 3864038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// specified frame. 3874038f9c21b17378617c25f3092fe615326f8b874Evan Chengstatic bool InstructionStoresToFI(const MachineInstr *MI, int FI) { 3884038f9c21b17378617c25f3092fe615326f8b874Evan Cheng for (MachineInstr::mmo_iterator o = MI->memoperands_begin(), 3894038f9c21b17378617c25f3092fe615326f8b874Evan Cheng oe = MI->memoperands_end(); o != oe; ++o) { 3904038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (!(*o)->isStore() || !(*o)->getValue()) 3914038f9c21b17378617c25f3092fe615326f8b874Evan Cheng continue; 3924038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (const FixedStackPseudoSourceValue *Value = 3934038f9c21b17378617c25f3092fe615326f8b874Evan Cheng dyn_cast<const FixedStackPseudoSourceValue>((*o)->getValue())) { 3944038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (Value->getFrameIndex() == FI) 3954038f9c21b17378617c25f3092fe615326f8b874Evan Cheng return true; 3964038f9c21b17378617c25f3092fe615326f8b874Evan Cheng } 3974038f9c21b17378617c25f3092fe615326f8b874Evan Cheng } 3984038f9c21b17378617c25f3092fe615326f8b874Evan Cheng return false; 3994038f9c21b17378617c25f3092fe615326f8b874Evan Cheng} 4004038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 4014038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// ProcessMI - Examine the instruction for potentai LICM candidate. Also 4024038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// gather register def and frame object update information. 4034038f9c21b17378617c25f3092fe615326f8b874Evan Chengvoid MachineLICM::ProcessMI(MachineInstr *MI, 404a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen BitVector &PhysRegDefs, 405a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen BitVector &PhysRegClobbers, 4064038f9c21b17378617c25f3092fe615326f8b874Evan Cheng SmallSet<int, 32> &StoredFIs, 4074038f9c21b17378617c25f3092fe615326f8b874Evan Cheng SmallVector<CandidateInfo, 32> &Candidates) { 4084038f9c21b17378617c25f3092fe615326f8b874Evan Cheng bool RuledOut = false; 409aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng bool HasNonInvariantUse = false; 4104038f9c21b17378617c25f3092fe615326f8b874Evan Cheng unsigned Def = 0; 4114038f9c21b17378617c25f3092fe615326f8b874Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 4124038f9c21b17378617c25f3092fe615326f8b874Evan Cheng const MachineOperand &MO = MI->getOperand(i); 4134038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (MO.isFI()) { 4144038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // Remember if the instruction stores to the frame index. 4154038f9c21b17378617c25f3092fe615326f8b874Evan Cheng int FI = MO.getIndex(); 4164038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (!StoredFIs.count(FI) && 4174038f9c21b17378617c25f3092fe615326f8b874Evan Cheng MFI->isSpillSlotObjectIndex(FI) && 4184038f9c21b17378617c25f3092fe615326f8b874Evan Cheng InstructionStoresToFI(MI, FI)) 4194038f9c21b17378617c25f3092fe615326f8b874Evan Cheng StoredFIs.insert(FI); 420aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng HasNonInvariantUse = true; 4214038f9c21b17378617c25f3092fe615326f8b874Evan Cheng continue; 4224038f9c21b17378617c25f3092fe615326f8b874Evan Cheng } 4234038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 424a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen // We can't hoist an instruction defining a physreg that is clobbered in 425a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen // the loop. 426a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen if (MO.isRegMask()) { 427478a8a02bc0f2e739ed8f4240152e99837e480b9Jakob Stoklund Olesen PhysRegClobbers.setBitsNotInMask(MO.getRegMask()); 428a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen continue; 429a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen } 430a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen 4314038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (!MO.isReg()) 4324038f9c21b17378617c25f3092fe615326f8b874Evan Cheng continue; 4334038f9c21b17378617c25f3092fe615326f8b874Evan Cheng unsigned Reg = MO.getReg(); 4344038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (!Reg) 4354038f9c21b17378617c25f3092fe615326f8b874Evan Cheng continue; 4364038f9c21b17378617c25f3092fe615326f8b874Evan Cheng assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 4374038f9c21b17378617c25f3092fe615326f8b874Evan Cheng "Not expecting virtual register!"); 4384038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 4395dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng if (!MO.isDef()) { 440a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen if (Reg && (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg))) 441aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng // If it's using a non-loop-invariant register, then it's obviously not 442aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng // safe to hoist. 443aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng HasNonInvariantUse = true; 4444038f9c21b17378617c25f3092fe615326f8b874Evan Cheng continue; 4455dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng } 4464038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 4474038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (MO.isImplicit()) { 448396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 449396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen PhysRegClobbers.set(*AI); 4504038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (!MO.isDead()) 4514038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // Non-dead implicit def? This cannot be hoisted. 4524038f9c21b17378617c25f3092fe615326f8b874Evan Cheng RuledOut = true; 4534038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // No need to check if a dead implicit def is also defined by 4544038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // another instruction. 4554038f9c21b17378617c25f3092fe615326f8b874Evan Cheng continue; 4564038f9c21b17378617c25f3092fe615326f8b874Evan Cheng } 4574038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 4584038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // FIXME: For now, avoid instructions with multiple defs, unless 4594038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // it's a dead implicit def. 4604038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (Def) 4614038f9c21b17378617c25f3092fe615326f8b874Evan Cheng RuledOut = true; 4624038f9c21b17378617c25f3092fe615326f8b874Evan Cheng else 4634038f9c21b17378617c25f3092fe615326f8b874Evan Cheng Def = Reg; 4644038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 4654038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // If we have already seen another instruction that defines the same 466a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen // register, then this is not safe. Two defs is indicated by setting a 467a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen // PhysRegClobbers bit. 468396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) { 469d0848a6398e0830898463ceb0041d4d7b163512dJakob Stoklund Olesen if (PhysRegDefs.test(*AS)) 470d0848a6398e0830898463ceb0041d4d7b163512dJakob Stoklund Olesen PhysRegClobbers.set(*AS); 471d0848a6398e0830898463ceb0041d4d7b163512dJakob Stoklund Olesen if (PhysRegClobbers.test(*AS)) 472a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen // MI defined register is seen defined by another instruction in 473a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen // the loop, it cannot be a LICM candidate. 4744038f9c21b17378617c25f3092fe615326f8b874Evan Cheng RuledOut = true; 475d0848a6398e0830898463ceb0041d4d7b163512dJakob Stoklund Olesen PhysRegDefs.set(*AS); 476a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen } 4774038f9c21b17378617c25f3092fe615326f8b874Evan Cheng } 4784038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 4795dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng // Only consider reloads for now and remats which do not have register 4805dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng // operands. FIXME: Consider unfold load folding instructions. 4814038f9c21b17378617c25f3092fe615326f8b874Evan Cheng if (Def && !RuledOut) { 4825dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng int FI = INT_MIN; 483aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) || 4845dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng (TII->isLoadFromStackSlot(MI, FI) && MFI->isSpillSlotObjectIndex(FI))) 4855dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng Candidates.push_back(CandidateInfo(MI, Def, FI)); 4864038f9c21b17378617c25f3092fe615326f8b874Evan Cheng } 4874038f9c21b17378617c25f3092fe615326f8b874Evan Cheng} 4884038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 4894038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop 4904038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// invariants out to the preheader. 49194d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Chengvoid MachineLICM::HoistRegionPostRA() { 492d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng MachineBasicBlock *Preheader = getCurPreheader(); 493d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng if (!Preheader) 494d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng return; 495d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng 496d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng unsigned NumRegs = TRI->getNumRegs(); 497a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop. 498a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen BitVector PhysRegClobbers(NumRegs); // Regs defined more than once. 499d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 5004038f9c21b17378617c25f3092fe615326f8b874Evan Cheng SmallVector<CandidateInfo, 32> Candidates; 501d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng SmallSet<int, 32> StoredFIs; 502d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 503d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // Walk the entire region, count number of defs for each register, and 50494d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng // collect potential LICM candidates. 50594d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks(); 50694d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 50794d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng MachineBasicBlock *BB = Blocks[i]; 508a2e87912d826b1843bb5b1058670f09b87aea905Bill Wendling 509a2e87912d826b1843bb5b1058670f09b87aea905Bill Wendling // If the header of the loop containing this basic block is a landing pad, 510a2e87912d826b1843bb5b1058670f09b87aea905Bill Wendling // then don't try to hoist instructions out of this loop. 511a2e87912d826b1843bb5b1058670f09b87aea905Bill Wendling const MachineLoop *ML = MLI->getLoopFor(BB); 512a2e87912d826b1843bb5b1058670f09b87aea905Bill Wendling if (ML && ML->getHeader()->isLandingPad()) continue; 513a2e87912d826b1843bb5b1058670f09b87aea905Bill Wendling 514d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // Conservatively treat live-in's as an external def. 5154038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // FIXME: That means a reload that're reused in successor block(s) will not 5164038f9c21b17378617c25f3092fe615326f8b874Evan Cheng // be LICM'ed. 51781bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator I = BB->livein_begin(), 518d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng E = BB->livein_end(); I != E; ++I) { 519d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng unsigned Reg = *I; 520396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 521396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen PhysRegDefs.set(*AI); 522d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng } 523d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 524fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng SpeculationState = SpeculateUnknown; 525d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng for (MachineBasicBlock::iterator 526d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 527d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng MachineInstr *MI = &*MII; 528a3c4ca9c7ba4bb98eb1c240726c8f4fb7e60f1c7Jakob Stoklund Olesen ProcessMI(MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates); 529d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng } 53094d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng } 531d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 532d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng // Gather the registers read / clobbered by the terminator. 533d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng BitVector TermRegs(NumRegs); 534d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng MachineBasicBlock::iterator TI = Preheader->getFirstTerminator(); 535d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng if (TI != Preheader->end()) { 536d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i) { 537d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng const MachineOperand &MO = TI->getOperand(i); 538d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng if (!MO.isReg()) 539d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng continue; 540d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng unsigned Reg = MO.getReg(); 541d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng if (!Reg) 542d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng continue; 543396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 544396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen TermRegs.set(*AI); 545d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng } 546d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng } 547d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng 548d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // Now evaluate whether the potential candidates qualify. 549d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // 1. Check if the candidate defined register is defined by another 550d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // instruction in the loop. 551d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // 2. If the candidate is a load from stack slot (always true for now), 552d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // check if the slot is stored anywhere in the loop. 553d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng // 3. Make sure candidate def should not clobber 554d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng // registers read by the terminator. Similarly its def should not be 555d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng // clobbered by the terminator. 556d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng for (unsigned i = 0, e = Candidates.size(); i != e; ++i) { 5575dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng if (Candidates[i].FI != INT_MIN && 5585dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng StoredFIs.count(Candidates[i].FI)) 559d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng continue; 560d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 561d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng unsigned Def = Candidates[i].Def; 562d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) { 563aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng bool Safe = true; 564aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng MachineInstr *MI = Candidates[i].MI; 565c15d9135a82525d1b1e52fe79c70e782c15e251eEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 566c15d9135a82525d1b1e52fe79c70e782c15e251eEvan Cheng const MachineOperand &MO = MI->getOperand(j); 5676327537a377d2b77748270258e99b257bf1723dfEvan Cheng if (!MO.isReg() || MO.isDef() || !MO.getReg()) 568aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng continue; 569d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng unsigned Reg = MO.getReg(); 570d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng if (PhysRegDefs.test(Reg) || 571d6c23557898b1fe9b21b28023f4133cab84a8b83Evan Cheng PhysRegClobbers.test(Reg)) { 572aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng // If it's using a non-loop-invariant register, then it's obviously 573aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng // not safe to hoist. 574aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng Safe = false; 575aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng break; 576aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng } 577aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng } 578aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng if (Safe) 579aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng HoistPostRA(MI, Candidates[i].Def); 580aeb2f4aa462949ce067125f2f56dc34df64b25dbEvan Cheng } 581d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng } 582d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng} 583d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 5849196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen/// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the current 5859196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen/// loop, and make sure it is not killed by any instructions in the loop. 58694d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Chengvoid MachineLICM::AddToLiveIns(unsigned Reg) { 58794d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks(); 5889196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 5899196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen MachineBasicBlock *BB = Blocks[i]; 5909196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen if (!BB->isLiveIn(Reg)) 5919196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen BB->addLiveIn(Reg); 5929196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen for (MachineBasicBlock::iterator 5939196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 5949196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen MachineInstr *MI = &*MII; 5959196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 5969196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 5979196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue; 5989196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg())) 5999196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen MO.setIsKill(false); 6009196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen } 6019196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen } 6029196ab640559ca473931b1ad74b90bbed516272fJakob Stoklund Olesen } 6034038f9c21b17378617c25f3092fe615326f8b874Evan Cheng} 6044038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 6054038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// HoistPostRA - When an instruction is found to only use loop invariant 6064038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// operands that is safe to hoist, this instruction is called to do the 6074038f9c21b17378617c25f3092fe615326f8b874Evan Cheng/// dirty work. 6084038f9c21b17378617c25f3092fe615326f8b874Evan Chengvoid MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { 609853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *Preheader = getCurPreheader(); 610853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 611d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // Now move the instructions to the predecessor, inserting it before any 612d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // terminator instructions. 61339f66601938e88a4e287986fab58a0d5053f8f8eJakob Stoklund Olesen DEBUG(dbgs() << "Hoisting to BB#" << Preheader->getNumber() << " from BB#" 61439f66601938e88a4e287986fab58a0d5053f8f8eJakob Stoklund Olesen << MI->getParent()->getNumber() << ": " << *MI); 615d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 616d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng // Splice the instruction to the preheader. 6174038f9c21b17378617c25f3092fe615326f8b874Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 618853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman Preheader->splice(Preheader->getFirstTerminator(), MBB, MI); 6194038f9c21b17378617c25f3092fe615326f8b874Evan Cheng 6209f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick // Add register to livein list to all the BBs in the current loop since a 62194d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng // loop invariant must be kept live throughout the whole loop. This is 62294d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng // important to ensure later passes do not scavenge the def register. 62394d1d9c2190b93feeb01934dbf1f2b828ceb82dcEvan Cheng AddToLiveIns(Def); 624d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 625d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng ++NumPostRAHoisted; 626d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng Changed = true; 627d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng} 628d94671a25e65918557a2c03c0fc12a60a5d138bfEvan Cheng 6292e350479478ccf809e2142a4f0ad8062342577ccDevang Patel// IsGuaranteedToExecute - Check if this mbb is guaranteed to execute. 6302e350479478ccf809e2142a4f0ad8062342577ccDevang Patel// If not then a load from this mbb may not be safe to hoist. 6312e350479478ccf809e2142a4f0ad8062342577ccDevang Patelbool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) { 632fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng if (SpeculationState != SpeculateUnknown) 633fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng return SpeculationState == SpeculateFalse; 6349f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick 6352e350479478ccf809e2142a4f0ad8062342577ccDevang Patel if (BB != CurLoop->getHeader()) { 6362e350479478ccf809e2142a4f0ad8062342577ccDevang Patel // Check loop exiting blocks. 6372e350479478ccf809e2142a4f0ad8062342577ccDevang Patel SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks; 6382e350479478ccf809e2142a4f0ad8062342577ccDevang Patel CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); 6392e350479478ccf809e2142a4f0ad8062342577ccDevang Patel for (unsigned i = 0, e = CurrentLoopExitingBlocks.size(); i != e; ++i) 6402e350479478ccf809e2142a4f0ad8062342577ccDevang Patel if (!DT->dominates(BB, CurrentLoopExitingBlocks[i])) { 641ea3abd553668e272772f04ae1536034cd37e70d1Nick Lewycky SpeculationState = SpeculateTrue; 642ea3abd553668e272772f04ae1536034cd37e70d1Nick Lewycky return false; 6432e350479478ccf809e2142a4f0ad8062342577ccDevang Patel } 6442e350479478ccf809e2142a4f0ad8062342577ccDevang Patel } 6452e350479478ccf809e2142a4f0ad8062342577ccDevang Patel 646fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng SpeculationState = SpeculateFalse; 647fad62874883ab78af47b4eeba042775a67ea7515Evan Cheng return true; 6482e350479478ccf809e2142a4f0ad8062342577ccDevang Patel} 6492e350479478ccf809e2142a4f0ad8062342577ccDevang Patel 650acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Coopervoid MachineLICM::EnterScope(MachineBasicBlock *MBB) { 651acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 6520f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 653acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Remember livein register pressure. 654acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper BackTrace.push_back(RegPressure); 655acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper} 656a2e87912d826b1843bb5b1058670f09b87aea905Bill Wendling 657acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Coopervoid MachineLICM::ExitScope(MachineBasicBlock *MBB) { 658acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 659acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper BackTrace.pop_back(); 660acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper} 6610f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 662acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 663acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// dominator tree node if its a leaf or all of its children are done. Walk 664acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// up the dominator tree to destroy ancestors which are now done. 665acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Coopervoid MachineLICM::ExitScopeIfDone(MachineDomTreeNode *Node, 66675fda5dcaebf3daafdbd06f44e89c7683b1be770Evan Cheng DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 66775fda5dcaebf3daafdbd06f44e89c7683b1be770Evan Cheng DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) { 668acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (OpenChildren[Node]) 66903a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng return; 6700e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 671acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Pop scope. 672acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper ExitScope(Node->getBlock()); 673acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 674acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Now traverse upwards to pop ancestors whose offsprings are all done. 675acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper while (MachineDomTreeNode *Parent = ParentMap[Node]) { 676acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper unsigned Left = --OpenChildren[Parent]; 677acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (Left != 0) 678acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper break; 679acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper ExitScope(Parent->getBlock()); 680acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper Node = Parent; 681acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper } 682acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper} 683acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 684acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// HoistOutOfLoop - Walk the specified loop in the CFG (defined by all 685acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// blocks dominated by the specified header block, and that are in the 686acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// current loop) in depth first order w.r.t the DominatorTree. This allows 687acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// us to visit definitions before uses, allowing us to hoist a loop body in 688acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// one pass without iteration. 689acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper/// 690acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Coopervoid MachineLICM::HoistOutOfLoop(MachineDomTreeNode *HeaderN) { 691acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper SmallVector<MachineDomTreeNode*, 32> Scopes; 692acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper SmallVector<MachineDomTreeNode*, 8> WorkList; 693acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap; 694acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 695acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 696acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Perform a DFS walk to determine the order of visit. 697acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper WorkList.push_back(HeaderN); 698acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper do { 699acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineDomTreeNode *Node = WorkList.pop_back_val(); 700acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper assert(Node != 0 && "Null dominator tree node?"); 701acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineBasicBlock *BB = Node->getBlock(); 702acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 703acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // If the header of the loop containing this basic block is a landing pad, 704acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // then don't try to hoist instructions out of this loop. 705acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper const MachineLoop *ML = MLI->getLoopFor(BB); 706acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (ML && ML->getHeader()->isLandingPad()) 707acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper continue; 708acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 709acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // If this subregion is not in the top level loop at all, exit. 710acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (!CurLoop->contains(BB)) 711acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper continue; 712acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 713acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper Scopes.push_back(Node); 714acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 715acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper unsigned NumChildren = Children.size(); 716acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 717acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Don't hoist things out of a large switch statement. This often causes 718acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // code to be hoisted that wasn't going to be executed, and increases 719acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // register pressure in a situation where it's likely to matter. 720acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (BB->succ_size() >= 25) 721acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper NumChildren = 0; 722acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 723acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper OpenChildren[Node] = NumChildren; 724acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Add children in reverse order as then the next popped worklist node is 725acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // the first child of this node. This means we ultimately traverse the 726acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // DOM tree in exactly the same order as if we'd recursed. 727acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper for (int i = (int)NumChildren-1; i >= 0; --i) { 728acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineDomTreeNode *Child = Children[i]; 729acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper ParentMap[Child] = Node; 730acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper WorkList.push_back(Child); 731acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper } 732acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper } while (!WorkList.empty()); 733acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 734acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (Scopes.size() != 0) { 735acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineBasicBlock *Preheader = getCurPreheader(); 736acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (!Preheader) 737acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper return; 738acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 739134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // Compute registers which are livein into the loop headers. 7402312842de0c641107dd04d7e056d02491cc781caEvan Cheng RegSeen.clear(); 7412312842de0c641107dd04d7e056d02491cc781caEvan Cheng BackTrace.clear(); 7422312842de0c641107dd04d7e056d02491cc781caEvan Cheng InitRegPressure(Preheader); 74398694138025fdb0cec0cda5727201ad00ded3d63Daniel Dunbar } 74411e8b74a7ae9ecd59b64180a59143e39bc3b9514Evan Cheng 745acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Now perform LICM. 746acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { 747acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineDomTreeNode *Node = Scopes[i]; 748acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineBasicBlock *MBB = Node->getBlock(); 7492312842de0c641107dd04d7e056d02491cc781caEvan Cheng 750acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineBasicBlock *Preheader = getCurPreheader(); 751acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (!Preheader) 752acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper continue; 7530f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 754acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper EnterScope(MBB); 75503a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 756acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // Process the block 757acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper SpeculationState = SpeculateUnknown; 758acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper for (MachineBasicBlock::iterator 759acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MII = MBB->begin(), E = MBB->end(); MII != E; ) { 760acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineBasicBlock::iterator NextMII = MII; ++NextMII; 761acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MachineInstr *MI = &*MII; 762acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper if (!Hoist(MI, Preheader)) 763acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper UpdateRegPressure(MI); 764acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper MII = NextMII; 765acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper } 766acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper 767acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 768acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper ExitScopeIfDone(Node, OpenChildren, ParentMap); 769acde91e2735cf2841a306a7c7af7af8c31f34a4aPete Cooper } 7700f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 7710f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 772134982daa9bcd87f79c357e3a2686804b9baddd9Evan Chengstatic bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { 773134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg()); 774134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng} 775134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 77661560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng/// getRegisterClassIDAndCost - For a given MI, register, and the operand 77761560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng/// index, return the ID and cost of its representative register class. 77861560e205a7997749f066dcceaadd5f4b9b5e1beEvan Chengvoid 77961560e205a7997749f066dcceaadd5f4b9b5e1beEvan ChengMachineLICM::getRegisterClassIDAndCost(const MachineInstr *MI, 78061560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned Reg, unsigned OpIdx, 78161560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned &RCId, unsigned &RCCost) const { 78261560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 783860e7cdab9d5eceda5ac52ae0ddfb4bdab0067f2Patrik Hagglund MVT VT = *RC->vt_begin(); 78499aa14ff64c92eab347d23696e358361d3bd90eaOwen Anderson if (VT == MVT::Untyped) { 78561560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng RCId = RC->getID(); 78661560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng RCCost = 1; 78761560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng } else { 78861560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng RCId = TLI->getRepRegClassFor(VT)->getID(); 78961560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng RCCost = TLI->getRepRegClassCostFor(VT); 79061560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng } 79161560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng} 7929f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick 79303a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng/// InitRegPressure - Find all virtual register references that are liveout of 79403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng/// the preheader to initialize the starting "register pressure". Note this 79503a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng/// does not count live through (livein but not used) registers. 7960e673919f0f02f39e2210c365f732299a21db49eEvan Chengvoid MachineLICM::InitRegPressure(MachineBasicBlock *BB) { 7970e673919f0f02f39e2210c365f732299a21db49eEvan Cheng std::fill(RegPressure.begin(), RegPressure.end(), 0); 79803a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 799134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // If the preheader has only a single predecessor and it ends with a 800134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // fallthrough or an unconditional branch, then scan its predecessor for live 801134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // defs as well. This happens whenever the preheader is created by splitting 802134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // the critical edge from the loop predecessor to the loop header. 803134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (BB->pred_size() == 1) { 804134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng MachineBasicBlock *TBB = 0, *FBB = 0; 805134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng SmallVector<MachineOperand, 4> Cond; 806134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty()) 807134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng InitRegPressure(*BB->pred_begin()); 808134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng } 809134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 8100e673919f0f02f39e2210c365f732299a21db49eEvan Cheng for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); 8110e673919f0f02f39e2210c365f732299a21db49eEvan Cheng MII != E; ++MII) { 8120e673919f0f02f39e2210c365f732299a21db49eEvan Cheng MachineInstr *MI = &*MII; 8130e673919f0f02f39e2210c365f732299a21db49eEvan Cheng for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 8140e673919f0f02f39e2210c365f732299a21db49eEvan Cheng const MachineOperand &MO = MI->getOperand(i); 8150e673919f0f02f39e2210c365f732299a21db49eEvan Cheng if (!MO.isReg() || MO.isImplicit()) 8160e673919f0f02f39e2210c365f732299a21db49eEvan Cheng continue; 8170e673919f0f02f39e2210c365f732299a21db49eEvan Cheng unsigned Reg = MO.getReg(); 818c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 8190e673919f0f02f39e2210c365f732299a21db49eEvan Cheng continue; 8200e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 821dc986d2462ca8df72af9e2f6afac0ba86b753e5bAndrew Trick bool isNew = RegSeen.insert(Reg); 82261560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned RCId, RCCost; 82361560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost); 82403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng if (MO.isDef()) 82561560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng RegPressure[RCId] += RCCost; 82603a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng else { 827134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng bool isKill = isOperandKill(MO, MRI); 828134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (isNew && !isKill) 82903a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng // Haven't seen this, it must be a livein. 83061560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng RegPressure[RCId] += RCCost; 831134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng else if (!isNew && isKill) 83261560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng RegPressure[RCId] -= RCCost; 83303a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng } 8340e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 8350e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 8360e673919f0f02f39e2210c365f732299a21db49eEvan Cheng} 8370e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 838134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng/// UpdateRegPressure - Update estimate of register pressure after the 839134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng/// specified instruction. 840134982daa9bcd87f79c357e3a2686804b9baddd9Evan Chengvoid MachineLICM::UpdateRegPressure(const MachineInstr *MI) { 841134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (MI->isImplicitDef()) 842134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng return; 8430e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 844134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng SmallVector<unsigned, 4> Defs; 8450e673919f0f02f39e2210c365f732299a21db49eEvan Cheng for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 8460e673919f0f02f39e2210c365f732299a21db49eEvan Cheng const MachineOperand &MO = MI->getOperand(i); 8472312842de0c641107dd04d7e056d02491cc781caEvan Cheng if (!MO.isReg() || MO.isImplicit()) 8480e673919f0f02f39e2210c365f732299a21db49eEvan Cheng continue; 8490e673919f0f02f39e2210c365f732299a21db49eEvan Cheng unsigned Reg = MO.getReg(); 850c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 8510e673919f0f02f39e2210c365f732299a21db49eEvan Cheng continue; 8520e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 853dc986d2462ca8df72af9e2f6afac0ba86b753e5bAndrew Trick bool isNew = RegSeen.insert(Reg); 8542312842de0c641107dd04d7e056d02491cc781caEvan Cheng if (MO.isDef()) 8552312842de0c641107dd04d7e056d02491cc781caEvan Cheng Defs.push_back(Reg); 856134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng else if (!isNew && isOperandKill(MO, MRI)) { 85761560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned RCId, RCCost; 85861560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost); 859134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (RCCost > RegPressure[RCId]) 860134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng RegPressure[RCId] = 0; 861134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng else 8622312842de0c641107dd04d7e056d02491cc781caEvan Cheng RegPressure[RCId] -= RCCost; 86303a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng } 8640e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 8650e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 86661560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned Idx = 0; 8672312842de0c641107dd04d7e056d02491cc781caEvan Cheng while (!Defs.empty()) { 8682312842de0c641107dd04d7e056d02491cc781caEvan Cheng unsigned Reg = Defs.pop_back_val(); 86961560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned RCId, RCCost; 87061560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng getRegisterClassIDAndCost(MI, Reg, Idx, RCId, RCCost); 8710e673919f0f02f39e2210c365f732299a21db49eEvan Cheng RegPressure[RCId] += RCCost; 87261560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng ++Idx; 8730e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 8740e673919f0f02f39e2210c365f732299a21db49eEvan Cheng} 8750e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 8769f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick/// isLoadFromGOTOrConstantPool - Return true if this machine instruction 87706e16bbec02d289552f942abe7a6353b51cdb5eaDevang Patel/// loads from global offset table or constant pool. 87806e16bbec02d289552f942abe7a6353b51cdb5eaDevang Patelstatic bool isLoadFromGOTOrConstantPool(MachineInstr &MI) { 8795a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng assert (MI.mayLoad() && "Expected MI that loads!"); 8806c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel for (MachineInstr::mmo_iterator I = MI.memoperands_begin(), 8819f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick E = MI.memoperands_end(); I != E; ++I) { 8826c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel if (const Value *V = (*I)->getValue()) { 8836c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) 88406e16bbec02d289552f942abe7a6353b51cdb5eaDevang Patel if (PSV == PSV->getGOT() || PSV == PSV->getConstantPool()) 8859f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick return true; 8866c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel } 8876c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel } 8886c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel return false; 8896c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel} 8906c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel 8915dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng/// IsLICMCandidate - Returns true if the instruction may be a suitable 8925dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng/// candidate for LICM. e.g. If the instruction is a call, then it's obviously 8935dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng/// not safe to hoist it. 8945dc57ce53329143c2b533882410be80ea5d259a7Evan Chengbool MachineLICM::IsLICMCandidate(MachineInstr &I) { 8957791080151a5a8bbda073551289469301d006fcbChris Lattner // Check if it's safe to move the instruction. 8967791080151a5a8bbda073551289469301d006fcbChris Lattner bool DontMoveAcrossStore = true; 8977791080151a5a8bbda073551289469301d006fcbChris Lattner if (!I.isSafeToMove(TII, AA, DontMoveAcrossStore)) 898a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner return false; 8992e350479478ccf809e2142a4f0ad8062342577ccDevang Patel 9002e350479478ccf809e2142a4f0ad8062342577ccDevang Patel // If it is load then check if it is guaranteed to execute by making sure that 9012e350479478ccf809e2142a4f0ad8062342577ccDevang Patel // it dominates all exiting blocks. If it doesn't, then there is a path out of 902e6de9f30cbdbeca7f6632420f2cd5728d9a2dc1cDevang Patel // the loop which does not execute this load, so we can't hoist it. Loads 903e6de9f30cbdbeca7f6632420f2cd5728d9a2dc1cDevang Patel // from constant memory are not safe to speculate all the time, for example 904e6de9f30cbdbeca7f6632420f2cd5728d9a2dc1cDevang Patel // indexed load from a jump table. 9052e350479478ccf809e2142a4f0ad8062342577ccDevang Patel // Stores and side effects are already checked by isSafeToMove. 9069f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick if (I.mayLoad() && !isLoadFromGOTOrConstantPool(I) && 9076c15fec3c5b4770570a4d681762a7bd510e65077Devang Patel !IsGuaranteedToExecute(I.getParent())) 9082e350479478ccf809e2142a4f0ad8062342577ccDevang Patel return false; 9092e350479478ccf809e2142a4f0ad8062342577ccDevang Patel 9105dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng return true; 9115dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng} 9125dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng 9135dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng/// IsLoopInvariantInst - Returns true if the instruction is loop 9145dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng/// invariant. I.e., all virtual register operands are defined outside of the 9155dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng/// loop, physical registers aren't accessed explicitly, and there are no side 9165dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng/// effects that aren't captured by the operands or other flags. 9179f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick/// 9185dc57ce53329143c2b533882410be80ea5d259a7Evan Chengbool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 9195dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng if (!IsLICMCandidate(I)) 9205dc57ce53329143c2b533882410be80ea5d259a7Evan Cheng return false; 921074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling 922e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // The instruction is loop invariant if all of its operands are. 9230f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 9240f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling const MachineOperand &MO = I.getOperand(i); 9250f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 926d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 927fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling continue; 928fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling 9290f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling unsigned Reg = MO.getReg(); 930074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling if (Reg == 0) continue; 9310f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 932c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Don't hoist an instruction that uses or defines a physical register. 933a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 934a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman if (MO.isUse()) { 935a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // If the physreg has no defs anywhere, it's just an ambient register 93645094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman // and we can freely move its uses. Alternatively, if it's allocatable, 93745094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman // it could get allocated to something with a def during allocation. 938c035c940a656f34a58ebe22fcc5f9b2a7d8e97fbJakob Stoklund Olesen if (!MRI->isConstantPhysReg(Reg, *I.getParent()->getParent())) 93945094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman return false; 940a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // Otherwise it's safe to move. 941a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman continue; 942a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman } else if (!MO.isDead()) { 943a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // A def that isn't dead. We can't move it. 944a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman return false; 945a363a9b71afcf326d376445f6f3cae0c36e6e9d9Dan Gohman } else if (CurLoop->getHeader()->isLiveIn(Reg)) { 946a363a9b71afcf326d376445f6f3cae0c36e6e9d9Dan Gohman // If the reg is live into the loop, we can't hoist an instruction 947a363a9b71afcf326d376445f6f3cae0c36e6e9d9Dan Gohman // which would clobber it. 948a363a9b71afcf326d376445f6f3cae0c36e6e9d9Dan Gohman return false; 949a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman } 950a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman } 9510f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 952c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!MO.isUse()) 953c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 954c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 9550e673919f0f02f39e2210c365f732299a21db49eEvan Cheng assert(MRI->getVRegDef(Reg) && 956e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling "Machine instr not mapped for this vreg?!"); 9570f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 9580f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If the loop contains the definition of an operand, then the instruction 9590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // isn't loop invariant. 9600e673919f0f02f39e2210c365f732299a21db49eEvan Cheng if (CurLoop->contains(MRI->getVRegDef(Reg))) 9610f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return false; 9620f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 9630f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 9640f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If we got this far, the instruction is loop invariant! 9650f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return true; 9660f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 9670f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 968af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 9698b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen/// HasLoopPHIUse - Return true if the specified instruction is used by a 9708b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen/// phi node and hoisting it could cause a copy to be inserted. 9718b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesenbool MachineLICM::HasLoopPHIUse(const MachineInstr *MI) const { 9728b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen SmallVector<const MachineInstr*, 8> Work(1, MI); 9738b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen do { 9748b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen MI = Work.pop_back_val(); 9758b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 9768b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen if (!MO->isReg() || !MO->isDef()) 9778b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen continue; 9788b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen unsigned Reg = MO->getReg(); 9798b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 9808b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen continue; 9818b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 9828b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen UE = MRI->use_end(); UI != UE; ++UI) { 9838b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen MachineInstr *UseMI = &*UI; 9848b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // A PHI may cause a copy to be inserted. 9858b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen if (UseMI->isPHI()) { 9868b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // A PHI inside the loop causes a copy because the live range of Reg is 9878b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // extended across the PHI. 9888b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen if (CurLoop->contains(UseMI)) 9898b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen return true; 9908b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // A PHI in an exit block can cause a copy to be inserted if the PHI 9918b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // has multiple predecessors in the loop with different values. 9928b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // For now, approximate by rejecting all exit blocks. 9938b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen if (isExitBlock(UseMI->getParent())) 9948b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen return true; 9958b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen continue; 9968b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen } 9978b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen // Look past copies as well. 9988b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen if (UseMI->isCopy() && CurLoop->contains(UseMI)) 9998b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen Work.push_back(UseMI); 10008b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen } 1001d67705faaa526a31feab831ac1e5e15ee37880a1Evan Cheng } 10028b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen } while (!Work.empty()); 1003af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return false; 100445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng} 100545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 10062312842de0c641107dd04d7e056d02491cc781caEvan Cheng/// HasHighOperandLatency - Compute operand latency between a def of 'Reg' 10072312842de0c641107dd04d7e056d02491cc781caEvan Cheng/// and an use in the current loop, return true if the target considered 10082312842de0c641107dd04d7e056d02491cc781caEvan Cheng/// it 'high'. 10092312842de0c641107dd04d7e056d02491cc781caEvan Chengbool MachineLICM::HasHighOperandLatency(MachineInstr &MI, 1010c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng unsigned DefIdx, unsigned Reg) const { 1011c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng if (!InstrItins || InstrItins->isEmpty() || MRI->use_nodbg_empty(Reg)) 10122312842de0c641107dd04d7e056d02491cc781caEvan Cheng return false; 10130e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 10140e673919f0f02f39e2210c365f732299a21db49eEvan Cheng for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 10150e673919f0f02f39e2210c365f732299a21db49eEvan Cheng E = MRI->use_nodbg_end(); I != E; ++I) { 10160e673919f0f02f39e2210c365f732299a21db49eEvan Cheng MachineInstr *UseMI = &*I; 1017c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng if (UseMI->isCopyLike()) 1018c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng continue; 10190e673919f0f02f39e2210c365f732299a21db49eEvan Cheng if (!CurLoop->contains(UseMI->getParent())) 10200e673919f0f02f39e2210c365f732299a21db49eEvan Cheng continue; 10210e673919f0f02f39e2210c365f732299a21db49eEvan Cheng for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { 10220e673919f0f02f39e2210c365f732299a21db49eEvan Cheng const MachineOperand &MO = UseMI->getOperand(i); 10230e673919f0f02f39e2210c365f732299a21db49eEvan Cheng if (!MO.isReg() || !MO.isUse()) 10240e673919f0f02f39e2210c365f732299a21db49eEvan Cheng continue; 10250e673919f0f02f39e2210c365f732299a21db49eEvan Cheng unsigned MOReg = MO.getReg(); 10260e673919f0f02f39e2210c365f732299a21db49eEvan Cheng if (MOReg != Reg) 10270e673919f0f02f39e2210c365f732299a21db49eEvan Cheng continue; 10280e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 10292312842de0c641107dd04d7e056d02491cc781caEvan Cheng if (TII->hasHighOperandLatency(InstrItins, MRI, &MI, DefIdx, UseMI, i)) 10302312842de0c641107dd04d7e056d02491cc781caEvan Cheng return true; 10310e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 10320e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 10332312842de0c641107dd04d7e056d02491cc781caEvan Cheng // Only look at the first in loop use. 10342312842de0c641107dd04d7e056d02491cc781caEvan Cheng break; 10350e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 10360e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 10372312842de0c641107dd04d7e056d02491cc781caEvan Cheng return false; 10380e673919f0f02f39e2210c365f732299a21db49eEvan Cheng} 10390e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 1040c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng/// IsCheapInstruction - Return true if the instruction is marked "cheap" or 1041c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng/// the operand latency between its def and a use is one or less. 1042c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Chengbool MachineLICM::IsCheapInstruction(MachineInstr &MI) const { 10435a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI.isAsCheapAsAMove() || MI.isCopyLike()) 1044c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng return true; 1045c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng if (!InstrItins || InstrItins->isEmpty()) 1046c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng return false; 1047c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng 1048c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng bool isCheap = false; 1049c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng unsigned NumDefs = MI.getDesc().getNumDefs(); 1050c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) { 1051c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng MachineOperand &DefMO = MI.getOperand(i); 1052c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng if (!DefMO.isReg() || !DefMO.isDef()) 1053c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng continue; 1054c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng --NumDefs; 1055c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng unsigned Reg = DefMO.getReg(); 1056c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng if (TargetRegisterInfo::isPhysicalRegister(Reg)) 1057c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng continue; 1058c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng 1059c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng if (!TII->hasLowDefLatency(InstrItins, &MI, i)) 1060c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng return false; 1061c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng isCheap = true; 1062c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng } 1063c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng 1064c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng return isCheap; 1065c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng} 1066c8141dfc7f983cb04e65d8acd6bcbdc8e4b8a0aeEvan Cheng 1067134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng/// CanCauseHighRegPressure - Visit BBs from header to current BB, check 106803a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng/// if hoisting an instruction of the given cost matrix can cause high 106903a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng/// register pressure. 107071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesenbool MachineLICM::CanCauseHighRegPressure(DenseMap<unsigned, int> &Cost, 107171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen bool CheapInstr) { 1072134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng for (DenseMap<unsigned, int>::iterator CI = Cost.begin(), CE = Cost.end(); 1073134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng CI != CE; ++CI) { 10749f17cf625dc8be1e92cd2755e2d118ce38fc7268Andrew Trick if (CI->second <= 0) 1075134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng continue; 1076134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 1077134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng unsigned RCId = CI->first; 10783cfecf5cc2279cbbcdd497f2898161e40e690c86Pete Cooper unsigned Limit = RegLimit[RCId]; 10793cfecf5cc2279cbbcdd497f2898161e40e690c86Pete Cooper int Cost = CI->second; 108071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen 108171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Don't hoist cheap instructions if they would increase register pressure, 108271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // even if we're under the limit. 108371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (CheapInstr) 108471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen return true; 108571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen 1086134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng for (unsigned i = BackTrace.size(); i != 0; --i) { 1087134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng SmallVector<unsigned, 8> &RP = BackTrace[i-1]; 10883cfecf5cc2279cbbcdd497f2898161e40e690c86Pete Cooper if (RP[RCId] + Cost >= Limit) 108903a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng return true; 109003a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng } 109103a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng } 109203a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 109303a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng return false; 109403a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng} 109503a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 1096134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng/// UpdateBackTraceRegPressure - Traverse the back trace from header to the 1097134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng/// current block and update their register pressures to reflect the effect 1098134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng/// of hoisting MI from the current block to the preheader. 1099134982daa9bcd87f79c357e3a2686804b9baddd9Evan Chengvoid MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) { 1100134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (MI->isImplicitDef()) 1101134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng return; 1102134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 1103134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // First compute the 'cost' of the instruction, i.e. its contribution 1104134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // to register pressure. 1105134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng DenseMap<unsigned, int> Cost; 1106134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 1107134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng const MachineOperand &MO = MI->getOperand(i); 1108134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (!MO.isReg() || MO.isImplicit()) 1109134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng continue; 1110134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng unsigned Reg = MO.getReg(); 1111c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1112134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng continue; 1113134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 111461560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng unsigned RCId, RCCost; 111561560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost); 1116134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (MO.isDef()) { 1117134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng DenseMap<unsigned, int>::iterator CI = Cost.find(RCId); 1118134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (CI != Cost.end()) 1119134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng CI->second += RCCost; 1120134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng else 1121134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng Cost.insert(std::make_pair(RCId, RCCost)); 1122134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng } else if (isOperandKill(MO, MRI)) { 1123134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng DenseMap<unsigned, int>::iterator CI = Cost.find(RCId); 1124134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (CI != Cost.end()) 1125134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng CI->second -= RCCost; 1126134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng else 1127134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng Cost.insert(std::make_pair(RCId, -RCCost)); 1128134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng } 1129134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng } 1130134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 1131134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // Update register pressure of blocks from loop header to current block. 1132134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng for (unsigned i = 0, e = BackTrace.size(); i != e; ++i) { 1133134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng SmallVector<unsigned, 8> &RP = BackTrace[i]; 1134134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng for (DenseMap<unsigned, int>::iterator CI = Cost.begin(), CE = Cost.end(); 1135134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng CI != CE; ++CI) { 1136134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng unsigned RCId = CI->first; 1137134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng RP[RCId] += CI->second; 1138134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng } 1139134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng } 1140134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng} 1141134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 114245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 114345e94d68d7c99235cf4decc72812445b214df40eEvan Cheng/// the given loop invariant. 1144c26abd94877eb1e2e00de8f9f927606e37e479d8Evan Chengbool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 11450e673919f0f02f39e2210c365f732299a21db49eEvan Cheng if (MI.isImplicitDef()) 11460e673919f0f02f39e2210c365f732299a21db49eEvan Cheng return true; 11470e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 114871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Besides removing computation from the loop, hoisting an instruction has 114971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // these effects: 115071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // 115171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // - The value defined by the instruction becomes live across the entire 115271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // loop. This increases register pressure in the loop. 115371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // 115471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // - If the value is used by a PHI in the loop, a copy will be required for 115571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // lowering the PHI after extending the live range. 115671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // 115771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // - When hoisting the last use of a value in the loop, that value no longer 115871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // needs to be live in the loop. This lowers register pressure in the loop. 115971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen 116071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen bool CheapInstr = IsCheapInstruction(MI); 116171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen bool CreatesCopy = HasLoopPHIUse(&MI); 116271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen 116371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Don't hoist a cheap instruction if it would create a copy in the loop. 116471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (CheapInstr && CreatesCopy) { 116571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI); 116671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen return false; 116771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen } 116861560e205a7997749f066dcceaadd5f4b9b5e1beEvan Cheng 116971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Rematerializable instructions should always be hoisted since the register 117071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // allocator can just pull them down again when needed. 117171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (TII->isTriviallyReMaterializable(&MI, AA)) 117271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen return true; 117371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen 117471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Estimate register pressure to determine whether to LICM the instruction. 117571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // In low register pressure situation, we can be more aggressive about 117671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // hoisting. Also, favors hoisting long latency instructions even in 117771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // moderately high pressure situation. 117871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Cheap instructions will only be hoisted if they don't increase register 117971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // pressure at all. 118071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // FIXME: If there are long latency loop-invariant instructions inside the 118171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // loop at this point, why didn't the optimizer's LICM hoist them? 118271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen DenseMap<unsigned, int> Cost; 118371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) { 118471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen const MachineOperand &MO = MI.getOperand(i); 118571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (!MO.isReg() || MO.isImplicit()) 118671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen continue; 118771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 118871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 118971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen continue; 119003a9fdf2e755c1cebdb8371d79b591d46daa9463Evan Cheng 119171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen unsigned RCId, RCCost; 119271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen getRegisterClassIDAndCost(&MI, Reg, i, RCId, RCCost); 119371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (MO.isDef()) { 119471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (HasHighOperandLatency(MI, i, Reg)) { 119571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen DEBUG(dbgs() << "Hoist High Latency: " << MI); 119671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen ++NumHighLatency; 119771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen return true; 11980e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 119971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen Cost[RCId] += RCCost; 120071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen } else if (isOperandKill(MO, MRI)) { 120171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Is a virtual register use is a kill, hoisting it out of the loop 120271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // may actually reduce register pressure or be register pressure 120371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // neutral. 120471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen Cost[RCId] -= RCCost; 12050e673919f0f02f39e2210c365f732299a21db49eEvan Cheng } 120671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen } 12070e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 120871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Visit BBs from header to current BB, if hoisting this doesn't cause 120971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // high register pressure, then it's safe to proceed. 121071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (!CanCauseHighRegPressure(Cost, CheapInstr)) { 121171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI); 121271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen ++NumLowRP; 121371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen return true; 121471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen } 12150e673919f0f02f39e2210c365f732299a21db49eEvan Cheng 121671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Don't risk increasing register pressure if it would create copies. 121771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (CreatesCopy) { 121871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI); 121971fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen return false; 122071fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen } 12217007e4c5564f32fe4f06765a9740218039e7b492Evan Cheng 122271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // Do not "speculate" in high register pressure situation. If an 122371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // instruction is not guaranteed to be executed in the loop, it's best to be 122471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // conservative. 122571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (AvoidSpeculation && 122671fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) { 122771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen DEBUG(dbgs() << "Won't speculate: " << MI); 122871fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen return false; 122987b75ba75e854773bde482309d6594c25c567e0eEvan Cheng } 123045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 123171fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // High register pressure situation, only hoist if the instruction is going 123271fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen // to be remat'ed. 123371fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen if (!TII->isTriviallyReMaterializable(&MI, AA) && 123471fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen !MI.isInvariantLoad(AA)) { 123571fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI); 12368b560b8c485992dbd62ee31aaff5ac25b5549bd6Jakob Stoklund Olesen return false; 123771fbed45d9f4e2e886afc7f22c058087e7872dc6Jakob Stoklund Olesen } 1238af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 1239af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return true; 1240af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng} 1241af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 12425c95230f25a51835375ebaae77b841c6d2c57889Dan GohmanMachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) { 1243e95f3195b8c65f377a59cc716bfda58c8f7c2f5eEvan Cheng // Don't unfold simple loads. 12445a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->canFoldAsLoad()) 1245e95f3195b8c65f377a59cc716bfda58c8f7c2f5eEvan Cheng return 0; 1246e95f3195b8c65f377a59cc716bfda58c8f7c2f5eEvan Cheng 12475c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // If not, we may be able to unfold a load and hoist that. 12485c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // First test whether the instruction is loading from an amenable 12495c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // memory location. 12509fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng if (!MI->isInvariantLoad(AA)) 125187b75ba75e854773bde482309d6594c25c567e0eEvan Cheng return 0; 125287b75ba75e854773bde482309d6594c25c567e0eEvan Cheng 12535c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // Next determine the register class for a temporary register. 12540115e164bad632572e2cfbaf72f0f0882d5319deDan Gohman unsigned LoadRegIndex; 12555c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman unsigned NewOpc = 12565c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), 12575c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman /*UnfoldLoad=*/true, 12580115e164bad632572e2cfbaf72f0f0882d5319deDan Gohman /*UnfoldStore=*/false, 12590115e164bad632572e2cfbaf72f0f0882d5319deDan Gohman &LoadRegIndex); 12605c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman if (NewOpc == 0) return 0; 1261e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MID = TII->get(NewOpc); 1262e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MID.getNumDefs() != 1) return 0; 1263397fc4874efe9c17e737d4c5c50bd19dc3bf27f5Jakob Stoklund Olesen MachineFunction &MF = *MI->getParent()->getParent(); 1264397fc4874efe9c17e737d4c5c50bd19dc3bf27f5Jakob Stoklund Olesen const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF); 12655c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // Ok, we're unfolding. Create a temporary register and do the unfold. 12660e673919f0f02f39e2210c365f732299a21db49eEvan Cheng unsigned Reg = MRI->createVirtualRegister(RC); 126787b75ba75e854773bde482309d6594c25c567e0eEvan Cheng 12685c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman SmallVector<MachineInstr *, 2> NewMIs; 12695c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman bool Success = 12705c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman TII->unfoldMemoryOperand(MF, MI, Reg, 12715c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman /*UnfoldLoad=*/true, /*UnfoldStore=*/false, 12725c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman NewMIs); 12735c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman (void)Success; 12745c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman assert(Success && 12755c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " 12765c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman "succeeded!"); 12775c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman assert(NewMIs.size() == 2 && 12785c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman "Unfolded a load into multiple instructions!"); 12795c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman MachineBasicBlock *MBB = MI->getParent(); 12807c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MachineBasicBlock::iterator Pos = MI; 12817c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MBB->insert(Pos, NewMIs[0]); 12827c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MBB->insert(Pos, NewMIs[1]); 12835c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // If unfolding produced a load that wasn't loop-invariant or profitable to 12845c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // hoist, discard the new instructions and bail. 1285c26abd94877eb1e2e00de8f9f927606e37e479d8Evan Cheng if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) { 12865c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman NewMIs[0]->eraseFromParent(); 12875c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman NewMIs[1]->eraseFromParent(); 12885c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman return 0; 12895c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman } 1290134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 1291134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // Update register pressure for the unfolded instruction. 1292134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng UpdateRegPressure(NewMIs[1]); 1293134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 12945c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // Otherwise we successfully unfolded a load that we can hoist. 12955c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman MI->eraseFromParent(); 12965c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman return NewMIs[0]; 12975c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman} 12985c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman 1299777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Chengvoid MachineLICM::InitCSEMap(MachineBasicBlock *BB) { 1300777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) { 1301777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng const MachineInstr *MI = &*I; 13029fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng unsigned Opcode = MI->getOpcode(); 13039fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 13049fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng CI = CSEMap.find(Opcode); 13059fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng if (CI != CSEMap.end()) 13069fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng CI->second.push_back(MI); 13079fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng else { 13089fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng std::vector<const MachineInstr*> CSEMIs; 13099fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng CSEMIs.push_back(MI); 13109fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 1311777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng } 1312777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng } 1313777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng} 1314777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng 131578e5c1140adc926e7c004748c1c912bfddd875b4Evan Chengconst MachineInstr* 131678e5c1140adc926e7c004748c1c912bfddd875b4Evan ChengMachineLICM::LookForDuplicate(const MachineInstr *MI, 131778e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng std::vector<const MachineInstr*> &PrevMIs) { 13189fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 13199fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng const MachineInstr *PrevMI = PrevMIs[i]; 13209fe2009956fc40f3aea46fb3c38dcfb61c4aca46Evan Cheng if (TII->produceSameValue(MI, PrevMI, (PreRegAlloc ? MRI : 0))) 13219fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng return PrevMI; 13229fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng } 13239fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng return 0; 13249fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng} 13259fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng 13269fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Chengbool MachineLICM::EliminateCSE(MachineInstr *MI, 13279fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) { 1328db8980903717e1127463f00a34cae9bd29f82a91Evan Cheng // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate 1329db8980903717e1127463f00a34cae9bd29f82a91Evan Cheng // the undef property onto uses. 1330db8980903717e1127463f00a34cae9bd29f82a91Evan Cheng if (CI == CSEMap.end() || MI->isImplicitDef()) 133178e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng return false; 133278e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng 133378e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) { 133465a41eb59e37b9e2b8d3ecff56c8fc44ddc9de58David Greene DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); 13356ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman 13366ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman // Replace virtual registers defined by MI by their counterparts defined 13376ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman // by Dup. 13381025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng SmallVector<unsigned, 2> Defs; 133978e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 134078e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng const MachineOperand &MO = MI->getOperand(i); 13416ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman 13426ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman // Physical registers may not differ here. 13436ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman assert((!MO.isReg() || MO.getReg() == 0 || 13446ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || 13456ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman MO.getReg() == Dup->getOperand(i).getReg()) && 13466ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman "Instructions with different phys regs are not identical!"); 13476ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman 13486ac33b4533889f132ba10c812ae574d779c827b9Dan Gohman if (MO.isReg() && MO.isDef() && 13491025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) 13501025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng Defs.push_back(i); 13511025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng } 13521025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng 13531025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng SmallVector<const TargetRegisterClass*, 2> OrigRCs; 13541025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 13551025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng unsigned Idx = Defs[i]; 13561025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng unsigned Reg = MI->getOperand(Idx).getReg(); 13571025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng unsigned DupReg = Dup->getOperand(Idx).getReg(); 13581025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng OrigRCs.push_back(MRI->getRegClass(DupReg)); 13591025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng 13601025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) { 13611025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng // Restore old RCs if more than one defs. 13621025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng for (unsigned j = 0; j != i; ++j) 13631025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]); 13641025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng return false; 1365e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman } 13669fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng } 13671025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng 13681025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 13691025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng unsigned Idx = Defs[i]; 13701025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng unsigned Reg = MI->getOperand(Idx).getReg(); 13711025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng unsigned DupReg = Dup->getOperand(Idx).getReg(); 13721025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng MRI->replaceRegWith(Reg, DupReg); 13731025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng MRI->clearKillFlags(DupReg); 13741025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng } 13751025cce290d99fd325bccd0c1e89dab49eea8140Evan Cheng 137678e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng MI->eraseFromParent(); 137778e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng ++NumCSEed; 137878e5c1140adc926e7c004748c1c912bfddd875b4Evan Cheng return true; 13799fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng } 13809fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng return false; 13819fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng} 13829fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng 13837efba85d414949febe51100e298077233526787cEvan Cheng/// MayCSE - Return true if the given instruction will be CSE'd if it's 13847efba85d414949febe51100e298077233526787cEvan Cheng/// hoisted out of the loop. 13857efba85d414949febe51100e298077233526787cEvan Chengbool MachineLICM::MayCSE(MachineInstr *MI) { 13867efba85d414949febe51100e298077233526787cEvan Cheng unsigned Opcode = MI->getOpcode(); 13877efba85d414949febe51100e298077233526787cEvan Cheng DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 13887efba85d414949febe51100e298077233526787cEvan Cheng CI = CSEMap.find(Opcode); 13897efba85d414949febe51100e298077233526787cEvan Cheng // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate 13907efba85d414949febe51100e298077233526787cEvan Cheng // the undef property onto uses. 13917efba85d414949febe51100e298077233526787cEvan Cheng if (CI == CSEMap.end() || MI->isImplicitDef()) 13927efba85d414949febe51100e298077233526787cEvan Cheng return false; 13937efba85d414949febe51100e298077233526787cEvan Cheng 13947efba85d414949febe51100e298077233526787cEvan Cheng return LookForDuplicate(MI, CI->second) != 0; 13957efba85d414949febe51100e298077233526787cEvan Cheng} 13967efba85d414949febe51100e298077233526787cEvan Cheng 1397e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// Hoist - When an instruction is found to use only loop invariant operands 1398e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// that are safe to hoist, this instruction is called to do the dirty work. 13990f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 1400134982daa9bcd87f79c357e3a2686804b9baddd9Evan Chengbool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) { 1401589f1f5a4321eeee2856baa5c8ab1139d6e0351eDan Gohman // First check whether we should hoist this instruction. 1402c26abd94877eb1e2e00de8f9f927606e37e479d8Evan Cheng if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { 14035c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman // If not, try unfolding a hoistable load. 14045c95230f25a51835375ebaae77b841c6d2c57889Dan Gohman MI = ExtractHoistableLoad(MI); 1405134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng if (!MI) return false; 1406589f1f5a4321eeee2856baa5c8ab1139d6e0351eDan Gohman } 14070f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1408c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Now move the instructions to the predecessor, inserting it before any 1409c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // terminator instructions. 1410c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DEBUG({ 141165a41eb59e37b9e2b8d3ecff56c8fc44ddc9de58David Greene dbgs() << "Hoisting " << *MI; 1412853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (Preheader->getBasicBlock()) 141365a41eb59e37b9e2b8d3ecff56c8fc44ddc9de58David Greene dbgs() << " to MachineBasicBlock " 1414853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman << Preheader->getName(); 1415589f1f5a4321eeee2856baa5c8ab1139d6e0351eDan Gohman if (MI->getParent()->getBasicBlock()) 141665a41eb59e37b9e2b8d3ecff56c8fc44ddc9de58David Greene dbgs() << " from MachineBasicBlock " 1417324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen << MI->getParent()->getName(); 141865a41eb59e37b9e2b8d3ecff56c8fc44ddc9de58David Greene dbgs() << "\n"; 1419c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman }); 1420b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 1421777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng // If this is the first instruction being hoisted to the preheader, 1422777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng // initialize the CSE map with potential common expressions. 142382e0a1a1a81ad54452823a8eb1e8d743cf38f098Evan Cheng if (FirstInLoop) { 1424853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman InitCSEMap(Preheader); 142582e0a1a1a81ad54452823a8eb1e8d743cf38f098Evan Cheng FirstInLoop = false; 142682e0a1a1a81ad54452823a8eb1e8d743cf38f098Evan Cheng } 1427777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng 1428af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // Look for opportunity to CSE the hoisted instruction. 1429777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng unsigned Opcode = MI->getOpcode(); 1430777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 1431777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng CI = CSEMap.find(Opcode); 14329fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng if (!EliminateCSE(MI, CI)) { 14339fb744e16945390d6ff0a631d4ad7637fec5b7b1Evan Cheng // Otherwise, splice the instruction to the preheader. 1434853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI); 1435777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng 1436134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng // Update register pressure for BBs from header to this block. 1437134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng UpdateBackTraceRegPressure(MI); 1438134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 1439e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman // Clear the kill flags of any register this instruction defines, 1440e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman // since they may need to be live throughout the entire loop 1441e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman // rather than just live for part of it. 1442e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1443e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman MachineOperand &MO = MI->getOperand(i); 1444e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman if (MO.isReg() && MO.isDef() && !MO.isDead()) 14450e673919f0f02f39e2210c365f732299a21db49eEvan Cheng MRI->clearKillFlags(MO.getReg()); 1446e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman } 1447e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman 1448af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // Add to the CSE map. 1449af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (CI != CSEMap.end()) 1450589f1f5a4321eeee2856baa5c8ab1139d6e0351eDan Gohman CI->second.push_back(MI); 1451af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng else { 1452af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng std::vector<const MachineInstr*> CSEMIs; 1453589f1f5a4321eeee2856baa5c8ab1139d6e0351eDan Gohman CSEMIs.push_back(MI); 1454777c6b7caa9bbefe14085bf51e91a0bf21b0b3c0Evan Cheng CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 1455af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 1456af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 1457b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 1458c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman ++NumHoisted; 14590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling Changed = true; 1460134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng 1461134982daa9bcd87f79c357e3a2686804b9baddd9Evan Cheng return true; 14620f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 1463853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 1464853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan GohmanMachineBasicBlock *MachineLICM::getCurPreheader() { 1465853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Determine the block to which to hoist instructions. If we can't find a 1466853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // suitable loop predecessor, we can't do any hoisting. 1467853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 1468853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // If we've tried to get a preheader and failed, don't try again. 1469853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1)) 1470853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return 0; 1471853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 1472853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (!CurPreheader) { 1473853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman CurPreheader = CurLoop->getLoopPreheader(); 1474853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (!CurPreheader) { 1475853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *Pred = CurLoop->getLoopPredecessor(); 1476853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (!Pred) { 1477853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1478853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return 0; 1479853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 1480853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 1481853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this); 1482853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (!CurPreheader) { 1483853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1484853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return 0; 1485853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 1486853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 1487853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 1488853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return CurPreheader; 1489853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman} 1490