← Back to branch summary

~ubuntu-branches/ubuntu/trusty/cloog/trusty

« back to all changes in this revision

Viewing changes to isl/isl_tab_pip.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-10-17 15:54:24 UTC
  • mfrom: (3.1.5 sid)
  • Revision ID: package-import@ubuntu.com-20131017155424-3q1gw7yhddylfkpj
Tags: 0.18.1-1
http://bugs.debian.org/711681
http://bugs.debian.org/719957
* New upstream version.
* Add a comment to build-depend on libpod-latex-perl | perl (<< 5.17.0),
  when the documentation is built. Closes: #711681.
* Use dh_autotools-dev to update config.{sub,guess}. Closes: #719957.

Show diffs side-by-side

added added

removed removed

Lines of Context:
isl/isl_tab_pip.c
119
119
        struct isl_tab *tab;
120
120
};
121
121
 
 
122
/* A stack (linked list) of solutions of subtrees of the search space.
 
123
 *
 
124
 * "M" describes the solution in terms of the dimensions of "dom".
 
125
 * The number of columns of "M" is one more than the total number
 
126
 * of dimensions of "dom".
 
127
 *
 
128
 * If "M" is NULL, then there is no solution on "dom".
 
129
 */
122
130
struct isl_partial_sol {
123
131
        int level;
124
132
        struct isl_basic_set *dom;
307
315
                        sol_pop_one(sol);
308
316
                } else {
309
317
                        struct isl_basic_set *bset;
 
318
                        isl_mat *M;
 
319
                        unsigned n;
310
320
 
 
321
                        n = isl_basic_set_dim(partial->next->dom, isl_dim_div);
 
322
                        n -= n_div;
311
323
                        bset = sol_domain(sol);
312
 
                        if (!bset)
313
 
                                goto error;
314
 
 
315
324
                        isl_basic_set_free(partial->next->dom);
316
325
                        partial->next->dom = bset;
 
326
                        M = partial->next->M;
 
327
                        if (M) {
 
328
                                M = isl_mat_drop_cols(M, M->n_col - n, n);
 
329
                                partial->next->M = M;
 
330
                                if (!M)
 
331
                                        goto error;
 
332
                        }
317
333
                        partial->next->level = sol->level;
318
334
 
 
335
                        if (!bset)
 
336
                                goto error;
 
337
 
319
338
                        sol->partial = partial->next;
320
339
                        isl_basic_set_free(partial->dom);
321
340
                        isl_mat_free(partial->M);
2068
2087
                tab->n_div = dom->n_div;
2069
2088
                tab->row_sign = isl_calloc_array(bmap->ctx,
2070
2089
                                        enum isl_tab_row_sign, tab->mat->n_row);
2071
 
                if (!tab->row_sign)
 
2090
                if (tab->mat->n_row && !tab->row_sign)
2072
2091
                        goto error;
2073
2092
        }
2074
2093
        if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)) {
2597
2616
        return NULL;
2598
2617
}
2599
2618
 
 
2619
/* Representation of the context when using generalized basis reduction.
 
2620
 *
 
2621
 * "shifted" contains the offsets of the unit hypercubes that lie inside the
 
2622
 * context.  Any rational point in "shifted" can therefore be rounded
 
2623
 * up to an integer point in the context.
 
2624
 * If the context is constrained by any equality, then "shifted" is not used
 
2625
 * as it would be empty.
 
2626
 */
2600
2627
struct isl_context_gbr {
2601
2628
        struct isl_context context;
2602
2629
        struct isl_tab *tab;
2702
2729
 
2703
2730
static int use_shifted(struct isl_context_gbr *cgbr)
2704
2731
{
 
2732
        if (!cgbr->tab)
 
2733
                return 0;
2705
2734
        return cgbr->tab->bmap->n_eq == 0 && cgbr->tab->bmap->n_div == 0;
2706
2735
}
2707
2736
 
2820
2849
        return NULL;
2821
2850
}
2822
2851
 
 
2852
/* Add the equality described by "eq" to the context.
 
2853
 * If "check" is set, then we check if the context is empty after
 
2854
 * adding the equality.
 
2855
 * If "update" is set, then we check if the samples are still valid.
 
2856
 *
 
2857
 * We do not explicitly add shifted copies of the equality to
 
2858
 * cgbr->shifted since they would conflict with each other.
 
2859
 * Instead, we directly mark cgbr->shifted empty.
 
2860
 */
2823
2861
static void context_gbr_add_eq(struct isl_context *context, isl_int *eq,
2824
2862
                int check, int update)
2825
2863
{
2827
2865
 
2828
2866
        cgbr->tab = add_gbr_eq(cgbr->tab, eq);
2829
2867
 
 
2868
        if (cgbr->shifted && !cgbr->shifted->empty && use_shifted(cgbr)) {
 
2869
                if (isl_tab_mark_empty(cgbr->shifted) < 0)
 
2870
                        goto error;
 
2871
        }
 
2872
 
2830
2873
        if (cgbr->cone && cgbr->cone->n_col != cgbr->cone->n_dead) {
2831
2874
                if (isl_tab_extend_cons(cgbr->cone, 2) < 0)
2832
2875
                        goto error;
3100
3143
 
3101
3144
        n_ineq = cgbr->tab->bmap->n_ineq;
3102
3145
        cgbr->tab = isl_tab_detect_equalities(cgbr->tab, cgbr->cone);
3103
 
        if (cgbr->tab && cgbr->tab->bmap->n_ineq > n_ineq)
 
3146
        if (!cgbr->tab)
 
3147
                return -1;
 
3148
        if (cgbr->tab->bmap->n_ineq > n_ineq)
3104
3149
                propagate_equalities(cgbr, tab, n_ineq);
3105
3150
 
3106
3151
        return 0;
3177
3222
        struct isl_context_gbr *cgbr = (struct isl_context_gbr *)context;
3178
3223
        struct isl_gbr_tab_undo *snap;
3179
3224
 
 
3225
        if (!cgbr->tab)
 
3226
                return NULL;
 
3227
 
3180
3228
        snap = isl_alloc_type(cgbr->tab->mat->ctx, struct isl_gbr_tab_undo);
3181
3229
        if (!snap)
3182
3230
                return NULL;
3833
3881
        sol->error = 1;
3834
3882
}
3835
3883
 
 
3884
/* Does "sol" contain a pair of partial solutions that could potentially
 
3885
 * be merged?
 
3886
 *
 
3887
 * We currently only check that "sol" is not in an error state
 
3888
 * and that there are at least two partial solutions of which the final two
 
3889
 * are defined at the same level.
 
3890
 */
 
3891
static int sol_has_mergeable_solutions(struct isl_sol *sol)
 
3892
{
 
3893
        if (sol->error)
 
3894
                return 0;
 
3895
        if (!sol->partial)
 
3896
                return 0;
 
3897
        if (!sol->partial->next)
 
3898
                return 0;
 
3899
        return sol->partial->level == sol->partial->next->level;
 
3900
}
 
3901
 
3836
3902
/* Compute the lexicographic minimum of the set represented by the main
3837
3903
 * tableau "tab" within the context "sol->context_tab".
3838
3904
 *
3843
3909
 * corresponding rows may not be marked as being non-negative.
3844
3910
 * In parts of the context where the added equality does not hold,
3845
3911
 * the main tableau is marked as being empty.
 
3912
 *
 
3913
 * Before we embark on the actual computation, we save a copy
 
3914
 * of the context.  When we return, we check if there are any
 
3915
 * partial solutions that can potentially be merged.  If so,
 
3916
 * we perform a rollback to the initial state of the context.
 
3917
 * The merging of partial solutions happens inside calls to
 
3918
 * sol_dec_level that are pushed onto the undo stack of the context.
 
3919
 * If there are no partial solutions that can potentially be merged
 
3920
 * then the rollback is skipped as it would just be wasted effort.
3846
3921
 */
3847
3922
static void find_solutions_main(struct isl_sol *sol, struct isl_tab *tab)
3848
3923
{
3849
3924
        int row;
 
3925
        void *saved;
3850
3926
 
3851
3927
        if (!tab)
3852
3928
                goto error;
3896
3972
                row = tab->n_redundant - 1;
3897
3973
        }
3898
3974
 
 
3975
        saved = sol->context->op->save(sol->context);
 
3976
 
3899
3977
        find_solutions(sol, tab);
3900
3978
 
 
3979
        if (sol_has_mergeable_solutions(sol))
 
3980
                sol->context->op->restore(sol->context, saved);
 
3981
        else
 
3982
                sol->context->op->discard(saved);
 
3983
 
3901
3984
        sol->level = 0;
3902
3985
        sol_pop(sol);
3903
3986
 
4506
4589
        ctx = isl_basic_map_get_ctx(bmap);
4507
4590
        list = isl_alloc_array(ctx, int, bmap->n_ineq);
4508
4591
        var = isl_vec_alloc(ctx, n_out);
4509
 
        if (!list || !var)
 
4592
        if ((bmap->n_ineq && !list) || (n_out && !var))
4510
4593
                goto error;
4511
4594
 
4512
4595
        list[0] = first;
5010
5093
 
5011
5094
        v = isl_vec_alloc(ctx, 1 + tab->n_var);
5012
5095
        triv = isl_calloc_array(ctx, struct isl_trivial, n_region);
5013
 
        if (!v || !triv)
 
5096
        if (!v || (n_region && !triv))
5014
5097
                goto error;
5015
5098
 
5016
5099
        level = 0;