This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: PATCH: Move sysdeps/x86_64/Implies to sysdeps/x86_64/64
From: "Carlos O'Donell" <carlos@systemhalted.org>
Date: Thu, 22 Mar 2012 19:18:10 -0400
> There have been patches in the past (Jakub?) to reduce the size
> of the generated rules.
And there have been GNU make patches, posted back in 2007 but never
applied, which solve one part of the computational complexity issue.
If people want to shave ~%30 of the make overhead from their builds
feel free to use the make-3.82 based patches attached, I spent last
night forward porting them so that I could use them myself. They
reduce a "do nothing" make on my Niagara-T3 sparc from 10 minutes
down to 6 minutes.
>From c13422b11ad0634eaf72ebbaa3936a86044f686d Mon Sep 17 00:00:00 2001
From: Mark Seaborn <mrs@mythic-beasts.com>
Date: Thu, 22 Mar 2012 00:51:12 -0700
Subject: [PATCH 1/5] Refactor: Move rule comparisons into separate functions.
Signed-off-by: David S. Miller <davem@davemloft.net>
---
rule.c | 95 +++++++++++++++++++++++++++++++++++++---------------------------
1 files changed, 55 insertions(+), 40 deletions(-)
diff --git a/rule.c b/rule.c
index a966cc9..6538887 100644
--- a/rule.c
+++ b/rule.c
@@ -275,6 +275,34 @@ convert_to_pattern (void)
}
+static int
+rule_targets_superset (struct rule *rule1, struct rule *rule2)
+{
+ int i;
+ for (i = 0; i < rule1->num; i++)
+ {
+ int j;
+ for (j = 0; j < rule2->num; j++)
+ if (!streq (rule1->targets[i], rule2->targets[j]))
+ break;
+ if (j == rule2->num)
+ return 1;
+ }
+ return 0;
+}
+
+static int
+rule_dependency_lists_equal (struct rule *rule1, struct rule *rule2)
+{
+ struct dep *dep1, *dep2;
+ for (dep1 = rule1->deps, dep2 = rule2->deps;
+ dep1 != NULL && dep2 != NULL;
+ dep1 = dep1->next, dep2 = dep2->next)
+ if (!streq (dep_name (dep1), dep_name (dep2)))
+ return 0;
+ return dep1 == NULL && dep2 == NULL;
+}
+
/* Install the pattern rule RULE (whose fields have been filled in) at the end
of the list (so that any rules previously defined will take precedence).
If this rule duplicates a previous one (identical target and dependencies),
@@ -286,7 +314,6 @@ static int
new_pattern_rule (struct rule *rule, int override)
{
struct rule *r, *lastrule;
- unsigned int i, j;
rule->in_use = 0;
rule->terminal = 0;
@@ -296,45 +323,33 @@ new_pattern_rule (struct rule *rule, int override)
/* Search for an identical rule. */
lastrule = 0;
for (r = pattern_rules; r != 0; lastrule = r, r = r->next)
- for (i = 0; i < rule->num; ++i)
- {
- for (j = 0; j < r->num; ++j)
- if (!streq (rule->targets[i], r->targets[j]))
- break;
- /* If all the targets matched... */
- if (j == r->num)
- {
- struct dep *d, *d2;
- for (d = rule->deps, d2 = r->deps;
- d != 0 && d2 != 0; d = d->next, d2 = d2->next)
- if (!streq (dep_name (d), dep_name (d2)))
- break;
- if (d == 0 && d2 == 0)
- {
- /* All the dependencies matched. */
- if (override)
- {
- /* Remove the old rule. */
- freerule (r, lastrule);
- /* Install the new one. */
- if (pattern_rules == 0)
- pattern_rules = rule;
- else
- last_pattern_rule->next = rule;
- last_pattern_rule = rule;
-
- /* We got one. Stop looking. */
- goto matched;
- }
- else
- {
- /* The old rule stays intact. Destroy the new one. */
- freerule (rule, (struct rule *) 0);
- return 0;
- }
- }
- }
- }
+ {
+ if (rule_targets_superset (rule, r)
+ && rule_dependency_lists_equal (rule, r))
+ {
+ /* All the dependencies matched. */
+ if (override)
+ {
+ /* Remove the old rule. */
+ freerule (r, lastrule);
+ /* Install the new one. */
+ if (pattern_rules == 0)
+ pattern_rules = rule;
+ else
+ last_pattern_rule->next = rule;
+ last_pattern_rule = rule;
+
+ /* We got one. Stop looking. */
+ goto matched;
+ }
+ else
+ {
+ /* The old rule stays intact. Destroy the new one. */
+ freerule (rule, (struct rule *) 0);
+ return 0;
+ }
+ }
+ }
matched:;
--
1.7.9.1
>From 34b47fcc0274b24ed2f864a05d2b098ed5b537ff Mon Sep 17 00:00:00 2001
From: Mark Seaborn <mrs@mythic-beasts.com>
Date: Thu, 22 Mar 2012 00:53:24 -0700
Subject: [PATCH 2/5] Clean up count_implicit_rule_limits()
* Remove unused variable, simplify loop.
* Corrected comment.
Signed-off-by: David S. Miller <davem@davemloft.net>
---
rule.c | 13 +++----------
1 files changed, 3 insertions(+), 10 deletions(-)
diff --git a/rule.c b/rule.c
index 6538887..f689600 100644
--- a/rule.c
+++ b/rule.c
@@ -64,28 +64,24 @@ unsigned int maxsuffix;
/* Compute the maximum dependency length and maximum number of
dependencies of all implicit rules. Also sets the subdir
- flag for a rule when appropriate, possibly removing the rule
- completely when appropriate. */
+ flag for a rule when appropriate. */
void
count_implicit_rule_limits (void)
{
char *name;
int namelen;
- struct rule *rule, *lastrule;
+ struct rule *rule;
num_pattern_rules = max_pattern_targets = max_pattern_deps = 0;
max_pattern_dep_length = 0;
name = 0;
namelen = 0;
- rule = pattern_rules;
- lastrule = 0;
- while (rule != 0)
+ for (rule = pattern_rules; rule != NULL; rule = rule->next)
{
unsigned int ndeps = 0;
struct dep *dep;
- struct rule *next = rule->next;
++num_pattern_rules;
@@ -139,9 +135,6 @@ count_implicit_rule_limits (void)
if (ndeps > max_pattern_deps)
max_pattern_deps = ndeps;
-
- lastrule = rule;
- rule = next;
}
if (name != 0)
--
1.7.9.1
>From cc49beeb48fcf03f4fc042572c5f6c99606ac8b9 Mon Sep 17 00:00:00 2001
From: Mark Seaborn <mrs@mythic-beasts.com>
Date: Thu, 22 Mar 2012 01:04:00 -0700
Subject: [PATCH 3/5] Refactor: Use a doubly-linked list of rules instead of a
singly-linked list.
Signed-off-by: David S. Miller <davem@davemloft.net>
---
implicit.c | 3 +-
rule.c | 85 ++++++++++++++++++++++++-----------------------------------
rule.h | 4 +-
3 files changed, 39 insertions(+), 53 deletions(-)
diff --git a/implicit.c b/implicit.c
index 5f98108..7d5e03e 100644
--- a/implicit.c
+++ b/implicit.c
@@ -301,7 +301,7 @@ pattern_search (struct file *file, int archive,
Put them in TRYRULES. */
nrules = 0;
- for (rule = pattern_rules; rule != 0; rule = rule->next)
+ for (rule = pattern_rules.next; rule != &pattern_rules; rule = rule->next)
{
unsigned int ti;
@@ -409,6 +409,7 @@ pattern_search (struct file *file, int archive,
++nrules;
}
}
+ rule = NULL;
/* Bail out early if we haven't found any rules. */
if (nrules == 0)
diff --git a/rule.c b/rule.c
index f689600..535bc80 100644
--- a/rule.c
+++ b/rule.c
@@ -27,15 +27,13 @@ this program. If not, see <http://www.gnu.org/licenses/>. */
#include "variable.h"
#include "rule.h"
-static void freerule (struct rule *rule, struct rule *lastrule);
+static void add_rule (struct rule *rule);
+static void remove_rule (struct rule *rule);
+static void free_rule (struct rule *rule);
/* Chain of all pattern rules. */
-struct rule *pattern_rules;
-
-/* Pointer to last rule in the chain, so we can add onto the end. */
-
-struct rule *last_pattern_rule;
+struct rule pattern_rules = { &pattern_rules, &pattern_rules };
/* Number of rules in the chain. */
@@ -78,7 +76,7 @@ count_implicit_rule_limits (void)
name = 0;
namelen = 0;
- for (rule = pattern_rules; rule != NULL; rule = rule->next)
+ for (rule = pattern_rules.next; rule != &pattern_rules; rule = rule->next)
{
unsigned int ndeps = 0;
struct dep *dep;
@@ -136,6 +134,7 @@ count_implicit_rule_limits (void)
if (ndeps > max_pattern_deps)
max_pattern_deps = ndeps;
}
+ rule = NULL;
if (name != 0)
free (name);
@@ -306,16 +305,13 @@ rule_dependency_lists_equal (struct rule *rule1, struct rule *rule2)
static int
new_pattern_rule (struct rule *rule, int override)
{
- struct rule *r, *lastrule;
+ struct rule *r;
rule->in_use = 0;
rule->terminal = 0;
- rule->next = 0;
-
/* Search for an identical rule. */
- lastrule = 0;
- for (r = pattern_rules; r != 0; lastrule = r, r = r->next)
+ for (r = pattern_rules.next; r != &pattern_rules; r = r->next)
{
if (rule_targets_superset (rule, r)
&& rule_dependency_lists_equal (rule, r))
@@ -323,42 +319,45 @@ new_pattern_rule (struct rule *rule, int override)
/* All the dependencies matched. */
if (override)
{
- /* Remove the old rule. */
- freerule (r, lastrule);
- /* Install the new one. */
- if (pattern_rules == 0)
- pattern_rules = rule;
- else
- last_pattern_rule->next = rule;
- last_pattern_rule = rule;
+ remove_rule (r);
+ free_rule (r);
+
+ add_rule (rule);
/* We got one. Stop looking. */
- goto matched;
+ return 1;
}
else
{
/* The old rule stays intact. Destroy the new one. */
- freerule (rule, (struct rule *) 0);
+ free_rule (rule);
return 0;
}
}
}
- matched:;
-
- if (r == 0)
- {
- /* There was no rule to replace. */
- if (pattern_rules == 0)
- pattern_rules = rule;
- else
- last_pattern_rule->next = rule;
- last_pattern_rule = rule;
- }
+ /* There was no rule to replace. */
+ add_rule (rule);
return 1;
}
+static void
+add_rule (struct rule *rule)
+{
+ rule->next = &pattern_rules;
+ rule->prev = pattern_rules.prev;
+ pattern_rules.prev->next = rule;
+ pattern_rules.prev = rule;
+}
+
+static void
+remove_rule (struct rule *rule)
+{
+ rule->prev->next = rule->next;
+ rule->next->prev = rule->prev;
+}
+
/* Install an implicit pattern rule based on the three text strings
in the structure P points to. These strings come from one of
@@ -401,15 +400,11 @@ install_pattern_rule (struct pspec *p, int terminal)
}
-/* Free all the storage used in RULE and take it out of the
- pattern_rules chain. LASTRULE is the rule whose next pointer
- points to RULE. */
+/* Free all the storage used in RULE. */
static void
-freerule (struct rule *rule, struct rule *lastrule)
+free_rule (struct rule *rule)
{
- struct rule *next = rule->next;
-
free_dep_chain (rule->deps);
/* MSVC erroneously warns without a cast here. */
@@ -429,16 +424,6 @@ freerule (struct rule *rule, struct rule *lastrule)
pointer from the `struct file' for the suffix rule. */
free (rule);
-
- if (pattern_rules == rule)
- if (lastrule != 0)
- abort ();
- else
- pattern_rules = next;
- else if (lastrule != 0)
- lastrule->next = next;
- if (last_pattern_rule == rule)
- last_pattern_rule = lastrule;
}
/* Create a new pattern rule with the targets in the nil-terminated array
@@ -507,7 +492,7 @@ print_rule_data_base (void)
puts (_("\n# Implicit Rules"));
rules = terminal = 0;
- for (r = pattern_rules; r != 0; r = r->next)
+ for (r = pattern_rules.next; r != &pattern_rules; r = r->next)
{
++rules;
diff --git a/rule.h b/rule.h
index b119d21..b4bb8e5 100644
--- a/rule.h
+++ b/rule.h
@@ -22,6 +22,7 @@ this program. If not, see <http://www.gnu.org/licenses/>. */
struct rule
{
struct rule *next;
+ struct rule *prev;
const char **targets; /* Targets of the rule. */
unsigned int *lens; /* Lengths of each target. */
const char **suffixes; /* Suffixes (after `%') of each target. */
@@ -39,8 +40,7 @@ struct pspec
};
-extern struct rule *pattern_rules;
-extern struct rule *last_pattern_rule;
+extern struct rule pattern_rules;
extern unsigned int num_pattern_rules;
extern unsigned int max_pattern_deps;
--
1.7.9.1
>From a2f981518b5b70ba313a87968e74593a55987c07 Mon Sep 17 00:00:00 2001
From: Mark Seaborn <mrs@mythic-beasts.com>
Date: Thu, 22 Mar 2012 01:10:25 -0700
Subject: [PATCH 4/5] Record rule targets in a hash table.
This is not used to replace any lookups yet.
Signed-off-by: David S. Miller <davem@davemloft.net>
---
main.c | 1 +
rule.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rule.h | 2 +
3 files changed, 79 insertions(+), 0 deletions(-)
diff --git a/main.c b/main.c
index c6989e3..5ba1dc2 100644
--- a/main.c
+++ b/main.c
@@ -552,6 +552,7 @@ initialize_global_hash_tables (void)
init_hash_files ();
hash_init_directories ();
hash_init_function_table ();
+ rule_init ();
}
static const char *
diff --git a/rule.c b/rule.c
index 535bc80..11ba01e 100644
--- a/rule.c
+++ b/rule.c
@@ -30,11 +30,22 @@ this program. If not, see <http://www.gnu.org/licenses/>. */
static void add_rule (struct rule *rule);
static void remove_rule (struct rule *rule);
static void free_rule (struct rule *rule);
+
+/* List of rules with the same target. */
+struct rule_target_list
+{
+ const char *target;
+ int target_num;
+ struct rule *rule;
+ struct rule_target_list *next;
+};
/* Chain of all pattern rules. */
struct rule pattern_rules = { &pattern_rules, &pattern_rules };
+struct hash_table rules_by_target;
+
/* Number of rules in the chain. */
unsigned int num_pattern_rules;
@@ -60,6 +71,31 @@ struct file *suffix_file;
unsigned int maxsuffix;
+static unsigned long
+rule_hash_1 (const void *key)
+{
+ return_ISTRING_HASH_1 (((struct rule_target_list *) key)->target);
+}
+
+static unsigned long
+rule_hash_2 (const void *key)
+{
+ return_ISTRING_HASH_2 (((struct rule_target_list *) key)->target);
+}
+
+static int
+rule_hash_cmp (const void *x, const void *y)
+{
+ return_ISTRING_COMPARE (((struct rule_target_list *) x)->target,
+ ((struct rule_target_list *) y)->target);
+}
+
+void
+rule_init (void)
+{
+ hash_init (&rules_by_target, 199, rule_hash_1, rule_hash_2, rule_hash_cmp);
+}
+
/* Compute the maximum dependency length and maximum number of
dependencies of all implicit rules. Also sets the subdir
flag for a rule when appropriate. */
@@ -345,6 +381,21 @@ new_pattern_rule (struct rule *rule, int override)
static void
add_rule (struct rule *rule)
{
+ int i;
+
+ /* Add to hash table. */
+ for (i = 0; i < rule->num; i++)
+ {
+ struct rule_target_list *node =
+ (void *) xmalloc (sizeof (struct rule_target_list));
+ node->target = rule->targets[i];
+ node->target_num = i;
+ node->rule = rule;
+ node->next = hash_find_item (&rules_by_target, node);
+ hash_insert (&rules_by_target, node);
+ }
+
+ /* Add to list. */
rule->next = &pattern_rules;
rule->prev = pattern_rules.prev;
pattern_rules.prev->next = rule;
@@ -354,6 +405,31 @@ add_rule (struct rule *rule)
static void
remove_rule (struct rule *rule)
{
+ int i;
+
+ /* Remove from hash table. */
+ for (i = 0; i < rule->num; i++)
+ {
+ struct rule_target_list key, **list;
+ key.target = rule->targets[i];
+ list = (struct rule_target_list **) hash_find_slot (&rules_by_target,
+ &key);
+ while(1)
+ {
+ assert (*list != NULL);
+ if ((*list)->rule == rule &&
+ (*list)->target_num == i)
+ {
+ struct rule_target_list *node = *list;
+ *list = node->next;
+ free (node);
+ break;
+ }
+ list = &(*list)->next;
+ }
+ }
+
+ /* Remove from list. */
rule->prev->next = rule->next;
rule->next->prev = rule->prev;
}
diff --git a/rule.h b/rule.h
index b4bb8e5..f0a1b71 100644
--- a/rule.h
+++ b/rule.h
@@ -57,3 +57,5 @@ void install_pattern_rule (struct pspec *p, int terminal);
void create_pattern_rule (const char **targets, const char **target_percents,
unsigned int num, int terminal, struct dep *deps,
struct commands *commands, int override);
+
+void rule_init (void);
--
1.7.9.1
>From 37f70586e75c2e7ddafeaed79c76b1fb25039f64 Mon Sep 17 00:00:00 2001
From: Mark Seaborn <mrs@mythic-beasts.com>
Date: Thu, 22 Mar 2012 01:14:07 -0700
Subject: [PATCH 5/5] Hook up hash table: use for searching for rules to
replace
Signed-off-by: David S. Miller <davem@davemloft.net>
---
rule.c | 52 ++++++++++++++++++++++++++++------------------------
1 files changed, 28 insertions(+), 24 deletions(-)
diff --git a/rule.c b/rule.c
index 11ba01e..8a4a988 100644
--- a/rule.c
+++ b/rule.c
@@ -341,35 +341,39 @@ rule_dependency_lists_equal (struct rule *rule1, struct rule *rule2)
static int
new_pattern_rule (struct rule *rule, int override)
{
- struct rule *r;
+ int i;
rule->in_use = 0;
rule->terminal = 0;
- /* Search for an identical rule. */
- for (r = pattern_rules.next; r != &pattern_rules; r = r->next)
+ /* Search for an existing rule to replace. */
+ for (i = 0; i < rule->num; i++)
{
- if (rule_targets_superset (rule, r)
- && rule_dependency_lists_equal (rule, r))
- {
- /* All the dependencies matched. */
- if (override)
- {
- remove_rule (r);
- free_rule (r);
-
- add_rule (rule);
-
- /* We got one. Stop looking. */
- return 1;
- }
- else
- {
- /* The old rule stays intact. Destroy the new one. */
- free_rule (rule);
- return 0;
- }
- }
+ struct rule_target_list key, *list;
+ key.target = rule->targets[i];
+ list = hash_find_item (&rules_by_target, &key);
+ for (; list != NULL; list = list->next)
+ {
+ struct rule *old_rule = list->rule;
+ if (rule_targets_superset (rule, old_rule)
+ && rule_dependency_lists_equal (rule, old_rule))
+ {
+ /* All the dependencies matched. */
+ if (override)
+ {
+ remove_rule (old_rule);
+ free_rule (old_rule);
+ add_rule (rule);
+ return 1;
+ }
+ else
+ {
+ /* The old rule stays intact. Destroy the new one. */
+ free_rule (rule);
+ return 0;
+ }
+ }
+ }
}
/* There was no rule to replace. */
--
1.7.9.1