source: clamav/trunk/libclamav/c++/llvm/lib/CodeGen/Splitter.cpp@ 319

Last change on this file since 319 was 319, checked in by Yuri Dario, 14 years ago

clamav: update trunk to 0.97.
File size: 27.0 KB
Line 
1//===-- llvm/CodeGen/Splitter.cpp - Splitter -----------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#define DEBUG_TYPE "loopsplitter"
11
12#include "Splitter.h"
13
14#include "SimpleRegisterCoalescing.h"
15#include "llvm/Module.h"
16#include "llvm/CodeGen/CalcSpillWeights.h"
17#include "llvm/CodeGen/LiveIntervalAnalysis.h"
18#include "llvm/CodeGen/LiveStackAnalysis.h"
19#include "llvm/CodeGen/MachineDominators.h"
20#include "llvm/CodeGen/MachineInstrBuilder.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/CodeGen/SlotIndexes.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/raw_ostream.h"
26#include "llvm/Target/TargetMachine.h"
27#include "llvm/Target/TargetInstrInfo.h"
28
29using namespace llvm;
30
31char LoopSplitter::ID = 0;
32INITIALIZE_PASS(LoopSplitter, "loop-splitting",
33 "Split virtual regists across loop boundaries.", false, false);
34
35namespace llvm {
36
37 class StartSlotComparator {
38 public:
39 StartSlotComparator(LiveIntervals &lis) : lis(lis) {}
40 bool operator()(const MachineBasicBlock *mbb1,
41 const MachineBasicBlock *mbb2) const {
42 return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2);
43 }
44 private:
45 LiveIntervals &lis;
46 };
47
48 class LoopSplit {
49 public:
50 LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop)
51 : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) {
52 assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
53 "Cannot split physical registers.");
54 }
55
56 LiveInterval& getLI() const { return li; }
57
58 MachineLoop& getLoop() const { return loop; }
59
60 bool isValid() const { return valid; }
61
62 bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); }
63
64 void invalidate() { valid = false; }
65
66 void splitIncoming() { inSplit = true; }
67
68 void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); }
69
70 void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); }
71
72 void apply() {
73 assert(valid && "Attempt to apply invalid split.");
74 applyIncoming();
75 applyOutgoing();
76 copyRanges();
77 renameInside();
78 }
79
80 private:
81 LoopSplitter &ls;
82 LiveInterval &li;
83 MachineLoop &loop;
84 bool valid, inSplit;
85 std::set<MachineLoop::Edge> outSplits;
86 std::vector<MachineInstr*> loopInstrs;
87
88 LiveInterval *newLI;
89 std::map<VNInfo*, VNInfo*> vniMap;
90
91 LiveInterval* getNewLI() {
92 if (newLI == 0) {
93 const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg);
94 unsigned vreg = ls.mri->createVirtualRegister(trc);
95 newLI = &ls.lis->getOrCreateInterval(vreg);
96 }
97 return newLI;
98 }
99
100 VNInfo* getNewVNI(VNInfo *oldVNI) {
101 VNInfo *newVNI = vniMap[oldVNI];
102
103 if (newVNI == 0) {
104 newVNI = getNewLI()->createValueCopy(oldVNI,
105 ls.lis->getVNInfoAllocator());
106 vniMap[oldVNI] = newVNI;
107 }
108
109 return newVNI;
110 }
111
112 void applyIncoming() {
113 if (!inSplit) {
114 return;
115 }
116
117 MachineBasicBlock *preHeader = loop.getLoopPreheader();
118 if (preHeader == 0) {
119 assert(ls.canInsertPreHeader(loop) &&
120 "Can't insert required preheader.");
121 preHeader = &ls.insertPreHeader(loop);
122 }
123
124 LiveRange *preHeaderRange =
125 ls.lis->findExitingRange(li, preHeader);
126 assert(preHeaderRange != 0 && "Range not live into preheader.");
127
128 // Insert the new copy.
129 MachineInstr *copy = BuildMI(*preHeader,
130 preHeader->getFirstTerminator(),
131 DebugLoc(),
132 ls.tii->get(TargetOpcode::COPY))
133 .addReg(getNewLI()->reg, RegState::Define)
134 .addReg(li.reg, RegState::Kill);
135
136 ls.lis->InsertMachineInstrInMaps(copy);
137
138 SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
139
140 VNInfo *newVal = getNewVNI(preHeaderRange->valno);
141 newVal->def = copyDefIdx;
142 newVal->setCopy(copy);
143 newVal->setIsDefAccurate(true);
144 li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
145
146 getNewLI()->addRange(LiveRange(copyDefIdx,
147 ls.lis->getMBBEndIdx(preHeader),
148 newVal));
149 }
150
151 void applyOutgoing() {
152
153 for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(),
154 osEnd = outSplits.end();
155 osItr != osEnd; ++osItr) {
156 MachineLoop::Edge edge = *osItr;
157 MachineBasicBlock *outBlock = edge.second;
158 if (ls.isCriticalEdge(edge)) {
159 assert(ls.canSplitEdge(edge) && "Unsplitable critical edge.");
160 outBlock = &ls.splitEdge(edge, loop);
161 }
162 LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
163 assert(outRange != 0 && "No exiting range?");
164
165 MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
166 DebugLoc(),
167 ls.tii->get(TargetOpcode::COPY))
168 .addReg(li.reg, RegState::Define)
169 .addReg(getNewLI()->reg, RegState::Kill);
170
171 ls.lis->InsertMachineInstrInMaps(copy);
172
173 SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
174
175 // Blow away output range definition.
176 outRange->valno->def = ls.lis->getInvalidIndex();
177 outRange->valno->setIsDefAccurate(false);
178 li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
179
180 VNInfo *newVal =
181 getNewLI()->getNextValue(SlotIndex(ls.lis->getMBBStartIdx(outBlock),
182 true),
183 0, false, ls.lis->getVNInfoAllocator());
184
185 getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
186 copyDefIdx, newVal));
187
188 }
189 }
190
191 void copyRange(LiveRange &lr) {
192 std::pair<bool, LoopSplitter::SlotPair> lsr =
193 ls.getLoopSubRange(lr, loop);
194
195 if (!lsr.first)
196 return;
197
198 LiveRange loopRange(lsr.second.first, lsr.second.second,
199 getNewVNI(lr.valno));
200
201 li.removeRange(loopRange.start, loopRange.end, true);
202
203 getNewLI()->addRange(loopRange);
204 }
205
206 void copyRanges() {
207 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
208 iEnd = loopInstrs.end();
209 iItr != iEnd; ++iItr) {
210 MachineInstr &instr = **iItr;
211 SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr);
212 if (instr.modifiesRegister(li.reg, 0)) {
213 LiveRange *defRange =
214 li.getLiveRangeContaining(instrIdx.getDefIndex());
215 if (defRange != 0) // May have caught this already.
216 copyRange(*defRange);
217 }
218 if (instr.readsRegister(li.reg, 0)) {
219 LiveRange *useRange =
220 li.getLiveRangeContaining(instrIdx.getUseIndex());
221 if (useRange != 0) { // May have caught this already.
222 copyRange(*useRange);
223 }
224 }
225 }
226
227 for (MachineLoop::block_iterator bbItr = loop.block_begin(),
228 bbEnd = loop.block_end();
229 bbItr != bbEnd; ++bbItr) {
230 MachineBasicBlock &loopBlock = **bbItr;
231 LiveRange *enteringRange =
232 ls.lis->findEnteringRange(li, &loopBlock);
233 if (enteringRange != 0) {
234 copyRange(*enteringRange);
235 }
236 }
237 }
238
239 void renameInside() {
240 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
241 iEnd = loopInstrs.end();
242 iItr != iEnd; ++iItr) {
243 MachineInstr &instr = **iItr;
244 for (unsigned i = 0; i < instr.getNumOperands(); ++i) {
245 MachineOperand &mop = instr.getOperand(i);
246 if (mop.isReg() && mop.getReg() == li.reg) {
247 mop.setReg(getNewLI()->reg);
248 }
249 }
250 }
251 }
252
253 };
254
255 void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const {
256 au.addRequired<MachineDominatorTree>();
257 au.addPreserved<MachineDominatorTree>();
258 au.addRequired<MachineLoopInfo>();
259 au.addPreserved<MachineLoopInfo>();
260 au.addPreserved<RegisterCoalescer>();
261 au.addPreserved<CalculateSpillWeights>();
262 au.addPreserved<LiveStacks>();
263 au.addRequired<SlotIndexes>();
264 au.addPreserved<SlotIndexes>();
265 au.addRequired<LiveIntervals>();
266 au.addPreserved<LiveIntervals>();
267 MachineFunctionPass::getAnalysisUsage(au);
268 }
269
270 bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
271
272 mf = &fn;
273 mri = &mf->getRegInfo();
274 tii = mf->getTarget().getInstrInfo();
275 tri = mf->getTarget().getRegisterInfo();
276 sis = &getAnalysis<SlotIndexes>();
277 lis = &getAnalysis<LiveIntervals>();
278 mli = &getAnalysis<MachineLoopInfo>();
279 mdt = &getAnalysis<MachineDominatorTree>();
280
281 fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
282 mf->getFunction()->getName().str();
283
284 dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
285
286 dumpOddTerminators();
287
288// dbgs() << "----------------------------------------\n";
289// lis->dump();
290// dbgs() << "----------------------------------------\n";
291
292// std::deque<MachineLoop*> loops;
293// std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
294// dbgs() << "Loops:\n";
295// while (!loops.empty()) {
296// MachineLoop &loop = *loops.front();
297// loops.pop_front();
298// std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
299
300// dumpLoopInfo(loop);
301// }
302
303 //lis->dump();
304 //exit(0);
305
306 // Setup initial intervals.
307 for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
308 liItr != liEnd; ++liItr) {
309 LiveInterval *li = liItr->second;
310
311 if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
312 !lis->intervalIsInOneMBB(*li)) {
313 intervals.push_back(li);
314 }
315 }
316
317 processIntervals();
318
319 intervals.clear();
320
321// dbgs() << "----------------------------------------\n";
322// lis->dump();
323// dbgs() << "----------------------------------------\n";
324
325 dumpOddTerminators();
326
327 //exit(1);
328
329 return false;
330 }
331
332 void LoopSplitter::releaseMemory() {
333 fqn.clear();
334 intervals.clear();
335 loopRangeMap.clear();
336 }
337
338 void LoopSplitter::dumpOddTerminators() {
339 for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end();
340 bbItr != bbEnd; ++bbItr) {
341 MachineBasicBlock *mbb = &*bbItr;
342 MachineBasicBlock *a = 0, *b = 0;
343 SmallVector<MachineOperand, 4> c;
344 if (tii->AnalyzeBranch(*mbb, a, b, c)) {
345 dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n";
346 dbgs() << " Terminators:\n";
347 for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end();
348 iItr != iEnd; ++iItr) {
349 MachineInstr *instr= &*iItr;
350 dbgs() << " " << *instr << "";
351 }
352 dbgs() << "\n Listed successors: [ ";
353 for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end();
354 sItr != sEnd; ++sItr) {
355 MachineBasicBlock *succMBB = *sItr;
356 dbgs() << succMBB->getNumber() << " ";
357 }
358 dbgs() << "]\n\n";
359 }
360 }
361 }
362
363 void LoopSplitter::dumpLoopInfo(MachineLoop &loop) {
364 MachineBasicBlock &headerBlock = *loop.getHeader();
365 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
366 ExitEdgesList exitEdges;
367 loop.getExitEdges(exitEdges);
368
369 dbgs() << " Header: BB#" << headerBlock.getNumber() << ", Contains: [ ";
370 for (std::vector<MachineBasicBlock*>::const_iterator
371 subBlockItr = loop.getBlocks().begin(),
372 subBlockEnd = loop.getBlocks().end();
373 subBlockItr != subBlockEnd; ++subBlockItr) {
374 MachineBasicBlock &subBlock = **subBlockItr;
375 dbgs() << "BB#" << subBlock.getNumber() << " ";
376 }
377 dbgs() << "], Exit edges: [ ";
378 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
379 exitEdgeEnd = exitEdges.end();
380 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
381 MachineLoop::Edge &exitEdge = *exitEdgeItr;
382 dbgs() << "(MBB#" << exitEdge.first->getNumber()
383 << ", MBB#" << exitEdge.second->getNumber() << ") ";
384 }
385 dbgs() << "], Sub-Loop Headers: [ ";
386 for (MachineLoop::iterator subLoopItr = loop.begin(),
387 subLoopEnd = loop.end();
388 subLoopItr != subLoopEnd; ++subLoopItr) {
389 MachineLoop &subLoop = **subLoopItr;
390 MachineBasicBlock &subLoopBlock = *subLoop.getHeader();
391 dbgs() << "BB#" << subLoopBlock.getNumber() << " ";
392 }
393 dbgs() << "]\n";
394 }
395
396 void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
397 mbb.updateTerminator();
398
399 for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
400 miItr != miEnd; ++miItr) {
401 if (lis->isNotInMIMap(miItr)) {
402 lis->InsertMachineInstrInMaps(miItr);
403 }
404 }
405 }
406
407 bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
408 MachineBasicBlock *header = loop.getHeader();
409 MachineBasicBlock *a = 0, *b = 0;
410 SmallVector<MachineOperand, 4> c;
411
412 for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(),
413 pbEnd = header->pred_end();
414 pbItr != pbEnd; ++pbItr) {
415 MachineBasicBlock *predBlock = *pbItr;
416 if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) {
417 return false;
418 }
419 }
420
421 MachineFunction::iterator headerItr(header);
422 if (headerItr == mf->begin())
423 return true;
424 MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
425 assert(headerLayoutPred != 0 && "Header should have layout pred.");
426
427 return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
428 }
429
430 MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
431 assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
432
433 MachineBasicBlock &header = *loop.getHeader();
434
435 // Save the preds - we'll need to update them once we insert the preheader.
436 typedef std::set<MachineBasicBlock*> HeaderPreds;
437 HeaderPreds headerPreds;
438
439 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
440 predEnd = header.pred_end();
441 predItr != predEnd; ++predItr) {
442 if (!loop.contains(*predItr))
443 headerPreds.insert(*predItr);
444 }
445
446 assert(!headerPreds.empty() && "No predecessors for header?");
447
448 //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
449
450 MachineBasicBlock *preHeader =
451 mf->CreateMachineBasicBlock(header.getBasicBlock());
452
453 assert(preHeader != 0 && "Failed to create pre-header.");
454
455 mf->insert(header, preHeader);
456
457 for (HeaderPreds::iterator hpItr = headerPreds.begin(),
458 hpEnd = headerPreds.end();
459 hpItr != hpEnd; ++hpItr) {
460 assert(*hpItr != 0 && "How'd a null predecessor get into this set?");
461 MachineBasicBlock &hp = **hpItr;
462 hp.ReplaceUsesOfBlockWith(&header, preHeader);
463 }
464 preHeader->addSuccessor(&header);
465
466 MachineBasicBlock *oldLayoutPred =
467 llvm::prior(MachineFunction::iterator(preHeader));
468 if (oldLayoutPred != 0) {
469 updateTerminators(*oldLayoutPred);
470 }
471
472 lis->InsertMBBInMaps(preHeader);
473
474 if (MachineLoop *parentLoop = loop.getParentLoop()) {
475 assert(parentLoop->getHeader() != loop.getHeader() &&
476 "Parent loop has same header?");
477 parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
478
479 // Invalidate all parent loop ranges.
480 while (parentLoop != 0) {
481 loopRangeMap.erase(parentLoop);
482 parentLoop = parentLoop->getParentLoop();
483 }
484 }
485
486 for (LiveIntervals::iterator liItr = lis->begin(),
487 liEnd = lis->end();
488 liItr != liEnd; ++liItr) {
489 LiveInterval &li = *liItr->second;
490
491 // Is this safe for physregs?
492 // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
493 if (!lis->isLiveInToMBB(li, &header))
494 continue;
495
496 if (lis->isLiveInToMBB(li, preHeader)) {
497 assert(lis->isLiveOutOfMBB(li, preHeader) &&
498 "Range terminates in newly added preheader?");
499 continue;
500 }
501
502 bool insertRange = false;
503
504 for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(),
505 predEnd = preHeader->pred_end();
506 predItr != predEnd; ++predItr) {
507 MachineBasicBlock *predMBB = *predItr;
508 if (lis->isLiveOutOfMBB(li, predMBB)) {
509 insertRange = true;
510 break;
511 }
512 }
513
514 if (!insertRange)
515 continue;
516
517 VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(preHeader),
518 0, false, lis->getVNInfoAllocator());
519 li.addRange(LiveRange(lis->getMBBStartIdx(preHeader),
520 lis->getMBBEndIdx(preHeader),
521 newVal));
522 }
523
524
525 //dbgs() << "Dumping SlotIndexes:\n";
526 //sis->dump();
527
528 //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
529
530 return *preHeader;
531 }
532
533 bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
534 assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
535 if (edge.second->pred_size() > 1)
536 return true;
537 return false;
538 }
539
540 bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
541 MachineFunction::iterator outBlockItr(edge.second);
542 if (outBlockItr == mf->begin())
543 return true;
544 MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr);
545 assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin.");
546 MachineBasicBlock *a = 0, *b = 0;
547 SmallVector<MachineOperand, 4> c;
548 return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) &&
549 !tii->AnalyzeBranch(*edge.first, a, b, c));
550 }
551
552 MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
553 MachineLoop &loop) {
554
555 MachineBasicBlock &inBlock = *edge.first;
556 MachineBasicBlock &outBlock = *edge.second;
557
558 assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
559 "Splitting non-critical edge?");
560
561 //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
562 // << " -> MBB#" << outBlock.getNumber() << ")...";
563
564 MachineBasicBlock *splitBlock =
565 mf->CreateMachineBasicBlock();
566
567 assert(splitBlock != 0 && "Failed to create split block.");
568
569 mf->insert(&outBlock, splitBlock);
570
571 inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
572 splitBlock->addSuccessor(&outBlock);
573
574 MachineBasicBlock *oldLayoutPred =
575 llvm::prior(MachineFunction::iterator(splitBlock));
576 if (oldLayoutPred != 0) {
577 updateTerminators(*oldLayoutPred);
578 }
579
580 lis->InsertMBBInMaps(splitBlock);
581
582 loopRangeMap.erase(&loop);
583
584 MachineLoop *splitParentLoop = loop.getParentLoop();
585 while (splitParentLoop != 0 &&
586 !splitParentLoop->contains(&outBlock)) {
587 splitParentLoop = splitParentLoop->getParentLoop();
588 }
589
590 if (splitParentLoop != 0) {
591 assert(splitParentLoop->contains(&loop) &&
592 "Split-block parent doesn't contain original loop?");
593 splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
594
595 // Invalidate all parent loop ranges.
596 while (splitParentLoop != 0) {
597 loopRangeMap.erase(splitParentLoop);
598 splitParentLoop = splitParentLoop->getParentLoop();
599 }
600 }
601
602
603 for (LiveIntervals::iterator liItr = lis->begin(),
604 liEnd = lis->end();
605 liItr != liEnd; ++liItr) {
606 LiveInterval &li = *liItr->second;
607 bool intersects = lis->isLiveOutOfMBB(li, &inBlock) &&
608 lis->isLiveInToMBB(li, &outBlock);
609 if (lis->isLiveInToMBB(li, splitBlock)) {
610 if (!intersects) {
611 li.removeRange(lis->getMBBStartIdx(splitBlock),
612 lis->getMBBEndIdx(splitBlock), true);
613 }
614 } else if (intersects) {
615 VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(splitBlock),
616 0, false, lis->getVNInfoAllocator());
617 li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock),
618 lis->getMBBEndIdx(splitBlock),
619 newVal));
620 }
621 }
622
623 //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
624
625 return *splitBlock;
626 }
627
628 LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) {
629 typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet;
630 LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop);
631 if (lrItr == loopRangeMap.end()) {
632 LoopMBBSet loopMBBs((StartSlotComparator(*lis)));
633 std::copy(loop.block_begin(), loop.block_end(),
634 std::inserter(loopMBBs, loopMBBs.begin()));
635
636 assert(!loopMBBs.empty() && "No blocks in loop?");
637
638 LoopRanges &loopRanges = loopRangeMap[&loop];
639 assert(loopRanges.empty() && "Loop encountered but not processed?");
640 SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin());
641 loopRanges.push_back(
642 std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()),
643 lis->getInvalidIndex()));
644 for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()),
645 curBlockEnd = loopMBBs.end();
646 curBlockItr != curBlockEnd; ++curBlockItr) {
647 SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr);
648 if (newStart != oldEnd) {
649 loopRanges.back().second = oldEnd;
650 loopRanges.push_back(std::make_pair(newStart,
651 lis->getInvalidIndex()));
652 }
653 oldEnd = lis->getMBBEndIdx(*curBlockItr);
654 }
655
656 loopRanges.back().second =
657 lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
658
659 return loopRanges;
660 }
661 return lrItr->second;
662 }
663
664 std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
665 const LiveRange &lr,
666 MachineLoop &loop) {
667 LoopRanges &loopRanges = getLoopRanges(loop);
668 LoopRanges::iterator lrItr = loopRanges.begin(),
669 lrEnd = loopRanges.end();
670 while (lrItr != lrEnd && lr.start >= lrItr->second) {
671 ++lrItr;
672 }
673
674 if (lrItr == lrEnd) {
675 SlotIndex invalid = lis->getInvalidIndex();
676 return std::make_pair(false, SlotPair(invalid, invalid));
677 }
678
679 SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
680 SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
681
682 return std::make_pair(true, SlotPair(srStart, srEnd));
683 }
684
685 void LoopSplitter::dumpLoopRanges(MachineLoop &loop) {
686 LoopRanges &loopRanges = getLoopRanges(loop);
687 dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ ";
688 for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end();
689 lrItr != lrEnd; ++lrItr) {
690 dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") ";
691 }
692 dbgs() << "]\n";
693 }
694
695 void LoopSplitter::processHeader(LoopSplit &split) {
696 MachineBasicBlock &header = *split.getLoop().getHeader();
697 //dbgs() << " Processing loop header BB#" << header.getNumber() << "\n";
698
699 if (!lis->isLiveInToMBB(split.getLI(), &header))
700 return; // Not live in, but nothing wrong so far.
701
702 MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
703 if (!preHeader) {
704
705 if (!canInsertPreHeader(split.getLoop())) {
706 split.invalidate();
707 return; // Couldn't insert a pre-header. Bail on this interval.
708 }
709
710 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
711 predEnd = header.pred_end();
712 predItr != predEnd; ++predItr) {
713 if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) {
714 split.splitIncoming();
715 break;
716 }
717 }
718 } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
719 split.splitIncoming();
720 }
721 }
722
723 void LoopSplitter::processLoopExits(LoopSplit &split) {
724 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
725 ExitEdgesList exitEdges;
726 split.getLoop().getExitEdges(exitEdges);
727
728 //dbgs() << " Processing loop exits:\n";
729
730 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
731 exitEdgeEnd = exitEdges.end();
732 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
733 MachineLoop::Edge exitEdge = *exitEdgeItr;
734
735 LiveRange *outRange =
736 split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
737
738 if (outRange != 0) {
739 if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
740 split.invalidate();
741 return;
742 }
743
744 split.splitOutgoing(exitEdge);
745 }
746 }
747 }
748
749 void LoopSplitter::processLoopUses(LoopSplit &split) {
750 std::set<MachineInstr*> processed;
751
752 for (MachineRegisterInfo::reg_iterator
753 rItr = mri->reg_begin(split.getLI().reg),
754 rEnd = mri->reg_end();
755 rItr != rEnd; ++rItr) {
756 MachineInstr &instr = *rItr;
757 if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) {
758 split.addLoopInstr(&instr);
759 processed.insert(&instr);
760 }
761 }
762
763 //dbgs() << " Rewriting reg" << li.reg << " to reg" << newLI->reg
764 // << " in blocks [ ";
765 //dbgs() << "]\n";
766 }
767
768 bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
769 assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
770 "Attempt to split physical register.");
771
772 LoopSplit split(*this, li, loop);
773 processHeader(split);
774 if (split.isValid())
775 processLoopExits(split);
776 if (split.isValid())
777 processLoopUses(split);
778 if (split.isValid() /* && split.isWorthwhile() */) {
779 split.apply();
780 DEBUG(dbgs() << "Success.\n");
781 return true;
782 }
783 DEBUG(dbgs() << "Failed.\n");
784 return false;
785 }
786
787 void LoopSplitter::processInterval(LiveInterval &li) {
788 std::deque<MachineLoop*> loops;
789 std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
790
791 while (!loops.empty()) {
792 MachineLoop &loop = *loops.front();
793 loops.pop_front();
794 DEBUG(
795 dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
796 << loop.getHeader()->getNumber() << " ";
797 );
798 if (!splitOverLoop(li, loop)) {
799 // Couldn't split over outer loop, schedule sub-loops to be checked.
800 std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
801 }
802 }
803 }
804
805 void LoopSplitter::processIntervals() {
806 while (!intervals.empty()) {
807 LiveInterval &li = *intervals.front();
808 intervals.pop_front();
809
810 assert(!lis->intervalIsInOneMBB(li) &&
811 "Single interval in process worklist.");
812
813 processInterval(li);
814 }
815 }
816
817}
Note: See TracBrowser for help on using the repository browser.