blob: 57684cdcc2f112fcffb9fad2ada9a76791dad144 [file] [log] [blame]
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +00001//===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +00007//
8//===----------------------------------------------------------------------===//
9//
10// Collect the sequence of machine instructions for a basic block.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/MachineBasicBlock.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000015#include "llvm/ADT/SmallPtrSet.h"
Cameron Zwarichb47fb382013-02-11 09:24:47 +000016#include "llvm/CodeGen/LiveIntervalAnalysis.h"
Dan Gohman3570f812010-06-22 17:25:57 +000017#include "llvm/CodeGen/LiveVariables.h"
18#include "llvm/CodeGen/MachineDominators.h"
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +000019#include "llvm/CodeGen/MachineFunction.h"
Jakob Stoklund Olesen533c3bf2013-07-03 23:56:20 +000020#include "llvm/CodeGen/MachineInstrBuilder.h"
Dan Gohman3570f812010-06-22 17:25:57 +000021#include "llvm/CodeGen/MachineLoopInfo.h"
Cameron Zwarichb47fb382013-02-11 09:24:47 +000022#include "llvm/CodeGen/MachineRegisterInfo.h"
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +000023#include "llvm/CodeGen/SlotIndexes.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000024#include "llvm/IR/BasicBlock.h"
25#include "llvm/IR/DataLayout.h"
Duncan P. N. Exon Smith326921542015-06-26 22:04:20 +000026#include "llvm/IR/ModuleSlotTracker.h"
Chris Lattnerd051af72010-01-26 04:55:51 +000027#include "llvm/MC/MCAsmInfo.h"
28#include "llvm/MC/MCContext.h"
Cong Hou663dd012015-12-13 09:52:14 +000029#include "llvm/Support/DataTypes.h"
David Greene6c56cef2010-01-04 23:22:07 +000030#include "llvm/Support/Debug.h"
Daniel Dunbar796e43e2009-07-24 10:36:58 +000031#include "llvm/Support/raw_ostream.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000032#include "llvm/Target/TargetInstrInfo.h"
33#include "llvm/Target/TargetMachine.h"
34#include "llvm/Target/TargetRegisterInfo.h"
Eric Christopherd9134482014-08-04 21:25:23 +000035#include "llvm/Target/TargetSubtargetInfo.h"
Chris Lattner4336b872004-10-26 15:43:42 +000036#include <algorithm>
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +000037using namespace llvm;
38
Chandler Carruthe96dd892014-04-21 22:55:11 +000039#define DEBUG_TYPE "codegen"
40
Cong Hou166e0852015-09-29 19:46:09 +000041MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
42 : BB(B), Number(-1), xParent(&MF) {
Dan Gohman804c95d2008-07-28 21:51:04 +000043 Insts.Parent = this;
Tanya Lattner91fa3a92004-05-24 07:14:35 +000044}
Tanya Lattner91fa3a92004-05-24 07:14:35 +000045
Dan Gohman0ece9432008-07-17 23:49:46 +000046MachineBasicBlock::~MachineBasicBlock() {
Dan Gohman0ece9432008-07-17 23:49:46 +000047}
48
Cong Hou2a02c1c2015-08-12 21:18:54 +000049/// Return the MCSymbol for this basic block.
Chris Lattner29bdac42010-03-13 21:04:28 +000050MCSymbol *MachineBasicBlock::getSymbol() const {
Eli Bendersky58b04b72013-04-22 21:21:08 +000051 if (!CachedMCSymbol) {
52 const MachineFunction *MF = getParent();
53 MCContext &Ctx = MF->getContext();
Mehdi Amini36d33fc2016-10-01 06:46:33 +000054 auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
Reid Klecknerb9204a52015-11-11 23:09:31 +000055 assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
Jim Grosbach6f482002015-05-18 18:43:14 +000056 CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
Eli Bendersky58b04b72013-04-22 21:21:08 +000057 Twine(MF->getFunctionNumber()) +
58 "_" + Twine(getNumber()));
59 }
60
61 return CachedMCSymbol;
Chris Lattnerd051af72010-01-26 04:55:51 +000062}
63
64
Chris Lattneraf119ca2009-08-23 00:35:30 +000065raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
Daniel Dunbar796e43e2009-07-24 10:36:58 +000066 MBB.print(OS);
67 return OS;
68}
Tanya Lattner91fa3a92004-05-24 07:14:35 +000069
Cong Hou2a02c1c2015-08-12 21:18:54 +000070/// When an MBB is added to an MF, we need to update the parent pointer of the
71/// MBB, the MBB numbering, and any instructions in the MBB to be on the right
72/// operand list for registers.
Chris Lattner961e7422008-01-01 01:12:31 +000073///
74/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
75/// gets the next available unique MBB number. If it is removed from a
76/// MachineFunction, it goes back to being #-1.
Duncan P. N. Exon Smithf947c3a2016-08-30 18:40:47 +000077void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
78 MachineBasicBlock *N) {
Dan Gohman3b460302008-07-07 23:14:23 +000079 MachineFunction &MF = *N->getParent();
80 N->Number = MF.addToMBBNumbering(N);
Chris Lattner961e7422008-01-01 01:12:31 +000081
82 // Make sure the instructions have their operands in the reginfo lists.
Dan Gohman3b460302008-07-07 23:14:23 +000083 MachineRegisterInfo &RegInfo = MF.getRegInfo();
Evan Cheng7fae11b2011-12-14 02:11:42 +000084 for (MachineBasicBlock::instr_iterator
85 I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
Chris Lattner961e7422008-01-01 01:12:31 +000086 I->AddRegOperandsToUseLists(RegInfo);
Brian Gaekecb5d22a2004-05-12 21:35:22 +000087}
88
Duncan P. N. Exon Smithf947c3a2016-08-30 18:40:47 +000089void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
90 MachineBasicBlock *N) {
Chris Lattner574e7162007-12-31 04:56:33 +000091 N->getParent()->removeFromMBBNumbering(N->Number);
Brian Gaekecb5d22a2004-05-12 21:35:22 +000092 N->Number = -1;
93}
94
Cong Hou2a02c1c2015-08-12 21:18:54 +000095/// When we add an instruction to a basic block list, we update its parent
96/// pointer and add its operands from reg use/def lists if appropriate.
Chris Lattneraf119ca2009-08-23 00:35:30 +000097void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
Craig Topperc0196b12014-04-14 00:51:57 +000098 assert(!N->getParent() && "machine instruction already in a basic block");
Dan Gohman3b460302008-07-07 23:14:23 +000099 N->setParent(Parent);
Jakub Staszakfeadd432011-06-16 18:01:17 +0000100
Dan Gohman3b460302008-07-07 23:14:23 +0000101 // Add the instruction's register operands to their corresponding
102 // use/def lists.
103 MachineFunction *MF = Parent->getParent();
104 N->AddRegOperandsToUseLists(MF->getRegInfo());
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +0000105}
106
Cong Hou2a02c1c2015-08-12 21:18:54 +0000107/// When we remove an instruction from a basic block list, we update its parent
108/// pointer and remove its operands from reg use/def lists if appropriate.
Chris Lattneraf119ca2009-08-23 00:35:30 +0000109void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {
Craig Topperc0196b12014-04-14 00:51:57 +0000110 assert(N->getParent() && "machine instruction not in a basic block");
Dan Gohman3b460302008-07-07 23:14:23 +0000111
112 // Remove from the use/def lists.
Jakob Stoklund Olesenc4102d42012-08-09 22:49:37 +0000113 if (MachineFunction *MF = N->getParent()->getParent())
114 N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
Jakub Staszakfeadd432011-06-16 18:01:17 +0000115
Craig Topperc0196b12014-04-14 00:51:57 +0000116 N->setParent(nullptr);
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +0000117}
118
Cong Hou2a02c1c2015-08-12 21:18:54 +0000119/// When moving a range of instructions from one MBB list to another, we need to
120/// update the parent pointers and the use/def lists.
Duncan P. N. Exon Smithcc9edac2016-09-11 16:38:18 +0000121void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList,
122 instr_iterator First,
123 instr_iterator Last) {
Cong Hou166e0852015-09-29 19:46:09 +0000124 assert(Parent->getParent() == FromList.Parent->getParent() &&
Dan Gohman804c95d2008-07-28 21:51:04 +0000125 "MachineInstr parent mismatch!");
Duncan P. N. Exon Smithb7668d52016-08-30 18:00:45 +0000126 assert(this != &FromList && "Called without a real transfer...");
127 assert(Parent != FromList.Parent && "Two lists have the same parent?");
Chris Lattner961e7422008-01-01 01:12:31 +0000128
129 // If splicing between two blocks within the same function, just update the
130 // parent pointers.
Cong Hou166e0852015-09-29 19:46:09 +0000131 for (; First != Last; ++First)
132 First->setParent(Parent);
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +0000133}
134
Duncan P. N. Exon Smithf947c3a2016-08-30 18:40:47 +0000135void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
Dan Gohman3b460302008-07-07 23:14:23 +0000136 assert(!MI->getParent() && "MI is still in a block!");
137 Parent->getParent()->DeleteMachineInstr(MI);
138}
139
Dan Gohman88c547e2010-07-07 14:33:51 +0000140MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
Benjamin Kramerbaa41d42012-02-10 00:28:31 +0000141 instr_iterator I = instr_begin(), E = instr_end();
142 while (I != E && I->isPHI())
Dan Gohman88c547e2010-07-07 14:33:51 +0000143 ++I;
Akira Hatanaka6fe7aca2012-10-26 17:11:42 +0000144 assert((I == E || !I->isInsideBundle()) &&
145 "First non-phi MI cannot be inside a bundle!");
Dan Gohman88c547e2010-07-07 14:33:51 +0000146 return I;
147}
148
Jakob Stoklund Olesenef541852010-10-30 01:26:14 +0000149MachineBasicBlock::iterator
150MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
Benjamin Kramerbaa41d42012-02-10 00:28:31 +0000151 iterator E = end();
Keith Walker830a8c12016-09-16 14:07:29 +0000152 while (I != E && (I->isPHI() || I->isPosition()))
153 ++I;
154 // FIXME: This needs to change if we wish to bundle labels
155 // inside the bundle.
156 assert((I == E || !I->isInsideBundle()) &&
157 "First non-phi / non-label instruction is inside a bundle!");
158 return I;
159}
160
161MachineBasicBlock::iterator
162MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) {
163 iterator E = end();
Rafael Espindolab1f25f12014-03-07 06:08:31 +0000164 while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue()))
Jakob Stoklund Olesenef541852010-10-30 01:26:14 +0000165 ++I;
Evan Cheng2a81dd42011-12-06 22:12:01 +0000166 // FIXME: This needs to change if we wish to bundle labels / dbg_values
167 // inside the bundle.
Akira Hatanaka6fe7aca2012-10-26 17:11:42 +0000168 assert((I == E || !I->isInsideBundle()) &&
Keith Walker830a8c12016-09-16 14:07:29 +0000169 "First non-phi / non-label / non-debug "
170 "instruction is inside a bundle!");
Jakob Stoklund Olesenef541852010-10-30 01:26:14 +0000171 return I;
172}
173
Chris Lattner4336b872004-10-26 15:43:42 +0000174MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
Benjamin Kramerbaa41d42012-02-10 00:28:31 +0000175 iterator B = begin(), E = end(), I = E;
176 while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
Jakob Stoklund Olesenc3810282011-01-14 02:12:54 +0000177 ; /*noop */
Benjamin Kramerbaa41d42012-02-10 00:28:31 +0000178 while (I != E && !I->isTerminator())
Evan Cheng2a81dd42011-12-06 22:12:01 +0000179 ++I;
180 return I;
181}
182
Evan Cheng7fae11b2011-12-14 02:11:42 +0000183MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
Benjamin Kramerbaa41d42012-02-10 00:28:31 +0000184 instr_iterator B = instr_begin(), E = instr_end(), I = E;
185 while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
Evan Cheng2a81dd42011-12-06 22:12:01 +0000186 ; /*noop */
Benjamin Kramerbaa41d42012-02-10 00:28:31 +0000187 while (I != E && !I->isTerminator())
Jakob Stoklund Olesenab3d6ec2011-01-14 06:33:45 +0000188 ++I;
Jakob Stoklund Olesenc3810282011-01-14 02:12:54 +0000189 return I;
Alkis Evlogimenosaf2de482004-02-23 18:14:48 +0000190}
191
Benjamin Kramer6b568962015-06-23 14:47:29 +0000192MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() {
193 // Skip over begin-of-block dbg_value instructions.
194 iterator I = begin(), E = end();
195 while (I != E && I->isDebugValue())
196 ++I;
197 return I;
198}
199
Jakob Stoklund Olesen4bc5e382011-01-13 21:28:52 +0000200MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() {
Evan Cheng2a81dd42011-12-06 22:12:01 +0000201 // Skip over end-of-block dbg_value instructions.
Evan Cheng7fae11b2011-12-14 02:11:42 +0000202 instr_iterator B = instr_begin(), I = instr_end();
Jakob Stoklund Olesen4bc5e382011-01-13 21:28:52 +0000203 while (I != B) {
204 --I;
Evan Cheng2a81dd42011-12-06 22:12:01 +0000205 // Return instruction that starts a bundle.
206 if (I->isDebugValue() || I->isInsideBundle())
207 continue;
208 return I;
209 }
210 // The block is all debug values.
211 return end();
212}
213
Reid Klecknered170792015-09-17 17:19:40 +0000214bool MachineBasicBlock::hasEHPadSuccessor() const {
215 for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
216 if ((*I)->isEHPad())
217 return true;
218 return false;
219}
220
Manman Ren19f49ac2012-09-11 22:23:19 +0000221#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Yaron Kereneb2a2542016-01-29 20:50:44 +0000222LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
David Greene6c56cef2010-01-04 23:22:07 +0000223 print(dbgs());
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +0000224}
Manman Ren742534c2012-09-06 19:06:06 +0000225#endif
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +0000226
Jakob Stoklund Olesen2bbeaa82009-11-20 01:17:03 +0000227StringRef MachineBasicBlock::getName() const {
228 if (const BasicBlock *LBB = getBasicBlock())
229 return LBB->getName();
230 else
231 return "(null)";
232}
233
Andrew Trick320c7032012-03-07 00:18:18 +0000234/// Return a hopefully unique identifier for this block.
235std::string MachineBasicBlock::getFullName() const {
236 std::string Name;
237 if (getParent())
Craig Toppera538d832012-08-22 06:07:19 +0000238 Name = (getParent()->getName() + ":").str();
Andrew Trick320c7032012-03-07 00:18:18 +0000239 if (getBasicBlock())
240 Name += getBasicBlock()->getName();
241 else
Yaron Keren75e0c4b2015-03-27 17:51:30 +0000242 Name += ("BB" + Twine(getNumber())).str();
Andrew Trick320c7032012-03-07 00:18:18 +0000243 return Name;
244}
245
Matthias Braun0e881d62016-05-05 18:14:43 +0000246void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes)
247 const {
Evan Chengbcf1d7f2007-02-10 02:38:19 +0000248 const MachineFunction *MF = getParent();
Chris Lattneraf119ca2009-08-23 00:35:30 +0000249 if (!MF) {
Chris Lattner4336b872004-10-26 15:43:42 +0000250 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
251 << " is null\n";
Tanya Lattnera578cb72004-05-24 06:11:51 +0000252 return;
253 }
Duncan P. N. Exon Smith326921542015-06-26 22:04:20 +0000254 const Function *F = MF->getFunction();
255 const Module *M = F ? F->getParent() : nullptr;
256 ModuleSlotTracker MST(M);
257 print(OS, MST, Indexes);
258}
259
260void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
Matthias Braun0e881d62016-05-05 18:14:43 +0000261 const SlotIndexes *Indexes) const {
Duncan P. N. Exon Smith326921542015-06-26 22:04:20 +0000262 const MachineFunction *MF = getParent();
263 if (!MF) {
264 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
265 << " is null\n";
266 return;
267 }
Alkis Evlogimenosfcb3f512004-09-05 18:39:20 +0000268
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000269 if (Indexes)
270 OS << Indexes->getMBBStartIdx(this) << '\t';
271
Dan Gohman34341e62009-10-31 20:19:03 +0000272 OS << "BB#" << getNumber() << ": ";
273
274 const char *Comma = "";
275 if (const BasicBlock *LBB = getBasicBlock()) {
276 OS << Comma << "derived from LLVM BB ";
Duncan P. N. Exon Smith326921542015-06-26 22:04:20 +0000277 LBB->printAsOperand(OS, /*PrintType=*/false, MST);
Dan Gohman34341e62009-10-31 20:19:03 +0000278 Comma = ", ";
279 }
Reid Kleckner0e288232015-08-27 23:27:47 +0000280 if (isEHPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; }
Dan Gohman34341e62009-10-31 20:19:03 +0000281 if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; }
Bill Wendling4fd96632012-06-15 19:30:42 +0000282 if (Alignment)
Jakob Stoklund Olesen2a2b37e2011-12-06 21:08:39 +0000283 OS << Comma << "Align " << Alignment << " (" << (1u << Alignment)
284 << " bytes)";
Jakob Stoklund Olesen2a2b37e2011-12-06 21:08:39 +0000285
Chris Lattneraf119ca2009-08-23 00:35:30 +0000286 OS << '\n';
Evan Chengbcf1d7f2007-02-10 02:38:19 +0000287
Eric Christopherfc6de422014-08-05 02:39:49 +0000288 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
Dan Gohmanc731c972007-10-03 19:26:29 +0000289 if (!livein_empty()) {
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000290 if (Indexes) OS << '\t';
Dan Gohman34341e62009-10-31 20:19:03 +0000291 OS << " Live Ins:";
Matthias Braund9da1622015-09-09 18:08:03 +0000292 for (const auto &LI : make_range(livein_begin(), livein_end())) {
293 OS << ' ' << PrintReg(LI.PhysReg, TRI);
294 if (LI.LaneMask != ~0u)
Matthias Braunc804cdb2015-09-25 21:51:24 +0000295 OS << ':' << PrintLaneMask(LI.LaneMask);
Matthias Braunb2b7ef12015-08-24 22:59:52 +0000296 }
Chris Lattneraf119ca2009-08-23 00:35:30 +0000297 OS << '\n';
Evan Chengbcf1d7f2007-02-10 02:38:19 +0000298 }
Chris Lattner9a1e91b2006-09-26 03:41:59 +0000299 // Print the preds of this block according to the CFG.
300 if (!pred_empty()) {
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000301 if (Indexes) OS << '\t';
Chris Lattner9a1e91b2006-09-26 03:41:59 +0000302 OS << " Predecessors according to CFG:";
303 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
Dan Gohman34341e62009-10-31 20:19:03 +0000304 OS << " BB#" << (*PI)->getNumber();
Chris Lattneraf119ca2009-08-23 00:35:30 +0000305 OS << '\n';
Chris Lattner9a1e91b2006-09-26 03:41:59 +0000306 }
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000307
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000308 for (auto &I : instrs()) {
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000309 if (Indexes) {
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000310 if (Indexes->hasIndex(I))
311 OS << Indexes->getInstructionIndex(I);
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000312 OS << '\t';
313 }
Chris Lattner1216f542009-08-23 00:47:04 +0000314 OS << '\t';
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000315 if (I.isInsideBundle())
Evan Cheng7fae11b2011-12-14 02:11:42 +0000316 OS << " * ";
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000317 I.print(OS, MST);
Alkis Evlogimenosfcb3f512004-09-05 18:39:20 +0000318 }
Chris Lattner329c14a2005-04-01 06:48:38 +0000319
320 // Print the successors of this block according to the CFG.
321 if (!succ_empty()) {
Jakob Stoklund Olesenb7050232010-10-26 20:21:46 +0000322 if (Indexes) OS << '\t';
Chris Lattner329c14a2005-04-01 06:48:38 +0000323 OS << " Successors according to CFG:";
Jakob Stoklund Olesen1dc107a2012-08-13 23:13:23 +0000324 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) {
Dan Gohman34341e62009-10-31 20:19:03 +0000325 OS << " BB#" << (*SI)->getNumber();
Cong Houd97c1002015-12-01 05:29:22 +0000326 if (!Probs.empty())
327 OS << '(' << *getProbabilityIterator(SI) << ')';
Jakob Stoklund Olesen1dc107a2012-08-13 23:13:23 +0000328 }
Chris Lattneraf119ca2009-08-23 00:35:30 +0000329 OS << '\n';
Chris Lattner329c14a2005-04-01 06:48:38 +0000330 }
Alkis Evlogimenos14f3fe82004-02-16 07:17:43 +0000331}
Chris Lattner4336b872004-10-26 15:43:42 +0000332
Cong Hou2793e722015-08-10 22:27:10 +0000333void MachineBasicBlock::printAsOperand(raw_ostream &OS,
334 bool /*PrintType*/) const {
Chandler Carruthd48cdbf2014-01-09 02:29:41 +0000335 OS << "BB#" << getNumber();
336}
337
Matthias Braune6a24852015-09-25 21:51:14 +0000338void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
David Majnemer42531262016-08-12 03:55:06 +0000339 LiveInVector::iterator I = find_if(
340 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
Matthias Braund9da1622015-09-09 18:08:03 +0000341 if (I == LiveIns.end())
342 return;
343
344 I->LaneMask &= ~LaneMask;
345 if (I->LaneMask == 0)
Jakob Stoklund Olesen8e58c902012-03-28 20:11:42 +0000346 LiveIns.erase(I);
Evan Chengf7ed82d2007-02-19 21:49:54 +0000347}
348
Matthias Braune6a24852015-09-25 21:51:14 +0000349bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
David Majnemer42531262016-08-12 03:55:06 +0000350 livein_iterator I = find_if(
351 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
Matthias Braund9da1622015-09-09 18:08:03 +0000352 return I != livein_end() && (I->LaneMask & LaneMask) != 0;
353}
354
355void MachineBasicBlock::sortUniqueLiveIns() {
356 std::sort(LiveIns.begin(), LiveIns.end(),
357 [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
358 return LI0.PhysReg < LI1.PhysReg;
359 });
360 // Liveins are sorted by physreg now we can merge their lanemasks.
361 LiveInVector::const_iterator I = LiveIns.begin();
362 LiveInVector::const_iterator J;
363 LiveInVector::iterator Out = LiveIns.begin();
364 for (; I != LiveIns.end(); ++Out, I = J) {
365 unsigned PhysReg = I->PhysReg;
Matthias Braune6a24852015-09-25 21:51:14 +0000366 LaneBitmask LaneMask = I->LaneMask;
Matthias Braund9da1622015-09-09 18:08:03 +0000367 for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
368 LaneMask |= J->LaneMask;
369 Out->PhysReg = PhysReg;
370 Out->LaneMask = LaneMask;
371 }
372 LiveIns.erase(Out, LiveIns.end());
Aaron Ballman9f154f62015-07-29 15:57:49 +0000373}
374
Jakob Stoklund Olesen533c3bf2013-07-03 23:56:20 +0000375unsigned
Matthias Braun130bd902015-08-25 22:05:55 +0000376MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) {
Jakob Stoklund Olesen533c3bf2013-07-03 23:56:20 +0000377 assert(getParent() && "MBB must be inserted in function");
378 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
379 assert(RC && "Register class is required");
Reid Kleckner0e288232015-08-27 23:27:47 +0000380 assert((isEHPad() || this == &getParent()->front()) &&
Jakob Stoklund Olesen533c3bf2013-07-03 23:56:20 +0000381 "Only the entry block and landing pads can have physreg live ins");
382
383 bool LiveIn = isLiveIn(PhysReg);
Jakob Stoklund Olesenbbbb5322013-07-04 04:32:35 +0000384 iterator I = SkipPHIsAndLabels(begin()), E = end();
Jakob Stoklund Olesen533c3bf2013-07-03 23:56:20 +0000385 MachineRegisterInfo &MRI = getParent()->getRegInfo();
Eric Christopherfc6de422014-08-05 02:39:49 +0000386 const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
Jakob Stoklund Olesen533c3bf2013-07-03 23:56:20 +0000387
388 // Look for an existing copy.
389 if (LiveIn)
390 for (;I != E && I->isCopy(); ++I)
391 if (I->getOperand(1).getReg() == PhysReg) {
392 unsigned VirtReg = I->getOperand(0).getReg();
393 if (!MRI.constrainRegClass(VirtReg, RC))
394 llvm_unreachable("Incompatible live-in register class.");
395 return VirtReg;
396 }
397
398 // No luck, create a virtual register.
399 unsigned VirtReg = MRI.createVirtualRegister(RC);
400 BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
401 .addReg(PhysReg, RegState::Kill);
402 if (!LiveIn)
403 addLiveIn(PhysReg);
404 return VirtReg;
405}
406
Chris Lattner94866be2006-10-24 00:02:26 +0000407void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000408 getParent()->splice(NewAfter->getIterator(), getIterator());
Chris Lattner94866be2006-10-24 00:02:26 +0000409}
410
411void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000412 getParent()->splice(++NewBefore->getIterator(), getIterator());
Chris Lattner94866be2006-10-24 00:02:26 +0000413}
414
Jim Grosbach801b33b2009-11-12 03:55:33 +0000415void MachineBasicBlock::updateTerminator() {
Eric Christopherfc6de422014-08-05 02:39:49 +0000416 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
Jim Grosbach801b33b2009-11-12 03:55:33 +0000417 // A block with no successors has no concerns with fall-through edges.
Chad Rosierdca76512016-05-25 21:53:46 +0000418 if (this->succ_empty())
419 return;
Jim Grosbach801b33b2009-11-12 03:55:33 +0000420
Craig Topperc0196b12014-04-14 00:51:57 +0000421 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
Jim Grosbach801b33b2009-11-12 03:55:33 +0000422 SmallVector<MachineOperand, 4> Cond;
Cong Hou166e0852015-09-29 19:46:09 +0000423 DebugLoc DL; // FIXME: this is nowhere
Jacques Pienaar71c30a12016-07-15 14:41:04 +0000424 bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
Jim Grosbach801b33b2009-11-12 03:55:33 +0000425 (void) B;
426 assert(!B && "UpdateTerminators requires analyzable predecessors!");
427 if (Cond.empty()) {
428 if (TBB) {
Chad Rosierdca76512016-05-25 21:53:46 +0000429 // The block has an unconditional branch. If its successor is now its
430 // layout successor, delete the branch.
Jim Grosbach801b33b2009-11-12 03:55:33 +0000431 if (isLayoutSuccessor(TBB))
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000432 TII->removeBranch(*this);
Jim Grosbach801b33b2009-11-12 03:55:33 +0000433 } else {
Chad Rosierdca76512016-05-25 21:53:46 +0000434 // The block has an unconditional fallthrough. If its successor is not its
435 // layout successor, insert a branch. First we have to locate the only
436 // non-landing-pad successor, as that is the fallthrough block.
Chandler Carruthee54feb2011-11-22 13:13:16 +0000437 for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
Reid Kleckner0e288232015-08-27 23:27:47 +0000438 if ((*SI)->isEHPad())
Chandler Carruthee54feb2011-11-22 13:13:16 +0000439 continue;
440 assert(!TBB && "Found more than one non-landing-pad successor!");
441 TBB = *SI;
442 }
Chandler Carruth8c68f1f2011-11-23 08:23:54 +0000443
Chad Rosierdca76512016-05-25 21:53:46 +0000444 // If there is no non-landing-pad successor, the block has no fall-through
445 // edges to be concerned with.
Chandler Carruth8c68f1f2011-11-23 08:23:54 +0000446 if (!TBB)
447 return;
448
449 // Finally update the unconditional successor to be reached via a branch
450 // if it would not be reached by fallthrough.
Jim Grosbach801b33b2009-11-12 03:55:33 +0000451 if (!isLayoutSuccessor(TBB))
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000452 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
Jim Grosbach801b33b2009-11-12 03:55:33 +0000453 }
Chad Rosierdca76512016-05-25 21:53:46 +0000454 return;
455 }
Chandler Carruth1f5580b2012-04-16 22:03:00 +0000456
Chad Rosierdca76512016-05-25 21:53:46 +0000457 if (FBB) {
458 // The block has a non-fallthrough conditional branch. If one of its
459 // successors is its layout successor, rewrite it to a fallthrough
460 // conditional branch.
461 if (isLayoutSuccessor(TBB)) {
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000462 if (TII->reverseBranchCondition(Cond))
Chandler Carruth1f5580b2012-04-16 22:03:00 +0000463 return;
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000464 TII->removeBranch(*this);
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000465 TII->insertBranch(*this, FBB, nullptr, Cond, DL);
Chad Rosierdca76512016-05-25 21:53:46 +0000466 } else if (isLayoutSuccessor(FBB)) {
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000467 TII->removeBranch(*this);
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000468 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
Jim Grosbach801b33b2009-11-12 03:55:33 +0000469 }
Chad Rosierdca76512016-05-25 21:53:46 +0000470 return;
471 }
472
473 // Walk through the successors and find the successor which is not a landing
474 // pad and is not the conditional branch destination (in TBB) as the
475 // fallthrough successor.
476 MachineBasicBlock *FallthroughBB = nullptr;
477 for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
478 if ((*SI)->isEHPad() || *SI == TBB)
479 continue;
480 assert(!FallthroughBB && "Found more than one fallthrough successor.");
481 FallthroughBB = *SI;
482 }
483
Haicheng Wub71b2f62016-07-03 19:14:17 +0000484 if (!FallthroughBB) {
485 if (canFallThrough()) {
486 // We fallthrough to the same basic block as the conditional jump targets.
487 // Remove the conditional jump, leaving unconditional fallthrough.
488 // FIXME: This does not seem like a reasonable pattern to support, but it
489 // has been seen in the wild coming out of degenerate ARM test cases.
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000490 TII->removeBranch(*this);
Haicheng Wub71b2f62016-07-03 19:14:17 +0000491
492 // Finally update the unconditional successor to be reached via a branch if
493 // it would not be reached by fallthrough.
494 if (!isLayoutSuccessor(TBB))
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000495 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
Haicheng Wub71b2f62016-07-03 19:14:17 +0000496 return;
497 }
Chad Rosierdca76512016-05-25 21:53:46 +0000498
Haicheng Wub71b2f62016-07-03 19:14:17 +0000499 // We enter here iff exactly one successor is TBB which cannot fallthrough
500 // and the rest successors if any are EHPads. In this case, we need to
501 // change the conditional branch into unconditional branch.
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000502 TII->removeBranch(*this);
Haicheng Wub71b2f62016-07-03 19:14:17 +0000503 Cond.clear();
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000504 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
Chad Rosierdca76512016-05-25 21:53:46 +0000505 return;
506 }
507
508 // The block has a fallthrough conditional branch.
509 if (isLayoutSuccessor(TBB)) {
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000510 if (TII->reverseBranchCondition(Cond)) {
Chad Rosierdca76512016-05-25 21:53:46 +0000511 // We can't reverse the condition, add an unconditional branch.
512 Cond.clear();
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000513 TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
Chad Rosierdca76512016-05-25 21:53:46 +0000514 return;
515 }
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000516 TII->removeBranch(*this);
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000517 TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
Chad Rosierdca76512016-05-25 21:53:46 +0000518 } else if (!isLayoutSuccessor(FallthroughBB)) {
Matt Arsenault1b9fc8e2016-09-14 20:43:16 +0000519 TII->removeBranch(*this);
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000520 TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
Jim Grosbach801b33b2009-11-12 03:55:33 +0000521 }
522}
Chris Lattner94866be2006-10-24 00:02:26 +0000523
Cong Houc1069892015-12-13 09:26:17 +0000524void MachineBasicBlock::validateSuccProbs() const {
525#ifndef NDEBUG
526 int64_t Sum = 0;
527 for (auto Prob : Probs)
528 Sum += Prob.getNumerator();
529 // Due to precision issue, we assume that the sum of probabilities is one if
530 // the difference between the sum of their numerators and the denominator is
531 // no greater than the number of successors.
Cong Houc00e65a2015-12-13 17:00:25 +0000532 assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
Cong Houc1069892015-12-13 09:26:17 +0000533 Probs.size() &&
534 "The sum of successors's probabilities exceeds one.");
535#endif // NDEBUG
536}
537
Cong Hou23a3bf02015-11-04 21:37:58 +0000538void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
539 BranchProbability Prob) {
540 // Probability list is either empty (if successor list isn't empty, this means
541 // disabled optimization) or has the same size as successor list.
Cong Hou4aef7ef2015-12-01 11:05:39 +0000542 if (!(Probs.empty() && !Successors.empty()))
Cong Hou23a3bf02015-11-04 21:37:58 +0000543 Probs.push_back(Prob);
544 Successors.push_back(Succ);
545 Succ->addPredecessor(this);
546}
547
548void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
549 // We need to make sure probability list is either empty or has the same size
550 // of successor list. When this function is called, we can safely delete all
551 // probability in the list.
552 Probs.clear();
553 Successors.push_back(Succ);
554 Succ->addPredecessor(this);
555}
556
Cong Houc1069892015-12-13 09:26:17 +0000557void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
558 bool NormalizeSuccProbs) {
David Majnemer0d955d02016-08-11 22:21:41 +0000559 succ_iterator I = find(Successors, Succ);
Cong Houc1069892015-12-13 09:26:17 +0000560 removeSuccessor(I, NormalizeSuccProbs);
Chris Lattner4336b872004-10-26 15:43:42 +0000561}
562
Jakub Staszakfeadd432011-06-16 18:01:17 +0000563MachineBasicBlock::succ_iterator
Cong Houc1069892015-12-13 09:26:17 +0000564MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
Chris Lattner4336b872004-10-26 15:43:42 +0000565 assert(I != Successors.end() && "Not a current successor!");
Jakub Staszak12a43bd2011-06-16 20:22:37 +0000566
Cong Hou23a3bf02015-11-04 21:37:58 +0000567 // If probability list is empty it means we don't use it (disabled
568 // optimization).
569 if (!Probs.empty()) {
570 probability_iterator WI = getProbabilityIterator(I);
571 Probs.erase(WI);
Cong Houc1069892015-12-13 09:26:17 +0000572 if (NormalizeSuccProbs)
573 normalizeSuccProbs();
Cong Hou23a3bf02015-11-04 21:37:58 +0000574 }
575
Chris Lattner4336b872004-10-26 15:43:42 +0000576 (*I)->removePredecessor(this);
Dan Gohmanf87dc922009-01-08 22:19:34 +0000577 return Successors.erase(I);
Chris Lattner4336b872004-10-26 15:43:42 +0000578}
579
Jakub Staszak12a43bd2011-06-16 20:22:37 +0000580void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
581 MachineBasicBlock *New) {
Jakob Stoklund Olesen8c28ac92012-08-10 03:23:27 +0000582 if (Old == New)
583 return;
Jakub Staszak12a43bd2011-06-16 20:22:37 +0000584
Jakob Stoklund Olesen8c28ac92012-08-10 03:23:27 +0000585 succ_iterator E = succ_end();
586 succ_iterator NewI = E;
587 succ_iterator OldI = E;
588 for (succ_iterator I = succ_begin(); I != E; ++I) {
589 if (*I == Old) {
590 OldI = I;
591 if (NewI != E)
592 break;
593 }
594 if (*I == New) {
595 NewI = I;
596 if (OldI != E)
597 break;
598 }
599 }
600 assert(OldI != E && "Old is not a successor of this block");
Jakob Stoklund Olesen8c28ac92012-08-10 03:23:27 +0000601
602 // If New isn't already a successor, let it take Old's place.
603 if (NewI == E) {
Cong Hou11c14202015-11-18 01:45:10 +0000604 Old->removePredecessor(this);
Jakob Stoklund Olesen8c28ac92012-08-10 03:23:27 +0000605 New->addPredecessor(this);
606 *OldI = New;
607 return;
Jakub Staszak12a43bd2011-06-16 20:22:37 +0000608 }
609
Jakob Stoklund Olesen8c28ac92012-08-10 03:23:27 +0000610 // New is already a successor.
Cong Hou23a3bf02015-11-04 21:37:58 +0000611 // Update its probability instead of adding a duplicate edge.
Cong Houd97c1002015-12-01 05:29:22 +0000612 if (!Probs.empty()) {
613 auto ProbIter = getProbabilityIterator(NewI);
614 if (!ProbIter->isUnknown())
615 *ProbIter += *getProbabilityIterator(OldI);
616 }
Cong Hou11c14202015-11-18 01:45:10 +0000617 removeSuccessor(OldI);
Jakub Staszak12a43bd2011-06-16 20:22:37 +0000618}
619
Cong Hou166e0852015-09-29 19:46:09 +0000620void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
621 Predecessors.push_back(Pred);
Chris Lattner4336b872004-10-26 15:43:42 +0000622}
623
Cong Hou166e0852015-09-29 19:46:09 +0000624void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
David Majnemer0d955d02016-08-11 22:21:41 +0000625 pred_iterator I = find(Predecessors, Pred);
Chris Lattner4336b872004-10-26 15:43:42 +0000626 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
627 Predecessors.erase(I);
628}
Evan Chenga92b2b32007-05-17 23:58:53 +0000629
Cong Hou166e0852015-09-29 19:46:09 +0000630void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
631 if (this == FromMBB)
Mon P Wang3e583932008-05-05 19:05:59 +0000632 return;
Jakub Staszakfeadd432011-06-16 18:01:17 +0000633
Cong Hou166e0852015-09-29 19:46:09 +0000634 while (!FromMBB->succ_empty()) {
635 MachineBasicBlock *Succ = *FromMBB->succ_begin();
Jakub Staszak12a43bd2011-06-16 20:22:37 +0000636
Cong Houd97c1002015-12-01 05:29:22 +0000637 // If probability list is empty it means we don't use it (disabled optimization).
638 if (!FromMBB->Probs.empty()) {
639 auto Prob = *FromMBB->Probs.begin();
640 addSuccessor(Succ, Prob);
641 } else
642 addSuccessorWithoutProb(Succ);
Jakub Staszak12a43bd2011-06-16 20:22:37 +0000643
Cong Hou166e0852015-09-29 19:46:09 +0000644 FromMBB->removeSuccessor(Succ);
Dan Gohman34396292010-07-06 20:24:04 +0000645 }
646}
647
648void
Cong Hou166e0852015-09-29 19:46:09 +0000649MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
650 if (this == FromMBB)
Dan Gohman34396292010-07-06 20:24:04 +0000651 return;
Jakub Staszakfeadd432011-06-16 18:01:17 +0000652
Cong Hou166e0852015-09-29 19:46:09 +0000653 while (!FromMBB->succ_empty()) {
654 MachineBasicBlock *Succ = *FromMBB->succ_begin();
Cong Houd97c1002015-12-01 05:29:22 +0000655 if (!FromMBB->Probs.empty()) {
656 auto Prob = *FromMBB->Probs.begin();
657 addSuccessor(Succ, Prob);
658 } else
659 addSuccessorWithoutProb(Succ);
Cong Hou166e0852015-09-29 19:46:09 +0000660 FromMBB->removeSuccessor(Succ);
Dan Gohman34396292010-07-06 20:24:04 +0000661
662 // Fix up any PHI nodes in the successor.
Evan Cheng7fae11b2011-12-14 02:11:42 +0000663 for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(),
664 ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
Dan Gohman34396292010-07-06 20:24:04 +0000665 for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
666 MachineOperand &MO = MI->getOperand(i);
Cong Hou166e0852015-09-29 19:46:09 +0000667 if (MO.getMBB() == FromMBB)
Dan Gohman34396292010-07-06 20:24:04 +0000668 MO.setMBB(this);
669 }
670 }
Cong Houc1069892015-12-13 09:26:17 +0000671 normalizeSuccProbs();
Mon P Wang3e583932008-05-05 19:05:59 +0000672}
673
Jakob Stoklund Olesenfee94ca2012-07-30 17:36:47 +0000674bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
David Majnemer42531262016-08-12 03:55:06 +0000675 return is_contained(predecessors(), MBB);
Jakob Stoklund Olesenfee94ca2012-07-30 17:36:47 +0000676}
677
Dan Gohmanff62c622009-03-30 20:06:29 +0000678bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
David Majnemer42531262016-08-12 03:55:06 +0000679 return is_contained(successors(), MBB);
Evan Chenga92b2b32007-05-17 23:58:53 +0000680}
Evan Chengdf757852007-06-04 06:44:01 +0000681
Dan Gohmanff62c622009-03-30 20:06:29 +0000682bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
Dan Gohmana78bae32008-10-02 22:09:09 +0000683 MachineFunction::const_iterator I(this);
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000684 return std::next(I) == MachineFunction::const_iterator(MBB);
Dan Gohmana78bae32008-10-02 22:09:09 +0000685}
686
Bob Wilson2d4ff122009-11-26 00:32:21 +0000687bool MachineBasicBlock::canFallThrough() {
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000688 MachineFunction::iterator Fallthrough = getIterator();
Bob Wilson2d4ff122009-11-26 00:32:21 +0000689 ++Fallthrough;
690 // If FallthroughBlock is off the end of the function, it can't fall through.
691 if (Fallthrough == getParent()->end())
692 return false;
693
694 // If FallthroughBlock isn't a successor, no fallthrough is possible.
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000695 if (!isSuccessor(&*Fallthrough))
Bob Wilson2d4ff122009-11-26 00:32:21 +0000696 return false;
697
Dan Gohman0b44cb02009-12-05 00:32:59 +0000698 // Analyze the branches, if any, at the end of the block.
Craig Topperc0196b12014-04-14 00:51:57 +0000699 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
Dan Gohman0b44cb02009-12-05 00:32:59 +0000700 SmallVector<MachineOperand, 4> Cond;
Eric Christopherfc6de422014-08-05 02:39:49 +0000701 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
Jacques Pienaar71c30a12016-07-15 14:41:04 +0000702 if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
Dan Gohman0b44cb02009-12-05 00:32:59 +0000703 // If we couldn't analyze the branch, examine the last instruction.
704 // If the block doesn't end in a known control barrier, assume fallthrough
Chad Rosier1a1531d2012-01-26 18:24:25 +0000705 // is possible. The isPredicated check is needed because this code can be
Dan Gohman0b44cb02009-12-05 00:32:59 +0000706 // called during IfConversion, where an instruction which is normally a
Chad Rosier9b61cf32012-01-26 20:19:05 +0000707 // Barrier is predicated and thus no longer an actual control barrier.
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +0000708 return empty() || !back().isBarrier() || TII->isPredicated(back());
Dan Gohman0b44cb02009-12-05 00:32:59 +0000709 }
Bob Wilson2d4ff122009-11-26 00:32:21 +0000710
711 // If there is no branch, control always falls through.
Craig Topperc0196b12014-04-14 00:51:57 +0000712 if (!TBB) return true;
Bob Wilson2d4ff122009-11-26 00:32:21 +0000713
714 // If there is some explicit branch to the fallthrough block, it can obviously
715 // reach, even though the branch should get folded to fall through implicitly.
716 if (MachineFunction::iterator(TBB) == Fallthrough ||
717 MachineFunction::iterator(FBB) == Fallthrough)
718 return true;
719
720 // If it's an unconditional branch to some block not the fall through, it
721 // doesn't fall through.
722 if (Cond.empty()) return false;
723
724 // Otherwise, if it is conditional and has no explicit false block, it falls
725 // through.
Craig Topperc0196b12014-04-14 00:51:57 +0000726 return FBB == nullptr;
Bob Wilson2d4ff122009-11-26 00:32:21 +0000727}
728
Quentin Colombet23341a82016-04-21 21:01:13 +0000729MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ,
730 Pass &P) {
Quentin Colombet77e18782016-04-21 20:46:27 +0000731 if (!canSplitCriticalEdge(Succ))
Craig Topperc0196b12014-04-14 00:51:57 +0000732 return nullptr;
Evan Cheng2d14d8a2012-04-24 19:06:55 +0000733
Dan Gohman3570f812010-06-22 17:25:57 +0000734 MachineFunction *MF = getParent();
Cong Hou166e0852015-09-29 19:46:09 +0000735 DebugLoc DL; // FIXME: this is nowhere
Dan Gohman3570f812010-06-22 17:25:57 +0000736
Dan Gohman3570f812010-06-22 17:25:57 +0000737 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000738 MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
Evan Chenga6848242010-08-17 17:15:14 +0000739 DEBUG(dbgs() << "Splitting critical edge:"
Dan Gohman3570f812010-06-22 17:25:57 +0000740 " BB#" << getNumber()
741 << " -- BB#" << NMBB->getNumber()
742 << " -- BB#" << Succ->getNumber() << '\n');
Cameron Zwarichcdcab382013-02-12 03:49:20 +0000743
Quentin Colombet23341a82016-04-21 21:01:13 +0000744 LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
745 SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
Cameron Zwarichcdcab382013-02-12 03:49:20 +0000746 if (LIS)
747 LIS->insertMBBInMaps(NMBB);
748 else if (Indexes)
Cameron Zwarich21beaf62013-02-10 23:29:54 +0000749 Indexes->insertMBBInMaps(NMBB);
Dan Gohman3570f812010-06-22 17:25:57 +0000750
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000751 // On some targets like Mips, branches may kill virtual registers. Make sure
752 // that LiveVariables is properly updated after updateTerminator replaces the
753 // terminators.
Quentin Colombet23341a82016-04-21 21:01:13 +0000754 LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000755
756 // Collect a list of virtual registers killed by the terminators.
757 SmallVector<unsigned, 4> KilledRegs;
758 if (LV)
Evan Cheng7fae11b2011-12-14 02:11:42 +0000759 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
Evan Cheng2a81dd42011-12-06 22:12:01 +0000760 I != E; ++I) {
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000761 MachineInstr *MI = &*I;
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000762 for (MachineInstr::mop_iterator OI = MI->operands_begin(),
763 OE = MI->operands_end(); OI != OE; ++OI) {
Lang Hamesedeea172012-02-09 05:59:36 +0000764 if (!OI->isReg() || OI->getReg() == 0 ||
765 !OI->isUse() || !OI->isKill() || OI->isUndef())
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000766 continue;
767 unsigned Reg = OI->getReg();
Lang Hamesedeea172012-02-09 05:59:36 +0000768 if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
Duncan P. N. Exon Smithd26fdc82016-07-01 01:51:32 +0000769 LV->getVarInfo(Reg).removeKill(*MI)) {
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000770 KilledRegs.push_back(Reg);
771 DEBUG(dbgs() << "Removing terminator kill: " << *MI);
772 OI->setIsKill(false);
773 }
774 }
775 }
776
Cameron Zwarichbfebb412013-02-17 00:10:44 +0000777 SmallVector<unsigned, 4> UsedRegs;
778 if (LIS) {
779 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
780 I != E; ++I) {
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000781 MachineInstr *MI = &*I;
Cameron Zwarichbfebb412013-02-17 00:10:44 +0000782
783 for (MachineInstr::mop_iterator OI = MI->operands_begin(),
784 OE = MI->operands_end(); OI != OE; ++OI) {
785 if (!OI->isReg() || OI->getReg() == 0)
786 continue;
787
788 unsigned Reg = OI->getReg();
David Majnemer0d955d02016-08-11 22:21:41 +0000789 if (!is_contained(UsedRegs, Reg))
Cameron Zwarichbfebb412013-02-17 00:10:44 +0000790 UsedRegs.push_back(Reg);
791 }
792 }
793 }
794
Dan Gohman3570f812010-06-22 17:25:57 +0000795 ReplaceUsesOfBlockWith(Succ, NMBB);
Cameron Zwarichba378ce2013-02-11 09:24:45 +0000796
797 // If updateTerminator() removes instructions, we need to remove them from
798 // SlotIndexes.
799 SmallVector<MachineInstr*, 4> Terminators;
800 if (Indexes) {
801 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
802 I != E; ++I)
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000803 Terminators.push_back(&*I);
Cameron Zwarichba378ce2013-02-11 09:24:45 +0000804 }
805
Dan Gohman3570f812010-06-22 17:25:57 +0000806 updateTerminator();
807
Cameron Zwarichba378ce2013-02-11 09:24:45 +0000808 if (Indexes) {
809 SmallVector<MachineInstr*, 4> NewTerminators;
810 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
811 I != E; ++I)
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000812 NewTerminators.push_back(&*I);
Cameron Zwarichba378ce2013-02-11 09:24:45 +0000813
814 for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
815 E = Terminators.end(); I != E; ++I) {
David Majnemer0d955d02016-08-11 22:21:41 +0000816 if (!is_contained(NewTerminators, *I))
817 Indexes->removeMachineInstrFromMaps(**I);
Cameron Zwarichba378ce2013-02-11 09:24:45 +0000818 }
819 }
820
Dan Gohman3570f812010-06-22 17:25:57 +0000821 // Insert unconditional "jump Succ" instruction in NMBB if necessary.
822 NMBB->addSuccessor(Succ);
823 if (!NMBB->isLayoutSuccessor(Succ)) {
Quentin Colombet77e18782016-04-21 20:46:27 +0000824 SmallVector<MachineOperand, 4> Cond;
825 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
Matt Arsenaulte8e0f5c2016-09-14 17:24:15 +0000826 TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
Cameron Zwarich21beaf62013-02-10 23:29:54 +0000827
828 if (Indexes) {
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000829 for (MachineInstr &MI : NMBB->instrs()) {
Cameron Zwarich21beaf62013-02-10 23:29:54 +0000830 // Some instructions may have been moved to NMBB by updateTerminator(),
831 // so we first remove any instruction that already has an index.
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000832 if (Indexes->hasIndex(MI))
833 Indexes->removeMachineInstrFromMaps(MI);
834 Indexes->insertMachineInstrInMaps(MI);
Cameron Zwarich21beaf62013-02-10 23:29:54 +0000835 }
836 }
Dan Gohman3570f812010-06-22 17:25:57 +0000837 }
838
839 // Fix PHI nodes in Succ so they refer to NMBB instead of this
Evan Cheng7fae11b2011-12-14 02:11:42 +0000840 for (MachineBasicBlock::instr_iterator
841 i = Succ->instr_begin(),e = Succ->instr_end();
842 i != e && i->isPHI(); ++i)
Dan Gohman3570f812010-06-22 17:25:57 +0000843 for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
844 if (i->getOperand(ni+1).getMBB() == this)
845 i->getOperand(ni+1).setMBB(NMBB);
846
Jakob Stoklund Olesen06b6ccf2011-10-14 17:25:46 +0000847 // Inherit live-ins from the successor
Matthias Braund9da1622015-09-09 18:08:03 +0000848 for (const auto &LI : Succ->liveins())
Matthias Braunb2b7ef12015-08-24 22:59:52 +0000849 NMBB->addLiveIn(LI);
Jakob Stoklund Olesen06b6ccf2011-10-14 17:25:46 +0000850
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000851 // Update LiveVariables.
Eric Christopherfc6de422014-08-05 02:39:49 +0000852 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000853 if (LV) {
854 // Restore kills of virtual registers that were killed by the terminators.
855 while (!KilledRegs.empty()) {
856 unsigned Reg = KilledRegs.pop_back_val();
Evan Cheng7fae11b2011-12-14 02:11:42 +0000857 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
Lang Hamesedeea172012-02-09 05:59:36 +0000858 if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000859 continue;
Lang Hamesedeea172012-02-09 05:59:36 +0000860 if (TargetRegisterInfo::isVirtualRegister(Reg))
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +0000861 LV->getVarInfo(Reg).Kills.push_back(&*I);
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000862 DEBUG(dbgs() << "Restored terminator kill: " << *I);
863 break;
864 }
865 }
866 // Update relevant live-through information.
Dan Gohman3570f812010-06-22 17:25:57 +0000867 LV->addNewBlock(NMBB, this, Succ);
Jakob Stoklund Olesendd6fcc42011-05-29 20:10:28 +0000868 }
Dan Gohman3570f812010-06-22 17:25:57 +0000869
Cameron Zwarichcdcab382013-02-12 03:49:20 +0000870 if (LIS) {
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000871 // After splitting the edge and updating SlotIndexes, live intervals may be
872 // in one of two situations, depending on whether this block was the last in
Cong Hou2793e722015-08-10 22:27:10 +0000873 // the function. If the original block was the last in the function, all
874 // live intervals will end prior to the beginning of the new split block. If
875 // the original block was not at the end of the function, all live intervals
876 // will extend to the end of the new split block.
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000877
878 bool isLastMBB =
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000879 std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000880
881 SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
882 SlotIndex PrevIndex = StartIndex.getPrevSlot();
883 SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
884
885 // Find the registers used from NMBB in PHIs in Succ.
886 SmallSet<unsigned, 8> PHISrcRegs;
887 for (MachineBasicBlock::instr_iterator
888 I = Succ->instr_begin(), E = Succ->instr_end();
889 I != E && I->isPHI(); ++I) {
890 for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
891 if (I->getOperand(ni+1).getMBB() == NMBB) {
892 MachineOperand &MO = I->getOperand(ni);
893 unsigned Reg = MO.getReg();
894 PHISrcRegs.insert(Reg);
Cameron Zwarichaf349312013-02-12 03:49:17 +0000895 if (MO.isUndef())
896 continue;
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000897
898 LiveInterval &LI = LIS->getInterval(Reg);
899 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
Cong Hou2793e722015-08-10 22:27:10 +0000900 assert(VNI &&
901 "PHI sources should be live out of their predecessors.");
Matthias Braun13ddb7c2013-10-10 21:28:43 +0000902 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000903 }
904 }
905 }
906
907 MachineRegisterInfo *MRI = &getParent()->getRegInfo();
908 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
909 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
910 if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
911 continue;
912
913 LiveInterval &LI = LIS->getInterval(Reg);
914 if (!LI.liveAt(PrevIndex))
915 continue;
916
Cameron Zwarichaf349312013-02-12 03:49:17 +0000917 bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000918 if (isLiveOut && isLastMBB) {
919 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
920 assert(VNI && "LiveInterval should have VNInfo where it is live.");
Matthias Braun13ddb7c2013-10-10 21:28:43 +0000921 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000922 } else if (!isLiveOut && !isLastMBB) {
Matthias Braun13ddb7c2013-10-10 21:28:43 +0000923 LI.removeSegment(StartIndex, EndIndex);
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000924 }
925 }
Cameron Zwarichbfebb412013-02-17 00:10:44 +0000926
927 // Update all intervals for registers whose uses may have been modified by
928 // updateTerminator().
Cameron Zwarich24955962013-02-17 11:09:00 +0000929 LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
Cameron Zwarichb47fb382013-02-11 09:24:47 +0000930 }
931
Dan Gohman3570f812010-06-22 17:25:57 +0000932 if (MachineDominatorTree *MDT =
Quentin Colombet23341a82016-04-21 21:01:13 +0000933 P.getAnalysisIfAvailable<MachineDominatorTree>())
Quentin Colombetabea99f2014-08-13 21:00:07 +0000934 MDT->recordSplitCriticalEdge(this, Succ, NMBB);
Dan Gohman3570f812010-06-22 17:25:57 +0000935
Quentin Colombet23341a82016-04-21 21:01:13 +0000936 if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
Dan Gohman3570f812010-06-22 17:25:57 +0000937 if (MachineLoop *TIL = MLI->getLoopFor(this)) {
938 // If one or the other blocks were not in a loop, the new block is not
939 // either, and thus LI doesn't need to be updated.
940 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
941 if (TIL == DestLoop) {
942 // Both in the same loop, the NMBB joins loop.
943 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
944 } else if (TIL->contains(DestLoop)) {
945 // Edge from an outer loop to an inner loop. Add to the outer loop.
946 TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
947 } else if (DestLoop->contains(TIL)) {
948 // Edge from an inner loop to an outer loop. Add to the outer loop.
949 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
950 } else {
951 // Edge from two loops with no containment relation. Because these
952 // are natural loops, we know that the destination block must be the
953 // header of its loop (adding a branch into a loop elsewhere would
954 // create an irreducible loop).
955 assert(DestLoop->getHeader() == Succ &&
956 "Should not create irreducible loops!");
957 if (MachineLoop *P = DestLoop->getParentLoop())
958 P->addBasicBlockToLoop(NMBB, MLI->getBase());
959 }
960 }
961 }
962
963 return NMBB;
964}
965
Quentin Colombet77e18782016-04-21 20:46:27 +0000966bool MachineBasicBlock::canSplitCriticalEdge(
967 const MachineBasicBlock *Succ) const {
968 // Splitting the critical edge to a landing pad block is non-trivial. Don't do
969 // it in this generic function.
970 if (Succ->isEHPad())
971 return false;
972
973 const MachineFunction *MF = getParent();
974
975 // Performance might be harmed on HW that implements branching using exec mask
976 // where both sides of the branches are always executed.
977 if (MF->getTarget().requiresStructuredCFG())
978 return false;
979
980 // We may need to update this's terminator, but we can't do that if
981 // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
982 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
983 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
984 SmallVector<MachineOperand, 4> Cond;
985 // AnalyzeBanch should modify this, since we did not allow modification.
Jacques Pienaar71c30a12016-07-15 14:41:04 +0000986 if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
Quentin Colombet77e18782016-04-21 20:46:27 +0000987 /*AllowModify*/ false))
988 return false;
989
990 // Avoid bugpoint weirdness: A block may end with a conditional branch but
991 // jumps to the same MBB is either case. We have duplicate CFG edges in that
992 // case that we can't handle. Since this never happens in properly optimized
993 // code, just skip those edges.
994 if (TBB && TBB == FBB) {
995 DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
996 << getNumber() << '\n');
997 return false;
998 }
999 return true;
1000}
1001
Jakob Stoklund Olesenccfb5fb2012-12-17 23:55:38 +00001002/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1003/// neighboring instructions so the bundle won't be broken by removing MI.
1004static void unbundleSingleMI(MachineInstr *MI) {
1005 // Removing the first instruction in a bundle.
1006 if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1007 MI->unbundleFromSucc();
1008 // Removing the last instruction in a bundle.
1009 if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1010 MI->unbundleFromPred();
1011 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1012 // are already fine.
Evan Cheng7fae11b2011-12-14 02:11:42 +00001013}
1014
Jakob Stoklund Olesenccfb5fb2012-12-17 23:55:38 +00001015MachineBasicBlock::instr_iterator
1016MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
Duncan P. N. Exon Smith0ac8eb92015-10-09 19:23:20 +00001017 unbundleSingleMI(&*I);
Jakob Stoklund Olesenccfb5fb2012-12-17 23:55:38 +00001018 return Insts.erase(I);
1019}
Evan Cheng7fae11b2011-12-14 02:11:42 +00001020
Jakob Stoklund Olesenccfb5fb2012-12-17 23:55:38 +00001021MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1022 unbundleSingleMI(MI);
1023 MI->clearFlag(MachineInstr::BundledPred);
1024 MI->clearFlag(MachineInstr::BundledSucc);
1025 return Insts.remove(MI);
Evan Cheng7fae11b2011-12-14 02:11:42 +00001026}
1027
Jakob Stoklund Olesen422e07b2012-12-18 17:54:53 +00001028MachineBasicBlock::instr_iterator
1029MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
1030 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1031 "Cannot insert instruction with bundle flags");
1032 // Set the bundle flags when inserting inside a bundle.
1033 if (I != instr_end() && I->isBundledWithPred()) {
1034 MI->setFlag(MachineInstr::BundledPred);
1035 MI->setFlag(MachineInstr::BundledSucc);
1036 }
1037 return Insts.insert(I, MI);
1038}
1039
Cong Hou2a02c1c2015-08-12 21:18:54 +00001040/// This method unlinks 'this' from the containing function, and returns it, but
1041/// does not delete it.
Dan Gohman3b460302008-07-07 23:14:23 +00001042MachineBasicBlock *MachineBasicBlock::removeFromParent() {
1043 assert(getParent() && "Not embedded in a function!");
1044 getParent()->remove(this);
1045 return this;
1046}
1047
Cong Hou2a02c1c2015-08-12 21:18:54 +00001048/// This method unlinks 'this' from the containing function, and deletes it.
Dan Gohman3b460302008-07-07 23:14:23 +00001049void MachineBasicBlock::eraseFromParent() {
1050 assert(getParent() && "Not embedded in a function!");
1051 getParent()->erase(this);
1052}
1053
Cong Hou2a02c1c2015-08-12 21:18:54 +00001054/// Given a machine basic block that branched to 'Old', change the code and CFG
1055/// so that it branches to 'New' instead.
Evan Chengdf757852007-06-04 06:44:01 +00001056void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1057 MachineBasicBlock *New) {
1058 assert(Old != New && "Cannot replace self with self!");
1059
Evan Cheng7fae11b2011-12-14 02:11:42 +00001060 MachineBasicBlock::instr_iterator I = instr_end();
1061 while (I != instr_begin()) {
Evan Chengdf757852007-06-04 06:44:01 +00001062 --I;
Evan Cheng7f8e5632011-12-07 07:15:52 +00001063 if (!I->isTerminator()) break;
Evan Chengdf757852007-06-04 06:44:01 +00001064
1065 // Scan the operands of this machine instruction, replacing any uses of Old
1066 // with New.
1067 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
Dan Gohman0d1e9a82008-10-03 15:45:36 +00001068 if (I->getOperand(i).isMBB() &&
Dan Gohman38453ee2008-09-13 17:58:21 +00001069 I->getOperand(i).getMBB() == Old)
Chris Lattnera5bb3702007-12-30 23:10:15 +00001070 I->getOperand(i).setMBB(New);
Evan Chengdf757852007-06-04 06:44:01 +00001071 }
1072
Dan Gohmanbb2f1072009-05-05 21:10:19 +00001073 // Update the successor information.
Jakub Staszak12a43bd2011-06-16 20:22:37 +00001074 replaceSuccessor(Old, New);
Evan Chengdf757852007-06-04 06:44:01 +00001075}
1076
Cong Hou2a02c1c2015-08-12 21:18:54 +00001077/// Various pieces of code can cause excess edges in the CFG to be inserted. If
1078/// we have proven that MBB can only branch to DestA and DestB, remove any other
1079/// MBB successors from the CFG. DestA and DestB can be null.
Jakub Staszakfeadd432011-06-16 18:01:17 +00001080///
Chris Lattner574e7162007-12-31 04:56:33 +00001081/// Besides DestA and DestB, retain other edges leading to LandingPads
1082/// (currently there can be only one; we don't check or require that here).
Evan Cheng2afd7022007-06-18 22:43:58 +00001083/// Note it is possible that DestA and/or DestB are LandingPads.
1084bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
1085 MachineBasicBlock *DestB,
Cong Hou166e0852015-09-29 19:46:09 +00001086 bool IsCond) {
Bill Wendling2d5967d2009-12-16 00:08:36 +00001087 // The values of DestA and DestB frequently come from a call to the
1088 // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1089 // values from there.
1090 //
1091 // 1. If both DestA and DestB are null, then the block ends with no branches
1092 // (it falls through to its successor).
Cong Hou166e0852015-09-29 19:46:09 +00001093 // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
Bill Wendling2d5967d2009-12-16 00:08:36 +00001094 // with only an unconditional branch.
Cong Hou166e0852015-09-29 19:46:09 +00001095 // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
Bill Wendling2d5967d2009-12-16 00:08:36 +00001096 // with a conditional branch that falls through to a successor (DestB).
Cong Hou166e0852015-09-29 19:46:09 +00001097 // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
Bill Wendling2d5967d2009-12-16 00:08:36 +00001098 // conditional branch followed by an unconditional branch. DestA is the
1099 // 'true' destination and DestB is the 'false' destination.
1100
Bill Wendling95643402010-04-01 00:00:43 +00001101 bool Changed = false;
Evan Cheng2afd7022007-06-18 22:43:58 +00001102
Duncan P. N. Exon Smith41cf73c2016-08-16 21:46:03 +00001103 MachineBasicBlock *FallThru = getNextNode();
Bill Wendling95643402010-04-01 00:00:43 +00001104
Craig Topperc0196b12014-04-14 00:51:57 +00001105 if (!DestA && !DestB) {
Bill Wendling95643402010-04-01 00:00:43 +00001106 // Block falls through to successor.
Duncan P. N. Exon Smith41cf73c2016-08-16 21:46:03 +00001107 DestA = FallThru;
1108 DestB = FallThru;
Craig Topperc0196b12014-04-14 00:51:57 +00001109 } else if (DestA && !DestB) {
Cong Hou166e0852015-09-29 19:46:09 +00001110 if (IsCond)
Bill Wendling95643402010-04-01 00:00:43 +00001111 // Block ends in conditional jump that falls through to successor.
Duncan P. N. Exon Smith41cf73c2016-08-16 21:46:03 +00001112 DestB = FallThru;
Evan Cheng2afd7022007-06-18 22:43:58 +00001113 } else {
Cong Hou166e0852015-09-29 19:46:09 +00001114 assert(DestA && DestB && IsCond &&
Bill Wendling95643402010-04-01 00:00:43 +00001115 "CFG in a bad state. Cannot correct CFG edges");
Evan Cheng2afd7022007-06-18 22:43:58 +00001116 }
Bill Wendling95643402010-04-01 00:00:43 +00001117
1118 // Remove superfluous edges. I.e., those which aren't destinations of this
1119 // basic block, duplicate edges, or landing pads.
1120 SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
Evan Cheng2afd7022007-06-18 22:43:58 +00001121 MachineBasicBlock::succ_iterator SI = succ_begin();
Evan Cheng2afd7022007-06-18 22:43:58 +00001122 while (SI != succ_end()) {
Bill Wendling2d5967d2009-12-16 00:08:36 +00001123 const MachineBasicBlock *MBB = *SI;
David Blaikie70573dc2014-11-19 07:49:26 +00001124 if (!SeenMBBs.insert(MBB).second ||
Reid Kleckner0e288232015-08-27 23:27:47 +00001125 (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
Bill Wendling95643402010-04-01 00:00:43 +00001126 // This is a superfluous edge, remove it.
Bill Wendlingfa9810d2010-03-31 23:26:26 +00001127 SI = removeSuccessor(SI);
Bill Wendling95643402010-04-01 00:00:43 +00001128 Changed = true;
1129 } else {
1130 ++SI;
Evan Cheng2afd7022007-06-18 22:43:58 +00001131 }
1132 }
Bill Wendling2d5967d2009-12-16 00:08:36 +00001133
Cong Houc1069892015-12-13 09:26:17 +00001134 if (Changed)
1135 normalizeSuccProbs();
Bill Wendling95643402010-04-01 00:00:43 +00001136 return Changed;
Evan Cheng2afd7022007-06-18 22:43:58 +00001137}
Evan Cheng57be2f22009-11-17 19:19:59 +00001138
Cong Hou2a02c1c2015-08-12 21:18:54 +00001139/// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1140/// instructions. Return UnknownLoc if there is none.
Dale Johannesenc5db5992010-01-20 21:36:02 +00001141DebugLoc
Evan Cheng7fae11b2011-12-14 02:11:42 +00001142MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
Dale Johannesenc5db5992010-01-20 21:36:02 +00001143 DebugLoc DL;
Evan Cheng7fae11b2011-12-14 02:11:42 +00001144 instr_iterator E = instr_end();
Evan Cheng2a81dd42011-12-06 22:12:01 +00001145 if (MBBI == E)
1146 return DL;
1147
1148 // Skip debug declarations, we don't want a DebugLoc from them.
1149 while (MBBI != E && MBBI->isDebugValue())
1150 MBBI++;
1151 if (MBBI != E)
1152 DL = MBBI->getDebugLoc();
Dale Johannesenc5db5992010-01-20 21:36:02 +00001153 return DL;
1154}
1155
Cong Houd97c1002015-12-01 05:29:22 +00001156/// Return probability of the edge from this block to MBB.
Cong Hou23a3bf02015-11-04 21:37:58 +00001157BranchProbability
1158MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
Cong Hou4aef7ef2015-12-01 11:05:39 +00001159 if (Probs.empty())
Cong Hou23a3bf02015-11-04 21:37:58 +00001160 return BranchProbability(1, succ_size());
1161
Cong Hou4aef7ef2015-12-01 11:05:39 +00001162 const auto &Prob = *getProbabilityIterator(Succ);
1163 if (Prob.isUnknown()) {
1164 // For unknown probabilities, collect the sum of all known ones, and evenly
1165 // ditribute the complemental of the sum to each unknown probability.
1166 unsigned KnownProbNum = 0;
1167 auto Sum = BranchProbability::getZero();
1168 for (auto &P : Probs) {
1169 if (!P.isUnknown()) {
1170 Sum += P;
1171 KnownProbNum++;
1172 }
1173 }
1174 return Sum.getCompl() / (Probs.size() - KnownProbNum);
1175 } else
1176 return Prob;
Manman Renb6819182014-01-29 23:18:47 +00001177}
1178
Cong Hou23a3bf02015-11-04 21:37:58 +00001179/// Set successor probability of a given iterator.
1180void MachineBasicBlock::setSuccProbability(succ_iterator I,
1181 BranchProbability Prob) {
1182 assert(!Prob.isUnknown());
Cong Houd97c1002015-12-01 05:29:22 +00001183 if (Probs.empty())
Cong Hou23a3bf02015-11-04 21:37:58 +00001184 return;
1185 *getProbabilityIterator(I) = Prob;
Cong Hou23a3bf02015-11-04 21:37:58 +00001186}
1187
Hans Wennborg1dbaf672015-12-01 03:49:42 +00001188/// Return probability iterator corresonding to the I successor iterator
1189MachineBasicBlock::const_probability_iterator
1190MachineBasicBlock::getProbabilityIterator(
1191 MachineBasicBlock::const_succ_iterator I) const {
Cong Houfa1917c2015-12-01 00:02:51 +00001192 assert(Probs.size() == Successors.size() && "Async probability list!");
1193 const size_t index = std::distance(Successors.begin(), I);
1194 assert(index < Probs.size() && "Not a current successor!");
1195 return Probs.begin() + index;
1196}
1197
Cong Houd97c1002015-12-01 05:29:22 +00001198/// Return probability iterator corresonding to the I successor iterator.
1199MachineBasicBlock::probability_iterator
1200MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1201 assert(Probs.size() == Successors.size() && "Async probability list!");
1202 const size_t index = std::distance(Successors.begin(), I);
1203 assert(index < Probs.size() && "Not a current successor!");
1204 return Probs.begin() + index;
1205}
1206
James Molloyc747cda2012-09-12 10:18:23 +00001207/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1208/// as of just before "MI".
Junmo Park12386102016-01-07 10:26:32 +00001209///
James Molloyc747cda2012-09-12 10:18:23 +00001210/// Search is localised to a neighborhood of
1211/// Neighborhood instructions before (searching for defs or kills) and N
1212/// instructions after (searching just for defs) MI.
1213MachineBasicBlock::LivenessQueryResult
1214MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
Matthias Braun07a07ba2015-05-27 05:12:39 +00001215 unsigned Reg, const_iterator Before,
1216 unsigned Neighborhood) const {
James Molloyc747cda2012-09-12 10:18:23 +00001217 unsigned N = Neighborhood;
James Molloyc747cda2012-09-12 10:18:23 +00001218
Matthias Braun07a07ba2015-05-27 05:12:39 +00001219 // Start by searching backwards from Before, looking for kills, reads or defs.
1220 const_iterator I(Before);
James Molloyc747cda2012-09-12 10:18:23 +00001221 // If this is the first insn in the block, don't search backwards.
Matthias Braun07a07ba2015-05-27 05:12:39 +00001222 if (I != begin()) {
James Molloyc747cda2012-09-12 10:18:23 +00001223 do {
1224 --I;
1225
Matthias Braun60d69e22015-12-11 19:42:09 +00001226 MachineOperandIteratorBase::PhysRegInfo Info =
Duncan P. N. Exon Smithf9ab4162016-02-27 17:05:33 +00001227 ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
James Molloyc747cda2012-09-12 10:18:23 +00001228
Matthias Braun60d69e22015-12-11 19:42:09 +00001229 // Defs happen after uses so they take precedence if both are present.
Tim Northoverdd219d02012-11-20 09:56:11 +00001230
Matthias Braun60d69e22015-12-11 19:42:09 +00001231 // Register is dead after a dead def of the full register.
1232 if (Info.DeadDef)
James Molloyc747cda2012-09-12 10:18:23 +00001233 return LQR_Dead;
Matthias Braun60d69e22015-12-11 19:42:09 +00001234 // Register is (at least partially) live after a def.
Quentin Colombet08e79992016-04-26 23:14:29 +00001235 if (Info.Defined) {
1236 if (!Info.PartialDeadDef)
1237 return LQR_Live;
1238 // As soon as we saw a partial definition (dead or not),
1239 // we cannot tell if the value is partial live without
1240 // tracking the lanemasks. We are not going to do this,
1241 // so fall back on the remaining of the analysis.
1242 break;
1243 }
Matthias Braun60d69e22015-12-11 19:42:09 +00001244 // Register is dead after a full kill or clobber and no def.
1245 if (Info.Killed || Info.Clobbered)
1246 return LQR_Dead;
1247 // Register must be live if we read it.
1248 if (Info.Read)
1249 return LQR_Live;
Matthias Braun07a07ba2015-05-27 05:12:39 +00001250 } while (I != begin() && --N > 0);
James Molloyc747cda2012-09-12 10:18:23 +00001251 }
1252
1253 // Did we get to the start of the block?
Matthias Braun07a07ba2015-05-27 05:12:39 +00001254 if (I == begin()) {
James Molloyc747cda2012-09-12 10:18:23 +00001255 // If so, the register's state is definitely defined by the live-in state.
Matthias Braun60d69e22015-12-11 19:42:09 +00001256 for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1257 ++RAI)
Matthias Braun07a07ba2015-05-27 05:12:39 +00001258 if (isLiveIn(*RAI))
Matthias Braun60d69e22015-12-11 19:42:09 +00001259 return LQR_Live;
James Molloyc747cda2012-09-12 10:18:23 +00001260
1261 return LQR_Dead;
1262 }
1263
1264 N = Neighborhood;
1265
Matthias Braun07a07ba2015-05-27 05:12:39 +00001266 // Try searching forwards from Before, looking for reads or defs.
1267 I = const_iterator(Before);
James Molloyc747cda2012-09-12 10:18:23 +00001268 // If this is the last insn in the block, don't search forwards.
Matthias Braun07a07ba2015-05-27 05:12:39 +00001269 if (I != end()) {
1270 for (++I; I != end() && N > 0; ++I, --N) {
Matthias Braun60d69e22015-12-11 19:42:09 +00001271 MachineOperandIteratorBase::PhysRegInfo Info =
Duncan P. N. Exon Smithf9ab4162016-02-27 17:05:33 +00001272 ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
James Molloyc747cda2012-09-12 10:18:23 +00001273
Matthias Braun60d69e22015-12-11 19:42:09 +00001274 // Register is live when we read it here.
1275 if (Info.Read)
1276 return LQR_Live;
1277 // Register is dead if we can fully overwrite or clobber it here.
1278 if (Info.FullyDefined || Info.Clobbered)
James Molloyc747cda2012-09-12 10:18:23 +00001279 return LQR_Dead;
1280 }
1281 }
1282
1283 // At this point we have no idea of the liveness of the register.
1284 return LQR_Unknown;
1285}
Reid Klecknerb8fd1622015-11-06 17:06:38 +00001286
1287const uint32_t *
1288MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1289 // EH funclet entry does not preserve any registers.
1290 return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1291}
1292
1293const uint32_t *
1294MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
1295 // If we see a return block with successors, this must be a funclet return,
1296 // which does not preserve any registers. If there are no successors, we don't
1297 // care what kind of return it is, putting a mask after it is a no-op.
1298 return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1299}