[Issue 4438] A missed function inlining

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4438



--- Comment #4 from bearophile_hugs at eml.cc 2011-04-14 17:25:38 PDT ---
A different case of missed inlining. In the following code isValidMove() is not
inlined by DMD 2.052 (with -O -inline -release), despite this function contains
no loop and no throws. Removing the "ref" for the board array in the
isValidMove() signature changes nothing.

The runtime is 12.6 seconds, the alternative version of the knightsTour()
function with manually inlined isValidMove() (currently commented out below)
runs in 8.0 seconds. My tests show that GCC -O3 is able to inline similar code
written in C.



// Code adapted from:
// http://en.literateprograms.org/The_Knight's_Tour_(C)?oldid=14704
import core.stdc.stdio: printf;

template TypeTuple(T...) {
    alias T TypeTuple;
}

bool isValidMove(int N)(ref int[N][N] board, int xpos, int ypos, int nmove) {
    if (xpos < 0 || xpos >= N || ypos < 0 || ypos >= N ||
        (board[xpos][ypos] && board[xpos][ypos] < nmove))
        return false;
    return true;
}

// run time: 12.6 seconds
bool knightsTour(int N)(ref int[N][N] board, int xpos, int ypos, int nmove) {
    if (!isValidMove(board, xpos, ypos, nmove))
        return false;

    board[xpos][ypos] = nmove;

    if (nmove == N * N)
        return true;

    alias TypeTuple!(+1, -2, -2, -1, -1, +2, +2, +1) spx;
    alias TypeTuple!(+2, +1, -1, +2, -2, +1, -1, -2) spy;
    static assert(spx.length == spy.length);
    bool ok = true;
    foreach (i, sx; spx)
        ok = ok && !knightsTour(board, xpos + sx, ypos + spy[i], nmove + 1);
    if (ok) {
        board[xpos][ypos] = N * N;
        return false;
    }

    return true;
}

/*
// run time:  8.0 seconds
bool knightsTour(int N)(ref int[N][N] board, int xpos, int ypos, int nmove) {
    // if is not valid move
    if (xpos < 0 || xpos >= N || ypos < 0 || ypos >= N ||
        (board[xpos][ypos] && board[xpos][ypos] < nmove))
        return false;

    board[xpos][ypos] = nmove;

    if (nmove == N * N)
        return true;

    alias TypeTuple!(+1, -2, -2, -1, -1, +2, +2, +1) spx;
    alias TypeTuple!(+2, +1, -1, +2, -2, +1, -1, -2) spy;
    static assert(spx.length == spy.length);
    bool ok = true;
    foreach (i, sx; spx)
        ok = ok && !knightsTour(board, xpos + sx, ypos + spy[i], nmove + 1);
    if (ok) {
        board[xpos][ypos] = N * N;
        return false;
    }

    return true;
}
*/

void main() {
    enum int side = 8;
    enum int xpos = 0;
    enum int ypos = xpos;

    int[side][side] board;
    printf("Executing Knight's Tour...\n");

    if (knightsTour(board, xpos, ypos, 1)) {
        printf("Solution found:\n");
        foreach (ref row; board) {
            foreach (item; row)
                printf("%3d", item);
            printf("\n");
        }
    } else
        printf("No solution found.\n");
}


The first part of the assembly of knightsTour() shows the call to
isValidMove():

_D4test20__T11knightsTourVk8Z11knightsTourFKG8G8iiiiZb  comdat
    sub ESP,02Ch
    push EBX
    push EBP
    push ESI
    mov ESI,044h[ESP]
    push EDI
    mov 038h[ESP],EAX
    push ESI
    push dword ptr 048h[ESP]
    push dword ptr 048h[ESP]
    call near ptr _D4test20__T11isValidMoveVk8Z11isValidMoveFKG8G8iiiiZb
    xor AL,1
    je  L2D
    pop EDI
    ...

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------