SSAWLF.c

/*******************************************************************************

 $Id$

 This file realizes the withlop folding for a code in ssa form. it uses no
 masks anymore. Most code is unchanged from the original implementation in
 WLF.c . Due to the ssaform, we can simplify some task in WLF concerning
 renaming operations.

 *******************************************************************************

 Usage of arg_info:

 wlfm_search_WL  :
 wlfm_search_ref :
 - NEXT   : store old information in nested WLs
 - WL     : reference to base node of current WL (N_Nwith)
 - FLAG   : collects information in the wlfm_search phase if there is
            at least one foldable reference in the WL.

 wlfm_replace    :
 wlfm_rename     :
 - SUBST  : Pointer to subst N_Ncode/ pointer to copy of subst N_Ncode
 - NEW_ID : pointer to N_id which shall replace the prf sel()
            in the target Code.
 - ID     : pointer to original N_id node in target WL to replace
            by subst WL.
 - NCA    : points to the assignment of the subst WL. Here new
                     assignments are inserted to define new variables.

 all wlfm phases :
 - ASSIGN : always the last N_assign node
 - FUNDEF : pointer to last fundef node. Needed to access vardecs

 ******************************************************************************

 Usage of ID_WL:

 ID_WL is used in 2 ways:
 (1) in WLI phase we store a pointer to (assign node of) a WL in ID_WL if
     the Id references a new WL. This pointer is used in WLF.
 (2) When the decision to fold the Id has been made it is necessary to
     create new code blocks. In this new code blocks ID_WL is used to
     point to it's original Id. So we have to distinguish between the Ids
     which are in the original code (1) and those in newly created code
     blocks (2).
     Creation of new code is initiated in CreateCode() and the resulting
     N_Ncode nodes are collected in new_codes until they are inserted into the
     syntax tree in WLFNwith(). While a code is in new_codes, ID_WL of every
     Id inside the code points to it's original Id (this is the Id which was
     copied by DUPdoDupTree()). DUPdoDupTree() sets this pointer and, if the
     argument of DUPdoDupTree() is a code inside new_codes, copies ID_WL of
     this code (which is a pointer to the original).

 ******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "types.h"
#include "tree_basic.h"
#include "tree_compound.h"
#include "str.h"
#include "memory.h"
#include "free.h"
#include "DupTree.h"
#include "globals.h"
#include "ctinfo.h"
#include "dbug.h"
#include "traverse.h"
#include "SSAWithloopFolding.h"
#include "SSAWLF.h"
#include "shape.h"
#include "type_utils.h"
#include "new_types.h"
#include "new_typecheck.h"
#include "constants.h"
#include "math_utils.h"

/*
 * INFO structure
 */
struct INFO {
    info *next;
    node *subst;
    node *wl;
    node *new_id;
    node *assign;
    node *fundef;
    node *id;
    node *nca;
    int flag;
    int mystery;
};

/*
 * INFO macros
 */
#define INFO_NEXT(n) (n->next)
#define INFO_SUBST(n) (n->subst)
#define INFO_WL(n) (n->wl)
#define INFO_NEW_ID(n) (n->new_id)
#define INFO_ASSIGN(n) (n->assign)
#define INFO_FUNDEF(n) (n->fundef)
#define INFO_ID(n) (n->id)
#define INFO_NCA(n) (n->nca)
#define INFO_FLAG(n) (n->flag)
#define INFO_MYSTERY(n) (n->mystery)

/*
 * INFO functions
 */
static info *
MakeInfo ()
{
    info *result;

    DBUG_ENTER ("MakeInfo");

    result = MEMmalloc (sizeof (info));

    INFO_NEXT (result) = NULL;
    INFO_SUBST (result) = NULL;
    INFO_WL (result) = NULL;
    INFO_NEW_ID (result) = NULL;
    INFO_ASSIGN (result) = NULL;
    INFO_FUNDEF (result) = NULL;
    INFO_ID (result) = NULL;
    INFO_NCA (result) = NULL;
    INFO_FLAG (result) = 0;
    INFO_MYSTERY (result) = 0;

    DBUG_RETURN (result);
}

static info *
FreeInfo (info *info)
{
    DBUG_ENTER ("FreeInfo");

    info = MEMfree (info);

    DBUG_RETURN (info);
}

/******************************************************************************
 *
 *   typedefs
 *
 ******************************************************************************/

/* Several traverse functions of this file are traversed for different
   purposes. This enum determines ths function. */
typedef enum {
    wlfm_search_WL,  /* find new WLs */
    wlfm_search_ref, /* find references within WL to fold. */
    wlfm_rename,     /* traverse copied body of substWL and
                        rename variables to avoid name clashes. */
    wlfm_replace     /* traverse copied body of targetWL and
                        replace substituted reference. */
    /* wlfm_search_WL and wlm_search_ref both traverse the original target code
       block. The first phase searches for other WLs inside the current WL
       body. The most cascated WLs are folded first. The second phase again
       traverses the target code and, if a foldable reference is found, initiates
       folding.  wlfm_replace traverses the copied target code block and tries to
       find the same point (Id which should be folded) here. Then the subst code
       is inserted at this point.  wlfm_rename traverses the subst code and renames
       variables which would lead to name clashes. */
} wlf_mode_type;

typedef struct CODE_CONSTRUCTION {
    node *target;
    node *subst;
    node *new;
    struct CODE_CONSTRUCTION *next;
} code_constr_type;

/******************************************************************************
 *
 *   global variables
 *
 ******************************************************************************/

static wlf_mode_type wlf_mode;

static code_constr_type *code_constr; /* list of combinded code blocks */

static node *new_codes; /* list of created N_Ncode nodes */

static info *ref_mode_arg_info; /* saves arg_info for CreateCode(). Else
                                   we would have to pass arg_info through
                                   many functions (which costs time) */

static intern_gen *new_ig; /* new generators derived by a traversel
                              of one Ncode block. */

static intern_gen *all_new_ig; /* new generators derived from all Ncode
                                  nodes. */

/* global vars to speed up function call of IntersectGrids(). They are only used
   to transfer information between IntersectGrids() and IntersectInternGen(). */

static int *intersect_grids_ot; /* grid offsets used by IntersectGrids() */

static int *intersect_grids_os;

static intern_gen *intersect_grids_tig, *intersect_grids_sig, *intersect_grids_baseig;

static intern_gen *intersect_intern_gen; /* resulting igs of IntersectInternGen. */

/******************************************************************************
 *
 * function:
 *   void AddCC(node *targetn, node *substn, node *resultn)
 *
 * description:
 *   adds entry to the global code_constr list.
 *
 ******************************************************************************/

static void
AddCC (node *targetn, node *substn, node *resultn)
{
    code_constr_type *cc;

    DBUG_ENTER ("AddCC");

    cc = MEMmalloc (sizeof (code_constr_type));
    cc->target = targetn;
    cc->subst = substn;
    cc->new = resultn;
    cc->next = code_constr;
    code_constr = cc;

    DBUG_VOID_RETURN;
}

/******************************************************************************
 *
 * function:
 *   code_constr_type *SearchCC(node *targetn, node *substn)
 *
 * description:
 *   Searches for an existing entry of targetn and substn and returns it
 *   or NULL if not found
 *
 ******************************************************************************/

static code_constr_type *
SearchCC (node *targetn, node *substn)
{
    code_constr_type *cc;

    DBUG_ENTER ("SearchCC");

    cc = code_constr;
    while (cc && (cc->target != targetn || cc->subst != substn)) {
        cc = cc->next;
    }

    DBUG_RETURN (cc);
}

/******************************************************************************
 *
 * function:
 *   void FreeCC(code_constr_type *cc)
 *
 * description:
 *   sets whole cc list free
 *
 ******************************************************************************/

static void
FreeCC (code_constr_type *cc)
{
    code_constr_type *tmpcc;

    DBUG_ENTER ("FreeCC");

    while (cc) {
        tmpcc = cc;
        cc = cc->next;
        tmpcc = MEMfree (tmpcc);
    }

    DBUG_VOID_RETURN;
}

/******************************************************************************
 *
 * function:
 *   intern_gen *MergeGenerators(intern_gen *ig)
 *
 * description:
 *   tries to merge gererators (grids) to reduce effort of further
 *   intersections.
 *   This optimization can result in better codeproduction of compile
 *   (wltransform.c, OptimizeWL does something similar but it not that
 *    powerful).
 *
 ******************************************************************************/

static intern_gen *
MergeGenerators (intern_gen *ig)
{
    DBUG_ENTER ("MergeGenerators");

    DBUG_RETURN (ig);
}

/******************************************************************************
 *
 * function:
 *   intern_gen *LinearTransformationsHelp(intern_gen *ig, int dim, prf prf,
 *                                         int arg_no, int constval)
 *
 * description:
 *   Executes transformation (prf const) on the given ig in dimension dim.
 *   More complex transformations require to split up generators in two new
 *   generators (original ig and newig). If a newig is created, it is returned.
 *
 ******************************************************************************/

static intern_gen *
LinearTransformationsHelp (intern_gen *ig, int dim, prf prf, int arg_no, int constval)
{
    int lbuf, ubuf, cut, buf;
    intern_gen *newig = NULL;

    DBUG_ENTER ("LinearTransformationsHelp");
    DBUG_ASSERT (((1 == arg_no) || (2 == arg_no)), "wrong parameters");

    switch (prf) {
    case F_add_SxS:
        /* addition is commutable, grids are not affected. */
        ig->l[dim] -= constval;
        ig->u[dim] -= constval;
        break;

    case F_sub_SxS:
        if (2 == arg_no) {
            /* index - scalar, grids are not affected */
            ig->l[dim] += constval;
            ig->u[dim] += constval;
        } else { /* arg_no == 1 */
            /* scalar - index */
            lbuf = constval - ig->u[dim] + 1; /* +1 to transform < in <= */
            ubuf = constval - ig->l[dim] + 1; /* +1 to transform <= in < */

            if (ig->step) {
                /*
                 * reverse the grid.
                 * Example:
                 * "xxx  xxx  xx" => "xx  xxx  xxx"
                 * done with 2 gens: "xx   xx   xx" &&
                 *                       "x    x  "
                 */
                cut = (ig->u[dim] - ig->l[dim]) % ig->step[dim];
                if (cut == 0) {
                    lbuf += ig->step[dim] - ig->width[dim];
                } else if (cut > ig->width[dim]) {
                    lbuf += cut - ig->width[dim];
                } else if (cut < ig->width[dim]) {
                    /* make newig */
                    newig = WLFcopyInternGen (ig);
                    newig->l[dim] = ig->l[dim] + cut;
                    newig->width[dim] = ig->width[dim] - cut;
                    ig->width[dim] = cut;
                    /* if u - l is smaller than width, the newig is empty */
                    if (newig->u[dim] <= newig->l[dim]) {
                        newig = WLFfreeInternGen (newig);
                    } else {
                        buf = (constval - newig->u[dim] + 1 + newig->step[dim]
                               - newig->width[dim]);
                        newig->u[dim] = constval - newig->l[dim] + 1;
                        newig->l[dim] = buf;
                    }
                }
            }

            ig->l[dim] = lbuf;
            ig->u[dim] = ubuf;
        }
        break;

    case F_mul_SxS:
        /*
         * first try  (srs):  ig->l[dim] = (ig->l[dim] + constval - 1) / constval;
         *                    ig->u[dim] = (ig->u[dim] - 1) / constval +1;
         *
         * second try (sbs):  ig->l[dim] = (ig->l[dim] + constval - 1) / constval;
         *                    ig->u[dim] = (ig->u[dim] + constval - 1) / constval;
         *
         * But this is still incorrect in some cases, e.g. if (constval < 0) ...
         *
         * These conditions must hold for l_neu and u_neu:
         *
         *   constval > 0:      l  >  constval * ( l_neu - 1 )
         *                  &&  l  <= constval * l_neu
         *                  &&  u  >  constval * ( u_neu - 1 )
         *                  &&  u  <= constval * u_neu
         *
         *             ==>      l / constvec  <=  l_neu  <  l / constvec + 1
         *                  &&  u / constvec  <=  u_neu  <  u / constvec + 1
         *
         *   constval < 0:      u  >  constval * l_neu           // bounds reflected, ...
         *                  &&  u  <= constval * ( l_neu - 1 )   // ... <= and < reversed
         *                  &&  l  >  constval * u_neu
         *                  &&  l  <= constval * ( u_neu - 1 )
         *
         *             ==>      u / constvec  <  l_neu  <=  u / constval + 1
         *                  &&  l / constvec  <  u_neu  <=  l / constval + 1
         *
         * Therefore the following code should work correctly:
         */
        if (constval > 0) {
            ig->l[dim] = ((ig->l[dim] % constval == 0) || (ig->l[dim] < 0))
                           ? (ig->l[dim] / constval)
                           : (ig->l[dim] / constval + 1);
            ig->u[dim] = ((ig->u[dim] % constval == 0) || (ig->u[dim] < 0))
                           ? (ig->u[dim] / constval)
                           : (ig->u[dim] / constval + 1);
        }
        if (constval < 0) {
            ig->l[dim] = ((ig->u[dim] % constval == 0) || (ig->u[dim] < 0))
                           ? (ig->u[dim] / constval + 1)
                           : (ig->u[dim] / constval);
            ig->u[dim] = ((ig->l[dim] % constval == 0) || (ig->l[dim] < 0))
                           ? (ig->l[dim] / constval + 1)
                           : (ig->l[dim] / constval);
        }

        if (ig->step) {
            DBUG_ASSERT (0, ("WL folding with transformed index variables "
                             "by multiplication and grids not supported right now."));
        }
        break;

    case F_div_SxS:
        DBUG_ASSERT ((arg_no == 2),
                     "WLF transformation (scalar / index) not yet implemented!");

        /*
         * first try  (srs):  ig->l[dim] = ig->l[dim] * constval;
         *                    ig->u[dim] = ig->u[dim] * constval;
         *
         * But this is incorrect in some cases, e.g. if (constval < 0) ...
         *
         * These conditions must hold for l_neu and u_neu:
         *
         *   constval > 0:      l  >  ( l_neu - 1 ) / constval
         *                  &&  l  <= l_neu / constval
         *                  &&  u  >  ( u_neu - 1 ) / constval
         *                  &&  u  <= u_neu / constval
         *
         *             ==>      l * constvec  <=  l_neu  <  l * constvec + 1
         *                  &&  u * constvec  <=  u_neu  <  u * constvec + 1
         *
         *   constval < 0:      u  >  l_neu / constval           // bounds reflected, ...
         *                  &&  u  <= ( l_neu - 1 ) / constval   // ... <= and < reversed
         *                  &&  l  >  u_neu / constval
         *                  &&  l  <= ( u_neu - 1 ) / constval
         *
         *             ==>      u * constvec  <  l_neu  <=  u * constval + 1
         *                  &&  l * constvec  <  u_neu  <=  l * constval + 1
         *
         * Therefore the following code should work correctly:
         */
        if (constval > 0) {
            ig->l[dim] = ig->l[dim] * constval;
            ig->u[dim] = ig->u[dim] * constval;
        }
        if (constval < 0) {
            ig->l[dim] = ig->u[dim] * constval + 1;
            ig->u[dim] = ig->l[dim] * constval + 1;
        }

        if (ig->step) {
            DBUG_ASSERT (0, ("WL folding with transformed index variables "
                             "by division and grids not supported right now."));
        }
        break;

    default:
        DBUG_ASSERT (0, ("Wrong transformation function"));
    }

    DBUG_RETURN (newig);
}

/******************************************************************************
 *
 * function:
 *   void LinearTransformationsScalar( intern_gen *ig,
 *                                     index_info *transformations, int dim)
 *
 * description:
 *   like LinearTransformationsVector(), but only transforms one dimension of ig.
 *
 *
 ******************************************************************************/

static intern_gen *
LinearTransformationsScalar (intern_gen *ig, index_info *transformations, int dim)
{
    intern_gen *actig, *newig;

    DBUG_ENTER ("LinearTransformationsScalar");
    DBUG_ASSERT (0 == transformations->vector, ("wrong parameters"));
    DBUG_ASSERT (!transformations->last[0] || !transformations->last[0]->vector,
                 ("scalar points to vector"));
    DBUG_ASSERT (transformations->permutation[0], ("scalar constant???"));

    actig = ig;
    if (transformations->arg_no)
        /* valid prf. */
        while (actig) { /* all igs */
            newig = LinearTransformationsHelp (actig, dim, transformations->prf,
                                               transformations->arg_no,
                                               transformations->const_arg[0]);

            if (newig) {
                newig->next = ig; /* insert new element before whole list. */
                ig = newig;       /* set new root */
            }
            actig = actig->next;
        }

    if (transformations->last[0]) {
        ig = LinearTransformationsScalar (ig, transformations->last[0], dim);
    }

    DBUG_RETURN (ig);
}

/******************************************************************************
 *
 * function:
 *   void LinearTransformationsVector(intern_gen *ig,
 *                                    index_info *transformations)
 *
 * description:
 *   realizes transformations on the given list of intern gens.
 *
 *
 ******************************************************************************/

static intern_gen *
LinearTransformationsVector (intern_gen *ig, index_info *transformations)
{
    int dim, act_dim;
    intern_gen *actig, *newig;

    DBUG_ENTER ("LinearTransformationsVector");
    DBUG_ASSERT (transformations->vector == ig->shape,
                 ("Transformations to not fit to generators"));

    dim = ig->shape;

    if (transformations->vector && transformations->arg_no) {
        /* vector transformation and a valid prf. */
        for (act_dim = 0; act_dim < dim; act_dim++) { /* all dimensions */
            actig = ig;
            if (transformations->permutation[act_dim]) {
                while (actig) { /* all igs */
                    newig
                      = LinearTransformationsHelp (actig, act_dim, transformations->prf,
                                                   transformations->arg_no,
                                                   transformations->const_arg[act_dim]);
                    if (newig) {
                        newig->next = ig; /* insert new element before whole list. */
                        ig = newig;       /* set new root */
                    }
                    actig = actig->next;
                }
            }
        }
    }

    if (transformations->last[0] && transformations->last[0]->vector) {
        ig = LinearTransformationsVector (ig, transformations->last[0]);
    } else { /* maybe additional scalar transformations */
        for (act_dim = 0; act_dim < dim; act_dim++) {
            if (transformations->last[act_dim]) {
                ig = LinearTransformationsScalar (ig, transformations->last[act_dim],
                                                  act_dim);
            }
        }
    }

    DBUG_RETURN (ig);
}

/******************************************************************************
 *
 * function:
 *   intern_gen *FinalTransformations( intern_gen *ig,
 *                                     index_info *transformations,
 *                                     int target_dim);
 *
 * description:
 *   transforms list of ig into cuboids of dimension target_dim.
 *
 *
 ******************************************************************************/

static intern_gen *
FinalTransformations (intern_gen *substig, index_info *transformations, int target_dim)
{
    intern_gen *tmpig, *newig, *rootig;
    int ok, i, *help;

    DBUG_ENTER ("FinalTransformations");
    DBUG_ASSERT (transformations->vector == substig->shape, ("wrong parameters"));

    /* create array to speed up later transformations.
       help[i] is
       - 0 if the ith index scalar is not used to index the subst array
       - d if the ith index scalar addresses the dth component of the subst array.

       Example:
       iv=[i,j,k]
       subst array A[42,i,k]
       help: [2,0,3] */
    i = sizeof (int) * target_dim;
    help = MEMmalloc (i);
    help = memset (help, 0, i);
    for (i = 0; i < transformations->vector; i++) {
        if (transformations->permutation[i]) {
            help[transformations->permutation[i] - 1] = i + 1;
        }
    }

    /* now process all substig and create new ig list rootig */
    tmpig = substig;
    newig = rootig = NULL;

    while (tmpig) {
        /* Check whether constants in *transformations disqualify this tmpig */
        ok = 1;
        for (i = 0; i < tmpig->shape && ok; i++)
            ok = (transformations->permutation[i] ||                /* not a constant */
                  ((tmpig->l[i] <= transformations->const_arg[i] && /* in range */
                    transformations->const_arg[i] < tmpig->u[i])
                   && (!tmpig->step || /* and no grid */
                       (transformations->const_arg[i] - tmpig->l[i])
                           % /* or in this grid */
                           tmpig->step[i]
                         < tmpig->width[i])));

        if (ok) {
            /* start transformations */
            newig = WLFcreateInternGen (target_dim, NULL != tmpig->step);
            for (i = 0; i < target_dim; i++) {
                if (help[i]) {
                    newig->l[i] = tmpig->l[help[i] - 1];
                    newig->u[i] = tmpig->u[help[i] - 1];
                    if (tmpig->step) {
                        newig->step[i] = tmpig->step[help[i] - 1];
                        newig->width[i] = tmpig->width[help[i] - 1];
                    }
                } else {
                    newig->l[i] = 0;
                    newig->u[i] = INT_MAX;
                    if (tmpig->step) {
                        newig->step[i] = 1;
                        newig->width[i] = 1;
                    }
                }
            }
            DBUG_ASSERT (0 == WLFnormalizeInternGen (newig),
                         ("Error while normalizing ig"));

            newig->code = tmpig->code;
            newig->next = rootig;
            rootig = newig;
        }

        /* go to next substig */
        tmpig = tmpig->next;
    }

    help = MEMfree (help);
    WLFfreeInternGenChain (substig);

    DBUG_RETURN (rootig);
}

/******************************************************************************
 *
 * function:
 *   node *CreateCode(node *target, node *subst)
 *
 * description:
 *   substitutes the code block subst into target. INFO_ID points
 *   to the N_id node in the target WL which shall be replaced.
 *   New vardecs and assignments are introduced and an N_Ncode node is returned.
 *   Most of the work is done in the usual traversal steps (with mode
 *   wlfm_replace and wlfm_rename).
 *
 ******************************************************************************/

static node *
CreateCode (node *target, node *subst)
{
    node *coden;
    info *new_arg_info;

    DBUG_ENTER ("CreateCode");

    DBUG_ASSERT ((N_code == NODE_TYPE (target)), "wrong Parameter");
    DBUG_ASSERT ((N_code == NODE_TYPE (subst)), "wrong Parameter");

    wlf_mode = wlfm_replace;

    /* create new arg_info to avoid modifications of the old one and copy
       all relevant information */
    new_arg_info = MakeInfo ();
    INFO_FUNDEF (new_arg_info) = INFO_FUNDEF (ref_mode_arg_info);
    INFO_ID (new_arg_info) = INFO_ID (ref_mode_arg_info);
    INFO_NCA (new_arg_info) = INFO_NCA (ref_mode_arg_info);
    INFO_SUBST (new_arg_info) = subst;
    INFO_NEW_ID (new_arg_info) = NULL;

    /* WHY is this copied? */
    INFO_MYSTERY (new_arg_info) = INFO_MYSTERY (ref_mode_arg_info);

    /*
     * DUPdoDupTree() shall fill ID_WL of Id nodes with special information.
     * So we have to call DUPdoDupTree() with DUP_WLF.
     */
    coden = DUPdoDupTreeType (CODE_CBLOCK (target), DUP_WLF);
    coden = TRAVdo (coden, new_arg_info);
    coden = TBmakeCode (coden, DUPdoDupTreeType (CODE_CEXPRS (target), DUP_WLF));

    new_arg_info = FreeInfo (new_arg_info);

    wlf_mode = wlfm_search_ref;

    DBUG_RETURN (coden);
}

/******************************************************************************
 *
 * function:
 *   void IntersectGrids(int dim, intern_gen *ig)
 *
 * description:
 *   recursive function to intersect two grids. Information are made available
 *   in global variables intersect_grids* to speed up recursive function calls.
 *
 ******************************************************************************/

static void
IntersectGrids (int dim)
{
    int dc, first, last, d;
    intern_gen *ig;
    code_constr_type *cc;
    node *coden;

    DBUG_ENTER ("IntersectGrids");

    dc = 0;

    while (dc < intersect_grids_baseig->step[dim]) {
        /* search common dc */
        if (((!intersect_grids_tig->step)
             || ((dc + intersect_grids_ot[dim]) % intersect_grids_tig->step[dim]
                 < intersect_grids_tig->width[dim]))
            && ((!intersect_grids_sig->step)
                || ((dc + intersect_grids_os[dim]) % intersect_grids_sig->step[dim]
                    < intersect_grids_sig->width[dim]))) {
            first = dc;
            /* search first dc where either in tig or sig the element is
               not present. */
            do {
                dc++;
            } while (
              ((!intersect_grids_tig->step)
               || ((dc + intersect_grids_ot[dim]) % intersect_grids_tig->step[dim]
                   < intersect_grids_tig->width[dim]))
              && ((!intersect_grids_sig->step)
                  || ((dc + intersect_grids_os[dim]) % intersect_grids_sig->step[dim]
                      < intersect_grids_sig->width[dim]))
              && (dc < intersect_grids_baseig->step[dim]));
            last = dc;

            if (dim < intersect_grids_baseig->shape - 1) {
                /* process inner dimensions if lower bound is less then upper bound. */
                if (intersect_grids_baseig->l[dim] + first
                    < intersect_grids_baseig->u[dim]) {
                    intersect_grids_baseig->l[dim] += first;
                    intersect_grids_baseig->width[dim] = last - first;
                    IntersectGrids (dim + 1);
                    intersect_grids_baseig->l[dim] -= first; /* restore old value */
                } else {
                    dc = intersect_grids_baseig->step[dim]; /* stop further search */
                }
            } else {
                /* create new ig and add it to structures
                   if lower bound is less then upper bound. */
                if (intersect_grids_baseig->l[dim] + first
                    < intersect_grids_baseig->u[dim]) {
                    ig = WLFcreateInternGen (intersect_grids_baseig->shape, 1);
                    for (d = 0; d < intersect_grids_baseig->shape; d++) {
                        ig->l[d] = intersect_grids_baseig->l[d];
                        ig->u[d] = intersect_grids_baseig->u[d];
                        ig->step[d] = intersect_grids_baseig->step[d];
                        ig->width[d] = intersect_grids_baseig->width[d];
                    }
                    ig->l[dim] += first;
                    ig->width[dim] = last - first;

                    /* add craetes code to code_constr list and to new_codes. */
                    cc = SearchCC (intersect_grids_tig->code, intersect_grids_sig->code);
                    if (cc) {
                        ig->code = cc->new;
                    } else {
                        coden = CreateCode (intersect_grids_tig->code,
                                            intersect_grids_sig->code);
                        ig->code = coden;
                        AddCC (intersect_grids_tig->code, intersect_grids_sig->code,
                               coden);
                        CODE_NEXT (coden) = new_codes;
                        new_codes = coden;
                    }

                    /* add new generator to intersect_intern_gen list. */
                    ig->next = intersect_intern_gen;
                    intersect_intern_gen = ig;
                } else {
                    dc = intersect_grids_baseig->step[dim]; /* stop further search */
                }
            }
        }

        dc++;
    }

    DBUG_VOID_RETURN;
}

/******************************************************************************
 *
 * function:
 *   intern_gen *IntersectInternGen(intern_gen *tig, intern_gen *sig)
 *
 * description:
 *   Intersects the generators of the currently processed code (tig) and all
 *   generators of the subst WL (sig). Appends new codes to code_constr.
 *   Returns intern_gen list of new intersections.
 *
 ******************************************************************************/

static intern_gen *
IntersectInternGen (intern_gen *target_ig, intern_gen *subst_ig)
{
    intern_gen *sig, *new_gen, *new_gen_step, *new_gen_nostep;
    int d, max_dim, l, u, create_steps;
    code_constr_type *cc;
    node *coden;

    DBUG_ENTER ("IntersectInternGen");
    DBUG_ASSERT (target_ig->shape == subst_ig->shape, ("wrong parameters"));

    max_dim = target_ig->shape;
    new_gen_step = NULL;
    new_gen_nostep = NULL;
    intersect_intern_gen = NULL;

    while (target_ig) {
        sig = subst_ig;
        while (sig) {
            if (!new_gen_step) {
                new_gen_step = WLFcreateInternGen (target_ig->shape, 1);
            }
            if (!new_gen_nostep) {
                new_gen_nostep = WLFcreateInternGen (target_ig->shape, 0);
            }

            create_steps = target_ig->step || sig->step;
            if (create_steps) {
                new_gen = new_gen_step;
                new_gen_step = NULL;
            } else {
                new_gen = new_gen_nostep;
                new_gen_nostep = NULL;
            }

            /* here we have to intersect target_ig and sig */
            /* first the bounds, ignore step/width */
            for (d = 0; d < max_dim; d++) {
                l = MATHmax (target_ig->l[d], sig->l[d]);
                u = MATHmin (target_ig->u[d], sig->u[d]);
                if (l >= u) {
                    break; /* empty intersection */
                } else {
                    new_gen->l[d] = l;
                    new_gen->u[d] = u;
                }
            }

            if (d == max_dim) {
                /* we have a new ig. Maybe. Because if both generators are
                   grids they may still be disjuct. */
                if (create_steps) {
                    /* prepare parameters for recursive function IntersectGrids().
                       Global pointers are used to speed up function call. */
                    /* new_gen will be the reference structure for new igs
                       created within IntersectGrids(). */
                    if (!target_ig->step) {
                        for (d = 0; d < max_dim; d++) {
                            new_gen->step[d] = sig->step[d];
                        }
                    } else if (!sig->step) {
                        for (d = 0; d < max_dim; d++) {
                            new_gen->step[d] = target_ig->step[d];
                        }
                    } else {
                        for (d = 0; d < max_dim; d++) {
                            new_gen->step[d] = MATHlcm (target_ig->step[d], sig->step[d]);
                        }
                    }

                    /* compute offsets */
                    if (target_ig->step) {
                        for (d = 0; d < max_dim; d++) {
                            intersect_grids_ot[d]
                              = (new_gen->l[d] - target_ig->l[d]) % target_ig->step[d];
                        }
                    }
                    if (sig->step) {
                        for (d = 0; d < max_dim; d++) {
                            intersect_grids_os[d]
                              = (new_gen->l[d] - sig->l[d]) % sig->step[d];
                        }
                    }

                    intersect_grids_baseig = new_gen;
                    intersect_grids_tig = target_ig;
                    intersect_grids_sig = sig;

                    IntersectGrids (0);
                    /* the mem of new_gen has not been erased in IntersectGrids(). It can
                       be used for the next intersection. Don't free it. */
                    new_gen_step = new_gen;
                } else {
                    /* craete new code and add it to code_constr list and to new_codes. */
                    cc = SearchCC (target_ig->code, sig->code);
                    if (cc) {
                        new_gen->code = cc->new;
                    } else {
                        coden = CreateCode (target_ig->code, sig->code);
                        new_gen->code = coden;
                        AddCC (target_ig->code, sig->code, coden);
                        CODE_NEXT (coden) = new_codes;
                        new_codes = coden;
                    }

                    /* add new generator to intersect_intern_gen list. */
                    new_gen->next = intersect_intern_gen;
                    intersect_intern_gen = new_gen;
                    new_gen = NULL;
                }
            }

            sig = sig->next; /* go on with next subst ig */
        }
        target_ig = target_ig->next; /* go on with next target ig */
    }

    if (new_gen_step) {
        new_gen_step = WLFfreeInternGen (new_gen_step);
    }
    if (new_gen_nostep) {
        new_gen_nostep = WLFfreeInternGen (new_gen_nostep);
    }

    DBUG_RETURN (intersect_intern_gen);
}

/******************************************************************************
 *
 * function:
 *   intern_gen *RemoveDoubleIndexVectors( intern_gen *subst_ig,
 *                                         index_info *transformations)
 *
 * description:
 *   only used if permutations of index scalar variables are enabled.
 *   This is a transformation to reduce the number of components of the ig.
 *
 ******************************************************************************/

static intern_gen *
RemoveDoubleIndexVectors (intern_gen *subst_ig, index_info *transformations)
{