docs/HowToManuallyUseTheIndividualPiecesOfPolly.rst

   1 ==================================================
   2 How to manually use the Individual pieces of Polly
   3 ==================================================
   4
   5 Execute the individual Polly passes manually
   6 ============================================
   7
   8 .. sectionauthor:: Singapuram Sanjay Srivallabh
   9
  10 This example presents the individual passes that are involved when optimizing
  11 code with Polly. We show how to execute them individually and explain for
  12 each which analysis is performed or what transformation is applied. In this
  13 example the polyhedral transformation is user-provided to show how much
  14 performance improvement can be expected by an optimal automatic optimizer.
  15
  16 1. **Create LLVM-IR from the C code**
  17 -------------------------------------
  18         Polly works on LLVM-IR. Hence it is necessary to translate the source
  19         files into LLVM-IR. If more than one file should be optimized the
  20         files can be combined into a single file with llvm-link.
  21
  22         .. code-block:: console
  23
  24                 clang -S -emit-llvm matmul.c -Xclang -disable-O0-optnone -o matmul.ll
  25
  26
  27 2. **Prepare the LLVM-IR for Polly**
  28 ------------------------------------
  29
  30         Polly is only able to work with code that matches a canonical form.
  31         To translate the LLVM-IR into this form we use a set of
  32         canonicalication passes. They are scheduled by using
  33         '-polly-canonicalize'.
  34
  35         .. code-block:: console
  36
  37                 opt -S -polly-canonicalize matmul.ll -o matmul.preopt.ll
  38
  39 3. **Show the SCoPs detected by Polly (optional)**
  40 --------------------------------------------------
  41
  42         To understand if Polly was able to detect SCoPs, we print the structure
  43         of the detected SCoPs. In our example two SCoPs are detected. One in
  44         'init_array' the other in 'main'.
  45
  46         .. code-block:: console
  47
  48                 $ opt -basicaa -polly-ast -analyze matmul.preopt.ll -polly-process-unprofitable -polly-use-llvm-names
  49
  50         .. code-block:: guess
  51
  52                 :: isl ast :: init_array :: %for.cond1.preheader---%for.end19
  53
  54                 if (1)
  55
  56                     for (int c0 = 0; c0 <= 1535; c0 += 1)
  57                       for (int c1 = 0; c1 <= 1535; c1 += 1)
  58                         Stmt_for_body3(c0, c1);
  59
  60                 else
  61                     {  /* original code */ }
  62
  63                 :: isl ast :: main :: %for.cond1.preheader---%for.end30
  64
  65                 if (1)
  66
  67                     for (int c0 = 0; c0 <= 1535; c0 += 1)
  68                       for (int c1 = 0; c1 <= 1535; c1 += 1) {
  69                         Stmt_for_body3(c0, c1);
  70                         for (int c2 = 0; c2 <= 1535; c2 += 1)
  71                           Stmt_for_body8(c0, c1, c2);
  72                       }
  73
  74                 else
  75                     {  /* original code */ }
  76
  77 4. **Highlight the detected SCoPs in the CFGs of the program (requires graphviz/dotty)**
  78 ----------------------------------------------------------------------------------------
  79
  80         Polly can use graphviz to graphically show a CFG in which the detected
  81         SCoPs are highlighted. It can also create '.dot' files that can be
  82         translated by the 'dot' utility into various graphic formats.
  83
  84
  85         .. code-block:: console
  86
  87                 $ opt -polly-use-llvm-names -basicaa -view-scops -disable-output matmul.preopt.ll
  88                 $ opt -polly-use-llvm-names -basicaa -view-scops-only -disable-output matmul.preopt.ll
  89
  90         The output for the different functions:
  91
  92         - view-scops : main_, init_array_, print_array_
  93         - view-scops-only : main-scopsonly_, init_array-scopsonly_, print_array-scopsonly_
  94
  95 .. _main:  http://polly.llvm.org/experiments/matmul/scops.main.dot.png
  96 .. _init_array: http://polly.llvm.org/experiments/matmul/scops.init_array.dot.png
  97 .. _print_array: http://polly.llvm.org/experiments/matmul/scops.print_array.dot.png
  98 .. _main-scopsonly: http://polly.llvm.org/experiments/matmul/scopsonly.main.dot.png
  99 .. _init_array-scopsonly: http://polly.llvm.org/experiments/matmul/scopsonly.init_array.dot.png
 100 .. _print_array-scopsonly: http://polly.llvm.org/experiments/matmul/scopsonly.print_array.dot.png
 101
 102 5. **View the polyhedral representation of the SCoPs**
 103 ------------------------------------------------------
 104
 105         .. code-block:: console
 106
 107                 $ opt -polly-use-llvm-names -basicaa -polly-scops -analyze matmul.preopt.ll -polly-process-unprofitable
 108
 109         .. code-block:: guess
 110
 111                 [...]Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond1.preheader => for.end19' in function 'init_array':
 112                     Function: init_array
 113                     Region: %for.cond1.preheader---%for.end19
 114                     Max Loop Depth:  2
 115                         Invariant Accesses: {
 116                         }
 117                         Context:
 118                         {  :  }
 119                         Assumed Context:
 120                         {  :  }
 121                         Invalid Context:
 122                         {  : 1 = 0 }
 123                         Arrays {
 124                             float MemRef_A[*][1536]; // Element size 4
 125                             float MemRef_B[*][1536]; // Element size 4
 126                         }
 127                         Arrays (Bounds as pw_affs) {
 128                             float MemRef_A[*][ { [] -> [(1536)] } ]; // Element size 4
 129                             float MemRef_B[*][ { [] -> [(1536)] } ]; // Element size 4
 130                         }
 131                         Alias Groups (0):
 132                             n/a
 133                         Statements {
 134                             Stmt_for_body3
 135                                 Domain :=
 136                                     { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 };
 137                                 Schedule :=
 138                                     { Stmt_for_body3[i0, i1] -> [i0, i1] };
 139                                 MustWriteAccess :=      [Reduction Type: NONE] [Scalar: 0]
 140                                     { Stmt_for_body3[i0, i1] -> MemRef_A[i0, i1] };
 141                                 MustWriteAccess :=      [Reduction Type: NONE] [Scalar: 0]
 142                                     { Stmt_for_body3[i0, i1] -> MemRef_B[i0, i1] };
 143                         }
 144                 [...]Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond1.preheader => for.end30' in function 'main':
 145                     Function: main
 146                     Region: %for.cond1.preheader---%for.end30
 147                     Max Loop Depth:  3
 148                     Invariant Accesses: {
 149                     }
 150                     Context:
 151                     {  :  }
 152                     Assumed Context:
 153                     {  :  }
 154                     Invalid Context:
 155                     {  : 1 = 0 }
 156                     Arrays {
 157                         float MemRef_C[*][1536]; // Element size 4
 158                         float MemRef_A[*][1536]; // Element size 4
 159                         float MemRef_B[*][1536]; // Element size 4
 160                     }
 161                     Arrays (Bounds as pw_affs) {
 162                         float MemRef_C[*][ { [] -> [(1536)] } ]; // Element size 4
 163                         float MemRef_A[*][ { [] -> [(1536)] } ]; // Element size 4
 164                         float MemRef_B[*][ { [] -> [(1536)] } ]; // Element size 4
 165                     }
 166                     Alias Groups (0):
 167                         n/a
 168                     Statements {
 169                         Stmt_for_body3
 170                             Domain :=
 171                                 { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 };
 172                             Schedule :=
 173                                 { Stmt_for_body3[i0, i1] -> [i0, i1, 0, 0] };
 174                             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 175                                 { Stmt_for_body3[i0, i1] -> MemRef_C[i0, i1] };
 176                         Stmt_for_body8
 177                             Domain :=
 178                                 { Stmt_for_body8[i0, i1, i2] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 and 0 <= i2 <= 1535 };
 179                             Schedule :=
 180                                 { Stmt_for_body8[i0, i1, i2] -> [i0, i1, 1, i2] };
 181                             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 182                                 { Stmt_for_body8[i0, i1, i2] -> MemRef_C[i0, i1] };
 183                             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 184                                 { Stmt_for_body8[i0, i1, i2] -> MemRef_A[i0, i2] };
 185                             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 186                                 { Stmt_for_body8[i0, i1, i2] -> MemRef_B[i2, i1] };
 187                             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 188                                 { Stmt_for_body8[i0, i1, i2] -> MemRef_C[i0, i1] };
 189                     }
 190
 191
 192 6. **Show the dependences for the SCoPs**
 193 -----------------------------------------
 194
 195         .. code-block:: console
 196
 197                 $ opt -basicaa -polly-use-llvm-names -polly-dependences -analyze matmul.preopt.ll -polly-process-unprofitable
 198
 199         .. code-block:: guess
 200
 201                 [...]Printing analysis 'Polly - Calculate dependences' for region: 'for.cond1.preheader => for.end19' in function 'init_array':
 202                         RAW dependences:
 203                                 {  }
 204                         WAR dependences:
 205                                 {  }
 206                         WAW dependences:
 207                                 {  }
 208                         Reduction dependences:
 209                                 n/a
 210                         Transitive closure of reduction dependences:
 211                                 {  }
 212                 [...]Printing analysis 'Polly - Calculate dependences' for region: 'for.cond1.preheader => for.end30' in function 'main':
 213                         RAW dependences:
 214                                 { Stmt_for_body3[i0, i1] -> Stmt_for_body8[i0, i1, 0] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535; Stmt_for_body8[i0, i1, i2] -> Stmt_for_body8[i0, i1, 1 + i2] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 and 0 <= i2 <= 1534 }
 215                         WAR dependences:
 216                                 {  }
 217                         WAW dependences:
 218                                 { Stmt_for_body3[i0, i1] -> Stmt_for_body8[i0, i1, 0] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535; Stmt_for_body8[i0, i1, i2] -> Stmt_for_body8[i0, i1, 1 + i2] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 and 0 <= i2 <= 1534 }
 219                         Reduction dependences:
 220                                 n/a
 221                         Transitive closure of reduction dependences:
 222                                 {  }
 223
 224 7. **Export jscop files**
 225 -------------------------
 226
 227         .. code-block:: console
 228
 229                 $ opt -basicaa -polly-use-llvm-names -polly-export-jscop matmul.preopt.ll -polly-process-unprofitable
 230
 231         .. code-block:: guess
 232
 233                 [...]Writing JScop '%for.cond1.preheader---%for.end19' in function 'init_array' to './init_array___%for.cond1.preheader---%for.end19.jscop'.
 234
 235                 Writing JScop '%for.cond1.preheader---%for.end30' in function 'main' to './main___%for.cond1.preheader---%for.end30.jscop'.
 236
 237
 238
 239 8. **Import the changed jscop files and print the updated SCoP structure (optional)**
 240 -------------------------------------------------------------------------------------
 241
 242         Polly can reimport jscop files, in which the schedules of the statements
 243         are changed. These changed schedules are used to descripe
 244         transformations. It is possible to import different jscop files by
 245         providing the postfix of the jscop file that is imported.
 246
 247         We apply three different transformations on the SCoP in the main
 248         function. The jscop files describing these transformations are
 249         hand written (and available in docs/experiments/matmul).
 250
 251         **No Polly**
 252
 253         As a baseline we do not call any Polly code generation, but only apply the normal -O3 optimizations.
 254
 255         .. code-block:: console
 256
 257                 $ opt -basicaa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-ast -analyze -polly-process-unprofitable
 258
 259         .. code-block:: c
 260
 261                 [...]
 262                 :: isl ast :: main :: %for.cond1.preheader---%for.end30
 263
 264                 if (1)
 265
 266                     for (int c0 = 0; c0 <= 1535; c0 += 1)
 267                       for (int c1 = 0; c1 <= 1535; c1 += 1) {
 268                         Stmt_for_body3(c0, c1);
 269                         for (int c3 = 0; c3 <= 1535; c3 += 1)
 270                           Stmt_for_body8(c0, c1, c3);
 271                       }
 272
 273                 else
 274                     {  /* original code */ }
 275                 [...]
 276
 277         **Loop Interchange (and Fission to allow the interchange)**
 278
 279         We split the loops and can now apply an interchange of the loop dimensions that enumerate Stmt_for_body8.
 280
 281         .. Although I feel (and have created a .jscop) we can avoid splitting the loops.
 282
 283         .. code-block:: console
 284
 285                 $ opt -basicaa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-import-jscop-postfix=interchanged -polly-ast -analyze -polly-process-unprofitable
 286
 287         .. code-block:: c
 288
 289                 [...]
 290                 :: isl ast :: main :: %for.cond1.preheader---%for.end30
 291
 292                 if (1)
 293
 294                     {
 295                       for (int c1 = 0; c1 <= 1535; c1 += 1)
 296                         for (int c2 = 0; c2 <= 1535; c2 += 1)
 297                           Stmt_for_body3(c1, c2);
 298                       for (int c1 = 0; c1 <= 1535; c1 += 1)
 299                         for (int c2 = 0; c2 <= 1535; c2 += 1)
 300                           for (int c3 = 0; c3 <= 1535; c3 += 1)
 301                             Stmt_for_body8(c1, c3, c2);
 302                     }
 303
 304                 else
 305                     {  /* original code */ }
 306                 [...]
 307
 308         **Interchange + Tiling**
 309
 310         In addition to the interchange we now tile the second loop nest.
 311
 312         .. code-block:: console
 313
 314                 $ opt -basicaa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-import-jscop-postfix=interchanged+tiled -polly-ast -analyze -polly-process-unprofitable
 315
 316         .. code-block:: c
 317
 318                 [...]
 319                 :: isl ast :: main :: %for.cond1.preheader---%for.end30
 320
 321                 if (1)
 322
 323                     {
 324                       for (int c1 = 0; c1 <= 1535; c1 += 1)
 325                         for (int c2 = 0; c2 <= 1535; c2 += 1)
 326                           Stmt_for_body3(c1, c2);
 327                       for (int c1 = 0; c1 <= 1535; c1 += 64)
 328                         for (int c2 = 0; c2 <= 1535; c2 += 64)
 329                           for (int c3 = 0; c3 <= 1535; c3 += 64)
 330                             for (int c4 = c1; c4 <= c1 + 63; c4 += 1)
 331                               for (int c5 = c3; c5 <= c3 + 63; c5 += 1)
 332                                 for (int c6 = c2; c6 <= c2 + 63; c6 += 1)
 333                                   Stmt_for_body8(c4, c6, c5);
 334                     }
 335
 336                 else
 337                     {  /* original code */ }
 338                 [...]
 339
 340
 341         **Interchange + Tiling + Strip-mining to prepare vectorization**
 342
 343         To later allow vectorization we create a so called trivially
 344         parallelizable loop. It is innermost, parallel and has only four
 345         iterations. It can be replaced by 4-element SIMD instructions.
 346
 347         .. code-block:: console
 348
 349                 $ opt -basicaa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-import-jscop-postfix=interchanged+tiled -polly-ast -analyze -polly-process-unprofitable
 350
 351         .. code-block:: c
 352
 353                 [...]
 354                 :: isl ast :: main :: %for.cond1.preheader---%for.end30
 355
 356                 if (1)
 357
 358                     {
 359                       for (int c1 = 0; c1 <= 1535; c1 += 1)
 360                         for (int c2 = 0; c2 <= 1535; c2 += 1)
 361                           Stmt_for_body3(c1, c2);
 362                       for (int c1 = 0; c1 <= 1535; c1 += 64)
 363                         for (int c2 = 0; c2 <= 1535; c2 += 64)
 364                           for (int c3 = 0; c3 <= 1535; c3 += 64)
 365                             for (int c4 = c1; c4 <= c1 + 63; c4 += 1)
 366                               for (int c5 = c3; c5 <= c3 + 63; c5 += 1)
 367                                 for (int c6 = c2; c6 <= c2 + 63; c6 += 4)
 368                                   for (int c7 = c6; c7 <= c6 + 3; c7 += 1)
 369                                     Stmt_for_body8(c4, c7, c5);
 370                     }
 371
 372                 else
 373                     {  /* original code */ }
 374                 [...]
 375
 376 9. **Codegenerate the SCoPs**
 377 -----------------------------
 378
 379         This generates new code for the SCoPs detected by polly. If
 380         -polly-import-jscop is present, transformations specified in the
 381         imported jscop files will be applied.
 382
 383
 384         .. code-block:: console
 385
 386                 $ opt -S matmul.preopt.ll | opt -S -O3 -o matmul.normalopt.ll
 387
 388         .. code-block:: console
 389
 390                 $ opt -S matmul.preopt.ll -basicaa -polly-use-llvm-names -polly-import-jscop -polly-import-jscop-postfix=interchanged -polly-codegen -polly-process-unprofitable | opt -S -O3 -o matmul.polly.interchanged.ll
 391
 392         .. code-block:: guess
 393
 394                 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged'.
 395                 File could not be read: No such file or directory
 396                 Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged'.
 397
 398         .. code-block:: console
 399
 400                 $ opt -S matmul.preopt.ll -basicaa -polly-use-llvm-names -polly-import-jscop -polly-import-jscop-postfix=interchanged+tiled -polly-codegen -polly-process-unprofitable | opt -S -O3 -o matmul.polly.interchanged+tiled.ll
 401
 402         .. code-block:: guess
 403
 404                 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged+tiled'.
 405                 File could not be read: No such file or directory
 406                 Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged+tiled'.
 407
 408         .. code-block:: console
 409
 410                 $ opt -S matmul.preopt.ll -basicaa -polly-use-llvm-names -polly-import-jscop -polly-import-jscop-postfix=interchanged+tiled+vector -polly-codegen -polly-vectorizer=polly -polly-process-unprofitable | opt -S -O3 -o matmul.polly.interchanged+tiled+vector.ll
 411
 412         .. code-block:: guess
 413
 414                 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged+tiled+vector'.
 415                 File could not be read: No such file or directory
 416                 Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged+tiled+vector'.
 417
 418         .. code-block:: console
 419
 420                 $ opt -S matmul.preopt.ll -basicaa -polly-use-llvm-names -polly-import-jscop -polly-import-jscop-postfix=interchanged+tiled+vector -polly-codegen -polly-vectorizer=polly -polly-parallel -polly-process-unprofitable | opt -S -O3 -o matmul.polly.interchanged+tiled+openmp.ll
 421
 422         .. code-block:: guess
 423
 424                 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged+tiled+vector'.
 425                 File could not be read: No such file or directory
 426                 Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged+tiled+vector'.
 427
 428
 429 10. **Create the executables**
 430 ------------------------------
 431
 432         .. code-block:: console
 433
 434                 $ llc matmul.normalopt.ll -o matmul.normalopt.s -relocation-model=pic
 435                 $ gcc matmul.normalopt.s -o matmul.normalopt.exe
 436                 $ llc matmul.polly.interchanged.ll -o matmul.polly.interchanged.s -relocation-model=pic
 437                 $ gcc matmul.polly.interchanged.s -o matmul.polly.interchanged.exe
 438                 $ llc matmul.polly.interchanged+tiled.ll -o matmul.polly.interchanged+tiled.s -relocation-model=pic
 439                 $ gcc matmul.polly.interchanged+tiled.s -o matmul.polly.interchanged+tiled.exe
 440                 $ llc matmul.polly.interchanged+tiled+vector.ll -o matmul.polly.interchanged+tiled+vector.s -relocation-model=pic
 441                 $ gcc matmul.polly.interchanged+tiled+vector.s -o matmul.polly.interchanged+tiled+vector.exe
 442                 $ llc matmul.polly.interchanged+tiled+vector+openmp.ll -o matmul.polly.interchanged+tiled+vector+openmp.s -relocation-model=pic
 443                 $ gcc matmul.polly.interchanged+tiled+vector+openmp.s -lgomp -o matmul.polly.interchanged+tiled+vector+openmp.exe
 444
 445 11. **Compare the runtime of the executables**
 446 ----------------------------------------------
 447
 448         By comparing the runtimes of the different code snippets we see that a
 449         simple loop interchange gives here the largest performance boost.
 450         However in this case, adding vectorization and using OpenMP degrades
 451         the performance.
 452
 453         .. code-block:: console
 454
 455                 $ time ./matmul.normalopt.exe
 456
 457                 real    0m11.295s
 458                 user    0m11.288s
 459                 sys     0m0.004s
 460                 $ time ./matmul.polly.interchanged.exe
 461
 462                 real    0m0.988s
 463                 user    0m0.980s
 464                 sys     0m0.008s
 465                 $ time ./matmul.polly.interchanged+tiled.exe
 466
 467                 real    0m0.830s
 468                 user    0m0.816s
 469                 sys     0m0.012s
 470                 $ time ./matmul.polly.interchanged+tiled+vector.exe
 471
 472                 real    0m5.430s
 473                 user    0m5.424s
 474                 sys     0m0.004s
 475                 $ time ./matmul.polly.interchanged+tiled+vector+openmp.exe
 476
 477                 real    0m3.184s
 478                 user    0m11.972s
 479                 sys     0m0.036s
 480