From 5a96b3dad2f634c9081c8b2b6c2575441dc5a2bd Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Wed, 7 Dec 2011 07:15:52 +0000 Subject: Add bundle aware API for querying instruction properties and switch the code generator to it. For non-bundle instructions, these behave exactly the same as the MC layer API. For properties like mayLoad / mayStore, look into the bundle and if any of the bundled instructions has the property it would return true. For properties like isPredicable, only return true if *all* of the bundled instructions have the property. For properties like canFoldAsLoad, isCompare, conservatively return false for bundles. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146026 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 29cfb49..8a34237 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -291,7 +291,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, if (!CEBCandidates.insert(std::make_pair(From, To))) return true; - if (!MI->isCopy() && !MI->getDesc().isAsCheapAsAMove()) + if (!MI->isCopy() && !MI->isAsCheapAsAMove()) return true; // MI is cheap, we probably don't want to break the critical edge for it. -- cgit v1.1 From cf405ba7a6e9448b753d9b72940059530c70ea90 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Thu, 8 Dec 2011 21:33:23 +0000 Subject: Filter "sink to" candidate blocks sooner. This avoids unnecessary computation to determine whether the block dominates all uses or not. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146184 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 8a34237..0d14b63 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -499,10 +499,21 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // we should sink to. for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), E = ParentBlock->succ_end(); SI != E; ++SI) { + MachineBasicBlock *SuccBlock = *SI; + // It is not possible to sink an instruction into its own block. This can + // happen with loops. + if (ParentBlock == SuccBlock) + continue; + + // It's not safe to sink instructions to EH landing pad. Control flow into + // landing pad is implicitly defined. + if (SuccBlock->isLandingPad()) + continue; + bool LocalUse = false; - if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, + if (AllUsesDominatedByBlock(Reg, SuccBlock, ParentBlock, BreakPHIEdge, LocalUse)) { - SuccToSinkTo = *SI; + SuccToSinkTo = SuccBlock; break; } if (LocalUse) @@ -520,15 +531,6 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { if (SuccToSinkTo == 0) return false; - // It's not safe to sink instructions to EH landing pad. Control flow into - // landing pad is implicitly defined. - if (SuccToSinkTo->isLandingPad()) - return false; - - // It is not possible to sink an instruction into its own block. This can - // happen with loops. - if (MI->getParent() == SuccToSinkTo) - return false; // If the instruction to move defines a dead physical register which is live // when leaving the basic block, don't move it because it could turn into a -- cgit v1.1 From e265bcf1a609c81c197971cd392e98a12d97162d Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Thu, 8 Dec 2011 21:48:01 +0000 Subject: Refactor. No intentional functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146187 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 70 ++++++++++++++++++++++++++------------------- 1 file changed, 41 insertions(+), 29 deletions(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 0d14b63..7740a75 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -90,6 +90,8 @@ namespace { bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, bool &BreakPHIEdge, bool &LocalUse) const; + MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, bool &BreakPHIEdge); + bool PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); }; @@ -401,25 +403,9 @@ static void collectDebugValues(MachineInstr *MI, } } -/// SinkInstruction - Determine whether it is safe to sink the specified machine -/// instruction out of its current block into a successor. -bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { - // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to - // be close to the source to make it easier to coalesce. - if (AvoidsSinking(MI, MRI)) - return false; - - // Check if it's safe to move the instruction. - if (!MI->isSafeToMove(TII, AA, SawStore)) - return false; - - // FIXME: This should include support for sinking instructions within the - // block they are currently in to shorten the live ranges. We often get - // instructions sunk into the top of a large block, but it would be better to - // also sink them down before their first use in the block. This xform has to - // be careful not to *increase* register pressure though, e.g. sinking - // "x = y + z" down if it kills y and z would increase the live ranges of y - // and z and only shrink the live range of x. +/// FindSuccToSinkTo - Find a successor to sink this instruction to. +MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, + bool &BreakPHIEdge) { // Loop over all the operands of the specified instruction. If there is // anything we can't handle, bail out. @@ -429,7 +415,6 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // decide. MachineBasicBlock *SuccToSinkTo = 0; - bool BreakPHIEdge = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) continue; // Ignore non-register operands. @@ -443,23 +428,23 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // and we can freely move its uses. Alternatively, if it's allocatable, // it could get allocated to something with a def during allocation. if (!MRI->def_empty(Reg)) - return false; + return NULL; if (AllocatableSet.test(Reg)) - return false; + return NULL; // Check for a def among the register's aliases too. for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { unsigned AliasReg = *Alias; if (!MRI->def_empty(AliasReg)) - return false; + return NULL; if (AllocatableSet.test(AliasReg)) - return false; + return NULL; } } else if (!MO.isDead()) { // A def that isn't dead. We can't move it. - return false; + return NULL; } } else { // Virtual register uses are always safe to sink. @@ -467,7 +452,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // If it's not safe to move defs of the register class, then abort. if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) - return false; + return NULL; // FIXME: This picks a successor to sink into based on having one // successor that dominates all the uses. However, there are cases where @@ -490,7 +475,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { bool LocalUse = false; if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, BreakPHIEdge, LocalUse)) - return false; + return NULL; continue; } @@ -518,14 +503,39 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { } if (LocalUse) // Def is used locally, it's never safe to move this def. - return false; + return NULL; } // If we couldn't find a block to sink to, ignore this instruction. if (SuccToSinkTo == 0) - return false; + return NULL; } } + return SuccToSinkTo; +} + +/// SinkInstruction - Determine whether it is safe to sink the specified machine +/// instruction out of its current block into a successor. +bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { + // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to + // be close to the source to make it easier to coalesce. + if (AvoidsSinking(MI, MRI)) + return false; + + // Check if it's safe to move the instruction. + if (!MI->isSafeToMove(TII, AA, SawStore)) + return false; + + // FIXME: This should include support for sinking instructions within the + // block they are currently in to shorten the live ranges. We often get + // instructions sunk into the top of a large block, but it would be better to + // also sink them down before their first use in the block. This xform has to + // be careful not to *increase* register pressure though, e.g. sinking + // "x = y + z" down if it kills y and z would increase the live ranges of y + // and z and only shrink the live range of x. + + bool BreakPHIEdge = false; + MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, BreakPHIEdge); // If there are no outputs, it must have side-effects. if (SuccToSinkTo == 0) @@ -546,6 +556,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); + MachineBasicBlock *ParentBlock = MI->getParent(); + // If the block has multiple predecessors, this would introduce computation on // a path that it doesn't already exist. We could split the critical edge, // but for now we just punt. -- cgit v1.1 From 7f7f0902a640c26e9ce70b5869fc7de3b8b27918 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Thu, 8 Dec 2011 23:52:00 +0000 Subject: Revert r146184. I am seeing performance regression cause by this patch in one test case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146205 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 7740a75..dff8109 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -485,16 +485,6 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), E = ParentBlock->succ_end(); SI != E; ++SI) { MachineBasicBlock *SuccBlock = *SI; - // It is not possible to sink an instruction into its own block. This can - // happen with loops. - if (ParentBlock == SuccBlock) - continue; - - // It's not safe to sink instructions to EH landing pad. Control flow into - // landing pad is implicitly defined. - if (SuccBlock->isLandingPad()) - continue; - bool LocalUse = false; if (AllUsesDominatedByBlock(Reg, SuccBlock, ParentBlock, BreakPHIEdge, LocalUse)) { @@ -511,6 +501,17 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, return NULL; } } + + // It is not possible to sink an instruction into its own block. This can + // happen with loops. + if (ParentBlock == SuccToSinkTo) + return NULL; + + // It's not safe to sink instructions to EH landing pad. Control flow into + // landing pad is implicitly defined. + if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) + return NULL; + return SuccToSinkTo; } -- cgit v1.1 From 2b1d77355bdeb9b7515b16bdd049c39ed78fca4b Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Fri, 9 Dec 2011 01:18:48 +0000 Subject: Update stale comment. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146220 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index dff8109..c4a533b 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -152,10 +152,7 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, if (MRI->use_nodbg_empty(Reg)) return true; - // Ignoring debug uses is necessary so debug info doesn't affect the code. - // This may leave a referencing dbg_value in the original block, before - // the definition of the vreg. Dwarf generator handles this although the - // user might not get the right info at runtime. + // Ignoring debug uses because debug info doesn't affect the code. // BreakPHIEdge is true if all the uses are in the successor MBB being sunken // into and they are all PHI nodes. In this case, machine-sink must break -- cgit v1.1 From f5b9a74f0a13afe3b7a8388be81e4062b63e4c30 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Fri, 9 Dec 2011 01:25:04 +0000 Subject: Fix comment. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146226 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index c4a533b..3837f6d 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -149,11 +149,10 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Only makes sense for vregs"); + // Ignore debug uses because debug info doesn't affect the code. if (MRI->use_nodbg_empty(Reg)) return true; - // Ignoring debug uses because debug info doesn't affect the code. - // BreakPHIEdge is true if all the uses are in the successor MBB being sunken // into and they are all PHI nodes. In this case, machine-sink must break // the critical edge first. e.g. -- cgit v1.1 From 5211134fbd35bf0befc60888860010b23c27ee5a Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Wed, 14 Dec 2011 23:20:38 +0000 Subject: Do not sink instruction, if it is not profitable. On ARM, peephole optimization for ABS creates a trivial cfg triangle which tempts machine sink to sink instructions in code which is really straight line code. Sometimes this sinking may alter register allocator input such that use and def of a reg is divided by a branch in between, which may result in extra spills. Now mahine sink avoids sinking if final sink destination is post dominator. Radar 10266272. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146604 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 89 ++++++++++++++++++++++++++++++++++++++------- 1 file changed, 76 insertions(+), 13 deletions(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 3837f6d..e47360d 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -90,7 +90,11 @@ namespace { bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, bool &BreakPHIEdge, bool &LocalUse) const; - MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, bool &BreakPHIEdge); + MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, + bool &BreakPHIEdge); + bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, + MachineBasicBlock *MBB, + MachineBasicBlock *SuccToSinkTo); bool PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); @@ -399,18 +403,76 @@ static void collectDebugValues(MachineInstr *MI, } } +/// isPostDominatedBy - Return true if A is post dominated by B. +static bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) { + + // FIXME - Use real post dominator. + if (A->succ_size() != 2) + return false; + MachineBasicBlock::succ_iterator I = A->succ_begin(); + if (B == *I) + ++I; + MachineBasicBlock *OtherSuccBlock = *I; + if (OtherSuccBlock->succ_size() != 1 || + *(OtherSuccBlock->succ_begin()) != B) + return false; + + return true; +} + +/// isProfitableToSinkTo - Return true if it is profitable to sink MI. +bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, + MachineBasicBlock *MBB, + MachineBasicBlock *SuccToSinkTo) { + assert (MI && "Invalid MachineInstr!"); + assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); + + if (MBB == SuccToSinkTo) + return false; + + // It is profitable if SuccToSinkTo does not post dominate current block. + if (!isPostDominatedBy(MBB, SuccToSinkTo)) + return true; + + // Check if only use in post dominated block is PHI instruction. + bool NonPHIUse = false; + for (MachineRegisterInfo::use_nodbg_iterator + I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); + I != E; ++I) { + MachineInstr *UseInst = &*I; + MachineBasicBlock *UseBlock = UseInst->getParent(); + if (UseBlock == SuccToSinkTo && !UseInst->isPHI()) + NonPHIUse = true; + } + if (!NonPHIUse) + return true; + + // If SuccToSinkTo post dominates then also it may be profitable if MI + // can further profitably sinked into another block in next round. + bool BreakPHIEdge = false; + // FIXME - If finding successor is compile time expensive then catch results. + if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) + return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); + + // If SuccToSinkTo is final destination and it is a post dominator of current + // block then it is not profitable to sink MI into SuccToSinkTo block. + return false; +} + /// FindSuccToSinkTo - Find a successor to sink this instruction to. MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, - bool &BreakPHIEdge) { + MachineBasicBlock *MBB, + bool &BreakPHIEdge) { + + assert (MI && "Invalid MachineInstr!"); + assert (MBB && "Invalid MachineBasicBlock!"); // Loop over all the operands of the specified instruction. If there is // anything we can't handle, bail out. - MachineBasicBlock *ParentBlock = MI->getParent(); // SuccToSinkTo - This is the successor to sink this instruction to, once we // decide. MachineBasicBlock *SuccToSinkTo = 0; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) continue; // Ignore non-register operands. @@ -469,7 +531,7 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // If a previous operand picked a block to sink to, then this operand // must be sinkable to the same block. bool LocalUse = false; - if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, + if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge, LocalUse)) return NULL; @@ -478,11 +540,11 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // Otherwise, we should look at all the successors and decide which one // we should sink to. - for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), - E = ParentBlock->succ_end(); SI != E; ++SI) { - MachineBasicBlock *SuccBlock = *SI; + for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), + E = MBB->succ_end(); SI != E; ++SI) { + MachineBasicBlock *SuccBlock = *SI; bool LocalUse = false; - if (AllUsesDominatedByBlock(Reg, SuccBlock, ParentBlock, + if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, BreakPHIEdge, LocalUse)) { SuccToSinkTo = SuccBlock; break; @@ -495,12 +557,14 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // If we couldn't find a block to sink to, ignore this instruction. if (SuccToSinkTo == 0) return NULL; + else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) + return NULL; } } // It is not possible to sink an instruction into its own block. This can // happen with loops. - if (ParentBlock == SuccToSinkTo) + if (MBB == SuccToSinkTo) return NULL; // It's not safe to sink instructions to EH landing pad. Control flow into @@ -532,7 +596,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // and z and only shrink the live range of x. bool BreakPHIEdge = false; - MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, BreakPHIEdge); + MachineBasicBlock *ParentBlock = MI->getParent(); + MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); // If there are no outputs, it must have side-effects. if (SuccToSinkTo == 0) @@ -553,8 +618,6 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); - MachineBasicBlock *ParentBlock = MI->getParent(); - // If the block has multiple predecessors, this would introduce computation on // a path that it doesn't already exist. We could split the critical edge, // but for now we just punt. -- cgit v1.1