Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/SplitKit.cpp @ 77:54457678186b LLVM3.6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.6
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Mon, 08 Sep 2014 22:06:00 +0900
parents 95c75e76d11b
children 60c9769439b8
comparison
equal deleted inserted replaced
34:e874dbf0ad9d 77:54457678186b
10 // This file contains the SplitAnalysis class as well as mutator functions for 10 // This file contains the SplitAnalysis class as well as mutator functions for
11 // live range splitting. 11 // live range splitting.
12 // 12 //
13 //===----------------------------------------------------------------------===// 13 //===----------------------------------------------------------------------===//
14 14
15 #define DEBUG_TYPE "regalloc"
16 #include "SplitKit.h" 15 #include "SplitKit.h"
17 #include "llvm/ADT/Statistic.h" 16 #include "llvm/ADT/Statistic.h"
18 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
19 #include "llvm/CodeGen/LiveRangeEdit.h" 18 #include "llvm/CodeGen/LiveRangeEdit.h"
20 #include "llvm/CodeGen/MachineDominators.h" 19 #include "llvm/CodeGen/MachineDominators.h"
27 #include "llvm/Target/TargetInstrInfo.h" 26 #include "llvm/Target/TargetInstrInfo.h"
28 #include "llvm/Target/TargetMachine.h" 27 #include "llvm/Target/TargetMachine.h"
29 28
30 using namespace llvm; 29 using namespace llvm;
31 30
31 #define DEBUG_TYPE "regalloc"
32
32 STATISTIC(NumFinished, "Number of splits finished"); 33 STATISTIC(NumFinished, "Number of splits finished");
33 STATISTIC(NumSimple, "Number of splits that were simple"); 34 STATISTIC(NumSimple, "Number of splits that were simple");
34 STATISTIC(NumCopies, "Number of copies inserted for splitting"); 35 STATISTIC(NumCopies, "Number of copies inserted for splitting");
35 STATISTIC(NumRemats, "Number of rematerialized defs for splitting"); 36 STATISTIC(NumRemats, "Number of rematerialized defs for splitting");
36 STATISTIC(NumRepairs, "Number of invalid live ranges repaired"); 37 STATISTIC(NumRepairs, "Number of invalid live ranges repaired");
37 38
38 //===----------------------------------------------------------------------===// 39 //===----------------------------------------------------------------------===//
39 // Split Analysis 40 // Split Analysis
40 //===----------------------------------------------------------------------===// 41 //===----------------------------------------------------------------------===//
41 42
42 SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 43 SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
43 const LiveIntervals &lis,
44 const MachineLoopInfo &mli) 44 const MachineLoopInfo &mli)
45 : MF(vrm.getMachineFunction()), 45 : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
46 VRM(vrm), 46 TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr),
47 LIS(lis), 47 LastSplitPoint(MF.getNumBlockIDs()) {}
48 Loops(mli),
49 TII(*MF.getTarget().getInstrInfo()),
50 CurLI(0),
51 LastSplitPoint(MF.getNumBlockIDs()) {}
52 48
53 void SplitAnalysis::clear() { 49 void SplitAnalysis::clear() {
54 UseSlots.clear(); 50 UseSlots.clear();
55 UseBlocks.clear(); 51 UseBlocks.clear();
56 ThroughBlocks.clear(); 52 ThroughBlocks.clear();
57 CurLI = 0; 53 CurLI = nullptr;
58 DidRepairRange = false; 54 DidRepairRange = false;
59 } 55 }
60 56
61 SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 57 SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
62 const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 58 const MachineBasicBlock *MBB = MF.getBlockNumbered(Num);
129 if (!(*I)->isPHIDef() && !(*I)->isUnused()) 125 if (!(*I)->isPHIDef() && !(*I)->isUnused())
130 UseSlots.push_back((*I)->def); 126 UseSlots.push_back((*I)->def);
131 127
132 // Get use slots form the use-def chain. 128 // Get use slots form the use-def chain.
133 const MachineRegisterInfo &MRI = MF.getRegInfo(); 129 const MachineRegisterInfo &MRI = MF.getRegInfo();
134 for (MachineRegisterInfo::use_nodbg_iterator 130 for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
135 I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 131 if (!MO.isUndef())
136 ++I) 132 UseSlots.push_back(LIS.getInstructionIndex(MO.getParent()).getRegSlot());
137 if (!I.getOperand().isUndef())
138 UseSlots.push_back(LIS.getInstructionIndex(&*I).getRegSlot());
139 133
140 array_pod_sort(UseSlots.begin(), UseSlots.end()); 134 array_pod_sort(UseSlots.begin(), UseSlots.end());
141 135
142 // Remove duplicates, keeping the smaller slot for each instruction. 136 // Remove duplicates, keeping the smaller slot for each instruction.
143 // That is what we want for early clobbers. 137 // That is what we want for early clobbers.
186 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 180 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
187 for (;;) { 181 for (;;) {
188 BlockInfo BI; 182 BlockInfo BI;
189 BI.MBB = MFI; 183 BI.MBB = MFI;
190 SlotIndex Start, Stop; 184 SlotIndex Start, Stop;
191 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 185 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
192 186
193 // If the block contains no uses, the range must be live through. At one 187 // If the block contains no uses, the range must be live through. At one
194 // point, RegisterCoalescer could create dangling ranges that ended 188 // point, RegisterCoalescer could create dangling ranges that ended
195 // mid-block. 189 // mid-block.
196 if (UseI == UseE || *UseI >= Stop) { 190 if (UseI == UseE || *UseI >= Stop) {
320 //===----------------------------------------------------------------------===// 314 //===----------------------------------------------------------------------===//
321 // Split Editor 315 // Split Editor
322 //===----------------------------------------------------------------------===// 316 //===----------------------------------------------------------------------===//
323 317
324 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 318 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
325 SplitEditor::SplitEditor(SplitAnalysis &sa, 319 SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
326 LiveIntervals &lis,
327 VirtRegMap &vrm,
328 MachineDominatorTree &mdt, 320 MachineDominatorTree &mdt,
329 MachineBlockFrequencyInfo &mbfi) 321 MachineBlockFrequencyInfo &mbfi)
330 : SA(sa), LIS(lis), VRM(vrm), 322 : SA(sa), LIS(lis), VRM(vrm), MRI(vrm.getMachineFunction().getRegInfo()),
331 MRI(vrm.getMachineFunction().getRegInfo()), 323 MDT(mdt), TII(*vrm.getMachineFunction()
332 MDT(mdt), 324 .getTarget()
333 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 325 .getSubtargetImpl()
334 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 326 ->getInstrInfo()),
335 MBFI(mbfi), 327 TRI(*vrm.getMachineFunction()
336 Edit(0), 328 .getTarget()
337 OpenIdx(0), 329 .getSubtargetImpl()
338 SpillMode(SM_Partition), 330 ->getRegisterInfo()),
339 RegAssign(Allocator) 331 MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition),
340 {} 332 RegAssign(Allocator) {}
341 333
342 void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { 334 void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
343 Edit = &LRE; 335 Edit = &LRE;
344 SpillMode = SM; 336 SpillMode = SM;
345 OpenIdx = 0; 337 OpenIdx = 0;
353 LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, 345 LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
354 &LIS.getVNInfoAllocator()); 346 &LIS.getVNInfoAllocator());
355 347
356 // We don't need an AliasAnalysis since we will only be performing 348 // We don't need an AliasAnalysis since we will only be performing
357 // cheap-as-a-copy remats anyway. 349 // cheap-as-a-copy remats anyway.
358 Edit->anyRematerializable(0); 350 Edit->anyRematerializable(nullptr);
359 } 351 }
360 352
361 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 353 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
362 void SplitEditor::dump() const { 354 void SplitEditor::dump() const {
363 if (RegAssign.empty()) { 355 if (RegAssign.empty()) {
423 // by a trivial live range. 415 // by a trivial live range.
424 SlotIndex Def = VNI->def; 416 SlotIndex Def = VNI->def;
425 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 417 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
426 LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); 418 LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
427 // Mark as complex mapped, forced. 419 // Mark as complex mapped, forced.
428 VFP = ValueForcePair(0, true); 420 VFP = ValueForcePair(nullptr, true);
429 } 421 }
430 422
431 VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 423 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
432 VNInfo *ParentVNI, 424 VNInfo *ParentVNI,
433 SlotIndex UseIdx, 425 SlotIndex UseIdx,
434 MachineBasicBlock &MBB, 426 MachineBasicBlock &MBB,
435 MachineBasicBlock::iterator I) { 427 MachineBasicBlock::iterator I) {
436 MachineInstr *CopyMI = 0; 428 MachineInstr *CopyMI = nullptr;
437 SlotIndex Def; 429 SlotIndex Def;
438 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 430 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
439 431
440 // We may be trying to avoid interference that ends at a deleted instruction, 432 // We may be trying to avoid interference that ends at a deleted instruction,
441 // so always begin RegIdx 0 early and all others late. 433 // so always begin RegIdx 0 early and all others late.
507 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 499 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
508 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 500 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
509 assert(MI && "enterIntvAfter called with invalid index"); 501 assert(MI && "enterIntvAfter called with invalid index");
510 502
511 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 503 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
512 llvm::next(MachineBasicBlock::iterator(MI))); 504 std::next(MachineBasicBlock::iterator(MI)));
513 return VNI->def; 505 return VNI->def;
514 } 506 }
515 507
516 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 508 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
517 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 509 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
568 defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 560 defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
569 return Idx; 561 return Idx;
570 } 562 }
571 563
572 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), 564 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
573 llvm::next(MachineBasicBlock::iterator(MI))); 565 std::next(MachineBasicBlock::iterator(MI)));
574 return VNI->def; 566 return VNI->def;
575 } 567 }
576 568
577 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 569 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
578 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 570 assert(OpenIdx && "openIntv not called before leaveIntvBefore");
886 // This value has multiple defs in RegIdx, but it wasn't rematerialized, 878 // This value has multiple defs in RegIdx, but it wasn't rematerialized,
887 // so the live range is accurate. Add live-in blocks in [Start;End) to the 879 // so the live range is accurate. Add live-in blocks in [Start;End) to the
888 // LiveInBlocks. 880 // LiveInBlocks.
889 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 881 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
890 SlotIndex BlockStart, BlockEnd; 882 SlotIndex BlockStart, BlockEnd;
891 tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 883 std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB);
892 884
893 // The first block may be live-in, or it may have its own def. 885 // The first block may be live-in, or it may have its own def.
894 if (Start != BlockStart) { 886 if (Start != BlockStart) {
895 VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); 887 VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
896 assert(VNI && "Missing def for complex mapped value"); 888 assert(VNI && "Missing def for complex mapped value");
922 if (End < BlockEnd) 914 if (End < BlockEnd)
923 LRC.addLiveInBlock(LR, MDT[MBB], End); 915 LRC.addLiveInBlock(LR, MDT[MBB], End);
924 else { 916 else {
925 // Live-through, and we don't know the value. 917 // Live-through, and we don't know the value.
926 LRC.addLiveInBlock(LR, MDT[MBB]); 918 LRC.addLiveInBlock(LR, MDT[MBB]);
927 LRC.setLiveOutValue(MBB, 0); 919 LRC.setLiveOutValue(MBB, nullptr);
928 } 920 }
929 } 921 }
930 BlockStart = BlockEnd; 922 BlockStart = BlockEnd;
931 ++MBB; 923 ++MBB;
932 } 924 }
970 962
971 /// rewriteAssigned - Rewrite all uses of Edit->getReg(). 963 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
972 void SplitEditor::rewriteAssigned(bool ExtendRanges) { 964 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
973 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 965 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
974 RE = MRI.reg_end(); RI != RE;) { 966 RE = MRI.reg_end(); RI != RE;) {
975 MachineOperand &MO = RI.getOperand(); 967 MachineOperand &MO = *RI;
976 MachineInstr *MI = MO.getParent(); 968 MachineInstr *MI = MO.getParent();
977 ++RI; 969 ++RI;
978 // LiveDebugVariables should have handled all DBG_VALUE instructions. 970 // LiveDebugVariables should have handled all DBG_VALUE instructions.
979 if (MI->isDebugValue()) { 971 if (MI->isDebugValue()) {
980 DEBUG(dbgs() << "Zapping " << *MI); 972 DEBUG(dbgs() << "Zapping " << *MI);
1181 1173
1182 void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 1174 void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
1183 unsigned IntvIn, SlotIndex LeaveBefore, 1175 unsigned IntvIn, SlotIndex LeaveBefore,
1184 unsigned IntvOut, SlotIndex EnterAfter){ 1176 unsigned IntvOut, SlotIndex EnterAfter){
1185 SlotIndex Start, Stop; 1177 SlotIndex Start, Stop;
1186 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 1178 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1187 1179
1188 DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 1180 DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop
1189 << ") intf " << LeaveBefore << '-' << EnterAfter 1181 << ") intf " << LeaveBefore << '-' << EnterAfter
1190 << ", live-through " << IntvIn << " -> " << IntvOut); 1182 << ", live-through " << IntvIn << " -> " << IntvOut);
1191 1183
1284 1276
1285 1277
1286 void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1278 void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
1287 unsigned IntvIn, SlotIndex LeaveBefore) { 1279 unsigned IntvIn, SlotIndex LeaveBefore) {
1288 SlotIndex Start, Stop; 1280 SlotIndex Start, Stop;
1289 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1281 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1290 1282
1291 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1283 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1292 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1284 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1293 << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1285 << ", reg-in " << IntvIn << ", leave before " << LeaveBefore
1294 << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1286 << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1376 } 1368 }
1377 1369
1378 void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1370 void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
1379 unsigned IntvOut, SlotIndex EnterAfter) { 1371 unsigned IntvOut, SlotIndex EnterAfter) {
1380 SlotIndex Start, Stop; 1372 SlotIndex Start, Stop;
1381 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1373 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1382 1374
1383 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1375 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1384 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1376 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1385 << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1377 << ", reg-out " << IntvOut << ", enter after " << EnterAfter
1386 << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1378 << (BI.LiveIn ? ", stack-in" : ", defined in block"));