WebSVN – nexmon – Blame – Rev 1 – /buildtools/isl-0.10/isl

1

office

1

/*

2

3

*

4

* Use of this software is governed by the GNU LGPLv2.1 license

5

*

6

* Written by Sven Verdoolaege, K.U.Leuven, Departement

7

* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium

8

*/

9

10

#include <assert.h>

11

#include <stdio.h>

12

#include <limits.h>

13

#include <isl_ctx_private.h>

14

#include <isl_map_private.h>

15

#include <isl/aff.h>

16

#include <isl/set.h>

17

#include <isl/flow.h>

18

#include <isl/constraint.h>

19

#include <isl/polynomial.h>

20

#include <isl/union_map.h>

21

#include <isl_factorization.h>

22

#include <isl/schedule.h>

23

#include <isl_options_private.h>

24

#include <isl/vertices.h>

25

26

#define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))

27

28

static char *srcdir;

29

30

static char *get_filename(isl_ctx *ctx, const char *name, const char *suffix) {

31

char *filename;

32

int length;

33

char *pattern = "%s/test_inputs/%s.%s";

34

35

length = strlen(pattern) - 6 + strlen(srcdir) + strlen(name)

36

+ strlen(suffix) + 1;

37

filename = isl_alloc_array(ctx, char, length);

if (!filename)

return NULL;

sprintf(filename, pattern, srcdir, name, suffix);

return filename;

}

void test_parse_map(isl_ctx *ctx, const char *str)

{

isl_map *map;

map = isl_map_read_from_str(ctx, str);

assert(map);

isl_map_free(map);

}

int test_parse_map_equal(isl_ctx *ctx, const char *str, const char *str2)

57

{

58

isl_map *map, *map2;

59

int equal;

60

61

map = isl_map_read_from_str(ctx, str);

62

map2 = isl_map_read_from_str(ctx, str2);

63

equal = isl_map_is_equal(map, map2);

64

isl_map_free(map);

65

isl_map_free(map2);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "maps not equal",

return -1);

return 0;

}

void test_parse_pwqp(isl_ctx *ctx, const char *str)

77

{

78

isl_pw_qpolynomial *pwqp;

79

80

pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);

81

assert(pwqp);

82

isl_pw_qpolynomial_free(pwqp);

83

}

84

85

static void test_parse_pwaff(isl_ctx *ctx, const char *str)

{

isl_pw_aff *pwaff;

pwaff = isl_pw_aff_read_from_str(ctx, str);

90

assert(pwaff);

91

isl_pw_aff_free(pwaff);

92

}

93

94

int test_parse(struct isl_ctx *ctx)

95

{

96

isl_map *map, *map2;

97

const char *str, *str2;

98

99

str = "{ [i] -> [-i] }";

100

map = isl_map_read_from_str(ctx, str);

assert(map);

isl_map_free(map);

str = "{ A[i] -> L[([i/3])] }";

105

map = isl_map_read_from_str(ctx, str);

assert(map);

isl_map_free(map);

test_parse_map(ctx, "{[[s] -> A[i]] -> [[s+1] -> A[i]]}");

110

test_parse_map(ctx, "{ [p1, y1, y2] -> [2, y1, y2] : "

111

"p1 = 1 && (y1 <= y2 || y2 = 0) }");

112

113

str = "{ [x,y] : [([x/2]+y)/3] >= 1 }";

114

str2 = "{ [x, y] : 2y >= 6 - x }";

115

if (test_parse_map_equal(ctx, str, str2) < 0)

116

return -1;

117

118

if (test_parse_map_equal(ctx, "{ [x,y] : x <= min(y, 2*y+3) }",

119

"{ [x,y] : x <= y, 2*y + 3 }") < 0)

120

return -1;

121

str = "{ [x, y] : (y <= x and y >= -3) or (2y <= -3 + x and y <= -4) }";

122

if (test_parse_map_equal(ctx, "{ [x,y] : x >= min(y, 2*y+3) }",

str) < 0)

return -1;

str = "{[new,old] -> [new+1-2*[(new+1)/2],old+1-2*[(old+1)/2]]}";

127

map = isl_map_read_from_str(ctx, str);

128

str = "{ [new, old] -> [o0, o1] : "

129

"exists (e0 = [(-1 - new + o0)/2], e1 = [(-1 - old + o1)/2]: "

130

"2e0 = -1 - new + o0 and 2e1 = -1 - old + o1 and o0 >= 0 and "

131

"o0 <= 1 and o1 >= 0 and o1 <= 1) }";

132

map2 = isl_map_read_from_str(ctx, str);

133

assert(isl_map_is_equal(map, map2));

134

isl_map_free(map);

135

isl_map_free(map2);

136

137

str = "{[new,old] -> [new+1-2*[(new+1)/2],old+1-2*[(old+1)/2]]}";

138

map = isl_map_read_from_str(ctx, str);

139

str = "{[new,old] -> [(new+1)%2,(old+1)%2]}";

140

map2 = isl_map_read_from_str(ctx, str);

141

assert(isl_map_is_equal(map, map2));

142

isl_map_free(map);

143

isl_map_free(map2);

144

145

str = "[n] -> { [c1] : c1>=0 and c1<=floord(n-4,3) }";

146

str2 = "[n] -> { [c1] : c1 >= 0 and 3c1 <= -4 + n }";

147

if (test_parse_map_equal(ctx, str, str2) < 0)

148

return -1;

149

150

str = "{ [i,j] -> [i] : i < j; [i,j] -> [j] : j <= i }";

151

str2 = "{ [i,j] -> [min(i,j)] }";

152

if (test_parse_map_equal(ctx, str, str2) < 0)

153

return -1;

154

155

str = "{ [i,j] : i != j }";

156

str2 = "{ [i,j] : i < j or i > j }";

157

if (test_parse_map_equal(ctx, str, str2) < 0)

158

return -1;

159

160

str = "{ [i,j] : (i+1)*2 >= j }";

161

str2 = "{ [i, j] : j <= 2 + 2i }";

162

if (test_parse_map_equal(ctx, str, str2) < 0)

163

return -1;

164

165

str = "{ [i] -> [i > 0 ? 4 : 5] }";

166

str2 = "{ [i] -> [5] : i <= 0; [i] -> [4] : i >= 1 }";

167

if (test_parse_map_equal(ctx, str, str2) < 0)

168

return -1;

169

170

str = "[N=2,M] -> { [i=[(M+N)/4]] }";

171

str2 = "[N, M] -> { [i] : N = 2 and 4i <= 2 + M and 4i >= -1 + M }";

172

if (test_parse_map_equal(ctx, str, str2) < 0)

173

return -1;

174

175

str = "{ [x] : x >= 0 }";

176

str2 = "{ [x] : x-0 >= 0 }";

177

if (test_parse_map_equal(ctx, str, str2) < 0)

178

return -1;

179

180

str = "{ [i] : ((i > 10)) }";

181

str2 = "{ [i] : i >= 11 }";

182

if (test_parse_map_equal(ctx, str, str2) < 0)

183

return -1;

184

185

str = "{ [i] -> [0] }";

186

str2 = "{ [i] -> [0 * i] }";

187

if (test_parse_map_equal(ctx, str, str2) < 0)

188

return -1;

189

190

test_parse_pwqp(ctx, "{ [i] -> i + [ (i + [i/3])/2 ] }");

191

test_parse_map(ctx, "{ S1[i] -> [([i/10]),i%10] : 0 <= i <= 45 }");

192

test_parse_pwaff(ctx, "{ [i] -> [i + 1] : i > 0; [a] -> [a] : a < 0 }");

193

test_parse_pwqp(ctx, "{ [x] -> ([(x)/2] * [(x)/3]) }");

194

195

if (test_parse_map_equal(ctx, "{ [a] -> [b] : (not false) }",

196

"{ [a] -> [b] : true }") < 0)

return -1;

return 0;

}

void test_read(struct isl_ctx *ctx)

{

char *filename;

FILE *input;

struct isl_basic_set *bset1, *bset2;

207

const char *str = "{[y]: Exists ( alpha : 2alpha = y)}";

208

209

filename = get_filename(ctx, "set", "omega");

210

assert(filename);

211

input = fopen(filename, "r");

212

assert(input);

213

214

bset1 = isl_basic_set_read_from_file(ctx, input);

215

bset2 = isl_basic_set_read_from_str(ctx, str);

216

217

assert(isl_basic_set_is_equal(bset1, bset2) == 1);

218

219

isl_basic_set_free(bset1);

220

isl_basic_set_free(bset2);

free(filename);

fclose(input);

}

void test_bounded(struct isl_ctx *ctx)

{

isl_set *set;

int bounded;

set = isl_set_read_from_str(ctx, "[n] -> {[i] : 0 <= i <= n }");

232

bounded = isl_set_is_bounded(set);

assert(bounded);

isl_set_free(set);

set = isl_set_read_from_str(ctx, "{[n, i] : 0 <= i <= n }");

237

bounded = isl_set_is_bounded(set);

assert(!bounded);

isl_set_free(set);

set = isl_set_read_from_str(ctx, "[n] -> {[i] : i <= n }");

242

bounded = isl_set_is_bounded(set);

assert(!bounded);

isl_set_free(set);

}

/* Construct the basic set { [i] : 5 <= i <= N } */

248

void test_construction(struct isl_ctx *ctx)

{

isl_int v;

isl_space *dim;

isl_local_space *ls;

253

struct isl_basic_set *bset;

254

struct isl_constraint *c;

isl_int_init(v);

dim = isl_space_set_alloc(ctx, 1, 1);

259

bset = isl_basic_set_universe(isl_space_copy(dim));

260

ls = isl_local_space_from_space(dim);

261

262

c = isl_inequality_alloc(isl_local_space_copy(ls));

263

isl_int_set_si(v, -1);

264

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

265

isl_int_set_si(v, 1);

266

isl_constraint_set_coefficient(c, isl_dim_param, 0, v);

267

bset = isl_basic_set_add_constraint(bset, c);

268

269

c = isl_inequality_alloc(isl_local_space_copy(ls));

270

isl_int_set_si(v, 1);

271

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

272

isl_int_set_si(v, -5);

273

isl_constraint_set_constant(c, v);

274

bset = isl_basic_set_add_constraint(bset, c);

275

276

isl_local_space_free(ls);

277

isl_basic_set_free(bset);

isl_int_clear(v);

}

void test_dim(struct isl_ctx *ctx)

283

{

284

const char *str;

285

isl_map *map1, *map2;

286

287

map1 = isl_map_read_from_str(ctx,

288

"[n] -> { [i] -> [j] : exists (a = [i/10] : i - 10a <= n ) }");

289

map1 = isl_map_add_dims(map1, isl_dim_in, 1);

290

map2 = isl_map_read_from_str(ctx,

291

"[n] -> { [i,k] -> [j] : exists (a = [i/10] : i - 10a <= n ) }");

292

assert(isl_map_is_equal(map1, map2));

293

isl_map_free(map2);

294

295

map1 = isl_map_project_out(map1, isl_dim_in, 0, 1);

296

map2 = isl_map_read_from_str(ctx, "[n] -> { [i] -> [j] : n >= 0 }");

297

assert(isl_map_is_equal(map1, map2));

298

299

isl_map_free(map1);

300

isl_map_free(map2);

301

302

str = "[n] -> { [i] -> [] : exists a : 0 <= i <= n and i = 2 a }";

303

map1 = isl_map_read_from_str(ctx, str);

304

str = "{ [i] -> [j] : exists a : 0 <= i <= j and i = 2 a }";

305

map2 = isl_map_read_from_str(ctx, str);

306

map1 = isl_map_move_dims(map1, isl_dim_out, 0, isl_dim_param, 0, 1);

307

assert(isl_map_is_equal(map1, map2));

308

309

isl_map_free(map1);

310

isl_map_free(map2);

311

}

312

313

void test_div(struct isl_ctx *ctx)

{

isl_int v;

isl_space *dim;

isl_local_space *ls;

318

struct isl_basic_set *bset;

319

struct isl_constraint *c;

isl_int_init(v);

/* test 1 */

dim = isl_space_set_alloc(ctx, 0, 3);

325

bset = isl_basic_set_universe(isl_space_copy(dim));

326

ls = isl_local_space_from_space(dim);

327

328

c = isl_equality_alloc(isl_local_space_copy(ls));

329

isl_int_set_si(v, -1);

330

isl_constraint_set_constant(c, v);

331

isl_int_set_si(v, 1);

332

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

333

isl_int_set_si(v, 3);

334

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

335

bset = isl_basic_set_add_constraint(bset, c);

336

337

c = isl_equality_alloc(isl_local_space_copy(ls));

338

isl_int_set_si(v, 1);

339

isl_constraint_set_constant(c, v);

340

isl_int_set_si(v, -1);

341

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

342

isl_int_set_si(v, 3);

343

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

344

bset = isl_basic_set_add_constraint(bset, c);

345

346

bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);

347

348

assert(bset && bset->n_div == 1);

349

isl_local_space_free(ls);

350

isl_basic_set_free(bset);

351

352

/* test 2 */

353

dim = isl_space_set_alloc(ctx, 0, 3);

354

bset = isl_basic_set_universe(isl_space_copy(dim));

355

ls = isl_local_space_from_space(dim);

356

357

c = isl_equality_alloc(isl_local_space_copy(ls));

358

isl_int_set_si(v, 1);

359

isl_constraint_set_constant(c, v);

360

isl_int_set_si(v, -1);

361

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

362

isl_int_set_si(v, 3);

363

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

364

bset = isl_basic_set_add_constraint(bset, c);

365

366

c = isl_equality_alloc(isl_local_space_copy(ls));

367

isl_int_set_si(v, -1);

368

isl_constraint_set_constant(c, v);

369

isl_int_set_si(v, 1);

370

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

371

isl_int_set_si(v, 3);

372

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

373

bset = isl_basic_set_add_constraint(bset, c);

374

375

bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);

376

377

assert(bset && bset->n_div == 1);

378

isl_local_space_free(ls);

379

isl_basic_set_free(bset);

380

381

/* test 3 */

382

dim = isl_space_set_alloc(ctx, 0, 3);

383

bset = isl_basic_set_universe(isl_space_copy(dim));

384

ls = isl_local_space_from_space(dim);

385

386

c = isl_equality_alloc(isl_local_space_copy(ls));

387

isl_int_set_si(v, 1);

388

isl_constraint_set_constant(c, v);

389

isl_int_set_si(v, -1);

390

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

391

isl_int_set_si(v, 3);

392

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

393

bset = isl_basic_set_add_constraint(bset, c);

394

395

c = isl_equality_alloc(isl_local_space_copy(ls));

396

isl_int_set_si(v, -3);

397

isl_constraint_set_constant(c, v);

398

isl_int_set_si(v, 1);

399

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

400

isl_int_set_si(v, 4);

401

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

402

bset = isl_basic_set_add_constraint(bset, c);

403

404

bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);

405

406

assert(bset && bset->n_div == 1);

407

isl_local_space_free(ls);

408

isl_basic_set_free(bset);

409

410

/* test 4 */

411

dim = isl_space_set_alloc(ctx, 0, 3);

412

bset = isl_basic_set_universe(isl_space_copy(dim));

413

ls = isl_local_space_from_space(dim);

414

415

c = isl_equality_alloc(isl_local_space_copy(ls));

416

isl_int_set_si(v, 2);

417

isl_constraint_set_constant(c, v);

418

isl_int_set_si(v, -1);

419

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

420

isl_int_set_si(v, 3);

421

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

422

bset = isl_basic_set_add_constraint(bset, c);

423

424

c = isl_equality_alloc(isl_local_space_copy(ls));

425

isl_int_set_si(v, -1);

426

isl_constraint_set_constant(c, v);

427

isl_int_set_si(v, 1);

428

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

429

isl_int_set_si(v, 6);

430

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

431

bset = isl_basic_set_add_constraint(bset, c);

432

433

bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 2);

434

435

assert(isl_basic_set_is_empty(bset));

436

isl_local_space_free(ls);

437

isl_basic_set_free(bset);

438

439

/* test 5 */

440

dim = isl_space_set_alloc(ctx, 0, 3);

441

bset = isl_basic_set_universe(isl_space_copy(dim));

442

ls = isl_local_space_from_space(dim);

443

444

c = isl_equality_alloc(isl_local_space_copy(ls));

445

isl_int_set_si(v, -1);

446

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

447

isl_int_set_si(v, 3);

448

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

449

bset = isl_basic_set_add_constraint(bset, c);

450

451

c = isl_equality_alloc(isl_local_space_copy(ls));

452

isl_int_set_si(v, 1);

453

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

454

isl_int_set_si(v, -3);

455

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

456

bset = isl_basic_set_add_constraint(bset, c);

457

458

bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 1);

459

460

assert(bset && bset->n_div == 0);

461

isl_basic_set_free(bset);

462

isl_local_space_free(ls);

463

464

/* test 6 */

465

dim = isl_space_set_alloc(ctx, 0, 3);

466

bset = isl_basic_set_universe(isl_space_copy(dim));

467

ls = isl_local_space_from_space(dim);

468

469

c = isl_equality_alloc(isl_local_space_copy(ls));

470

isl_int_set_si(v, -1);

471

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

472

isl_int_set_si(v, 6);

473

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

474

bset = isl_basic_set_add_constraint(bset, c);

475

476

c = isl_equality_alloc(isl_local_space_copy(ls));

477

isl_int_set_si(v, 1);

478

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

479

isl_int_set_si(v, -3);

480

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

481

bset = isl_basic_set_add_constraint(bset, c);

482

483

bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 1);

484

485

assert(bset && bset->n_div == 1);

486

isl_basic_set_free(bset);

487

isl_local_space_free(ls);

488

489

/* test 7 */

490

/* This test is a bit tricky. We set up an equality

491

* a + 3b + 3c = 6 e0

492

* Normalization of divs creates _two_ divs

493

* a = 3 e0

494

* c - b - e0 = 2 e1

495

* Afterwards e0 is removed again because it has coefficient -1

496

* and we end up with the original equality and div again.

497

* Perhaps we can avoid the introduction of this temporary div.

498

*/

499

dim = isl_space_set_alloc(ctx, 0, 4);

500

bset = isl_basic_set_universe(isl_space_copy(dim));

501

ls = isl_local_space_from_space(dim);

502

503

c = isl_equality_alloc(isl_local_space_copy(ls));

504

isl_int_set_si(v, -1);

505

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

506

isl_int_set_si(v, -3);

507

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

508

isl_int_set_si(v, -3);

509

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

510

isl_int_set_si(v, 6);

511

isl_constraint_set_coefficient(c, isl_dim_set, 3, v);

512

bset = isl_basic_set_add_constraint(bset, c);

513

514

bset = isl_basic_set_project_out(bset, isl_dim_set, 3, 1);

515

516

/* Test disabled for now */

517

/*

518

assert(bset && bset->n_div == 1);

519

*/

520

isl_local_space_free(ls);

521

isl_basic_set_free(bset);

522

523

/* test 8 */

524

dim = isl_space_set_alloc(ctx, 0, 5);

525

bset = isl_basic_set_universe(isl_space_copy(dim));

526

ls = isl_local_space_from_space(dim);

527

528

c = isl_equality_alloc(isl_local_space_copy(ls));

529

isl_int_set_si(v, -1);

530

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

531

isl_int_set_si(v, -3);

532

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

533

isl_int_set_si(v, -3);

534

isl_constraint_set_coefficient(c, isl_dim_set, 3, v);

535

isl_int_set_si(v, 6);

536

isl_constraint_set_coefficient(c, isl_dim_set, 4, v);

537

bset = isl_basic_set_add_constraint(bset, c);

538

539

c = isl_equality_alloc(isl_local_space_copy(ls));

540

isl_int_set_si(v, -1);

541

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

542

isl_int_set_si(v, 1);

543

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

544

isl_int_set_si(v, 1);

545

isl_constraint_set_constant(c, v);

546

bset = isl_basic_set_add_constraint(bset, c);

547

548

bset = isl_basic_set_project_out(bset, isl_dim_set, 4, 1);

549

550

/* Test disabled for now */

551

/*

552

assert(bset && bset->n_div == 1);

553

*/

554

isl_local_space_free(ls);

555

isl_basic_set_free(bset);

556

557

/* test 9 */

558

dim = isl_space_set_alloc(ctx, 0, 4);

559

bset = isl_basic_set_universe(isl_space_copy(dim));

560

ls = isl_local_space_from_space(dim);

561

562

c = isl_equality_alloc(isl_local_space_copy(ls));

563

isl_int_set_si(v, 1);

564

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

565

isl_int_set_si(v, -1);

566

isl_constraint_set_coefficient(c, isl_dim_set, 1, v);

567

isl_int_set_si(v, -2);

568

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

569

bset = isl_basic_set_add_constraint(bset, c);

570

571

c = isl_equality_alloc(isl_local_space_copy(ls));

572

isl_int_set_si(v, -1);

573

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

574

isl_int_set_si(v, 3);

575

isl_constraint_set_coefficient(c, isl_dim_set, 3, v);

576

isl_int_set_si(v, 2);

577

isl_constraint_set_constant(c, v);

578

bset = isl_basic_set_add_constraint(bset, c);

579

580

bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 2);

581

582

bset = isl_basic_set_fix_si(bset, isl_dim_set, 0, 2);

583

584

assert(!isl_basic_set_is_empty(bset));

585

586

isl_local_space_free(ls);

587

isl_basic_set_free(bset);

588

589

/* test 10 */

590

dim = isl_space_set_alloc(ctx, 0, 3);

591

bset = isl_basic_set_universe(isl_space_copy(dim));

592

ls = isl_local_space_from_space(dim);

593

594

c = isl_equality_alloc(isl_local_space_copy(ls));

595

isl_int_set_si(v, 1);

596

isl_constraint_set_coefficient(c, isl_dim_set, 0, v);

597

isl_int_set_si(v, -2);

598

isl_constraint_set_coefficient(c, isl_dim_set, 2, v);

599

bset = isl_basic_set_add_constraint(bset, c);

600

601

bset = isl_basic_set_project_out(bset, isl_dim_set, 2, 1);

602

603

bset = isl_basic_set_fix_si(bset, isl_dim_set, 0, 2);

604

605

isl_local_space_free(ls);

606

isl_basic_set_free(bset);

isl_int_clear(v);

}

void test_application_case(struct isl_ctx *ctx, const char *name)

{

char *filename;

FILE *input;

struct isl_basic_set *bset1, *bset2;

616

struct isl_basic_map *bmap;

617

618

filename = get_filename(ctx, name, "omega");

619

assert(filename);

620

input = fopen(filename, "r");

621

assert(input);

622

623

bset1 = isl_basic_set_read_from_file(ctx, input);

624

bmap = isl_basic_map_read_from_file(ctx, input);

625

626

bset1 = isl_basic_set_apply(bset1, bmap);

627

628

bset2 = isl_basic_set_read_from_file(ctx, input);

629

630

assert(isl_basic_set_is_equal(bset1, bset2) == 1);

631

632

isl_basic_set_free(bset1);

633

isl_basic_set_free(bset2);

free(filename);

fclose(input);

}

void test_application(struct isl_ctx *ctx)

640

{

641

test_application_case(ctx, "application");

642

test_application_case(ctx, "application2");

643

}

644

645

void test_affine_hull_case(struct isl_ctx *ctx, const char *name)

{

char *filename;

FILE *input;

struct isl_basic_set *bset1, *bset2;

650

651

filename = get_filename(ctx, name, "polylib");

652

assert(filename);

653

input = fopen(filename, "r");

654

assert(input);

655

656

bset1 = isl_basic_set_read_from_file(ctx, input);

657

bset2 = isl_basic_set_read_from_file(ctx, input);

658

659

bset1 = isl_basic_set_affine_hull(bset1);

660

661

assert(isl_basic_set_is_equal(bset1, bset2) == 1);

662

663

isl_basic_set_free(bset1);

664

isl_basic_set_free(bset2);

free(filename);

fclose(input);

}

int test_affine_hull(struct isl_ctx *ctx)

{

const char *str;

isl_set *set;

isl_basic_set *bset;

675

int n;

676

677

test_affine_hull_case(ctx, "affine2");

678

test_affine_hull_case(ctx, "affine");

679

test_affine_hull_case(ctx, "affine3");

680

681

str = "[m] -> { [i0] : exists (e0, e1: e1 <= 1 + i0 and "

682

"m >= 3 and 4i0 <= 2 + m and e1 >= i0 and "

683

"e1 >= 0 and e1 <= 2 and e1 >= 1 + 2e0 and "

684

"2e1 <= 1 + m + 4e0 and 2e1 >= 2 - m + 4i0 - 4e0) }";

685

set = isl_set_read_from_str(ctx, str);

686

bset = isl_set_affine_hull(set);

687

n = isl_basic_set_dim(bset, isl_dim_div);

688

isl_basic_set_free(bset);

689

if (n != 0)

690

isl_die(ctx, isl_error_unknown, "not expecting any divs",

return -1);

return 0;

}

void test_convex_hull_case(struct isl_ctx *ctx, const char *name)

{

char *filename;

FILE *input;

struct isl_basic_set *bset1, *bset2;

701

struct isl_set *set;

702

703

filename = get_filename(ctx, name, "polylib");

704

assert(filename);

705

input = fopen(filename, "r");

706

assert(input);

707

708

bset1 = isl_basic_set_read_from_file(ctx, input);

709

bset2 = isl_basic_set_read_from_file(ctx, input);

710

711

set = isl_basic_set_union(bset1, bset2);

712

bset1 = isl_set_convex_hull(set);

713

714

bset2 = isl_basic_set_read_from_file(ctx, input);

715

716

assert(isl_basic_set_is_equal(bset1, bset2) == 1);

717

718

isl_basic_set_free(bset1);

719

isl_basic_set_free(bset2);

free(filename);

fclose(input);

}

void test_convex_hull_algo(struct isl_ctx *ctx, int convex)

726

{

727

const char *str1, *str2;

728

isl_set *set1, *set2;

729

int orig_convex = ctx->opt->convex;

730

ctx->opt->convex = convex;

731

732

test_convex_hull_case(ctx, "convex0");

733

test_convex_hull_case(ctx, "convex1");

734

test_convex_hull_case(ctx, "convex2");

735

test_convex_hull_case(ctx, "convex3");

736

test_convex_hull_case(ctx, "convex4");

737

test_convex_hull_case(ctx, "convex5");

738

test_convex_hull_case(ctx, "convex6");

739

test_convex_hull_case(ctx, "convex7");

740

test_convex_hull_case(ctx, "convex8");

741

test_convex_hull_case(ctx, "convex9");

742

test_convex_hull_case(ctx, "convex10");

743

test_convex_hull_case(ctx, "convex11");

744

test_convex_hull_case(ctx, "convex12");

745

test_convex_hull_case(ctx, "convex13");

746

test_convex_hull_case(ctx, "convex14");

747

test_convex_hull_case(ctx, "convex15");

748

749

str1 = "{ [i0, i1, i2] : (i2 = 1 and i0 = 0 and i1 >= 0) or "

750

"(i0 = 1 and i1 = 0 and i2 = 1) or "

751

"(i0 = 0 and i1 = 0 and i2 = 0) }";

752

str2 = "{ [i0, i1, i2] : i0 >= 0 and i2 >= i0 and i2 <= 1 and i1 >= 0 }";

753

set1 = isl_set_read_from_str(ctx, str1);

754

set2 = isl_set_read_from_str(ctx, str2);

755

set1 = isl_set_from_basic_set(isl_set_convex_hull(set1));

756

assert(isl_set_is_equal(set1, set2));

757

isl_set_free(set1);

758

isl_set_free(set2);

759

760

ctx->opt->convex = orig_convex;

761

}

762

763

void test_convex_hull(struct isl_ctx *ctx)

764

{

765

test_convex_hull_algo(ctx, ISL_CONVEX_HULL_FM);

766

test_convex_hull_algo(ctx, ISL_CONVEX_HULL_WRAP);

767

}

768

769

void test_gist_case(struct isl_ctx *ctx, const char *name)

{

char *filename;

FILE *input;

struct isl_basic_set *bset1, *bset2;

774

775

filename = get_filename(ctx, name, "polylib");

776

assert(filename);

777

input = fopen(filename, "r");

778

assert(input);

779

780

bset1 = isl_basic_set_read_from_file(ctx, input);

781

bset2 = isl_basic_set_read_from_file(ctx, input);

782

783

bset1 = isl_basic_set_gist(bset1, bset2);

784

785

bset2 = isl_basic_set_read_from_file(ctx, input);

786

787

assert(isl_basic_set_is_equal(bset1, bset2) == 1);

788

789

isl_basic_set_free(bset1);

790

isl_basic_set_free(bset2);

free(filename);

fclose(input);

}

void test_gist(struct isl_ctx *ctx)

797

{

798

const char *str;

799

isl_basic_set *bset1, *bset2;

800

801

test_gist_case(ctx, "gist1");

802

803

str = "[p0, p2, p3, p5, p6, p10] -> { [] : "

804

"exists (e0 = [(15 + p0 + 15p6 + 15p10)/16], e1 = [(p5)/8], "

805

"e2 = [(p6)/128], e3 = [(8p2 - p5)/128], "

806

"e4 = [(128p3 - p6)/4096]: 8e1 = p5 and 128e2 = p6 and "

807

"128e3 = 8p2 - p5 and 4096e4 = 128p3 - p6 and p2 >= 0 and "

808

"16e0 >= 16 + 16p6 + 15p10 and p2 <= 15 and p3 >= 0 and "

809

"p3 <= 31 and p6 >= 128p3 and p5 >= 8p2 and p10 >= 0 and "

810

"16e0 <= 15 + p0 + 15p6 + 15p10 and 16e0 >= p0 + 15p6 + 15p10 and "

811

"p10 <= 15 and p10 <= -1 + p0 - p6) }";

812

bset1 = isl_basic_set_read_from_str(ctx, str);

813

str = "[p0, p2, p3, p5, p6, p10] -> { [] : exists (e0 = [(p5)/8], "

814

"e1 = [(p6)/128], e2 = [(8p2 - p5)/128], "

815

"e3 = [(128p3 - p6)/4096]: 8e0 = p5 and 128e1 = p6 and "

816

"128e2 = 8p2 - p5 and 4096e3 = 128p3 - p6 and p5 >= -7 and "

817

"p2 >= 0 and 8p2 <= -1 + p0 and p2 <= 15 and p3 >= 0 and "

818

"p3 <= 31 and 128p3 <= -1 + p0 and p6 >= -127 and "

819

"p5 <= -1 + p0 and p6 <= -1 + p0 and p6 >= 128p3 and "

820

"p0 >= 1 and p5 >= 8p2 and p10 >= 0 and p10 <= 15 ) }";

821

bset2 = isl_basic_set_read_from_str(ctx, str);

822

bset1 = isl_basic_set_gist(bset1, bset2);

823

assert(bset1 && bset1->n_div == 0);

824

isl_basic_set_free(bset1);

825

}

826

827

int test_coalesce_set(isl_ctx *ctx, const char *str, int check_one)

828

{

829

isl_set *set, *set2;

int equal;

int one;

set = isl_set_read_from_str(ctx, str);

834

set = isl_set_coalesce(set);

835

set2 = isl_set_read_from_str(ctx, str);

836

equal = isl_set_is_equal(set, set2);

837

one = set && set->n == 1;

838

isl_set_free(set);

839

isl_set_free(set2);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown,

845

"coalesced set not equal to input", return -1);

846

if (check_one && !one)

847

isl_die(ctx, isl_error_unknown,

848

"coalesced set should not be a union", return -1);

return 0;

}

int test_coalesce_unbounded_wrapping(isl_ctx *ctx)

{

int r = 0;

int bounded;

bounded = isl_options_get_coalesce_bounded_wrapping(ctx);

859

isl_options_set_coalesce_bounded_wrapping(ctx, 0);

860

861

if (test_coalesce_set(ctx,

862

"{[x,y,z] : y + 2 >= 0 and x - y + 1 >= 0 and "

863

"-x - y + 1 >= 0 and -3 <= z <= 3;"

864

"[x,y,z] : -x+z + 20 >= 0 and -x-z + 20 >= 0 and "

865

"x-z + 20 >= 0 and x+z + 20 >= 0 and "

866

"-10 <= y <= 0}", 1) < 0)

867

goto error;

868

if (test_coalesce_set(ctx,

869

"{[x,y] : 0 <= x,y <= 10; [5,y]: 4 <=y <= 11}", 1) < 0)

870

goto error;

871

if (test_coalesce_set(ctx,

872

"{[x,0,0] : -5 <= x <= 5; [0,y,1] : -5 <= y <= 5 }", 1) < 0)

goto error;

if (0) {

error:

r = -1;

}

isl_options_set_coalesce_bounded_wrapping(ctx, bounded);

return r;

}

int test_coalesce(struct isl_ctx *ctx)

886

{

887

const char *str;

888

struct isl_set *set, *set2;

889

struct isl_map *map, *map2;

890

891

set = isl_set_read_from_str(ctx,

892

"{[x,y]: x >= 0 & x <= 10 & y >= 0 & y <= 10 or "

893

"y >= x & x >= 2 & 5 >= y }");

894

set = isl_set_coalesce(set);

895

assert(set && set->n == 1);

896

isl_set_free(set);

897

898

set = isl_set_read_from_str(ctx,

899

"{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "

900

"x + y >= 10 & y <= x & x + y <= 20 & y >= 0}");

901

set = isl_set_coalesce(set);

902

assert(set && set->n == 1);

903

isl_set_free(set);

904

905

set = isl_set_read_from_str(ctx,

906

"{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "

907

"x + y >= 10 & y <= x & x + y <= 19 & y >= 0}");

908

set = isl_set_coalesce(set);

909

assert(set && set->n == 2);

910

isl_set_free(set);

911

912

set = isl_set_read_from_str(ctx,

913

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

914

"y >= 0 & x >= 6 & x <= 10 & y <= x}");

915

set = isl_set_coalesce(set);

916

assert(set && set->n == 1);

917

isl_set_free(set);

918

919

set = isl_set_read_from_str(ctx,

920

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

921

"y >= 0 & x >= 7 & x <= 10 & y <= x}");

922

set = isl_set_coalesce(set);

923

assert(set && set->n == 2);

924

isl_set_free(set);

925

926

set = isl_set_read_from_str(ctx,

927

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

928

"y >= 0 & x >= 6 & x <= 10 & y + 1 <= x}");

929

set = isl_set_coalesce(set);

930

assert(set && set->n == 2);

931

isl_set_free(set);

932

933

set = isl_set_read_from_str(ctx,

934

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

935

"y >= 0 & x = 6 & y <= 6}");

936

set = isl_set_coalesce(set);

937

assert(set && set->n == 1);

938

isl_set_free(set);

939

940

set = isl_set_read_from_str(ctx,

941

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

942

"y >= 0 & x = 7 & y <= 6}");

943

set = isl_set_coalesce(set);

944

assert(set && set->n == 2);

945

isl_set_free(set);

946

947

set = isl_set_read_from_str(ctx,

948

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

949

"y >= 0 & x = 6 & y <= 5}");

950

set = isl_set_coalesce(set);

951

assert(set && set->n == 1);

952

set2 = isl_set_read_from_str(ctx,

953

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

954

"y >= 0 & x = 6 & y <= 5}");

955

assert(isl_set_is_equal(set, set2));

956

isl_set_free(set);

957

isl_set_free(set2);

958

959

set = isl_set_read_from_str(ctx,

960

"{[x,y]: y >= 0 & x <= 5 & y <= x or "

961

"y >= 0 & x = 6 & y <= 7}");

962

set = isl_set_coalesce(set);

963

assert(set && set->n == 2);

964

isl_set_free(set);

965

966

set = isl_set_read_from_str(ctx,

967

"[n] -> { [i] : i = 1 and n >= 2 or 2 <= i and i <= n }");

968

set = isl_set_coalesce(set);

969

assert(set && set->n == 1);

970

set2 = isl_set_read_from_str(ctx,

971

"[n] -> { [i] : i = 1 and n >= 2 or 2 <= i and i <= n }");

972

assert(isl_set_is_equal(set, set2));

973

isl_set_free(set);

974

isl_set_free(set2);

975

976

set = isl_set_read_from_str(ctx,

977

"{[x,y] : x >= 0 and y >= 0 or 0 <= y and y <= 5 and x = -1}");

978

set = isl_set_coalesce(set);

979

set2 = isl_set_read_from_str(ctx,

980

"{[x,y] : x >= 0 and y >= 0 or 0 <= y and y <= 5 and x = -1}");

981

assert(isl_set_is_equal(set, set2));

982

isl_set_free(set);

983

isl_set_free(set2);

984

985

set = isl_set_read_from_str(ctx,

986

"[n] -> { [i] : 1 <= i and i <= n - 1 or "

987

"2 <= i and i <= n }");

988

set = isl_set_coalesce(set);

989

assert(set && set->n == 1);

990

set2 = isl_set_read_from_str(ctx,

991

"[n] -> { [i] : 1 <= i and i <= n - 1 or "

992

"2 <= i and i <= n }");

993

assert(isl_set_is_equal(set, set2));

994

isl_set_free(set);

995

isl_set_free(set2);

996

997

map = isl_map_read_from_str(ctx,

998

"[n] -> { [i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "

999

"e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "

1000

"e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "

1001

"4e4 = -2 + o0 and i0 >= 8 + 2n and o0 >= 2 + i0 and "

1002

"o0 <= 56 + 2n and o0 <= -12 + 4n and i0 <= 57 + 2n and "

1003

"i0 <= -11 + 4n and o0 >= 6 + 2n and 4e0 <= i0 and "

1004

"4e0 >= -3 + i0 and 4e1 <= o0 and 4e1 >= -3 + o0 and "

1005

"4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0);"

1006

"[i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "

1007

"e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "

1008

"e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "

1009

"4e4 = -2 + o0 and 2e0 >= 3 + n and e0 <= -4 + n and "

1010

"2e0 <= 27 + n and e1 <= -4 + n and 2e1 <= 27 + n and "

1011

"2e1 >= 2 + n and e1 >= 1 + e0 and i0 >= 7 + 2n and "

1012

"i0 <= -11 + 4n and i0 <= 57 + 2n and 4e0 <= -2 + i0 and "

1013

"4e0 >= -3 + i0 and o0 >= 6 + 2n and o0 <= -11 + 4n and "

1014

"o0 <= 57 + 2n and 4e1 <= -2 + o0 and 4e1 >= -3 + o0 and "

1015

"4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0 ) }");

1016

map = isl_map_coalesce(map);

1017

map2 = isl_map_read_from_str(ctx,

1018

"[n] -> { [i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "

1019

"e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "

1020

"e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "

1021

"4e4 = -2 + o0 and i0 >= 8 + 2n and o0 >= 2 + i0 and "

1022

"o0 <= 56 + 2n and o0 <= -12 + 4n and i0 <= 57 + 2n and "

1023

"i0 <= -11 + 4n and o0 >= 6 + 2n and 4e0 <= i0 and "

1024

"4e0 >= -3 + i0 and 4e1 <= o0 and 4e1 >= -3 + o0 and "

1025

"4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0);"

1026

"[i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "

1027

"e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "

1028

"e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "

1029

"4e4 = -2 + o0 and 2e0 >= 3 + n and e0 <= -4 + n and "

1030

"2e0 <= 27 + n and e1 <= -4 + n and 2e1 <= 27 + n and "

1031

"2e1 >= 2 + n and e1 >= 1 + e0 and i0 >= 7 + 2n and "

1032

"i0 <= -11 + 4n and i0 <= 57 + 2n and 4e0 <= -2 + i0 and "

1033

"4e0 >= -3 + i0 and o0 >= 6 + 2n and o0 <= -11 + 4n and "

1034

"o0 <= 57 + 2n and 4e1 <= -2 + o0 and 4e1 >= -3 + o0 and "

1035

"4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0 ) }");

1036

assert(isl_map_is_equal(map, map2));

1037

isl_map_free(map);

1038

isl_map_free(map2);

1039

1040

str = "[n, m] -> { [] -> [o0, o2, o3] : (o3 = 1 and o0 >= 1 + m and "

1041

"o0 <= n + m and o2 <= m and o0 >= 2 + n and o2 >= 3) or "

1042

"(o0 >= 2 + n and o0 >= 1 + m and o0 <= n + m and n >= 1 and "

1043

"o3 <= -1 + o2 and o3 >= 1 - m + o2 and o3 >= 2 and o3 <= n) }";

1044

map = isl_map_read_from_str(ctx, str);

1045

map = isl_map_coalesce(map);

1046

map2 = isl_map_read_from_str(ctx, str);

1047

assert(isl_map_is_equal(map, map2));

1048

isl_map_free(map);

1049

isl_map_free(map2);

1050

1051

str = "[M, N] -> { [i0, i1, i2, i3, i4, i5, i6] -> "

1052

"[o0, o1, o2, o3, o4, o5, o6] : "

1053

"(o6 <= -4 + 2M - 2N + i0 + i1 - i2 + i6 - o0 - o1 + o2 and "

1054

"o3 <= -2 + i3 and o6 >= 2 + i0 + i3 + i6 - o0 - o3 and "

1055

"o6 >= 2 - M + N + i3 + i4 + i6 - o3 - o4 and o0 <= -1 + i0 and "

1056

"o4 >= 4 - 3M + 3N - i0 - i1 + i2 + 2i3 + i4 + o0 + o1 - o2 - 2o3 "

1057

"and o6 <= -3 + 2M - 2N + i3 + i4 - i5 + i6 - o3 - o4 + o5 and "

1058

"2o6 <= -5 + 5M - 5N + 2i0 + i1 - i2 - i5 + 2i6 - 2o0 - o1 + o2 + o5 "

1059

"and o6 >= 2i0 + i1 + i6 - 2o0 - o1 and "

1060

"3o6 <= -5 + 4M - 4N + 2i0 + i1 - i2 + 2i3 + i4 - i5 + 3i6 "

1061

"- 2o0 - o1 + o2 - 2o3 - o4 + o5) or "

1062

"(N >= 2 and o3 <= -1 + i3 and o0 <= -1 + i0 and "

1063

"o6 >= i3 + i6 - o3 and M >= 0 and "

1064

"2o6 >= 1 + i0 + i3 + 2i6 - o0 - o3 and "

1065

"o6 >= 1 - M + i0 + i6 - o0 and N >= 2M and o6 >= i0 + i6 - o0) }";

1066

map = isl_map_read_from_str(ctx, str);

1067

map = isl_map_coalesce(map);

1068

map2 = isl_map_read_from_str(ctx, str);

1069

assert(isl_map_is_equal(map, map2));

1070

isl_map_free(map);

1071

isl_map_free(map2);

1072

1073

str = "[M, N] -> { [] -> [o0] : (o0 = 0 and M >= 1 and N >= 2) or "

1074

"(o0 = 0 and M >= 1 and N >= 2M and N >= 2 + M) or "

1075

"(o0 = 0 and M >= 2 and N >= 3) or "

1076

"(M = 0 and o0 = 0 and N >= 3) }";

1077

map = isl_map_read_from_str(ctx, str);

1078

map = isl_map_coalesce(map);

1079

map2 = isl_map_read_from_str(ctx, str);

1080

assert(isl_map_is_equal(map, map2));

1081

isl_map_free(map);

1082

isl_map_free(map2);

1083

1084

str = "{ [i0, i1, i2, i3] : (i1 = 10i0 and i0 >= 1 and 10i0 <= 100 and "

1085

"i3 <= 9 + 10 i2 and i3 >= 1 + 10i2 and i3 >= 0) or "

1086

"(i1 <= 9 + 10i0 and i1 >= 1 + 10i0 and i2 >= 0 and "

1087

"i0 >= 0 and i1 <= 100 and i3 <= 9 + 10i2 and i3 >= 1 + 10i2) }";

1088

map = isl_map_read_from_str(ctx, str);

1089

map = isl_map_coalesce(map);

1090

map2 = isl_map_read_from_str(ctx, str);

1091

assert(isl_map_is_equal(map, map2));

1092

isl_map_free(map);

1093

isl_map_free(map2);

1094

1095

test_coalesce_set(ctx,

1096

"[M] -> { [i1] : (i1 >= 2 and i1 <= M) or "

1097

"(i1 = M and M >= 1) }", 0);

1098

test_coalesce_set(ctx,

1099

"{[x,y] : x,y >= 0; [x,y] : 10 <= x <= 20 and y >= -1 }", 0);

1100

test_coalesce_set(ctx,

1101

"{ [x, y] : (x >= 1 and y >= 1 and x <= 2 and y <= 2) or "

1102

"(y = 3 and x = 1) }", 1);

1103

test_coalesce_set(ctx,

1104

"[M] -> { [i0, i1, i2, i3, i4] : (i1 >= 3 and i4 >= 2 + i2 and "

1105

"i2 >= 2 and i0 >= 2 and i3 >= 1 + i2 and i0 <= M and "

1106

"i1 <= M and i3 <= M and i4 <= M) or "

1107

"(i1 >= 2 and i4 >= 1 + i2 and i2 >= 2 and i0 >= 2 and "

1108

"i3 >= 1 + i2 and i0 <= M and i1 <= -1 + M and i3 <= M and "

1109

"i4 <= -1 + M) }", 1);

1110

test_coalesce_set(ctx,

1111

"{ [x, y] : (x >= 0 and y >= 0 and x <= 10 and y <= 10) or "

1112

"(x >= 1 and y >= 1 and x <= 11 and y <= 11) }", 1);

1113

if (test_coalesce_unbounded_wrapping(ctx) < 0)

1114

return -1;

1115

if (test_coalesce_set(ctx, "{[x,0] : x >= 0; [x,1] : x <= 20}", 0) < 0)

1116

return -1;

1117

if (test_coalesce_set(ctx, "{ [x, 1 - x] : 0 <= x <= 1; [0,0] }", 1) < 0)

1118

return -1;

1119

if (test_coalesce_set(ctx, "{ [0,0]; [i,i] : 1 <= i <= 10 }", 1) < 0)

1120

return -1;

1121

if (test_coalesce_set(ctx, "{ [0,0]; [i,j] : 1 <= i,j <= 10 }", 0) < 0)

1122

return -1;

1123

if (test_coalesce_set(ctx, "{ [0,0]; [i,2i] : 1 <= i <= 10 }", 1) < 0)

1124

return -1;

1125

if (test_coalesce_set(ctx, "{ [0,0]; [i,2i] : 2 <= i <= 10 }", 0) < 0)

1126

return -1;

1127

if (test_coalesce_set(ctx, "{ [1,0]; [i,2i] : 1 <= i <= 10 }", 0) < 0)

1128

return -1;

1129

if (test_coalesce_set(ctx, "{ [0,1]; [i,2i] : 1 <= i <= 10 }", 0) < 0)

1130

return -1;

1131

if (test_coalesce_set(ctx, "{ [a, b] : exists e : 2e = a and "

1132

"a >= 0 and (a <= 3 or (b <= 0 and b >= -4 + a)) }", 0) < 0)

1133

return -1;

1134

if (test_coalesce_set(ctx,

1135

"{ [i, j, i', j'] : i <= 2 and j <= 2 and "

1136

"j' >= -1 + 2i + j - 2i' and i' <= -1 + i and "

1137

"j >= 1 and j' <= i + j - i' and i >= 1; "

1138

"[1, 1, 1, 1] }", 0) < 0)

1139

return -1;

1140

if (test_coalesce_set(ctx, "{ [i,j] : exists a,b : i = 2a and j = 3b; "

1141

"[i,j] : exists a : j = 3a }", 1) < 0)

return -1;

return 0;

}

void test_closure(struct isl_ctx *ctx)

{

const char *str;

isl_set *dom;

isl_map *up, *right;

1151

isl_map *map, *map2;

1152

int exact;

1153

1154

/* COCOA example 1 */

1155

map = isl_map_read_from_str(ctx,

1156

"[n] -> { [i,j] -> [i2,j2] : i2 = i + 1 and j2 = j + 1 and "

1157

"1 <= i and i < n and 1 <= j and j < n or "

1158

"i2 = i + 1 and j2 = j - 1 and "

1159

"1 <= i and i < n and 2 <= j and j <= n }");

1160

map = isl_map_power(map, &exact);

assert(exact);

isl_map_free(map);

/* COCOA example 1 */

1165

map = isl_map_read_from_str(ctx,

1166

"[n] -> { [i,j] -> [i2,j2] : i2 = i + 1 and j2 = j + 1 and "

1167

"1 <= i and i < n and 1 <= j and j < n or "

1168

"i2 = i + 1 and j2 = j - 1 and "

1169

"1 <= i and i < n and 2 <= j and j <= n }");

1170

map = isl_map_transitive_closure(map, &exact);

1171

assert(exact);

1172

map2 = isl_map_read_from_str(ctx,

1173

"[n] -> { [i,j] -> [i2,j2] : exists (k1,k2,k : "

1174

"1 <= i and i < n and 1 <= j and j <= n and "

1175

"2 <= i2 and i2 <= n and 1 <= j2 and j2 <= n and "

1176

"i2 = i + k1 + k2 and j2 = j + k1 - k2 and "

1177

"k1 >= 0 and k2 >= 0 and k1 + k2 = k and k >= 1 )}");

1178

assert(isl_map_is_equal(map, map2));

1179

isl_map_free(map2);

1180

isl_map_free(map);

1181

1182

map = isl_map_read_from_str(ctx,

1183

"[n] -> { [x] -> [y] : y = x + 1 and 0 <= x and x <= n and "

1184

" 0 <= y and y <= n }");

1185

map = isl_map_transitive_closure(map, &exact);

1186

map2 = isl_map_read_from_str(ctx,

1187

"[n] -> { [x] -> [y] : y > x and 0 <= x and x <= n and "

1188

" 0 <= y and y <= n }");

1189

assert(isl_map_is_equal(map, map2));

1190

isl_map_free(map2);

1191

isl_map_free(map);

1192

1193

/* COCOA example 2 */

1194

map = isl_map_read_from_str(ctx,

1195

"[n] -> { [i,j] -> [i2,j2] : i2 = i + 2 and j2 = j + 2 and "

1196

"1 <= i and i < n - 1 and 1 <= j and j < n - 1 or "

1197

"i2 = i + 2 and j2 = j - 2 and "

1198

"1 <= i and i < n - 1 and 3 <= j and j <= n }");

1199

map = isl_map_transitive_closure(map, &exact);

1200

assert(exact);

1201

map2 = isl_map_read_from_str(ctx,

1202

"[n] -> { [i,j] -> [i2,j2] : exists (k1,k2,k : "

1203

"1 <= i and i < n - 1 and 1 <= j and j <= n and "

1204

"3 <= i2 and i2 <= n and 1 <= j2 and j2 <= n and "

1205

"i2 = i + 2 k1 + 2 k2 and j2 = j + 2 k1 - 2 k2 and "

1206

"k1 >= 0 and k2 >= 0 and k1 + k2 = k and k >= 1) }");

1207

assert(isl_map_is_equal(map, map2));

1208

isl_map_free(map);

1209

isl_map_free(map2);

1210

1211

/* COCOA Fig.2 left */

1212

map = isl_map_read_from_str(ctx,

1213

"[n] -> { [i,j] -> [i2,j2] : i2 = i + 2 and j2 = j and "

1214

"i <= 2 j - 3 and i <= n - 2 and j <= 2 i - 1 and "

1215

"j <= n or "

1216

"i2 = i and j2 = j + 2 and i <= 2 j - 1 and i <= n and "

1217

"j <= 2 i - 3 and j <= n - 2 or "

1218

"i2 = i + 1 and j2 = j + 1 and i <= 2 j - 1 and "

1219

"i <= n - 1 and j <= 2 i - 1 and j <= n - 1 }");

1220

map = isl_map_transitive_closure(map, &exact);

assert(exact);

isl_map_free(map);

/* COCOA Fig.2 right */

1225

map = isl_map_read_from_str(ctx,

1226

"[n] -> { [i,j] -> [i2,j2] : i2 = i + 3 and j2 = j and "

1227

"i <= 2 j - 4 and i <= n - 3 and j <= 2 i - 1 and "

1228

"j <= n or "

1229

"i2 = i and j2 = j + 3 and i <= 2 j - 1 and i <= n and "

1230

"j <= 2 i - 4 and j <= n - 3 or "

1231

"i2 = i + 1 and j2 = j + 1 and i <= 2 j - 1 and "

1232

"i <= n - 1 and j <= 2 i - 1 and j <= n - 1 }");

1233

map = isl_map_power(map, &exact);

assert(exact);

isl_map_free(map);

/* COCOA Fig.2 right */

1238

map = isl_map_read_from_str(ctx,

1239

"[n] -> { [i,j] -> [i2,j2] : i2 = i + 3 and j2 = j and "

1240

"i <= 2 j - 4 and i <= n - 3 and j <= 2 i - 1 and "

1241

"j <= n or "

1242

"i2 = i and j2 = j + 3 and i <= 2 j - 1 and i <= n and "

1243

"j <= 2 i - 4 and j <= n - 3 or "

1244

"i2 = i + 1 and j2 = j + 1 and i <= 2 j - 1 and "

1245

"i <= n - 1 and j <= 2 i - 1 and j <= n - 1 }");

1246

map = isl_map_transitive_closure(map, &exact);

1247

assert(exact);

1248

map2 = isl_map_read_from_str(ctx,

1249

"[n] -> { [i,j] -> [i2,j2] : exists (k1,k2,k3,k : "

1250

"i <= 2 j - 1 and i <= n and j <= 2 i - 1 and "

1251

"j <= n and 3 + i + 2 j <= 3 n and "

1252

"3 + 2 i + j <= 3n and i2 <= 2 j2 -1 and i2 <= n and "

1253

"i2 <= 3 j2 - 4 and j2 <= 2 i2 -1 and j2 <= n and "

1254

"13 + 4 j2 <= 11 i2 and i2 = i + 3 k1 + k3 and "

1255

"j2 = j + 3 k2 + k3 and k1 >= 0 and k2 >= 0 and "

1256

"k3 >= 0 and k1 + k2 + k3 = k and k > 0) }");

1257

assert(isl_map_is_equal(map, map2));

1258

isl_map_free(map2);

1259

isl_map_free(map);

1260

1261

/* COCOA Fig.1 right */

1262

dom = isl_set_read_from_str(ctx,

1263

"{ [x,y] : x >= 0 and -2 x + 3 y >= 0 and x <= 3 and "

1264

"2 x - 3 y + 3 >= 0 }");

1265

right = isl_map_read_from_str(ctx,

1266

"{ [x,y] -> [x2,y2] : x2 = x + 1 and y2 = y }");

1267

up = isl_map_read_from_str(ctx,

1268

"{ [x,y] -> [x2,y2] : x2 = x and y2 = y + 1 }");

1269

right = isl_map_intersect_domain(right, isl_set_copy(dom));

1270

right = isl_map_intersect_range(right, isl_set_copy(dom));

1271

up = isl_map_intersect_domain(up, isl_set_copy(dom));

1272

up = isl_map_intersect_range(up, dom);

1273

map = isl_map_union(up, right);

1274

map = isl_map_transitive_closure(map, &exact);

1275

assert(exact);

1276

map2 = isl_map_read_from_str(ctx,

1277

"{ [0,0] -> [0,1]; [0,0] -> [1,1]; [0,1] -> [1,1]; "

1278

" [2,2] -> [3,2]; [2,2] -> [3,3]; [3,2] -> [3,3] }");

1279

assert(isl_map_is_equal(map, map2));

1280

isl_map_free(map2);

1281

isl_map_free(map);

1282

1283

/* COCOA Theorem 1 counter example */

1284

map = isl_map_read_from_str(ctx,

1285

"{ [i,j] -> [i2,j2] : i = 0 and 0 <= j and j <= 1 and "

1286

"i2 = 1 and j2 = j or "

1287

"i = 0 and j = 0 and i2 = 0 and j2 = 1 }");

1288

map = isl_map_transitive_closure(map, &exact);

assert(exact);

isl_map_free(map);

map = isl_map_read_from_str(ctx,

1293

"[m,n] -> { [i,j] -> [i2,j2] : i2 = i and j2 = j + 2 and "

1294

"1 <= i,i2 <= n and 1 <= j,j2 <= m or "

1295

"i2 = i + 1 and 3 <= j2 - j <= 4 and "

1296

"1 <= i,i2 <= n and 1 <= j,j2 <= m }");

1297

map = isl_map_transitive_closure(map, &exact);

assert(exact);

isl_map_free(map);

/* Kelly et al 1996, fig 12 */

1302

map = isl_map_read_from_str(ctx,

1303

"[n] -> { [i,j] -> [i2,j2] : i2 = i and j2 = j + 1 and "

1304

"1 <= i,j,j+1 <= n or "

1305

"j = n and j2 = 1 and i2 = i + 1 and "

1306

"1 <= i,i+1 <= n }");

1307

map = isl_map_transitive_closure(map, &exact);

1308

assert(exact);

1309

map2 = isl_map_read_from_str(ctx,

1310

"[n] -> { [i,j] -> [i2,j2] : 1 <= j < j2 <= n and "

1311

"1 <= i <= n and i = i2 or "

1312

"1 <= i < i2 <= n and 1 <= j <= n and "

1313

"1 <= j2 <= n }");

1314

assert(isl_map_is_equal(map, map2));

1315

isl_map_free(map2);

1316

isl_map_free(map);

1317

1318

/* Omega's closure4 */

1319

map = isl_map_read_from_str(ctx,

1320

"[m,n] -> { [x,y] -> [x2,y2] : x2 = x and y2 = y + 1 and "

1321

"1 <= x,y <= 10 or "

1322

"x2 = x + 1 and y2 = y and "

1323

"1 <= x <= 20 && 5 <= y <= 15 }");

1324

map = isl_map_transitive_closure(map, &exact);

assert(exact);

isl_map_free(map);

map = isl_map_read_from_str(ctx,

1329

"[n] -> { [x] -> [y]: 1 <= n <= y - x <= 10 }");

1330

map = isl_map_transitive_closure(map, &exact);

1331

assert(!exact);

1332

map2 = isl_map_read_from_str(ctx,

1333

"[n] -> { [x] -> [y] : 1 <= n <= 10 and y >= n + x }");

1334

assert(isl_map_is_equal(map, map2));

1335

isl_map_free(map);

1336

isl_map_free(map2);

1337

1338

str = "[n, m] -> { [i0, i1, i2, i3] -> [o0, o1, o2, o3] : "

1339

"i3 = 1 and o0 = i0 and o1 = -1 + i1 and o2 = -1 + i2 and "

1340

"o3 = -2 + i2 and i1 <= -1 + i0 and i1 >= 1 - m + i0 and "

1341

"i1 >= 2 and i1 <= n and i2 >= 3 and i2 <= 1 + n and i2 <= m }";

1342

map = isl_map_read_from_str(ctx, str);

1343

map = isl_map_transitive_closure(map, &exact);

1344

assert(exact);

1345

map2 = isl_map_read_from_str(ctx, str);

1346

assert(isl_map_is_equal(map, map2));

1347

isl_map_free(map);

1348

isl_map_free(map2);

1349

1350

str = "{[0] -> [1]; [2] -> [3]}";

1351

map = isl_map_read_from_str(ctx, str);

1352

map = isl_map_transitive_closure(map, &exact);

1353

assert(exact);

1354

map2 = isl_map_read_from_str(ctx, str);

1355

assert(isl_map_is_equal(map, map2));

1356

isl_map_free(map);

1357

isl_map_free(map2);

1358

1359

str = "[n] -> { [[i0, i1, 1, 0, i0] -> [i5, 1]] -> "

1360

"[[i0, -1 + i1, 2, 0, i0] -> [-1 + i5, 2]] : "

1361

"exists (e0 = [(3 - n)/3]: i5 >= 2 and i1 >= 2 and "

1362

"3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "

1363

"3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n); "

1364

"[[i0, i1, 2, 0, i0] -> [i5, 1]] -> "

1365

"[[i0, i1, 1, 0, i0] -> [-1 + i5, 2]] : "

1366

"exists (e0 = [(3 - n)/3]: i5 >= 2 and i1 >= 1 and "

1367

"3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "

1368

"3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n); "

1369

"[[i0, i1, 1, 0, i0] -> [i5, 2]] -> "

1370

"[[i0, -1 + i1, 2, 0, i0] -> [i5, 1]] : "

1371

"exists (e0 = [(3 - n)/3]: i1 >= 2 and i5 >= 1 and "

1372

"3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "

1373

"3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n); "

1374

"[[i0, i1, 2, 0, i0] -> [i5, 2]] -> "

1375

"[[i0, i1, 1, 0, i0] -> [i5, 1]] : "

1376

"exists (e0 = [(3 - n)/3]: i5 >= 1 and i1 >= 1 and "

1377

"3i0 <= -1 + n and i1 <= -1 + n and i5 <= -1 + n and "

1378

"3e0 >= 1 - n and 3e0 <= 2 - n and 3i0 >= -2 + n) }";

1379

map = isl_map_read_from_str(ctx, str);

1380

map = isl_map_transitive_closure(map, NULL);

assert(map);

isl_map_free(map);

}

void test_lex(struct isl_ctx *ctx)

{

isl_space *dim;

isl_map *map;

dim = isl_space_set_alloc(ctx, 0, 0);

1391

map = isl_map_lex_le(dim);

1392

assert(!isl_map_is_empty(map));

isl_map_free(map);

}

void test_lexmin(struct isl_ctx *ctx)

1397

{

1398

const char *str;

1399

isl_basic_map *bmap;

1400

isl_map *map, *map2;

1401

isl_set *set;

1402

isl_set *set2;

1403

isl_pw_multi_aff *pma;

1404

1405

str = "[p0, p1] -> { [] -> [] : "

1406

"exists (e0 = [(2p1)/3], e1, e2, e3 = [(3 - p1 + 3e0)/3], "

1407

"e4 = [(p1)/3], e5 = [(p1 + 3e4)/3]: "

1408

"3e0 >= -2 + 2p1 and 3e0 >= p1 and 3e3 >= 1 - p1 + 3e0 and "

1409

"3e0 <= 2p1 and 3e3 >= -2 + p1 and 3e3 <= -1 + p1 and p1 >= 3 and "

1410

"3e5 >= -2 + 2p1 and 3e5 >= p1 and 3e5 <= -1 + p1 + 3e4 and "

1411

"3e4 <= p1 and 3e4 >= -2 + p1 and e3 <= -1 + e0 and "

1412

"3e4 >= 6 - p1 + 3e1 and 3e1 >= p1 and 3e5 >= -2 + p1 + 3e4 and "

1413

"2e4 >= 3 - p1 + 2e1 and e4 <= e1 and 3e3 <= 2 - p1 + 3e0 and "

1414

"e5 >= 1 + e1 and 3e4 >= 6 - 2p1 + 3e1 and "

1415

"p0 >= 2 and p1 >= p0 and 3e2 >= p1 and 3e4 >= 6 - p1 + 3e2 and "

1416

"e2 <= e1 and e3 >= 1 and e4 <= e2) }";

1417

map = isl_map_read_from_str(ctx, str);

1418

map = isl_map_lexmin(map);

1419

isl_map_free(map);

1420

1421

str = "[C] -> { [obj,a,b,c] : obj <= 38 a + 7 b + 10 c and "

1422

"a + b <= 1 and c <= 10 b and c <= C and a,b,c,C >= 0 }";

1423

set = isl_set_read_from_str(ctx, str);

1424

set = isl_set_lexmax(set);

1425

str = "[C] -> { [obj,a,b,c] : C = 8 }";

1426

set2 = isl_set_read_from_str(ctx, str);

1427

set = isl_set_intersect(set, set2);

1428

assert(!isl_set_is_empty(set));

1429

isl_set_free(set);

1430

1431

str = "{ [x] -> [y] : x <= y <= 10; [x] -> [5] : -8 <= x <= 8 }";

1432

map = isl_map_read_from_str(ctx, str);

1433

map = isl_map_lexmin(map);

1434

str = "{ [x] -> [5] : 6 <= x <= 8; "

1435

"[x] -> [x] : x <= 5 or (9 <= x <= 10) }";

1436

map2 = isl_map_read_from_str(ctx, str);

1437

assert(isl_map_is_equal(map, map2));

1438

isl_map_free(map);

1439

isl_map_free(map2);

1440

1441

str = "{ [x] -> [y] : 4y = x or 4y = -1 + x or 4y = -2 + x }";

1442

map = isl_map_read_from_str(ctx, str);

1443

map2 = isl_map_copy(map);

1444

map = isl_map_lexmin(map);

1445

assert(isl_map_is_equal(map, map2));

1446

isl_map_free(map);

1447

isl_map_free(map2);

1448

1449

str = "{ [x] -> [y] : x = 4y; [x] -> [y] : x = 2y }";

1450

map = isl_map_read_from_str(ctx, str);

1451

map = isl_map_lexmin(map);

1452

str = "{ [x] -> [y] : (4y = x and x >= 0) or "

1453

"(exists (e0 = [(x)/4], e1 = [(-2 + x)/4]: 2y = x and "

1454

"4e1 = -2 + x and 4e0 <= -1 + x and 4e0 >= -3 + x)) or "

1455

"(exists (e0 = [(x)/4]: 2y = x and 4e0 = x and x <= -4)) }";

1456

map2 = isl_map_read_from_str(ctx, str);

1457

assert(isl_map_is_equal(map, map2));

1458

isl_map_free(map);

1459

isl_map_free(map2);

1460

1461

str = "{ [i] -> [i', j] : j = i - 8i' and i' >= 0 and i' <= 7 and "

1462

" 8i' <= i and 8i' >= -7 + i }";

1463

bmap = isl_basic_map_read_from_str(ctx, str);

1464

pma = isl_basic_map_lexmin_pw_multi_aff(isl_basic_map_copy(bmap));

1465

map2 = isl_map_from_pw_multi_aff(pma);

1466

map = isl_map_from_basic_map(bmap);

1467

assert(isl_map_is_equal(map, map2));

1468

isl_map_free(map);

1469

isl_map_free(map2);

1470

1471

str = "{ T[a] -> S[b, c] : a = 4b-2c and c >= b }";

1472

map = isl_map_read_from_str(ctx, str);

1473

map = isl_map_lexmin(map);

1474

str = "{ T[a] -> S[b, c] : 2b = a and 2c = a }";

1475

map2 = isl_map_read_from_str(ctx, str);

1476

assert(isl_map_is_equal(map, map2));

1477

isl_map_free(map);

1478

isl_map_free(map2);

}

struct must_may {

isl_map *must;

isl_map *may;

};

static int collect_must_may(__isl_take isl_map *dep, int must,

1487

void *dep_user, void *user)

1488

{

1489

struct must_may *mm = (struct must_may *)user;

1490

1491

if (must)

1492

mm->must = isl_map_union(mm->must, dep);

1493

else

1494

mm->may = isl_map_union(mm->may, dep);

return 0;

}

static int common_space(void *first, void *second)

1500

{

1501

int depth = *(int *)first;

return 2 * depth;

}

static int map_is_equal(__isl_keep isl_map *map, const char *str)

{

isl_map *map2;

int equal;

if (!map)

return -1;

map2 = isl_map_read_from_str(map->ctx, str);

1514

equal = isl_map_is_equal(map, map2);

1515

isl_map_free(map2);

return equal;

}

static int map_check_equal(__isl_keep isl_map *map, const char *str)

{

int equal;

equal = map_is_equal(map, str);

if (equal < 0)

return -1;

if (!equal)

isl_die(isl_map_get_ctx(map), isl_error_unknown,

1529

"result not as expected", return -1);

return 0;

}

void test_dep(struct isl_ctx *ctx)

{

const char *str;

isl_space *dim;

isl_map *map;

isl_access_info *ai;

1539

isl_flow *flow;

1540

int depth;

1541

struct must_may mm;

depth = 3;

str = "{ [2,i,0] -> [i] : 0 <= i <= 10 }";

1546

map = isl_map_read_from_str(ctx, str);

1547

ai = isl_access_info_alloc(map, &depth, &common_space, 2);

1548

1549

str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";

1550

map = isl_map_read_from_str(ctx, str);

1551

ai = isl_access_info_add_source(ai, map, 1, &depth);

1552

1553

str = "{ [1,i,0] -> [5] : 0 <= i <= 10 }";

1554

map = isl_map_read_from_str(ctx, str);

1555

ai = isl_access_info_add_source(ai, map, 1, &depth);

1556

1557

flow = isl_access_info_compute_flow(ai);

1558

dim = isl_space_alloc(ctx, 0, 3, 3);

1559

mm.must = isl_map_empty(isl_space_copy(dim));

1560

mm.may = isl_map_empty(dim);

1561

1562

isl_flow_foreach(flow, collect_must_may, &mm);

1563

1564

str = "{ [0,i,0] -> [2,i,0] : (0 <= i <= 4) or (6 <= i <= 10); "

1565

" [1,10,0] -> [2,5,0] }";

1566

assert(map_is_equal(mm.must, str));

1567

str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";

1568

assert(map_is_equal(mm.may, str));

1569

1570

isl_map_free(mm.must);

1571

isl_map_free(mm.may);

1572

isl_flow_free(flow);

1573

1574

1575

str = "{ [2,i,0] -> [i] : 0 <= i <= 10 }";

1576

map = isl_map_read_from_str(ctx, str);

1577

ai = isl_access_info_alloc(map, &depth, &common_space, 2);

1578

1579

str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";

1580

map = isl_map_read_from_str(ctx, str);

1581

ai = isl_access_info_add_source(ai, map, 1, &depth);

1582

1583

str = "{ [1,i,0] -> [5] : 0 <= i <= 10 }";

1584

map = isl_map_read_from_str(ctx, str);

1585

ai = isl_access_info_add_source(ai, map, 0, &depth);

1586

1587

flow = isl_access_info_compute_flow(ai);

1588

dim = isl_space_alloc(ctx, 0, 3, 3);

1589

mm.must = isl_map_empty(isl_space_copy(dim));

1590

mm.may = isl_map_empty(dim);

1591

1592

isl_flow_foreach(flow, collect_must_may, &mm);

1593

1594

str = "{ [0,i,0] -> [2,i,0] : (0 <= i <= 4) or (6 <= i <= 10) }";

1595

assert(map_is_equal(mm.must, str));

1596

str = "{ [0,5,0] -> [2,5,0]; [1,i,0] -> [2,5,0] : 0 <= i <= 10 }";

1597

assert(map_is_equal(mm.may, str));

1598

1599

isl_map_free(mm.must);

1600

isl_map_free(mm.may);

1601

isl_flow_free(flow);

1602

1603

1604

str = "{ [2,i,0] -> [i] : 0 <= i <= 10 }";

1605

map = isl_map_read_from_str(ctx, str);

1606

ai = isl_access_info_alloc(map, &depth, &common_space, 2);

1607

1608

str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";

1609

map = isl_map_read_from_str(ctx, str);

1610

ai = isl_access_info_add_source(ai, map, 0, &depth);

1611

1612

str = "{ [1,i,0] -> [5] : 0 <= i <= 10 }";

1613

map = isl_map_read_from_str(ctx, str);

1614

ai = isl_access_info_add_source(ai, map, 0, &depth);

1615

1616

flow = isl_access_info_compute_flow(ai);

1617

dim = isl_space_alloc(ctx, 0, 3, 3);

1618

mm.must = isl_map_empty(isl_space_copy(dim));

1619

mm.may = isl_map_empty(dim);

1620

1621

isl_flow_foreach(flow, collect_must_may, &mm);

1622

1623

str = "{ [0,i,0] -> [2,i,0] : 0 <= i <= 10; "

1624

" [1,i,0] -> [2,5,0] : 0 <= i <= 10 }";

1625

assert(map_is_equal(mm.may, str));

1626

str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";

1627

assert(map_is_equal(mm.must, str));

1628

1629

isl_map_free(mm.must);

1630

isl_map_free(mm.may);

1631

isl_flow_free(flow);

1632

1633

1634

str = "{ [0,i,2] -> [i] : 0 <= i <= 10 }";

1635

map = isl_map_read_from_str(ctx, str);

1636

ai = isl_access_info_alloc(map, &depth, &common_space, 2);

1637

1638

str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";

1639

map = isl_map_read_from_str(ctx, str);

1640

ai = isl_access_info_add_source(ai, map, 0, &depth);

1641

1642

str = "{ [0,i,1] -> [5] : 0 <= i <= 10 }";

1643

map = isl_map_read_from_str(ctx, str);

1644

ai = isl_access_info_add_source(ai, map, 0, &depth);

1645

1646

flow = isl_access_info_compute_flow(ai);

1647

dim = isl_space_alloc(ctx, 0, 3, 3);

1648

mm.must = isl_map_empty(isl_space_copy(dim));

1649

mm.may = isl_map_empty(dim);

1650

1651

isl_flow_foreach(flow, collect_must_may, &mm);

1652

1653

str = "{ [0,i,0] -> [0,i,2] : 0 <= i <= 10; "

1654

" [0,i,1] -> [0,5,2] : 0 <= i <= 5 }";

1655

assert(map_is_equal(mm.may, str));

1656

str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";

1657

assert(map_is_equal(mm.must, str));

1658

1659

isl_map_free(mm.must);

1660

isl_map_free(mm.may);

1661

isl_flow_free(flow);

1662

1663

1664

str = "{ [0,i,1] -> [i] : 0 <= i <= 10 }";

1665

map = isl_map_read_from_str(ctx, str);

1666

ai = isl_access_info_alloc(map, &depth, &common_space, 2);

1667

1668

str = "{ [0,i,0] -> [i] : 0 <= i <= 10 }";

1669

map = isl_map_read_from_str(ctx, str);

1670

ai = isl_access_info_add_source(ai, map, 0, &depth);

1671

1672

str = "{ [0,i,2] -> [5] : 0 <= i <= 10 }";

1673

map = isl_map_read_from_str(ctx, str);

1674

ai = isl_access_info_add_source(ai, map, 0, &depth);

1675

1676

flow = isl_access_info_compute_flow(ai);

1677

dim = isl_space_alloc(ctx, 0, 3, 3);

1678

mm.must = isl_map_empty(isl_space_copy(dim));

1679

mm.may = isl_map_empty(dim);

1680

1681

isl_flow_foreach(flow, collect_must_may, &mm);

1682

1683

str = "{ [0,i,0] -> [0,i,1] : 0 <= i <= 10; "

1684

" [0,i,2] -> [0,5,1] : 0 <= i <= 4 }";

1685

assert(map_is_equal(mm.may, str));

1686

str = "{ [i,j,k] -> [l,m,n] : 1 = 0 }";

1687

assert(map_is_equal(mm.must, str));

1688

1689

isl_map_free(mm.must);

1690

isl_map_free(mm.may);

1691

isl_flow_free(flow);

depth = 5;

str = "{ [1,i,0,0,0] -> [i,j] : 0 <= i <= 10 and 0 <= j <= 10 }";

1697

map = isl_map_read_from_str(ctx, str);

1698

ai = isl_access_info_alloc(map, &depth, &common_space, 1);

1699

1700

str = "{ [0,i,0,j,0] -> [i,j] : 0 <= i <= 10 and 0 <= j <= 10 }";

1701

map = isl_map_read_from_str(ctx, str);

1702

ai = isl_access_info_add_source(ai, map, 1, &depth);

1703

1704

flow = isl_access_info_compute_flow(ai);

1705

dim = isl_space_alloc(ctx, 0, 5, 5);

1706

mm.must = isl_map_empty(isl_space_copy(dim));

1707

mm.may = isl_map_empty(dim);

1708

1709

isl_flow_foreach(flow, collect_must_may, &mm);

1710

1711

str = "{ [0,i,0,j,0] -> [1,i,0,0,0] : 0 <= i,j <= 10 }";

1712

assert(map_is_equal(mm.must, str));

1713

str = "{ [0,0,0,0,0] -> [0,0,0,0,0] : 1 = 0 }";

1714

assert(map_is_equal(mm.may, str));

1715

1716

isl_map_free(mm.must);

1717

isl_map_free(mm.may);

1718

isl_flow_free(flow);

1719

}

1720

1721

int test_sv(isl_ctx *ctx)

{

const char *str;

isl_map *map;

isl_union_map *umap;

1726

int sv;

1727

1728

str = "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 9 }";

1729

map = isl_map_read_from_str(ctx, str);

1730

sv = isl_map_is_single_valued(map);

isl_map_free(map);

if (sv < 0)

return -1;

if (!sv)

isl_die(ctx, isl_error_internal,

1736

"map not detected as single valued", return -1);

1737

1738

str = "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 10 }";

1739

map = isl_map_read_from_str(ctx, str);

1740

sv = isl_map_is_single_valued(map);

isl_map_free(map);

if (sv < 0)

return -1;

if (sv)

isl_die(ctx, isl_error_internal,

1746

"map detected as single valued", return -1);

1747

1748

str = "{ S1[i] -> [i] : 0 <= i <= 9; S2[i] -> [i] : 0 <= i <= 9 }";

1749

umap = isl_union_map_read_from_str(ctx, str);

1750

sv = isl_union_map_is_single_valued(umap);

1751

isl_union_map_free(umap);

if (sv < 0)

return -1;

if (!sv)

isl_die(ctx, isl_error_internal,

1756

"map not detected as single valued", return -1);

1757

1758

str = "{ [i] -> S1[i] : 0 <= i <= 9; [i] -> S2[i] : 0 <= i <= 9 }";

1759

umap = isl_union_map_read_from_str(ctx, str);

1760

sv = isl_union_map_is_single_valued(umap);

1761

isl_union_map_free(umap);

if (sv < 0)

return -1;

if (sv)

isl_die(ctx, isl_error_internal,

1766

"map detected as single valued", return -1);

return 0;

}

void test_bijective_case(struct isl_ctx *ctx, const char *str, int bijective)

{

isl_map *map;

map = isl_map_read_from_str(ctx, str);

1776

if (bijective)

1777

assert(isl_map_is_bijective(map));

1778

else

1779

assert(!isl_map_is_bijective(map));

isl_map_free(map);

}

void test_bijective(struct isl_ctx *ctx)

1784

{

1785

test_bijective_case(ctx, "[N,M]->{[i,j] -> [i]}", 0);

1786

test_bijective_case(ctx, "[N,M]->{[i,j] -> [i] : j=i}", 1);

1787

test_bijective_case(ctx, "[N,M]->{[i,j] -> [i] : j=0}", 1);

1788

test_bijective_case(ctx, "[N,M]->{[i,j] -> [i] : j=N}", 1);

1789

test_bijective_case(ctx, "[N,M]->{[i,j] -> [j,i]}", 1);

1790

test_bijective_case(ctx, "[N,M]->{[i,j] -> [i+j]}", 0);

1791

test_bijective_case(ctx, "[N,M]->{[i,j] -> []}", 0);

1792

test_bijective_case(ctx, "[N,M]->{[i,j] -> [i,j,N]}", 1);

1793

test_bijective_case(ctx, "[N,M]->{[i,j] -> [2i]}", 0);

1794

test_bijective_case(ctx, "[N,M]->{[i,j] -> [i,i]}", 0);

1795

test_bijective_case(ctx, "[N,M]->{[i,j] -> [2i,i]}", 0);

1796

test_bijective_case(ctx, "[N,M]->{[i,j] -> [2i,j]}", 1);

1797

test_bijective_case(ctx, "[N,M]->{[i,j] -> [x,y] : 2x=i & y =j}", 1);

1798

}

1799

1800

void test_pwqp(struct isl_ctx *ctx)

{

const char *str;

isl_set *set;

isl_pw_qpolynomial *pwqp1, *pwqp2;

1805

1806

str = "{ [i,j,k] -> 1 + 9 * [i/5] + 7 * [j/11] + 4 * [k/13] }";

1807

pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);

1808

1809

pwqp1 = isl_pw_qpolynomial_move_dims(pwqp1, isl_dim_param, 0,

1810

isl_dim_in, 1, 1);

1811

1812

str = "[j] -> { [i,k] -> 1 + 9 * [i/5] + 7 * [j/11] + 4 * [k/13] }";

1813

pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);

1814

1815

pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);

1816

1817

assert(isl_pw_qpolynomial_is_zero(pwqp1));

1818

1819

isl_pw_qpolynomial_free(pwqp1);

1820

1821

str = "{ [i] -> i }";

1822

pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);

1823

str = "{ [k] : exists a : k = 2a }";

1824

set = isl_set_read_from_str(ctx, str);

1825

pwqp1 = isl_pw_qpolynomial_gist(pwqp1, set);

1826

str = "{ [i] -> i }";

1827

pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);

1828

1829

pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);

1830

1831

assert(isl_pw_qpolynomial_is_zero(pwqp1));

1832

1833

isl_pw_qpolynomial_free(pwqp1);

1834

1835

str = "{ [i] -> i + [ (i + [i/3])/2 ] }";

1836

pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);

1837

str = "{ [10] }";

1838

set = isl_set_read_from_str(ctx, str);

1839

pwqp1 = isl_pw_qpolynomial_gist(pwqp1, set);

1840

str = "{ [i] -> 16 }";

1841

pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);

1842

1843

pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);

1844

1845

assert(isl_pw_qpolynomial_is_zero(pwqp1));

1846

1847

isl_pw_qpolynomial_free(pwqp1);

1848

1849

str = "{ [i] -> ([(i)/2]) }";

1850

pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);

1851

str = "{ [k] : exists a : k = 2a+1 }";

1852

set = isl_set_read_from_str(ctx, str);

1853

pwqp1 = isl_pw_qpolynomial_gist(pwqp1, set);

1854

str = "{ [i] -> -1/2 + 1/2 * i }";

1855

pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);

1856

1857

pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);

1858

1859

assert(isl_pw_qpolynomial_is_zero(pwqp1));

1860

1861

isl_pw_qpolynomial_free(pwqp1);

1862

1863

str = "{ [i] -> ([([i/2] + [i/2])/5]) }";

1864

pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);

1865

str = "{ [i] -> ([(2 * [i/2])/5]) }";

1866

pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);

1867

1868

pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);

1869

1870

assert(isl_pw_qpolynomial_is_zero(pwqp1));

1871

1872

isl_pw_qpolynomial_free(pwqp1);

1873

1874

str = "{ [x] -> ([x/2] + [(x+1)/2]) }";

1875

pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);

1876

str = "{ [x] -> x }";

1877

pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);

1878

1879

pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);

1880

1881

assert(isl_pw_qpolynomial_is_zero(pwqp1));

1882

1883

isl_pw_qpolynomial_free(pwqp1);

1884

1885

str = "{ [i] -> ([i/2]) : i >= 0; [i] -> ([i/3]) : i < 0 }";

1886

pwqp1 = isl_pw_qpolynomial_read_from_str(ctx, str);

1887

pwqp2 = isl_pw_qpolynomial_read_from_str(ctx, str);

1888

pwqp1 = isl_pw_qpolynomial_coalesce(pwqp1);

1889

pwqp1 = isl_pw_qpolynomial_sub(pwqp1, pwqp2);

1890

assert(isl_pw_qpolynomial_is_zero(pwqp1));

1891

isl_pw_qpolynomial_free(pwqp1);

1892

}

1893

1894

void test_split_periods(isl_ctx *ctx)

1895

{

1896

const char *str;

1897

isl_pw_qpolynomial *pwqp;

1898

1899

str = "{ [U,V] -> 1/3 * U + 2/3 * V - [(U + 2V)/3] + [U/2] : "

1900

"U + 2V + 3 >= 0 and - U -2V >= 0 and - U + 10 >= 0 and "

1901

"U >= 0; [U,V] -> U^2 : U >= 100 }";

1902

pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);

1903

1904

pwqp = isl_pw_qpolynomial_split_periods(pwqp, 2);

1905

assert(pwqp);

1906

1907

isl_pw_qpolynomial_free(pwqp);

1908

}

1909

1910

void test_union(isl_ctx *ctx)

1911

{

1912

const char *str;

1913

isl_union_set *uset1, *uset2;

1914

isl_union_map *umap1, *umap2;

1915

1916

str = "{ [i] : 0 <= i <= 1 }";

1917

uset1 = isl_union_set_read_from_str(ctx, str);

1918

str = "{ [1] -> [0] }";

1919

umap1 = isl_union_map_read_from_str(ctx, str);

1920

1921

umap2 = isl_union_set_lex_gt_union_set(isl_union_set_copy(uset1), uset1);

1922

assert(isl_union_map_is_equal(umap1, umap2));

1923

1924

isl_union_map_free(umap1);

1925

isl_union_map_free(umap2);

1926

1927

str = "{ A[i] -> B[i]; B[i] -> C[i]; A[0] -> C[1] }";

1928

umap1 = isl_union_map_read_from_str(ctx, str);

1929

str = "{ A[i]; B[i] }";

1930

uset1 = isl_union_set_read_from_str(ctx, str);

1931

1932

uset2 = isl_union_map_domain(umap1);

1933

1934

assert(isl_union_set_is_equal(uset1, uset2));

1935

1936

isl_union_set_free(uset1);

1937

isl_union_set_free(uset2);

1938

}

1939

1940

void test_bound(isl_ctx *ctx)

1941

{

1942

const char *str;

1943

isl_pw_qpolynomial *pwqp;

1944

isl_pw_qpolynomial_fold *pwf;

1945

1946

str = "{ [[a, b, c, d] -> [e]] -> 0 }";

1947

pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);

1948

pwf = isl_pw_qpolynomial_bound(pwqp, isl_fold_max, NULL);

1949

assert(isl_pw_qpolynomial_fold_dim(pwf, isl_dim_in) == 4);

1950

isl_pw_qpolynomial_fold_free(pwf);

1951

1952

str = "{ [[x]->[x]] -> 1 : exists a : x = 2 a }";

1953

pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);

1954

pwf = isl_pw_qpolynomial_bound(pwqp, isl_fold_max, NULL);

1955

assert(isl_pw_qpolynomial_fold_dim(pwf, isl_dim_in) == 1);

1956

isl_pw_qpolynomial_fold_free(pwf);

1957

}

1958

1959

void test_lift(isl_ctx *ctx)

1960

{

1961

const char *str;

1962

isl_basic_map *bmap;

1963

isl_basic_set *bset;

1964

1965

str = "{ [i0] : exists e0 : i0 = 4e0 }";

1966

bset = isl_basic_set_read_from_str(ctx, str);

1967

bset = isl_basic_set_lift(bset);

1968

bmap = isl_basic_map_from_range(bset);

1969

bset = isl_basic_map_domain(bmap);

1970

isl_basic_set_free(bset);

1971

}

1972

1973

void test_subset(isl_ctx *ctx)

1974

{

1975

const char *str;

1976

isl_set *set1, *set2;

1977

1978

str = "{ [112, 0] }";

1979

set1 = isl_set_read_from_str(ctx, str);

1980

str = "{ [i0, i1] : exists (e0 = [(i0 - i1)/16], e1: "

1981

"16e0 <= i0 - i1 and 16e0 >= -15 + i0 - i1 and "

1982

"16e1 <= i1 and 16e0 >= -i1 and 16e1 >= -i0 + i1) }";

1983

set2 = isl_set_read_from_str(ctx, str);

1984

assert(isl_set_is_subset(set1, set2));

1985

isl_set_free(set1);

1986

isl_set_free(set2);

1987

}

1988

1989

int test_factorize(isl_ctx *ctx)

1990

{

1991

const char *str;

1992

isl_basic_set *bset;

1993

isl_factorizer *f;

1994

1995

str = "{ [i0, i1, i2, i3, i4, i5, i6, i7] : 3i5 <= 2 - 2i0 and "

1996

"i0 >= -2 and i6 >= 1 + i3 and i7 >= 0 and 3i5 >= -2i0 and "

1997

"2i4 <= i2 and i6 >= 1 + 2i0 + 3i1 and i4 <= -1 and "

1998

"i6 >= 1 + 2i0 + 3i5 and i6 <= 2 + 2i0 + 3i5 and "

1999

"3i5 <= 2 - 2i0 - i2 + 3i4 and i6 <= 2 + 2i0 + 3i1 and "

2000

"i0 <= -1 and i7 <= i2 + i3 - 3i4 - i6 and "

2001

"3i5 >= -2i0 - i2 + 3i4 }";

2002

bset = isl_basic_set_read_from_str(ctx, str);

2003

f = isl_basic_set_factorizer(bset);

2004

isl_basic_set_free(bset);

2005

isl_factorizer_free(f);

2006

if (!f)

2007

isl_die(ctx, isl_error_unknown,

2008

"failed to construct factorizer", return -1);

2009

2010

str = "{ [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12] : "

2011

"i12 <= 2 + i0 - i11 and 2i8 >= -i4 and i11 >= i1 and "

2012

"3i5 <= -i2 and 2i11 >= -i4 - 2i7 and i11 <= 3 + i0 + 3i9 and "

2013

"i11 <= -i4 - 2i7 and i12 >= -i10 and i2 >= -2 and "

2014

"i11 >= i1 + 3i10 and i11 >= 1 + i0 + 3i9 and "

2015

"i11 <= 1 - i4 - 2i8 and 6i6 <= 6 - i2 and 3i6 >= 1 - i2 and "

2016

"i11 <= 2 + i1 and i12 <= i4 + i11 and i12 >= i0 - i11 and "

2017

"3i5 >= -2 - i2 and i12 >= -1 + i4 + i11 and 3i3 <= 3 - i2 and "

2018

"9i6 <= 11 - i2 + 6i5 and 3i3 >= 1 - i2 and "

2019

"9i6 <= 5 - i2 + 6i3 and i12 <= -1 and i2 <= 0 }";

2020

bset = isl_basic_set_read_from_str(ctx, str);

2021

f = isl_basic_set_factorizer(bset);

2022

isl_basic_set_free(bset);

2023

isl_factorizer_free(f);

2024

if (!f)

2025

isl_die(ctx, isl_error_unknown,

2026

"failed to construct factorizer", return -1);

return 0;

}

static int check_injective(__isl_take isl_map *map, void *user)

2032

{

2033

int *injective = user;

2034

2035

*injective = isl_map_is_injective(map);

2036

isl_map_free(map);

2037

2038

if (*injective < 0 || !*injective)

return -1;

return 0;

}

int test_one_schedule(isl_ctx *ctx, const char *d, const char *w,

2045

const char *r, const char *s, int tilable, int parallel)

{

int i;

isl_union_set *D;

isl_union_map *W, *R, *S;

2050

isl_union_map *empty;

2051

isl_union_map *dep_raw, *dep_war, *dep_waw, *dep;

2052

isl_union_map *validity, *proximity;

2053

isl_union_map *schedule;

2054

isl_union_map *test;

2055

isl_union_set *delta;

2056

isl_union_set *domain;

2057

isl_set *delta_set;

2058

isl_set *slice;

2059

isl_set *origin;

2060

isl_schedule *sched;

2061

int is_nonneg, is_parallel, is_tilable, is_injection, is_complete;

2062

2063

D = isl_union_set_read_from_str(ctx, d);

2064

W = isl_union_map_read_from_str(ctx, w);

2065

R = isl_union_map_read_from_str(ctx, r);

2066

S = isl_union_map_read_from_str(ctx, s);

2067

2068

W = isl_union_map_intersect_domain(W, isl_union_set_copy(D));

2069

R = isl_union_map_intersect_domain(R, isl_union_set_copy(D));

2070

2071

empty = isl_union_map_empty(isl_union_map_get_space(S));

2072

isl_union_map_compute_flow(isl_union_map_copy(R),

2073

isl_union_map_copy(W), empty,

2074

isl_union_map_copy(S),

2075

&dep_raw, NULL, NULL, NULL);

2076

isl_union_map_compute_flow(isl_union_map_copy(W),

2077

isl_union_map_copy(W),

2078

isl_union_map_copy(R),

2079

isl_union_map_copy(S),

2080

&dep_waw, &dep_war, NULL, NULL);

2081

2082

dep = isl_union_map_union(dep_waw, dep_war);

2083

dep = isl_union_map_union(dep, dep_raw);

2084

validity = isl_union_map_copy(dep);

2085

proximity = isl_union_map_copy(dep);

2086

2087

sched = isl_union_set_compute_schedule(isl_union_set_copy(D),

2088

validity, proximity);

2089

schedule = isl_schedule_get_map(sched);

2090

isl_schedule_free(sched);

2091

isl_union_map_free(W);

2092

isl_union_map_free(R);

2093

isl_union_map_free(S);

2094

2095

is_injection = 1;

2096

isl_union_map_foreach_map(schedule, &check_injective, &is_injection);

2097

2098

domain = isl_union_map_domain(isl_union_map_copy(schedule));

2099

is_complete = isl_union_set_is_subset(D, domain);

2100

isl_union_set_free(D);

2101

isl_union_set_free(domain);

2102

2103

test = isl_union_map_reverse(isl_union_map_copy(schedule));

2104

test = isl_union_map_apply_range(test, dep);

2105

test = isl_union_map_apply_range(test, schedule);

2106

2107

delta = isl_union_map_deltas(test);

2108

if (isl_union_set_n_set(delta) == 0) {

is_tilable = 1;

is_parallel = 1;

is_nonneg = 1;

isl_union_set_free(delta);

2113

} else {

2114

delta_set = isl_set_from_union_set(delta);

2115

2116

slice = isl_set_universe(isl_set_get_space(delta_set));

2117

for (i = 0; i < tilable; ++i)

2118

slice = isl_set_lower_bound_si(slice, isl_dim_set, i, 0);

2119

is_tilable = isl_set_is_subset(delta_set, slice);

2120

isl_set_free(slice);

2121

2122

slice = isl_set_universe(isl_set_get_space(delta_set));

2123

for (i = 0; i < parallel; ++i)

2124

slice = isl_set_fix_si(slice, isl_dim_set, i, 0);

2125

is_parallel = isl_set_is_subset(delta_set, slice);

2126

isl_set_free(slice);

2127

2128

origin = isl_set_universe(isl_set_get_space(delta_set));

2129

for (i = 0; i < isl_set_dim(origin, isl_dim_set); ++i)

2130

origin = isl_set_fix_si(origin, isl_dim_set, i, 0);

2131

2132

delta_set = isl_set_union(delta_set, isl_set_copy(origin));

2133

delta_set = isl_set_lexmin(delta_set);

2134

2135

is_nonneg = isl_set_is_equal(delta_set, origin);

2136

2137

isl_set_free(origin);

2138

isl_set_free(delta_set);

2139

}

2140

2141

if (is_nonneg < 0 || is_parallel < 0 || is_tilable < 0 ||

2142

is_injection < 0 || is_complete < 0)

2143

return -1;

2144

if (!is_complete)

2145

isl_die(ctx, isl_error_unknown,

2146

"generated schedule incomplete", return -1);

2147

if (!is_injection)

2148

isl_die(ctx, isl_error_unknown,

2149

"generated schedule not injective on each statement",

2150

return -1);

2151

if (!is_nonneg)

2152

isl_die(ctx, isl_error_unknown,

2153

"negative dependences in generated schedule",

2154

return -1);

2155

if (!is_tilable)

2156

isl_die(ctx, isl_error_unknown,

2157

"generated schedule not as tilable as expected",

2158

return -1);

2159

if (!is_parallel)

2160

isl_die(ctx, isl_error_unknown,

2161

"generated schedule not as parallel as expected",

return -1);

return 0;

}

int test_special_schedule(isl_ctx *ctx, const char *domain,

2168

const char *validity, const char *proximity, const char *expected_sched)

2169

{

2170

isl_union_set *dom;

2171

isl_union_map *dep;

2172

isl_union_map *prox;

2173

isl_union_map *sched1, *sched2;

2174

isl_schedule *schedule;

2175

int equal;

2176

2177

dom = isl_union_set_read_from_str(ctx, domain);

2178

dep = isl_union_map_read_from_str(ctx, validity);

2179

prox = isl_union_map_read_from_str(ctx, proximity);

2180

schedule = isl_union_set_compute_schedule(dom, dep, prox);

2181

sched1 = isl_schedule_get_map(schedule);

2182

isl_schedule_free(schedule);

2183

2184

sched2 = isl_union_map_read_from_str(ctx, expected_sched);

2185

2186

equal = isl_union_map_is_equal(sched1, sched2);

2187

isl_union_map_free(sched1);

2188

isl_union_map_free(sched2);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "unexpected schedule",

return -1);

return 0;

}

int test_schedule(isl_ctx *ctx)

2200

{

2201

const char *D, *W, *R, *V, *P, *S;

2202

2203

/* Jacobi */

2204

D = "[T,N] -> { S1[t,i] : 1 <= t <= T and 2 <= i <= N - 1 }";

2205

W = "{ S1[t,i] -> a[t,i] }";

2206

R = "{ S1[t,i] -> a[t-1,i]; S1[t,i] -> a[t-1,i-1]; "

2207

"S1[t,i] -> a[t-1,i+1] }";

2208

S = "{ S1[t,i] -> [t,i] }";

2209

if (test_one_schedule(ctx, D, W, R, S, 2, 0) < 0)

2210

return -1;

2211

2212

/* Fig. 5 of CC2008 */

2213

D = "[N] -> { S_0[i, j] : i >= 0 and i <= -1 + N and j >= 2 and "

2214

"j <= -1 + N }";

2215

W = "[N] -> { S_0[i, j] -> a[i, j] : i >= 0 and i <= -1 + N and "

2216

"j >= 2 and j <= -1 + N }";

2217

R = "[N] -> { S_0[i, j] -> a[j, i] : i >= 0 and i <= -1 + N and "

2218

"j >= 2 and j <= -1 + N; "

2219

"S_0[i, j] -> a[i, -1 + j] : i >= 0 and i <= -1 + N and "

2220

"j >= 2 and j <= -1 + N }";

2221

S = "[N] -> { S_0[i, j] -> [0, i, 0, j, 0] }";

2222

if (test_one_schedule(ctx, D, W, R, S, 2, 0) < 0)

2223

return -1;

2224

2225

D = "{ S1[i] : 0 <= i <= 10; S2[i] : 0 <= i <= 9 }";

2226

W = "{ S1[i] -> a[i] }";

2227

R = "{ S2[i] -> a[i+1] }";

2228

S = "{ S1[i] -> [0,i]; S2[i] -> [1,i] }";

2229

if (test_one_schedule(ctx, D, W, R, S, 1, 1) < 0)

2230

return -1;

2231

2232

D = "{ S1[i] : 0 <= i < 10; S2[i] : 0 <= i < 10 }";

2233

W = "{ S1[i] -> a[i] }";

2234

R = "{ S2[i] -> a[9-i] }";

2235

S = "{ S1[i] -> [0,i]; S2[i] -> [1,i] }";

2236

if (test_one_schedule(ctx, D, W, R, S, 1, 1) < 0)

2237

return -1;

2238

2239

D = "[N] -> { S1[i] : 0 <= i < N; S2[i] : 0 <= i < N }";

2240

W = "{ S1[i] -> a[i] }";

2241

R = "[N] -> { S2[i] -> a[N-1-i] }";

2242

S = "{ S1[i] -> [0,i]; S2[i] -> [1,i] }";

2243

if (test_one_schedule(ctx, D, W, R, S, 1, 1) < 0)

2244

return -1;

2245

2246

D = "{ S1[i] : 0 < i < 10; S2[i] : 0 <= i < 10 }";

2247

W = "{ S1[i] -> a[i]; S2[i] -> b[i] }";

2248

R = "{ S2[i] -> a[i]; S1[i] -> b[i-1] }";

2249

S = "{ S1[i] -> [i,0]; S2[i] -> [i,1] }";

2250

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2251

return -1;

2252

2253

D = "[N] -> { S1[i] : 1 <= i <= N; S2[i,j] : 1 <= i,j <= N }";

2254

W = "{ S1[i] -> a[0,i]; S2[i,j] -> a[i,j] }";

2255

R = "{ S2[i,j] -> a[i-1,j] }";

2256

S = "{ S1[i] -> [0,i,0]; S2[i,j] -> [1,i,j] }";

2257

if (test_one_schedule(ctx, D, W, R, S, 2, 1) < 0)

2258

return -1;

2259

2260

D = "[N] -> { S1[i] : 1 <= i <= N; S2[i,j] : 1 <= i,j <= N }";

2261

W = "{ S1[i] -> a[i,0]; S2[i,j] -> a[i,j] }";

2262

R = "{ S2[i,j] -> a[i,j-1] }";

2263

S = "{ S1[i] -> [0,i,0]; S2[i,j] -> [1,i,j] }";

2264

if (test_one_schedule(ctx, D, W, R, S, 2, 1) < 0)

2265

return -1;

2266

2267

D = "[N] -> { S_0[]; S_1[i] : i >= 0 and i <= -1 + N; S_2[] }";

2268

W = "[N] -> { S_0[] -> a[0]; S_2[] -> b[0]; "

2269

"S_1[i] -> a[1 + i] : i >= 0 and i <= -1 + N }";

2270

R = "[N] -> { S_2[] -> a[N]; S_1[i] -> a[i] : i >= 0 and i <= -1 + N }";

2271

S = "[N] -> { S_1[i] -> [1, i, 0]; S_2[] -> [2, 0, 1]; "

2272

"S_0[] -> [0, 0, 0] }";

2273

if (test_one_schedule(ctx, D, W, R, S, 1, 0) < 0)

2274

return -1;

2275

ctx->opt->schedule_parametric = 0;

2276

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2277

return -1;

2278

ctx->opt->schedule_parametric = 1;

2279

2280

D = "[N] -> { S1[i] : 1 <= i <= N; S2[i] : 1 <= i <= N; "

2281

"S3[i,j] : 1 <= i,j <= N; S4[i] : 1 <= i <= N }";

2282

W = "{ S1[i] -> a[i,0]; S2[i] -> a[0,i]; S3[i,j] -> a[i,j] }";

2283

R = "[N] -> { S3[i,j] -> a[i-1,j]; S3[i,j] -> a[i,j-1]; "

2284

"S4[i] -> a[i,N] }";

2285

S = "{ S1[i] -> [0,i,0]; S2[i] -> [1,i,0]; S3[i,j] -> [2,i,j]; "

2286

"S4[i] -> [4,i,0] }";

2287

if (test_one_schedule(ctx, D, W, R, S, 2, 0) < 0)

2288

return -1;

2289

2290

D = "[N] -> { S_0[i, j] : i >= 1 and i <= N and j >= 1 and j <= N }";

2291

W = "[N] -> { S_0[i, j] -> s[0] : i >= 1 and i <= N and j >= 1 and "

2292

"j <= N }";

2293

R = "[N] -> { S_0[i, j] -> s[0] : i >= 1 and i <= N and j >= 1 and "

2294

"j <= N; "

2295

"S_0[i, j] -> a[i, j] : i >= 1 and i <= N and j >= 1 and "

2296

"j <= N }";

2297

S = "[N] -> { S_0[i, j] -> [0, i, 0, j, 0] }";

2298

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2299

return -1;

2300

2301

D = "[N] -> { S_0[t] : t >= 0 and t <= -1 + N; "

2302

" S_2[t] : t >= 0 and t <= -1 + N; "

2303

" S_1[t, i] : t >= 0 and t <= -1 + N and i >= 0 and "

2304

"i <= -1 + N }";

2305

W = "[N] -> { S_0[t] -> a[t, 0] : t >= 0 and t <= -1 + N; "

2306

" S_2[t] -> b[t] : t >= 0 and t <= -1 + N; "

2307

" S_1[t, i] -> a[t, 1 + i] : t >= 0 and t <= -1 + N and "

2308

"i >= 0 and i <= -1 + N }";

2309

R = "[N] -> { S_1[t, i] -> a[t, i] : t >= 0 and t <= -1 + N and "

2310

"i >= 0 and i <= -1 + N; "

2311

" S_2[t] -> a[t, N] : t >= 0 and t <= -1 + N }";

2312

S = "[N] -> { S_2[t] -> [0, t, 2]; S_1[t, i] -> [0, t, 1, i, 0]; "

2313

" S_0[t] -> [0, t, 0] }";

2314

2315

if (test_one_schedule(ctx, D, W, R, S, 2, 1) < 0)

2316

return -1;

2317

ctx->opt->schedule_parametric = 0;

2318

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2319

return -1;

2320

ctx->opt->schedule_parametric = 1;

2321

2322

D = "[N] -> { S1[i,j] : 0 <= i,j < N; S2[i,j] : 0 <= i,j < N }";

2323

S = "{ S1[i,j] -> [0,i,j]; S2[i,j] -> [1,i,j] }";

2324

if (test_one_schedule(ctx, D, "{}", "{}", S, 2, 2) < 0)

2325

return -1;

2326

2327

D = "[M, N] -> { S_1[i] : i >= 0 and i <= -1 + M; "

2328

"S_0[i, j] : i >= 0 and i <= -1 + M and j >= 0 and j <= -1 + N }";

2329

W = "[M, N] -> { S_0[i, j] -> a[j] : i >= 0 and i <= -1 + M and "

2330

"j >= 0 and j <= -1 + N; "

2331

"S_1[i] -> b[0] : i >= 0 and i <= -1 + M }";

2332

R = "[M, N] -> { S_0[i, j] -> a[0] : i >= 0 and i <= -1 + M and "

2333

"j >= 0 and j <= -1 + N; "

2334

"S_1[i] -> b[0] : i >= 0 and i <= -1 + M }";

2335

S = "[M, N] -> { S_1[i] -> [1, i, 0]; S_0[i, j] -> [0, i, 0, j, 0] }";

2336

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2337

return -1;

2338

2339

D = "{ S_0[i] : i >= 0 }";

2340

W = "{ S_0[i] -> a[i] : i >= 0 }";

2341

R = "{ S_0[i] -> a[0] : i >= 0 }";

2342

S = "{ S_0[i] -> [0, i, 0] }";

2343

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2344

return -1;

2345

2346

D = "{ S_0[i] : i >= 0; S_1[i] : i >= 0 }";

2347

W = "{ S_0[i] -> a[i] : i >= 0; S_1[i] -> b[i] : i >= 0 }";

2348

R = "{ S_0[i] -> b[0] : i >= 0; S_1[i] -> a[i] : i >= 0 }";

2349

S = "{ S_1[i] -> [0, i, 1]; S_0[i] -> [0, i, 0] }";

2350

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2351

return -1;

2352

2353

D = "[n] -> { S_0[j, k] : j <= -1 + n and j >= 0 and "

2354

"k <= -1 + n and k >= 0 }";

2355

W = "[n] -> { S_0[j, k] -> B[j] : j <= -1 + n and j >= 0 and " "k <= -1 + n and k >= 0 }";

2356

R = "[n] -> { S_0[j, k] -> B[j] : j <= -1 + n and j >= 0 and "

2357

"k <= -1 + n and k >= 0; "

2358

"S_0[j, k] -> B[k] : j <= -1 + n and j >= 0 and "

2359

"k <= -1 + n and k >= 0; "

2360

"S_0[j, k] -> A[k] : j <= -1 + n and j >= 0 and "

2361

"k <= -1 + n and k >= 0 }";

2362

S = "[n] -> { S_0[j, k] -> [2, j, k] }";

2363

ctx->opt->schedule_outer_zero_distance = 1;

2364

if (test_one_schedule(ctx, D, W, R, S, 0, 0) < 0)

2365

return -1;

2366

ctx->opt->schedule_outer_zero_distance = 0;

2367

2368

D = "{Stmt_for_body24[i0, i1, i2, i3]:"

2369

"i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 6 and i2 >= 2 and "

2370

"i2 <= 6 - i1 and i3 >= 0 and i3 <= -1 + i2;"

2371

"Stmt_for_body24[i0, i1, 1, 0]:"

2372

"i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 5;"

2373

"Stmt_for_body7[i0, i1, i2]:"

2374

"i0 >= 0 and i0 <= 1 and i1 >= 0 and i1 <= 7 and i2 >= 0 and "

2375

"i2 <= 7 }";

2376

2377

V = "{Stmt_for_body24[0, i1, i2, i3] -> "

2378

"Stmt_for_body24[1, i1, i2, i3]:"

2379

"i3 >= 0 and i3 <= -1 + i2 and i1 >= 0 and i2 <= 6 - i1 and "

2380

"i2 >= 1;"

2381

"Stmt_for_body24[0, i1, i2, i3] -> "

2382

"Stmt_for_body7[1, 1 + i1 + i3, 1 + i1 + i2]:"

2383

"i3 <= -1 + i2 and i2 <= 6 - i1 and i2 >= 1 and i1 >= 0 and "

2384

"i3 >= 0;"

2385

"Stmt_for_body24[0, i1, i2, i3] ->"

2386

"Stmt_for_body7[1, i1, 1 + i1 + i3]:"

2387

"i3 >= 0 and i2 <= 6 - i1 and i1 >= 0 and i3 <= -1 + i2;"

2388

"Stmt_for_body7[0, i1, i2] -> Stmt_for_body7[1, i1, i2]:"

2389

"(i2 >= 1 + i1 and i2 <= 6 and i1 >= 0 and i1 <= 4) or "

2390

"(i2 >= 3 and i2 <= 7 and i1 >= 1 and i2 >= 1 + i1) or "

2391

"(i2 >= 0 and i2 <= i1 and i2 >= -7 + i1 and i1 <= 7);"

2392

"Stmt_for_body7[0, i1, 1 + i1] -> Stmt_for_body7[1, i1, 1 + i1]:"

2393

"i1 <= 6 and i1 >= 0;"

2394

"Stmt_for_body7[0, 0, 7] -> Stmt_for_body7[1, 0, 7];"

2395

"Stmt_for_body7[i0, i1, i2] -> "

2396

"Stmt_for_body24[i0, o1, -1 + i2 - o1, -1 + i1 - o1]:"

2397

"i0 >= 0 and i0 <= 1 and o1 >= 0 and i2 >= 1 + i1 and "

2398

"o1 <= -2 + i2 and i2 <= 7 and o1 <= -1 + i1;"

2399

"Stmt_for_body7[i0, i1, i2] -> "

2400

"Stmt_for_body24[i0, i1, o2, -1 - i1 + i2]:"

2401

"i0 >= 0 and i0 <= 1 and i1 >= 0 and o2 >= -i1 + i2 and "

2402

"o2 >= 1 and o2 <= 6 - i1 and i2 >= 1 + i1 }";

2403

P = V;

2404

S = "{ Stmt_for_body24[i0, i1, i2, i3] -> "

2405

"[i0, 5i0 + i1, 6i0 + i1 + i2, 1 + 6i0 + i1 + i2 + i3, 1];"

2406

"Stmt_for_body7[i0, i1, i2] -> [0, 5i0, 6i0 + i1, 6i0 + i2, 0] }";

2407

2408

if (test_special_schedule(ctx, D, V, P, S) < 0)

2409

return -1;

2410

2411

D = "{ S_0[i, j] : i >= 1 and i <= 10 and j >= 1 and j <= 8 }";

2412

V = "{ S_0[i, j] -> S_0[i, 1 + j] : i >= 1 and i <= 10 and "

2413

"j >= 1 and j <= 7;"

2414

"S_0[i, j] -> S_0[1 + i, j] : i >= 1 and i <= 9 and "

2415

"j >= 1 and j <= 8 }";

2416

P = "{ }";

2417

S = "{ S_0[i, j] -> [i + j, j] }";

2418

ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;

2419

if (test_special_schedule(ctx, D, V, P, S) < 0)

2420

return -1;

2421

ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;

2422

2423

/* Fig. 1 from Feautrier's "Some Efficient Solutions..." pt. 2, 1992 */

2424

D = "[N] -> { S_0[i, j] : i >= 0 and i <= -1 + N and "

2425

"j >= 0 and j <= -1 + i }";

2426

V = "[N] -> { S_0[i, j] -> S_0[i, 1 + j] : j <= -2 + i and "

2427

"i <= -1 + N and j >= 0;"

2428

"S_0[i, -1 + i] -> S_0[1 + i, 0] : i >= 1 and "

2429

"i <= -2 + N }";

2430

P = "{ }";

2431

S = "{ S_0[i, j] -> [i, j] }";

2432

ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;

2433

if (test_special_schedule(ctx, D, V, P, S) < 0)

2434

return -1;

2435

ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;

2436

2437

/* Test both algorithms on a case with only proximity dependences. */

2438

D = "{ S[i,j] : 0 <= i <= 10 }";

2439

V = "{ }";

2440

P = "{ S[i,j] -> S[i+1,j] : 0 <= i,j <= 10 }";

2441

S = "{ S[i, j] -> [j, i] }";

2442

ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER;

2443

if (test_special_schedule(ctx, D, V, P, S) < 0)

2444

return -1;

2445

ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL;

2446

return test_special_schedule(ctx, D, V, P, S);

2447

}

2448

2449

int test_plain_injective(isl_ctx *ctx, const char *str, int injective)

2450

{

2451

isl_union_map *umap;

2452

int test;

2453

2454

umap = isl_union_map_read_from_str(ctx, str);

2455

test = isl_union_map_plain_is_injective(umap);

2456

isl_union_map_free(umap);

2457

if (test < 0)

2458

return -1;

2459

if (test == injective)

2460

return 0;

2461

if (injective)

2462

isl_die(ctx, isl_error_unknown,

2463

"map not detected as injective", return -1);

2464

else

2465

isl_die(ctx, isl_error_unknown,

2466

"map detected as injective", return -1);

2467

}

2468

2469

int test_injective(isl_ctx *ctx)

{

const char *str;

if (test_plain_injective(ctx, "{S[i,j] -> A[0]; T[i,j] -> B[1]}", 0))

2474

return -1;

2475

if (test_plain_injective(ctx, "{S[] -> A[0]; T[] -> B[0]}", 1))

2476

return -1;

2477

if (test_plain_injective(ctx, "{S[] -> A[0]; T[] -> A[1]}", 1))

2478

return -1;

2479

if (test_plain_injective(ctx, "{S[] -> A[0]; T[] -> A[0]}", 0))

2480

return -1;

2481

if (test_plain_injective(ctx, "{S[i] -> A[i,0]; T[i] -> A[i,1]}", 1))

2482

return -1;

2483

if (test_plain_injective(ctx, "{S[i] -> A[i]; T[i] -> A[i]}", 0))

2484

return -1;

2485

if (test_plain_injective(ctx, "{S[] -> A[0,0]; T[] -> A[0,1]}", 1))

2486

return -1;

2487

if (test_plain_injective(ctx, "{S[] -> A[0,0]; T[] -> A[1,0]}", 1))

2488

return -1;

2489

2490

str = "{S[] -> A[0,0]; T[] -> A[0,1]; U[] -> A[1,0]}";

2491

if (test_plain_injective(ctx, str, 1))

2492

return -1;

2493

str = "{S[] -> A[0,0]; T[] -> A[0,1]; U[] -> A[0,0]}";

2494

if (test_plain_injective(ctx, str, 0))

return -1;

return 0;

}

static int aff_plain_is_equal(__isl_keep isl_aff *aff, const char *str)

{

isl_aff *aff2;

int equal;

if (!aff)

return -1;

aff2 = isl_aff_read_from_str(isl_aff_get_ctx(aff), str);

2509

equal = isl_aff_plain_is_equal(aff, aff2);

2510

isl_aff_free(aff2);

return equal;

}

static int aff_check_plain_equal(__isl_keep isl_aff *aff, const char *str)

{

int equal;

equal = aff_plain_is_equal(aff, str);

if (equal < 0)

return -1;

if (!equal)

isl_die(isl_aff_get_ctx(aff), isl_error_unknown,

2524

"result not as expected", return -1);

return 0;

}

int test_aff(isl_ctx *ctx)

{

const char *str;

isl_set *set;

isl_space *space;

isl_local_space *ls;

isl_aff *aff;

int zero, equal;

space = isl_space_set_alloc(ctx, 0, 1);

2538

ls = isl_local_space_from_space(space);

2539

aff = isl_aff_zero_on_domain(ls);

2540

2541

aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);

2542

aff = isl_aff_scale_down_ui(aff, 3);

2543

aff = isl_aff_floor(aff);

2544

aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);

2545

aff = isl_aff_scale_down_ui(aff, 2);

2546

aff = isl_aff_floor(aff);

2547

aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);

2548

2549

str = "{ [10] }";

2550

set = isl_set_read_from_str(ctx, str);

2551

aff = isl_aff_gist(aff, set);

2552

2553

aff = isl_aff_add_constant_si(aff, -16);

2554

zero = isl_aff_plain_is_zero(aff);

isl_aff_free(aff);

if (zero < 0)

return -1;

if (!zero)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

2561

2562

aff = isl_aff_read_from_str(ctx, "{ [-1] }");

2563

aff = isl_aff_scale_down_ui(aff, 64);

2564

aff = isl_aff_floor(aff);

2565

equal = aff_check_plain_equal(aff, "{ [-1] }");

isl_aff_free(aff);

if (equal < 0)

return -1;

return 0;

}

int test_dim_max(isl_ctx *ctx)

{

int equal;

const char *str;

isl_set *set1, *set2;

isl_set *set;

isl_map *map;

isl_pw_aff *pwaff;

str = "[N] -> { [i] : 0 <= i <= min(N,10) }";

2583

set = isl_set_read_from_str(ctx, str);

2584

pwaff = isl_set_dim_max(set, 0);

2585

set1 = isl_set_from_pw_aff(pwaff);

2586

str = "[N] -> { [10] : N >= 10; [N] : N <= 9 and N >= 0 }";

2587

set2 = isl_set_read_from_str(ctx, str);

2588

equal = isl_set_is_equal(set1, set2);

2589

isl_set_free(set1);

2590

isl_set_free(set2);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

2595

2596

str = "[N] -> { [i] : 0 <= i <= max(2N,N+6) }";

2597

set = isl_set_read_from_str(ctx, str);

2598

pwaff = isl_set_dim_max(set, 0);

2599

set1 = isl_set_from_pw_aff(pwaff);

2600

str = "[N] -> { [6 + N] : -6 <= N <= 5; [2N] : N >= 6 }";

2601

set2 = isl_set_read_from_str(ctx, str);

2602

equal = isl_set_is_equal(set1, set2);

2603

isl_set_free(set1);

2604

isl_set_free(set2);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

2609

2610

str = "[N] -> { [i] : 0 <= i <= 2N or 0 <= i <= N+6 }";

2611

set = isl_set_read_from_str(ctx, str);

2612

pwaff = isl_set_dim_max(set, 0);

2613

set1 = isl_set_from_pw_aff(pwaff);

2614

str = "[N] -> { [6 + N] : -6 <= N <= 5; [2N] : N >= 6 }";

2615

set2 = isl_set_read_from_str(ctx, str);

2616

equal = isl_set_is_equal(set1, set2);

2617

isl_set_free(set1);

2618

isl_set_free(set2);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

2623

2624

str = "[N,M] -> { [i,j] -> [([i/16]), i%16, ([j/16]), j%16] : "

2625

"0 <= i < N and 0 <= j < M }";

2626

map = isl_map_read_from_str(ctx, str);

2627

set = isl_map_range(map);

2628

2629

pwaff = isl_set_dim_max(isl_set_copy(set), 0);

2630

set1 = isl_set_from_pw_aff(pwaff);

2631

str = "[N,M] -> { [([(N-1)/16])] : M,N > 0 }";

2632

set2 = isl_set_read_from_str(ctx, str);

2633

equal = isl_set_is_equal(set1, set2);

2634

isl_set_free(set1);

2635

isl_set_free(set2);

2636

2637

pwaff = isl_set_dim_max(isl_set_copy(set), 3);

2638

set1 = isl_set_from_pw_aff(pwaff);

2639

str = "[N,M] -> { [t] : t = min(M-1,15) and M,N > 0 }";

2640

set2 = isl_set_read_from_str(ctx, str);

2641

if (equal >= 0 && equal)

2642

equal = isl_set_is_equal(set1, set2);

2643

isl_set_free(set1);

2644

isl_set_free(set2);

isl_set_free(set);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

return 0;

}

int test_product(isl_ctx *ctx)

{

const char *str;

isl_set *set;

isl_union_set *uset1, *uset2;

int ok;

str = "{ A[i] }";

set = isl_set_read_from_str(ctx, str);

2665

set = isl_set_product(set, isl_set_copy(set));

2666

ok = isl_set_is_wrapping(set);

isl_set_free(set);

if (ok < 0)

return -1;

if (!ok)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

2672

2673

str = "{ [] }";

2674

uset1 = isl_union_set_read_from_str(ctx, str);

2675

uset1 = isl_union_set_product(uset1, isl_union_set_copy(uset1));

2676

str = "{ [[] -> []] }";

2677

uset2 = isl_union_set_read_from_str(ctx, str);

2678

ok = isl_union_set_is_equal(uset1, uset2);

2679

isl_union_set_free(uset1);

2680

isl_union_set_free(uset2);

if (ok < 0)

return -1;

if (!ok)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

return 0;

}

int test_equal(isl_ctx *ctx)

2690

{

2691

const char *str;

2692

isl_set *set, *set2;

2693

int equal;

2694

2695

str = "{ S_6[i] }";

2696

set = isl_set_read_from_str(ctx, str);

2697

str = "{ S_7[i] }";

2698

set2 = isl_set_read_from_str(ctx, str);

2699

equal = isl_set_is_equal(set, set2);

2700

isl_set_free(set);

2701

isl_set_free(set2);

if (equal < 0)

return -1;

if (equal)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

return 0;

}

static int test_plain_fixed(isl_ctx *ctx, __isl_take isl_map *map,

2711

enum isl_dim_type type, unsigned pos, int fixed)

{

int test;

test = isl_map_plain_is_fixed(map, type, pos, NULL);

isl_map_free(map);

if (test < 0)

return -1;

if (test == fixed)

return 0;

if (fixed)

isl_die(ctx, isl_error_unknown,

2723

"map not detected as fixed", return -1);

2724

else

2725

isl_die(ctx, isl_error_unknown,

2726

"map detected as fixed", return -1);

2727

}

2728

2729

int test_fixed(isl_ctx *ctx)

{

const char *str;

isl_map *map;

str = "{ [i] -> [i] }";

2735

map = isl_map_read_from_str(ctx, str);

2736

if (test_plain_fixed(ctx, map, isl_dim_out, 0, 0))

2737

return -1;

2738

str = "{ [i] -> [1] }";

2739

map = isl_map_read_from_str(ctx, str);

2740

if (test_plain_fixed(ctx, map, isl_dim_out, 0, 1))

2741

return -1;

2742

str = "{ S_1[p1] -> [o0] : o0 = -2 and p1 >= 1 and p1 <= 7 }";

2743

map = isl_map_read_from_str(ctx, str);

2744

if (test_plain_fixed(ctx, map, isl_dim_out, 0, 1))

2745

return -1;

2746

map = isl_map_read_from_str(ctx, str);

2747

map = isl_map_neg(map);

2748

if (test_plain_fixed(ctx, map, isl_dim_out, 0, 1))

return -1;

return 0;

}

int test_vertices(isl_ctx *ctx)

2755

{

2756

const char *str;

2757

isl_basic_set *bset;

2758

isl_vertices *vertices;

2759

2760

str = "{ A[t, i] : t = 12 and i >= 4 and i <= 12 }";

2761

bset = isl_basic_set_read_from_str(ctx, str);

2762

vertices = isl_basic_set_compute_vertices(bset);

2763

isl_basic_set_free(bset);

2764

isl_vertices_free(vertices);

if (!vertices)

return -1;

str = "{ A[t, i] : t = 14 and i = 1 }";

2769

bset = isl_basic_set_read_from_str(ctx, str);

2770

vertices = isl_basic_set_compute_vertices(bset);

2771

isl_basic_set_free(bset);

2772

isl_vertices_free(vertices);

if (!vertices)

return -1;

return 0;

}

int test_union_pw(isl_ctx *ctx)

{

int equal;

const char *str;

isl_union_set *uset;

2784

isl_union_pw_qpolynomial *upwqp1, *upwqp2;

2785

2786

str = "{ [x] -> x^2 }";

2787

upwqp1 = isl_union_pw_qpolynomial_read_from_str(ctx, str);

2788

upwqp2 = isl_union_pw_qpolynomial_copy(upwqp1);

2789

uset = isl_union_pw_qpolynomial_domain(upwqp1);

2790

upwqp1 = isl_union_pw_qpolynomial_copy(upwqp2);

2791

upwqp1 = isl_union_pw_qpolynomial_intersect_domain(upwqp1, uset);

2792

equal = isl_union_pw_qpolynomial_plain_is_equal(upwqp1, upwqp2);

2793

isl_union_pw_qpolynomial_free(upwqp1);

2794

isl_union_pw_qpolynomial_free(upwqp2);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

return 0;

}

int test_output(isl_ctx *ctx)

{

char *s;

const char *str;

isl_pw_aff *pa;

isl_printer *p;

int equal;

str = "[x] -> { [1] : x % 4 <= 2; [2] : x = 3 }";

2812

pa = isl_pw_aff_read_from_str(ctx, str);

2813

2814

p = isl_printer_to_str(ctx);

2815

p = isl_printer_set_output_format(p, ISL_FORMAT_C);

2816

p = isl_printer_print_pw_aff(p, pa);

2817

s = isl_printer_get_str(p);

2818

isl_printer_free(p);

2819

isl_pw_aff_free(pa);

2820

equal = !strcmp(s, "(2 - x + 4*floord(x, 4) >= 0) ? (1) : 2");

free(s);

if (equal < 0)

return -1;

if (!equal)

isl_die(ctx, isl_error_unknown, "unexpected result", return -1);

return 0;

}

int test_sample(isl_ctx *ctx)

2831

{

2832

const char *str;

2833

isl_basic_set *bset1, *bset2;

2834

int empty, subset;

2835

2836

str = "{ [a, b, c, d, e, f, g, h, i, j, k] : "

2837

"3i >= 1073741823b - c - 1073741823e + f and c >= 0 and "

2838

"3i >= -1 + 3221225466b + c + d - 3221225466e - f and "

2839

"2e >= a - b and 3e <= 2a and 3k <= -a and f <= -1 + a and "

2840

"3i <= 4 - a + 4b + 2c - e - 2f and 3k <= -a + c - f and "

2841

"3h >= -2 + a and 3g >= -3 - a and 3k >= -2 - a and "

2842

"3i >= -2 - a - 2c + 3e + 2f and 3h <= a + c - f and "

2843

"3h >= a + 2147483646b + 2c - 2147483646e - 2f and "

2844

"3g <= -1 - a and 3i <= 1 + c + d - f and a <= 1073741823 and "

2845

"f >= 1 - a + 1073741822b + c + d - 1073741822e and "

2846

"3i >= 1 + 2b - 2c + e + 2f + 3g and "

2847

"1073741822f <= 1073741822 - a + 1073741821b + 1073741822c +"

2848

"d - 1073741821e and "

2849

"3j <= 3 - a + 3b and 3g <= -2 - 2b + c + d - e - f and "

2850

"3j >= 1 - a + b + 2e and "

2851

"3f >= -3 + a + 3221225462b + 3c + d - 3221225465e and "

2852

"3i <= 4 - a + 4b - e and "

2853

"f <= 1073741822 + 1073741822b - 1073741822e and 3h <= a and "

2854

"f >= 0 and 2e <= 4 - a + 5b - d and 2e <= a - b + d and "

2855

"c <= -1 + a and 3i >= -2 - a + 3e and "

2856

"1073741822e <= 1073741823 - a + 1073741822b + c and "

2857

"3g >= -4 + 3221225464b + 3c + d - 3221225467e - 3f and "

2858

"3i >= -1 + 3221225466b + 3c + d - 3221225466e - 3f and "

2859

"1073741823e >= 1 + 1073741823b - d and "

2860

"3i >= 1073741823b + c - 1073741823e - f and "

2861

"3i >= 1 + 2b + e + 3g }";

2862

bset1 = isl_basic_set_read_from_str(ctx, str);

2863

bset2 = isl_basic_set_sample(isl_basic_set_copy(bset1));

2864

empty = isl_basic_set_is_empty(bset2);

2865

subset = isl_basic_set_is_subset(bset2, bset1);

2866

isl_basic_set_free(bset1);

2867

isl_basic_set_free(bset2);

2868

if (empty)

2869

isl_die(ctx, isl_error_unknown, "point not found", return -1);

2870

if (!subset)

2871

isl_die(ctx, isl_error_unknown, "bad point found", return -1);

return 0;

}

int test_fixed_power(isl_ctx *ctx)

{

const char *str;

isl_map *map;

isl_int exp;

int equal;

isl_int_init(exp);

str = "{ [i] -> [i + 1] }";

2885

map = isl_map_read_from_str(ctx, str);

2886

isl_int_set_si(exp, 23);

2887

map = isl_map_fixed_power(map, exp);

2888

equal = map_check_equal(map, "{ [i] -> [i + 23] }");

2889

isl_int_clear(exp);

isl_map_free(map);

if (equal < 0)

return -1;

return 0;

}

int test_slice(isl_ctx *ctx)

{

const char *str;

isl_map *map;

int equal;

str = "{ [i] -> [j] }";

2904

map = isl_map_read_from_str(ctx, str);

2905

map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);

2906

equal = map_check_equal(map, "{ [i] -> [i] }");

isl_map_free(map);

if (equal < 0)

return -1;

str = "{ [i] -> [j] }";

2912

map = isl_map_read_from_str(ctx, str);

2913

map = isl_map_equate(map, isl_dim_in, 0, isl_dim_in, 0);

2914

equal = map_check_equal(map, "{ [i] -> [j] }");

isl_map_free(map);

if (equal < 0)

return -1;

str = "{ [i] -> [j] }";

2920

map = isl_map_read_from_str(ctx, str);

2921

map = isl_map_oppose(map, isl_dim_in, 0, isl_dim_out, 0);

2922

equal = map_check_equal(map, "{ [i] -> [-i] }");

isl_map_free(map);

if (equal < 0)

return -1;

str = "{ [i] -> [j] }";

2928

map = isl_map_read_from_str(ctx, str);

2929

map = isl_map_oppose(map, isl_dim_in, 0, isl_dim_in, 0);

2930

equal = map_check_equal(map, "{ [0] -> [j] }");

isl_map_free(map);

if (equal < 0)

return -1;

str = "{ [i] -> [j] }";

2936

map = isl_map_read_from_str(ctx, str);

2937

map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_out, 0);

2938

equal = map_check_equal(map, "{ [i] -> [j] : i > j }");

isl_map_free(map);

if (equal < 0)

return -1;

str = "{ [i] -> [j] }";

2944

map = isl_map_read_from_str(ctx, str);

2945

map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_in, 0);

2946

equal = map_check_equal(map, "{ [i] -> [j] : false }");

isl_map_free(map);

if (equal < 0)

return -1;

return 0;

}

struct {

const char *name;

int (*fn)(isl_ctx *ctx);

2957

} tests [] = {

2958

{ "slice", &test_slice },

2959

{ "fixed power", &test_fixed_power },

2960

{ "sample", &test_sample },

2961

{ "output", &test_output },

2962

{ "vertices", &test_vertices },

2963

{ "fixed", &test_fixed },

2964

{ "equal", &test_equal },

2965

{ "product", &test_product },

2966

{ "dim_max", &test_dim_max },

2967

{ "affine", &test_aff },

2968

{ "injective", &test_injective },

2969

{ "schedule", &test_schedule },

2970

{ "union_pw", &test_union_pw },

2971

{ "parse", &test_parse },

2972

{ "single-valued", &test_sv },

2973

{ "affine hull", &test_affine_hull },

2974

{ "coalesce", &test_coalesce },

2975

{ "factorize", &test_factorize },

};

int main()

{

int i;

struct isl_ctx *ctx;

2982

2983

srcdir = getenv("srcdir");

2984

assert(srcdir);

2985

2986

ctx = isl_ctx_alloc();

2987

for (i = 0; i < ARRAY_SIZE(tests); ++i) {

2988

printf("%s\n", tests[i].name);

2989

if (tests[i].fn(ctx) < 0)

goto error;

}

test_subset(ctx);

test_lift(ctx);

test_bound(ctx);

test_union(ctx);

test_split_periods(ctx);

2997

test_pwqp(ctx);

2998

test_lex(ctx);

2999

test_bijective(ctx);

test_dep(ctx);

test_read(ctx);

test_bounded(ctx);

test_construction(ctx);

3004

test_dim(ctx);

3005

test_div(ctx);

3006

test_application(ctx);

3007

test_convex_hull(ctx);

test_gist(ctx);

test_closure(ctx);

test_lexmin(ctx);

isl_ctx_free(ctx);

return 0;

error:

isl_ctx_free(ctx);

return -1;

}

nexmon – Blame information for rev 1