Re: [PATCH] ld: add support for LOG2() in linker scripts

[Clemens Lang <clemens dot lang at fau dot de>]

Hi,

thanks for your quick reply.

On Fri, Jul 19, 2013 at 02:28:40PM +0100, nick clifton wrote:
> >  - Where can I find the source for [2], so I can add documentation?
> 
> In <binutils_sources>/ld/ld.texinfo

See attached patch.

> >  - Do you require some form of copyright assignment?
> 
> Yes - an FSF copyright assignment.  I have attached the form that you
> can fill in and email off in order to start this process rolling.

I've mailed the form.

>   1. A ChangeLog entry describing the patch.
> 
>   2. A patch to the ld/NEWS file mentioning the new feature.
> 
>   3. A testcase in the ld/testsuite/ld-scripts directory to make
> sure that the new directive works correctly and continues to work in
> the future.

Added in the new version of the attached patch.

-- 
Clemens Lang
System Software Group, University of Erlangen-Nuremberg

>From 9b2f920e1422081305576ed27ebaa4c29056b2dd Mon Sep 17 00:00:00 2001
From: Clemens Lang <clemens.lang@fau.de>
Date: Fri, 19 Jul 2013 11:29:15 +0200
Subject: [PATCH] ld: add support for LOG2() in linker scripts

Adds a binary logarithm function usable in linker scripts. LOG2(x)
returns the logarithm of x, rounded down to the next integer. Returns
0 for x == 0. Can be used to determine the logarithm rounded up using
LOG2(x-1) + 1.

This is useful for ARM devices using an MPU conforming to PMSAv7, e.g.,
the Cortex-M3, where MPU regions need to be aligned depending on their
size. Without the ability to compute logarithms in linker scripts, this
cannot be achieved in a single linking pass.
---
 ld/ChangeLog                     |    6 ++++++
 ld/NEWS                          |    2 ++
 ld/ld.texinfo                    |    5 +++++
 ld/ldexp.c                       |   18 ++++++++++++++++++
 ld/ldgram.y                      |    4 +++-
 ld/ldlex.l                       |    1 +
 ld/testsuite/ld-scripts/log2.exp |   34 ++++++++++++++++++++++++++++++++++
 ld/testsuite/ld-scripts/log2.s   |    1 +
 ld/testsuite/ld-scripts/log2.t   |    8 ++++++++
 9 files changed, 78 insertions(+), 1 deletion(-)
 create mode 100644 ld/testsuite/ld-scripts/log2.exp
 create mode 100644 ld/testsuite/ld-scripts/log2.s
 create mode 100644 ld/testsuite/ld-scripts/log2.t

diff --git a/ld/ChangeLog b/ld/ChangeLog
index 08ac085..0a30c8b 100644
--- a/ld/ChangeLog
+++ b/ld/ChangeLog
@@ -1,3 +1,9 @@
+2013-07-16  Clemens Lang  <clemens.lang@fau.de>
+
+	* ldexp.c: Add LOG2() builtin function to linker script language
+	* ldgram.y: Likewise
+	* ldlex.l: Likewise
+
 2013-07-08  Jeff Law  <law@redhat.com>
 
 	* scripttempl/elf.sc: Handle function names and other text after
diff --git a/ld/NEWS b/ld/NEWS
index 34b494a..72ac60e 100644
--- a/ld/NEWS
+++ b/ld/NEWS
@@ -1,5 +1,7 @@
 -*- text -*-
 
+* Add LOG2() builtin function to the linker script language
+
 * Add support for the Texas Instruments MSP430X processor.
 
 * Add support for Altera Nios II.
diff --git a/ld/ld.texinfo b/ld/ld.texinfo
index d783ca9..2ccbe39 100644
--- a/ld/ld.texinfo
+++ b/ld/ld.texinfo
@@ -5943,6 +5943,11 @@ Return the length of the memory region named @var{memory}.
 Return the absolute LMA of the named @var{section}.  (@pxref{Output
 Section LMA}).
 
+@item LOG2(@var{exp})
+@kindex LOG2(@var{exp})
+Return the binary logarithm of @var{exp} rounded towards 0. @code{LOG2(0)}
+returns 0.
+
 @kindex MAX
 @item MAX(@var{exp1}, @var{exp2})
 Returns the maximum of @var{exp1} and @var{exp2}.
diff --git a/ld/ldexp.c b/ld/ldexp.c
index ae3919b..f038b83 100644
--- a/ld/ldexp.c
+++ b/ld/ldexp.c
@@ -81,6 +81,7 @@ exp_print_token (token_code_type code, int infix_p)
     { GE, ">=" },
     { LSHIFT, "<<" },
     { RSHIFT, ">>" },
+    { LOG2, "LOG2" },
     { ALIGN_K, "ALIGN" },
     { BLOCK, "BLOCK" },
     { QUAD, "QUAD" },
@@ -143,6 +144,19 @@ make_abs (void)
 }
 
 static void
+make_log2 (void)
+{
+  bfd_vma value = expld.result.value;
+  bfd_vma result = 0;
+  while (value >>= 1)
+    {
+      result++;
+    }
+  expld.result.section = NULL;
+  expld.result.value = result;
+}
+
+static void
 new_abs (bfd_vma value)
 {
   expld.result.valid_p = TRUE;
@@ -242,6 +256,10 @@ fold_unary (etree_type *tree)
 	  make_abs ();
 	  break;
 
+	case LOG2:
+	  make_log2 ();
+	  break;
+
 	case '~':
 	  expld.result.value = ~expld.result.value;
 	  break;
diff --git a/ld/ldgram.y b/ld/ldgram.y
index ee88196..5cec080 100644
--- a/ld/ldgram.y
+++ b/ld/ldgram.y
@@ -149,7 +149,7 @@ static int error_index;
 %token ALIGNMOD AT SUBALIGN HIDDEN PROVIDE PROVIDE_HIDDEN AS_NEEDED
 %type <token> assign_op atype attributes_opt sect_constraint
 %type <name>  filename
-%token CHIP LIST SECT ABSOLUTE  LOAD NEWLINE ENDWORD ORDER NAMEWORD ASSERT_K
+%token CHIP LIST SECT ABSOLUTE LOAD NEWLINE ENDWORD ORDER NAMEWORD ASSERT_K LOG2
 %token FORMAT PUBLIC DEFSYMEND BASE ALIAS TRUNCATE REL
 %token INPUT_SCRIPT INPUT_MRI_SCRIPT INPUT_DEFSYM CASE EXTERN START
 %token <name> VERS_TAG VERS_IDENTIFIER
@@ -1012,6 +1012,8 @@ exp	:
 			{ $$ = exp_nameop (ORIGIN, $3); }
 	|	LENGTH '(' NAME ')'
 			{ $$ = exp_nameop (LENGTH, $3); }
+	|	LOG2 '(' exp ')'
+			{ $$ = exp_unop (LOG2, $3); }
 	;
 
 
diff --git a/ld/ldlex.l b/ld/ldlex.l
index abe31c0..a64cf5b 100644
--- a/ld/ldlex.l
+++ b/ld/ldlex.l
@@ -259,6 +259,7 @@ V_IDENTIFIER [*?.$_a-zA-Z\[\]\-\!\^\\]([*?.$_a-zA-Z0-9\[\]\-\!\^\\]|::)*
 <EXPRESSION,BOTH,SCRIPT>"ALIGNOF"	{ RTOKEN(ALIGNOF); }
 <EXPRESSION,BOTH>"MAX"			{ RTOKEN(MAX_K); }
 <EXPRESSION,BOTH>"MIN"			{ RTOKEN(MIN_K); }
+<EXPRESSION,BOTH>"LOG2"			{ RTOKEN(LOG2); }
 <EXPRESSION,BOTH,SCRIPT>"ASSERT"	{ RTOKEN(ASSERT_K); }
 <BOTH,SCRIPT>"ENTRY"			{ RTOKEN(ENTRY);}
 <BOTH,SCRIPT,MRI>"EXTERN"		{ RTOKEN(EXTERN);}
diff --git a/ld/testsuite/ld-scripts/log2.exp b/ld/testsuite/ld-scripts/log2.exp
new file mode 100644
index 0000000..43827dc
--- /dev/null
+++ b/ld/testsuite/ld-scripts/log2.exp
@@ -0,0 +1,34 @@
+# Test LOG2() expression in linker script language.
+# By Clemens Lang
+#   Copyright 2013
+#   Free Software Foundation, Inc.
+#
+# This file is part of the GNU Binutils.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+# MA 02110-1301, USA.
+
+set testname "binary logarithm"
+
+if {![ld_assemble $as $srcdir/$subdir/log2.s tmpdir/log2.o]} {
+	unresolved $testname
+	return
+}
+
+if {![ld_simple_link $ld tmpdir/log2 "-T $srcdir/$subdir/log2.t tmpdir/log2.o"]} {
+	fail $testname
+} else {
+	pass $testname
+}
diff --git a/ld/testsuite/ld-scripts/log2.s b/ld/testsuite/ld-scripts/log2.s
new file mode 100644
index 0000000..f3f74ab
--- /dev/null
+++ b/ld/testsuite/ld-scripts/log2.s
@@ -0,0 +1 @@
+	.word 0
diff --git a/ld/testsuite/ld-scripts/log2.t b/ld/testsuite/ld-scripts/log2.t
new file mode 100644
index 0000000..63e43cc
--- /dev/null
+++ b/ld/testsuite/ld-scripts/log2.t
@@ -0,0 +1,8 @@
+ASSERT(LOG2(0) == 0,      "LOG2(0) == 0");
+ASSERT(LOG2(1) == 0,      "LOG2(1) == 0");
+ASSERT(LOG2(2) == 1,      "LOG2(2) == 1");
+ASSERT(LOG2(3) == 1,      "LOG2(3) == 1");
+ASSERT(LOG2(4) == 2,      "LOG2(4) == 2");
+ASSERT(LOG2(0x0ff) == 7,  "LOG2(0x0ff) == 7");
+ASSERT(LOG2(0x100) == 8,  "LOG2(0x100) == 8");
+ASSERT(LOG2(0x1ff) == 8,  "LOG2(0x1ff) == 8");