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/CodeGen/RegAllocRegistry.h"
25#include "llvm/Function.h"
26#include "llvm/Target/TargetMachine.h"
27#include "llvm/ADT/SmallPtrSet.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Compiler.h"
32#include "llvm/Support/Debug.h"
33#include <algorithm>
34#include <map>
35using namespace llvm;
36
37STATISTIC(NumAtomic, "Number of atomic phis lowered");
38STATISTIC(NumSplits, "Number of critical edges split on demand");
39
40static cl::opt<bool>
41SplitEdges("split-phi-edges",
42 cl::desc("Split critical edges during phi elimination"),
43 cl::init(false), cl::Hidden);
44
45char PHIElimination::ID = 0;
46static RegisterPass<PHIElimination>
47X("phi-node-elimination", "Eliminate PHI nodes for register allocation");
48
49const PassInfo *const llvm::PHIEliminationID = &X;
50
51namespace llvm { FunctionPass *createLocalRegisterAllocator(); }
52
53// Should we run edge splitting?
54static bool shouldSplitEdges() {
55 // Edge splitting breaks the local register allocator. It cannot tolerate
56 // LiveVariables being run.
57 if (RegisterRegAlloc::getDefault() == createLocalRegisterAllocator)
58 return false;
59 return SplitEdges;
60}
61
62void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
63 AU.addPreserved<LiveVariables>();
64 AU.addPreserved<MachineDominatorTree>();
65 if (shouldSplitEdges()) {
66 AU.addRequired<LiveVariables>();
67 } else {
68 AU.setPreservesCFG();
69 AU.addPreservedID(MachineLoopInfoID);
70 }
71 MachineFunctionPass::getAnalysisUsage(AU);
72}
73
74bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) {
75 MRI = &Fn.getRegInfo();
76
77 PHIDefs.clear();
78 PHIKills.clear();
79 bool Changed = false;
80
81 // Split critical edges to help the coalescer
82 if (shouldSplitEdges())
83 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
84 Changed |= SplitPHIEdges(Fn, *I);
85
86 // Populate VRegPHIUseCount
87 analyzePHINodes(Fn);
88
89 // Eliminate PHI instructions by inserting copies into predecessor blocks.
90 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
91 Changed |= EliminatePHINodes(Fn, *I);
92
--- 263 unchanged lines hidden (view full) ---
356 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
357 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
358 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
359 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(),
360 BBI->getOperand(i).getReg())];
361}
362
363bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
364 MachineBasicBlock &MBB) {
365 if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
366 return false; // Quick exit for basic blocks without PHIs.
367 LiveVariables &LV = getAnalysis<LiveVariables>();
368 for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
369 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
370 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
371 unsigned Reg = BBI->getOperand(i).getReg();
372 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
373 // We break edges when registers are live out from the predecessor block
374 // (not considering PHI nodes). If the register is live in to this block
375 // 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/CodeGen/RegAllocRegistry.h"
25#include "llvm/Function.h"
26#include "llvm/Target/TargetMachine.h"
27#include "llvm/ADT/SmallPtrSet.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Compiler.h"
32#include "llvm/Support/Debug.h"
33#include <algorithm>
34#include <map>
35using namespace llvm;
36
37STATISTIC(NumAtomic, "Number of atomic phis lowered");
38STATISTIC(NumSplits, "Number of critical edges split on demand");
39
40static cl::opt<bool>
41SplitEdges("split-phi-edges",
42 cl::desc("Split critical edges during phi elimination"),
43 cl::init(false), cl::Hidden);
44
45char PHIElimination::ID = 0;
46static RegisterPass<PHIElimination>
47X("phi-node-elimination", "Eliminate PHI nodes for register allocation");
48
49const PassInfo *const llvm::PHIEliminationID = &X;
50
51namespace llvm { FunctionPass *createLocalRegisterAllocator(); }
52
53// Should we run edge splitting?
54static bool shouldSplitEdges() {
55 // Edge splitting breaks the local register allocator. It cannot tolerate
56 // LiveVariables being run.
57 if (RegisterRegAlloc::getDefault() == createLocalRegisterAllocator)
58 return false;
59 return SplitEdges;
60}
61
62void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
63 AU.addPreserved<LiveVariables>();
64 AU.addPreserved<MachineDominatorTree>();
65 if (shouldSplitEdges()) {
66 AU.addRequired<LiveVariables>();
67 } else {
68 AU.setPreservesCFG();
69 AU.addPreservedID(MachineLoopInfoID);
70 }
71 MachineFunctionPass::getAnalysisUsage(AU);
72}
73
74bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) {
75 MRI = &Fn.getRegInfo();
76
77 PHIDefs.clear();
78 PHIKills.clear();
79 bool Changed = false;
80
81 // Split critical edges to help the coalescer
82 if (shouldSplitEdges())
83 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
84 Changed |= SplitPHIEdges(Fn, *I);
85
86 // Populate VRegPHIUseCount
87 analyzePHINodes(Fn);
88
89 // Eliminate PHI instructions by inserting copies into predecessor blocks.
90 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
91 Changed |= EliminatePHINodes(Fn, *I);
92
--- 263 unchanged lines hidden (view full) ---
356 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
357 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
358 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
359 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(),
360 BBI->getOperand(i).getReg())];
361}
362
363bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
364 MachineBasicBlock &MBB) {
365 if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
366 return false; // Quick exit for basic blocks without PHIs.
367 LiveVariables &LV = getAnalysis<LiveVariables>();
368 for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
369 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
370 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
371 unsigned Reg = BBI->getOperand(i).getReg();
372 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
373 // We break edges when registers are live out from the predecessor block
374 // (not considering PHI nodes). If the register is live in to this block
375 // anyway, we would gain nothing from splitting.
--- 117 unchanged lines hidden ---