Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 1 | //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | f3ebc3f | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // Collect the sequence of machine instructions for a basic block. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "llvm/CodeGen/MachineBasicBlock.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 15 | #include "llvm/ADT/SmallPtrSet.h" |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 16 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 17 | #include "llvm/CodeGen/LiveVariables.h" |
| 18 | #include "llvm/CodeGen/MachineDominators.h" |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/MachineFunction.h" |
Jakob Stoklund Olesen | 533c3bf | 2013-07-03 23:56:20 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/MachineLoopInfo.h" |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/SlotIndexes.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 24 | #include "llvm/IR/BasicBlock.h" |
| 25 | #include "llvm/IR/DataLayout.h" |
Duncan P. N. Exon Smith | 32692154 | 2015-06-26 22:04:20 +0000 | [diff] [blame] | 26 | #include "llvm/IR/ModuleSlotTracker.h" |
Chris Lattner | d051af7 | 2010-01-26 04:55:51 +0000 | [diff] [blame] | 27 | #include "llvm/MC/MCAsmInfo.h" |
| 28 | #include "llvm/MC/MCContext.h" |
Cong Hou | 663dd01 | 2015-12-13 09:52:14 +0000 | [diff] [blame] | 29 | #include "llvm/Support/DataTypes.h" |
David Greene | 6c56cef | 2010-01-04 23:22:07 +0000 | [diff] [blame] | 30 | #include "llvm/Support/Debug.h" |
Daniel Dunbar | 796e43e | 2009-07-24 10:36:58 +0000 | [diff] [blame] | 31 | #include "llvm/Support/raw_ostream.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 32 | #include "llvm/Target/TargetInstrInfo.h" |
| 33 | #include "llvm/Target/TargetMachine.h" |
| 34 | #include "llvm/Target/TargetRegisterInfo.h" |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 35 | #include "llvm/Target/TargetSubtargetInfo.h" |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 36 | #include <algorithm> |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 37 | using namespace llvm; |
| 38 | |
Chandler Carruth | e96dd89 | 2014-04-21 22:55:11 +0000 | [diff] [blame] | 39 | #define DEBUG_TYPE "codegen" |
| 40 | |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 41 | MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B) |
| 42 | : BB(B), Number(-1), xParent(&MF) { |
Dan Gohman | 804c95d | 2008-07-28 21:51:04 +0000 | [diff] [blame] | 43 | Insts.Parent = this; |
Tanya Lattner | 91fa3a9 | 2004-05-24 07:14:35 +0000 | [diff] [blame] | 44 | } |
Tanya Lattner | 91fa3a9 | 2004-05-24 07:14:35 +0000 | [diff] [blame] | 45 | |
Dan Gohman | 0ece943 | 2008-07-17 23:49:46 +0000 | [diff] [blame] | 46 | MachineBasicBlock::~MachineBasicBlock() { |
Dan Gohman | 0ece943 | 2008-07-17 23:49:46 +0000 | [diff] [blame] | 47 | } |
| 48 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 49 | /// Return the MCSymbol for this basic block. |
Chris Lattner | 29bdac4 | 2010-03-13 21:04:28 +0000 | [diff] [blame] | 50 | MCSymbol *MachineBasicBlock::getSymbol() const { |
Eli Bendersky | 58b04b7 | 2013-04-22 21:21:08 +0000 | [diff] [blame] | 51 | if (!CachedMCSymbol) { |
| 52 | const MachineFunction *MF = getParent(); |
| 53 | MCContext &Ctx = MF->getContext(); |
Mehdi Amini | 36d33fc | 2016-10-01 06:46:33 +0000 | [diff] [blame^] | 54 | auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix(); |
Reid Kleckner | b9204a5 | 2015-11-11 23:09:31 +0000 | [diff] [blame] | 55 | assert(getNumber() >= 0 && "cannot get label for unreachable MBB"); |
Jim Grosbach | 6f48200 | 2015-05-18 18:43:14 +0000 | [diff] [blame] | 56 | CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" + |
Eli Bendersky | 58b04b7 | 2013-04-22 21:21:08 +0000 | [diff] [blame] | 57 | Twine(MF->getFunctionNumber()) + |
| 58 | "_" + Twine(getNumber())); |
| 59 | } |
| 60 | |
| 61 | return CachedMCSymbol; |
Chris Lattner | d051af7 | 2010-01-26 04:55:51 +0000 | [diff] [blame] | 62 | } |
| 63 | |
| 64 | |
Chris Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 65 | raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { |
Daniel Dunbar | 796e43e | 2009-07-24 10:36:58 +0000 | [diff] [blame] | 66 | MBB.print(OS); |
| 67 | return OS; |
| 68 | } |
Tanya Lattner | 91fa3a9 | 2004-05-24 07:14:35 +0000 | [diff] [blame] | 69 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 70 | /// 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 Lattner | 961e742 | 2008-01-01 01:12:31 +0000 | [diff] [blame] | 73 | /// |
| 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 Smith | f947c3a | 2016-08-30 18:40:47 +0000 | [diff] [blame] | 77 | void ilist_callback_traits<MachineBasicBlock>::addNodeToList( |
| 78 | MachineBasicBlock *N) { |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 79 | MachineFunction &MF = *N->getParent(); |
| 80 | N->Number = MF.addToMBBNumbering(N); |
Chris Lattner | 961e742 | 2008-01-01 01:12:31 +0000 | [diff] [blame] | 81 | |
| 82 | // Make sure the instructions have their operands in the reginfo lists. |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 83 | MachineRegisterInfo &RegInfo = MF.getRegInfo(); |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 84 | for (MachineBasicBlock::instr_iterator |
| 85 | I = N->instr_begin(), E = N->instr_end(); I != E; ++I) |
Chris Lattner | 961e742 | 2008-01-01 01:12:31 +0000 | [diff] [blame] | 86 | I->AddRegOperandsToUseLists(RegInfo); |
Brian Gaeke | cb5d22a | 2004-05-12 21:35:22 +0000 | [diff] [blame] | 87 | } |
| 88 | |
Duncan P. N. Exon Smith | f947c3a | 2016-08-30 18:40:47 +0000 | [diff] [blame] | 89 | void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList( |
| 90 | MachineBasicBlock *N) { |
Chris Lattner | 574e716 | 2007-12-31 04:56:33 +0000 | [diff] [blame] | 91 | N->getParent()->removeFromMBBNumbering(N->Number); |
Brian Gaeke | cb5d22a | 2004-05-12 21:35:22 +0000 | [diff] [blame] | 92 | N->Number = -1; |
| 93 | } |
| 94 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 95 | /// 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 Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 97 | void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 98 | assert(!N->getParent() && "machine instruction already in a basic block"); |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 99 | N->setParent(Parent); |
Jakub Staszak | feadd43 | 2011-06-16 18:01:17 +0000 | [diff] [blame] | 100 | |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 101 | // Add the instruction's register operands to their corresponding |
| 102 | // use/def lists. |
| 103 | MachineFunction *MF = Parent->getParent(); |
| 104 | N->AddRegOperandsToUseLists(MF->getRegInfo()); |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 105 | } |
| 106 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 107 | /// 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 Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 109 | void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 110 | assert(N->getParent() && "machine instruction not in a basic block"); |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 111 | |
| 112 | // Remove from the use/def lists. |
Jakob Stoklund Olesen | c4102d4 | 2012-08-09 22:49:37 +0000 | [diff] [blame] | 113 | if (MachineFunction *MF = N->getParent()->getParent()) |
| 114 | N->RemoveRegOperandsFromUseLists(MF->getRegInfo()); |
Jakub Staszak | feadd43 | 2011-06-16 18:01:17 +0000 | [diff] [blame] | 115 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 116 | N->setParent(nullptr); |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 117 | } |
| 118 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 119 | /// 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 Smith | cc9edac | 2016-09-11 16:38:18 +0000 | [diff] [blame] | 121 | void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList, |
| 122 | instr_iterator First, |
| 123 | instr_iterator Last) { |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 124 | assert(Parent->getParent() == FromList.Parent->getParent() && |
Dan Gohman | 804c95d | 2008-07-28 21:51:04 +0000 | [diff] [blame] | 125 | "MachineInstr parent mismatch!"); |
Duncan P. N. Exon Smith | b7668d5 | 2016-08-30 18:00:45 +0000 | [diff] [blame] | 126 | assert(this != &FromList && "Called without a real transfer..."); |
| 127 | assert(Parent != FromList.Parent && "Two lists have the same parent?"); |
Chris Lattner | 961e742 | 2008-01-01 01:12:31 +0000 | [diff] [blame] | 128 | |
| 129 | // If splicing between two blocks within the same function, just update the |
| 130 | // parent pointers. |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 131 | for (; First != Last; ++First) |
| 132 | First->setParent(Parent); |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 133 | } |
| 134 | |
Duncan P. N. Exon Smith | f947c3a | 2016-08-30 18:40:47 +0000 | [diff] [blame] | 135 | void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) { |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 136 | assert(!MI->getParent() && "MI is still in a block!"); |
| 137 | Parent->getParent()->DeleteMachineInstr(MI); |
| 138 | } |
| 139 | |
Dan Gohman | 88c547e | 2010-07-07 14:33:51 +0000 | [diff] [blame] | 140 | MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() { |
Benjamin Kramer | baa41d4 | 2012-02-10 00:28:31 +0000 | [diff] [blame] | 141 | instr_iterator I = instr_begin(), E = instr_end(); |
| 142 | while (I != E && I->isPHI()) |
Dan Gohman | 88c547e | 2010-07-07 14:33:51 +0000 | [diff] [blame] | 143 | ++I; |
Akira Hatanaka | 6fe7aca | 2012-10-26 17:11:42 +0000 | [diff] [blame] | 144 | assert((I == E || !I->isInsideBundle()) && |
| 145 | "First non-phi MI cannot be inside a bundle!"); |
Dan Gohman | 88c547e | 2010-07-07 14:33:51 +0000 | [diff] [blame] | 146 | return I; |
| 147 | } |
| 148 | |
Jakob Stoklund Olesen | ef54185 | 2010-10-30 01:26:14 +0000 | [diff] [blame] | 149 | MachineBasicBlock::iterator |
| 150 | MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) { |
Benjamin Kramer | baa41d4 | 2012-02-10 00:28:31 +0000 | [diff] [blame] | 151 | iterator E = end(); |
Keith Walker | 830a8c1 | 2016-09-16 14:07:29 +0000 | [diff] [blame] | 152 | 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 | |
| 161 | MachineBasicBlock::iterator |
| 162 | MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) { |
| 163 | iterator E = end(); |
Rafael Espindola | b1f25f1 | 2014-03-07 06:08:31 +0000 | [diff] [blame] | 164 | while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue())) |
Jakob Stoklund Olesen | ef54185 | 2010-10-30 01:26:14 +0000 | [diff] [blame] | 165 | ++I; |
Evan Cheng | 2a81dd4 | 2011-12-06 22:12:01 +0000 | [diff] [blame] | 166 | // FIXME: This needs to change if we wish to bundle labels / dbg_values |
| 167 | // inside the bundle. |
Akira Hatanaka | 6fe7aca | 2012-10-26 17:11:42 +0000 | [diff] [blame] | 168 | assert((I == E || !I->isInsideBundle()) && |
Keith Walker | 830a8c1 | 2016-09-16 14:07:29 +0000 | [diff] [blame] | 169 | "First non-phi / non-label / non-debug " |
| 170 | "instruction is inside a bundle!"); |
Jakob Stoklund Olesen | ef54185 | 2010-10-30 01:26:14 +0000 | [diff] [blame] | 171 | return I; |
| 172 | } |
| 173 | |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 174 | MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { |
Benjamin Kramer | baa41d4 | 2012-02-10 00:28:31 +0000 | [diff] [blame] | 175 | iterator B = begin(), E = end(), I = E; |
| 176 | while (I != B && ((--I)->isTerminator() || I->isDebugValue())) |
Jakob Stoklund Olesen | c381028 | 2011-01-14 02:12:54 +0000 | [diff] [blame] | 177 | ; /*noop */ |
Benjamin Kramer | baa41d4 | 2012-02-10 00:28:31 +0000 | [diff] [blame] | 178 | while (I != E && !I->isTerminator()) |
Evan Cheng | 2a81dd4 | 2011-12-06 22:12:01 +0000 | [diff] [blame] | 179 | ++I; |
| 180 | return I; |
| 181 | } |
| 182 | |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 183 | MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { |
Benjamin Kramer | baa41d4 | 2012-02-10 00:28:31 +0000 | [diff] [blame] | 184 | instr_iterator B = instr_begin(), E = instr_end(), I = E; |
| 185 | while (I != B && ((--I)->isTerminator() || I->isDebugValue())) |
Evan Cheng | 2a81dd4 | 2011-12-06 22:12:01 +0000 | [diff] [blame] | 186 | ; /*noop */ |
Benjamin Kramer | baa41d4 | 2012-02-10 00:28:31 +0000 | [diff] [blame] | 187 | while (I != E && !I->isTerminator()) |
Jakob Stoklund Olesen | ab3d6ec | 2011-01-14 06:33:45 +0000 | [diff] [blame] | 188 | ++I; |
Jakob Stoklund Olesen | c381028 | 2011-01-14 02:12:54 +0000 | [diff] [blame] | 189 | return I; |
Alkis Evlogimenos | af2de48 | 2004-02-23 18:14:48 +0000 | [diff] [blame] | 190 | } |
| 191 | |
Benjamin Kramer | 6b56896 | 2015-06-23 14:47:29 +0000 | [diff] [blame] | 192 | MachineBasicBlock::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 Olesen | 4bc5e38 | 2011-01-13 21:28:52 +0000 | [diff] [blame] | 200 | MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { |
Evan Cheng | 2a81dd4 | 2011-12-06 22:12:01 +0000 | [diff] [blame] | 201 | // Skip over end-of-block dbg_value instructions. |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 202 | instr_iterator B = instr_begin(), I = instr_end(); |
Jakob Stoklund Olesen | 4bc5e38 | 2011-01-13 21:28:52 +0000 | [diff] [blame] | 203 | while (I != B) { |
| 204 | --I; |
Evan Cheng | 2a81dd4 | 2011-12-06 22:12:01 +0000 | [diff] [blame] | 205 | // 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 Kleckner | ed17079 | 2015-09-17 17:19:40 +0000 | [diff] [blame] | 214 | bool 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 Ren | 19f49ac | 2012-09-11 22:23:19 +0000 | [diff] [blame] | 221 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
Yaron Keren | eb2a254 | 2016-01-29 20:50:44 +0000 | [diff] [blame] | 222 | LLVM_DUMP_METHOD void MachineBasicBlock::dump() const { |
David Greene | 6c56cef | 2010-01-04 23:22:07 +0000 | [diff] [blame] | 223 | print(dbgs()); |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 224 | } |
Manman Ren | 742534c | 2012-09-06 19:06:06 +0000 | [diff] [blame] | 225 | #endif |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 226 | |
Jakob Stoklund Olesen | 2bbeaa8 | 2009-11-20 01:17:03 +0000 | [diff] [blame] | 227 | StringRef MachineBasicBlock::getName() const { |
| 228 | if (const BasicBlock *LBB = getBasicBlock()) |
| 229 | return LBB->getName(); |
| 230 | else |
| 231 | return "(null)"; |
| 232 | } |
| 233 | |
Andrew Trick | 320c703 | 2012-03-07 00:18:18 +0000 | [diff] [blame] | 234 | /// Return a hopefully unique identifier for this block. |
| 235 | std::string MachineBasicBlock::getFullName() const { |
| 236 | std::string Name; |
| 237 | if (getParent()) |
Craig Topper | a538d83 | 2012-08-22 06:07:19 +0000 | [diff] [blame] | 238 | Name = (getParent()->getName() + ":").str(); |
Andrew Trick | 320c703 | 2012-03-07 00:18:18 +0000 | [diff] [blame] | 239 | if (getBasicBlock()) |
| 240 | Name += getBasicBlock()->getName(); |
| 241 | else |
Yaron Keren | 75e0c4b | 2015-03-27 17:51:30 +0000 | [diff] [blame] | 242 | Name += ("BB" + Twine(getNumber())).str(); |
Andrew Trick | 320c703 | 2012-03-07 00:18:18 +0000 | [diff] [blame] | 243 | return Name; |
| 244 | } |
| 245 | |
Matthias Braun | 0e881d6 | 2016-05-05 18:14:43 +0000 | [diff] [blame] | 246 | void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes) |
| 247 | const { |
Evan Cheng | bcf1d7f | 2007-02-10 02:38:19 +0000 | [diff] [blame] | 248 | const MachineFunction *MF = getParent(); |
Chris Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 249 | if (!MF) { |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 250 | OS << "Can't print out MachineBasicBlock because parent MachineFunction" |
| 251 | << " is null\n"; |
Tanya Lattner | a578cb7 | 2004-05-24 06:11:51 +0000 | [diff] [blame] | 252 | return; |
| 253 | } |
Duncan P. N. Exon Smith | 32692154 | 2015-06-26 22:04:20 +0000 | [diff] [blame] | 254 | const Function *F = MF->getFunction(); |
| 255 | const Module *M = F ? F->getParent() : nullptr; |
| 256 | ModuleSlotTracker MST(M); |
| 257 | print(OS, MST, Indexes); |
| 258 | } |
| 259 | |
| 260 | void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST, |
Matthias Braun | 0e881d6 | 2016-05-05 18:14:43 +0000 | [diff] [blame] | 261 | const SlotIndexes *Indexes) const { |
Duncan P. N. Exon Smith | 32692154 | 2015-06-26 22:04:20 +0000 | [diff] [blame] | 262 | 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 Evlogimenos | fcb3f51 | 2004-09-05 18:39:20 +0000 | [diff] [blame] | 268 | |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 269 | if (Indexes) |
| 270 | OS << Indexes->getMBBStartIdx(this) << '\t'; |
| 271 | |
Dan Gohman | 34341e6 | 2009-10-31 20:19:03 +0000 | [diff] [blame] | 272 | 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 Smith | 32692154 | 2015-06-26 22:04:20 +0000 | [diff] [blame] | 277 | LBB->printAsOperand(OS, /*PrintType=*/false, MST); |
Dan Gohman | 34341e6 | 2009-10-31 20:19:03 +0000 | [diff] [blame] | 278 | Comma = ", "; |
| 279 | } |
Reid Kleckner | 0e28823 | 2015-08-27 23:27:47 +0000 | [diff] [blame] | 280 | if (isEHPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } |
Dan Gohman | 34341e6 | 2009-10-31 20:19:03 +0000 | [diff] [blame] | 281 | if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } |
Bill Wendling | 4fd9663 | 2012-06-15 19:30:42 +0000 | [diff] [blame] | 282 | if (Alignment) |
Jakob Stoklund Olesen | 2a2b37e | 2011-12-06 21:08:39 +0000 | [diff] [blame] | 283 | OS << Comma << "Align " << Alignment << " (" << (1u << Alignment) |
| 284 | << " bytes)"; |
Jakob Stoklund Olesen | 2a2b37e | 2011-12-06 21:08:39 +0000 | [diff] [blame] | 285 | |
Chris Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 286 | OS << '\n'; |
Evan Cheng | bcf1d7f | 2007-02-10 02:38:19 +0000 | [diff] [blame] | 287 | |
Eric Christopher | fc6de42 | 2014-08-05 02:39:49 +0000 | [diff] [blame] | 288 | const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); |
Dan Gohman | c731c97 | 2007-10-03 19:26:29 +0000 | [diff] [blame] | 289 | if (!livein_empty()) { |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 290 | if (Indexes) OS << '\t'; |
Dan Gohman | 34341e6 | 2009-10-31 20:19:03 +0000 | [diff] [blame] | 291 | OS << " Live Ins:"; |
Matthias Braun | d9da162 | 2015-09-09 18:08:03 +0000 | [diff] [blame] | 292 | for (const auto &LI : make_range(livein_begin(), livein_end())) { |
| 293 | OS << ' ' << PrintReg(LI.PhysReg, TRI); |
| 294 | if (LI.LaneMask != ~0u) |
Matthias Braun | c804cdb | 2015-09-25 21:51:24 +0000 | [diff] [blame] | 295 | OS << ':' << PrintLaneMask(LI.LaneMask); |
Matthias Braun | b2b7ef1 | 2015-08-24 22:59:52 +0000 | [diff] [blame] | 296 | } |
Chris Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 297 | OS << '\n'; |
Evan Cheng | bcf1d7f | 2007-02-10 02:38:19 +0000 | [diff] [blame] | 298 | } |
Chris Lattner | 9a1e91b | 2006-09-26 03:41:59 +0000 | [diff] [blame] | 299 | // Print the preds of this block according to the CFG. |
| 300 | if (!pred_empty()) { |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 301 | if (Indexes) OS << '\t'; |
Chris Lattner | 9a1e91b | 2006-09-26 03:41:59 +0000 | [diff] [blame] | 302 | OS << " Predecessors according to CFG:"; |
| 303 | for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) |
Dan Gohman | 34341e6 | 2009-10-31 20:19:03 +0000 | [diff] [blame] | 304 | OS << " BB#" << (*PI)->getNumber(); |
Chris Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 305 | OS << '\n'; |
Chris Lattner | 9a1e91b | 2006-09-26 03:41:59 +0000 | [diff] [blame] | 306 | } |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 307 | |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 308 | for (auto &I : instrs()) { |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 309 | if (Indexes) { |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 310 | if (Indexes->hasIndex(I)) |
| 311 | OS << Indexes->getInstructionIndex(I); |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 312 | OS << '\t'; |
| 313 | } |
Chris Lattner | 1216f54 | 2009-08-23 00:47:04 +0000 | [diff] [blame] | 314 | OS << '\t'; |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 315 | if (I.isInsideBundle()) |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 316 | OS << " * "; |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 317 | I.print(OS, MST); |
Alkis Evlogimenos | fcb3f51 | 2004-09-05 18:39:20 +0000 | [diff] [blame] | 318 | } |
Chris Lattner | 329c14a | 2005-04-01 06:48:38 +0000 | [diff] [blame] | 319 | |
| 320 | // Print the successors of this block according to the CFG. |
| 321 | if (!succ_empty()) { |
Jakob Stoklund Olesen | b705023 | 2010-10-26 20:21:46 +0000 | [diff] [blame] | 322 | if (Indexes) OS << '\t'; |
Chris Lattner | 329c14a | 2005-04-01 06:48:38 +0000 | [diff] [blame] | 323 | OS << " Successors according to CFG:"; |
Jakob Stoklund Olesen | 1dc107a | 2012-08-13 23:13:23 +0000 | [diff] [blame] | 324 | for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) { |
Dan Gohman | 34341e6 | 2009-10-31 20:19:03 +0000 | [diff] [blame] | 325 | OS << " BB#" << (*SI)->getNumber(); |
Cong Hou | d97c100 | 2015-12-01 05:29:22 +0000 | [diff] [blame] | 326 | if (!Probs.empty()) |
| 327 | OS << '(' << *getProbabilityIterator(SI) << ')'; |
Jakob Stoklund Olesen | 1dc107a | 2012-08-13 23:13:23 +0000 | [diff] [blame] | 328 | } |
Chris Lattner | af119ca | 2009-08-23 00:35:30 +0000 | [diff] [blame] | 329 | OS << '\n'; |
Chris Lattner | 329c14a | 2005-04-01 06:48:38 +0000 | [diff] [blame] | 330 | } |
Alkis Evlogimenos | 14f3fe8 | 2004-02-16 07:17:43 +0000 | [diff] [blame] | 331 | } |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 332 | |
Cong Hou | 2793e72 | 2015-08-10 22:27:10 +0000 | [diff] [blame] | 333 | void MachineBasicBlock::printAsOperand(raw_ostream &OS, |
| 334 | bool /*PrintType*/) const { |
Chandler Carruth | d48cdbf | 2014-01-09 02:29:41 +0000 | [diff] [blame] | 335 | OS << "BB#" << getNumber(); |
| 336 | } |
| 337 | |
Matthias Braun | e6a2485 | 2015-09-25 21:51:14 +0000 | [diff] [blame] | 338 | void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) { |
David Majnemer | 4253126 | 2016-08-12 03:55:06 +0000 | [diff] [blame] | 339 | LiveInVector::iterator I = find_if( |
| 340 | LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); |
Matthias Braun | d9da162 | 2015-09-09 18:08:03 +0000 | [diff] [blame] | 341 | if (I == LiveIns.end()) |
| 342 | return; |
| 343 | |
| 344 | I->LaneMask &= ~LaneMask; |
| 345 | if (I->LaneMask == 0) |
Jakob Stoklund Olesen | 8e58c90 | 2012-03-28 20:11:42 +0000 | [diff] [blame] | 346 | LiveIns.erase(I); |
Evan Cheng | f7ed82d | 2007-02-19 21:49:54 +0000 | [diff] [blame] | 347 | } |
| 348 | |
Matthias Braun | e6a2485 | 2015-09-25 21:51:14 +0000 | [diff] [blame] | 349 | bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const { |
David Majnemer | 4253126 | 2016-08-12 03:55:06 +0000 | [diff] [blame] | 350 | livein_iterator I = find_if( |
| 351 | LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); |
Matthias Braun | d9da162 | 2015-09-09 18:08:03 +0000 | [diff] [blame] | 352 | return I != livein_end() && (I->LaneMask & LaneMask) != 0; |
| 353 | } |
| 354 | |
| 355 | void 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 Braun | e6a2485 | 2015-09-25 21:51:14 +0000 | [diff] [blame] | 366 | LaneBitmask LaneMask = I->LaneMask; |
Matthias Braun | d9da162 | 2015-09-09 18:08:03 +0000 | [diff] [blame] | 367 | 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 Ballman | 9f154f6 | 2015-07-29 15:57:49 +0000 | [diff] [blame] | 373 | } |
| 374 | |
Jakob Stoklund Olesen | 533c3bf | 2013-07-03 23:56:20 +0000 | [diff] [blame] | 375 | unsigned |
Matthias Braun | 130bd90 | 2015-08-25 22:05:55 +0000 | [diff] [blame] | 376 | MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) { |
Jakob Stoklund Olesen | 533c3bf | 2013-07-03 23:56:20 +0000 | [diff] [blame] | 377 | assert(getParent() && "MBB must be inserted in function"); |
| 378 | assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg"); |
| 379 | assert(RC && "Register class is required"); |
Reid Kleckner | 0e28823 | 2015-08-27 23:27:47 +0000 | [diff] [blame] | 380 | assert((isEHPad() || this == &getParent()->front()) && |
Jakob Stoklund Olesen | 533c3bf | 2013-07-03 23:56:20 +0000 | [diff] [blame] | 381 | "Only the entry block and landing pads can have physreg live ins"); |
| 382 | |
| 383 | bool LiveIn = isLiveIn(PhysReg); |
Jakob Stoklund Olesen | bbbb532 | 2013-07-04 04:32:35 +0000 | [diff] [blame] | 384 | iterator I = SkipPHIsAndLabels(begin()), E = end(); |
Jakob Stoklund Olesen | 533c3bf | 2013-07-03 23:56:20 +0000 | [diff] [blame] | 385 | MachineRegisterInfo &MRI = getParent()->getRegInfo(); |
Eric Christopher | fc6de42 | 2014-08-05 02:39:49 +0000 | [diff] [blame] | 386 | const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo(); |
Jakob Stoklund Olesen | 533c3bf | 2013-07-03 23:56:20 +0000 | [diff] [blame] | 387 | |
| 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 Lattner | 94866be | 2006-10-24 00:02:26 +0000 | [diff] [blame] | 407 | void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 408 | getParent()->splice(NewAfter->getIterator(), getIterator()); |
Chris Lattner | 94866be | 2006-10-24 00:02:26 +0000 | [diff] [blame] | 409 | } |
| 410 | |
| 411 | void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 412 | getParent()->splice(++NewBefore->getIterator(), getIterator()); |
Chris Lattner | 94866be | 2006-10-24 00:02:26 +0000 | [diff] [blame] | 413 | } |
| 414 | |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 415 | void MachineBasicBlock::updateTerminator() { |
Eric Christopher | fc6de42 | 2014-08-05 02:39:49 +0000 | [diff] [blame] | 416 | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 417 | // A block with no successors has no concerns with fall-through edges. |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 418 | if (this->succ_empty()) |
| 419 | return; |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 420 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 421 | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 422 | SmallVector<MachineOperand, 4> Cond; |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 423 | DebugLoc DL; // FIXME: this is nowhere |
Jacques Pienaar | 71c30a1 | 2016-07-15 14:41:04 +0000 | [diff] [blame] | 424 | bool B = TII->analyzeBranch(*this, TBB, FBB, Cond); |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 425 | (void) B; |
| 426 | assert(!B && "UpdateTerminators requires analyzable predecessors!"); |
| 427 | if (Cond.empty()) { |
| 428 | if (TBB) { |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 429 | // The block has an unconditional branch. If its successor is now its |
| 430 | // layout successor, delete the branch. |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 431 | if (isLayoutSuccessor(TBB)) |
Matt Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 432 | TII->removeBranch(*this); |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 433 | } else { |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 434 | // 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 Carruth | ee54feb | 2011-11-22 13:13:16 +0000 | [diff] [blame] | 437 | for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { |
Reid Kleckner | 0e28823 | 2015-08-27 23:27:47 +0000 | [diff] [blame] | 438 | if ((*SI)->isEHPad()) |
Chandler Carruth | ee54feb | 2011-11-22 13:13:16 +0000 | [diff] [blame] | 439 | continue; |
| 440 | assert(!TBB && "Found more than one non-landing-pad successor!"); |
| 441 | TBB = *SI; |
| 442 | } |
Chandler Carruth | 8c68f1f | 2011-11-23 08:23:54 +0000 | [diff] [blame] | 443 | |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 444 | // If there is no non-landing-pad successor, the block has no fall-through |
| 445 | // edges to be concerned with. |
Chandler Carruth | 8c68f1f | 2011-11-23 08:23:54 +0000 | [diff] [blame] | 446 | 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 Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 451 | if (!isLayoutSuccessor(TBB)) |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 452 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 453 | } |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 454 | return; |
| 455 | } |
Chandler Carruth | 1f5580b | 2012-04-16 22:03:00 +0000 | [diff] [blame] | 456 | |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 457 | 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 Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 462 | if (TII->reverseBranchCondition(Cond)) |
Chandler Carruth | 1f5580b | 2012-04-16 22:03:00 +0000 | [diff] [blame] | 463 | return; |
Matt Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 464 | TII->removeBranch(*this); |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 465 | TII->insertBranch(*this, FBB, nullptr, Cond, DL); |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 466 | } else if (isLayoutSuccessor(FBB)) { |
Matt Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 467 | TII->removeBranch(*this); |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 468 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 469 | } |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 470 | 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 Wu | b71b2f6 | 2016-07-03 19:14:17 +0000 | [diff] [blame] | 484 | 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 Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 490 | TII->removeBranch(*this); |
Haicheng Wu | b71b2f6 | 2016-07-03 19:14:17 +0000 | [diff] [blame] | 491 | |
| 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 Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 495 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
Haicheng Wu | b71b2f6 | 2016-07-03 19:14:17 +0000 | [diff] [blame] | 496 | return; |
| 497 | } |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 498 | |
Haicheng Wu | b71b2f6 | 2016-07-03 19:14:17 +0000 | [diff] [blame] | 499 | // 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 Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 502 | TII->removeBranch(*this); |
Haicheng Wu | b71b2f6 | 2016-07-03 19:14:17 +0000 | [diff] [blame] | 503 | Cond.clear(); |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 504 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 505 | return; |
| 506 | } |
| 507 | |
| 508 | // The block has a fallthrough conditional branch. |
| 509 | if (isLayoutSuccessor(TBB)) { |
Matt Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 510 | if (TII->reverseBranchCondition(Cond)) { |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 511 | // We can't reverse the condition, add an unconditional branch. |
| 512 | Cond.clear(); |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 513 | TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL); |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 514 | return; |
| 515 | } |
Matt Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 516 | TII->removeBranch(*this); |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 517 | TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL); |
Chad Rosier | dca7651 | 2016-05-25 21:53:46 +0000 | [diff] [blame] | 518 | } else if (!isLayoutSuccessor(FallthroughBB)) { |
Matt Arsenault | 1b9fc8e | 2016-09-14 20:43:16 +0000 | [diff] [blame] | 519 | TII->removeBranch(*this); |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 520 | TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL); |
Jim Grosbach | 801b33b | 2009-11-12 03:55:33 +0000 | [diff] [blame] | 521 | } |
| 522 | } |
Chris Lattner | 94866be | 2006-10-24 00:02:26 +0000 | [diff] [blame] | 523 | |
Cong Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 524 | void 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 Hou | c00e65a | 2015-12-13 17:00:25 +0000 | [diff] [blame] | 532 | assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <= |
Cong Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 533 | Probs.size() && |
| 534 | "The sum of successors's probabilities exceeds one."); |
| 535 | #endif // NDEBUG |
| 536 | } |
| 537 | |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 538 | void 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 Hou | 4aef7ef | 2015-12-01 11:05:39 +0000 | [diff] [blame] | 542 | if (!(Probs.empty() && !Successors.empty())) |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 543 | Probs.push_back(Prob); |
| 544 | Successors.push_back(Succ); |
| 545 | Succ->addPredecessor(this); |
| 546 | } |
| 547 | |
| 548 | void 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 Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 557 | void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ, |
| 558 | bool NormalizeSuccProbs) { |
David Majnemer | 0d955d0 | 2016-08-11 22:21:41 +0000 | [diff] [blame] | 559 | succ_iterator I = find(Successors, Succ); |
Cong Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 560 | removeSuccessor(I, NormalizeSuccProbs); |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 561 | } |
| 562 | |
Jakub Staszak | feadd43 | 2011-06-16 18:01:17 +0000 | [diff] [blame] | 563 | MachineBasicBlock::succ_iterator |
Cong Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 564 | MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) { |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 565 | assert(I != Successors.end() && "Not a current successor!"); |
Jakub Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 566 | |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 567 | // 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 Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 572 | if (NormalizeSuccProbs) |
| 573 | normalizeSuccProbs(); |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 574 | } |
| 575 | |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 576 | (*I)->removePredecessor(this); |
Dan Gohman | f87dc92 | 2009-01-08 22:19:34 +0000 | [diff] [blame] | 577 | return Successors.erase(I); |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 578 | } |
| 579 | |
Jakub Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 580 | void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, |
| 581 | MachineBasicBlock *New) { |
Jakob Stoklund Olesen | 8c28ac9 | 2012-08-10 03:23:27 +0000 | [diff] [blame] | 582 | if (Old == New) |
| 583 | return; |
Jakub Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 584 | |
Jakob Stoklund Olesen | 8c28ac9 | 2012-08-10 03:23:27 +0000 | [diff] [blame] | 585 | 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 Olesen | 8c28ac9 | 2012-08-10 03:23:27 +0000 | [diff] [blame] | 601 | |
| 602 | // If New isn't already a successor, let it take Old's place. |
| 603 | if (NewI == E) { |
Cong Hou | 11c1420 | 2015-11-18 01:45:10 +0000 | [diff] [blame] | 604 | Old->removePredecessor(this); |
Jakob Stoklund Olesen | 8c28ac9 | 2012-08-10 03:23:27 +0000 | [diff] [blame] | 605 | New->addPredecessor(this); |
| 606 | *OldI = New; |
| 607 | return; |
Jakub Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 608 | } |
| 609 | |
Jakob Stoklund Olesen | 8c28ac9 | 2012-08-10 03:23:27 +0000 | [diff] [blame] | 610 | // New is already a successor. |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 611 | // Update its probability instead of adding a duplicate edge. |
Cong Hou | d97c100 | 2015-12-01 05:29:22 +0000 | [diff] [blame] | 612 | if (!Probs.empty()) { |
| 613 | auto ProbIter = getProbabilityIterator(NewI); |
| 614 | if (!ProbIter->isUnknown()) |
| 615 | *ProbIter += *getProbabilityIterator(OldI); |
| 616 | } |
Cong Hou | 11c1420 | 2015-11-18 01:45:10 +0000 | [diff] [blame] | 617 | removeSuccessor(OldI); |
Jakub Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 618 | } |
| 619 | |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 620 | void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) { |
| 621 | Predecessors.push_back(Pred); |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 622 | } |
| 623 | |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 624 | void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) { |
David Majnemer | 0d955d0 | 2016-08-11 22:21:41 +0000 | [diff] [blame] | 625 | pred_iterator I = find(Predecessors, Pred); |
Chris Lattner | 4336b87 | 2004-10-26 15:43:42 +0000 | [diff] [blame] | 626 | assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); |
| 627 | Predecessors.erase(I); |
| 628 | } |
Evan Cheng | a92b2b3 | 2007-05-17 23:58:53 +0000 | [diff] [blame] | 629 | |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 630 | void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) { |
| 631 | if (this == FromMBB) |
Mon P Wang | 3e58393 | 2008-05-05 19:05:59 +0000 | [diff] [blame] | 632 | return; |
Jakub Staszak | feadd43 | 2011-06-16 18:01:17 +0000 | [diff] [blame] | 633 | |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 634 | while (!FromMBB->succ_empty()) { |
| 635 | MachineBasicBlock *Succ = *FromMBB->succ_begin(); |
Jakub Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 636 | |
Cong Hou | d97c100 | 2015-12-01 05:29:22 +0000 | [diff] [blame] | 637 | // 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 Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 643 | |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 644 | FromMBB->removeSuccessor(Succ); |
Dan Gohman | 3439629 | 2010-07-06 20:24:04 +0000 | [diff] [blame] | 645 | } |
| 646 | } |
| 647 | |
| 648 | void |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 649 | MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) { |
| 650 | if (this == FromMBB) |
Dan Gohman | 3439629 | 2010-07-06 20:24:04 +0000 | [diff] [blame] | 651 | return; |
Jakub Staszak | feadd43 | 2011-06-16 18:01:17 +0000 | [diff] [blame] | 652 | |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 653 | while (!FromMBB->succ_empty()) { |
| 654 | MachineBasicBlock *Succ = *FromMBB->succ_begin(); |
Cong Hou | d97c100 | 2015-12-01 05:29:22 +0000 | [diff] [blame] | 655 | if (!FromMBB->Probs.empty()) { |
| 656 | auto Prob = *FromMBB->Probs.begin(); |
| 657 | addSuccessor(Succ, Prob); |
| 658 | } else |
| 659 | addSuccessorWithoutProb(Succ); |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 660 | FromMBB->removeSuccessor(Succ); |
Dan Gohman | 3439629 | 2010-07-06 20:24:04 +0000 | [diff] [blame] | 661 | |
| 662 | // Fix up any PHI nodes in the successor. |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 663 | for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(), |
| 664 | ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI) |
Dan Gohman | 3439629 | 2010-07-06 20:24:04 +0000 | [diff] [blame] | 665 | for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) { |
| 666 | MachineOperand &MO = MI->getOperand(i); |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 667 | if (MO.getMBB() == FromMBB) |
Dan Gohman | 3439629 | 2010-07-06 20:24:04 +0000 | [diff] [blame] | 668 | MO.setMBB(this); |
| 669 | } |
| 670 | } |
Cong Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 671 | normalizeSuccProbs(); |
Mon P Wang | 3e58393 | 2008-05-05 19:05:59 +0000 | [diff] [blame] | 672 | } |
| 673 | |
Jakob Stoklund Olesen | fee94ca | 2012-07-30 17:36:47 +0000 | [diff] [blame] | 674 | bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const { |
David Majnemer | 4253126 | 2016-08-12 03:55:06 +0000 | [diff] [blame] | 675 | return is_contained(predecessors(), MBB); |
Jakob Stoklund Olesen | fee94ca | 2012-07-30 17:36:47 +0000 | [diff] [blame] | 676 | } |
| 677 | |
Dan Gohman | ff62c62 | 2009-03-30 20:06:29 +0000 | [diff] [blame] | 678 | bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { |
David Majnemer | 4253126 | 2016-08-12 03:55:06 +0000 | [diff] [blame] | 679 | return is_contained(successors(), MBB); |
Evan Cheng | a92b2b3 | 2007-05-17 23:58:53 +0000 | [diff] [blame] | 680 | } |
Evan Cheng | df75785 | 2007-06-04 06:44:01 +0000 | [diff] [blame] | 681 | |
Dan Gohman | ff62c62 | 2009-03-30 20:06:29 +0000 | [diff] [blame] | 682 | bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { |
Dan Gohman | a78bae3 | 2008-10-02 22:09:09 +0000 | [diff] [blame] | 683 | MachineFunction::const_iterator I(this); |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 684 | return std::next(I) == MachineFunction::const_iterator(MBB); |
Dan Gohman | a78bae3 | 2008-10-02 22:09:09 +0000 | [diff] [blame] | 685 | } |
| 686 | |
Bob Wilson | 2d4ff12 | 2009-11-26 00:32:21 +0000 | [diff] [blame] | 687 | bool MachineBasicBlock::canFallThrough() { |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 688 | MachineFunction::iterator Fallthrough = getIterator(); |
Bob Wilson | 2d4ff12 | 2009-11-26 00:32:21 +0000 | [diff] [blame] | 689 | ++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 Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 695 | if (!isSuccessor(&*Fallthrough)) |
Bob Wilson | 2d4ff12 | 2009-11-26 00:32:21 +0000 | [diff] [blame] | 696 | return false; |
| 697 | |
Dan Gohman | 0b44cb0 | 2009-12-05 00:32:59 +0000 | [diff] [blame] | 698 | // Analyze the branches, if any, at the end of the block. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 699 | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
Dan Gohman | 0b44cb0 | 2009-12-05 00:32:59 +0000 | [diff] [blame] | 700 | SmallVector<MachineOperand, 4> Cond; |
Eric Christopher | fc6de42 | 2014-08-05 02:39:49 +0000 | [diff] [blame] | 701 | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
Jacques Pienaar | 71c30a1 | 2016-07-15 14:41:04 +0000 | [diff] [blame] | 702 | if (TII->analyzeBranch(*this, TBB, FBB, Cond)) { |
Dan Gohman | 0b44cb0 | 2009-12-05 00:32:59 +0000 | [diff] [blame] | 703 | // 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 Rosier | 1a1531d | 2012-01-26 18:24:25 +0000 | [diff] [blame] | 705 | // is possible. The isPredicated check is needed because this code can be |
Dan Gohman | 0b44cb0 | 2009-12-05 00:32:59 +0000 | [diff] [blame] | 706 | // called during IfConversion, where an instruction which is normally a |
Chad Rosier | 9b61cf3 | 2012-01-26 20:19:05 +0000 | [diff] [blame] | 707 | // Barrier is predicated and thus no longer an actual control barrier. |
Duncan P. N. Exon Smith | 6307eb5 | 2016-02-23 02:46:52 +0000 | [diff] [blame] | 708 | return empty() || !back().isBarrier() || TII->isPredicated(back()); |
Dan Gohman | 0b44cb0 | 2009-12-05 00:32:59 +0000 | [diff] [blame] | 709 | } |
Bob Wilson | 2d4ff12 | 2009-11-26 00:32:21 +0000 | [diff] [blame] | 710 | |
| 711 | // If there is no branch, control always falls through. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 712 | if (!TBB) return true; |
Bob Wilson | 2d4ff12 | 2009-11-26 00:32:21 +0000 | [diff] [blame] | 713 | |
| 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 Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 726 | return FBB == nullptr; |
Bob Wilson | 2d4ff12 | 2009-11-26 00:32:21 +0000 | [diff] [blame] | 727 | } |
| 728 | |
Quentin Colombet | 23341a8 | 2016-04-21 21:01:13 +0000 | [diff] [blame] | 729 | MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, |
| 730 | Pass &P) { |
Quentin Colombet | 77e1878 | 2016-04-21 20:46:27 +0000 | [diff] [blame] | 731 | if (!canSplitCriticalEdge(Succ)) |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 732 | return nullptr; |
Evan Cheng | 2d14d8a | 2012-04-24 19:06:55 +0000 | [diff] [blame] | 733 | |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 734 | MachineFunction *MF = getParent(); |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 735 | DebugLoc DL; // FIXME: this is nowhere |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 736 | |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 737 | MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 738 | MF->insert(std::next(MachineFunction::iterator(this)), NMBB); |
Evan Cheng | a684824 | 2010-08-17 17:15:14 +0000 | [diff] [blame] | 739 | DEBUG(dbgs() << "Splitting critical edge:" |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 740 | " BB#" << getNumber() |
| 741 | << " -- BB#" << NMBB->getNumber() |
| 742 | << " -- BB#" << Succ->getNumber() << '\n'); |
Cameron Zwarich | cdcab38 | 2013-02-12 03:49:20 +0000 | [diff] [blame] | 743 | |
Quentin Colombet | 23341a8 | 2016-04-21 21:01:13 +0000 | [diff] [blame] | 744 | LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>(); |
| 745 | SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>(); |
Cameron Zwarich | cdcab38 | 2013-02-12 03:49:20 +0000 | [diff] [blame] | 746 | if (LIS) |
| 747 | LIS->insertMBBInMaps(NMBB); |
| 748 | else if (Indexes) |
Cameron Zwarich | 21beaf6 | 2013-02-10 23:29:54 +0000 | [diff] [blame] | 749 | Indexes->insertMBBInMaps(NMBB); |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 750 | |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 751 | // 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 Colombet | 23341a8 | 2016-04-21 21:01:13 +0000 | [diff] [blame] | 754 | LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>(); |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 755 | |
| 756 | // Collect a list of virtual registers killed by the terminators. |
| 757 | SmallVector<unsigned, 4> KilledRegs; |
| 758 | if (LV) |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 759 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
Evan Cheng | 2a81dd4 | 2011-12-06 22:12:01 +0000 | [diff] [blame] | 760 | I != E; ++I) { |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 761 | MachineInstr *MI = &*I; |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 762 | for (MachineInstr::mop_iterator OI = MI->operands_begin(), |
| 763 | OE = MI->operands_end(); OI != OE; ++OI) { |
Lang Hames | edeea17 | 2012-02-09 05:59:36 +0000 | [diff] [blame] | 764 | if (!OI->isReg() || OI->getReg() == 0 || |
| 765 | !OI->isUse() || !OI->isKill() || OI->isUndef()) |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 766 | continue; |
| 767 | unsigned Reg = OI->getReg(); |
Lang Hames | edeea17 | 2012-02-09 05:59:36 +0000 | [diff] [blame] | 768 | if (TargetRegisterInfo::isPhysicalRegister(Reg) || |
Duncan P. N. Exon Smith | d26fdc8 | 2016-07-01 01:51:32 +0000 | [diff] [blame] | 769 | LV->getVarInfo(Reg).removeKill(*MI)) { |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 770 | KilledRegs.push_back(Reg); |
| 771 | DEBUG(dbgs() << "Removing terminator kill: " << *MI); |
| 772 | OI->setIsKill(false); |
| 773 | } |
| 774 | } |
| 775 | } |
| 776 | |
Cameron Zwarich | bfebb41 | 2013-02-17 00:10:44 +0000 | [diff] [blame] | 777 | SmallVector<unsigned, 4> UsedRegs; |
| 778 | if (LIS) { |
| 779 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
| 780 | I != E; ++I) { |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 781 | MachineInstr *MI = &*I; |
Cameron Zwarich | bfebb41 | 2013-02-17 00:10:44 +0000 | [diff] [blame] | 782 | |
| 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 Majnemer | 0d955d0 | 2016-08-11 22:21:41 +0000 | [diff] [blame] | 789 | if (!is_contained(UsedRegs, Reg)) |
Cameron Zwarich | bfebb41 | 2013-02-17 00:10:44 +0000 | [diff] [blame] | 790 | UsedRegs.push_back(Reg); |
| 791 | } |
| 792 | } |
| 793 | } |
| 794 | |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 795 | ReplaceUsesOfBlockWith(Succ, NMBB); |
Cameron Zwarich | ba378ce | 2013-02-11 09:24:45 +0000 | [diff] [blame] | 796 | |
| 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 Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 803 | Terminators.push_back(&*I); |
Cameron Zwarich | ba378ce | 2013-02-11 09:24:45 +0000 | [diff] [blame] | 804 | } |
| 805 | |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 806 | updateTerminator(); |
| 807 | |
Cameron Zwarich | ba378ce | 2013-02-11 09:24:45 +0000 | [diff] [blame] | 808 | if (Indexes) { |
| 809 | SmallVector<MachineInstr*, 4> NewTerminators; |
| 810 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
| 811 | I != E; ++I) |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 812 | NewTerminators.push_back(&*I); |
Cameron Zwarich | ba378ce | 2013-02-11 09:24:45 +0000 | [diff] [blame] | 813 | |
| 814 | for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(), |
| 815 | E = Terminators.end(); I != E; ++I) { |
David Majnemer | 0d955d0 | 2016-08-11 22:21:41 +0000 | [diff] [blame] | 816 | if (!is_contained(NewTerminators, *I)) |
| 817 | Indexes->removeMachineInstrFromMaps(**I); |
Cameron Zwarich | ba378ce | 2013-02-11 09:24:45 +0000 | [diff] [blame] | 818 | } |
| 819 | } |
| 820 | |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 821 | // Insert unconditional "jump Succ" instruction in NMBB if necessary. |
| 822 | NMBB->addSuccessor(Succ); |
| 823 | if (!NMBB->isLayoutSuccessor(Succ)) { |
Quentin Colombet | 77e1878 | 2016-04-21 20:46:27 +0000 | [diff] [blame] | 824 | SmallVector<MachineOperand, 4> Cond; |
| 825 | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
Matt Arsenault | e8e0f5c | 2016-09-14 17:24:15 +0000 | [diff] [blame] | 826 | TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL); |
Cameron Zwarich | 21beaf6 | 2013-02-10 23:29:54 +0000 | [diff] [blame] | 827 | |
| 828 | if (Indexes) { |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 829 | for (MachineInstr &MI : NMBB->instrs()) { |
Cameron Zwarich | 21beaf6 | 2013-02-10 23:29:54 +0000 | [diff] [blame] | 830 | // 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 Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 832 | if (Indexes->hasIndex(MI)) |
| 833 | Indexes->removeMachineInstrFromMaps(MI); |
| 834 | Indexes->insertMachineInstrInMaps(MI); |
Cameron Zwarich | 21beaf6 | 2013-02-10 23:29:54 +0000 | [diff] [blame] | 835 | } |
| 836 | } |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 837 | } |
| 838 | |
| 839 | // Fix PHI nodes in Succ so they refer to NMBB instead of this |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 840 | for (MachineBasicBlock::instr_iterator |
| 841 | i = Succ->instr_begin(),e = Succ->instr_end(); |
| 842 | i != e && i->isPHI(); ++i) |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 843 | 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 Olesen | 06b6ccf | 2011-10-14 17:25:46 +0000 | [diff] [blame] | 847 | // Inherit live-ins from the successor |
Matthias Braun | d9da162 | 2015-09-09 18:08:03 +0000 | [diff] [blame] | 848 | for (const auto &LI : Succ->liveins()) |
Matthias Braun | b2b7ef1 | 2015-08-24 22:59:52 +0000 | [diff] [blame] | 849 | NMBB->addLiveIn(LI); |
Jakob Stoklund Olesen | 06b6ccf | 2011-10-14 17:25:46 +0000 | [diff] [blame] | 850 | |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 851 | // Update LiveVariables. |
Eric Christopher | fc6de42 | 2014-08-05 02:39:49 +0000 | [diff] [blame] | 852 | const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 853 | 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 Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 857 | for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) { |
Lang Hames | edeea17 | 2012-02-09 05:59:36 +0000 | [diff] [blame] | 858 | if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false)) |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 859 | continue; |
Lang Hames | edeea17 | 2012-02-09 05:59:36 +0000 | [diff] [blame] | 860 | if (TargetRegisterInfo::isVirtualRegister(Reg)) |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 861 | LV->getVarInfo(Reg).Kills.push_back(&*I); |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 862 | DEBUG(dbgs() << "Restored terminator kill: " << *I); |
| 863 | break; |
| 864 | } |
| 865 | } |
| 866 | // Update relevant live-through information. |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 867 | LV->addNewBlock(NMBB, this, Succ); |
Jakob Stoklund Olesen | dd6fcc4 | 2011-05-29 20:10:28 +0000 | [diff] [blame] | 868 | } |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 869 | |
Cameron Zwarich | cdcab38 | 2013-02-12 03:49:20 +0000 | [diff] [blame] | 870 | if (LIS) { |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 871 | // 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 Hou | 2793e72 | 2015-08-10 22:27:10 +0000 | [diff] [blame] | 873 | // 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 Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 877 | |
| 878 | bool isLastMBB = |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 879 | std::next(MachineFunction::iterator(NMBB)) == getParent()->end(); |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 880 | |
| 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 Zwarich | af34931 | 2013-02-12 03:49:17 +0000 | [diff] [blame] | 895 | if (MO.isUndef()) |
| 896 | continue; |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 897 | |
| 898 | LiveInterval &LI = LIS->getInterval(Reg); |
| 899 | VNInfo *VNI = LI.getVNInfoAt(PrevIndex); |
Cong Hou | 2793e72 | 2015-08-10 22:27:10 +0000 | [diff] [blame] | 900 | assert(VNI && |
| 901 | "PHI sources should be live out of their predecessors."); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 902 | LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 903 | } |
| 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 Zwarich | af34931 | 2013-02-12 03:49:17 +0000 | [diff] [blame] | 917 | bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ)); |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 918 | if (isLiveOut && isLastMBB) { |
| 919 | VNInfo *VNI = LI.getVNInfoAt(PrevIndex); |
| 920 | assert(VNI && "LiveInterval should have VNInfo where it is live."); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 921 | LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 922 | } else if (!isLiveOut && !isLastMBB) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 923 | LI.removeSegment(StartIndex, EndIndex); |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 924 | } |
| 925 | } |
Cameron Zwarich | bfebb41 | 2013-02-17 00:10:44 +0000 | [diff] [blame] | 926 | |
| 927 | // Update all intervals for registers whose uses may have been modified by |
| 928 | // updateTerminator(). |
Cameron Zwarich | 2495596 | 2013-02-17 11:09:00 +0000 | [diff] [blame] | 929 | LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs); |
Cameron Zwarich | b47fb38 | 2013-02-11 09:24:47 +0000 | [diff] [blame] | 930 | } |
| 931 | |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 932 | if (MachineDominatorTree *MDT = |
Quentin Colombet | 23341a8 | 2016-04-21 21:01:13 +0000 | [diff] [blame] | 933 | P.getAnalysisIfAvailable<MachineDominatorTree>()) |
Quentin Colombet | abea99f | 2014-08-13 21:00:07 +0000 | [diff] [blame] | 934 | MDT->recordSplitCriticalEdge(this, Succ, NMBB); |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 935 | |
Quentin Colombet | 23341a8 | 2016-04-21 21:01:13 +0000 | [diff] [blame] | 936 | if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>()) |
Dan Gohman | 3570f81 | 2010-06-22 17:25:57 +0000 | [diff] [blame] | 937 | 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 Colombet | 77e1878 | 2016-04-21 20:46:27 +0000 | [diff] [blame] | 966 | bool 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 Pienaar | 71c30a1 | 2016-07-15 14:41:04 +0000 | [diff] [blame] | 986 | if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond, |
Quentin Colombet | 77e1878 | 2016-04-21 20:46:27 +0000 | [diff] [blame] | 987 | /*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 Olesen | ccfb5fb | 2012-12-17 23:55:38 +0000 | [diff] [blame] | 1002 | /// 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. |
| 1004 | static 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 Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 1013 | } |
| 1014 | |
Jakob Stoklund Olesen | ccfb5fb | 2012-12-17 23:55:38 +0000 | [diff] [blame] | 1015 | MachineBasicBlock::instr_iterator |
| 1016 | MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) { |
Duncan P. N. Exon Smith | 0ac8eb9 | 2015-10-09 19:23:20 +0000 | [diff] [blame] | 1017 | unbundleSingleMI(&*I); |
Jakob Stoklund Olesen | ccfb5fb | 2012-12-17 23:55:38 +0000 | [diff] [blame] | 1018 | return Insts.erase(I); |
| 1019 | } |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 1020 | |
Jakob Stoklund Olesen | ccfb5fb | 2012-12-17 23:55:38 +0000 | [diff] [blame] | 1021 | MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) { |
| 1022 | unbundleSingleMI(MI); |
| 1023 | MI->clearFlag(MachineInstr::BundledPred); |
| 1024 | MI->clearFlag(MachineInstr::BundledSucc); |
| 1025 | return Insts.remove(MI); |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 1026 | } |
| 1027 | |
Jakob Stoklund Olesen | 422e07b | 2012-12-18 17:54:53 +0000 | [diff] [blame] | 1028 | MachineBasicBlock::instr_iterator |
| 1029 | MachineBasicBlock::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 Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 1040 | /// This method unlinks 'this' from the containing function, and returns it, but |
| 1041 | /// does not delete it. |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 1042 | MachineBasicBlock *MachineBasicBlock::removeFromParent() { |
| 1043 | assert(getParent() && "Not embedded in a function!"); |
| 1044 | getParent()->remove(this); |
| 1045 | return this; |
| 1046 | } |
| 1047 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 1048 | /// This method unlinks 'this' from the containing function, and deletes it. |
Dan Gohman | 3b46030 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 1049 | void MachineBasicBlock::eraseFromParent() { |
| 1050 | assert(getParent() && "Not embedded in a function!"); |
| 1051 | getParent()->erase(this); |
| 1052 | } |
| 1053 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 1054 | /// Given a machine basic block that branched to 'Old', change the code and CFG |
| 1055 | /// so that it branches to 'New' instead. |
Evan Cheng | df75785 | 2007-06-04 06:44:01 +0000 | [diff] [blame] | 1056 | void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, |
| 1057 | MachineBasicBlock *New) { |
| 1058 | assert(Old != New && "Cannot replace self with self!"); |
| 1059 | |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 1060 | MachineBasicBlock::instr_iterator I = instr_end(); |
| 1061 | while (I != instr_begin()) { |
Evan Cheng | df75785 | 2007-06-04 06:44:01 +0000 | [diff] [blame] | 1062 | --I; |
Evan Cheng | 7f8e563 | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 1063 | if (!I->isTerminator()) break; |
Evan Cheng | df75785 | 2007-06-04 06:44:01 +0000 | [diff] [blame] | 1064 | |
| 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 Gohman | 0d1e9a8 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 1068 | if (I->getOperand(i).isMBB() && |
Dan Gohman | 38453ee | 2008-09-13 17:58:21 +0000 | [diff] [blame] | 1069 | I->getOperand(i).getMBB() == Old) |
Chris Lattner | a5bb370 | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 1070 | I->getOperand(i).setMBB(New); |
Evan Cheng | df75785 | 2007-06-04 06:44:01 +0000 | [diff] [blame] | 1071 | } |
| 1072 | |
Dan Gohman | bb2f107 | 2009-05-05 21:10:19 +0000 | [diff] [blame] | 1073 | // Update the successor information. |
Jakub Staszak | 12a43bd | 2011-06-16 20:22:37 +0000 | [diff] [blame] | 1074 | replaceSuccessor(Old, New); |
Evan Cheng | df75785 | 2007-06-04 06:44:01 +0000 | [diff] [blame] | 1075 | } |
| 1076 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 1077 | /// 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 Staszak | feadd43 | 2011-06-16 18:01:17 +0000 | [diff] [blame] | 1080 | /// |
Chris Lattner | 574e716 | 2007-12-31 04:56:33 +0000 | [diff] [blame] | 1081 | /// 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 Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1083 | /// Note it is possible that DestA and/or DestB are LandingPads. |
| 1084 | bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, |
| 1085 | MachineBasicBlock *DestB, |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 1086 | bool IsCond) { |
Bill Wendling | 2d5967d | 2009-12-16 00:08:36 +0000 | [diff] [blame] | 1087 | // 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 Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 1093 | // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends |
Bill Wendling | 2d5967d | 2009-12-16 00:08:36 +0000 | [diff] [blame] | 1094 | // with only an unconditional branch. |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 1095 | // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends |
Bill Wendling | 2d5967d | 2009-12-16 00:08:36 +0000 | [diff] [blame] | 1096 | // with a conditional branch that falls through to a successor (DestB). |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 1097 | // 4. If DestA and DestB is set and IsCond is true, then the block ends with a |
Bill Wendling | 2d5967d | 2009-12-16 00:08:36 +0000 | [diff] [blame] | 1098 | // conditional branch followed by an unconditional branch. DestA is the |
| 1099 | // 'true' destination and DestB is the 'false' destination. |
| 1100 | |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1101 | bool Changed = false; |
Evan Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1102 | |
Duncan P. N. Exon Smith | 41cf73c | 2016-08-16 21:46:03 +0000 | [diff] [blame] | 1103 | MachineBasicBlock *FallThru = getNextNode(); |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1104 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 1105 | if (!DestA && !DestB) { |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1106 | // Block falls through to successor. |
Duncan P. N. Exon Smith | 41cf73c | 2016-08-16 21:46:03 +0000 | [diff] [blame] | 1107 | DestA = FallThru; |
| 1108 | DestB = FallThru; |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 1109 | } else if (DestA && !DestB) { |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 1110 | if (IsCond) |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1111 | // Block ends in conditional jump that falls through to successor. |
Duncan P. N. Exon Smith | 41cf73c | 2016-08-16 21:46:03 +0000 | [diff] [blame] | 1112 | DestB = FallThru; |
Evan Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1113 | } else { |
Cong Hou | 166e085 | 2015-09-29 19:46:09 +0000 | [diff] [blame] | 1114 | assert(DestA && DestB && IsCond && |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1115 | "CFG in a bad state. Cannot correct CFG edges"); |
Evan Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1116 | } |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1117 | |
| 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 Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1121 | MachineBasicBlock::succ_iterator SI = succ_begin(); |
Evan Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1122 | while (SI != succ_end()) { |
Bill Wendling | 2d5967d | 2009-12-16 00:08:36 +0000 | [diff] [blame] | 1123 | const MachineBasicBlock *MBB = *SI; |
David Blaikie | 70573dc | 2014-11-19 07:49:26 +0000 | [diff] [blame] | 1124 | if (!SeenMBBs.insert(MBB).second || |
Reid Kleckner | 0e28823 | 2015-08-27 23:27:47 +0000 | [diff] [blame] | 1125 | (MBB != DestA && MBB != DestB && !MBB->isEHPad())) { |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1126 | // This is a superfluous edge, remove it. |
Bill Wendling | fa9810d | 2010-03-31 23:26:26 +0000 | [diff] [blame] | 1127 | SI = removeSuccessor(SI); |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1128 | Changed = true; |
| 1129 | } else { |
| 1130 | ++SI; |
Evan Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1131 | } |
| 1132 | } |
Bill Wendling | 2d5967d | 2009-12-16 00:08:36 +0000 | [diff] [blame] | 1133 | |
Cong Hou | c106989 | 2015-12-13 09:26:17 +0000 | [diff] [blame] | 1134 | if (Changed) |
| 1135 | normalizeSuccProbs(); |
Bill Wendling | 9564340 | 2010-04-01 00:00:43 +0000 | [diff] [blame] | 1136 | return Changed; |
Evan Cheng | 2afd702 | 2007-06-18 22:43:58 +0000 | [diff] [blame] | 1137 | } |
Evan Cheng | 57be2f2 | 2009-11-17 19:19:59 +0000 | [diff] [blame] | 1138 | |
Cong Hou | 2a02c1c | 2015-08-12 21:18:54 +0000 | [diff] [blame] | 1139 | /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE |
| 1140 | /// instructions. Return UnknownLoc if there is none. |
Dale Johannesen | c5db599 | 2010-01-20 21:36:02 +0000 | [diff] [blame] | 1141 | DebugLoc |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 1142 | MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { |
Dale Johannesen | c5db599 | 2010-01-20 21:36:02 +0000 | [diff] [blame] | 1143 | DebugLoc DL; |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 1144 | instr_iterator E = instr_end(); |
Evan Cheng | 2a81dd4 | 2011-12-06 22:12:01 +0000 | [diff] [blame] | 1145 | 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 Johannesen | c5db599 | 2010-01-20 21:36:02 +0000 | [diff] [blame] | 1153 | return DL; |
| 1154 | } |
| 1155 | |
Cong Hou | d97c100 | 2015-12-01 05:29:22 +0000 | [diff] [blame] | 1156 | /// Return probability of the edge from this block to MBB. |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 1157 | BranchProbability |
| 1158 | MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const { |
Cong Hou | 4aef7ef | 2015-12-01 11:05:39 +0000 | [diff] [blame] | 1159 | if (Probs.empty()) |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 1160 | return BranchProbability(1, succ_size()); |
| 1161 | |
Cong Hou | 4aef7ef | 2015-12-01 11:05:39 +0000 | [diff] [blame] | 1162 | 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 Ren | b681918 | 2014-01-29 23:18:47 +0000 | [diff] [blame] | 1177 | } |
| 1178 | |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 1179 | /// Set successor probability of a given iterator. |
| 1180 | void MachineBasicBlock::setSuccProbability(succ_iterator I, |
| 1181 | BranchProbability Prob) { |
| 1182 | assert(!Prob.isUnknown()); |
Cong Hou | d97c100 | 2015-12-01 05:29:22 +0000 | [diff] [blame] | 1183 | if (Probs.empty()) |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 1184 | return; |
| 1185 | *getProbabilityIterator(I) = Prob; |
Cong Hou | 23a3bf0 | 2015-11-04 21:37:58 +0000 | [diff] [blame] | 1186 | } |
| 1187 | |
Hans Wennborg | 1dbaf67 | 2015-12-01 03:49:42 +0000 | [diff] [blame] | 1188 | /// Return probability iterator corresonding to the I successor iterator |
| 1189 | MachineBasicBlock::const_probability_iterator |
| 1190 | MachineBasicBlock::getProbabilityIterator( |
| 1191 | MachineBasicBlock::const_succ_iterator I) const { |
Cong Hou | fa1917c | 2015-12-01 00:02:51 +0000 | [diff] [blame] | 1192 | 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 Hou | d97c100 | 2015-12-01 05:29:22 +0000 | [diff] [blame] | 1198 | /// Return probability iterator corresonding to the I successor iterator. |
| 1199 | MachineBasicBlock::probability_iterator |
| 1200 | MachineBasicBlock::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 Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1207 | /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed |
| 1208 | /// as of just before "MI". |
Junmo Park | 1238610 | 2016-01-07 10:26:32 +0000 | [diff] [blame] | 1209 | /// |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1210 | /// 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. |
| 1213 | MachineBasicBlock::LivenessQueryResult |
| 1214 | MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, |
Matthias Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1215 | unsigned Reg, const_iterator Before, |
| 1216 | unsigned Neighborhood) const { |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1217 | unsigned N = Neighborhood; |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1218 | |
Matthias Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1219 | // Start by searching backwards from Before, looking for kills, reads or defs. |
| 1220 | const_iterator I(Before); |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1221 | // If this is the first insn in the block, don't search backwards. |
Matthias Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1222 | if (I != begin()) { |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1223 | do { |
| 1224 | --I; |
| 1225 | |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1226 | MachineOperandIteratorBase::PhysRegInfo Info = |
Duncan P. N. Exon Smith | f9ab416 | 2016-02-27 17:05:33 +0000 | [diff] [blame] | 1227 | ConstMIOperands(*I).analyzePhysReg(Reg, TRI); |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1228 | |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1229 | // Defs happen after uses so they take precedence if both are present. |
Tim Northover | dd219d0 | 2012-11-20 09:56:11 +0000 | [diff] [blame] | 1230 | |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1231 | // Register is dead after a dead def of the full register. |
| 1232 | if (Info.DeadDef) |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1233 | return LQR_Dead; |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1234 | // Register is (at least partially) live after a def. |
Quentin Colombet | 08e7999 | 2016-04-26 23:14:29 +0000 | [diff] [blame] | 1235 | 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 Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1244 | // 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 Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1250 | } while (I != begin() && --N > 0); |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1251 | } |
| 1252 | |
| 1253 | // Did we get to the start of the block? |
Matthias Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1254 | if (I == begin()) { |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1255 | // If so, the register's state is definitely defined by the live-in state. |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1256 | for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid(); |
| 1257 | ++RAI) |
Matthias Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1258 | if (isLiveIn(*RAI)) |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1259 | return LQR_Live; |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1260 | |
| 1261 | return LQR_Dead; |
| 1262 | } |
| 1263 | |
| 1264 | N = Neighborhood; |
| 1265 | |
Matthias Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1266 | // Try searching forwards from Before, looking for reads or defs. |
| 1267 | I = const_iterator(Before); |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1268 | // If this is the last insn in the block, don't search forwards. |
Matthias Braun | 07a07ba | 2015-05-27 05:12:39 +0000 | [diff] [blame] | 1269 | if (I != end()) { |
| 1270 | for (++I; I != end() && N > 0; ++I, --N) { |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1271 | MachineOperandIteratorBase::PhysRegInfo Info = |
Duncan P. N. Exon Smith | f9ab416 | 2016-02-27 17:05:33 +0000 | [diff] [blame] | 1272 | ConstMIOperands(*I).analyzePhysReg(Reg, TRI); |
James Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1273 | |
Matthias Braun | 60d69e2 | 2015-12-11 19:42:09 +0000 | [diff] [blame] | 1274 | // 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 Molloy | c747cda | 2012-09-12 10:18:23 +0000 | [diff] [blame] | 1279 | 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 Kleckner | b8fd162 | 2015-11-06 17:06:38 +0000 | [diff] [blame] | 1286 | |
| 1287 | const uint32_t * |
| 1288 | MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const { |
| 1289 | // EH funclet entry does not preserve any registers. |
| 1290 | return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr; |
| 1291 | } |
| 1292 | |
| 1293 | const uint32_t * |
| 1294 | MachineBasicBlock::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 | } |