From 61560e205a7997749f066dcceaadd5f4b9b5e1be Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Thu, 1 Sep 2011 01:45:00 +0000 Subject: Teach MachineLICM reg pressure tracking code to deal with MVT::untyped. Sorry, I can't come up with a small test case. rdar://10043690 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138934 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 67 +++++++++++++++++++++++++++------------------ 1 file changed, 40 insertions(+), 27 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 722ceb2..d310f25 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -202,6 +202,13 @@ namespace { /// void HoistRegion(MachineDomTreeNode *N, bool IsHeader = false); + /// getRegisterClassIDAndCost - For a given MI, register, and the operand + /// index, return the ID and cost of its representative register class by + /// reference. + void getRegisterClassIDAndCost(const MachineInstr *MI, + unsigned Reg, unsigned OpIdx, + unsigned &RCId, unsigned &RCCost) const; + /// InitRegPressure - Find all virtual register references that are liveout /// of the preheader to initialize the starting "register pressure". Note /// this does not count live through (livein but not used) registers. @@ -596,6 +603,23 @@ static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg()); } +/// getRegisterClassIDAndCost - For a given MI, register, and the operand +/// index, return the ID and cost of its representative register class. +void +MachineLICM::getRegisterClassIDAndCost(const MachineInstr *MI, + unsigned Reg, unsigned OpIdx, + unsigned &RCId, unsigned &RCCost) const { + const TargetRegisterClass *RC = MRI->getRegClass(Reg); + EVT VT = *RC->vt_begin(); + if (VT == MVT::untyped) { + RCId = RC->getID(); + RCCost = 1; + } else { + RCId = TLI->getRepRegClassFor(VT)->getID(); + RCCost = TLI->getRepRegClassCostFor(VT); + } +} + /// InitRegPressure - Find all virtual register references that are liveout of /// the preheader to initialize the starting "register pressure". Note this /// does not count live through (livein but not used) registers. @@ -625,18 +649,17 @@ void MachineLICM::InitRegPressure(MachineBasicBlock *BB) { continue; bool isNew = RegSeen.insert(Reg); - const TargetRegisterClass *RC = MRI->getRegClass(Reg); - EVT VT = *RC->vt_begin(); - unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); + unsigned RCId, RCCost; + getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost); if (MO.isDef()) - RegPressure[RCId] += TLI->getRepRegClassCostFor(VT); + RegPressure[RCId] += RCCost; else { bool isKill = isOperandKill(MO, MRI); if (isNew && !isKill) // Haven't seen this, it must be a livein. - RegPressure[RCId] += TLI->getRepRegClassCostFor(VT); + RegPressure[RCId] += RCCost; else if (!isNew && isKill) - RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT); + RegPressure[RCId] -= RCCost; } } } @@ -661,11 +684,8 @@ void MachineLICM::UpdateRegPressure(const MachineInstr *MI) { if (MO.isDef()) Defs.push_back(Reg); else if (!isNew && isOperandKill(MO, MRI)) { - const TargetRegisterClass *RC = MRI->getRegClass(Reg); - EVT VT = *RC->vt_begin(); - unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); - unsigned RCCost = TLI->getRepRegClassCostFor(VT); - + unsigned RCId, RCCost; + getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost); if (RCCost > RegPressure[RCId]) RegPressure[RCId] = 0; else @@ -673,13 +693,13 @@ void MachineLICM::UpdateRegPressure(const MachineInstr *MI) { } } + unsigned Idx = 0; while (!Defs.empty()) { unsigned Reg = Defs.pop_back_val(); - const TargetRegisterClass *RC = MRI->getRegClass(Reg); - EVT VT = *RC->vt_begin(); - unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); - unsigned RCCost = TLI->getRepRegClassCostFor(VT); + unsigned RCId, RCCost; + getRegisterClassIDAndCost(MI, Reg, Idx, RCId, RCCost); RegPressure[RCId] += RCCost; + ++Idx; } } @@ -879,10 +899,8 @@ void MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) { if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; - const TargetRegisterClass *RC = MRI->getRegClass(Reg); - EVT VT = *RC->vt_begin(); - unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); - unsigned RCCost = TLI->getRepRegClassCostFor(VT); + unsigned RCId, RCCost; + getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost); if (MO.isDef()) { DenseMap::iterator CI = Cost.find(RCId); if (CI != Cost.end()) @@ -941,16 +959,15 @@ bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { unsigned Reg = MO.getReg(); if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; + + unsigned RCId, RCCost; + getRegisterClassIDAndCost(&MI, Reg, i, RCId, RCCost); if (MO.isDef()) { if (HasHighOperandLatency(MI, i, Reg)) { ++NumHighLatency; return true; } - const TargetRegisterClass *RC = MRI->getRegClass(Reg); - EVT VT = *RC->vt_begin(); - unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); - unsigned RCCost = TLI->getRepRegClassCostFor(VT); DenseMap::iterator CI = Cost.find(RCId); if (CI != Cost.end()) CI->second += RCCost; @@ -960,10 +977,6 @@ bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { // Is a virtual register use is a kill, hoisting it out of the loop // may actually reduce register pressure or be register pressure // neutral. - const TargetRegisterClass *RC = MRI->getRegClass(Reg); - EVT VT = *RC->vt_begin(); - unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); - unsigned RCCost = TLI->getRepRegClassCostFor(VT); DenseMap::iterator CI = Cost.find(RCId); if (CI != Cost.end()) CI->second -= RCCost; -- cgit v1.1 From 9ac743a4ee61cb845bbe22a2f6898f38c2adafce Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Mon, 10 Oct 2011 19:09:20 +0000 Subject: Add dominance check for the instruction being hoisted. For example, MachineLICM should not hoist a load that is not guaranteed to be executed. Radar 10254254. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141569 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index d310f25..f8cbe41 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -168,6 +168,11 @@ namespace { /// bool IsLoopInvariantInst(MachineInstr &I); + /// IsGuaranteedToExecute - check to make sure that the MI dominates + /// all of the exit blocks. If it doesn't, then there is a path out of the + /// loop which does not execute this instruction, so we can't hoist it. + bool IsGuaranteedToExecute(MachineInstr *MI); + /// HasAnyPHIUse - Return true if the specified register is used by any /// phi node. bool HasAnyPHIUse(unsigned Reg) const; @@ -1129,6 +1134,29 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, return false; } +/// IsGuaranteedToExecute - check to make sure that the instruction dominates +/// all of the exit blocks. If it doesn't, then there is a path out of the loop +/// which does not execute this instruction, so we can't hoist it. +bool MachineLICM::IsGuaranteedToExecute(MachineInstr *MI) { + // If the instruction is in the header block for the loop (which is very + // common), it is always guaranteed to dominate the exit blocks. Since this + // is a common case, and can save some work, check it now. + if (MI->getParent() == CurLoop->getHeader()) + return true; + + // Get the exit blocks for the current loop. + SmallVector ExitBlocks; + CurLoop->getExitingBlocks(ExitBlocks); + + // Verify that the block dominates each of the exit blocks of the loop. + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) + if (ExitBlocks[i] != CurLoop->getHeader() && + !DT->dominates(MI->getParent(), ExitBlocks[i])) + return false; + + return true; +} + /// Hoist - When an instruction is found to use only loop invariant operands /// that are safe to hoist, this instruction is called to do the dirty work. /// @@ -1139,6 +1167,8 @@ bool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) { MI = ExtractHoistableLoad(MI); if (!MI) return false; } + if (!IsGuaranteedToExecute(MI)) + return false; // Now move the instructions to the predecessor, inserting it before any // terminator instructions. -- cgit v1.1 From 6b50bc9d88538c155503582b095fdba518070257 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Mon, 10 Oct 2011 20:32:03 +0000 Subject: If loop header is also loop exiting block then it may not be safe to hoist instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141576 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index f8cbe41..bd25b2c 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -1145,13 +1145,12 @@ bool MachineLICM::IsGuaranteedToExecute(MachineInstr *MI) { return true; // Get the exit blocks for the current loop. - SmallVector ExitBlocks; - CurLoop->getExitingBlocks(ExitBlocks); + SmallVector ExitingBlocks; + CurLoop->getExitingBlocks(ExitingBlocks); // Verify that the block dominates each of the exit blocks of the loop. - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (ExitBlocks[i] != CurLoop->getHeader() && - !DT->dominates(MI->getParent(), ExitBlocks[i])) + for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) + if (!DT->dominates(MI->getParent(), ExitingBlocks[i])) return false; return true; -- cgit v1.1 From db7334dbc55fb4b86fa3db19bff08ec02ba474d5 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Mon, 10 Oct 2011 23:18:02 +0000 Subject: Revert r141569 and r141576. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141594 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 29 ----------------------------- 1 file changed, 29 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index bd25b2c..d310f25 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -168,11 +168,6 @@ namespace { /// bool IsLoopInvariantInst(MachineInstr &I); - /// IsGuaranteedToExecute - check to make sure that the MI dominates - /// all of the exit blocks. If it doesn't, then there is a path out of the - /// loop which does not execute this instruction, so we can't hoist it. - bool IsGuaranteedToExecute(MachineInstr *MI); - /// HasAnyPHIUse - Return true if the specified register is used by any /// phi node. bool HasAnyPHIUse(unsigned Reg) const; @@ -1134,28 +1129,6 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, return false; } -/// IsGuaranteedToExecute - check to make sure that the instruction dominates -/// all of the exit blocks. If it doesn't, then there is a path out of the loop -/// which does not execute this instruction, so we can't hoist it. -bool MachineLICM::IsGuaranteedToExecute(MachineInstr *MI) { - // If the instruction is in the header block for the loop (which is very - // common), it is always guaranteed to dominate the exit blocks. Since this - // is a common case, and can save some work, check it now. - if (MI->getParent() == CurLoop->getHeader()) - return true; - - // Get the exit blocks for the current loop. - SmallVector ExitingBlocks; - CurLoop->getExitingBlocks(ExitingBlocks); - - // Verify that the block dominates each of the exit blocks of the loop. - for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) - if (!DT->dominates(MI->getParent(), ExitingBlocks[i])) - return false; - - return true; -} - /// Hoist - When an instruction is found to use only loop invariant operands /// that are safe to hoist, this instruction is called to do the dirty work. /// @@ -1166,8 +1139,6 @@ bool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) { MI = ExtractHoistableLoad(MI); if (!MI) return false; } - if (!IsGuaranteedToExecute(MI)) - return false; // Now move the instructions to the predecessor, inserting it before any // terminator instructions. -- cgit v1.1 From 2e350479478ccf809e2142a4f0ad8062342577cc Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Tue, 11 Oct 2011 18:09:58 +0000 Subject: Add dominance check for the instruction being hoisted. For example, MachineLICM should not hoist a load that is not guaranteed to be executed. Radar 10254254. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141689 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 47 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 46 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index d310f25..f6a08d3 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -91,6 +91,11 @@ namespace { // For each opcode, keep a list of potential CSE instructions. DenseMap > CSEMap; + // If a MBB does not dominate loop exiting blocks then it may not safe + // to hoist loads from this block. + bool CurrentMBBDominatesLoopExitingBlocks; + bool NeedToCheckMBBDominance; + public: static char ID; // Pass identification, replacement for typeid MachineLICM() : @@ -194,6 +199,10 @@ namespace { /// hoist the given loop invariant. bool IsProfitableToHoist(MachineInstr &MI); + /// IsGuaranteedToExecute - Check if this mbb is guaranteed to execute. + /// If not then a load from this mbb may not be safe to hoist. + bool IsGuaranteedToExecute(MachineBasicBlock *BB); + /// HoistRegion - Walk the specified region of the CFG (defined by all /// blocks dominated by the specified block, and that are in the current /// loop) in depth first order w.r.t the DominatorTree. This allows us to @@ -295,6 +304,9 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { MRI = &MF.getRegInfo(); InstrItins = TM->getInstrItineraryData(); AllocatableSet = TRI->getAllocatableSet(MF); + // Stay conservative. + CurrentMBBDominatesLoopExitingBlocks = false; + NeedToCheckMBBDominance = true; if (PreRegAlloc) { // Estimate register pressure during pre-regalloc pass. @@ -459,6 +471,7 @@ void MachineLICM::HoistRegionPostRA() { ++PhysRegDefs[*AS]; } + NeedToCheckMBBDominance = true; for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); MII != E; ++MII) { MachineInstr *MI = &*MII; @@ -552,6 +565,30 @@ void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { Changed = true; } +// IsGuaranteedToExecute - Check if this mbb is guaranteed to execute. +// If not then a load from this mbb may not be safe to hoist. +bool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) { + // Do not check if we already have checked it once. + if (NeedToCheckMBBDominance == false) + return CurrentMBBDominatesLoopExitingBlocks; + + NeedToCheckMBBDominance = false; + + if (BB != CurLoop->getHeader()) { + // Check loop exiting blocks. + SmallVector CurrentLoopExitingBlocks; + CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); + for (unsigned i = 0, e = CurrentLoopExitingBlocks.size(); i != e; ++i) + if (!DT->dominates(BB, CurrentLoopExitingBlocks[i])) { + CurrentMBBDominatesLoopExitingBlocks = false; + return CurrentMBBDominatesLoopExitingBlocks; + } + } + + CurrentMBBDominatesLoopExitingBlocks = true; + return CurrentMBBDominatesLoopExitingBlocks; +} + /// HoistRegion - Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth /// first order w.r.t the DominatorTree. This allows us to visit definitions @@ -578,6 +615,7 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N, bool IsHeader) { // Remember livein register pressure. BackTrace.push_back(RegPressure); + NeedToCheckMBBDominance = true; for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); MII != E; ) { MachineBasicBlock::iterator NextMII = MII; ++NextMII; @@ -711,7 +749,14 @@ bool MachineLICM::IsLICMCandidate(MachineInstr &I) { bool DontMoveAcrossStore = true; if (!I.isSafeToMove(TII, AA, DontMoveAcrossStore)) return false; - + + // If it is load then check if it is guaranteed to execute by making sure that + // it dominates all exiting blocks. If it doesn't, then there is a path out of + // the loop which does not execute this load, so we can't hoist it. + // Stores and side effects are already checked by isSafeToMove. + if (I.getDesc().mayLoad() && !IsGuaranteedToExecute(I.getParent())) + return false; + return true; } -- cgit v1.1 From c83693f5b0aa26de55881345a79f4202ef9c3088 Mon Sep 17 00:00:00 2001 From: Bill Wendling Date: Tue, 11 Oct 2011 22:42:31 +0000 Subject: N.B. This is with the new EH scheme: The blocks with invokes have branches to the dispatch block, because that more correctly models the behavior of the CFG. The dispatch of course has edges to the landing pads. Those landing pads could contain invokes, which then have branches back to the dispatch. This creates a loop. The machine LICM pass looks at this loop and thinks it can hoist elements out of it. But because the dispatch is an alternate entry point into the program, the hoisted instructions won't be executed. I wasn't able to get a testcase which was small and could reproduce all of the time. The function_try_block.cpp in llvm-test was where this showed up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141726 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index f6a08d3..70da982 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -336,6 +336,11 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { continue; } + // If the header is a landing pad, then we don't want to hoist instructions + // out of it. This can happen with SjLj exception handling which has a + // dispatch table as the landing pad. + if (CurLoop->getHeader()->isLandingPad()) continue; + if (!PreRegAlloc) HoistRegionPostRA(); else { -- cgit v1.1 From fad62874883ab78af47b4eeba042775a67ea7515 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Tue, 11 Oct 2011 23:48:44 +0000 Subject: Refine r141689 with a tri-state variable. Also teach MachineLICM to avoid "speculation" when register pressure is high. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141744 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 42 +++++++++++++++++++++++------------------- 1 file changed, 23 insertions(+), 19 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 70da982..63c73d2 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -91,10 +91,16 @@ namespace { // For each opcode, keep a list of potential CSE instructions. DenseMap > CSEMap; + enum { + SpeculateFalse = 0, + SpeculateTrue = 1, + SpeculateUnknown = 2 + }; + // If a MBB does not dominate loop exiting blocks then it may not safe // to hoist loads from this block. - bool CurrentMBBDominatesLoopExitingBlocks; - bool NeedToCheckMBBDominance; + // Tri-state: 0 - false, 1 - true, 2 - unknown + unsigned SpeculationState; public: static char ID; // Pass identification, replacement for typeid @@ -304,9 +310,6 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { MRI = &MF.getRegInfo(); InstrItins = TM->getInstrItineraryData(); AllocatableSet = TRI->getAllocatableSet(MF); - // Stay conservative. - CurrentMBBDominatesLoopExitingBlocks = false; - NeedToCheckMBBDominance = true; if (PreRegAlloc) { // Estimate register pressure during pre-regalloc pass. @@ -476,7 +479,7 @@ void MachineLICM::HoistRegionPostRA() { ++PhysRegDefs[*AS]; } - NeedToCheckMBBDominance = true; + SpeculationState = SpeculateUnknown; for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); MII != E; ++MII) { MachineInstr *MI = &*MII; @@ -573,25 +576,22 @@ void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { // IsGuaranteedToExecute - Check if this mbb is guaranteed to execute. // If not then a load from this mbb may not be safe to hoist. bool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) { - // Do not check if we already have checked it once. - if (NeedToCheckMBBDominance == false) - return CurrentMBBDominatesLoopExitingBlocks; - - NeedToCheckMBBDominance = false; - + if (SpeculationState != SpeculateUnknown) + return SpeculationState == SpeculateFalse; + if (BB != CurLoop->getHeader()) { // Check loop exiting blocks. SmallVector CurrentLoopExitingBlocks; CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); for (unsigned i = 0, e = CurrentLoopExitingBlocks.size(); i != e; ++i) if (!DT->dominates(BB, CurrentLoopExitingBlocks[i])) { - CurrentMBBDominatesLoopExitingBlocks = false; - return CurrentMBBDominatesLoopExitingBlocks; + SpeculationState = SpeculateTrue; + return false; } } - CurrentMBBDominatesLoopExitingBlocks = true; - return CurrentMBBDominatesLoopExitingBlocks; + SpeculationState = SpeculateFalse; + return true; } /// HoistRegion - Walk the specified region of the CFG (defined by all blocks @@ -620,7 +620,7 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N, bool IsHeader) { // Remember livein register pressure. BackTrace.push_back(RegPressure); - NeedToCheckMBBDominance = true; + SpeculationState = SpeculateUnknown; for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); MII != E; ) { MachineBasicBlock::iterator NextMII = MII; ++NextMII; @@ -1044,8 +1044,12 @@ bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { // High register pressure situation, only hoist if the instruction is going to // be remat'ed. - if (!TII->isTriviallyReMaterializable(&MI, AA) && - !MI.isInvariantLoad(AA)) + // Also, do not "speculate" in high register pressure situation. If an + // instruction is not guaranteed to be executed in the loop, it's best to be + // conservative. + if (SpeculationState == SpeculateTrue || + (!TII->isTriviallyReMaterializable(&MI, AA) && + !MI.isInvariantLoad(AA))) return false; } -- cgit v1.1 From 7efba85d414949febe51100e298077233526787c Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Wed, 12 Oct 2011 00:09:14 +0000 Subject: Fix r141744. 1. The speculation check may not have been performed if the BB hasn't had a load LICM candidate. 2. If the candidate would be CSE'ed, then go ahead and speculatively LICM the instruction even if it's in high register pressure situation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141747 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 63c73d2..6116281 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -251,6 +251,10 @@ namespace { bool EliminateCSE(MachineInstr *MI, DenseMap >::iterator &CI); + /// MayCSE - Return true if the given instruction will be CSE'd if it's + /// hoisted out of the loop. + bool MayCSE(MachineInstr *MI); + /// Hoist - When an instruction is found to only use loop invariant operands /// that is safe to hoist, this instruction is called to do the dirty work. /// It returns true if the instruction is hoisted. @@ -1047,7 +1051,7 @@ bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { // Also, do not "speculate" in high register pressure situation. If an // instruction is not guaranteed to be executed in the loop, it's best to be // conservative. - if (SpeculationState == SpeculateTrue || + if ((!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI)) || (!TII->isTriviallyReMaterializable(&MI, AA) && !MI.isInvariantLoad(AA))) return false; @@ -1183,6 +1187,20 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, return false; } +/// MayCSE - Return true if the given instruction will be CSE'd if it's +/// hoisted out of the loop. +bool MachineLICM::MayCSE(MachineInstr *MI) { + unsigned Opcode = MI->getOpcode(); + DenseMap >::iterator + CI = CSEMap.find(Opcode); + // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate + // the undef property onto uses. + if (CI == CSEMap.end() || MI->isImplicitDef()) + return false; + + return LookForDuplicate(MI, CI->second) != 0; +} + /// Hoist - When an instruction is found to use only loop invariant operands /// that are safe to hoist, this instruction is called to do the dirty work. /// -- cgit v1.1 From a2e87912d826b1843bb5b1058670f09b87aea905 Mon Sep 17 00:00:00 2001 From: Bill Wendling Date: Wed, 12 Oct 2011 02:58:01 +0000 Subject: Expand the check for a landing pad so that it looks at the basic block's containing loop's header to see if that's a landing pad. If it is, then we don't want to hoist instructions out of the loop and above the header. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141767 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 6116281..889406a 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -343,11 +343,6 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { continue; } - // If the header is a landing pad, then we don't want to hoist instructions - // out of it. This can happen with SjLj exception handling which has a - // dispatch table as the landing pad. - if (CurLoop->getHeader()->isLandingPad()) continue; - if (!PreRegAlloc) HoistRegionPostRA(); else { @@ -472,6 +467,12 @@ void MachineLICM::HoistRegionPostRA() { const std::vector Blocks = CurLoop->getBlocks(); for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { MachineBasicBlock *BB = Blocks[i]; + + // If the header of the loop containing this basic block is a landing pad, + // then don't try to hoist instructions out of this loop. + const MachineLoop *ML = MLI->getLoopFor(BB); + if (ML && ML->getHeader()->isLandingPad()) continue; + // Conservatively treat live-in's as an external def. // FIXME: That means a reload that're reused in successor block(s) will not // be LICM'ed. @@ -607,6 +608,11 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N, bool IsHeader) { assert(N != 0 && "Null dominator tree node?"); MachineBasicBlock *BB = N->getBlock(); + // If the header of the loop containing this basic block is a landing pad, + // then don't try to hoist instructions out of this loop. + const MachineLoop *ML = MLI->getLoopFor(BB); + if (ML && ML->getHeader()->isLandingPad()) return; + // If this subregion is not in the top level loop at all, exit. if (!CurLoop->contains(BB)) return; -- cgit v1.1 From 7007e4c5564f32fe4f06765a9740218039e7b492 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Wed, 12 Oct 2011 21:33:49 +0000 Subject: Disable machine LICM speculation check (for profitability) until I have time to investigate the regressions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141813 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 21 +++++++++++++++------ 1 file changed, 15 insertions(+), 6 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 889406a..25109ab 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -37,10 +37,16 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; +static cl::opt +AvoidSpeculation("avoid-speculation", + cl::desc("MachineLICM should avoid speculation"), + cl::init(false), cl::Hidden); + STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); STATISTIC(NumLowRP, @@ -1052,14 +1058,17 @@ bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { return true; } - // High register pressure situation, only hoist if the instruction is going to - // be remat'ed. - // Also, do not "speculate" in high register pressure situation. If an + // Do not "speculate" in high register pressure situation. If an // instruction is not guaranteed to be executed in the loop, it's best to be // conservative. - if ((!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI)) || - (!TII->isTriviallyReMaterializable(&MI, AA) && - !MI.isInvariantLoad(AA))) + if (AvoidSpeculation && + (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) + return false; + + // High register pressure situation, only hoist if the instruction is going to + // be remat'ed. + if (!TII->isTriviallyReMaterializable(&MI, AA) && + !MI.isInvariantLoad(AA)) return false; } -- cgit v1.1 From ea3abd553668e272772f04ae1536034cd37e70d1 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Thu, 13 Oct 2011 01:09:50 +0000 Subject: Tabs to spaces. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141844 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 25109ab..a1f80d5 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -596,8 +596,8 @@ bool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) { CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); for (unsigned i = 0, e = CurrentLoopExitingBlocks.size(); i != e; ++i) if (!DT->dominates(BB, CurrentLoopExitingBlocks[i])) { - SpeculationState = SpeculateTrue; - return false; + SpeculationState = SpeculateTrue; + return false; } } -- cgit v1.1 From 6c15fec3c5b4770570a4d681762a7bd510e65077 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Mon, 17 Oct 2011 17:35:01 +0000 Subject: It is safe to speculate load from GOT. This fixes performance regression caused by r141689. Radar 10281206. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142202 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index a1f80d5..8f7a8eb 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -762,6 +762,21 @@ void MachineLICM::UpdateRegPressure(const MachineInstr *MI) { } } +/// isLoadFromGOT - Return true if this machine instruction loads from +/// global offset table. +static bool isLoadFromGOT(MachineInstr &MI) { + assert (MI.getDesc().mayLoad() && "Expected MI that loads!"); + for (MachineInstr::mmo_iterator I = MI.memoperands_begin(), + E = MI.memoperands_end(); I != E; ++I) { + if (const Value *V = (*I)->getValue()) { + if (const PseudoSourceValue *PSV = dyn_cast(V)) + if (PSV == PSV->getGOT()) + return true; + } + } + return false; +} + /// IsLICMCandidate - Returns true if the instruction may be a suitable /// candidate for LICM. e.g. If the instruction is a call, then it's obviously /// not safe to hoist it. @@ -775,7 +790,8 @@ bool MachineLICM::IsLICMCandidate(MachineInstr &I) { // it dominates all exiting blocks. If it doesn't, then there is a path out of // the loop which does not execute this load, so we can't hoist it. // Stores and side effects are already checked by isSafeToMove. - if (I.getDesc().mayLoad() && !IsGuaranteedToExecute(I.getParent())) + if (I.getDesc().mayLoad() && !isLoadFromGOT(I) && + !IsGuaranteedToExecute(I.getParent())) return false; return true; -- cgit v1.1 From 1025cce290d99fd325bccd0c1e89dab49eea8140 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Mon, 17 Oct 2011 19:50:12 +0000 Subject: Constraint register class with constrainRegClass() to CSE a virtual into another. rdar://10293289 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142234 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 29 ++++++++++++++++++++++++++--- 1 file changed, 26 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 8f7a8eb..969a9b0 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -1196,6 +1196,7 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, // Replace virtual registers defined by MI by their counterparts defined // by Dup. + SmallVector Defs; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); @@ -1206,11 +1207,33 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, "Instructions with different phys regs are not identical!"); if (MO.isReg() && MO.isDef() && - !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { - MRI->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); - MRI->clearKillFlags(Dup->getOperand(i).getReg()); + !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) + Defs.push_back(i); + } + + SmallVector OrigRCs; + for (unsigned i = 0, e = Defs.size(); i != e; ++i) { + unsigned Idx = Defs[i]; + unsigned Reg = MI->getOperand(Idx).getReg(); + unsigned DupReg = Dup->getOperand(Idx).getReg(); + OrigRCs.push_back(MRI->getRegClass(DupReg)); + + if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) { + // Restore old RCs if more than one defs. + for (unsigned j = 0; j != i; ++j) + MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]); + return false; } } + + for (unsigned i = 0, e = Defs.size(); i != e; ++i) { + unsigned Idx = Defs[i]; + unsigned Reg = MI->getOperand(Idx).getReg(); + unsigned DupReg = Dup->getOperand(Idx).getReg(); + MRI->replaceRegWith(Reg, DupReg); + MRI->clearKillFlags(DupReg); + } + MI->eraseFromParent(); ++NumCSEed; return true; -- cgit v1.1