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++ در طول فرایند کامپایل می‌پردازد.

هشدار:

در دسترس قرار دادن 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 را فراهم می‌کند:

رفتار backendهای OpenMP را می‌توان با استفاده از سوئیچ‌های خط فرمان زیر دقیق‌تر تنظیم کرد:

توجه داشته باشید که در زمان نگارش این متن، 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

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 به یک تابع خاص، از گزینهٔ -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 کامپایل کنید https://clang.llvm.org/docs/UsersManual.html#profiling-with-instrumentation تا اطلاعات بسامد اجرا (Hotness) در opt-viewer نمایش داده شود. فایل‌های html حاصل در مرورگر اینترنت قابل مشاهده هستند.

اجرای دستی گذرهای مجزای Polly

این مثال گذرهای (passes) مجزایی را که هنگام بهینه‌سازی کد با Polly دخیل هستند نشان می‌دهد. ما نحوه اجرای آن‌ها را به‌صورت تک‌به‌تک نمایش داده و برای هر یک توضیح می‌دهیم که چه تحلیلی انجام می‌گیرد یا چه تبدیلی اعمال می‌شود. در این مثال تبدیل چندوجهی توسط کاربر ارائه شده تا نشان داده شود که چه میزان بهبود کارایی را می‌توان از یک بهینه‌ساز خودکار ایدئال انتظار داشت.

1. ایجاد LLVM-IR از کد C

clang -S -emit-llvm matmul.c -Xclang -disable-O0-optnone -o matmul.ll

opt -S -polly-canonicalize matmul.ll -o matmul.preopt.ll

3. نمایش SCoPهای شناسایی‌شده توسط Polly (اختیاری)

$ 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)

$ 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

$ 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 (اختیاری)

$ 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 */ }
[...]

$ 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 */ }
[...]

$ 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 */ }
[...]

$ 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)

$ 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. مقایسه زمان اجرای فایل‌های اجرایی

$ 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

ارسال تغییرات (Commit) به شاخه اصلی polly

استفاده از bugpoint برای ردگیری خطاها در فایل‌های حجیم

اشکال‌زدایی پس‌رفت‌هایی که در نقطه‌ای نامشخص در گذشته رخ داده‌اند

در صورت بروز پس‌رفت در کارایی یا صحت عملکرد (برای نمونه، نسخهٔ قبلی Polly طبق انتظار عمل می‌کرد ولی نسخهٔ جدیدتر دچار مشکل شده است)، اجرای تنصیف (bisect) در طول تاریخچهٔ نسخه‌ها، روش استاندارد برای شناسایی کامیتی است که این پس‌رفت را ایجاد کرده است.

پروژهٔ LLVM دارای یک مخزن واحد است که تمام پروژه‌ها را در بر می‌گیرد. این مخزن را می‌توان از این نشانی کلون کرد: https://github.com/llvm/llvm-project. چگونگی اجرای bisect بر روی یک مخزن git در اینجا شرح داده شده است: https://www.metaltoad.com/blog/beginners-guide-git-bisect-process-elimination. فرایند bisect همچنین می‌تواند به‌صورت خودکار انجام شود، همان‌طور که در اینجا توضیح داده شده است: https://www.metaltoad.com/blog/mechanizing-git-bisect-bug-hunting-lazy. یک اسکریپت اجرای ویژهٔ LLVM نیز در اینجا در دسترس است: https://gist.github.com/dcci/891cd98d80b1b95352a407d80914f7cf.

ضرب ماتریسی تعمیم‌یافته با کارایی بالا

ابزار Polly به‌طور خودکار ضرب ماتریسی تعمیم‌یافته را شناسایی کرده و بهینه‌سازی می‌کند؛ محاسبات C ← α ⊗ C ⊕ β ⊗ A ⊗ B، که در آن A و B و C سه ماتریس با اندازهٔ متناسب هستند، عملگرهای ⊕ و ⊗ از نیم‌حلقهٔ ماتریسی متناظر سرچشمه می‌گیرند، α و β مقادیر ثابت هستند، و بتا با صفر برابر نیست. این کار امکان دستیابی به ساختاری بسیار بهینه‌شده، مشابه پیاده‌سازی حرفه‌ای GEMM که در GotoBLAS و جانشینان آن یافت می‌شود را فراهم می‌سازد. ارزیابی کارایی GEMM در شکل زیر نشان داده شده است.

تأثیر Polly بر زمان کامپایل

مجموعهٔ Clang+LLVM+Polly با استفاده از Clang روی سیستمی مبتنی بر پردازندهٔ Intel(R) Core(TM) i7-7700 کامپایل شده‌اند. این آزمایش دو بار تکرار شده است: یک بار با فعال بودن Polly و یک بار بدون آن، تا تأثیر آن بر زمان کامپایل اندازه‌گیری شود.

نسخه‌های زیر مورد استفاده قرار گرفته‌اند:

از سامانهٔ ساخت ninja https://ninja-build.org استفاده شده است.

برای هر دو حالت، کل فرایند کامپایل پنج بار تکرار شد. زمان‌های کامپایل بر حسب ثانیه در جدول زیر آمده است.

میانهٔ زمان کامپایل بدون فعال بودن Polly برابر ۹۶۷ ثانیه و با فعال بودن Polly برابر ۹۸۱ ثانیه است. میزان سربار ۱٫۴٪ است.