From 81a6995243380668e6f991fa4e11dd0a6e37e030 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Thu, 9 Aug 2012 22:49:46 +0000
Subject: [PATCH] Partition use lists so defs always come before uses.

This makes it possible to speed up def_iterator by stopping at the first
use. This makes def_empty() and getUniqueVRegDef() much faster when
there are many uses.

In a +Asserts build, LiveVariables is 100x faster in one case because
getVRegDef() has an assertion that would scan to the end of a
def_iterator chain.

Spill weight calculation is significantly faster (300x in one case)
because isTriviallyReMaterializable() calls MRI->isConstantPhysReg(%RIP)
which calls def_empty(%RIP).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161634 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/CodeGen/MachineRegisterInfo.h | 19 ++++++++++++++-----
 lib/CodeGen/MachineRegisterInfo.cpp        | 14 +++++++++++---
 test/CodeGen/X86/apm.ll                    |  4 ++--
 test/CodeGen/X86/xor.ll                    |  2 +-
 4 files changed, 28 insertions(+), 11 deletions(-)

diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h
index 68905e3c5e5..42a8aa43d98 100644
--- a/include/llvm/CodeGen/MachineRegisterInfo.h
+++ b/include/llvm/CodeGen/MachineRegisterInfo.h
@@ -513,11 +513,20 @@ public:
       assert(Op && "Cannot increment end iterator!");
       Op = getNextOperandForReg(Op);
 
-      // If this is an operand we don't care about, skip it.
-      while (Op && ((!ReturnUses && Op->isUse()) ||
-                    (!ReturnDefs && Op->isDef()) ||
-                    (SkipDebug && Op->isDebug())))
-        Op = getNextOperandForReg(Op);
+      // All defs come before the uses, so stop def_iterator early.
+      if (!ReturnUses) {
+        if (Op) {
+          if (Op->isUse())
+            Op = 0;
+          else
+            assert(!Op->isDebug() && "Can't have debug defs");
+        }
+      } else {
+        // If this is an operand we don't care about, skip it.
+        while (Op && ((!ReturnDefs && Op->isDef()) ||
+                      (SkipDebug && Op->isDebug())))
+          Op = getNextOperandForReg(Op);
+      }
 
       return *this;
     }
diff --git a/lib/CodeGen/MachineRegisterInfo.cpp b/lib/CodeGen/MachineRegisterInfo.cpp
index bd826fb7c1b..5fb938f3400 100644
--- a/lib/CodeGen/MachineRegisterInfo.cpp
+++ b/lib/CodeGen/MachineRegisterInfo.cpp
@@ -144,9 +144,17 @@ void MachineRegisterInfo::addRegOperandToUseList(MachineOperand *MO) {
   Head->Contents.Reg.Prev = MO;
   MO->Contents.Reg.Prev = Last;
 
-  // Insert at the front.
-  MO->Contents.Reg.Next = Head;
-  HeadRef = MO;
+  // Def operands always precede uses. This allows def_iterator to stop early.
+  // Insert def operands at the front, and use operands at the back.
+  if (MO->isDef()) {
+    // Insert def at the front.
+    MO->Contents.Reg.Next = Head;
+    HeadRef = MO;
+  } else {
+    // Insert use at the end.
+    MO->Contents.Reg.Next = 0;
+    Last->Contents.Reg.Next = MO;
+  }
 }
 
 /// Remove MO from its use-def list.
diff --git a/test/CodeGen/X86/apm.ll b/test/CodeGen/X86/apm.ll
index 9f4b0f46562..aaedf18481b 100644
--- a/test/CodeGen/X86/apm.ll
+++ b/test/CodeGen/X86/apm.ll
@@ -3,8 +3,8 @@
 ; PR8573
 
 ; CHECK: foo:
-; CHECK: movl    %esi, %ecx
-; CHECK-NEXT: leaq    (%rdi), %rax
+; CHECK: leaq    (%rdi), %rax
+; CHECK-NEXT: movl    %esi, %ecx
 ; CHECK-NEXT: monitor
 ; WIN64: foo:
 ; WIN64:      leaq    (%rcx), %rax
diff --git a/test/CodeGen/X86/xor.ll b/test/CodeGen/X86/xor.ll
index 73416eff0e6..996bfc40ee5 100644
--- a/test/CodeGen/X86/xor.ll
+++ b/test/CodeGen/X86/xor.ll
@@ -31,7 +31,7 @@ entry:
 ; X64: test3:
 ; X64:	notl
 ; X64:	andl
-; X64:	shrl	%eax
+; X64:	shrl
 ; X64:	ret
 
 ; X32: test3:
-- 
2.34.1