← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/StrongPHIElimination.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/StrongPHIElimination.cpp
 
1
//===- StrongPhiElimination.cpp - Eliminate PHI nodes by inserting copies -===//
 
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
// This pass eliminates machine instruction PHI nodes by inserting copy
 
11
// instructions, using an intelligent copy-folding technique based on
 
12
// dominator information.  This is technique is derived from:
 
13
// 
 
14
//    Budimlic, et al. Fast copy coalescing and live-range identification.
 
15
//    In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language
 
16
//    Design and Implementation (Berlin, Germany, June 17 - 19, 2002).
 
17
//    PLDI '02. ACM, New York, NY, 25-32.
 
18
//    DOI= http://doi.acm.org/10.1145/512529.512534
 
19
//
 
20
//===----------------------------------------------------------------------===//
 
21
 
 
22
#define DEBUG_TYPE "strongphielim"
 
23
#include "llvm/CodeGen/Passes.h"
 
24
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 
25
#include "llvm/CodeGen/MachineDominators.h"
 
26
#include "llvm/CodeGen/MachineFunctionPass.h"
 
27
#include "llvm/CodeGen/MachineInstr.h"
 
28
#include "llvm/CodeGen/MachineLoopInfo.h"
 
29
#include "llvm/CodeGen/MachineRegisterInfo.h"
 
30
#include "llvm/CodeGen/RegisterCoalescer.h"
 
31
#include "llvm/Target/TargetInstrInfo.h"
 
32
#include "llvm/Target/TargetMachine.h"
 
33
#include "llvm/ADT/DepthFirstIterator.h"
 
34
#include "llvm/ADT/Statistic.h"
 
35
#include "llvm/Support/Debug.h"
 
36
using namespace llvm;
 
37
 
 
38
namespace {
 
39
  struct StrongPHIElimination : public MachineFunctionPass {
 
40
    static char ID; // Pass identification, replacement for typeid
 
41
    StrongPHIElimination() : MachineFunctionPass(&ID) {}
 
42
 
 
43
    // Waiting stores, for each MBB, the set of copies that need to
 
44
    // be inserted into that MBB
 
45
    DenseMap<MachineBasicBlock*,
 
46
             std::multimap<unsigned, unsigned> > Waiting;
 
47
    
 
48
    // Stacks holds the renaming stack for each register
 
49
    std::map<unsigned, std::vector<unsigned> > Stacks;
 
50
    
 
51
    // Registers in UsedByAnother are PHI nodes that are themselves
 
52
    // used as operands to another PHI node
 
53
    std::set<unsigned> UsedByAnother;
 
54
    
 
55
    // RenameSets are the is a map from a PHI-defined register
 
56
    // to the input registers to be coalesced along with the 
 
57
    // predecessor block for those input registers.
 
58
    std::map<unsigned, std::map<unsigned, MachineBasicBlock*> > RenameSets;
 
59
    
 
60
    // PhiValueNumber holds the ID numbers of the VNs for each phi that we're
 
61
    // eliminating, indexed by the register defined by that phi.
 
62
    std::map<unsigned, unsigned> PhiValueNumber;
 
63
 
 
64
    // Store the DFS-in number of each block
 
65
    DenseMap<MachineBasicBlock*, unsigned> preorder;
 
66
    
 
67
    // Store the DFS-out number of each block
 
68
    DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
 
69
 
 
70
    bool runOnMachineFunction(MachineFunction &Fn);
 
71
    
 
72
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
73
      AU.setPreservesCFG();
 
74
      AU.addRequired<MachineDominatorTree>();
 
75
      AU.addRequired<SlotIndexes>();
 
76
      AU.addPreserved<SlotIndexes>();
 
77
      AU.addRequired<LiveIntervals>();
 
78
      
 
79
      // TODO: Actually make this true.
 
80
      AU.addPreserved<LiveIntervals>();
 
81
      AU.addPreserved<RegisterCoalescer>();
 
82
      MachineFunctionPass::getAnalysisUsage(AU);
 
83
    }
 
84
    
 
85
    virtual void releaseMemory() {
 
86
      preorder.clear();
 
87
      maxpreorder.clear();
 
88
      
 
89
      Waiting.clear();
 
90
      Stacks.clear();
 
91
      UsedByAnother.clear();
 
92
      RenameSets.clear();
 
93
    }
 
94
 
 
95
  private:
 
96
    
 
97
    /// DomForestNode - Represents a node in the "dominator forest".  This is
 
98
    /// a forest in which the nodes represent registers and the edges
 
99
    /// represent a dominance relation in the block defining those registers.
 
100
    struct DomForestNode {
 
101
    private:
 
102
      // Store references to our children
 
103
      std::vector<DomForestNode*> children;
 
104
      // The register we represent
 
105
      unsigned reg;
 
106
      
 
107
      // Add another node as our child
 
108
      void addChild(DomForestNode* DFN) { children.push_back(DFN); }
 
109
      
 
110
    public:
 
111
      typedef std::vector<DomForestNode*>::iterator iterator;
 
112
      
 
113
      // Create a DomForestNode by providing the register it represents, and
 
114
      // the node to be its parent.  The virtual root node has register 0
 
115
      // and a null parent.
 
116
      DomForestNode(unsigned r, DomForestNode* parent) : reg(r) {
 
117
        if (parent)
 
118
          parent->addChild(this);
 
119
      }
 
120
      
 
121
      ~DomForestNode() {
 
122
        for (iterator I = begin(), E = end(); I != E; ++I)
 
123
          delete *I;
 
124
      }
 
125
      
 
126
      /// getReg - Return the regiser that this node represents
 
127
      inline unsigned getReg() { return reg; }
 
128
      
 
129
      // Provide iterator access to our children
 
130
      inline DomForestNode::iterator begin() { return children.begin(); }
 
131
      inline DomForestNode::iterator end() { return children.end(); }
 
132
    };
 
133
    
 
134
    void computeDFS(MachineFunction& MF);
 
135
    void processBlock(MachineBasicBlock* MBB);
 
136
    
 
137
    std::vector<DomForestNode*> computeDomForest(
 
138
                           std::map<unsigned, MachineBasicBlock*>& instrs,
 
139
                                                 MachineRegisterInfo& MRI);
 
140
    void processPHIUnion(MachineInstr* Inst,
 
141
                         std::map<unsigned, MachineBasicBlock*>& PHIUnion,
 
142
                         std::vector<StrongPHIElimination::DomForestNode*>& DF,
 
143
                         std::vector<std::pair<unsigned, unsigned> >& locals);
 
144
    void ScheduleCopies(MachineBasicBlock* MBB, std::set<unsigned>& pushed);
 
145
    void InsertCopies(MachineDomTreeNode* MBB,
 
146
                      SmallPtrSet<MachineBasicBlock*, 16>& v);
 
147
    bool mergeLiveIntervals(unsigned primary, unsigned secondary);
 
148
  };
 
149
}
 
150
 
 
151
char StrongPHIElimination::ID = 0;
 
152
static RegisterPass<StrongPHIElimination>
 
153
X("strong-phi-node-elimination",
 
154
  "Eliminate PHI nodes for register allocation, intelligently");
 
155
 
 
156
const PassInfo *const llvm::StrongPHIEliminationID = &X;
 
157
 
 
158
/// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree
 
159
/// of the given MachineFunction.  These numbers are then used in other parts
 
160
/// of the PHI elimination process.
 
161
void StrongPHIElimination::computeDFS(MachineFunction& MF) {
 
162
  SmallPtrSet<MachineDomTreeNode*, 8> frontier;
 
163
  SmallPtrSet<MachineDomTreeNode*, 8> visited;
 
164
  
 
165
  unsigned time = 0;
 
166
  
 
167
  MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>();
 
168
  
 
169
  MachineDomTreeNode* node = DT.getRootNode();
 
170
  
 
171
  std::vector<MachineDomTreeNode*> worklist;
 
172
  worklist.push_back(node);
 
173
  
 
174
  while (!worklist.empty()) {
 
175
    MachineDomTreeNode* currNode = worklist.back();
 
176
    
 
177
    if (!frontier.count(currNode)) {
 
178
      frontier.insert(currNode);
 
179
      ++time;
 
180
      preorder.insert(std::make_pair(currNode->getBlock(), time));
 
181
    }
 
182
    
 
183
    bool inserted = false;
 
184
    for (MachineDomTreeNode::iterator I = currNode->begin(), E = currNode->end();
 
185
         I != E; ++I)
 
186
      if (!frontier.count(*I) && !visited.count(*I)) {
 
187
        worklist.push_back(*I);
 
188
        inserted = true;
 
189
        break;
 
190
      }
 
191
    
 
192
    if (!inserted) {
 
193
      frontier.erase(currNode);
 
194
      visited.insert(currNode);
 
195
      maxpreorder.insert(std::make_pair(currNode->getBlock(), time));
 
196
      
 
197
      worklist.pop_back();
 
198
    }
 
199
  }
 
200
}
 
201
 
 
202
namespace {
 
203
 
 
204
/// PreorderSorter - a helper class that is used to sort registers
 
205
/// according to the preorder number of their defining blocks
 
206
class PreorderSorter {
 
207
private:
 
208
  DenseMap<MachineBasicBlock*, unsigned>& preorder;
 
209
  MachineRegisterInfo& MRI;
 
210
  
 
211
public:
 
212
  PreorderSorter(DenseMap<MachineBasicBlock*, unsigned>& p,
 
213
                MachineRegisterInfo& M) : preorder(p), MRI(M) { }
 
214
  
 
215
  bool operator()(unsigned A, unsigned B) {
 
216
    if (A == B)
 
217
      return false;
 
218
    
 
219
    MachineBasicBlock* ABlock = MRI.getVRegDef(A)->getParent();
 
220
    MachineBasicBlock* BBlock = MRI.getVRegDef(B)->getParent();
 
221
    
 
222
    if (preorder[ABlock] < preorder[BBlock])
 
223
      return true;
 
224
    else if (preorder[ABlock] > preorder[BBlock])
 
225
      return false;
 
226
    
 
227
    return false;
 
228
  }
 
229
};
 
230
 
 
231
}
 
232
 
 
233
/// computeDomForest - compute the subforest of the DomTree corresponding
 
234
/// to the defining blocks of the registers in question
 
235
std::vector<StrongPHIElimination::DomForestNode*>
 
236
StrongPHIElimination::computeDomForest(
 
237
                  std::map<unsigned, MachineBasicBlock*>& regs, 
 
238
                                       MachineRegisterInfo& MRI) {
 
239
  // Begin by creating a virtual root node, since the actual results
 
240
  // may well be a forest.  Assume this node has maximum DFS-out number.
 
241
  DomForestNode* VirtualRoot = new DomForestNode(0, 0);
 
242
  maxpreorder.insert(std::make_pair((MachineBasicBlock*)0, ~0UL));
 
243
  
 
244
  // Populate a worklist with the registers
 
245
  std::vector<unsigned> worklist;
 
246
  worklist.reserve(regs.size());
 
247
  for (std::map<unsigned, MachineBasicBlock*>::iterator I = regs.begin(),
 
248
       E = regs.end(); I != E; ++I)
 
249
    worklist.push_back(I->first);
 
250
  
 
251
  // Sort the registers by the DFS-in number of their defining block
 
252
  PreorderSorter PS(preorder, MRI);
 
253
  std::sort(worklist.begin(), worklist.end(), PS);
 
254
  
 
255
  // Create a "current parent" stack, and put the virtual root on top of it
 
256
  DomForestNode* CurrentParent = VirtualRoot;
 
257
  std::vector<DomForestNode*> stack;
 
258
  stack.push_back(VirtualRoot);
 
259
  
 
260
  // Iterate over all the registers in the previously computed order
 
261
  for (std::vector<unsigned>::iterator I = worklist.begin(), E = worklist.end();
 
262
       I != E; ++I) {
 
263
    unsigned pre = preorder[MRI.getVRegDef(*I)->getParent()];
 
264
    MachineBasicBlock* parentBlock = CurrentParent->getReg() ?
 
265
                 MRI.getVRegDef(CurrentParent->getReg())->getParent() :
 
266
                 0;
 
267
    
 
268
    // If the DFS-in number of the register is greater than the DFS-out number
 
269
    // of the current parent, repeatedly pop the parent stack until it isn't.
 
270
    while (pre > maxpreorder[parentBlock]) {
 
271
      stack.pop_back();
 
272
      CurrentParent = stack.back();
 
273
      
 
274
      parentBlock = CurrentParent->getReg() ?
 
275
                   MRI.getVRegDef(CurrentParent->getReg())->getParent() :
 
276
                   0;
 
277
    }
 
278
    
 
279
    // Now that we've found the appropriate parent, create a DomForestNode for
 
280
    // this register and attach it to the forest
 
281
    DomForestNode* child = new DomForestNode(*I, CurrentParent);
 
282
    
 
283
    // Push this new node on the "current parent" stack
 
284
    stack.push_back(child);
 
285
    CurrentParent = child;
 
286
  }
 
287
  
 
288
  // Return a vector containing the children of the virtual root node
 
289
  std::vector<DomForestNode*> ret;
 
290
  ret.insert(ret.end(), VirtualRoot->begin(), VirtualRoot->end());
 
291
  return ret;
 
292
}
 
293
 
 
294
/// isLiveIn - helper method that determines, from a regno, if a register
 
295
/// is live into a block
 
296
static bool isLiveIn(unsigned r, MachineBasicBlock* MBB,
 
297
                     LiveIntervals& LI) {
 
298
  LiveInterval& I = LI.getOrCreateInterval(r);
 
299
  SlotIndex idx = LI.getMBBStartIdx(MBB);
 
300
  return I.liveAt(idx);
 
301
}
 
302
 
 
303
/// isLiveOut - help method that determines, from a regno, if a register is
 
304
/// live out of a block.
 
305
static bool isLiveOut(unsigned r, MachineBasicBlock* MBB,
 
306
                      LiveIntervals& LI) {
 
307
  for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
 
308
       E = MBB->succ_end(); PI != E; ++PI)
 
309
    if (isLiveIn(r, *PI, LI))
 
310
      return true;
 
311
  
 
312
  return false;
 
313
}
 
314
 
 
315
/// interferes - checks for local interferences by scanning a block.  The only
 
316
/// trick parameter is 'mode' which tells it the relationship of the two
 
317
/// registers. 0 - defined in the same block, 1 - first properly dominates
 
318
/// second, 2 - second properly dominates first 
 
319
static bool interferes(unsigned a, unsigned b, MachineBasicBlock* scan,
 
320
                       LiveIntervals& LV, unsigned mode) {
 
321
  MachineInstr* def = 0;
 
322
  MachineInstr* kill = 0;
 
323
  
 
324
  // The code is still in SSA form at this point, so there is only one
 
325
  // definition per VReg.  Thus we can safely use MRI->getVRegDef().
 
326
  const MachineRegisterInfo* MRI = &scan->getParent()->getRegInfo();
 
327
  
 
328
  bool interference = false;
 
329
  
 
330
  // Wallk the block, checking for interferences
 
331
  for (MachineBasicBlock::iterator MBI = scan->begin(), MBE = scan->end();
 
332
       MBI != MBE; ++MBI) {
 
333
    MachineInstr* curr = MBI;
 
334
    
 
335
    // Same defining block...
 
336
    if (mode == 0) {
 
337
      if (curr == MRI->getVRegDef(a)) {
 
338
        // If we find our first definition, save it
 
339
        if (!def) {
 
340
          def = curr;
 
341
        // If there's already an unkilled definition, then 
 
342
        // this is an interference
 
343
        } else if (!kill) {
 
344
          interference = true;
 
345
          break;
 
346
        // If there's a definition followed by a KillInst, then
 
347
        // they can't interfere
 
348
        } else {
 
349
          interference = false;
 
350
          break;
 
351
        }
 
352
      // Symmetric with the above
 
353
      } else if (curr == MRI->getVRegDef(b)) {
 
354
        if (!def) {
 
355
          def = curr;
 
356
        } else if (!kill) {
 
357
          interference = true;
 
358
          break;
 
359
        } else {
 
360
          interference = false;
 
361
          break;
 
362
        }
 
363
      // Store KillInsts if they match up with the definition
 
364
      } else if (curr->killsRegister(a)) {
 
365
        if (def == MRI->getVRegDef(a)) {
 
366
          kill = curr;
 
367
        } else if (curr->killsRegister(b)) {
 
368
          if (def == MRI->getVRegDef(b)) {
 
369
            kill = curr;
 
370
          }
 
371
        }
 
372
      }
 
373
    // First properly dominates second...
 
374
    } else if (mode == 1) {
 
375
      if (curr == MRI->getVRegDef(b)) {
 
376
        // Definition of second without kill of first is an interference
 
377
        if (!kill) {
 
378
          interference = true;
 
379
          break;
 
380
        // Definition after a kill is a non-interference
 
381
        } else {
 
382
          interference = false;
 
383
          break;
 
384
        }
 
385
      // Save KillInsts of First
 
386
      } else if (curr->killsRegister(a)) {
 
387
        kill = curr;
 
388
      }
 
389
    // Symmetric with the above
 
390
    } else if (mode == 2) {
 
391
      if (curr == MRI->getVRegDef(a)) {
 
392
        if (!kill) {
 
393
          interference = true;
 
394
          break;
 
395
        } else {
 
396
          interference = false;
 
397
          break;
 
398
        }
 
399
      } else if (curr->killsRegister(b)) {
 
400
        kill = curr;
 
401
      }
 
402
    }
 
403
  }
 
404
  
 
405
  return interference;
 
406
}
 
407
 
 
408
/// processBlock - Determine how to break up PHIs in the current block.  Each
 
409
/// PHI is broken up by some combination of renaming its operands and inserting
 
410
/// copies.  This method is responsible for determining which operands receive
 
411
/// which treatment.
 
412
void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
 
413
  LiveIntervals& LI = getAnalysis<LiveIntervals>();
 
414
  MachineRegisterInfo& MRI = MBB->getParent()->getRegInfo();
 
415
  
 
416
  // Holds names that have been added to a set in any PHI within this block
 
417
  // before the current one.
 
418
  std::set<unsigned> ProcessedNames;
 
419
  
 
420
  // Iterate over all the PHI nodes in this block
 
421
  MachineBasicBlock::iterator P = MBB->begin();
 
422
  while (P != MBB->end() && P->isPHI()) {
 
423
    unsigned DestReg = P->getOperand(0).getReg();
 
424
    
 
425
    // Don't both doing PHI elimination for dead PHI's.
 
426
    if (P->registerDefIsDead(DestReg)) {
 
427
      ++P;
 
428
      continue;
 
429
    }
 
430
 
 
431
    LiveInterval& PI = LI.getOrCreateInterval(DestReg);
 
432
    SlotIndex pIdx = LI.getInstructionIndex(P).getDefIndex();
 
433
    VNInfo* PVN = PI.getLiveRangeContaining(pIdx)->valno;
 
434
    PhiValueNumber.insert(std::make_pair(DestReg, PVN->id));
 
435
 
 
436
    // PHIUnion is the set of incoming registers to the PHI node that
 
437
    // are going to be renames rather than having copies inserted.  This set
 
438
    // is refinded over the course of this function.  UnionedBlocks is the set
 
439
    // of corresponding MBBs.
 
440
    std::map<unsigned, MachineBasicBlock*> PHIUnion;
 
441
    SmallPtrSet<MachineBasicBlock*, 8> UnionedBlocks;
 
442
  
 
443
    // Iterate over the operands of the PHI node
 
444
    for (int i = P->getNumOperands() - 1; i >= 2; i-=2) {
 
445
      unsigned SrcReg = P->getOperand(i-1).getReg();
 
446
      
 
447
      // Don't need to try to coalesce a register with itself.
 
448
      if (SrcReg == DestReg) {
 
449
        ProcessedNames.insert(SrcReg);
 
450
        continue;
 
451
      }
 
452
      
 
453
      // We don't need to insert copies for implicit_defs.
 
454
      MachineInstr* DefMI = MRI.getVRegDef(SrcReg);
 
455
      if (DefMI->isImplicitDef())
 
456
        ProcessedNames.insert(SrcReg);
 
457
    
 
458
      // Check for trivial interferences via liveness information, allowing us
 
459
      // to avoid extra work later.  Any registers that interfere cannot both
 
460
      // be in the renaming set, so choose one and add copies for it instead.
 
461
      // The conditions are:
 
462
      //   1) if the operand is live into the PHI node's block OR
 
463
      //   2) if the PHI node is live out of the operand's defining block OR
 
464
      //   3) if the operand is itself a PHI node and the original PHI is
 
465
      //      live into the operand's defining block OR
 
466
      //   4) if the operand is already being renamed for another PHI node
 
467
      //      in this block OR
 
468
      //   5) if any two operands are defined in the same block, insert copies
 
469
      //      for one of them
 
470
      if (isLiveIn(SrcReg, P->getParent(), LI) ||
 
471
          isLiveOut(P->getOperand(0).getReg(),
 
472
                    MRI.getVRegDef(SrcReg)->getParent(), LI) ||
 
473
          ( MRI.getVRegDef(SrcReg)->isPHI() &&
 
474
            isLiveIn(P->getOperand(0).getReg(),
 
475
                     MRI.getVRegDef(SrcReg)->getParent(), LI) ) ||
 
476
          ProcessedNames.count(SrcReg) ||
 
477
          UnionedBlocks.count(MRI.getVRegDef(SrcReg)->getParent())) {
 
478
        
 
479
        // Add a copy for the selected register
 
480
        MachineBasicBlock* From = P->getOperand(i).getMBB();
 
481
        Waiting[From].insert(std::make_pair(SrcReg, DestReg));
 
482
        UsedByAnother.insert(SrcReg);
 
483
      } else {
 
484
        // Otherwise, add it to the renaming set
 
485
        PHIUnion.insert(std::make_pair(SrcReg,P->getOperand(i).getMBB()));
 
486
        UnionedBlocks.insert(MRI.getVRegDef(SrcReg)->getParent());
 
487
      }
 
488
    }
 
489
    
 
490
    // Compute the dominator forest for the renaming set.  This is a forest
 
491
    // where the nodes are the registers and the edges represent dominance 
 
492
    // relations between the defining blocks of the registers
 
493
    std::vector<StrongPHIElimination::DomForestNode*> DF = 
 
494
                                                computeDomForest(PHIUnion, MRI);
 
495
    
 
496
    // Walk DomForest to resolve interferences at an inter-block level.  This
 
497
    // will remove registers from the renaming set (and insert copies for them)
 
498
    // if interferences are found.
 
499
    std::vector<std::pair<unsigned, unsigned> > localInterferences;
 
500
    processPHIUnion(P, PHIUnion, DF, localInterferences);
 
501
    
 
502
    // If one of the inputs is defined in the same block as the current PHI
 
503
    // then we need to check for a local interference between that input and
 
504
    // the PHI.
 
505
    for (std::map<unsigned, MachineBasicBlock*>::iterator I = PHIUnion.begin(),
 
506
         E = PHIUnion.end(); I != E; ++I)
 
507
      if (MRI.getVRegDef(I->first)->getParent() == P->getParent())
 
508
        localInterferences.push_back(std::make_pair(I->first,
 
509
                                                    P->getOperand(0).getReg()));
 
510
    
 
511
    // The dominator forest walk may have returned some register pairs whose
 
512
    // interference cannot be determined from dominator analysis.  We now 
 
513
    // examine these pairs for local interferences.
 
514
    for (std::vector<std::pair<unsigned, unsigned> >::iterator I =
 
515
        localInterferences.begin(), E = localInterferences.end(); I != E; ++I) {
 
516
      std::pair<unsigned, unsigned> p = *I;
 
517
      
 
518
      MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
 
519
      
 
520
      // Determine the block we need to scan and the relationship between
 
521
      // the two registers
 
522
      MachineBasicBlock* scan = 0;
 
523
      unsigned mode = 0;
 
524
      if (MRI.getVRegDef(p.first)->getParent() ==
 
525
          MRI.getVRegDef(p.second)->getParent()) {
 
526
        scan = MRI.getVRegDef(p.first)->getParent();
 
527
        mode = 0; // Same block
 
528
      } else if (MDT.dominates(MRI.getVRegDef(p.first)->getParent(),
 
529
                               MRI.getVRegDef(p.second)->getParent())) {
 
530
        scan = MRI.getVRegDef(p.second)->getParent();
 
531
        mode = 1; // First dominates second
 
532
      } else {
 
533
        scan = MRI.getVRegDef(p.first)->getParent();
 
534
        mode = 2; // Second dominates first
 
535
      }
 
536
      
 
537
      // If there's an interference, we need to insert  copies
 
538
      if (interferes(p.first, p.second, scan, LI, mode)) {
 
539
        // Insert copies for First
 
540
        for (int i = P->getNumOperands() - 1; i >= 2; i-=2) {
 
541
          if (P->getOperand(i-1).getReg() == p.first) {
 
542
            unsigned SrcReg = p.first;
 
543
            MachineBasicBlock* From = P->getOperand(i).getMBB();
 
544
            
 
545
            Waiting[From].insert(std::make_pair(SrcReg,
 
546
                                                P->getOperand(0).getReg()));
 
547
            UsedByAnother.insert(SrcReg);
 
548
            
 
549
            PHIUnion.erase(SrcReg);
 
550
          }
 
551
        }
 
552
      }
 
553
    }
 
554
    
 
555
    // Add the renaming set for this PHI node to our overall renaming information
 
556
    for (std::map<unsigned, MachineBasicBlock*>::iterator QI = PHIUnion.begin(),
 
557
         QE = PHIUnion.end(); QI != QE; ++QI) {
 
558
      DEBUG(dbgs() << "Adding Renaming: " << QI->first << " -> "
 
559
                   << P->getOperand(0).getReg() << "\n");
 
560
    }
 
561
    
 
562
    RenameSets.insert(std::make_pair(P->getOperand(0).getReg(), PHIUnion));
 
563
    
 
564
    // Remember which registers are already renamed, so that we don't try to 
 
565
    // rename them for another PHI node in this block
 
566
    for (std::map<unsigned, MachineBasicBlock*>::iterator I = PHIUnion.begin(),
 
567
         E = PHIUnion.end(); I != E; ++I)
 
568
      ProcessedNames.insert(I->first);
 
569
    
 
570
    ++P;
 
571
  }
 
572
}
 
573
 
 
574
/// processPHIUnion - Take a set of candidate registers to be coalesced when
 
575
/// decomposing the PHI instruction.  Use the DominanceForest to remove the ones
 
576
/// that are known to interfere, and flag others that need to be checked for
 
577
/// local interferences.
 
578
void StrongPHIElimination::processPHIUnion(MachineInstr* Inst,
 
579
                        std::map<unsigned, MachineBasicBlock*>& PHIUnion,
 
580
                        std::vector<StrongPHIElimination::DomForestNode*>& DF,
 
581
                        std::vector<std::pair<unsigned, unsigned> >& locals) {
 
582
  
 
583
  std::vector<DomForestNode*> worklist(DF.begin(), DF.end());
 
584
  SmallPtrSet<DomForestNode*, 4> visited;
 
585
  
 
586
  // Code is still in SSA form, so we can use MRI::getVRegDef()
 
587
  MachineRegisterInfo& MRI = Inst->getParent()->getParent()->getRegInfo();
 
588
  
 
589
  LiveIntervals& LI = getAnalysis<LiveIntervals>();
 
590
  unsigned DestReg = Inst->getOperand(0).getReg();
 
591
  
 
592
  // DF walk on the DomForest
 
593
  while (!worklist.empty()) {
 
594
    DomForestNode* DFNode = worklist.back();
 
595
    
 
596
    visited.insert(DFNode);
 
597
    
 
598
    bool inserted = false;
 
599
    for (DomForestNode::iterator CI = DFNode->begin(), CE = DFNode->end();
 
600
         CI != CE; ++CI) {
 
601
      DomForestNode* child = *CI;   
 
602
      
 
603
      // If the current node is live-out of the defining block of one of its
 
604
      // children, insert a copy for it.  NOTE: The paper actually calls for
 
605
      // a more elaborate heuristic for determining whether to insert copies
 
606
      // for the child or the parent.  In the interest of simplicity, we're
 
607
      // just always choosing the parent.
 
608
      if (isLiveOut(DFNode->getReg(),
 
609
          MRI.getVRegDef(child->getReg())->getParent(), LI)) {
 
610
        // Insert copies for parent
 
611
        for (int i = Inst->getNumOperands() - 1; i >= 2; i-=2) {
 
612
          if (Inst->getOperand(i-1).getReg() == DFNode->getReg()) {
 
613
            unsigned SrcReg = DFNode->getReg();
 
614
            MachineBasicBlock* From = Inst->getOperand(i).getMBB();
 
615
            
 
616
            Waiting[From].insert(std::make_pair(SrcReg, DestReg));
 
617
            UsedByAnother.insert(SrcReg);
 
618
            
 
619
            PHIUnion.erase(SrcReg);
 
620
          }
 
621
        }
 
622
      
 
623
      // If a node is live-in to the defining block of one of its children, but
 
624
      // not live-out, then we need to scan that block for local interferences.
 
625
      } else if (isLiveIn(DFNode->getReg(),
 
626
                          MRI.getVRegDef(child->getReg())->getParent(), LI) ||
 
627
                 MRI.getVRegDef(DFNode->getReg())->getParent() ==
 
628
                                 MRI.getVRegDef(child->getReg())->getParent()) {
 
629
        // Add (p, c) to possible local interferences
 
630
        locals.push_back(std::make_pair(DFNode->getReg(), child->getReg()));
 
631
      }
 
632
      
 
633
      if (!visited.count(child)) {
 
634
        worklist.push_back(child);
 
635
        inserted = true;
 
636
      }
 
637
    }
 
638
    
 
639
    if (!inserted) worklist.pop_back();
 
640
  }
 
641
}
 
642
 
 
643
/// ScheduleCopies - Insert copies into predecessor blocks, scheduling
 
644
/// them properly so as to avoid the 'lost copy' and the 'virtual swap'
 
645
/// problems.
 
646
///
 
647
/// Based on "Practical Improvements to the Construction and Destruction
 
648
/// of Static Single Assignment Form" by Briggs, et al.
 
649
void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
 
650
                                          std::set<unsigned>& pushed) {
 
651
  // FIXME: This function needs to update LiveIntervals
 
652
  std::multimap<unsigned, unsigned>& copy_set= Waiting[MBB];
 
653
  
 
654
  std::multimap<unsigned, unsigned> worklist;
 
655
  std::map<unsigned, unsigned> map;
 
656
  
 
657
  // Setup worklist of initial copies
 
658
  for (std::multimap<unsigned, unsigned>::iterator I = copy_set.begin(),
 
659
       E = copy_set.end(); I != E; ) {
 
660
    map.insert(std::make_pair(I->first, I->first));
 
661
    map.insert(std::make_pair(I->second, I->second));
 
662
         
 
663
    if (!UsedByAnother.count(I->second)) {
 
664
      worklist.insert(*I);
 
665
      
 
666
      // Avoid iterator invalidation
 
667
      std::multimap<unsigned, unsigned>::iterator OI = I;
 
668
      ++I;
 
669
      copy_set.erase(OI);
 
670
    } else {
 
671
      ++I;
 
672
    }
 
673
  }
 
674
  
 
675
  LiveIntervals& LI = getAnalysis<LiveIntervals>();
 
676
  MachineFunction* MF = MBB->getParent();
 
677
  MachineRegisterInfo& MRI = MF->getRegInfo();
 
678
  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
 
679
  
 
680
  SmallVector<std::pair<unsigned, MachineInstr*>, 4> InsertedPHIDests;
 
681
  
 
682
  // Iterate over the worklist, inserting copies
 
683
  while (!worklist.empty() || !copy_set.empty()) {
 
684
    while (!worklist.empty()) {
 
685
      std::multimap<unsigned, unsigned>::iterator WI = worklist.begin();
 
686
      std::pair<unsigned, unsigned> curr = *WI;
 
687
      worklist.erase(WI);
 
688
      
 
689
      const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first);
 
690
      
 
691
      if (isLiveOut(curr.second, MBB, LI)) {
 
692
        // Create a temporary
 
693
        unsigned t = MF->getRegInfo().createVirtualRegister(RC);
 
694
        
 
695
        // Insert copy from curr.second to a temporary at
 
696
        // the Phi defining curr.second
 
697
        MachineBasicBlock::iterator PI = MRI.getVRegDef(curr.second);
 
698
        TII->copyRegToReg(*PI->getParent(), PI, t,
 
699
                          curr.second, RC, RC);
 
700
        
 
701
        DEBUG(dbgs() << "Inserted copy from " << curr.second << " to " << t
 
702
                     << "\n");
 
703
        
 
704
        // Push temporary on Stacks
 
705
        Stacks[curr.second].push_back(t);
 
706
        
 
707
        // Insert curr.second in pushed
 
708
        pushed.insert(curr.second);
 
709
        
 
710
        // Create a live interval for this temporary
 
711
        InsertedPHIDests.push_back(std::make_pair(t, --PI));
 
712
      }
 
713
      
 
714
      // Insert copy from map[curr.first] to curr.second
 
715
      TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), curr.second,
 
716
                        map[curr.first], RC, RC);
 
717
      map[curr.first] = curr.second;
 
718
      DEBUG(dbgs() << "Inserted copy from " << curr.first << " to "
 
719
                   << curr.second << "\n");
 
720
      
 
721
      // Push this copy onto InsertedPHICopies so we can
 
722
      // update LiveIntervals with it.
 
723
      MachineBasicBlock::iterator MI = MBB->getFirstTerminator();
 
724
      InsertedPHIDests.push_back(std::make_pair(curr.second, --MI));
 
725
      
 
726
      // If curr.first is a destination in copy_set...
 
727
      for (std::multimap<unsigned, unsigned>::iterator I = copy_set.begin(),
 
728
           E = copy_set.end(); I != E; )
 
729
        if (curr.first == I->second) {
 
730
          std::pair<unsigned, unsigned> temp = *I;
 
731
          worklist.insert(temp);
 
732
          
 
733
          // Avoid iterator invalidation
 
734
          std::multimap<unsigned, unsigned>::iterator OI = I;
 
735
          ++I;
 
736
          copy_set.erase(OI);
 
737
          
 
738
          break;
 
739
        } else {
 
740
          ++I;
 
741
        }
 
742
    }
 
743
    
 
744
    if (!copy_set.empty()) {
 
745
      std::multimap<unsigned, unsigned>::iterator CI = copy_set.begin();
 
746
      std::pair<unsigned, unsigned> curr = *CI;
 
747
      worklist.insert(curr);
 
748
      copy_set.erase(CI);
 
749
      
 
750
      LiveInterval& I = LI.getInterval(curr.second);
 
751
      MachineBasicBlock::iterator term = MBB->getFirstTerminator();
 
752
      SlotIndex endIdx = SlotIndex();
 
753
      if (term != MBB->end())
 
754
        endIdx = LI.getInstructionIndex(term);
 
755
      else
 
756
        endIdx = LI.getMBBEndIdx(MBB);
 
757
      
 
758
      if (I.liveAt(endIdx)) {
 
759
        const TargetRegisterClass *RC =
 
760
                                       MF->getRegInfo().getRegClass(curr.first);
 
761
        
 
762
        // Insert a copy from dest to a new temporary t at the end of b
 
763
        unsigned t = MF->getRegInfo().createVirtualRegister(RC);
 
764
        TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), t,
 
765
                          curr.second, RC, RC);
 
766
        map[curr.second] = t;
 
767
        
 
768
        MachineBasicBlock::iterator TI = MBB->getFirstTerminator();
 
769
        InsertedPHIDests.push_back(std::make_pair(t, --TI));
 
770
      }
 
771
    }
 
772
  }
 
773
  
 
774
  // Renumber the instructions so that we can perform the index computations
 
775
  // needed to create new live intervals.
 
776
  LI.renumber();
 
777
  
 
778
  // For copies that we inserted at the ends of predecessors, we construct
 
779
  // live intervals.  This is pretty easy, since we know that the destination
 
780
  // register cannot have be in live at that point previously.  We just have
 
781
  // to make sure that, for registers that serve as inputs to more than one
 
782
  // PHI, we don't create multiple overlapping live intervals.
 
783
  std::set<unsigned> RegHandled;
 
784
  for (SmallVector<std::pair<unsigned, MachineInstr*>, 4>::iterator I =
 
785
       InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I) {
 
786
    if (RegHandled.insert(I->first).second) {
 
787
      LiveInterval& Int = LI.getOrCreateInterval(I->first);
 
788
      SlotIndex instrIdx = LI.getInstructionIndex(I->second);
 
789
      if (Int.liveAt(instrIdx.getDefIndex()))
 
790
        Int.removeRange(instrIdx.getDefIndex(),
 
791
                        LI.getMBBEndIdx(I->second->getParent()).getNextSlot(),
 
792
                        true);
 
793
      
 
794
      LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second);
 
795
      R.valno->setCopy(I->second);
 
796
      R.valno->def = LI.getInstructionIndex(I->second).getDefIndex();
 
797
    }
 
798
  }
 
799
}
 
800
 
 
801
/// InsertCopies - insert copies into MBB and all of its successors
 
802
void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN,
 
803
                                 SmallPtrSet<MachineBasicBlock*, 16>& visited) {
 
804
  MachineBasicBlock* MBB = MDTN->getBlock();
 
805
  visited.insert(MBB);
 
806
  
 
807
  std::set<unsigned> pushed;
 
808
  
 
809
  LiveIntervals& LI = getAnalysis<LiveIntervals>();
 
810
  // Rewrite register uses from Stacks
 
811
  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 
812
      I != E; ++I) {
 
813
    if (I->isPHI())
 
814
      continue;
 
815
    
 
816
    for (unsigned i = 0; i < I->getNumOperands(); ++i)
 
817
      if (I->getOperand(i).isReg() &&
 
818
          Stacks[I->getOperand(i).getReg()].size()) {
 
819
        // Remove the live range for the old vreg.
 
820
        LiveInterval& OldInt = LI.getInterval(I->getOperand(i).getReg());
 
821
        LiveInterval::iterator OldLR =
 
822
          OldInt.FindLiveRangeContaining(LI.getInstructionIndex(I).getUseIndex());
 
823
        if (OldLR != OldInt.end())
 
824
          OldInt.removeRange(*OldLR, true);
 
825
        
 
826
        // Change the register
 
827
        I->getOperand(i).setReg(Stacks[I->getOperand(i).getReg()].back());
 
828
        
 
829
        // Add a live range for the new vreg
 
830
        LiveInterval& Int = LI.getInterval(I->getOperand(i).getReg());
 
831
        VNInfo* FirstVN = *Int.vni_begin();
 
832
        FirstVN->setHasPHIKill(false);
 
833
        if (I->getOperand(i).isKill())
 
834
          FirstVN->addKill(LI.getInstructionIndex(I).getUseIndex());
 
835
        
 
836
        LiveRange LR (LI.getMBBStartIdx(I->getParent()),
 
837
                      LI.getInstructionIndex(I).getUseIndex().getNextSlot(),
 
838
                      FirstVN);
 
839
        
 
840
        Int.addRange(LR);
 
841
      }
 
842
  }    
 
843
  
 
844
  // Schedule the copies for this block
 
845
  ScheduleCopies(MBB, pushed);
 
846
  
 
847
  // Recur down the dominator tree.
 
848
  for (MachineDomTreeNode::iterator I = MDTN->begin(),
 
849
       E = MDTN->end(); I != E; ++I)
 
850
    if (!visited.count((*I)->getBlock()))
 
851
      InsertCopies(*I, visited);
 
852
  
 
853
  // As we exit this block, pop the names we pushed while processing it
 
854
  for (std::set<unsigned>::iterator I = pushed.begin(), 
 
855
       E = pushed.end(); I != E; ++I)
 
856
    Stacks[*I].pop_back();
 
857
}
 
858
 
 
859
bool StrongPHIElimination::mergeLiveIntervals(unsigned primary,
 
860
                                              unsigned secondary) {
 
861
  
 
862
  LiveIntervals& LI = getAnalysis<LiveIntervals>();
 
863
  LiveInterval& LHS = LI.getOrCreateInterval(primary);
 
864
  LiveInterval& RHS = LI.getOrCreateInterval(secondary);
 
865
  
 
866
  LI.renumber();
 
867
  
 
868
  DenseMap<VNInfo*, VNInfo*> VNMap;
 
869
  for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
 
870
    LiveRange R = *I;
 
871
 
 
872
    SlotIndex Start = R.start;
 
873
    SlotIndex End = R.end;
 
874
    if (LHS.getLiveRangeContaining(Start))
 
875
      return false;
 
876
    
 
877
    if (LHS.getLiveRangeContaining(End))
 
878
      return false;
 
879
    
 
880
    LiveInterval::iterator RI = std::upper_bound(LHS.begin(), LHS.end(), R);
 
881
    if (RI != LHS.end() && RI->start < End)
 
882
      return false;
 
883
  }
 
884
  
 
885
  for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
 
886
    LiveRange R = *I;
 
887
    VNInfo* OldVN = R.valno;
 
888
    VNInfo*& NewVN = VNMap[OldVN];
 
889
    if (!NewVN) {
 
890
      NewVN = LHS.createValueCopy(OldVN, LI.getVNInfoAllocator());
 
891
    }
 
892
    
 
893
    LiveRange LR (R.start, R.end, NewVN);
 
894
    LHS.addRange(LR);
 
895
  }
 
896
  
 
897
  LI.removeInterval(RHS.reg);
 
898
  
 
899
  return true;
 
900
}
 
901
 
 
902
bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
 
903
  LiveIntervals& LI = getAnalysis<LiveIntervals>();
 
904
  
 
905
  // Compute DFS numbers of each block
 
906
  computeDFS(Fn);
 
907
  
 
908
  // Determine which phi node operands need copies
 
909
  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 
910
    if (!I->empty() && I->begin()->isPHI())
 
911
      processBlock(I);
 
912
  
 
913
  // Break interferences where two different phis want to coalesce
 
914
  // in the same register.
 
915
  std::set<unsigned> seen;
 
916
  typedef std::map<unsigned, std::map<unsigned, MachineBasicBlock*> >
 
917
          RenameSetType;
 
918
  for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end();
 
919
       I != E; ++I) {
 
920
    for (std::map<unsigned, MachineBasicBlock*>::iterator
 
921
         OI = I->second.begin(), OE = I->second.end(); OI != OE; ) {
 
922
      if (!seen.count(OI->first)) {
 
923
        seen.insert(OI->first);
 
924
        ++OI;
 
925
      } else {
 
926
        Waiting[OI->second].insert(std::make_pair(OI->first, I->first));
 
927
        unsigned reg = OI->first;
 
928
        ++OI;
 
929
        I->second.erase(reg);
 
930
        DEBUG(dbgs() << "Removing Renaming: " << reg << " -> " << I->first
 
931
                     << "\n");
 
932
      }
 
933
    }
 
934
  }
 
935
  
 
936
  // Insert copies
 
937
  // FIXME: This process should probably preserve LiveIntervals
 
938
  SmallPtrSet<MachineBasicBlock*, 16> visited;
 
939
  MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
 
940
  InsertCopies(MDT.getRootNode(), visited);
 
941
  
 
942
  // Perform renaming
 
943
  for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end();
 
944
       I != E; ++I)
 
945
    while (I->second.size()) {
 
946
      std::map<unsigned, MachineBasicBlock*>::iterator SI = I->second.begin();
 
947
      
 
948
      DEBUG(dbgs() << "Renaming: " << SI->first << " -> " << I->first << "\n");
 
949
      
 
950
      if (SI->first != I->first) {
 
951
        if (mergeLiveIntervals(I->first, SI->first)) {
 
952
          Fn.getRegInfo().replaceRegWith(SI->first, I->first);
 
953
      
 
954
          if (RenameSets.count(SI->first)) {
 
955
            I->second.insert(RenameSets[SI->first].begin(),
 
956
                             RenameSets[SI->first].end());
 
957
            RenameSets.erase(SI->first);
 
958
          }
 
959
        } else {
 
960
          // Insert a last-minute copy if a conflict was detected.
 
961
          const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo();
 
962
          const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(I->first);
 
963
          TII->copyRegToReg(*SI->second, SI->second->getFirstTerminator(),
 
964
                            I->first, SI->first, RC, RC);
 
965
          
 
966
          LI.renumber();
 
967
          
 
968
          LiveInterval& Int = LI.getOrCreateInterval(I->first);
 
969
          SlotIndex instrIdx =
 
970
                     LI.getInstructionIndex(--SI->second->getFirstTerminator());
 
971
          if (Int.liveAt(instrIdx.getDefIndex()))
 
972
            Int.removeRange(instrIdx.getDefIndex(),
 
973
                            LI.getMBBEndIdx(SI->second).getNextSlot(), true);
 
974
 
 
975
          LiveRange R = LI.addLiveRangeToEndOfBlock(I->first,
 
976
                                            --SI->second->getFirstTerminator());
 
977
          R.valno->setCopy(--SI->second->getFirstTerminator());
 
978
          R.valno->def = instrIdx.getDefIndex();
 
979
          
 
980
          DEBUG(dbgs() << "Renaming failed: " << SI->first << " -> "
 
981
                       << I->first << "\n");
 
982
        }
 
983
      }
 
984
      
 
985
      LiveInterval& Int = LI.getOrCreateInterval(I->first);
 
986
      const LiveRange* LR =
 
987
                       Int.getLiveRangeContaining(LI.getMBBEndIdx(SI->second));
 
988
      LR->valno->setHasPHIKill(true);
 
989
      
 
990
      I->second.erase(SI->first);
 
991
    }
 
992
  
 
993
  // Remove PHIs
 
994
  std::vector<MachineInstr*> phis;
 
995
  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
 
996
    for (MachineBasicBlock::iterator BI = I->begin(), BE = I->end();
 
997
         BI != BE; ++BI)
 
998
      if (BI->isPHI())
 
999
        phis.push_back(BI);
 
1000
  }
 
1001
  
 
1002
  for (std::vector<MachineInstr*>::iterator I = phis.begin(), E = phis.end();
 
1003
       I != E; ) {
 
1004
    MachineInstr* PInstr = *(I++);
 
1005
    
 
1006
    // If this is a dead PHI node, then remove it from LiveIntervals.
 
1007
    unsigned DestReg = PInstr->getOperand(0).getReg();
 
1008
    LiveInterval& PI = LI.getInterval(DestReg);
 
1009
    if (PInstr->registerDefIsDead(DestReg)) {
 
1010
      if (PI.containsOneValue()) {
 
1011
        LI.removeInterval(DestReg);
 
1012
      } else {
 
1013
        SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
 
1014
        PI.removeRange(*PI.getLiveRangeContaining(idx), true);
 
1015
      }
 
1016
    } else {
 
1017
      // Trim live intervals of input registers.  They are no longer live into
 
1018
      // this block if they died after the PHI.  If they lived after it, don't
 
1019
      // trim them because they might have other legitimate uses.
 
1020
      for (unsigned i = 1; i < PInstr->getNumOperands(); i += 2) {
 
1021
        unsigned reg = PInstr->getOperand(i).getReg();
 
1022
        
 
1023
        MachineBasicBlock* MBB = PInstr->getOperand(i+1).getMBB();
 
1024
        LiveInterval& InputI = LI.getInterval(reg);
 
1025
        if (MBB != PInstr->getParent() &&
 
1026
            InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())) &&
 
1027
            InputI.expiredAt(LI.getInstructionIndex(PInstr).getNextIndex()))
 
1028
          InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()),
 
1029
                             LI.getInstructionIndex(PInstr),
 
1030
                             true);
 
1031
      }
 
1032
      
 
1033
      // If the PHI is not dead, then the valno defined by the PHI
 
1034
      // now has an unknown def.
 
1035
      SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
 
1036
      const LiveRange* PLR = PI.getLiveRangeContaining(idx);
 
1037
      PLR->valno->setIsPHIDef(true);
 
1038
      LiveRange R (LI.getMBBStartIdx(PInstr->getParent()),
 
1039
                   PLR->start, PLR->valno);
 
1040
      PI.addRange(R);
 
1041
    }
 
1042
    
 
1043
    LI.RemoveMachineInstrFromMaps(PInstr);
 
1044
    PInstr->eraseFromParent();
 
1045
  }
 
1046
  
 
1047
  LI.renumber();
 
1048
  
 
1049
  return true;
 
1050
}