حلقه‌های نرمال‌شده

در علوم کامپیوتر، یک حلقهٔ نرمال (که بعضاً حلقهٔ خوش‌رفتار نامیده می‌شود)، حلقه‌ای است که در آن متغیر حلقه از ۰ (یا هر ثابت) شروع می‌شود و تا زمان تحقق شرط خروج، در هر تکرار یک افزایش می‌یابد. حلقه‌های نرمال‌شده برای نظریه کامپایلر، تجزیه و تحلیل وابستگی حلقه بسیار مهم هستند زیرا تجزیه و تحلیل وابستگی داده‌ها را ساده می‌کنند.

حلقه‌های خوش‌رفتار

یک حلقهٔ خوش‌رفتار معمولاً به شکل زیر است:

for ( i = 0; i <MAX; i++ )
  a[i] = b[i] + 5;

از آنجا که این افزایش یک‌واحدی و ثابت است، به راحتی می‌توان دید که اگر هر دوی a و b از MAX بزرگتر باشند، این حلقه هرگز به حافظه خارج از محدوده اختصاص یافته دسترسی نخواهد داشت.

حلقه‌های غیرنرمال

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

یک مثال ساده از حلقه‌های غیرنرمال، حلقهٔ زیر است، که از ابتدا (صفر) شروع نمی‌شود و بعد هر دور بیش از یک افزایش می‌یابد:

// Example 1
for ( i = 7; i <MAX; i+=3 )
  a[i] = b[i] + 5;

یک مثال پیچیده‌تر، با یک شرط خروج اضافی:

// Example 2
for ( i = 7; i <MAX || i> MIN; i+=3 )
  a[i] = b[i] + 5;

حلقه‌ها همچنین می‌توانند رفتار غیرقابل‌پیش‌بینی در طول زمان اجرا داشته باشند. مانند زمانی که که شرایط خروج به مقدار داده‌های اصلاح‌شده بستگی دارد:

// Example 3
for ( i = 7; i <MAX && a[i]; i+=3 )
  a[i] = b[i] + 5;

یا حتی محاسبات پویا با استفاده از فراخوانی تابع‌ها:

// Example 4
for ( i = start(); i <max(); i+=increment() )
  a[i] = b[i] + 5;

حلقه‌های معکوس نیز بسیار ساده هستند و می‌توان آن‌ها را به راحتی نرمال کرد:

// Example 5
for ( i = MAX; i> 0; i-- )
  a[i] = b[i] + 5;

تبدیل به یک حلقهٔ نرمال‌شده

اگر حلقهٔ غیرنرمال رفتار پویایی نداشته باشد، تبدیل آن به یک حلقهٔ نرمال معمولاً بسیار آسان است. به عنوان مثال، اولین مثال (مثال ۱) بالا را می‌توان به راحتی مانند زیر نرمال کرد:

// Example 1 -> normalized
for ( i = 0; i <(MAX-7)/3; i++ )
  a[i*3+7] = b[i*3+7] + 5;

در حالی که مثال سوم می‌تواند تا حدی نرمال شود تا بتواند برخی موازی‌سازی‌ها را امکان‌پذیر کند، اما با این وجود ندانستن تعداد دقیق دفعاتی که حلقه اجرا می‌شود (عمر حلقه)، این کار را سخت‌تر می‌کند.

شروع از عدد ۷ چندان مشکلی ندارد، به شرطی که این افزایش منظم باشد؛ ترجیحاً یک. وقتی چندین جمله در داخل حلقه از ایندکس استفاده می‌کنند، ممکن است تعدادی متغیره موقت خصوصی برای مقابله با مراحل تکرار مختلف و سرعت‌های متفاوت هر دور حلقه ایجاد شوند.

نرمال‌سازی حلقهٔ معکوس (مثال ۵) نیز آسان است:

// Example 5 -> normalized
for ( i = 0; i <MAX; i++ )
  a[MAX-i] = b[MAX-i] + 5;

توجه داشته باشید که دسترسی هنوز برعکس است. در این حالت، منطقی نیست که آن را به حالت برعکس رها کنید (زیرا هیچ وابستگی به داده وجود ندارد)، اما در صورت وجود وابستگی، باید احتیاط کرد تا جهت دسترسی نیز برگردد، زیرا این امر می‌تواند ترتیب مقداردهی‌ها را مختل کند.

تبدیل‌های غیرممکن

مثال ۴ (که در بالا آمده‌است) پیش‌بینی هرچیزی از آن حلقه را غیرممکن می‌کند. تا زمانی که خود توابع بدیهی (ثابت) نباشند، راهی وجود ندارد که بدانید حلقه از کجا شروع می‌شود، متوقف می‌شود و بعد از هر دور اندیس چه‌مقدار افزایش می‌یابد. موازی‌سازی این حلقه‌ها نه تنها سخت است، بلکه عمل‌کرد افتضاحی نیز دارد.

در هر تکرار، حلقه دو تابع (حداکثر () و افزایش ()) را ارزیابی می‌کند. حتی اگر توابع inline باشند، شرایط بسیار پیچیده می‌شود که ارزش بهینه‌سازی را ندارد. برنامه‌نویس باید بیشتر مراقب باشد تا این حلقه‌ها را به جز در موارد کاملاً ضروری ایجاد نکند.

یکی دیگر از خطرهای این حلقه‌ها، زمانی‌ست که ارزیابی به داده‌های اصلاح‌شده بستگی داشته باشد. به عنوان مثال، یکی از خطاهای معمول هنگام استفاده از اشاره‌گرها (iterator)، این است که مواردی از لیست را هنگام تغییر در لیست حذف کنید، یا برای خروج از حلقه به اندازه‌هایی وابسته باشید که دیگر صحیح نیستند.