libpcp/pcp_expr_canonicalizer.cc

   1 // Copyright (C) 2009 Free Software Foundation, Inc.
   2 // Contributed by Jan Sjodin <jan.sjodin@amd.com>.
   3
   4 // This file is part of the Polyhedral Compilation Package Library (libpcp).
   5
   6 // Libpcp is free software; you can redistribute it and/or modify it
   7 // under the terms of the GNU Lesser General Public License as published by
   8 // the Free Software Foundation; either version 2.1 of the License, or
   9 // (at your option) any later version.
  10
  11 // Libpcp is distributed in the hope that it will be useful, but WITHOUT ANY
  12 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13 // FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  14 // more details.
  15
  16 // You should have received a copy of the GNU Lesser General Public License
  17 // along with libpcp; see the file COPYING.LIB.  If not, write to the
  18 // Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  19 // MA 02110-1301, USA.
  20
  21 // As a special exception, if you link this library with other files, some
  22 // of which are compiled with GCC, to produce an executable, this library
  23 // does not by itself cause the resulting executable to be covered by the
  24 // GNU General Public License.  This exception does not however invalidate
  25 // any other reasons why the executable file might be covered by the GNU
  26 // General Public License.
  27
  28 #include "pcp_error.h"
  29 #include "pcp_stack.h"
  30 #include "pcp_expr_canonicalizer.h"
  31 #include "pcp_emitter.h"
  32
  33 // Creates an expression:
  34 // +(*(0, iv_0), ... *(0, iv_n), *(0, param_0), ..., *(0, param_m), 0)
  35 PcpExpr*
  36 PcpScalarContextStack::createBaseExpr()
  37 {
  38   int size = this->getSize();
  39   PcpArithBuilder* builder = new PcpArithBuilder();
  40   builder->setOperator(PcpArithOperator::add());
  41   for(int i = 0; i < size; i++)
  42     {
  43       PcpExpr* scalar = this->peek(i);
  44       PcpArith* mulZeroScalar = PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
  45                                                                new PcpConstant(0),
  46                                                                scalar);
  47       builder->addOperand(mulZeroScalar);
  48     }
  49   builder->addOperand(new PcpConstant(0));
  50   PcpArith* zeros = builder->createArith();
  51   delete builder;
  52   //  printf("Zero expr: %s\n", PcpEmitter::pcpExprToString(zeros));
  53   return zeros;
  54 }
  55
  56 PcpScalarContextStack::PcpScalarContextStack(PcpScop* scop) : PcpListStack<PcpExpr*>()
  57 {
  58   PcpIterator<PcpParameter*>* iter = scop->getParametersIterator();
  59   for(;iter->hasNext(); iter->next())
  60     {
  61       this->push(iter->get());
  62     }
  63 }
  64
  65
  66 void
  67 PcpExprCanonicalizer::setScalarOrder(PcpScalarOrder* scalarOrder)
  68 {
  69   this->scalarOrder = scalarOrder;
  70 }
  71
  72 PcpScalarOrder*
  73 PcpExprCanonicalizer::getScalarOrder()
  74 {
  75   return this->scalarOrder;
  76 }
  77
  78 void
  79 PcpExprCanonicalizer::setScalarContextStack(PcpScalarContextStack* scalarContextStack)
  80 {
  81   this->scalarContextStack = scalarContextStack;
  82 }
  83
  84 PcpScalarContextStack*
  85 PcpExprCanonicalizer::getScalarContextStack()
  86 {
  87   return this->scalarContextStack;
  88 }
  89
  90
  91 PcpExpr*
  92 PcpExprCanonicalizer::stripMultiplier(PcpExpr* expr)
  93 {
  94   pcpAssert(!expr->isArith() || expr->toArith()->getOperator().isMultiply());
  95   return expr->isArith() ? expr->toArith()->getOperand(1) : expr;
  96 }
  97
  98 bool
  99 PcpExprCanonicalizer::equal(PcpExpr* expr1, PcpExpr* expr2)
 100 {
 101   return this->getScalarOrder()->equal(this->stripMultiplier(expr1),
 102                                        this->stripMultiplier(expr2));
 103 }
 104
 105 bool
 106 PcpExprCanonicalizer::less(PcpExpr* expr1, PcpExpr* expr2)
 107 {
 108   return this->getScalarOrder()->less(this->stripMultiplier(expr1),
 109                                       this->stripMultiplier(expr2));
 110 }
 111
 112 PcpConstant*
 113 PcpExprCanonicalizer::negateConstant(PcpConstant* constant)
 114 {
 115   return new PcpConstant(-(constant->getValue()));
 116 }
 117
 118 PcpConstant*
 119 PcpExprCanonicalizer::addConstants(PcpConstant* constant1,
 120                               PcpConstant* constant2)
 121 {
 122   return new PcpConstant(constant1->getValue() +
 123                          constant2->getValue());
 124 }
 125
 126 PcpConstant*
 127 PcpExprCanonicalizer::addConstants(PcpConstant* constant1,
 128                               int constant2)
 129 {
 130   return new PcpConstant(constant1->getValue() +
 131                          constant2);
 132 }
 133
 134 PcpConstant*
 135 PcpExprCanonicalizer::addConstants(int constant1,
 136                               int constant2)
 137 {
 138   return new PcpConstant(constant1 + constant2);
 139 }
 140
 141 PcpExpr*
 142 PcpExprCanonicalizer::addTerms(PcpExpr* expr1, PcpExpr* expr2)
 143 {
 144   PcpExpr* result;
 145   if(expr1->isConstant())
 146     {
 147       result = this->addConstants(expr1->toConstant(), expr2->toConstant());
 148     }
 149   else if(expr1->isArith() && !expr2->isArith())
 150     result = addTerms(expr2, expr1);
 151 //   else if(!expr1->isArith())
 152 //     {
 153 //       pcpAssert(false); // This case is no longer used since we always create *(1,x)
 154 //       PcpExpr* multiplier = NULL;
 155 //       if(!expr2->isArith())
 156 //      {
 157 //        multiplier = this->addConstants(1,1);
 158 //      }
 159 //       else
 160 //      multiplier = this->addConstants(expr2->toArith()->getOperand(0)->toConstant(), 1);
 161 //       result = PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
 162 //                                            multiplier,
 163 //                                            expr1);
 164 //     }
 165   else // Iv is multiply
 166     {
 167       PcpExpr* multiplier =
 168         this->addConstants(expr1->toArith()->getOperand(0)->toConstant(),
 169                                expr2->toArith()->getOperand(0)->toConstant());
 170       result = PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
 171                                     multiplier,
 172                                     expr1->toArith()->getOperand(1));
 173     }
 174
 175   return result;
 176 }
 177
 178 // Merges normalized arithmetic expressions, where scalars are also
 179 // wrapped with a + operator, e.g. +(42).
 180 PcpArith*
 181 PcpExprCanonicalizer::addSums(PcpArith* sum1, PcpArith* sum2)
 182 {
 183   pcpAssert(sum1 != NULL && sum2 != NULL);
 184   pcpAssert(sum1->getOperator().isAdd());
 185   pcpAssert(sum2->getOperator().isAdd());
 186
 187   //  printf("      Sum1: %s\n", PcpEmitter::pcpArithToString(sum1));
 188   //  printf("      Sum2: %s\n", PcpEmitter::pcpArithToString(sum2));
 189
 190   PcpArithBuilder* builder = new PcpArithBuilder();
 191   builder->setOperator(PcpArithOperator::add());
 192
 193   PcpIterator<PcpExpr*>* iter1 = sum1->getOperandsIterator();
 194   PcpIterator<PcpExpr*>* iter2 = sum2->getOperandsIterator();
 195
 196   while(iter1->hasNext() || iter2->hasNext())
 197     {
 198       PcpExpr* newOperand = NULL;
 199       if(!iter1->hasNext())
 200         {
 201           newOperand = iter2->get();
 202           iter2->next();
 203         }
 204       else if(!iter2->hasNext())
 205         {
 206           newOperand = iter1->get();
 207           iter1->next();
 208         }
 209       else
 210         {
 211           PcpExpr* expr1 = iter1->get();
 212           PcpExpr* expr2 = iter2->get();
 213           //      printf("Expr1: %s\n", PcpEmitter::pcpExprToString(expr1));
 214           // printf("Expr2: %s\n", PcpEmitter::pcpExprToString(expr2));
 215           if(this->equal(expr1, expr2))
 216             {
 217               newOperand = this->addTerms(expr1, expr2);
 218               iter1->next();
 219               iter2->next();
 220               //              printf("Equal: add them\n");
 221             }
 222           else if(this->less(expr1, expr2))
 223             {
 224               newOperand = iter1->get();
 225               iter1->next();
 226               //              printf("Less: Push expr 1\n");
 227             }
 228           else
 229             {
 230               newOperand = iter2->get();
 231               iter2->next();
 232               //              printf("Greater: Push expr 2\n");
 233             }
 234         }
 235
 236       // Add 0 to make expr complete (commented out expression)
 237       if(newOperand != NULL) // &&
 238         //(!newOperand->isConstant() ||
 239         //newOperand->toConstant()->getValue() != 0))
 240         builder->addOperand(newOperand);
 241     }
 242
 243   PcpArith* result = builder->createArith();
 244   delete builder;
 245   delete iter1;
 246   delete iter2;
 247
 248   //  printf("Sum Result: %s\n", PcpEmitter::pcpArithToString(result));
 249   return result;
 250 }
 251
 252 PcpArith*
 253 PcpExprCanonicalizer::createUnaryArith(PcpArithOperator oper, PcpExpr* expr)
 254 {
 255   PcpArithBuilder* builder = new PcpArithBuilder();
 256
 257   builder->setOperator(oper);
 258   builder->addOperand(expr);
 259
 260   PcpArith* result = builder->createArith();
 261   delete builder;
 262   return result;
 263 }
 264
 265 PcpArith*
 266 PcpExprCanonicalizer::createUnaryPlus(PcpExpr* expr)
 267 {
 268   return createUnaryArith(PcpArithOperator::add(), expr);
 269 }
 270
 271 PcpArith*
 272 PcpExprCanonicalizer::createUnaryMinus(PcpExpr* expr)
 273 {
 274   return createUnaryArith(PcpArithOperator::subtract(), expr);
 275 }
 276
 277 PcpConstant*
 278 PcpExprCanonicalizer::getCanonicalConstant(PcpArith* expr)
 279 {
 280   return (expr->getOperator().isAdd() && expr->getNumOperands() == 1 &&
 281           expr->getOperand(0)->isConstant())
 282     ? expr->getOperand(0)->toConstant()
 283     : NULL;
 284 }
 285
 286 PcpConstant*
 287 PcpExprCanonicalizer::multiplyConstants(PcpConstant* constant1, PcpConstant* constant2)
 288 {
 289   return new PcpConstant(constant1->getValue() * constant2->getValue());
 290 }
 291
 292 PcpArith*
 293 PcpExprCanonicalizer::multiplyConstMul(PcpConstant* multiplier, PcpArith* multiply)
 294 {
 295   pcpAssert(multiply->getOperator().isMultiply());
 296   PcpConstant* constant = multiply->getOperand(0)->toConstant();
 297   PcpConstant* newConstant = this->multiplyConstants(multiplier, constant);
 298   return PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
 299                                           newConstant,
 300                                           multiply->getOperand(1));
 301 }
 302
 303 PcpArith*
 304 PcpExprCanonicalizer::multiplyScalar(PcpConstant* constant, PcpExpr* scalar)
 305 {
 306   return PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
 307                                         constant,
 308                                         scalar);
 309 }
 310
 311 PcpArith*
 312 PcpExprCanonicalizer::multiplyFactors(PcpConstant* multiplier, PcpArith* sum)
 313 {
 314
 315   // Don't simplify anything since we want the full expressions
 316   /*
 317   if(multiplier->getValue() == 0)
 318     return this->createUnaryPlus(multiplier);
 319   if(multiplier->getValue() == 1)
 320     return sum;
 321   */
 322
 323   PcpIterator<PcpExpr*>* iter = sum->getOperandsIterator();
 324   PcpArithBuilder* builder = new PcpArithBuilder();
 325
 326   builder->setOperator(PcpArithOperator::add());
 327
 328   for(; iter->hasNext(); iter->next())
 329     {
 330       PcpExpr* term = iter->get();
 331       if(term->isArith())
 332         {
 333           PcpArith* newTerm = this->multiplyConstMul(multiplier, term->toArith());
 334           builder->addOperand(newTerm);
 335         }
 336       else if(term->isConstant())
 337         {
 338           PcpConstant* newConstant = this->multiplyConstants(multiplier, term->toConstant());
 339           builder->addOperand(newConstant);
 340         }
 341       else
 342         {
 343           PcpArith* newTerm = this->multiplyScalar(multiplier, term);
 344           builder->addOperand(newTerm);
 345         }
 346     }
 347
 348   PcpArith* result = builder->createArith();
 349   delete builder;
 350   return result;
 351 }
 352
 353 bool
 354 PcpExprCanonicalizer::sameScalarBase(PcpArith* factor1, PcpArith* factor2)
 355 {
 356   return (factor1->getNumOperands() == 2 &&
 357           factor2->getNumOperands() == 2 &&
 358           factor1->getOperator().isMultiply() &&
 359           factor2->getOperator().isMultiply() &&
 360           factor1->getOperand(0)->isConstant() &&
 361           factor2->getOperand(0)->isConstant() &&
 362           factor1->getOperand(1) == factor2->getOperand(1));
 363 }
 364
 365 PcpArith*
 366 PcpExprCanonicalizer::multiplyFactors(PcpArith* factor1, PcpArith* factor2)
 367 {
 368   PcpConstant* constant1 = this->getCanonicalConstant(factor1);
 369   PcpConstant* constant2 = this->getCanonicalConstant(factor2);
 370
 371   pcpAssert(constant1 != NULL || constant2 != NULL
 372             || sameScalarBase(factor1, factor2));
 373
 374   bool nonConstants = constant1 == NULL && constant2 == NULL;
 375   bool factor1isConst = constant1 != NULL;
 376   bool factor2isConst = constant2 != NULL;
 377
 378   PcpConstant* multiplier =
 379         nonConstants ? factor1->getOperand(0)->toConstant()
 380     : factor1isConst ? constant1
 381     : constant2;
 382
 383   PcpArith* sum = !factor2isConst ? factor2 : factor1;
 384
 385   return this->multiplyFactors(multiplier, sum);
 386 }
 387
 388 PcpArith*
 389 PcpExprCanonicalizer::negateExpr(PcpArith* canonicalizedExpr)
 390 {
 391   PcpIterator<PcpExpr*>* iter = canonicalizedExpr->getOperandsIterator();
 392   PcpArithBuilder* builder = new PcpArithBuilder();
 393   builder->setOperator(PcpArithOperator::add());
 394   for(;iter->hasNext(); iter->next())
 395     {
 396       PcpExpr* operand = iter->get();
 397       if(operand->isArith())
 398         {
 399           PcpArith* arith = operand->toArith();
 400           PcpArithOperator oper = arith->getOperator();
 401           pcpAssert(oper.isMultiply());
 402           builder->addOperand(PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
 403                                                             this->negateConstant(arith->getOperand(0)->toConstant()),
 404                                                             arith->getOperand(1)));
 405         }
 406       else if(operand->isConstant())
 407         builder->addOperand(this->negateConstant(operand->toConstant()));
 408       else
 409         builder->addOperand(PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
 410                                                            new PcpConstant(-1),
 411                                                            operand));
 412
 413     }
 414   PcpArith* result = builder->createArith();
 415   delete builder;
 416   delete iter;
 417   return result;
 418 }
 419
 420 PcpArith*
 421 PcpExprCanonicalizer::canonicalizeExpr(PcpExpr* expr)
 422 {
 423   if(!expr->isArith())
 424     return createUnaryPlus(expr->isConstant()
 425                            ? expr
 426                            : PcpArith::pcpArithBinaryCreate(PcpArithOperator::multiply(),
 427                                                             new PcpConstant(1),
 428                                                             expr));
 429   PcpArith* arith = expr->toArith();
 430   PcpArithOperator oper = arith->getOperator();
 431
 432   if(arith->getNumOperands() == 1)
 433     return oper.isSubtract() ? negateExpr(canonicalizeExpr(arith->getOperand(0)))
 434                              : arith;
 435   if(oper.isSubtract() && arith->getNumOperands() == 2)
 436     {
 437       PcpArith* lhs = this->negateExpr(this->canonicalizeExpr(arith->getOperand(1)));
 438       return addSums(this->canonicalizeExpr(arith->getOperand(0)), lhs);
 439     }
 440   else
 441     {
 442       PcpIterator<PcpExpr*>* iter = arith->getOperandsIterator();
 443       PcpArith* result = this->canonicalizeExpr(iter->get());
 444
 445       iter->next();
 446       for(;iter->hasNext();iter->next())
 447         {
 448           PcpExpr* operand = iter->get();
 449           PcpArith* canonicalizedOperand = this->canonicalizeExpr(operand);
 450           if(oper.isAdd())
 451             result = this->addSums(canonicalizedOperand, result);
 452           else if(oper.isMultiply())
 453             result = this->multiplyFactors(canonicalizedOperand, result);
 454           else
 455             pcpAssert(false);
 456         }
 457       return result;
 458     }
 459 }
 460
 461 PcpArith*
 462 PcpExprCanonicalizer::canonicalizeExprWithBase(PcpExpr* expr)
 463 {
 464   PcpExpr* base = this->getCanonicalizationBase();
 465   if(base)
 466     expr = PcpArith::pcpArithBinaryCreate(PcpArithOperator::add(), base, expr);
 467   return canonicalizeExpr(expr);
 468 }
 469
 470 PcpCompare*
 471 PcpExprCanonicalizer::canonicalizeCompare(PcpCompare* compare)
 472 {
 473   PcpCompareOperator oper = compare->getOperator();
 474   PcpExpr* lhs = compare->getLhs();
 475   PcpExpr* rhs = compare->getRhs();
 476
 477   //  printf("Lhs: %s\n", PcpEmitter::pcpExprToString(lhs));
 478   // printf("Rhs: %s\n", PcpEmitter::pcpExprToString(rhs));
 479
 480   PcpArith* canonLhs = canonicalizeExprWithBase(lhs);
 481   PcpArith* canonRhs = canonicalizeExprWithBase(rhs);
 482
 483   //  printf("canonLhs: %s\n", PcpEmitter::pcpExprToString(canonLhs));
 484   // printf("canonRhs: %s\n", PcpEmitter::pcpExprToString(canonRhs));
 485
 486   if(canonRhs->isConstant() && canonRhs->toConstant()->getValue() == 0)
 487     return compare;
 488   else
 489     {
 490       PcpArith* negRhs = negateExpr(canonRhs);
 491       PcpArith* newLhs = addSums(canonLhs, negRhs);
 492       return new PcpCompare(compare->getOperator(),
 493                             newLhs,
 494                             createUnaryPlus(new PcpConstant(0)));
 495     }
 496 }
 497
 498 PcpBoolArith*
 499 PcpExprCanonicalizer::createUnaryOr(PcpBoolExpr* boolExpr)
 500 {
 501   PcpBoolArithBuilder* builder = new PcpBoolArithBuilder();
 502
 503   builder->setOperator(PcpBoolArithOperator::boolOr());
 504   builder->addOperand(boolExpr);
 505
 506   PcpBoolArith* result = builder->createBoolArith();
 507   delete builder;
 508   return result;
 509 }
 510
 511 void
 512 PcpExprCanonicalizer::appendOperandsToBuilder(PcpBoolArithBuilder* builder,
 513                                               PcpBoolArith* boolArith)
 514 {
 515   PcpIterator<PcpBoolExpr*>* iter = boolArith->getOperandsIterator();
 516   for(;iter->hasNext(); iter->next())
 517     {
 518       builder->addOperand(iter->get());
 519     }
 520   delete iter;
 521 }
 522
 523 PcpBoolArith*
 524 PcpExprCanonicalizer::mergeOr(PcpBoolArith* or1, PcpBoolArith* or2)
 525 {
 526   pcpAssert(or1 != NULL && or2 != NULL);
 527   pcpAssert(or1->getOperator().isBoolOr());
 528   pcpAssert(or2->getOperator().isBoolOr());
 529
 530   PcpBoolArithBuilder* builder = new PcpBoolArithBuilder();
 531   builder->setOperator(PcpBoolArithOperator::boolOr());
 532
 533   appendOperandsToBuilder(builder, or1);
 534   appendOperandsToBuilder(builder, or2);
 535
 536   PcpBoolArith* result = builder->createBoolArith();
 537   delete builder;
 538   return result;
 539 }
 540
 541 PcpBoolArith*
 542 PcpExprCanonicalizer::createFlattenedAnd(PcpBoolExpr* boolExpr1, PcpBoolExpr* boolExpr2)
 543 {
 544   PcpBoolArith* result;
 545   if(!boolExpr1->isBoolArith() && !boolExpr2->isBoolArith())
 546     result = PcpBoolArith::pcpBoolArithBinaryCreate(PcpBoolArithOperator::boolAnd(),
 547                                                     boolExpr1,
 548                                                     boolExpr2);
 549   else if(!boolExpr1->isBoolArith() && boolExpr2->isBoolArith())
 550     result = this->createFlattenedAnd(boolExpr2, boolExpr1);
 551   else
 552     {
 553       PcpBoolArithBuilder* builder = new PcpBoolArithBuilder();
 554       builder->setOperator(PcpBoolArithOperator::boolAnd());
 555
 556       PcpBoolArith* arith1 = boolExpr1->toBoolArith();
 557       pcpAssert(arith1->getOperator().isBoolAnd());
 558
 559       this->appendOperandsToBuilder(builder, boolExpr1->toBoolArith());
 560
 561       if(boolExpr2->isBoolArith())
 562         {
 563           PcpBoolArith* arith2 = boolExpr2->toBoolArith();
 564
 565           pcpAssert(arith2->getOperator().isBoolAnd());
 566
 567           this->appendOperandsToBuilder(builder, boolExpr2->toBoolArith());
 568         }
 569       else
 570         builder->addOperand(boolExpr2);
 571
 572       result = builder->createBoolArith();
 573       delete builder;
 574     }
 575   return result;
 576 }
 577
 578 PcpBoolArith*
 579 PcpExprCanonicalizer::distributeAnd(PcpBoolArith* or1, PcpBoolArith* or2)
 580 {
 581   PcpBoolArithBuilder* builder = new PcpBoolArithBuilder();
 582   builder->setOperator(PcpBoolArithOperator::boolOr());
 583
 584   PcpIterator<PcpBoolExpr*>* iter1 = or1->getOperandsIterator();
 585   for(;iter1->hasNext(); iter1->next())
 586     {
 587       PcpBoolExpr* expr1 = iter1->get();
 588       PcpIterator<PcpBoolExpr*>* iter2 = or2->getOperandsIterator();
 589       for(;iter2->hasNext(); iter2->next())
 590         {
 591           PcpBoolExpr* expr2 = iter2->get();
 592           PcpBoolArith* newAnd = this->createFlattenedAnd(expr1, expr2);
 593           builder->addOperand(newAnd);
 594         }
 595     }
 596   PcpBoolArith* result = builder->createBoolArith();
 597   delete builder;
 598   return result;
 599 }
 600
 601 PcpBoolArith*
 602 PcpExprCanonicalizer::canonicalizeBoolExpr(PcpBoolExpr* boolExpr)
 603 {
 604   if(!boolExpr->isBoolArith())
 605     return this->createUnaryOr(this->canonicalizeCompare(boolExpr->toCompare()));
 606
 607   PcpBoolArith* boolArith = boolExpr->toBoolArith();
 608   if(boolArith->getNumOperands() < 2)
 609     return boolArith;
 610   else
 611     {
 612       PcpIterator<PcpBoolExpr*>* iter = boolArith->getOperandsIterator();
 613       PcpBoolArithOperator oper = boolArith->getOperator();
 614       PcpBoolArith* result = this->canonicalizeBoolExpr(iter->get());
 615       iter->next();
 616       for(;iter->hasNext(); iter->next())
 617         {
 618           PcpBoolExpr* operand = iter->get();
 619           PcpBoolArith* canonicalizedOperand = this->canonicalizeBoolExpr(operand);
 620           if(oper.isBoolOr())
 621             {
 622               result = this->mergeOr(canonicalizedOperand, result);
 623             }
 624           else if(oper.isBoolAnd())
 625             {
 626               result = this->distributeAnd(canonicalizedOperand, result);
 627             }
 628           else
 629             pcpAssert(false);
 630         }
 631       return result;
 632     }
 633 }
 634
 635 void
 636 PcpExprCanonicalizer::visit(PcpScop* scop)
 637 {
 638   scop->getBody()->accept(this);
 639 }
 640
 641 void
 642 PcpExprCanonicalizer::visit(PcpLoop* loop)
 643 {
 644   this->getScalarContextStack()->push(loop->getIv()); // Iv(loop->getIv());
 645   PcpExpr* oldBase = this->getCanonicalizationBase();
 646   PcpExpr* newBase = this->getScalarContextStack()->createBaseExpr();
 647   this->setCanonicalizationBase(newBase);
 648   PcpBoolExpr* conditionBefore = loop->getCondition();
 649   PcpBoolArith* canonicalized = this->canonicalizeBoolExpr(conditionBefore);
 650   PcpBoolExpr* simplified = canonicalized->getNumOperands() == 1
 651     ? canonicalized->getOperand(0)
 652     : canonicalized;
 653   loop->setCondition(simplified);
 654   loop->getBody()->accept(this);
 655   this->getScalarContextStack()->pop();
 656   this->setCanonicalizationBase(oldBase);
 657 }
 658
 659 void
 660 PcpExprCanonicalizer::visit(PcpSequence* sequence)
 661 {
 662   visitChildren(sequence);
 663 }
 664
 665 void
 666 PcpExprCanonicalizer::visit(PcpGuard* guard)
 667 {
 668   visitChildren(guard);
 669 }
 670
 671 void
 672 PcpExprCanonicalizer::visit(PcpCopy* copy)
 673 {
 674   visitChildren(copy);
 675 }
 676
 677 void
 678 PcpExprCanonicalizer::visit(PcpUserStmt* userStmt)
 679 {
 680   visitChildren(userStmt);
 681 }
 682
 683 void
 684 PcpExprCanonicalizer::visit(PcpArrayAccess* arrayAccess)
 685 {
 686   PcpIterator<PcpExpr*>* iter = arrayAccess->getSubscriptsIterator();
 687   int i;
 688   for(i = 0; i < arrayAccess->getNumSubscripts(); i++)
 689     {
 690       PcpExpr* expr = arrayAccess->getSubscript(i);
 691       PcpArith* canonicalized = canonicalizeExprWithBase(expr);
 692       PcpExpr* simplified = canonicalized->getNumOperands() == 1
 693         ? canonicalized->getOperand(0)
 694         : canonicalized;
 695
 696       arrayAccess->setSubscript(i, simplified);
 697     }
 698   delete iter;
 699 }
 700
 701 void
 702 PcpExprCanonicalizer::setCanonicalizationBase(PcpExpr* canonicalizationBase)
 703 {
 704   this->canonicalizationBase = canonicalizationBase;
 705 }
 706
 707 PcpExpr*
 708 PcpExprCanonicalizer::getCanonicalizationBase()
 709 {
 710   return this->canonicalizationBase;
 711 }
 712
 713
 714 void
 715 PcpExprCanonicalizer::canonicalize(PcpScop* scop)
 716 {
 717   setScalarContextStack(new PcpScalarContextStack(scop));
 718   visit(scop);
 719 }
 720
 721 PcpExprCanonicalizer::PcpExprCanonicalizer(PcpScalarOrder* scalarOrder)
 722 {
 723   setScalarOrder(scalarOrder);
 724 }