[Sbcl-commits] master: Improve basic block ordering for some loops.

[Lutz E. <le...@us...>]

The branch "master" has been updated in SBCL:
       via  67f44c921881037d272c5245f0ca2ab74ce1f763 (commit)
      from  e35a79c777f51eddd3dcb0ca27000ce4cfa60e73 (commit)

- Log -----------------------------------------------------------------
commit 67f44c921881037d272c5245f0ca2ab74ce1f763
Author: Lutz Euler <lut...@fr...>
Date:   Wed Oct 17 21:05:58 2012 +0200

    Improve basic block ordering for some loops.
    
    Currently the compiler rotates most loops to minimize branching costs,
    but for some loops this actually has the opposite effect (i.e., larger
    and slower code being generated), namely for those that already have the
    termination test at the end.
    
    So, inhibit loop rotation if such a loop is detected. The decision is
    based upon whether the loop's back edge starts with a conditional branch
    (don't rotate) or an unconditional branch (do rotate). This heuristic is
    correct in simple cases but may err, e.g. if a loop has multiple back
    edges. As we didn't try before and don't try now to analyse complex
    loops to aid the decision whether to rotate or not, or even how far,
    hopefully any differences introduced here will cancel on average with
    respect to their impact on performance and code size.
    
    (Loops consisting of only one basic block -- which necessarily have the
    termination test at the end -- were (obviously) treated correctly
    already. But even small loops can easily consist of multiple blocks, for
    example if the loop body contains code from inlining a function call.)
---
 NEWS                      |    2 ++
 src/compiler/control.lisp |   19 ++++++++++++++++++-
 2 files changed, 20 insertions(+), 1 deletions(-)

diff --git a/NEWS b/NEWS
index 9057028..a460f8d 100644
--- a/NEWS
+++ b/NEWS
@@ -2,6 +2,8 @@
 changes relative to sbcl-1.1.0:
   * enhancement: WITH-COMPILATION-UNIT no longer grabs the world-lock.
     (COMPILE and COMPILE-FILE still do.)
+  * optimization: The compiler no longer rotates loops in some cases where
+    this transformation actually lead to worse code being generated.
   * bug fix: SB-CLTL2:MACROEXPAND-ALL correctly handles shadowing of
     symbol-macros by lexical bindings.
   * bug fix: stack allocation was prevented by high DEBUG declaration in
diff --git a/src/compiler/control.lisp b/src/compiler/control.lisp
index 6d3b5f5..3c4a3ff 100644
--- a/src/compiler/control.lisp
+++ b/src/compiler/control.lisp
@@ -47,6 +47,22 @@
 ;;; suppress rotation of loop heads which are the start of a function
 ;;; (i.e. tail calls), as the debugger wants functions to start at the
 ;;; start.
+;;;
+;;; The rotation also is not done if the back edge identified in the
+;;; first step originates from a block that has more than one successor.
+;;; This matches loops that have their terminating condition tested at
+;;; the end, for which the original block order already minimizes the
+;;; number of branches: the back edge starts at a conditional branch at
+;;; the loop's tail and no other branches are needed. We used not to
+;;; test for this situation, rotating these loops, too, resulting in
+;;; machine code that looked like this
+;;;       jump to L1
+;;;   L0: body of loop
+;;;       conditionally branch to L2 if the loop should terminate
+;;;   L1: jump to L0
+;;;   L2:
+;;; which is ugly, and larger and often slower than what is generated
+;;; when not rotating these loops.
 (defun find-rotated-loop-head (block)
   (declare (type cblock block))
   (let* ((num (block-number block))
@@ -59,7 +75,8 @@
     (cond
      ((and pred
            (not (physenv-nlx-info env))
-           (not (eq (lambda-block (block-home-lambda block)) block)))
+           (not (eq (lambda-block (block-home-lambda block)) block))
+           (null (cdr (block-succ pred))))
       (let ((current pred)
             (current-num (block-number pred)))
         (block DONE

-----------------------------------------------------------------------


hooks/post-receive
-- 
SBCL