Ignore:
Timestamp:
Jun 20, 2015, 3:52:41 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in

Location:
icGREP/icgrep-devel/icgrep
Files:
13 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r4189 r4611  
    2323#include <iostream>
    2424
    25 class Uset_Iterator {
    26 public:
    27     Uset_Iterator(UnicodeSet s) : uSet(s), run_no(0), offset(0), quad_no(0) {};
    28     bool at_end();
    29     RunStructure current_run();
    30     bitquad_t get_quad();
    31     void advance(int n);
    32 private:
    33     UnicodeSet uSet;
    34     int run_no;
    35     int offset;
    36     int quad_no;
    37 };
    38 
    3925bool Uset_Iterator::at_end() {
    40   return run_no == uSet.runs.size();
     26    return run_no == uSet.runs.size();
    4127}
    4228
    4329RunStructure Uset_Iterator::current_run() {
    44   RunStructure this_run = uSet.runs[run_no];
    45   return RunStructure(this_run.run_type, this_run.run_length - offset);
     30    RunStructure this_run = uSet.runs[run_no];
     31    return RunStructure(this_run.run_type, this_run.run_length - offset);
    4632}
    4733
    4834bitquad_t Uset_Iterator::get_quad() {
    49   RunStructure this_run = uSet.runs[run_no];
    50   if (this_run.run_type == Empty) return 0;
    51   else if (this_run.run_type == Full) return FullQuadMask;
    52   else return uSet.quads[quad_no];
     35    RunStructure this_run = uSet.runs[run_no];
     36    if (this_run.run_type == Empty) return 0;
     37    else if (this_run.run_type == Full) return FullQuadMask;
     38    else return uSet.quads[quad_no];
    5339}
    5440
    5541void Uset_Iterator::advance(int n) {
    56   while (n > 0) {
    57     RunStructure this_run = uSet.runs[run_no];
    58     int remain = this_run.run_length - offset;
    59     if (remain > n) {
    60       offset += n;
    61       if (this_run.run_type == Mixed) quad_no += n;
    62       n = 0;
    63     }
    64     else if (remain == n) {
    65       run_no += 1;
    66       offset = 0;
    67       if (this_run.run_type == Mixed) quad_no += n;
    68       n = 0;
     42    while (n > 0) {
     43        RunStructure this_run = uSet.runs[run_no];
     44        int remain = this_run.run_length - offset;
     45        if (remain > n) {
     46            offset += n;
     47            if (this_run.run_type == Mixed) quad_no += n;
     48            n = 0;
     49        }
     50        else if (remain == n) {
     51            run_no += 1;
     52            offset = 0;
     53            if (this_run.run_type == Mixed) quad_no += n;
     54            n = 0;
     55        }
     56        else {
     57            run_no += 1;
     58            offset = 0;
     59            if (this_run.run_type == Mixed) quad_no += remain;
     60            n -= remain;
     61        }
     62    }
     63}
     64
     65void UnicodeSet::append_run(run_type_t run_type, int run_length) {
     66    if (run_length == 0) {
     67        return;
     68    }
     69    else if (runs.size() == 0) {
     70        runs.emplace_back(run_type, run_length);
    6971    }
    7072    else {
    71       run_no += 1;
    72       offset = 0;
    73       if (this_run.run_type == Mixed) quad_no += remain;
    74       n -= remain;
    75     }
    76   }
    77 }
    78 
    79 void UnicodeSet::append_run(run_type_t run_type, int run_length) {
    80     if (run_length == 0) return;
    81     if (runs.size() == 0) runs.push_back(RunStructure(run_type, run_length));
    82     else {
    83       RunStructure last_run = runs[runs.size()-1];
    84       if (last_run.run_type == run_type) runs[runs.size()-1].run_length += run_length;
    85       else runs.push_back(RunStructure(run_type, run_length));
     73        RunStructure last_run = runs[runs.size()-1];
     74        if (last_run.run_type == run_type) {
     75            runs[runs.size()-1].run_length += run_length;
     76        }
     77        else {
     78            runs.emplace_back(run_type, run_length);
     79        }
    8680    }
    8781    quad_count += run_length;
     
    10195}
    10296
    103 void Dump_uset(UnicodeSet s) {
    104     UnicodeSet iset;
     97void Dump_uset(const UnicodeSet & s) {
    10598    Uset_Iterator it(s);
    10699    while (!it.at_end()) {
    107       RunStructure this_run = it.current_run();
    108       if (this_run.run_type == Empty) {
    109         std::cout << "Empty(" << this_run.run_length << ")\n";
    110         it.advance(this_run.run_length);
    111       }
    112       else if (this_run.run_type == Full) {
    113         std::cout << "Full(" << this_run.run_length << ")\n";
    114         it.advance(this_run.run_length);
    115       }
    116       else {
    117         for (int i = 0; i < this_run.run_length; i++) {
    118           std::cout << "Mixed(" << std::hex << it.get_quad() << std::dec << ")\n";
    119           it.advance(1);
    120         }
    121       }
    122     }
    123 }
    124 
    125 
     100        RunStructure this_run = it.current_run();
     101        if (this_run.run_type == Empty) {
     102            std::cout << "Empty(" << this_run.run_length << ")\n";
     103            it.advance(this_run.run_length);
     104        }
     105        else if (this_run.run_type == Full) {
     106            std::cout << "Full(" << this_run.run_length << ")\n";
     107            it.advance(this_run.run_length);
     108        }
     109        else {
     110            for (int i = 0; i < this_run.run_length; i++) {
     111                std::cout << "Mixed(" << std::hex << it.get_quad() << std::dec << ")\n";
     112                it.advance(1);
     113            }
     114        }
     115    }
     116}
    126117
    127118UnicodeSet empty_uset() {
    128119    UnicodeSet iset;
    129     iset.runs.push_back(RunStructure(Empty, UnicodeQuadCount));
     120    iset.runs.emplace_back(Empty, UnicodeQuadCount);
    130121    iset.quad_count = UnicodeQuadCount;
    131122    return iset;
     
    166157}
    167158
    168 UnicodeSet uset_complement (UnicodeSet s) {
     159UnicodeSet uset_complement (const UnicodeSet & s) {
    169160    assert(s.quad_count == UnicodeQuadCount);
    170161    UnicodeSet iset;
    171162    Uset_Iterator it(s);
    172163    while (!it.at_end()) {
    173       RunStructure this_run = it.current_run();
    174       if (this_run.run_type == Empty) {
    175         iset.append_run(Full, this_run.run_length);
    176         it.advance(this_run.run_length);
    177       }
    178       else if (this_run.run_type == Full) {
    179         iset.append_run(Empty, this_run.run_length);
    180         it.advance(this_run.run_length);
    181       }
    182       else {
    183         for (int i = 0; i < this_run.run_length; i++) {
    184           iset.append_quad(FullQuadMask ^ it.get_quad());
    185           it.advance(1);
    186         }
    187       }
    188     }
    189     return iset;
    190 }
    191 
    192 UnicodeSet uset_intersection (UnicodeSet s1, UnicodeSet s2) {
     164        RunStructure this_run = it.current_run();
     165        if (this_run.run_type == Empty) {
     166            iset.append_run(Full, this_run.run_length);
     167            it.advance(this_run.run_length);
     168        }
     169        else if (this_run.run_type == Full) {
     170            iset.append_run(Empty, this_run.run_length);
     171            it.advance(this_run.run_length);
     172        }
     173        else {
     174            for (int i = 0; i < this_run.run_length; i++) {
     175                iset.append_quad(FullQuadMask ^ it.get_quad());
     176                it.advance(1);
     177            }
     178        }
     179    }
     180    return iset;
     181}
     182
     183UnicodeSet uset_intersection (const UnicodeSet & s1, const UnicodeSet & s2) {
    193184    assert(s1.quad_count == UnicodeQuadCount);
    194185    assert(s2.quad_count == UnicodeQuadCount);
     
    197188    Uset_Iterator i2(s2);
    198189    while (!i1.at_end()) {
    199       RunStructure run1 = i1.current_run();
    200       RunStructure run2 = i2.current_run();
    201       int n = std::min(run1.run_length, run2.run_length);
    202       if ((run1.run_type == Empty) || (run2.run_type == Empty)) {
    203         iset.append_run(Empty, n);
    204         i1.advance(n);
    205         i2.advance(n);
    206       }
    207       else if ((run1.run_type == Full) && (run2.run_type == Full)) {
    208         iset.append_run(Full, n);
    209         i1.advance(n);
    210         i2.advance(n);
    211       }
    212       else if (run1.run_type == Full) {
    213         for (int i = 0; i < n; i++) {
    214           iset.append_quad(i2.get_quad());
    215           i2.advance(1);
    216         }
    217         i1.advance(n); 
    218       }
    219       else if (run2.run_type == Full) {
    220         for (int i = 0; i < n; i++) {
    221           iset.append_quad(i1.get_quad());
    222           i1.advance(1);
    223         }
    224         i2.advance(n); 
    225       }
    226       else {
    227         for (int i = 0; i < n; i++) {
    228           iset.append_quad(i1.get_quad() & i2.get_quad());
    229           i1.advance(1);
    230           i2.advance(1);
    231         }
    232       }
    233     }
    234     return iset;
    235 }
    236 
    237 UnicodeSet uset_union (UnicodeSet s1, UnicodeSet s2) {
     190        RunStructure run1 = i1.current_run();
     191        RunStructure run2 = i2.current_run();
     192        int n = std::min(run1.run_length, run2.run_length);
     193        if ((run1.run_type == Empty) || (run2.run_type == Empty)) {
     194            iset.append_run(Empty, n);
     195            i1.advance(n);
     196            i2.advance(n);
     197        }
     198        else if ((run1.run_type == Full) && (run2.run_type == Full)) {
     199            iset.append_run(Full, n);
     200            i1.advance(n);
     201            i2.advance(n);
     202        }
     203        else if (run1.run_type == Full) {
     204            for (int i = 0; i < n; i++) {
     205                iset.append_quad(i2.get_quad());
     206                i2.advance(1);
     207            }
     208            i1.advance(n);
     209        }
     210        else if (run2.run_type == Full) {
     211            for (int i = 0; i < n; i++) {
     212                iset.append_quad(i1.get_quad());
     213                i1.advance(1);
     214            }
     215            i2.advance(n);
     216        }
     217        else {
     218            for (int i = 0; i < n; i++) {
     219                iset.append_quad(i1.get_quad() & i2.get_quad());
     220                i1.advance(1);
     221                i2.advance(1);
     222            }
     223        }
     224    }
     225    return iset;
     226}
     227
     228UnicodeSet uset_union (const UnicodeSet & s1, const UnicodeSet & s2) {
    238229    assert(s1.quad_count == UnicodeQuadCount);
    239230    assert(s2.quad_count == UnicodeQuadCount);
     
    242233    Uset_Iterator i2(s2);
    243234    while (!i1.at_end()) {
    244       RunStructure run1 = i1.current_run();
    245       RunStructure run2 = i2.current_run();
    246       int n = std::min(run1.run_length, run2.run_length);
    247       if ((run1.run_type == Empty) && (run2.run_type == Empty)) {
    248         iset.append_run(Empty, n);
    249         i1.advance(n);
    250         i2.advance(n);
    251       }
    252       else if ((run1.run_type == Full) || (run2.run_type == Full)) {
    253         iset.append_run(Full, n);
    254         i1.advance(n);
    255         i2.advance(n);
    256       }
    257       else if (run1.run_type == Empty) {
    258         for (int i = 0; i < n; i++) {
    259           iset.append_quad(i2.get_quad());
    260           i2.advance(1);
    261         }
    262         i1.advance(n); 
    263       }
    264       else if (run2.run_type == Empty) {
    265         for (int i = 0; i < n; i++) {
    266           iset.append_quad(i1.get_quad());
    267           i1.advance(1);
    268         }
    269         i2.advance(n); 
    270       }
    271       else {
    272         for (int i = 0; i < n; i++) {
    273           iset.append_quad(i1.get_quad() | i2.get_quad());
    274           i1.advance(1);
    275           i2.advance(1);
    276         }
    277       }
    278     }
    279     return iset;
    280 }
    281 
    282 UnicodeSet uset_difference (UnicodeSet s1, UnicodeSet s2) {
     235        RunStructure run1 = i1.current_run();
     236        RunStructure run2 = i2.current_run();
     237        int n = std::min(run1.run_length, run2.run_length);
     238        if ((run1.run_type == Empty) && (run2.run_type == Empty)) {
     239            iset.append_run(Empty, n);
     240            i1.advance(n);
     241            i2.advance(n);
     242        }
     243        else if ((run1.run_type == Full) || (run2.run_type == Full)) {
     244            iset.append_run(Full, n);
     245            i1.advance(n);
     246            i2.advance(n);
     247        }
     248        else if (run1.run_type == Empty) {
     249            for (int i = 0; i < n; i++) {
     250                iset.append_quad(i2.get_quad());
     251                i2.advance(1);
     252            }
     253            i1.advance(n);
     254        }
     255        else if (run2.run_type == Empty) {
     256            for (int i = 0; i < n; i++) {
     257                iset.append_quad(i1.get_quad());
     258                i1.advance(1);
     259            }
     260            i2.advance(n);
     261        }
     262        else {
     263            for (int i = 0; i < n; i++) {
     264                iset.append_quad(i1.get_quad() | i2.get_quad());
     265                i1.advance(1);
     266                i2.advance(1);
     267            }
     268        }
     269    }
     270    return iset;
     271}
     272
     273UnicodeSet uset_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
    283274    assert(s1.quad_count == UnicodeQuadCount);
    284275    assert(s2.quad_count == UnicodeQuadCount);
     
    287278    Uset_Iterator i2(s2);
    288279    while (!i1.at_end()) {
    289       RunStructure run1 = i1.current_run();
    290       RunStructure run2 = i2.current_run();
    291       int n = std::min(run1.run_length, run2.run_length);
    292       if ((run1.run_type == Empty) || (run2.run_type == Full)) {
    293         iset.append_run(Empty, n);
    294         i1.advance(n);
    295         i2.advance(n);
    296       }
    297       else if ((run1.run_type == Full) && (run2.run_type == Empty)) {
    298         iset.append_run(Full, n);
    299         i1.advance(n);
    300         i2.advance(n);
    301       }
    302       else if (run1.run_type == Full) {
    303         for (int i = 0; i < n; i++) {
    304           iset.append_quad(FullQuadMask ^ i2.get_quad());
    305           i2.advance(1);
    306         }
    307         i1.advance(n); 
    308       }
    309       else if (run2.run_type == Empty) {
    310         for (int i = 0; i < n; i++) {
    311           iset.append_quad(i1.get_quad());
    312           i1.advance(1);
    313         }
    314         i2.advance(n); 
    315       }
    316       else {
    317         for (int i = 0; i < n; i++) {
    318           iset.append_quad(i1.get_quad() & ~i2.get_quad());
    319           i1.advance(1);
    320           i2.advance(1);
    321         }
    322       }
    323     }
    324     return iset;
    325 }
    326 
    327 UnicodeSet uset_symmetric_difference (UnicodeSet s1, UnicodeSet s2) {
     280        RunStructure run1 = i1.current_run();
     281        RunStructure run2 = i2.current_run();
     282        int n = std::min(run1.run_length, run2.run_length);
     283        if ((run1.run_type == Empty) || (run2.run_type == Full)) {
     284            iset.append_run(Empty, n);
     285            i1.advance(n);
     286            i2.advance(n);
     287        }
     288        else if ((run1.run_type == Full) && (run2.run_type == Empty)) {
     289            iset.append_run(Full, n);
     290            i1.advance(n);
     291            i2.advance(n);
     292        }
     293        else if (run1.run_type == Full) {
     294            for (int i = 0; i < n; i++) {
     295                iset.append_quad(FullQuadMask ^ i2.get_quad());
     296                i2.advance(1);
     297            }
     298            i1.advance(n);
     299        }
     300        else if (run2.run_type == Empty) {
     301            for (int i = 0; i < n; i++) {
     302                iset.append_quad(i1.get_quad());
     303                i1.advance(1);
     304            }
     305            i2.advance(n);
     306        }
     307        else {
     308            for (int i = 0; i < n; i++) {
     309                iset.append_quad(i1.get_quad() & ~i2.get_quad());
     310                i1.advance(1);
     311                i2.advance(1);
     312            }
     313        }
     314    }
     315    return iset;
     316}
     317
     318UnicodeSet uset_symmetric_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
    328319    assert(s1.quad_count == UnicodeQuadCount);
    329320    assert(s2.quad_count == UnicodeQuadCount);
     
    332323    Uset_Iterator i2(s2);
    333324    while (!i1.at_end()) {
    334       RunStructure run1 = i1.current_run();
    335       RunStructure run2 = i2.current_run();
    336       int n = std::min(run1.run_length, run2.run_length);
    337       if (((run1.run_type == Empty) && (run2.run_type == Full)) || ((run1.run_type == Full) && (run2.run_type == Empty))) {
    338         iset.append_run(Full, n);
    339         i1.advance(n);
    340         i2.advance(n);
    341       }
    342       else if (((run1.run_type == Full) && (run2.run_type == Full)) || ((run1.run_type == Empty) && (run2.run_type == Empty))) {
    343         iset.append_run(Empty, n);
    344         i1.advance(n);
    345         i2.advance(n);
    346       }
    347       else if (run1.run_type == Empty) {
    348         for (int i = 0; i < n; i++) {
    349           iset.append_quad(i2.get_quad());
    350           i2.advance(1);
    351         }
    352         i1.advance(n); 
    353       }
    354       else if (run2.run_type == Empty) {
    355         for (int i = 0; i < n; i++) {
    356           iset.append_quad(i1.get_quad());
    357           i1.advance(1);
    358         }
    359         i2.advance(n); 
    360       }
    361       else if (run1.run_type == Full) {
    362         for (int i = 0; i < n; i++) {
    363           iset.append_quad(FullQuadMask ^ i2.get_quad());
    364           i2.advance(1);
    365         }
    366         i1.advance(n); 
    367       }
    368       else if (run2.run_type == Empty) {
    369         for (int i = 0; i < n; i++) {
    370           iset.append_quad(FullQuadMask ^ i1.get_quad());
    371           i1.advance(1);
    372         }
    373         i2.advance(n); 
    374       }
    375       else {
    376         for (int i = 0; i < n; i++) {
    377           iset.append_quad(i1.get_quad() ^ i2.get_quad());
    378           i1.advance(1);
    379           i2.advance(1);
    380         }
    381       }
    382     }
    383     return iset;
    384 }
    385 
    386 bool uset_member(UnicodeSet s, int codepoint){
     325        RunStructure run1 = i1.current_run();
     326        RunStructure run2 = i2.current_run();
     327        int n = std::min(run1.run_length, run2.run_length);
     328        if (((run1.run_type == Empty) && (run2.run_type == Full)) || ((run1.run_type == Full) && (run2.run_type == Empty))) {
     329            iset.append_run(Full, n);
     330            i1.advance(n);
     331            i2.advance(n);
     332        }
     333        else if (((run1.run_type == Full) && (run2.run_type == Full)) || ((run1.run_type == Empty) && (run2.run_type == Empty))) {
     334            iset.append_run(Empty, n);
     335            i1.advance(n);
     336            i2.advance(n);
     337        }
     338        else if (run1.run_type == Empty) {
     339            for (int i = 0; i < n; i++) {
     340                iset.append_quad(i2.get_quad());
     341                i2.advance(1);
     342            }
     343            i1.advance(n);
     344        }
     345        else if (run2.run_type == Empty) {
     346            for (int i = 0; i < n; i++) {
     347                iset.append_quad(i1.get_quad());
     348                i1.advance(1);
     349            }
     350            i2.advance(n);
     351        }
     352        else if (run1.run_type == Full) {
     353            for (int i = 0; i < n; i++) {
     354                iset.append_quad(FullQuadMask ^ i2.get_quad());
     355                i2.advance(1);
     356            }
     357            i1.advance(n);
     358        }
     359        else if (run2.run_type == Empty) {
     360            for (int i = 0; i < n; i++) {
     361                iset.append_quad(FullQuadMask ^ i1.get_quad());
     362                i1.advance(1);
     363            }
     364            i2.advance(n);
     365        }
     366        else {
     367            for (int i = 0; i < n; i++) {
     368                iset.append_quad(i1.get_quad() ^ i2.get_quad());
     369                i1.advance(1);
     370                i2.advance(1);
     371            }
     372        }
     373    }
     374    return iset;
     375}
     376
     377bool uset_member(const UnicodeSet & s, int codepoint){
    387378    int quad_no = codepoint / quad_bits;
    388379    bitquad_t quad_val = 1 << (codepoint & mod_quad_bit_mask);
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r4189 r4611  
    44#include <vector>
    55#include <ostream>
     6
    67//
    78// unicode_set.h - representing and manipulating sets of Unicode
     
    3839
    3940struct RunStructure {
    40   RunStructure(run_type_t r, uint16_t lgth) : run_type(r), run_length(lgth) {};
     41  RunStructure(run_type_t r, uint16_t lgth) : run_type(r), run_length(lgth) {}
    4142  run_type_t run_type;
    4243  uint16_t run_length;
     
    5859//
    5960//  Nullary constructor for incremental building.
    60     UnicodeSet() : runs(std::vector<RunStructure>()), quads(std::vector<bitquad_t>()), quad_count(0) {};
     61    UnicodeSet() : runs(std::vector<RunStructure>()), quads(std::vector<bitquad_t>()), quad_count(0) {}
    6162//
    6263//  Ternary constructor for constant construction using precomputed data.
    63     UnicodeSet(std::vector<RunStructure> r, std::vector<bitquad_t> q, int c) : runs(r), quads(q), quad_count(c) {};
     64    UnicodeSet(std::initializer_list<RunStructure> r, std::initializer_list<bitquad_t> q, int c) : runs(r), quads(q), quad_count(c) {}
    6465};
    6566
    66     void Dump_uset(UnicodeSet s);
    67     UnicodeSet empty_uset();
    68     UnicodeSet singleton_uset(int codepoint);
    69     UnicodeSet range_uset(int lo_codepoint, int hi_codepoint);
    70     UnicodeSet uset_complement (UnicodeSet s);
    71     UnicodeSet uset_union(UnicodeSet s1, UnicodeSet s2);
    72     UnicodeSet uset_intersection(UnicodeSet s1, UnicodeSet s2);
    73     UnicodeSet uset_difference(UnicodeSet s1, UnicodeSet s2);
    74     UnicodeSet uset_symmetric_difference(UnicodeSet s1, UnicodeSet s2);
    75     bool uset_member(UnicodeSet s, int codepoint);
     67void Dump_uset(UnicodeSet s);
     68UnicodeSet empty_uset();
     69UnicodeSet singleton_uset(int codepoint);
     70UnicodeSet range_uset(int lo_codepoint, int hi_codepoint);
     71UnicodeSet uset_complement (const UnicodeSet &s);
     72UnicodeSet uset_union(const UnicodeSet & s1, const UnicodeSet & s2);
     73UnicodeSet uset_intersection(const UnicodeSet &s1, const UnicodeSet &s2);
     74UnicodeSet uset_difference(const UnicodeSet &s1, const UnicodeSet &s2);
     75UnicodeSet uset_symmetric_difference(const UnicodeSet & s1, const UnicodeSet & s2);
     76bool uset_member(const UnicodeSet & s, int codepoint);
     77
     78class Uset_Iterator {
     79public:
     80    Uset_Iterator(const UnicodeSet & s) : uSet(s), run_no(0), offset(0), quad_no(0) {}
     81    bool at_end();
     82    RunStructure current_run();
     83    bitquad_t get_quad();
     84    void advance(int n);
     85private:
     86    const UnicodeSet & uSet;
     87    int run_no;
     88    int offset;
     89    int quad_no;
     90};
    7691
    7792#endif
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4602 r4611  
    415415, mOnes(predecessor->mOnes) // inherit the original "Ones" variable for simplicity
    416416, mSymbolGenerator(predecessor->mSymbolGenerator)
    417 , mParent(predecessor)
    418 {
    419     // predecessor->addUser(this);
     417, mParent(predecessor) {
     418
    420419}
    421420
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4602 r4611  
    170170    inline Type * insertAtInsertionPoint(Type * expr) {
    171171        if (isa<Statement>(expr)) {
     172            if (LLVM_UNLIKELY(isa<If>(expr) || isa<While>(expr))) {
     173                PabloBlock & body = isa<If>(expr) ? cast<If>(expr)->getBody() : cast<While>(expr)->getBody();
     174                this->addUser(&body);
     175            }
    172176            insert(cast<Statement>(expr));
    173177        }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4610 r4611  
    1111#include <pablo/builder.hpp>
    1212#include <boost/range/iterator_range.hpp>
     13#include <pablo/printer_pablos.h>
    1314#include <cudd.h>
    1415#include <util.h>
     
    116117    LOG("Characterize:            " << (end_characterize - start_characterize));
    117118
     119    RECORD_TIMESTAMP(start_minimization);
     120    am.minimize(entry);
     121    RECORD_TIMESTAMP(end_minimization);
     122    LOG("Minimize:                " << (end_minimization - start_minimization));
     123
    118124    RECORD_TIMESTAMP(start_shutdown);
    119125    am.shutdown();
     
    162168 * the proper variable ordering.
    163169 ** ------------------------------------------------------------------------------------------------------------- */
    164 void AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
     170void AutoMultiplexing::initialize(const std::vector<Var *> & vars, PabloBlock & entry) {
    165171
    166172    flat_map<const PabloAST *, unsigned> map;   
    167     std::stack<const Statement *> scope;
     173    std::stack<Statement *> scope;
    168174    unsigned complexStatements = 0; // number of statements that cannot always be categorized without generating a new variable
    169175
    170176    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    171177    unsigned n = 0, m = 0;
    172     for (const Statement * stmt = entry.front(); ; ) {
     178    for (Statement * stmt = entry.front(); ; ) {
    173179        while ( stmt ) {
    174180            ++n;
     
    186192
    187193            switch (stmt->getClassTypeId()) {
    188                 case PabloAST::ClassTypeId::Advance:                   
    189                     mAdvance.push_back(const_cast<Advance*>(cast<Advance>(stmt)));
     194                case PabloAST::ClassTypeId::Advance:
     195                    mAdvanceMap.emplace(stmt, m);
    190196                    map.emplace(stmt, m++);
    191197                case PabloAST::ClassTypeId::Call:
     
    228234            unsigned u;
    229235            if (isa<Advance>(stmt)) {
    230                 assert (mAdvance[m] == stmt);
     236                assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m);
    231237                u = m++;
    232238            }
     
    283289
    284290    // Map the predefined 0/1 entries
    285     mCharacterizationMap.emplace(entry.createZeroes(), Zero());
    286     mCharacterizationMap.emplace(entry.createOnes(), One());
     291    mCharacterizationMap[entry.createZeroes()] = Zero();
     292    mCharacterizationMap[entry.createOnes()] = One();
    287293
    288294    // Order the variables so the input Vars are pushed to the end; they ought to
     
    290296    unsigned i = complexStatements;
    291297    for (const Var * var : vars) {
    292         mCharacterizationMap.emplace(var, Cudd_bddIthVar(mManager, i++));
     298        mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++);
    293299    }
    294300}
     
    300306 * Scan through the program and iteratively compute the BDDs for each statement.
    301307 ** ------------------------------------------------------------------------------------------------------------- */
    302 void AutoMultiplexing::characterize(PabloBlock & entry) {
    303 
    304     std::vector<std::pair<DdNode *, DdNode *>> advances; // the input BDD and the BDD variable of the i-th Advance
    305     std::stack<Statement *> scope;
    306     std::vector<bool> unconstrained(mAdvance.size());
    307     advances.reserve(mAdvance.size());
    308 
    309     // TODO: What if we did some minterm analysis in here? We'd need to be careful to keep the Advances properly indexed.
    310 
    311     // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    312     for (Statement * stmt = entry.front(); ; ) {
    313         while ( stmt ) {
    314 
    315             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    316                 // Set the next statement to be the first statement of the inner scope and push the
    317                 // next statement of the current statement into the scope stack.
    318                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    319                 scope.push(stmt->getNextNode());
    320                 stmt = nested.front();
    321                 continue;
    322             }
    323 
    324             DdNode * bdd = nullptr;
    325             // Map our operands to the computed BDDs
    326             std::array<DdNode *, 3> input;
    327             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    328                 PabloAST * const op = stmt->getOperand(i);
    329                 if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    330                     continue;
    331                 }
    332                 auto f = mCharacterizationMap.find(op);
    333                 if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    334                     throw std::runtime_error("Uncharacterized operand " + std::to_string(i) + " of " + stmt->getName()->to_string());
    335                 }
    336                 input[i] = f->second;
    337             }
    338 
    339             switch (stmt->getClassTypeId()) {
    340                 case PabloAST::ClassTypeId::Assign:
    341                     bdd = input[0];
    342                     break;
    343                 case PabloAST::ClassTypeId::And:
    344                     bdd = And(input[0], input[1]);
    345                     break;
    346                 case PabloAST::ClassTypeId::Next:
    347                     // The next instruction is almost identical to an OR; however, a Next cannot be
    348                     // an operand of a Statement. Instead it updates the Initial operand's value.
    349                 case PabloAST::ClassTypeId::Or:           
    350                     bdd = Or(input[0], input[1]);
    351                     break;
    352                 case PabloAST::ClassTypeId::Xor:
    353                     bdd = Xor(input[0], input[1]);
    354                     break;
    355                 case PabloAST::ClassTypeId::Not:
    356                     bdd = Not(input[0]);
    357                     break;
    358                 case PabloAST::ClassTypeId::Sel:
    359                     bdd = Ite(input[0], input[1], input[2]);
    360                     break;
    361                 case PabloAST::ClassTypeId::ScanThru:
    362                     // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
    363                     // of a contradition being erroneously calculated later. An example of this
    364                     // would be ¬(ScanThru(c,m) √ m)
    365                 case PabloAST::ClassTypeId::MatchStar:
    366                     if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
    367                         bdd = Zero();
    368                         break;
    369                     }
    370                 case PabloAST::ClassTypeId::Call:
    371                     bdd = NewVar();
    372                     break;
    373                 case PabloAST::ClassTypeId::Advance:
    374                     assert (stmt == mAdvance[advances.size()]);
    375                     if (LLVM_UNLIKELY(isZero(input[0]))) {
    376                         bdd = Zero();
    377                         advances.emplace_back(bdd, bdd);
    378                     }
    379                     else {
    380 
    381                         // When we built the path graph, we constructed it in the same order; hense the row/column of
    382                         // the path graph is equivalent to the index.
    383 
    384                         // Only test pairs if they are in the same scope or one has a user in the a scope that is reachable by
    385                         // the other?
    386 
    387                         // Can we use a transposed copy of the subset graph to determine an ordering of variables?
    388 
    389                         DdNode * const Ik = input[0];
    390                         DdNode * Ck = NewVar();
    391                         DdNode * const Nk = Not(Ck);
    392 
    393                         const unsigned k = advances.size();
    394 
    395                         std::fill(unconstrained.begin(), unconstrained.begin() + k, false);
    396 
    397                         for (unsigned i = 0; i != k; ++i) {
    398                             // Have we already proven that these are unconstrained by the subset relationships?
    399                             if (unconstrained[i]) continue;
    400                             Advance * adv = mAdvance[i];
    401                             // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    402                             if ((stmt->getOperand(1) == adv->getOperand(1)) && (notTransitivelyDependant(i, k))) {
    403                                 DdNode * Ii = std::get<0>(advances[i]);
    404                                 DdNode * Ni = std::get<1>(advances[i]);
    405                                 // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
    406                                 DdNode * const IiIk = Intersect(Ik, Ii);
    407                                 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    408                                 if (noSatisfyingAssignment(IiIk)) {
    409                                     assert (mCharacterizationMap.count(adv));
    410                                     DdNode *& Ci = mCharacterizationMap[adv];
    411                                     // Mark the i-th and k-th Advances as being mutually exclusive
    412                                     Ck = And(Ck, Ni);
    413                                     Ci = And(Ci, Nk);
    414                                     // If Ai ∩ Ak = âˆ
     308void AutoMultiplexing::characterize(PabloBlock & block) {
     309    for (Statement * stmt : block) {
     310        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     311            // Set the next statement to be the first statement of the inner scope and push the
     312            // next statement of the current statement into the scope stack.
     313            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     314            continue;
     315        }
     316        mCharacterizationMap[stmt] = characterize(stmt, true);
     317    }
     318}
     319
     320/** ------------------------------------------------------------------------------------------------------------- *
     321 * @brief characterize
     322 ** ------------------------------------------------------------------------------------------------------------- */
     323DdNode * AutoMultiplexing::characterize(Statement * const stmt, const bool throwUncharacterizedOperandError) {
     324
     325    DdNode * bdd = nullptr;
     326    // Map our operands to the computed BDDs
     327    std::array<DdNode *, 3> input;
     328    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     329        PabloAST * const op = stmt->getOperand(i);
     330        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
     331            continue;
     332        }
     333        auto f = mCharacterizationMap.find(op);
     334        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
     335            if (throwUncharacterizedOperandError) {
     336                std::string tmp;
     337                llvm::raw_string_ostream msg(tmp);
     338                msg << "Uncharacterized operand " << std::to_string(i);
     339                PabloPrinter::print(stmt, " of ", msg);
     340                throw std::runtime_error(msg.str());
     341            }
     342            return nullptr;
     343        }
     344        input[i] = f->second;
     345    }
     346
     347    switch (stmt->getClassTypeId()) {
     348        case PabloAST::ClassTypeId::Assign:
     349            bdd = input[0];
     350            break;
     351        case PabloAST::ClassTypeId::And:
     352            bdd = And(input[0], input[1]);
     353            break;
     354        case PabloAST::ClassTypeId::Next:
     355        case PabloAST::ClassTypeId::Or:
     356            bdd = Or(input[0], input[1]);
     357            break;
     358        case PabloAST::ClassTypeId::Xor:
     359            bdd = Xor(input[0], input[1]);
     360            break;
     361        case PabloAST::ClassTypeId::Not:
     362            bdd = Not(input[0]);
     363            break;
     364        case PabloAST::ClassTypeId::Sel:
     365            bdd = Ite(input[0], input[1], input[2]);
     366            break;
     367        case PabloAST::ClassTypeId::ScanThru:
     368            // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
     369            // of a contradition being erroneously calculated later. An example of this
     370            // would be ¬(ScanThru(c,m) √ m)
     371        case PabloAST::ClassTypeId::MatchStar:
     372            if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
     373                bdd = Zero();
     374                break;
     375            }
     376        case PabloAST::ClassTypeId::Call:
     377            bdd = NewVar();
     378            break;
     379        case PabloAST::ClassTypeId::Advance:
     380            bdd = characterize(cast<Advance>(stmt), input[0]);
     381            break;
     382        default:
     383            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
     384    }
     385
     386    assert ("Failed to generate a BDD." && (bdd));
     387
     388    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
     389        Cudd_RecursiveDeref(mManager, bdd);
     390        bdd = Zero();
     391    }
     392
     393    return bdd;
     394
     395}
     396
     397/** ------------------------------------------------------------------------------------------------------------- *
     398 * @brief characterize
     399 ** ------------------------------------------------------------------------------------------------------------- */
     400inline DdNode * AutoMultiplexing::characterize(Advance * adv, DdNode * input) {
     401    DdNode * Ik, * Ck, * Nk;
     402    if (LLVM_UNLIKELY(isZero(input))) {
     403        Ik = Ck = Nk = Zero();
     404    }
     405    else {
     406
     407        Ik = input;
     408        Ck = NewVar();
     409        Nk = Not(Ck);
     410
     411        assert (mAdvanceMap.count(adv));
     412
     413        const auto k = mAdvanceMap[adv];
     414
     415        std::vector<bool> unconstrained(k , false);
     416
     417        // Can we use a transposed copy of the subset graph to determine an ordering of variables?
     418        for (unsigned i = 0; i != k; ++i) {
     419            // Have we already proven that these are unconstrained by the subset relationships?
     420            if (unconstrained[i]) continue;
     421            Advance * tmp = std::get<0>(mAdvance[i]);
     422            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
     423            if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
     424                DdNode * Ii = std::get<1>(mAdvance[i]);
     425                DdNode * Ni = std::get<2>(mAdvance[i]);
     426                // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
     427                DdNode * const IiIk = Intersect(Ik, Ii);
     428                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
     429                if (noSatisfyingAssignment(IiIk)) {
     430                    assert (mCharacterizationMap.count(tmp));
     431                    DdNode *& Ci = mCharacterizationMap[tmp];
     432                    // Mark the i-th and k-th Advances as being mutually exclusive
     433                    Ck = And(Ck, Ni);
     434                    Ci = And(Ci, Nk);
     435                    // If Ai ∩ Ak = âˆ
    415436 and Aj ⊂ Ai, Aj ∩ Ak = âˆ
    416437.
    417                                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    418                                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    419                                         const auto j = source(*ei, mSubsetGraph);
    420                                         if (notTransitivelyDependant(k, j)) {
    421                                             Advance * adv = mAdvance[j];
    422                                             assert (mCharacterizationMap.count(adv));
    423                                             DdNode *& Cj = mCharacterizationMap[adv];
    424                                             DdNode * Nj = std::get<1>(advances[j]);
    425                                             // Mark the i-th and j-th Advances as being mutually exclusive
    426                                             Ck = And(Ck, Nj);
    427                                             Cj = And(Cj, Nk);
    428                                             unconstrained[j] = true;
    429                                         }
    430                                     }
    431                                     unconstrained[i] = true;
    432                                 }
    433                                 else if (Ik == IiIk) {
    434                                     // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
    435                                     // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
    436                                     // in the same mutually exclusive set.
    437                                     add_edge(k, i, mSubsetGraph);
    438                                     // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
    439                                     graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
    440                                     for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    441                                         const auto j = target(*ei, mSubsetGraph);
    442                                         add_edge(k, j, mSubsetGraph);
    443                                         unconstrained[j] = true;
    444                                     }
    445                                     unconstrained[i] = true;
    446                                 }
    447                                 else if (Ii == IiIk) {
    448                                     // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
    449                                     add_edge(i, k, mSubsetGraph);
    450                                     // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
    451                                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    452                                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    453                                         const auto j = source(*ei, mSubsetGraph);
    454                                         add_edge(j, k, mSubsetGraph);
    455                                         unconstrained[j] = true;
    456                                     }
    457                                     unconstrained[i] = true;
    458                                 }
    459                                 Cudd_RecursiveDeref(mManager, IiIk);
    460                             }
     438                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
     439                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
     440                        const auto j = source(*ei, mSubsetGraph);
     441                        if (notTransitivelyDependant(k, j)) {
     442                            Advance * adv = std::get<0>(mAdvance[j]);
     443                            assert (mCharacterizationMap.count(adv));
     444                            DdNode *& Cj = mCharacterizationMap[adv];
     445                            DdNode * Nj = std::get<2>(mAdvance[j]);
     446                            // Mark the i-th and j-th Advances as being mutually exclusive
     447                            Ck = And(Ck, Nj);
     448                            Cj = And(Cj, Nk);
     449                            unconstrained[j] = true;
    461450                        }
    462 
    463                         for (unsigned i = 0; i != k; ++i) {
    464                             const Advance * const adv = mAdvance[i];
    465                             // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
    466                             if (!unconstrained[i] || (stmt->getParent() != adv->getParent())) {
    467                                 // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
    468                                 // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
    469                                 add_edge(i, k, mConstraintGraph);
    470                             }
    471                         }
    472 
    473                         // Append this advance to the list of known advances. Both its input BDD and the Advance variable are stored in
    474                         // the list to eliminate the need for searching for it.
    475                         advances.emplace_back(Ik, Nk);
    476                         bdd = Ck;
    477                     }
    478                     break;
    479                 default:
    480                     throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    481             }
    482             assert ("Failed to generate a BDD." && (bdd));
    483             mCharacterizationMap[stmt] = bdd;
    484             if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    485                 if (!isa<Assign>(stmt)) {
    486                     Cudd_RecursiveDeref(mManager, bdd);
    487                     mCharacterizationMap[stmt] = Zero();
    488                     stmt = stmt->replaceWith(entry.createZeroes());
    489                     continue;
    490                 }
    491             }
    492             stmt = stmt->getNextNode();
    493         }
    494 
    495         if (scope.empty()) {
    496             break;
    497         }
    498         stmt = scope.top();
    499         scope.pop();
     451                    }
     452                    unconstrained[i] = true;
     453                }
     454                else if (Ik == IiIk) {
     455                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
     456                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
     457                    // in the same mutually exclusive set.
     458                    add_edge(k, i, mSubsetGraph);
     459                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
     460                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
     461                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
     462                        const auto j = target(*ei, mSubsetGraph);
     463                        add_edge(k, j, mSubsetGraph);
     464                        unconstrained[j] = true;
     465                    }
     466                    unconstrained[i] = true;
     467                }
     468                else if (Ii == IiIk) {
     469                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
     470                    add_edge(i, k, mSubsetGraph);
     471                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
     472                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
     473                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
     474                        const auto j = source(*ei, mSubsetGraph);
     475                        add_edge(j, k, mSubsetGraph);
     476                        unconstrained[j] = true;
     477                    }
     478                    unconstrained[i] = true;
     479                }
     480                Cudd_RecursiveDeref(mManager, IiIk);
     481            }
     482        }
     483
     484        for (unsigned i = 0; i != k; ++i) {
     485            const Advance * const tmp = std::get<0>(mAdvance[i]);
     486            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
     487            if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
     488                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
     489                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
     490                add_edge(i, k, mConstraintGraph);
     491            }
     492        }
     493    }
     494
     495    mAdvance.emplace_back(adv, Ik, Nk);
     496
     497    return Ck;
     498}
     499
     500/** ------------------------------------------------------------------------------------------------------------- *
     501 * @brief reevaluate
     502 ** ------------------------------------------------------------------------------------------------------------- */
     503void AutoMultiplexing::reevaluate(Next * next, DdNode * value) {
     504
     505    Assign * const initial = cast<Assign>(next->getOperand(0));
     506
     507    if (LLVM_UNLIKELY(mCharacterizationMap[initial] == value)) {
     508        return;
     509    }
     510    mCharacterizationMap[initial] = value;
     511
     512
     513    std::queue<PabloAST *> Q;
     514    flat_set<PabloBlock *> within_scope;
     515
     516    for (PabloBlock * block = next->getParent(); ;) {
     517        within_scope.insert(block);
     518        for (PabloAST * user : block->users()) {
     519            if (within_scope.insert(cast<PabloBlock>(user)).second) {
     520                Q.push(user);
     521            }
     522        }
     523        if (Q.empty()) {
     524            break;
     525        }
     526        block = cast<PabloBlock>(Q.front());
     527        Q.pop();
     528    }
     529
     530    std::unordered_set<PabloAST *> visited;
     531
     532    for (Statement * current = initial; ; ) {
     533        for (PabloAST * user : current->users()) {
     534            if (Statement * stmt = dyn_cast<Statement>(user)) {
     535                if (visited.insert(user).second && within_scope.count(stmt->getParent())) {
     536                    DdNode * bdd = characterize(stmt, false);
     537                    if (bdd && mCharacterizationMap[user] != bdd) {
     538                        mCharacterizationMap[user] = bdd;
     539                        Q.push(stmt);
     540                    }
     541                }
     542            }
     543        }
     544        if (Q.empty()) {
     545            break;
     546        }
     547        current = cast<Statement>(Q.front());
     548        Q.pop();
     549    }
     550
     551}
     552
     553/** ------------------------------------------------------------------------------------------------------------- *
     554 * @brief minimize
     555 * @param entry the entry block of the program
     556 *
     557 * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
     558 * earlier one (assuming its in scope) and replace any contradictions with Zero.
     559 ** ------------------------------------------------------------------------------------------------------------- */
     560inline void AutoMultiplexing::minimize(PabloBlock & entry) {
     561    SubsitutionMap baseMap;
     562    baseMap.insert(Zero(), entry.createZeroes());
     563    baseMap.insert(One(), entry.createOnes());
     564    minimize(entry, baseMap);
     565}
     566
     567/** ------------------------------------------------------------------------------------------------------------- *
     568 * @brief minimize
     569 ** ------------------------------------------------------------------------------------------------------------- */
     570void AutoMultiplexing::minimize(PabloBlock & block, SubsitutionMap & parent) {
     571    SubsitutionMap subsitutionMap(&parent);
     572    for (Statement * stmt : block) {
     573        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     574            // Set the next statement to be the first statement of the inner scope and push the
     575            // next statement of the current statement into the scope stack.
     576            minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
     577            continue;
     578        }
     579
     580        if (isa<Assign>(stmt) || isa<Next>(stmt)) {
     581            continue;
     582        }
     583
     584        DdNode * bdd = mCharacterizationMap[stmt];
     585        PabloAST * replacement = subsitutionMap.test(bdd, stmt);
     586        if (LLVM_UNLIKELY(replacement != nullptr)) {
     587            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
     588                assert (mAdvanceMap.count(stmt));
     589                const auto k = mAdvanceMap[stmt];
     590                const auto m = num_vertices(mConstraintGraph);
     591                for (unsigned i = 0; i != m; ++i) {
     592                    add_edge(k, m, mConstraintGraph);
     593                }
     594            }
     595            Cudd_RecursiveDeref(mManager, bdd);
     596            stmt->replaceWith(replacement);
     597        }
    500598    }
    501599}
     
    505603 ** ------------------------------------------------------------------------------------------------------------- */
    506604inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
     605    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
    507606    return (mConstraintGraph.get_edge(i, j) == 0);
    508607}
     
    869968                    // with the complement of each advance indicated by V.
    870969
    871                     Advance * adv = mAdvance[s];
     970                    Advance * adv = std::get<0>(mAdvance[s]);
    872971                    PabloBlock * pb = adv->getParent();
    873972
    874973                    for (auto i : V) {
    875                         Q.push(mAdvance[i]->getOperand(0));
     974                        Q.push(std::get<0>(mAdvance[i])->getOperand(0));
    876975                    }                   
    877976                    while (Q.size() > 1) {
     
    896995                    std::sort(V.begin(), V.end());
    897996                    for (auto i : V) {
    898                         Q.push(mAdvance[i]);
     997                        Q.push(std::get<0>(mAdvance[i]));
    899998                    }
    900999                    while (Q.size() > 1) {
     
    9611060
    9621061            for (unsigned i = 0; i != n; ++i) {
    963                 V[i] = mAdvance[I[i]];
     1062                V[i] = std::get<0>(mAdvance[I[i]]);
    9641063            }
    9651064
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4610 r4611  
    1313#include <random>
    1414#include <stdint.h>
     15#include <llvm/ADT/DenseMap.h>
    1516
    1617struct DdManager; // forward declare of the CUDD manager
     
    2122class AutoMultiplexing {
    2223
    23     using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>;
     24    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
    2425    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
    2526    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
     
    2930    using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
    3031    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    31     using Advances = std::vector<Advance *>;
     32    // the Advance pointer, input BDD and the BDD variable of the i-th Advance
     33    using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
     34    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
    3235    using IndependentSet = std::vector<ConstraintVertex>;
     36
     37    struct SubsitutionMap {
     38        SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
     39        PabloAST * test(const DdNode * node, PabloAST * stmt) {
     40            PabloAST * replacement = find(node);
     41            if (LLVM_LIKELY(replacement == nullptr)) {
     42                mMap.insert(std::make_pair(node, stmt));
     43            }
     44            return replacement;
     45        }
     46        PabloAST * find(const DdNode * node) const {
     47            auto f = mMap.find(node);
     48            if (LLVM_LIKELY(f == mMap.end())) {
     49                PabloAST * replacement = nullptr;
     50                if (mParent == nullptr) {
     51                    replacement = mParent->find(node);
     52                }
     53                return replacement;
     54            }
     55            return f->second;
     56        }
     57        void insert(const DdNode * node, PabloAST * stmt) {
     58            mMap.insert(std::make_pair(node, stmt));
     59        }
     60    private:
     61        const SubsitutionMap * const mParent;
     62        llvm::DenseMap<const DdNode *, PabloAST *> mMap;
     63    };
    3364
    3465public:
    3566    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
    3667protected:
    37     void initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    38     void characterize(PabloBlock & entry);
     68    void initialize(const std::vector<Var *> & vars, PabloBlock & entry);
     69    void characterize(PabloBlock & block);
     70    DdNode * characterize(Statement * const stmt, const bool throwUncharacterizedOperandError);
     71    DdNode * characterize(Advance * adv, DdNode * input);
     72    void reevaluate(Next * next, DdNode * value);
     73    void minimize(PabloBlock & entry);
     74    void minimize(PabloBlock & block, SubsitutionMap & parent);
     75
    3976    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
    4077    bool generateMultiplexSets(RNG & rng, unsigned k = 1);
     
    68105    ConstraintGraph         mConstraintGraph;
    69106    SubsetGraph             mSubsetGraph;
    70     Advances                mAdvance;   
     107    AdvanceMap              mAdvanceMap;
     108    AdvanceVector           mAdvance;
    71109    MultiplexSetGraph       mMultiplexSetGraph;
    72110};
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4594 r4611  
    132132                    expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
    133133                    break;
    134                 default:
    135                     throw std::runtime_error("Unhandled trivial folding optimization!");
     134                case PabloAST::ClassTypeId::Next:
     135                    expr = stmt;
     136                    break;
     137                default: {
     138                    std::string tmp;
     139                    llvm::raw_string_ostream msg(tmp);
     140                    PabloPrinter::print(stmt, "Unhandled trivial folding optimization! ", msg);
     141                    throw std::runtime_error(msg.str());
     142                }
    136143            }
    137144            stmt = stmt->replaceWith(expr);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4594 r4611  
    136136        mPrev->mNext = this;
    137137    }
     138    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
     139        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
     140        mParent->addUser(&body);
     141    }
    138142}
    139143
     
    153157        mNext->mPrev = this;
    154158    }
     159    if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
     160        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
     161        mParent->addUser(&body);
     162    }
    155163}
    156164
     
    172180        if (LLVM_LIKELY(mNext != nullptr)) {
    173181            mNext->mPrev = mPrev;
     182        }
     183        if (LLVM_UNLIKELY(isa<If>(this) || isa<While>(this))) {
     184            PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
     185            mParent->removeUser(&body);
    174186        }
    175187    }
     
    200212        while (stmt) {
    201213            stmt = stmt->eraseFromParent(recursively);
    202         }
     214        }       
    203215    }
    204216
     
    230242
    231243#ifndef NDEBUG
    232     bool Statement::noRecursiveOperand(const PabloAST * const operand) {
    233         if (operand && isa<Statement>(operand)) {
    234             std::queue<const Statement *> Q;
    235             Q.push(cast<Statement>(operand));
    236             while (!Q.empty()) {
    237                 const Statement * stmt = Q.front();
    238                 if (stmt == this) {
    239                     return false;
    240                 }
    241                 Q.pop();
    242                 for (auto i = 0; i != stmt->getNumOperands(); ++i) {
    243                     const PabloAST * op = stmt->getOperand(i);
    244                     if (isa<Statement>(op)) {
    245                         Q.push(cast<Statement>(op));
    246                     }
    247                 }
    248             }
    249         }
    250         return true;
    251     }
     244bool Statement::noRecursiveOperand(const PabloAST * const operand) {
     245    if (operand && isa<Statement>(operand)) {
     246        std::queue<const Statement *> Q;
     247        Q.push(cast<Statement>(operand));
     248        while (!Q.empty()) {
     249            const Statement * stmt = Q.front();
     250            if (stmt == this) {
     251                return false;
     252            }
     253            Q.pop();
     254            for (auto i = 0; i != stmt->getNumOperands(); ++i) {
     255                const PabloAST * op = stmt->getOperand(i);
     256                if (isa<Statement>(op)) {
     257                    Q.push(cast<Statement>(op));
     258                }
     259            }
     260        }
     261    }
     262    return true;
     263}
    252264#endif
    253265
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4586 r4611  
    220220    inline void setName(const String * const name) {
    221221        mName = name;
    222     }
     222    }   
    223223#ifndef NDEBUG
    224224    bool noRecursiveOperand(const PabloAST * const operand);
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4567 r4611  
    176176        strm  << var->getName();
    177177    }
     178    else if (const Next * next = dyn_cast<const Next>(expr)) {
     179        strm << "Next(" << next->getName() << ")";
     180    }
    178181    else if (const Statement * stmt = dyn_cast<Statement>(expr)) {
    179182        strm << stmt->getName();
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.h

    r4567 r4611  
    1919class PabloPrinter {
    2020public:
    21     using DefinedVars = std::vector<pablo::PabloAST *, pablo::PabloAST::VectorAllocator>;
     21    using DefinedVars = pablo::If::DefinedVars;
    2222    static void print(const pablo::PabloBlock & block, llvm::raw_ostream & strm);
    2323    static void print(const pablo::StatementList & stmts, llvm::raw_ostream & strm);
  • icGREP/icgrep-devel/icgrep/re/re_cc.cpp

    r4519 r4611  
    146146    return cci;
    147147}
     148
     149/** ------------------------------------------------------------------------------------------------------------- *
     150 * @brief rangeIntersect
     151 * @param cc
     152 * @param lo
     153 * @param hi
     154 ** ------------------------------------------------------------------------------------------------------------- */
     155CC * rangeIntersect(const CC * cc, const CodePointType lo, const CodePointType hi) {
     156    assert ("cc cannot be null" && cc);
     157    CC * intersect = makeCC();
     158    for (const auto & p : *cc) {
     159        if ((p.lo_codepoint <= hi) && (p.hi_codepoint >= lo)) {
     160            intersect->insert_range(std::max(lo, p.lo_codepoint), std::min(hi, p.hi_codepoint));
     161        }
     162    }
     163    return intersect;
     164}
     165
     166/** ------------------------------------------------------------------------------------------------------------- *
     167 * @brief rangeGaps
     168 * @param cc
     169 * @param lo
     170 * @param hi
     171 ** ------------------------------------------------------------------------------------------------------------- */
     172CC * rangeGaps(const CC * cc, const CodePointType lo, const CodePointType hi) {
     173    assert ("cc cannot be null" && cc);
     174    CC * gaps = makeCC();
     175    CodePointType cp = lo;
     176    if (cp < hi) {
     177        auto i = cc->cbegin(), end = cc->cend();
     178        for (; i != end && cp < hi; ++i) {
     179            if (i->hi_codepoint < cp) {
     180                continue;
     181            }
     182            else if (i->lo_codepoint > cp) {
     183                gaps->insert_range(cp, i->lo_codepoint - 1);
     184            }
     185            cp = i->hi_codepoint + 1;
     186        }
     187        if (cp < hi) {
     188            gaps->insert_range(cp, hi);
     189        }
     190    }
     191    return gaps;
     192}
     193
     194/** ------------------------------------------------------------------------------------------------------------- *
     195 * @brief outerRanges
     196 * @param cc
     197 ** ------------------------------------------------------------------------------------------------------------- */
     198CC * outerRanges(const CC * cc) {
     199    assert ("cc cannot be null" && cc);
     200    CC * ranges = makeCC();
     201    auto i = cc->cbegin();
     202    const auto end = cc->cend();
     203    for (auto j = i; ++j != end; ) {
     204        if (j->hi_codepoint > i->hi_codepoint) {
     205            ranges->insert_range(i->lo_codepoint, i->hi_codepoint);
     206            i = j;
     207        }
     208    }
     209    return ranges;
     210}
     211
     212/** ------------------------------------------------------------------------------------------------------------- *
     213 * @brief innerRanges
     214 * @param cc
     215 ** ------------------------------------------------------------------------------------------------------------- */
     216CC * innerRanges(const CC * cc) {
     217    assert ("cc cannot be null" && cc);
     218    CC * ranges = makeCC();
     219    auto i = cc->cbegin();
     220    const auto end = cc->cend();
     221    for (auto j = i; ++j != end; ) {
     222        if (j->hi_codepoint <= i->hi_codepoint) {
     223            ranges->insert_range(j->lo_codepoint, j->hi_codepoint);
     224        }
     225        else {
     226            i = j;
     227        }
     228    }
     229    return ranges;
     230}
    148231   
    149232}
  • icGREP/icgrep-devel/icgrep/re/re_cc.h

    r4516 r4611  
    187187
    188188CC * caseInsensitize(const CC * cc);
     189
     190CC * rangeIntersect(const CC * cc, const CodePointType lo, const CodePointType hi);
     191
     192CC * rangeGaps(const CC * cc, const CodePointType lo, const CodePointType hi);
     193
     194CC * outerRanges(const CC * cc);
     195
     196CC * innerRanges(const CC * cc);
     197
    189198}
    190199
Note: See TracChangeset for help on using the changeset viewer.