POLLY(1) Polly POLLY(1) (NAME) polly - LLVM (RELEASE NOTES) Polly 22 . (THE ARCHITECTURE) Polly LLVM . LLVM-IR . . Polly . LLVM-IR LLVM-IR . [] Polly LLVM (Polly in the LLVM pass pipeline) LLVM -O1/-O2/-O3 clang/opt . Canonicalization () -mem2reg -instcombine -cfgsimplify (early loop unrolling) . IR . Inliner cycle ( ) Scalar Simplification ( ) Simple Loop Optimizations ( ) Inliner () . LLVM . LLVM (inline) . . . (Loop invariant code motion) . Target Specialization ( ) IR . (vectorization) (target specific loop unrolling) ( distribution) . [] Polly : LLVM . Polly . [] Polly LLVM-IR Polly . LLVM IR . C Polly Polly . Polly . IR . Polly -polly-position=early ( ). [] Polly (vectorizer) (template) ++C Polly ( Polly ). IR Polly . Polly . LLVM Polly IR Polly Polly . Polly -polly-position=before-vectorizer . Polly . Polly . [].SH " POLLY CLANG (USING POLLY WITH CLANG)" Polly Clang C/C++ . : : clang/LLVM/Polly ( revision ). Polly Clang Polly tools/polly (checked out) clang opt bugpoint . . Polly Polly -O3 -mllvm -polly (Polly -O1 -O2 -O3 -Os -Oz ). clang -O3 -mllvm -polly file.c OpenMP OpenMP -mllvm -polly-parallel -lgomp CFLAGS . clang -O3 -mllvm -polly -mllvm -polly-parallel -lgomp file.c backend OpenMP OpenMP-backend Polly : -polly-omp-backend[=BACKEND] backend OpenMP BACKEND 'GNU' () 'LLVM' backend OpenMP : -polly-num-threads[=NUM] (threads) NUM (: 0 /OMP runtime ) -polly-scheduling[=SCHED] OpenMP SCHED 'static' 'dynamic' 'guided' 'runtime' () -polly-scheduling-chunksize[=CHUNK] (chunksize ) CHUNK ( 1 ) backend GNU polly-num-threads polly-scheduling "runtime" . : backend (dynamic) chunksize ( ). -mllvm -polly-omp-backend=LLVM -mllvm -polly-num-threads=4 -mllvm -polly-scheduling=dynamic -mllvm -polly-scheduling-chunksize=1 -mllvm -polly-vectorizer=stripmine CFLAGS . clang -O3 -mllvm -polly -mllvm -polly-vectorizer=stripmine file.c Polly Polly (pass manager) . Polly . Polly -O0 clang . LLVM-IR Polly : clang file.c -c -O3 -mllvm -polly -mllvm -polly-dump-before-file=before-polly.ll 'before-polly.ll' LLVM-IR polly SSA (inlining) . Polly 'opt' 'before-polly.ll' . Polly : clang file.c -c -O3 -mllvm -polly -mllvm -debug-pass=Arguments Polly '-polly-detect' '-polly-codegen' . . Polly : opt before-polly.ll -polly-simplify -polly-optree -polly-delicm -polly-simplify -polly-prune-unprofitable -polly-opt-isl -polly-codegen / (legacy) LLVM . IR Polly C/C++/Objective C . . LLVM-IR ('-O0' ) ('-polly-canonicalize'). Polly //. '-disable-O0-optnone' clang 'optnone' . LTO . clang file.c -c -O0 -Xclang -disable-O0-optnone -emit-llvm -S -o - | opt -polly-canonicalize -S '-disable-llvm-passes' LLVM -O0 . -O1 ( -O0) 'optnone' . clang file.c -c -O1 -Xclang -disable-llvm-passes -emit-llvm -S -o - | opt -polly-canonicalize -S Polly (dump) . '-polly-canonicalize' . clang file.c -c -O3 -mllvm -polly -mllvm -polly-position=early -mllvm -polly-dump-before-file=before-polly.ll Polly Polly . -mllvm -option-name CFLAGS clang . Polly Polly -polly-only-func=functionname . LLVM-IR Polly LLVM-IR . Polly polly-no-codegen . SCoP Polly graphviz SCoP . -polly-show -polly-show-only -polly-dot -polly-dot-only. 'show' dotty graphviz SCoP . 'dot' dot SCoP . 'only' . Polly isl . isl Pluto (data- locality) . -polly-optimizer=none . (tiling) . -polly-tiling=false . ( ). / (Import / Export) -polly-import -polly-export . . SCoP . Polly opt-viewer -fsave-optimization-record .opt.yaml . yaml (remark) . Python 2.7 PyYaml Pygments . opt-viewer: llvm/tools/opt-viewer/opt-viewer.py -source-dir /path/to/program/src/ \ /path/to/program/src/foo.opt.yaml \ /path/to/program/src/bar.opt.yaml \ -o ./output yaml ( yaml *.opt.yaml ) opt-viewer . PGO (Hotness) opt-viewer . html . POLLY (HOW TO MANUALLY USE THE INDIVIDUAL PIECES OF POLLY) Polly (passes) Polly . . . 1. LLVM-IR C Polly LLVM-IR LLVM-IR . llvm-link . clang -S -emit-llvm matmul.c -Xclang -disable-O0-optnone -o matmul.ll Polly (canonical form) . LLVM-IR (canonicalization passes) . '-polly-canonicalize' . opt -S -polly-canonicalize matmul.ll -o matmul.preopt.ll 3. SCoP Polly () Polly SCoP SCoP . SCoP 'init_array' 'main'. $ opt -basic-aa -polly-ast -analyze matmul.preopt.ll -polly-process-unprofitable -polly-use-llvm-names :: isl ast :: init_array :: %for.cond1.preheader---%for.end19 if (1) for (int c0 = 0; c0 <= 1535; c0 += 1) for (int c1 = 0; c1 <= 1535; c1 += 1) Stmt_for_body3(c0, c1); else { /* original code */ } :: isl ast :: main :: %for.cond1.preheader---%for.end30 if (1) for (int c0 = 0; c0 <= 1535; c0 += 1) for (int c1 = 0; c1 <= 1535; c1 += 1) { Stmt_for_body3(c0, c1); for (int c2 = 0; c2 <= 1535; c2 += 1) Stmt_for_body8(c0, c1, c2); } else { /* original code */ } 4. SCoP CFG ( graphviz/dotty) Polly graphviz CFG SCoP . '.dot' 'dot' . $ opt -polly-use-llvm-names -basic-aa -view-scops -disable-output matmul.preopt.ll $ opt -polly-use-llvm-names -basic-aa -view-scops-only -disable-output matmul.preopt.ll : o view-scops : main , init_array , print_array o view-scops-only : main-scopsonly , init_array-scopsonly , print_array-scopsonly $ opt -polly-use-llvm-names -basic-aa -polly-scops -analyze matmul.preopt.ll -polly-process-unprofitable [...]Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond1.preheader => for.end19' in function 'init_array': Function: init_array Region: %for.cond1.preheader---%for.end19 Max Loop Depth: 2 Invariant Accesses: { } Context: { : } Assumed Context: { : } Invalid Context: { : 1 = 0 } Arrays { float MemRef_A[*][1536]; // Element size 4 float MemRef_B[*][1536]; // Element size 4 } Arrays (Bounds as pw_affs) { float MemRef_A[*][ { [] -> [(1536)] } ]; // Element size 4 float MemRef_B[*][ { [] -> [(1536)] } ]; // Element size 4 } Alias Groups (0): n/a Statements { Stmt_for_body3 Domain := { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 }; Schedule := { Stmt_for_body3[i0, i1] -> [i0, i1] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] { Stmt_for_body3[i0, i1] -> MemRef_A[i0, i1] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] { Stmt_for_body3[i0, i1] -> MemRef_B[i0, i1] }; } [...]Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond1.preheader => for.end30' in function 'main': Function: main Region: %for.cond1.preheader---%for.end30 Max Loop Depth: 3 Invariant Accesses: { } Context: { : } Assumed Context: { : } Invalid Context: { : 1 = 0 } Arrays { float MemRef_C[*][1536]; // Element size 4 float MemRef_A[*][1536]; // Element size 4 float MemRef_B[*][1536]; // Element size 4 } Arrays (Bounds as pw_affs) { float MemRef_C[*][ { [] -> [(1536)] } ]; // Element size 4 float MemRef_A[*][ { [] -> [(1536)] } ]; // Element size 4 float MemRef_B[*][ { [] -> [(1536)] } ]; // Element size 4 } Alias Groups (0): n/a Statements { Stmt_for_body3 Domain := { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 }; Schedule := { Stmt_for_body3[i0, i1] -> [i0, i1, 0, 0] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] { Stmt_for_body3[i0, i1] -> MemRef_C[i0, i1] }; Stmt_for_body8 Domain := { Stmt_for_body8[i0, i1, i2] : 0 <= i0 <= 1535 and 0 <= i1 <= 1535 and 0 <= i2 <= 1535 }; Schedule := { Stmt_for_body8[i0, i1, i2] -> [i0, i1, 1, i2] }; ReadAccess := [Reduction Type: NONE] [Scalar: 0] { Stmt_for_body8[i0, i1, i2] -> MemRef_C[i0, i1] }; ReadAccess := [Reduction Type: NONE] [Scalar: 0] { Stmt_for_body8[i0, i1, i2] -> MemRef_A[i0, i2] }; ReadAccess := [Reduction Type: NONE] [Scalar: 0] { Stmt_for_body8[i0, i1, i2] -> MemRef_B[i2, i1] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] { Stmt_for_body8[i0, i1, i2] -> MemRef_C[i0, i1] }; } $ opt -basic-aa -polly-use-llvm-names -polly-dependences -analyze matmul.preopt.ll -polly-process-unprofitable [...]Printing analysis 'Polly - Calculate dependences' for region: 'for.cond1.preheader => for.end19' in function 'init_array': RAW dependences: { } WAR dependences: { } WAW dependences: { } Reduction dependences: n/a Transitive closure of reduction dependences: { } [...]Printing analysis 'Polly - Calculate dependences' for region: 'for.cond1.preheader => for.end30' in function 'main': RAW dependences: { 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 } WAR dependences: { } WAW dependences: { 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 } Reduction dependences: n/a Transitive closure of reduction dependences: { } 7. jscop $ opt -basic-aa -polly-use-llvm-names -polly-export-jscop matmul.preopt.ll -polly-process-unprofitable [...]Writing JScop '%for.cond1.preheader---%for.end19' in function 'init_array' to './init_array___%for.cond1.preheader---%for.end19.jscop'. Writing JScop '%for.cond1.preheader---%for.end30' in function 'main' to './main___%for.cond1.preheader---%for.end30.jscop'. 8. jscop SCoP () Polly jscop . . jscop jscop . SCoP main . jscop ( docs/experiments/matmul ). Polly Polly -O3 . $ opt -basic-aa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-ast -analyze -polly-process-unprofitable [...] :: isl ast :: main :: %for.cond1.preheader---%for.end30 if (1) for (int c0 = 0; c0 <= 1535; c0 += 1) for (int c1 = 0; c1 <= 1535; c1 += 1) { Stmt_for_body3(c0, c1); for (int c3 = 0; c3 <= 1535; c3 += 1) Stmt_for_body8(c0, c1, c3); } else { /* original code */ } [...] ( ) Stmt_for_body8 . $ opt -basic-aa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-import-jscop-postfix=interchanged -polly-ast -analyze -polly-process-unprofitable [...] :: isl ast :: main :: %for.cond1.preheader---%for.end30 if (1) { for (int c1 = 0; c1 <= 1535; c1 += 1) for (int c2 = 0; c2 <= 1535; c2 += 1) Stmt_for_body3(c1, c2); for (int c1 = 0; c1 <= 1535; c1 += 1) for (int c2 = 0; c2 <= 1535; c2 += 1) for (int c3 = 0; c3 <= 1535; c3 += 1) Stmt_for_body8(c1, c3, c2); } else { /* original code */ } [...] + (Tiling) . $ opt -basic-aa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-import-jscop-postfix=interchanged+tiled -polly-ast -analyze -polly-process-unprofitable [...] :: isl ast :: main :: %for.cond1.preheader---%for.end30 if (1) { for (int c1 = 0; c1 <= 1535; c1 += 1) for (int c2 = 0; c2 <= 1535; c2 += 1) Stmt_for_body3(c1, c2); for (int c1 = 0; c1 <= 1535; c1 += 64) for (int c2 = 0; c2 <= 1535; c2 += 64) for (int c3 = 0; c3 <= 1535; c3 += 64) for (int c4 = c1; c4 <= c1 + 63; c4 += 1) for (int c5 = c3; c5 <= c3 + 63; c5 += 1) for (int c6 = c2; c6 <= c2 + 63; c6 += 1) Stmt_for_body8(c4, c6, c5); } else { /* original code */ } [...] + + (Strip-mining) (trivially parallelizable) . . - SIMD . $ opt -basic-aa -polly-use-llvm-names matmul.preopt.ll -polly-import-jscop -polly-import-jscop-postfix=interchanged+tiled -polly-ast -analyze -polly-process-unprofitable [...] :: isl ast :: main :: %for.cond1.preheader---%for.end30 if (1) { for (int c1 = 0; c1 <= 1535; c1 += 1) for (int c2 = 0; c2 <= 1535; c2 += 1) Stmt_for_body3(c1, c2); for (int c1 = 0; c1 <= 1535; c1 += 64) for (int c2 = 0; c2 <= 1535; c2 += 64) for (int c3 = 0; c3 <= 1535; c3 += 64) for (int c4 = c1; c4 <= c1 + 63; c4 += 1) for (int c5 = c3; c5 <= c3 + 63; c5 += 1) for (int c6 = c2; c6 <= c2 + 63; c6 += 4) for (int c7 = c6; c7 <= c6 + 3; c7 += 1) Stmt_for_body8(c4, c7, c5); } else { /* original code */ } [...] 9. SCoP (Codegenerate the SCoPs) SCoP polly . -polly-import-jscop jscop . $ opt -S matmul.preopt.ll | opt -S -O3 -o matmul.normalopt.ll $ opt -S matmul.preopt.ll -basic-aa -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 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged'. File could not be read: No such file or directory Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged'. $ opt -S matmul.preopt.ll -basic-aa -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 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged+tiled'. File could not be read: No such file or directory Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged+tiled'. $ opt -S matmul.preopt.ll -basic-aa -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 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged+tiled+vector'. File could not be read: No such file or directory Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged+tiled+vector'. $ opt -S matmul.preopt.ll -basic-aa -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 Reading JScop '%for.cond1.preheader---%for.end19' in function 'init_array' from './init_array___%for.cond1.preheader---%for.end19.jscop.interchanged+tiled+vector'. File could not be read: No such file or directory Reading JScop '%for.cond1.preheader---%for.end30' in function 'main' from './main___%for.cond1.preheader---%for.end30.jscop.interchanged+tiled+vector'. $ llc matmul.normalopt.ll -o matmul.normalopt.s -relocation-model=pic $ gcc matmul.normalopt.s -o matmul.normalopt.exe $ llc matmul.polly.interchanged.ll -o matmul.polly.interchanged.s -relocation-model=pic $ gcc matmul.polly.interchanged.s -o matmul.polly.interchanged.exe $ llc matmul.polly.interchanged+tiled.ll -o matmul.polly.interchanged+tiled.s -relocation-model=pic $ gcc matmul.polly.interchanged+tiled.s -o matmul.polly.interchanged+tiled.exe $ llc matmul.polly.interchanged+tiled+vector.ll -o matmul.polly.interchanged+tiled+vector.s -relocation-model=pic $ gcc matmul.polly.interchanged+tiled+vector.s -o matmul.polly.interchanged+tiled+vector.exe $ llc matmul.polly.interchanged+tiled+vector+openmp.ll -o matmul.polly.interchanged+tiled+vector+openmp.s -relocation-model=pic $ gcc matmul.polly.interchanged+tiled+vector+openmp.s -lgomp -o matmul.polly.interchanged+tiled+vector+openmp.exe 11. (loop interchange) . (vectorization) OpenMP . $ time ./matmul.normalopt.exe real 0m11.295s user 0m11.288s sys 0m0.004s $ time ./matmul.polly.interchanged.exe real 0m0.988s user 0m0.980s sys 0m0.008s $ time ./matmul.polly.interchanged+tiled.exe real 0m0.830s user 0m0.816s sys 0m0.012s $ time ./matmul.polly.interchanged+tiled+vector.exe real 0m5.430s user 0m5.424s sys 0m0.004s $ time ./matmul.polly.interchanged+tiled+vector+openmp.exe real 0m3.184s user 0m11.972s sys 0m0.036s POLLY (TIPS AND TRICKS ON USING AND CONTRIBUTING TO POLLY) (Commit) polly o git-svn bugpoint opt .ll bugpoint . : o $ bugpoint -opt-args : o $ bugpoint crash.ll -polly-codegen -opt-args -polly-canonicalize -polly-process-unprofitable bugpoint LLVM opt -O3 -polly : o $ bugpoint -O3 file.ll -opt-args -polly bugpoint (crash) . : o $ opt -O3 -polly -debug-pass=Arguments . -debug-pass=Arguments . o (bisect) . ( Polly ) (bisect) . LLVM . : . bisect git : . bisect : . LLVM : . (PERFORMANCE) Polly C <- x C + x A x B A B C + x . GEMM GotoBLAS . GEMM . [] Polly Clang+LLVM+Polly Clang Intel(R) Core(TM) i7-7700 . : Polly . : o Polly ( 0db98a4837b6f233063307bb9184374175401922) o Clang ( 3e1d04a92b51ed36163995c96c31a0e4bbb1561d) o LLVM ( 0265ec7ebad69a47f5c899d95295b5eb41aba68e) ninja . . . +----------------------+--------------------+ |Polly | Polly | | | | +----------------------+--------------------+ |964 | 977 | +----------------------+--------------------+ |964 | 980 | +----------------------+--------------------+ |967 | 981 | +----------------------+--------------------+ |967 | 981 | +----------------------+--------------------+ |968 | 982 | +----------------------+--------------------+ Polly Polly . . o Polly o <> o <> (COPYRIGHT) 2010-2026 Polly 22 June 21, 2026 POLLY(1)