Reuse lowered phi nodes.

Tail duplication produces lots of identical phi nodes in different basic
blocks. Teach PHIElimination to reuse the join registers when lowering a phi
node that is identical to an already lowered node. This saves virtual
registers, and more importantly it avoids creating copies the the coalescer
doesn't know how to eliminate.

Teach LiveIntervalAnalysis about the phi joins with multiple uses.

This patch significantly reduces code size produced by -pre-regalloc-taildup.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91549 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 13 insertions, 4 deletions

diff --git a/lib/CodeGen/PHIElimination.h b/lib/CodeGen/PHIElimination.h
index b0b71ce2bc..1bcc9dc7d9 100644
--- a/lib/CodeGen/PHIElimination.h
+++ b/lib/CodeGen/PHIElimination.h
@@ -16,8 +16,6 @@
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/Target/TargetInstrInfo.h"
 
-#include <map>
-
 namespace llvm {
 
   /// Lower PHI instructions to copies.  
@@ -120,8 +118,8 @@ namespace llvm {
       return I;
     }
 
-    typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair;
-    typedef std::map<BBVRegPair, unsigned> VRegPHIUse;
+    typedef std::pair<unsigned, unsigned> BBVRegPair;
+    typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse;
 
     VRegPHIUse VRegPHIUseCount;
     PHIDefMap PHIDefs;
@@ -129,6 +127,17 @@ namespace llvm {
 
     // Defs of PHI sources which are implicit_def.
     SmallPtrSet<MachineInstr*, 4> ImpDefs;
+
+    // Lowered PHI nodes may be reused. We provide special DenseMap traits to
+    // match PHI nodes with identical arguments.
+    struct PHINodeTraits : public DenseMapInfo<MachineInstr*> {
+      static unsigned getHashValue(const MachineInstr *PtrVal);
+      static bool isEqual(const MachineInstr *LHS, const MachineInstr *RHS);
+    };
+
+    // Map reusable lowered PHI node -> incoming join register.
+    typedef DenseMap<MachineInstr*, unsigned, PHINodeTraits> LoweredPHIMap;
+    LoweredPHIMap LoweredPHIs;
   };
 
 }