Author: resistor
Date: Tue Oct 30 22:37:57 2007
New Revision: 43542
URL: http://llvm.org/viewvc/llvm-project?rev=43542&view=rev
Log:
Add the skeleton of a better PHI elimination pass.
Added:
llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp
Modified:
llvm/trunk/include/llvm/CodeGen/Passes.h
Modified: llvm/trunk/include/llvm/CodeGen/Passes.h
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/CodeGen/Passes.h?rev=43542&r1=43541&r2=43542&view=diff
==============================================================================
--- llvm/trunk/include/llvm/CodeGen/Passes.h (original)
+++ llvm/trunk/include/llvm/CodeGen/Passes.h Tue Oct 30 22:37:57 2007
@@ -44,6 +44,14 @@
/// these register allocator like this: AU.addRequiredID(PHIEliminationID);
///
extern const PassInfo *PHIEliminationID;
+
+ /// StrongPHIElimination pass - This pass eliminates machine instruction PHI
+ /// nodes by inserting copy instructions. This destroys SSA information, but
+ /// is the desired input for some register allocators. This pass is
+ /// "required" by these register allocator like this:
+ /// AU.addRequiredID(PHIEliminationID);
+ /// This pass is still in development
+ extern const PassInfo *StrongPHIEliminationID;
/// SimpleRegisterCoalescing pass. Aggressively coalesces every register
/// copy it can.
Added: llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp?rev=43542&view=auto
==============================================================================
--- llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp (added)
+++ llvm/trunk/lib/CodeGen/StrongPHIElimination.cpp Tue Oct 30 22:37:57 2007
@@ -0,0 +1,112 @@
+//===- StrongPhiElimination.cpp - Eliminate PHI nodes by inserting copies
-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Owen Anderson and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass eliminates machine instruction PHI nodes by inserting copy
+// instructions, using an intelligent copy-folding technique based on
+// dominator information. This is technique is derived from:
+//
+// Budimlic, et al. Fast copy coalescing and live-range identification.
+// In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language
+// Design and Implementation (Berlin, Germany, June 17 - 19, 2002).
+// PLDI '02. ACM, New York, NY, 25-32.
+// DOI= http://doi.acm.org/10.1145/512529.512534
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "strongphielim"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Support/Compiler.h"
+using namespace llvm;
+
+
+namespace {
+ struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass {
+ static char ID; // Pass identification, replacement for typeid
+ StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {}
+
+ bool runOnMachineFunction(MachineFunction &Fn) {
+ computeDFS(Fn);
+
+
+ return false;
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<MachineDominatorTree>();
+ MachineFunctionPass::getAnalysisUsage(AU);
+ }
+
+ virtual void releaseMemory() {
+ preorder.clear();
+ maxpreorder.clear();
+ }
+
+ private:
+ DenseMap<MachineBasicBlock*, unsigned> preorder;
+ DenseMap<MachineBasicBlock*, unsigned> maxpreorder;
+
+ void computeDFS(MachineFunction& MF);
+ };
+
+ char StrongPHIElimination::ID = 0;
+ RegisterPass<StrongPHIElimination> X("strong-phi-node-elimination",
+ "Eliminate PHI nodes for register allocation,
intelligently");
+}
+
+const PassInfo *llvm::StrongPHIEliminationID = X.getPassInfo();
+
+/// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree
+/// of the given MachineFunction. These numbers are then used in other parts
+/// of the PHI elimination process.
+void StrongPHIElimination::computeDFS(MachineFunction& MF) {
+ SmallPtrSet<MachineDomTreeNode*, 8> frontier;
+ SmallPtrSet<MachineDomTreeNode*, 8> visited;
+
+ unsigned time = 0;
+
+ MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>();
+
+ MachineDomTreeNode* node = DT.getRootNode();
+
+ std::vector<MachineDomTreeNode*> worklist;
+ worklist.push_back(node);
+
+ while (!worklist.empty()) {
+ MachineDomTreeNode* currNode = worklist.back();
+
+ if (!frontier.count(currNode)) {
+ frontier.insert(currNode);
+ ++time;
+ preorder.insert(std::make_pair(currNode->getBlock(), time));
+ }
+
+ bool inserted = false;
+ for (MachineDomTreeNode::iterator I = node->begin(), E = node->end();
+ I != E; ++I)
+ if (!frontier.count(*I) && !visited.count(*I)) {
+ worklist.push_back(*I);
+ inserted = true;
+ break;
+ }
+
+ if (!inserted) {
+ frontier.erase(currNode);
+ visited.insert(currNode);
+ maxpreorder.insert(std::make_pair(currNode->getBlock(), time));
+
+ worklist.pop_back();
+ }
+ }
+}
\ No newline at end of file
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
