1//===-- PhiElimination.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//===----------------------------------------------------------------------===//
--- 7 unchanged lines hidden (view full) ---
16#define DEBUG_TYPE "phielim"
17#include "PHIElimination.h"
18#include "llvm/CodeGen/LiveVariables.h"
19#include "llvm/CodeGen/Passes.h"
20#include "llvm/CodeGen/MachineDominators.h"
21#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/Function.h"
25#include "llvm/Target/TargetMachine.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/STLExtras.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/Support/CommandLine.h"
30#include "llvm/Support/Compiler.h"
31#include "llvm/Support/Debug.h"
32#include <algorithm>
33#include <map>
34using namespace llvm;
35
36STATISTIC(NumAtomic, "Number of atomic phis lowered");
37STATISTIC(NumSplits, "Number of critical edges split on demand");
38
39char PHIElimination::ID = 0;
40static RegisterPass<PHIElimination>
41X("phi-node-elimination", "Eliminate PHI nodes for register allocation");
42
43const PassInfo *const llvm::PHIEliminationID = &X;
44
45void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
46 AU.addPreserved<LiveVariables>();
47 AU.addPreserved<MachineDominatorTree>();
48 // rdar://7401784 This would be nice:
49 // AU.addPreservedID(MachineLoopInfoID);
50 MachineFunctionPass::getAnalysisUsage(AU);
51}
52
53bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) {
54 MRI = &Fn.getRegInfo();
55
56 PHIDefs.clear();
57 PHIKills.clear();
58 bool Changed = false;
59
60 // Split critical edges to help the coalescer
61 if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>())
62 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
63 Changed |= SplitPHIEdges(Fn, *I, *LV);
64
65 // Populate VRegPHIUseCount
66 analyzePHINodes(Fn);
67
68 // Eliminate PHI instructions by inserting copies into predecessor blocks.
69 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
70 Changed |= EliminatePHINodes(Fn, *I);
71
--- 263 unchanged lines hidden (view full) ---
335 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
336 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
337 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
338 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(),
339 BBI->getOperand(i).getReg())];
340}
341
342bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
343 MachineBasicBlock &MBB,
344 LiveVariables &LV) {
345 if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
346 return false; // Quick exit for basic blocks without PHIs.
347
348 for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
349 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
350 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
351 unsigned Reg = BBI->getOperand(i).getReg();
352 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
353 // We break edges when registers are live out from the predecessor block
354 // (not considering PHI nodes). If the register is live in to this block
355 // anyway, we would gain nothing from splitting.
--- 117 unchanged lines hidden ---
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//===----------------------------------------------------------------------===//
--- 7 unchanged lines hidden (view full) ---
16#define DEBUG_TYPE "phielim"
17#include "PHIElimination.h"
18#include "llvm/CodeGen/LiveVariables.h"
19#include "llvm/CodeGen/Passes.h"
20#include "llvm/CodeGen/MachineDominators.h"
21#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/Function.h"
25#include "llvm/Target/TargetMachine.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/STLExtras.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/Support/CommandLine.h"
30#include "llvm/Support/Compiler.h"
31#include "llvm/Support/Debug.h"
32#include <algorithm>
33#include <map>
34using namespace llvm;
35
36STATISTIC(NumAtomic, "Number of atomic phis lowered");
37STATISTIC(NumSplits, "Number of critical edges split on demand");
38
39char PHIElimination::ID = 0;
40static RegisterPass<PHIElimination>
41X("phi-node-elimination", "Eliminate PHI nodes for register allocation");
42
43const PassInfo *const llvm::PHIEliminationID = &X;
44
45void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
46 AU.addPreserved<LiveVariables>();
47 AU.addPreserved<MachineDominatorTree>();
48 // rdar://7401784 This would be nice:
49 // AU.addPreservedID(MachineLoopInfoID);
50 MachineFunctionPass::getAnalysisUsage(AU);
51}
52
53bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) {
54 MRI = &Fn.getRegInfo();
55
56 PHIDefs.clear();
57 PHIKills.clear();
58 bool Changed = false;
59
60 // Split critical edges to help the coalescer
61 if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>())
62 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
63 Changed |= SplitPHIEdges(Fn, *I, *LV);
64
65 // Populate VRegPHIUseCount
66 analyzePHINodes(Fn);
67
68 // Eliminate PHI instructions by inserting copies into predecessor blocks.
69 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
70 Changed |= EliminatePHINodes(Fn, *I);
71
--- 263 unchanged lines hidden (view full) ---
335 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
336 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
337 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
338 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(),
339 BBI->getOperand(i).getReg())];
340}
341
342bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
343 MachineBasicBlock &MBB,
344 LiveVariables &LV) {
345 if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
346 return false; // Quick exit for basic blocks without PHIs.
347
348 for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
349 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
350 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
351 unsigned Reg = BBI->getOperand(i).getReg();
352 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
353 // We break edges when registers are live out from the predecessor block
354 // (not considering PHI nodes). If the register is live in to this block
355 // anyway, we would gain nothing from splitting.
--- 117 unchanged lines hidden ---