From c962841f40d731bd67b143468504c39748792923 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Kim=20Nguy=E1=BB=85n?= <kn@lri.fr>
Date: Thu, 1 Mar 2012 14:23:00 +0100
Subject: [PATCH] Enable gcc's link time optimization Enable use of ASM
 popcount instruction if present.

---
 src/Makefile                       | 10 ++++++-
 src/static_bitsequence/sdarray.cpp | 46 +++++++++++++++---------------
 2 files changed, 32 insertions(+), 24 deletions(-)

diff --git a/src/Makefile b/src/Makefile
index aaec1e9..033d2db 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -1,6 +1,14 @@
 CPP=g++
+POPCOUNT=$(shell grep -q popcnt /proc/cpuinfo && echo 1)
 
-CPPFLAGS=-O3 -Wall -DNDEBUG -fno-PIC
+ifeq ($(POPCOUNT), 1)
+	POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT
+else
+#POPCOUNT_FLAG=-DHAS_POPCOUNT_TABLE
+	POPCOUNT_FLAG=
+endif
+
+CPPFLAGS=-O3 -Wall -DNDEBUG -fno-PIC $(POPCOUNT_FLAG) -flto
 
 INCL=-I../includes/
 
diff --git a/src/static_bitsequence/sdarray.cpp b/src/static_bitsequence/sdarray.cpp
index a84680f..0d43d81 100644
--- a/src/static_bitsequence/sdarray.cpp
+++ b/src/static_bitsequence/sdarray.cpp
@@ -140,6 +140,26 @@ uint __getbits(uint *B, int i, int d) {
 }
 #endif
 
+
+
+#ifdef HAS_NATIVE_POPCOUNT
+static inline unsigned int popcount(unsigned int n){
+  asm ("popcnt %1, %0" : "=r" (n) : "0" (n));
+  return n;
+}
+
+static inline unsigned int popcount8(unsigned int n) {
+  return popcount(n & 0xff);
+}
+
+static inline unsigned int _fast_popcount(int x)
+{
+  return popcount8(x);
+}
+
+
+#else
+
 static const unsigned int _popCount[] = {
   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
@@ -158,34 +178,14 @@ static const unsigned int _popCount[] = {
   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
   4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
 };
-static inline unsigned int
-_fast_popcount2(int x)
-{
-    uint m1 = 0x55555555;
-    uint m2 = 0x33333333;
-    uint m4 = 0x0f0f0f0f;
-    x -= (x >> 1) & m1;
-    x = (x & m2) + ((x >> 2) & m2);
-    x = (x + (x >> 4)) & m4;
-    x += x >>  8;
-    return (x + (x >> 16)) & 0x3f;
-}
-
-static inline unsigned int
-_fast_popcount3(int x) 
-{
-  uint m1 = 0x55555555;
-  uint m2 = 0xc30c30c3;
-  x -= (x >> 1) & m1;
-  x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);
-  x += x >> 6;
-  return  (x + (x >> 12) + (x >> 24)) & 0x3f;
-}
 
 static inline unsigned int
 _fast_popcount(int x) {
   return _popCount[x];
 }
+#endif
+
+
 
 static unsigned int __selecttbl[8*256];
 static int built = 0;
-- 
2.17.1