blob: 0e5c839c180169fafd03cfd946c033a90f077361 [file] [log] [blame]
Eugene Zelenko900b6332017-08-29 22:32:07 +00001//===- MachineSink.cpp - Sinking for machine instructions -----------------===//
Chris Lattnerf3edc092008-01-04 07:36:53 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
Bill Wendling7ee730e2010-06-02 23:04:26 +000010// This pass moves instructions into successor blocks when possible, so that
Dan Gohman5d79a2c2009-08-05 01:19:01 +000011// they aren't executed on paths where their results aren't needed.
12//
13// This pass is not intended to be a replacement or a complete alternative
14// for an LLVM-IR-level sinking pass. It is only designed to sink simple
15// constructs that are not exposed before lowering and instruction selection.
Chris Lattnerf3edc092008-01-04 07:36:53 +000016//
17//===----------------------------------------------------------------------===//
18
Quentin Colombet5cded892014-08-11 23:52:01 +000019#include "llvm/ADT/SetVector.h"
Evan Chenge53ab6d2010-09-17 22:28:18 +000020#include "llvm/ADT/SmallSet.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000021#include "llvm/ADT/SmallVector.h"
Matthias Braun352b89c2015-05-16 03:11:07 +000022#include "llvm/ADT/SparseBitVector.h"
Chris Lattnerf3edc092008-01-04 07:36:53 +000023#include "llvm/ADT/Statistic.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000024#include "llvm/Analysis/AliasAnalysis.h"
Eugene Zelenko1804a772016-08-25 00:45:04 +000025#include "llvm/CodeGen/MachineBasicBlock.h"
Bruno Cardoso Lopesd04f7592014-09-25 23:14:26 +000026#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
Dehao Chenf03f5152016-10-20 18:06:52 +000027#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000028#include "llvm/CodeGen/MachineDominators.h"
Eugene Zelenko1804a772016-08-25 00:45:04 +000029#include "llvm/CodeGen/MachineFunction.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineInstr.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000032#include "llvm/CodeGen/MachineLoopInfo.h"
Eugene Zelenko1804a772016-08-25 00:45:04 +000033#include "llvm/CodeGen/MachineOperand.h"
Jingyue Wu29542802014-10-15 03:27:43 +000034#include "llvm/CodeGen/MachinePostDominators.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000035#include "llvm/CodeGen/MachineRegisterInfo.h"
David Blaikie3f833ed2017-11-08 01:01:31 +000036#include "llvm/CodeGen/TargetInstrInfo.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000037#include "llvm/CodeGen/TargetRegisterInfo.h"
38#include "llvm/CodeGen/TargetSubtargetInfo.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000039#include "llvm/IR/BasicBlock.h"
Sanjoy Das16901a32016-01-20 00:06:14 +000040#include "llvm/IR/LLVMContext.h"
Paul Robinson8bd9d6a2017-12-09 00:17:01 +000041#include "llvm/IR/DebugInfoMetadata.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000042#include "llvm/Pass.h"
43#include "llvm/Support/BranchProbability.h"
Evan Chengae9939c2010-08-19 17:33:11 +000044#include "llvm/Support/CommandLine.h"
Chris Lattnerf3edc092008-01-04 07:36:53 +000045#include "llvm/Support/Debug.h"
Bill Wendling63aa0002009-08-22 20:26:23 +000046#include "llvm/Support/raw_ostream.h"
Eugene Zelenko1804a772016-08-25 00:45:04 +000047#include <algorithm>
48#include <cassert>
49#include <cstdint>
50#include <map>
51#include <utility>
52#include <vector>
53
Chris Lattnerf3edc092008-01-04 07:36:53 +000054using namespace llvm;
55
Chandler Carruth1b9dde02014-04-22 02:02:50 +000056#define DEBUG_TYPE "machine-sink"
57
Andrew Trick9e761992012-02-08 21:22:43 +000058static cl::opt<bool>
Evan Chengae9939c2010-08-19 17:33:11 +000059SplitEdges("machine-sink-split",
60 cl::desc("Split critical edges during machine sinking"),
Evan Chengf3e9a482010-09-20 22:52:00 +000061 cl::init(true), cl::Hidden);
Evan Chengae9939c2010-08-19 17:33:11 +000062
Bruno Cardoso Lopesd04f7592014-09-25 23:14:26 +000063static cl::opt<bool>
64UseBlockFreqInfo("machine-sink-bfi",
65 cl::desc("Use block frequency info to find successors to sink"),
66 cl::init(true), cl::Hidden);
67
Dehao Chenf03f5152016-10-20 18:06:52 +000068static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
69 "machine-sink-split-probability-threshold",
70 cl::desc(
71 "Percentage threshold for splitting single-instruction critical edge. "
72 "If the branch threshold is higher than this threshold, we allow "
73 "speculative execution of up to 1 instruction to avoid branching to "
74 "splitted critical edge"),
75 cl::init(40), cl::Hidden);
76
Evan Chenge53ab6d2010-09-17 22:28:18 +000077STATISTIC(NumSunk, "Number of machine instructions sunk");
78STATISTIC(NumSplit, "Number of critical edges split");
79STATISTIC(NumCoalesces, "Number of copies coalesced");
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +000080STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
Chris Lattnerf3edc092008-01-04 07:36:53 +000081
82namespace {
Eugene Zelenko1804a772016-08-25 00:45:04 +000083
Nick Lewycky02d5f772009-10-25 06:33:48 +000084 class MachineSinking : public MachineFunctionPass {
Chris Lattnerf3edc092008-01-04 07:36:53 +000085 const TargetInstrInfo *TII;
Dan Gohmana3176872009-09-25 22:53:29 +000086 const TargetRegisterInfo *TRI;
Jingyue Wu29542802014-10-15 03:27:43 +000087 MachineRegisterInfo *MRI; // Machine register information
88 MachineDominatorTree *DT; // Machine dominator tree
89 MachinePostDominatorTree *PDT; // Machine post dominator tree
Jakob Stoklund Olesencdc3df42010-04-15 23:41:02 +000090 MachineLoopInfo *LI;
Bruno Cardoso Lopesd04f7592014-09-25 23:14:26 +000091 const MachineBlockFrequencyInfo *MBFI;
Dehao Chenf03f5152016-10-20 18:06:52 +000092 const MachineBranchProbabilityInfo *MBPI;
Dan Gohman87b02d52009-10-09 23:27:56 +000093 AliasAnalysis *AA;
Chris Lattnerf3edc092008-01-04 07:36:53 +000094
Evan Chenge53ab6d2010-09-17 22:28:18 +000095 // Remember which edges have been considered for breaking.
Eugene Zelenko1804a772016-08-25 00:45:04 +000096 SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
Evan Chenge53ab6d2010-09-17 22:28:18 +000097 CEBCandidates;
Quentin Colombet5cded892014-08-11 23:52:01 +000098 // Remember which edges we are about to split.
99 // This is different from CEBCandidates since those edges
100 // will be split.
Eugene Zelenko900b6332017-08-29 22:32:07 +0000101 SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
Evan Chenge53ab6d2010-09-17 22:28:18 +0000102
Matthias Braun352b89c2015-05-16 03:11:07 +0000103 SparseBitVector<> RegsToClearKillFlags;
104
Eugene Zelenko900b6332017-08-29 22:32:07 +0000105 using AllSuccsCache =
106 std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
Arnaud A. de Grandmaisond8673ed2015-06-15 09:09:06 +0000107
Chris Lattnerf3edc092008-01-04 07:36:53 +0000108 public:
109 static char ID; // Pass identification
Eugene Zelenko1804a772016-08-25 00:45:04 +0000110
Owen Anderson6c18d1a2010-10-19 17:21:58 +0000111 MachineSinking() : MachineFunctionPass(ID) {
112 initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
113 }
Jim Grosbach01edd682010-06-03 23:49:57 +0000114
Craig Topper4584cd52014-03-07 09:26:03 +0000115 bool runOnMachineFunction(MachineFunction &MF) override;
Jim Grosbach01edd682010-06-03 23:49:57 +0000116
Craig Topper4584cd52014-03-07 09:26:03 +0000117 void getAnalysisUsage(AnalysisUsage &AU) const override {
Dan Gohman04023152009-07-31 23:37:33 +0000118 AU.setPreservesCFG();
Chris Lattnerf3edc092008-01-04 07:36:53 +0000119 MachineFunctionPass::getAnalysisUsage(AU);
Chandler Carruth7b560d42015-09-09 17:55:00 +0000120 AU.addRequired<AAResultsWrapperPass>();
Chris Lattnerf3edc092008-01-04 07:36:53 +0000121 AU.addRequired<MachineDominatorTree>();
Jingyue Wu29542802014-10-15 03:27:43 +0000122 AU.addRequired<MachinePostDominatorTree>();
Jakob Stoklund Olesencdc3df42010-04-15 23:41:02 +0000123 AU.addRequired<MachineLoopInfo>();
Dehao Chenf03f5152016-10-20 18:06:52 +0000124 AU.addRequired<MachineBranchProbabilityInfo>();
Chris Lattnerf3edc092008-01-04 07:36:53 +0000125 AU.addPreserved<MachineDominatorTree>();
Jingyue Wu29542802014-10-15 03:27:43 +0000126 AU.addPreserved<MachinePostDominatorTree>();
Jakob Stoklund Olesencdc3df42010-04-15 23:41:02 +0000127 AU.addPreserved<MachineLoopInfo>();
Bruno Cardoso Lopesd04f7592014-09-25 23:14:26 +0000128 if (UseBlockFreqInfo)
129 AU.addRequired<MachineBlockFrequencyInfo>();
Chris Lattnerf3edc092008-01-04 07:36:53 +0000130 }
Evan Chenge53ab6d2010-09-17 22:28:18 +0000131
Craig Topper4584cd52014-03-07 09:26:03 +0000132 void releaseMemory() override {
Evan Chenge53ab6d2010-09-17 22:28:18 +0000133 CEBCandidates.clear();
134 }
135
Chris Lattnerf3edc092008-01-04 07:36:53 +0000136 private:
137 bool ProcessBlock(MachineBasicBlock &MBB);
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000138 bool isWorthBreakingCriticalEdge(MachineInstr &MI,
Evan Chenge53ab6d2010-09-17 22:28:18 +0000139 MachineBasicBlock *From,
140 MachineBasicBlock *To);
Eugene Zelenko900b6332017-08-29 22:32:07 +0000141
Adrian Prantl5f8f34e42018-05-01 15:54:18 +0000142 /// Postpone the splitting of the given critical
Quentin Colombet5cded892014-08-11 23:52:01 +0000143 /// edge (\p From, \p To).
144 ///
145 /// We do not split the edges on the fly. Indeed, this invalidates
146 /// the dominance information and thus triggers a lot of updates
147 /// of that information underneath.
148 /// Instead, we postpone all the splits after each iteration of
149 /// the main loop. That way, the information is at least valid
150 /// for the lifetime of an iteration.
151 ///
152 /// \return True if the edge is marked as toSplit, false otherwise.
Patrik Hagglundd06de4b2014-12-04 10:36:42 +0000153 /// False can be returned if, for instance, this is not profitable.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000154 bool PostponeSplitCriticalEdge(MachineInstr &MI,
Quentin Colombet5cded892014-08-11 23:52:01 +0000155 MachineBasicBlock *From,
156 MachineBasicBlock *To,
157 bool BreakPHIEdge);
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000158 bool SinkInstruction(MachineInstr &MI, bool &SawStore,
Eugene Zelenko900b6332017-08-29 22:32:07 +0000159
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000160 AllSuccsCache &AllSuccessors);
Evan Cheng25b60682010-08-18 23:09:25 +0000161 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
Evan Chenge53ab6d2010-09-17 22:28:18 +0000162 MachineBasicBlock *DefMBB,
Evan Cheng2031b762010-09-20 19:12:55 +0000163 bool &BreakPHIEdge, bool &LocalUse) const;
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000164 MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000165 bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000166 bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
Devang Patelc2686882011-12-14 23:20:38 +0000167 MachineBasicBlock *MBB,
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000168 MachineBasicBlock *SuccToSinkTo,
169 AllSuccsCache &AllSuccessors);
Devang Patelb94c9a42011-12-08 21:48:01 +0000170
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000171 bool PerformTrivialForwardCoalescing(MachineInstr &MI,
Evan Chenge53ab6d2010-09-17 22:28:18 +0000172 MachineBasicBlock *MBB);
Arnaud A. de Grandmaisond8673ed2015-06-15 09:09:06 +0000173
174 SmallVector<MachineBasicBlock *, 4> &
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000175 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000176 AllSuccsCache &AllSuccessors) const;
Chris Lattnerf3edc092008-01-04 07:36:53 +0000177 };
Eugene Zelenko1804a772016-08-25 00:45:04 +0000178
Chris Lattnerf3edc092008-01-04 07:36:53 +0000179} // end anonymous namespace
Jim Grosbach01edd682010-06-03 23:49:57 +0000180
Dan Gohmand78c4002008-05-13 00:00:25 +0000181char MachineSinking::ID = 0;
Eugene Zelenko900b6332017-08-29 22:32:07 +0000182
Andrew Trick1fa5bcb2012-02-08 21:23:13 +0000183char &llvm::MachineSinkingID = MachineSinking::ID;
Eugene Zelenko900b6332017-08-29 22:32:07 +0000184
Matthias Braun1527baa2017-05-25 21:26:32 +0000185INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
186 "Machine code sinking", false, false)
Dehao Chenf03f5152016-10-20 18:06:52 +0000187INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
Owen Anderson8ac477f2010-10-12 19:48:12 +0000188INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
189INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
Chandler Carruth7b560d42015-09-09 17:55:00 +0000190INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
Matthias Braun1527baa2017-05-25 21:26:32 +0000191INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
192 "Machine code sinking", false, false)
Chris Lattnerf3edc092008-01-04 07:36:53 +0000193
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000194bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
Evan Chenge53ab6d2010-09-17 22:28:18 +0000195 MachineBasicBlock *MBB) {
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000196 if (!MI.isCopy())
Evan Chenge53ab6d2010-09-17 22:28:18 +0000197 return false;
198
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000199 unsigned SrcReg = MI.getOperand(1).getReg();
200 unsigned DstReg = MI.getOperand(0).getReg();
Evan Chenge53ab6d2010-09-17 22:28:18 +0000201 if (!TargetRegisterInfo::isVirtualRegister(SrcReg) ||
202 !TargetRegisterInfo::isVirtualRegister(DstReg) ||
203 !MRI->hasOneNonDBGUse(SrcReg))
204 return false;
205
206 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
207 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
208 if (SRC != DRC)
209 return false;
210
211 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
212 if (DefMI->isCopyLike())
213 return false;
214 DEBUG(dbgs() << "Coalescing: " << *DefMI);
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000215 DEBUG(dbgs() << "*** to: " << MI);
Evan Chenge53ab6d2010-09-17 22:28:18 +0000216 MRI->replaceRegWith(DstReg, SrcReg);
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000217 MI.eraseFromParent();
Patrik Hagglund57d315b2014-09-09 07:47:00 +0000218
219 // Conservatively, clear any kill flags, since it's possible that they are no
220 // longer correct.
221 MRI->clearKillFlags(SrcReg);
222
Evan Chenge53ab6d2010-09-17 22:28:18 +0000223 ++NumCoalesces;
224 return true;
225}
226
Chris Lattnerf3edc092008-01-04 07:36:53 +0000227/// AllUsesDominatedByBlock - Return true if all uses of the specified register
Evan Cheng25b60682010-08-18 23:09:25 +0000228/// occur in blocks dominated by the specified block. If any use is in the
229/// definition block, then return false since it is never legal to move def
230/// after uses.
Evan Chenge53ab6d2010-09-17 22:28:18 +0000231bool
232MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
233 MachineBasicBlock *MBB,
234 MachineBasicBlock *DefMBB,
Evan Cheng2031b762010-09-20 19:12:55 +0000235 bool &BreakPHIEdge,
236 bool &LocalUse) const {
Dan Gohman3a4be0f2008-02-10 18:45:23 +0000237 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
238 "Only makes sense for vregs");
Evan Chengb339f3d2010-09-18 06:42:17 +0000239
Devang Patel706574a2011-12-09 01:25:04 +0000240 // Ignore debug uses because debug info doesn't affect the code.
Evan Chengb339f3d2010-09-18 06:42:17 +0000241 if (MRI->use_nodbg_empty(Reg))
242 return true;
243
Evan Cheng2031b762010-09-20 19:12:55 +0000244 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
245 // into and they are all PHI nodes. In this case, machine-sink must break
246 // the critical edge first. e.g.
247 //
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000248 // %bb.1: derived from LLVM BB %bb4.preheader
249 // Predecessors according to CFG: %bb.0
Evan Chengb339f3d2010-09-18 06:42:17 +0000250 // ...
Francis Visoiu Mistriha8a83d12017-12-07 10:40:31 +0000251 // %reg16385 = DEC64_32r %reg16437, implicit-def dead %eflags
Evan Chengb339f3d2010-09-18 06:42:17 +0000252 // ...
Francis Visoiu Mistriha8a83d12017-12-07 10:40:31 +0000253 // JE_4 <%bb.37>, implicit %eflags
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000254 // Successors according to CFG: %bb.37 %bb.2
Evan Chengb339f3d2010-09-18 06:42:17 +0000255 //
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000256 // %bb.2: derived from LLVM BB %bb.nph
257 // Predecessors according to CFG: %bb.0 %bb.1
Francis Visoiu Mistriha8a83d12017-12-07 10:40:31 +0000258 // %reg16386 = PHI %reg16434, %bb.0, %reg16385, %bb.1
Evan Cheng2031b762010-09-20 19:12:55 +0000259 BreakPHIEdge = true;
Owen Andersonb36376e2014-03-17 19:36:09 +0000260 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
261 MachineInstr *UseInst = MO.getParent();
262 unsigned OpNo = &MO - &UseInst->getOperand(0);
Evan Chengb339f3d2010-09-18 06:42:17 +0000263 MachineBasicBlock *UseBlock = UseInst->getParent();
264 if (!(UseBlock == MBB && UseInst->isPHI() &&
Owen Andersonb36376e2014-03-17 19:36:09 +0000265 UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
Evan Cheng2031b762010-09-20 19:12:55 +0000266 BreakPHIEdge = false;
Evan Chengb339f3d2010-09-18 06:42:17 +0000267 break;
268 }
269 }
Evan Cheng2031b762010-09-20 19:12:55 +0000270 if (BreakPHIEdge)
Evan Chengb339f3d2010-09-18 06:42:17 +0000271 return true;
272
Owen Andersonb36376e2014-03-17 19:36:09 +0000273 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
Chris Lattnerf3edc092008-01-04 07:36:53 +0000274 // Determine the block of the use.
Owen Andersonb36376e2014-03-17 19:36:09 +0000275 MachineInstr *UseInst = MO.getParent();
276 unsigned OpNo = &MO - &UseInst->getOperand(0);
Chris Lattnerf3edc092008-01-04 07:36:53 +0000277 MachineBasicBlock *UseBlock = UseInst->getParent();
Evan Chengb339f3d2010-09-18 06:42:17 +0000278 if (UseInst->isPHI()) {
Chris Lattnerf3edc092008-01-04 07:36:53 +0000279 // PHI nodes use the operand in the predecessor block, not the block with
280 // the PHI.
Owen Andersonb36376e2014-03-17 19:36:09 +0000281 UseBlock = UseInst->getOperand(OpNo+1).getMBB();
Evan Cheng361b9be2010-08-19 18:33:29 +0000282 } else if (UseBlock == DefMBB) {
283 LocalUse = true;
284 return false;
Chris Lattnerf3edc092008-01-04 07:36:53 +0000285 }
Bill Wendling7ee730e2010-06-02 23:04:26 +0000286
Chris Lattnerf3edc092008-01-04 07:36:53 +0000287 // Check that it dominates.
288 if (!DT->dominates(MBB, UseBlock))
289 return false;
290 }
Bill Wendling7ee730e2010-06-02 23:04:26 +0000291
Chris Lattnerf3edc092008-01-04 07:36:53 +0000292 return true;
293}
294
Chris Lattnerf3edc092008-01-04 07:36:53 +0000295bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
Matthias Braunf1caa282017-12-15 22:22:58 +0000296 if (skipFunction(MF.getFunction()))
Paul Robinson7c99ec52014-03-31 17:43:35 +0000297 return false;
298
David Greene4b7aa242010-01-05 01:26:00 +0000299 DEBUG(dbgs() << "******** Machine Sinking ********\n");
Jim Grosbach01edd682010-06-03 23:49:57 +0000300
Eric Christophereb9e87f2014-10-14 07:00:33 +0000301 TII = MF.getSubtarget().getInstrInfo();
302 TRI = MF.getSubtarget().getRegisterInfo();
Evan Chenge53ab6d2010-09-17 22:28:18 +0000303 MRI = &MF.getRegInfo();
Chris Lattnerf3edc092008-01-04 07:36:53 +0000304 DT = &getAnalysis<MachineDominatorTree>();
Jingyue Wu29542802014-10-15 03:27:43 +0000305 PDT = &getAnalysis<MachinePostDominatorTree>();
Jakob Stoklund Olesencdc3df42010-04-15 23:41:02 +0000306 LI = &getAnalysis<MachineLoopInfo>();
Bruno Cardoso Lopesd04f7592014-09-25 23:14:26 +0000307 MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
Dehao Chenf03f5152016-10-20 18:06:52 +0000308 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000309 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Chris Lattnerf3edc092008-01-04 07:36:53 +0000310
311 bool EverMadeChange = false;
Jim Grosbach01edd682010-06-03 23:49:57 +0000312
Eugene Zelenko1804a772016-08-25 00:45:04 +0000313 while (true) {
Chris Lattnerf3edc092008-01-04 07:36:53 +0000314 bool MadeChange = false;
315
316 // Process all basic blocks.
Evan Chenge53ab6d2010-09-17 22:28:18 +0000317 CEBCandidates.clear();
Quentin Colombet5cded892014-08-11 23:52:01 +0000318 ToSplit.clear();
Arnaud A. de Grandmaisond8673ed2015-06-15 09:09:06 +0000319 for (auto &MBB: MF)
320 MadeChange |= ProcessBlock(MBB);
Jim Grosbach01edd682010-06-03 23:49:57 +0000321
Quentin Colombet5cded892014-08-11 23:52:01 +0000322 // If we have anything we marked as toSplit, split it now.
323 for (auto &Pair : ToSplit) {
Quentin Colombet23341a82016-04-21 21:01:13 +0000324 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
Quentin Colombet5cded892014-08-11 23:52:01 +0000325 if (NewSucc != nullptr) {
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000326 DEBUG(dbgs() << " *** Splitting critical edge: "
327 << printMBBReference(*Pair.first) << " -- "
328 << printMBBReference(*NewSucc) << " -- "
329 << printMBBReference(*Pair.second) << '\n');
Quentin Colombet5cded892014-08-11 23:52:01 +0000330 MadeChange = true;
331 ++NumSplit;
332 } else
333 DEBUG(dbgs() << " *** Not legal to break critical edge\n");
334 }
Chris Lattnerf3edc092008-01-04 07:36:53 +0000335 // If this iteration over the code changed anything, keep iterating.
336 if (!MadeChange) break;
337 EverMadeChange = true;
Jim Grosbach01edd682010-06-03 23:49:57 +0000338 }
Matthias Braun352b89c2015-05-16 03:11:07 +0000339
340 // Now clear any kill flags for recorded registers.
341 for (auto I : RegsToClearKillFlags)
342 MRI->clearKillFlags(I);
343 RegsToClearKillFlags.clear();
344
Chris Lattnerf3edc092008-01-04 07:36:53 +0000345 return EverMadeChange;
346}
347
348bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
Chris Lattnerf3edc092008-01-04 07:36:53 +0000349 // Can't sink anything out of a block that has less than two successors.
Chris Lattner30c3de62009-04-10 16:38:36 +0000350 if (MBB.succ_size() <= 1 || MBB.empty()) return false;
351
Dan Gohman918a90a2010-04-05 19:17:22 +0000352 // Don't bother sinking code out of unreachable blocks. In addition to being
Jim Grosbach01edd682010-06-03 23:49:57 +0000353 // unprofitable, it can also lead to infinite looping, because in an
354 // unreachable loop there may be nowhere to stop.
Dan Gohman918a90a2010-04-05 19:17:22 +0000355 if (!DT->isReachableFromEntry(&MBB)) return false;
356
Chris Lattner30c3de62009-04-10 16:38:36 +0000357 bool MadeChange = false;
358
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000359 // Cache all successors, sorted by frequency info and loop depth.
360 AllSuccsCache AllSuccessors;
Arnaud A. de Grandmaisond8673ed2015-06-15 09:09:06 +0000361
Chris Lattner08af5a92008-01-12 00:17:41 +0000362 // Walk the basic block bottom-up. Remember if we saw a store.
Chris Lattner30c3de62009-04-10 16:38:36 +0000363 MachineBasicBlock::iterator I = MBB.end();
364 --I;
365 bool ProcessedBegin, SawStore = false;
366 do {
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000367 MachineInstr &MI = *I; // The instruction to sink.
Jim Grosbach01edd682010-06-03 23:49:57 +0000368
Chris Lattner30c3de62009-04-10 16:38:36 +0000369 // Predecrement I (if it's not begin) so that it isn't invalidated by
370 // sinking.
371 ProcessedBegin = I == MBB.begin();
372 if (!ProcessedBegin)
373 --I;
Dale Johannesen2061c842010-03-05 00:02:59 +0000374
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000375 if (MI.isDebugValue())
Dale Johannesen2061c842010-03-05 00:02:59 +0000376 continue;
377
Evan Chengfe917ef2011-04-11 18:47:20 +0000378 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
379 if (Joined) {
380 MadeChange = true;
Evan Chenge53ab6d2010-09-17 22:28:18 +0000381 continue;
Evan Chengfe917ef2011-04-11 18:47:20 +0000382 }
Evan Chenge53ab6d2010-09-17 22:28:18 +0000383
Richard Trieu7a083812016-02-18 22:09:30 +0000384 if (SinkInstruction(MI, SawStore, AllSuccessors)) {
385 ++NumSunk;
386 MadeChange = true;
387 }
Jim Grosbach01edd682010-06-03 23:49:57 +0000388
Chris Lattner30c3de62009-04-10 16:38:36 +0000389 // If we just processed the first instruction in the block, we're done.
390 } while (!ProcessedBegin);
Jim Grosbach01edd682010-06-03 23:49:57 +0000391
Chris Lattnerf3edc092008-01-04 07:36:53 +0000392 return MadeChange;
393}
394
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000395bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
Evan Chenge53ab6d2010-09-17 22:28:18 +0000396 MachineBasicBlock *From,
397 MachineBasicBlock *To) {
398 // FIXME: Need much better heuristics.
399
400 // If the pass has already considered breaking this edge (during this pass
401 // through the function), then let's go ahead and break it. This means
402 // sinking multiple "cheap" instructions into the same block.
David Blaikie70573dc2014-11-19 07:49:26 +0000403 if (!CEBCandidates.insert(std::make_pair(From, To)).second)
Evan Chenge53ab6d2010-09-17 22:28:18 +0000404 return true;
405
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000406 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
Evan Chenge53ab6d2010-09-17 22:28:18 +0000407 return true;
408
Dehao Chenf03f5152016-10-20 18:06:52 +0000409 if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
410 BranchProbability(SplitEdgeProbabilityThreshold, 100))
411 return true;
412
Evan Chenge53ab6d2010-09-17 22:28:18 +0000413 // MI is cheap, we probably don't want to break the critical edge for it.
414 // However, if this would allow some definitions of its source operands
415 // to be sunk then it's probably worth it.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000416 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
417 const MachineOperand &MO = MI.getOperand(i);
Will Dietz5cb7f4e2013-10-14 16:57:17 +0000418 if (!MO.isReg() || !MO.isUse())
Evan Chenge53ab6d2010-09-17 22:28:18 +0000419 continue;
Will Dietz5cb7f4e2013-10-14 16:57:17 +0000420 unsigned Reg = MO.getReg();
421 if (Reg == 0)
422 continue;
423
424 // We don't move live definitions of physical registers,
425 // so sinking their uses won't enable any opportunities.
426 if (TargetRegisterInfo::isPhysicalRegister(Reg))
427 continue;
428
429 // If this instruction is the only user of a virtual register,
430 // check if breaking the edge will enable sinking
431 // both this instruction and the defining instruction.
432 if (MRI->hasOneNonDBGUse(Reg)) {
433 // If the definition resides in same MBB,
434 // claim it's likely we can sink these together.
435 // If definition resides elsewhere, we aren't
436 // blocking it from being sunk so don't break the edge.
437 MachineInstr *DefMI = MRI->getVRegDef(Reg);
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000438 if (DefMI->getParent() == MI.getParent())
Will Dietz5cb7f4e2013-10-14 16:57:17 +0000439 return true;
440 }
Evan Chenge53ab6d2010-09-17 22:28:18 +0000441 }
442
443 return false;
444}
445
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000446bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
Quentin Colombet5cded892014-08-11 23:52:01 +0000447 MachineBasicBlock *FromBB,
448 MachineBasicBlock *ToBB,
449 bool BreakPHIEdge) {
Evan Chenge53ab6d2010-09-17 22:28:18 +0000450 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
Quentin Colombet5cded892014-08-11 23:52:01 +0000451 return false;
Evan Chenge53ab6d2010-09-17 22:28:18 +0000452
Evan Chengae9939c2010-08-19 17:33:11 +0000453 // Avoid breaking back edge. From == To means backedge for single BB loop.
Evan Chengf3e9a482010-09-20 22:52:00 +0000454 if (!SplitEdges || FromBB == ToBB)
Quentin Colombet5cded892014-08-11 23:52:01 +0000455 return false;
Evan Chengae9939c2010-08-19 17:33:11 +0000456
Evan Chenge53ab6d2010-09-17 22:28:18 +0000457 // Check for backedges of more "complex" loops.
458 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
459 LI->isLoopHeader(ToBB))
Quentin Colombet5cded892014-08-11 23:52:01 +0000460 return false;
Evan Chenge53ab6d2010-09-17 22:28:18 +0000461
462 // It's not always legal to break critical edges and sink the computation
463 // to the edge.
464 //
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000465 // %bb.1:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000466 // v1024
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000467 // Beq %bb.3
Evan Chenge53ab6d2010-09-17 22:28:18 +0000468 // <fallthrough>
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000469 // %bb.2:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000470 // ... no uses of v1024
471 // <fallthrough>
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000472 // %bb.3:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000473 // ...
474 // = v1024
475 //
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000476 // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000477 //
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000478 // %bb.1:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000479 // ...
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000480 // Bne %bb.2
481 // %bb.4:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000482 // v1024 =
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000483 // B %bb.3
484 // %bb.2:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000485 // ... no uses of v1024
486 // <fallthrough>
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000487 // %bb.3:
Evan Chenge53ab6d2010-09-17 22:28:18 +0000488 // ...
489 // = v1024
490 //
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000491 // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
Evan Chenge53ab6d2010-09-17 22:28:18 +0000492 // flow. We need to ensure the new basic block where the computation is
493 // sunk to dominates all the uses.
494 // It's only legal to break critical edge and sink the computation to the
495 // new block if all the predecessors of "To", except for "From", are
496 // not dominated by "From". Given SSA property, this means these
497 // predecessors are dominated by "To".
498 //
499 // There is no need to do this check if all the uses are PHI nodes. PHI
500 // sources are only defined on the specific predecessor edges.
Evan Cheng2031b762010-09-20 19:12:55 +0000501 if (!BreakPHIEdge) {
Evan Chengae9939c2010-08-19 17:33:11 +0000502 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
503 E = ToBB->pred_end(); PI != E; ++PI) {
504 if (*PI == FromBB)
505 continue;
506 if (!DT->dominates(ToBB, *PI))
Quentin Colombet5cded892014-08-11 23:52:01 +0000507 return false;
Evan Chengae9939c2010-08-19 17:33:11 +0000508 }
Evan Chengae9939c2010-08-19 17:33:11 +0000509 }
510
Quentin Colombet5cded892014-08-11 23:52:01 +0000511 ToSplit.insert(std::make_pair(FromBB, ToBB));
512
513 return true;
Evan Chengae9939c2010-08-19 17:33:11 +0000514}
515
Andrew Trick9e761992012-02-08 21:22:43 +0000516/// collectDebgValues - Scan instructions following MI and collect any
Devang Patel9de7a7d2011-09-07 00:07:58 +0000517/// matching DBG_VALUEs.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000518static void collectDebugValues(MachineInstr &MI,
Craig Topperb94011f2013-07-14 04:42:23 +0000519 SmallVectorImpl<MachineInstr *> &DbgValues) {
Devang Patel9de7a7d2011-09-07 00:07:58 +0000520 DbgValues.clear();
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000521 if (!MI.getOperand(0).isReg())
Devang Patel9de7a7d2011-09-07 00:07:58 +0000522 return;
523
524 MachineBasicBlock::iterator DI = MI; ++DI;
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000525 for (MachineBasicBlock::iterator DE = MI.getParent()->end();
Devang Patel9de7a7d2011-09-07 00:07:58 +0000526 DI != DE; ++DI) {
527 if (!DI->isDebugValue())
528 return;
529 if (DI->getOperand(0).isReg() &&
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000530 DI->getOperand(0).getReg() == MI.getOperand(0).getReg())
531 DbgValues.push_back(&*DI);
Devang Patel9de7a7d2011-09-07 00:07:58 +0000532 }
533}
534
Devang Patelc2686882011-12-14 23:20:38 +0000535/// isProfitableToSinkTo - Return true if it is profitable to sink MI.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000536bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
Devang Patelc2686882011-12-14 23:20:38 +0000537 MachineBasicBlock *MBB,
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000538 MachineBasicBlock *SuccToSinkTo,
539 AllSuccsCache &AllSuccessors) {
Devang Patelc2686882011-12-14 23:20:38 +0000540 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
541
542 if (MBB == SuccToSinkTo)
543 return false;
544
545 // It is profitable if SuccToSinkTo does not post dominate current block.
Jingyue Wu29542802014-10-15 03:27:43 +0000546 if (!PDT->dominates(SuccToSinkTo, MBB))
547 return true;
548
549 // It is profitable to sink an instruction from a deeper loop to a shallower
550 // loop, even if the latter post-dominates the former (PR21115).
551 if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
552 return true;
Devang Patelc2686882011-12-14 23:20:38 +0000553
554 // Check if only use in post dominated block is PHI instruction.
555 bool NonPHIUse = false;
Owen Andersonb36376e2014-03-17 19:36:09 +0000556 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
557 MachineBasicBlock *UseBlock = UseInst.getParent();
558 if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
Devang Patelc2686882011-12-14 23:20:38 +0000559 NonPHIUse = true;
560 }
561 if (!NonPHIUse)
562 return true;
563
564 // If SuccToSinkTo post dominates then also it may be profitable if MI
565 // can further profitably sinked into another block in next round.
566 bool BreakPHIEdge = false;
Patrik Hagglundd06de4b2014-12-04 10:36:42 +0000567 // FIXME - If finding successor is compile time expensive then cache results.
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000568 if (MachineBasicBlock *MBB2 =
569 FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
570 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
Devang Patelc2686882011-12-14 23:20:38 +0000571
572 // If SuccToSinkTo is final destination and it is a post dominator of current
573 // block then it is not profitable to sink MI into SuccToSinkTo block.
574 return false;
575}
576
Arnaud A. de Grandmaisond8673ed2015-06-15 09:09:06 +0000577/// Get the sorted sequence of successors for this MachineBasicBlock, possibly
578/// computing it if it was not already cached.
579SmallVector<MachineBasicBlock *, 4> &
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000580MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000581 AllSuccsCache &AllSuccessors) const {
Arnaud A. de Grandmaisond8673ed2015-06-15 09:09:06 +0000582 // Do we have the sorted successors in cache ?
583 auto Succs = AllSuccessors.find(MBB);
584 if (Succs != AllSuccessors.end())
585 return Succs->second;
586
587 SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(),
588 MBB->succ_end());
589
590 // Handle cases where sinking can happen but where the sink point isn't a
591 // successor. For example:
592 //
593 // x = computation
594 // if () {} else {}
595 // use x
596 //
597 const std::vector<MachineDomTreeNode *> &Children =
598 DT->getNode(MBB)->getChildren();
599 for (const auto &DTChild : Children)
600 // DomTree children of MBB that have MBB as immediate dominator are added.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000601 if (DTChild->getIDom()->getBlock() == MI.getParent() &&
Arnaud A. de Grandmaisond8673ed2015-06-15 09:09:06 +0000602 // Skip MBBs already added to the AllSuccs vector above.
603 !MBB->isSuccessor(DTChild->getBlock()))
604 AllSuccs.push_back(DTChild->getBlock());
605
606 // Sort Successors according to their loop depth or block frequency info.
607 std::stable_sort(
608 AllSuccs.begin(), AllSuccs.end(),
609 [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
610 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
611 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
612 bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
613 return HasBlockFreq ? LHSFreq < RHSFreq
614 : LI->getLoopDepth(L) < LI->getLoopDepth(R);
615 });
616
617 auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
618
619 return it.first->second;
620}
621
Devang Patelb94c9a42011-12-08 21:48:01 +0000622/// FindSuccToSinkTo - Find a successor to sink this instruction to.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000623MachineBasicBlock *
624MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
625 bool &BreakPHIEdge,
626 AllSuccsCache &AllSuccessors) {
Devang Patelc2686882011-12-14 23:20:38 +0000627 assert (MBB && "Invalid MachineBasicBlock!");
Jim Grosbach01edd682010-06-03 23:49:57 +0000628
Chris Lattnerf3edc092008-01-04 07:36:53 +0000629 // Loop over all the operands of the specified instruction. If there is
630 // anything we can't handle, bail out.
Jim Grosbach01edd682010-06-03 23:49:57 +0000631
Chris Lattnerf3edc092008-01-04 07:36:53 +0000632 // SuccToSinkTo - This is the successor to sink this instruction to, once we
633 // decide.
Craig Topperc0196b12014-04-14 00:51:57 +0000634 MachineBasicBlock *SuccToSinkTo = nullptr;
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000635 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
636 const MachineOperand &MO = MI.getOperand(i);
Dan Gohman0d1e9a82008-10-03 15:45:36 +0000637 if (!MO.isReg()) continue; // Ignore non-register operands.
Jim Grosbach01edd682010-06-03 23:49:57 +0000638
Chris Lattnerf3edc092008-01-04 07:36:53 +0000639 unsigned Reg = MO.getReg();
640 if (Reg == 0) continue;
Jim Grosbach01edd682010-06-03 23:49:57 +0000641
Dan Gohman3a4be0f2008-02-10 18:45:23 +0000642 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
Dan Gohmana3176872009-09-25 22:53:29 +0000643 if (MO.isUse()) {
644 // If the physreg has no defs anywhere, it's just an ambient register
Dan Gohman2f5bdcb2009-09-26 02:34:00 +0000645 // and we can freely move its uses. Alternatively, if it's allocatable,
646 // it could get allocated to something with a def during allocation.
Matthias Braunde8c1b32016-10-28 18:05:09 +0000647 if (!MRI->isConstantPhysReg(Reg))
Craig Topperc0196b12014-04-14 00:51:57 +0000648 return nullptr;
Bill Wendlinge41e40f2010-06-25 20:48:10 +0000649 } else if (!MO.isDead()) {
650 // A def that isn't dead. We can't move it.
Craig Topperc0196b12014-04-14 00:51:57 +0000651 return nullptr;
Dan Gohmana3176872009-09-25 22:53:29 +0000652 }
Chris Lattnerf3edc092008-01-04 07:36:53 +0000653 } else {
654 // Virtual register uses are always safe to sink.
655 if (MO.isUse()) continue;
Evan Cheng47a65a12009-02-07 01:21:47 +0000656
657 // If it's not safe to move defs of the register class, then abort.
Evan Chenge53ab6d2010-09-17 22:28:18 +0000658 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
Craig Topperc0196b12014-04-14 00:51:57 +0000659 return nullptr;
Jim Grosbach01edd682010-06-03 23:49:57 +0000660
Chris Lattnerf3edc092008-01-04 07:36:53 +0000661 // Virtual register defs can only be sunk if all their uses are in blocks
662 // dominated by one of the successors.
663 if (SuccToSinkTo) {
664 // If a previous operand picked a block to sink to, then this operand
665 // must be sinkable to the same block.
Evan Cheng361b9be2010-08-19 18:33:29 +0000666 bool LocalUse = false;
Devang Patelc2686882011-12-14 23:20:38 +0000667 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
Evan Cheng2031b762010-09-20 19:12:55 +0000668 BreakPHIEdge, LocalUse))
Craig Topperc0196b12014-04-14 00:51:57 +0000669 return nullptr;
Bill Wendling7ee730e2010-06-02 23:04:26 +0000670
Chris Lattnerf3edc092008-01-04 07:36:53 +0000671 continue;
672 }
Jim Grosbach01edd682010-06-03 23:49:57 +0000673
Chris Lattnerf3edc092008-01-04 07:36:53 +0000674 // Otherwise, we should look at all the successors and decide which one
Bruno Cardoso Lopesd04f7592014-09-25 23:14:26 +0000675 // we should sink to. If we have reliable block frequency information
676 // (frequency != 0) available, give successors with smaller frequencies
677 // higher priority, otherwise prioritize smaller loop depths.
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000678 for (MachineBasicBlock *SuccBlock :
679 GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
Evan Cheng361b9be2010-08-19 18:33:29 +0000680 bool LocalUse = false;
Devang Patelc2686882011-12-14 23:20:38 +0000681 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
Evan Cheng2031b762010-09-20 19:12:55 +0000682 BreakPHIEdge, LocalUse)) {
Devang Patel1a3c1692011-12-08 21:33:23 +0000683 SuccToSinkTo = SuccBlock;
Chris Lattnerf3edc092008-01-04 07:36:53 +0000684 break;
685 }
Evan Cheng25b60682010-08-18 23:09:25 +0000686 if (LocalUse)
687 // Def is used locally, it's never safe to move this def.
Craig Topperc0196b12014-04-14 00:51:57 +0000688 return nullptr;
Chris Lattnerf3edc092008-01-04 07:36:53 +0000689 }
Jim Grosbach01edd682010-06-03 23:49:57 +0000690
Chris Lattnerf3edc092008-01-04 07:36:53 +0000691 // If we couldn't find a block to sink to, ignore this instruction.
Craig Topperc0196b12014-04-14 00:51:57 +0000692 if (!SuccToSinkTo)
693 return nullptr;
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000694 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
Craig Topperc0196b12014-04-14 00:51:57 +0000695 return nullptr;
Chris Lattnerf3edc092008-01-04 07:36:53 +0000696 }
697 }
Devang Patel202cf2f2011-12-08 23:52:00 +0000698
699 // It is not possible to sink an instruction into its own block. This can
700 // happen with loops.
Devang Patelc2686882011-12-14 23:20:38 +0000701 if (MBB == SuccToSinkTo)
Craig Topperc0196b12014-04-14 00:51:57 +0000702 return nullptr;
Devang Patel202cf2f2011-12-08 23:52:00 +0000703
704 // It's not safe to sink instructions to EH landing pad. Control flow into
705 // landing pad is implicitly defined.
Reid Kleckner0e288232015-08-27 23:27:47 +0000706 if (SuccToSinkTo && SuccToSinkTo->isEHPad())
Craig Topperc0196b12014-04-14 00:51:57 +0000707 return nullptr;
Devang Patel202cf2f2011-12-08 23:52:00 +0000708
Devang Patelb94c9a42011-12-08 21:48:01 +0000709 return SuccToSinkTo;
710}
711
Adrian Prantl5f8f34e42018-05-01 15:54:18 +0000712/// Return true if MI is likely to be usable as a memory operation by the
Sanjoy Das16901a32016-01-20 00:06:14 +0000713/// implicit null check optimization.
714///
715/// This is a "best effort" heuristic, and should not be relied upon for
716/// correctness. This returning true does not guarantee that the implicit null
717/// check optimization is legal over MI, and this returning false does not
718/// guarantee MI cannot possibly be used to do a null check.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000719static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
Sanjoy Das16901a32016-01-20 00:06:14 +0000720 const TargetInstrInfo *TII,
721 const TargetRegisterInfo *TRI) {
Eugene Zelenko900b6332017-08-29 22:32:07 +0000722 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
Sanjoy Das16901a32016-01-20 00:06:14 +0000723
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000724 auto *MBB = MI.getParent();
Sanjoy Das16901a32016-01-20 00:06:14 +0000725 if (MBB->pred_size() != 1)
726 return false;
727
728 auto *PredMBB = *MBB->pred_begin();
729 auto *PredBB = PredMBB->getBasicBlock();
730
731 // Frontends that don't use implicit null checks have no reason to emit
732 // branches with make.implicit metadata, and this function should always
733 // return false for them.
734 if (!PredBB ||
735 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
736 return false;
737
Chad Rosierc27a18f2016-03-09 16:00:35 +0000738 unsigned BaseReg;
739 int64_t Offset;
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000740 if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
Sanjoy Das16901a32016-01-20 00:06:14 +0000741 return false;
742
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000743 if (!(MI.mayLoad() && !MI.isPredicable()))
Sanjoy Das16901a32016-01-20 00:06:14 +0000744 return false;
745
746 MachineBranchPredicate MBP;
Jacques Pienaar71c30a12016-07-15 14:41:04 +0000747 if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
Sanjoy Das16901a32016-01-20 00:06:14 +0000748 return false;
749
750 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
751 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
752 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
753 MBP.LHS.getReg() == BaseReg;
754}
755
Devang Patelb94c9a42011-12-08 21:48:01 +0000756/// SinkInstruction - Determine whether it is safe to sink the specified machine
757/// instruction out of its current block into a successor.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000758bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000759 AllSuccsCache &AllSuccessors) {
Fiona Glaser44a2f7a2016-03-29 22:44:57 +0000760 // Don't sink instructions that the target prefers not to sink.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000761 if (!TII->shouldSink(MI))
Devang Patelb94c9a42011-12-08 21:48:01 +0000762 return false;
763
764 // Check if it's safe to move the instruction.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000765 if (!MI.isSafeToMove(AA, SawStore))
Devang Patelb94c9a42011-12-08 21:48:01 +0000766 return false;
767
Owen Andersond95b08a2015-10-09 18:06:13 +0000768 // Convergent operations may not be made control-dependent on additional
769 // values.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000770 if (MI.isConvergent())
Owen Anderson55313d22015-06-01 17:26:30 +0000771 return false;
772
Sanjoy Das16901a32016-01-20 00:06:14 +0000773 // Don't break implicit null checks. This is a performance heuristic, and not
774 // required for correctness.
775 if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
776 return false;
777
Devang Patelb94c9a42011-12-08 21:48:01 +0000778 // FIXME: This should include support for sinking instructions within the
779 // block they are currently in to shorten the live ranges. We often get
780 // instructions sunk into the top of a large block, but it would be better to
781 // also sink them down before their first use in the block. This xform has to
782 // be careful not to *increase* register pressure though, e.g. sinking
783 // "x = y + z" down if it kills y and z would increase the live ranges of y
784 // and z and only shrink the live range of x.
785
786 bool BreakPHIEdge = false;
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000787 MachineBasicBlock *ParentBlock = MI.getParent();
Arnaud A. de Grandmaisonc8a694f2015-06-16 08:57:21 +0000788 MachineBasicBlock *SuccToSinkTo =
789 FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
Jim Grosbach01edd682010-06-03 23:49:57 +0000790
Chris Lattner6ec78272008-01-05 01:39:17 +0000791 // If there are no outputs, it must have side-effects.
Craig Topperc0196b12014-04-14 00:51:57 +0000792 if (!SuccToSinkTo)
Chris Lattner6ec78272008-01-05 01:39:17 +0000793 return false;
Evan Cheng25104362009-02-15 08:36:12 +0000794
Daniel Dunbaref5a4382010-06-23 00:48:25 +0000795 // If the instruction to move defines a dead physical register which is live
796 // when leaving the basic block, don't move it because it could turn into a
797 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000798 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
799 const MachineOperand &MO = MI.getOperand(I);
Bill Wendlinge41e40f2010-06-25 20:48:10 +0000800 if (!MO.isReg()) continue;
801 unsigned Reg = MO.getReg();
802 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
803 if (SuccToSinkTo->isLiveIn(Reg))
Bill Wendlingf82aea62010-06-03 07:54:20 +0000804 return false;
Bill Wendlinge41e40f2010-06-25 20:48:10 +0000805 }
Bill Wendlingf82aea62010-06-03 07:54:20 +0000806
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000807 DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
Bill Wendling7ee730e2010-06-02 23:04:26 +0000808
Will Dietz5cb7f4e2013-10-14 16:57:17 +0000809 // If the block has multiple predecessors, this is a critical edge.
810 // Decide if we can sink along it or need to break the edge.
Chris Lattnerf3edc092008-01-04 07:36:53 +0000811 if (SuccToSinkTo->pred_size() > 1) {
Jakob Stoklund Olesen20b71e22010-04-13 19:06:14 +0000812 // We cannot sink a load across a critical edge - there may be stores in
813 // other code paths.
Evan Chengae9939c2010-08-19 17:33:11 +0000814 bool TryBreak = false;
Jakob Stoklund Olesen20b71e22010-04-13 19:06:14 +0000815 bool store = true;
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000816 if (!MI.isSafeToMove(AA, store)) {
Evan Chenge5af9302010-08-19 23:33:02 +0000817 DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
Evan Chengae9939c2010-08-19 17:33:11 +0000818 TryBreak = true;
Jakob Stoklund Olesen20b71e22010-04-13 19:06:14 +0000819 }
820
821 // We don't want to sink across a critical edge if we don't dominate the
822 // successor. We could be introducing calculations to new code paths.
Evan Chengae9939c2010-08-19 17:33:11 +0000823 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
Evan Chenge5af9302010-08-19 23:33:02 +0000824 DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
Evan Chengae9939c2010-08-19 17:33:11 +0000825 TryBreak = true;
Jakob Stoklund Olesen20b71e22010-04-13 19:06:14 +0000826 }
827
Jakob Stoklund Olesencdc3df42010-04-15 23:41:02 +0000828 // Don't sink instructions into a loop.
Evan Chengae9939c2010-08-19 17:33:11 +0000829 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
Evan Chenge5af9302010-08-19 23:33:02 +0000830 DEBUG(dbgs() << " *** NOTE: Loop header found\n");
Evan Chengae9939c2010-08-19 17:33:11 +0000831 TryBreak = true;
Jakob Stoklund Olesencdc3df42010-04-15 23:41:02 +0000832 }
833
Jakob Stoklund Olesen20b71e22010-04-13 19:06:14 +0000834 // Otherwise we are OK with sinking along a critical edge.
Evan Chengae9939c2010-08-19 17:33:11 +0000835 if (!TryBreak)
836 DEBUG(dbgs() << "Sinking along critical edge.\n");
837 else {
Quentin Colombet5cded892014-08-11 23:52:01 +0000838 // Mark this edge as to be split.
839 // If the edge can actually be split, the next iteration of the main loop
840 // will sink MI in the newly created block.
841 bool Status =
842 PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
843 if (!Status)
Evan Chenge53ab6d2010-09-17 22:28:18 +0000844 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
Quentin Colombet5cded892014-08-11 23:52:01 +0000845 "break critical edge\n");
846 // The instruction will not be sunk this time.
847 return false;
Evan Chengae9939c2010-08-19 17:33:11 +0000848 }
Chris Lattnerf3edc092008-01-04 07:36:53 +0000849 }
Jim Grosbach01edd682010-06-03 23:49:57 +0000850
Evan Cheng2031b762010-09-20 19:12:55 +0000851 if (BreakPHIEdge) {
852 // BreakPHIEdge is true if all the uses are in the successor MBB being
853 // sunken into and they are all PHI nodes. In this case, machine-sink must
854 // break the critical edge first.
Quentin Colombet5cded892014-08-11 23:52:01 +0000855 bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
856 SuccToSinkTo, BreakPHIEdge);
857 if (!Status)
Evan Chengb339f3d2010-09-18 06:42:17 +0000858 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
859 "break critical edge\n");
Quentin Colombet5cded892014-08-11 23:52:01 +0000860 // The instruction will not be sunk this time.
861 return false;
Evan Chengb339f3d2010-09-18 06:42:17 +0000862 }
863
Bill Wendling7ee730e2010-06-02 23:04:26 +0000864 // Determine where to insert into. Skip phi nodes.
Chris Lattnerf3edc092008-01-04 07:36:53 +0000865 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
Evan Chengb339f3d2010-09-18 06:42:17 +0000866 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
Chris Lattnerf3edc092008-01-04 07:36:53 +0000867 ++InsertPos;
Jim Grosbach01edd682010-06-03 23:49:57 +0000868
Devang Patel9de7a7d2011-09-07 00:07:58 +0000869 // collect matching debug values.
870 SmallVector<MachineInstr *, 2> DbgValuesToSink;
871 collectDebugValues(MI, DbgValuesToSink);
872
Paul Robinson8bd9d6a2017-12-09 00:17:01 +0000873 // Merge or erase debug location to ensure consistent stepping in profilers
874 // and debuggers.
875 if (!SuccToSinkTo->empty() && InsertPos != SuccToSinkTo->end())
876 MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
877 InsertPos->getDebugLoc()));
878 else
879 MI.setDebugLoc(DebugLoc());
880
881
Chris Lattnerf3edc092008-01-04 07:36:53 +0000882 // Move the instruction.
883 SuccToSinkTo->splice(InsertPos, ParentBlock, MI,
884 ++MachineBasicBlock::iterator(MI));
Dan Gohmanc90f51c2010-05-13 20:34:42 +0000885
Paul Robinson8bd9d6a2017-12-09 00:17:01 +0000886 // Move previously adjacent debug value instructions to the insert position.
Craig Toppere1c1d362013-07-03 05:11:49 +0000887 for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
Devang Patel9de7a7d2011-09-07 00:07:58 +0000888 DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) {
889 MachineInstr *DbgMI = *DBI;
890 SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI,
891 ++MachineBasicBlock::iterator(DbgMI));
892 }
893
Juergen Ributzka4bea4942014-09-04 02:07:36 +0000894 // Conservatively, clear any kill flags, since it's possible that they are no
895 // longer correct.
Pete Cooper85b1c482015-05-08 17:54:32 +0000896 // Note that we have to clear the kill flags for any register this instruction
897 // uses as we may sink over another instruction which currently kills the
898 // used registers.
Duncan P. N. Exon Smithcb38ffa2016-07-01 00:11:48 +0000899 for (MachineOperand &MO : MI.operands()) {
Pete Cooper85b1c482015-05-08 17:54:32 +0000900 if (MO.isReg() && MO.isUse())
Matthias Braun352b89c2015-05-16 03:11:07 +0000901 RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
Pete Cooper85b1c482015-05-08 17:54:32 +0000902 }
Dan Gohmanc90f51c2010-05-13 20:34:42 +0000903
Chris Lattnerf3edc092008-01-04 07:36:53 +0000904 return true;
905}
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +0000906
907//===----------------------------------------------------------------------===//
908// This pass is not intended to be a replacement or a complete alternative
909// for the pre-ra machine sink pass. It is only designed to sink COPY
910// instructions which should be handled after RA.
911//
912// This pass sinks COPY instructions into a successor block, if the COPY is not
913// used in the current block and the COPY is live-in to a single successor
914// (i.e., doesn't require the COPY to be duplicated). This avoids executing the
915// copy on paths where their results aren't needed. This also exposes
916// additional opportunites for dead copy elimination and shrink wrapping.
917//
918// These copies were either not handled by or are inserted after the MachineSink
919// pass. As an example of the former case, the MachineSink pass cannot sink
920// COPY instructions with allocatable source registers; for AArch64 these type
921// of copy instructions are frequently used to move function parameters (PhyReg)
922// into virtual registers in the entry block.
923//
924// For the machine IR below, this pass will sink %w19 in the entry into its
925// successor (%bb.1) because %w19 is only live-in in %bb.1.
926// %bb.0:
927// %wzr = SUBSWri %w1, 1
928// %w19 = COPY %w0
929// Bcc 11, %bb.2
930// %bb.1:
931// Live Ins: %w19
932// BL @fun
933// %w0 = ADDWrr %w0, %w19
934// RET %w0
935// %bb.2:
936// %w0 = COPY %wzr
937// RET %w0
938// As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
939// able to see %bb.0 as a candidate.
940//===----------------------------------------------------------------------===//
941namespace {
942
943class PostRAMachineSinking : public MachineFunctionPass {
944public:
945 bool runOnMachineFunction(MachineFunction &MF) override;
946
947 static char ID;
948 PostRAMachineSinking() : MachineFunctionPass(ID) {}
949 StringRef getPassName() const override { return "PostRA Machine Sink"; }
950
Jun Bum Limf90fe702018-03-28 19:56:26 +0000951 void getAnalysisUsage(AnalysisUsage &AU) const override {
952 AU.setPreservesCFG();
953 MachineFunctionPass::getAnalysisUsage(AU);
954 }
955
Jun Bum Lim7ab1b322018-04-03 18:17:34 +0000956 MachineFunctionProperties getRequiredProperties() const override {
957 return MachineFunctionProperties().set(
Jun Bum Lim06073bf2018-04-13 14:23:09 +0000958 MachineFunctionProperties::Property::NoVRegs);
Jun Bum Lim7ab1b322018-04-03 18:17:34 +0000959 }
960
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +0000961private:
Jun Bum Lim47aece12018-04-27 18:44:37 +0000962 /// Track which register units have been modified and used.
963 LiveRegUnits ModifiedRegUnits, UsedRegUnits;
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +0000964
965 /// Sink Copy instructions unused in the same block close to their uses in
966 /// successors.
967 bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
968 const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
969};
970} // namespace
971
972char PostRAMachineSinking::ID = 0;
973char &llvm::PostRAMachineSinkingID = PostRAMachineSinking::ID;
974
975INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
976 "PostRA Machine Sink", false, false)
977
Jun Bum Lim47aece12018-04-27 18:44:37 +0000978static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
979 const TargetRegisterInfo *TRI) {
980 LiveRegUnits LiveInRegUnits(*TRI);
981 LiveInRegUnits.addLiveIns(MBB);
982 return !LiveInRegUnits.available(Reg);
Jun Bum Lim06073bf2018-04-13 14:23:09 +0000983}
984
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +0000985static MachineBasicBlock *
986getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
Jun Bum Lim9e3e14b2018-04-27 19:59:20 +0000987 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
988 unsigned Reg, const TargetRegisterInfo *TRI) {
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +0000989 // Try to find a single sinkable successor in which Reg is live-in.
990 MachineBasicBlock *BB = nullptr;
991 for (auto *SI : SinkableBBs) {
Jun Bum Lim9e3e14b2018-04-27 19:59:20 +0000992 if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +0000993 // If BB is set here, Reg is live-in to at least two sinkable successors,
994 // so quit.
995 if (BB)
996 return nullptr;
997 BB = SI;
998 }
999 }
1000 // Reg is not live-in to any sinkable successors.
1001 if (!BB)
1002 return nullptr;
1003
1004 // Check if any register aliased with Reg is live-in in other successors.
1005 for (auto *SI : CurBB.successors()) {
Jun Bum Lim9e3e14b2018-04-27 19:59:20 +00001006 if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001007 return nullptr;
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001008 }
1009 return BB;
1010}
1011
Jun Bum Lim9e3e14b2018-04-27 19:59:20 +00001012static MachineBasicBlock *
1013getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
1014 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1015 ArrayRef<unsigned> DefedRegsInCopy,
1016 const TargetRegisterInfo *TRI) {
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001017 MachineBasicBlock *SingleBB = nullptr;
1018 for (auto DefReg : DefedRegsInCopy) {
1019 MachineBasicBlock *BB =
1020 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1021 if (!BB || (SingleBB && SingleBB != BB))
1022 return nullptr;
1023 SingleBB = BB;
1024 }
1025 return SingleBB;
1026}
1027
1028static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,
1029 SmallVectorImpl<unsigned> &UsedOpsInCopy,
Jun Bum Lim47aece12018-04-27 18:44:37 +00001030 LiveRegUnits &UsedRegUnits,
1031 const TargetRegisterInfo *TRI) {
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001032 for (auto U : UsedOpsInCopy) {
1033 MachineOperand &MO = MI->getOperand(U);
1034 unsigned SrcReg = MO.getReg();
Jun Bum Lim47aece12018-04-27 18:44:37 +00001035 if (!UsedRegUnits.available(SrcReg)) {
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001036 MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1037 for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1038 if (UI.killsRegister(SrcReg, TRI)) {
1039 UI.clearRegisterKills(SrcReg, TRI);
1040 MO.setIsKill(true);
1041 break;
1042 }
1043 }
1044 }
1045 }
1046}
1047
1048static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,
1049 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1050 SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1051 for (auto DefReg : DefedRegsInCopy)
1052 SuccBB->removeLiveIn(DefReg);
1053 for (auto U : UsedOpsInCopy) {
1054 unsigned Reg = MI->getOperand(U).getReg();
1055 if (!SuccBB->isLiveIn(Reg))
1056 SuccBB->addLiveIn(Reg);
1057 }
1058}
1059
1060static bool hasRegisterDependency(MachineInstr *MI,
1061 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1062 SmallVectorImpl<unsigned> &DefedRegsInCopy,
Jun Bum Lim47aece12018-04-27 18:44:37 +00001063 LiveRegUnits &ModifiedRegUnits,
1064 LiveRegUnits &UsedRegUnits) {
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001065 bool HasRegDependency = false;
1066 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1067 MachineOperand &MO = MI->getOperand(i);
1068 if (!MO.isReg())
1069 continue;
1070 unsigned Reg = MO.getReg();
1071 if (!Reg)
1072 continue;
1073 if (MO.isDef()) {
Jun Bum Lim47aece12018-04-27 18:44:37 +00001074 if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001075 HasRegDependency = true;
1076 break;
1077 }
1078 DefedRegsInCopy.push_back(Reg);
1079
1080 // FIXME: instead of isUse(), readsReg() would be a better fix here,
1081 // For example, we can ignore modifications in reg with undef. However,
1082 // it's not perfectly clear if skipping the internal read is safe in all
1083 // other targets.
1084 } else if (MO.isUse()) {
Jun Bum Lim47aece12018-04-27 18:44:37 +00001085 if (!ModifiedRegUnits.available(Reg)) {
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001086 HasRegDependency = true;
1087 break;
1088 }
1089 UsedOpsInCopy.push_back(i);
1090 }
1091 }
1092 return HasRegDependency;
1093}
1094
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001095bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1096 MachineFunction &MF,
1097 const TargetRegisterInfo *TRI,
1098 const TargetInstrInfo *TII) {
Jun Bum Lim9e3e14b2018-04-27 19:59:20 +00001099 SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001100 // FIXME: For now, we sink only to a successor which has a single predecessor
1101 // so that we can directly sink COPY instructions to the successor without
1102 // adding any new block or branch instruction.
1103 for (MachineBasicBlock *SI : CurBB.successors())
1104 if (!SI->livein_empty() && SI->pred_size() == 1)
Jun Bum Lim9e3e14b2018-04-27 19:59:20 +00001105 SinkableBBs.insert(SI);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001106
1107 if (SinkableBBs.empty())
1108 return false;
1109
1110 bool Changed = false;
1111
1112 // Track which registers have been modified and used between the end of the
1113 // block and the current instruction.
Jun Bum Lim47aece12018-04-27 18:44:37 +00001114 ModifiedRegUnits.clear();
1115 UsedRegUnits.clear();
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001116
1117 for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
1118 MachineInstr *MI = &*I;
1119 ++I;
1120
1121 // Do not move any instruction across function call.
1122 if (MI->isCall())
1123 return false;
1124
1125 if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) {
Jun Bum Lim47aece12018-04-27 18:44:37 +00001126 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1127 TRI);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001128 continue;
1129 }
1130
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001131 // Track the operand index for use in Copy.
1132 SmallVector<unsigned, 2> UsedOpsInCopy;
1133 // Track the register number defed in Copy.
1134 SmallVector<unsigned, 2> DefedRegsInCopy;
1135
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001136 // Don't sink the COPY if it would violate a register dependency.
Jun Bum Lim47aece12018-04-27 18:44:37 +00001137 if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1138 ModifiedRegUnits, UsedRegUnits)) {
1139 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1140 TRI);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001141 continue;
1142 }
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001143 assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
1144 "Unexpect SrcReg or DefReg");
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001145 MachineBasicBlock *SuccBB =
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001146 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001147 // Don't sink if we cannot find a single sinkable successor in which Reg
1148 // is live-in.
1149 if (!SuccBB) {
Jun Bum Lim47aece12018-04-27 18:44:37 +00001150 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1151 TRI);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001152 continue;
1153 }
1154 assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
1155 "Unexpected predecessor");
1156
1157 // Clear the kill flag if SrcReg is killed between MI and the end of the
1158 // block.
Jun Bum Lim47aece12018-04-27 18:44:37 +00001159 clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001160 MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
1161 SuccBB->splice(InsertPos, &CurBB, MI);
Jun Bum Lim06073bf2018-04-13 14:23:09 +00001162 updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001163
1164 Changed = true;
1165 ++NumPostRACopySink;
1166 }
1167 return Changed;
1168}
1169
1170bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
1171 bool Changed = false;
1172 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1173 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001174
Jun Bum Lim47aece12018-04-27 18:44:37 +00001175 ModifiedRegUnits.init(*TRI);
1176 UsedRegUnits.init(*TRI);
Jun Bum Lim2ecb7ba2018-03-22 20:06:47 +00001177 for (auto &BB : MF)
1178 Changed |= tryToSinkCopy(BB, MF, TRI, TII);
1179
1180 return Changed;
1181}