1 //===- StrongPhiElimination.cpp - Eliminate PHI nodes by inserting copies -===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Owen Anderson and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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:
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
20 //===----------------------------------------------------------------------===//
22 #define DEBUG_TYPE "strongphielim"
23 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/CodeGen/MachineDominators.h"
25 #include "llvm/CodeGen/MachineFunctionPass.h"
26 #include "llvm/CodeGen/MachineInstr.h"
27 #include "llvm/Target/TargetInstrInfo.h"
28 #include "llvm/Target/TargetMachine.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/Support/Compiler.h"
35 struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass {
36 static char ID; // Pass identification, replacement for typeid
37 StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {}
39 bool runOnMachineFunction(MachineFunction &Fn) {
46 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
47 AU.addRequired<MachineDominatorTree>();
48 MachineFunctionPass::getAnalysisUsage(AU);
51 virtual void releaseMemory() {
57 DenseMap<MachineBasicBlock*, unsigned> preorder;
58 DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
60 void computeDFS(MachineFunction& MF);
63 char StrongPHIElimination::ID = 0;
64 RegisterPass<StrongPHIElimination> X("strong-phi-node-elimination",
65 "Eliminate PHI nodes for register allocation, intelligently");
68 const PassInfo *llvm::StrongPHIEliminationID = X.getPassInfo();
70 /// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree
71 /// of the given MachineFunction. These numbers are then used in other parts
72 /// of the PHI elimination process.
73 void StrongPHIElimination::computeDFS(MachineFunction& MF) {
74 SmallPtrSet<MachineDomTreeNode*, 8> frontier;
75 SmallPtrSet<MachineDomTreeNode*, 8> visited;
79 MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>();
81 MachineDomTreeNode* node = DT.getRootNode();
83 std::vector<MachineDomTreeNode*> worklist;
84 worklist.push_back(node);
86 while (!worklist.empty()) {
87 MachineDomTreeNode* currNode = worklist.back();
89 if (!frontier.count(currNode)) {
90 frontier.insert(currNode);
92 preorder.insert(std::make_pair(currNode->getBlock(), time));
95 bool inserted = false;
96 for (MachineDomTreeNode::iterator I = node->begin(), E = node->end();
98 if (!frontier.count(*I) && !visited.count(*I)) {
99 worklist.push_back(*I);
105 frontier.erase(currNode);
106 visited.insert(currNode);
107 maxpreorder.insert(std::make_pair(currNode->getBlock(), time));