[PATCH v2 next 12/15] kallsyms: scripts/kallsyms: Optimise compress_symbols()

[David Laight <david.laight.linux@gmail.com>]

When (say) axyb is replaced with azb instead of decrementing the
token_profit[] value for every pair of token in the old string before
the substitution and then incrementing it afterwards just decrement
the counts for ax and yb and increment the ones for az and zb.
Set the count for xy (the number of actual substitions) to zero
afterwards.

This pretty much halves the time taken to do the actual compression
which is by far largest part of the entire process.

Output file unchanged.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 74 ++++++++++++++++++----------------------------
 1 file changed, 29 insertions(+), 45 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 9e1bc0fdaa9f..ee06a9c7435f 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -479,13 +479,11 @@ static void learn_symbol(const unsigned char *sym, int len)
 		token_profit[PAIR(sym[i], sym[i + 1])]++;
 }
 
-/* decrease the count for all the possible tokens in a symbol */
-static void forget_symbol(const unsigned char *sym, int len)
+static void adjust_profit(unsigned int old_left, unsigned int new_left,
+			  unsigned int old_right, unsigned int new_right)
 {
-	int i;
-
-	for (i = 0; i < len - 1; i++)
-		token_profit[PAIR(sym[i], sym[i + 1])]--;
+	token_profit[PAIR(old_left, old_right)]--;
+	token_profit[PAIR(new_left, new_right)]++;
 }
 
 /* do the initial token count */
@@ -497,13 +495,12 @@ static void build_initial_token_table(void)
 		learn_symbol(symbol[i]->sym, symbol[i]->len);
 }
 
-static unsigned char *find_token(unsigned char *str, int len,
+static unsigned char *find_token(unsigned char *str, unsigned char *end,
 				 unsigned int want)
 {
 	unsigned int token = PAIR(0, *str++);
-	int i;
 
-	for (i = 0; i < len - 1; i++) {
+	while (str < end) {
 		token = PAIR(RIGHT(token), *str++);
 		if (token == want)
 			return str - 2;
@@ -512,46 +509,33 @@ static unsigned char *find_token(unsigned char *str, int len,
 }
 
 /* replace a given token in all the valid symbols. Use the sampled symbols
- * to update the counts */
-static void compress_symbols(unsigned int token_pair, int idx)
+ * to update the counts.
+ * Marked noinline to help register allocation. compress_symbols() is only called
+ * about 200 times whereas find_token() can be called well over a million times. */
+static __attribute__((noinline)) void compress_symbols(unsigned int token_pair, int idx)
 {
-	unsigned int i, len, size;
-	unsigned char *p1, *p2;
+	unsigned int i, len;
+	unsigned char *sym, *p, *end;
 
 	for (i = 0; i < symbol_cnt; i++) {
-
-		len = symbol[i]->len;
-		p1 = symbol[i]->sym;
-
-		/* find the token on the symbol */
-		p2 = find_token(p1, len, token_pair);
-		if (!p2) continue;
-
-		/* decrease the counts for this symbol's tokens */
-		forget_symbol(symbol[i]->sym, len);
-
-		size = len;
-
-		do {
-			*p2 = idx;
-			p2++;
-			size -= (p2 - p1);
-			memmove(p2, p2 + 1, size);
-			p1 = p2;
-			len--;
-
-			if (size < 2) break;
-
-			/* find the token on the symbol */
-			p2 = find_token(p1, size, token_pair);
-
-		} while (p2);
-
-		symbol[i]->len = len;
-
-		/* increase the counts for this symbol's new tokens */
-		learn_symbol(symbol[i]->sym, len);
+		sym = symbol[i]->sym;
+		end = sym + symbol[i]->len;
+
+		for (p = sym; (p = find_token(p, end, token_pair)); p++) {
+			len = end - p - 2;
+			end--;
+			*p = idx;
+			if (p != sym)
+				adjust_profit(p[-1], p[-1], LEFT(token_pair), idx);
+			if (!len)
+				break;
+			adjust_profit(RIGHT(token_pair), idx, p[2], p[2]);
+			memmove(p + 1, p + 2, len);
+		}
+		symbol[i]->len = end - sym;
 	}
+
+	token_profit[token_pair] = 0;
 }
 
 /* search the token with the maximum profit */
-- 
2.39.5