การออกแบบคอมไพเลอร์ - การเพิ่มประสิทธิภาพโค้ด

การเพิ่มประสิทธิภาพเป็นเทคนิคการแปลงโปรแกรมซึ่งพยายามปรับปรุงโค้ดโดยทำให้ใช้ทรัพยากรน้อยลง (เช่น CPU หน่วยความจำ) และให้ความเร็วสูง

ในการเพิ่มประสิทธิภาพโครงสร้างการเขียนโปรแกรมทั่วไประดับสูงจะถูกแทนที่ด้วยรหัสโปรแกรมระดับต่ำที่มีประสิทธิภาพมาก กระบวนการเพิ่มประสิทธิภาพโค้ดต้องเป็นไปตามกฎสามข้อที่ระบุด้านล่าง:

  • รหัสผลลัพธ์จะต้องไม่เปลี่ยนแปลงความหมายของโปรแกรม แต่อย่างใด

  • การเพิ่มประสิทธิภาพควรเพิ่มความเร็วของโปรแกรมและถ้าเป็นไปได้โปรแกรมควรต้องการจำนวนทรัพยากรน้อยลง

  • การเพิ่มประสิทธิภาพควรเป็นไปอย่างรวดเร็วและไม่ควรทำให้กระบวนการคอมไพล์โดยรวมล่าช้า

ความพยายามสำหรับโค้ดที่ปรับให้เหมาะสมสามารถทำได้ในระดับต่างๆของการรวบรวมกระบวนการ

  • ในตอนแรกผู้ใช้สามารถเปลี่ยน / จัดเรียงโค้ดใหม่หรือใช้อัลกอริทึมที่ดีกว่าในการเขียนโค้ด

  • หลังจากสร้างโค้ดระดับกลางคอมไพลเลอร์สามารถแก้ไขโค้ดกลางได้โดยการคำนวณแอดเดรสและปรับปรุงลูป

  • ในขณะที่สร้างรหัสเครื่องเป้าหมายคอมไพลเลอร์สามารถใช้ประโยชน์จากลำดับชั้นของหน่วยความจำและการลงทะเบียน CPU

การเพิ่มประสิทธิภาพสามารถแบ่งออกเป็นสองประเภทอย่างกว้าง ๆ ได้แก่ แบบอิสระและขึ้นอยู่กับเครื่องจักร

การเพิ่มประสิทธิภาพโดยไม่ขึ้นกับเครื่อง

ในการปรับให้เหมาะสมนี้คอมไพลเลอร์ใช้รหัสกลางและแปลงส่วนหนึ่งของรหัสที่ไม่เกี่ยวข้องกับการลงทะเบียน CPU และ / หรือตำแหน่งหน่วยความจำสัมบูรณ์ ตัวอย่างเช่น:

do
{
   item = 10;
   value = value + item; 
} while(value<100);

รหัสนี้เกี่ยวข้องกับการกำหนดรายการตัวระบุซ้ำ ๆ ซึ่งหากเราวางวิธีนี้:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

ไม่ควรบันทึกเฉพาะรอบของ CPU เท่านั้น แต่สามารถใช้กับโปรเซสเซอร์ใดก็ได้

การปรับให้เหมาะสมขึ้นอยู่กับเครื่อง

การปรับให้เหมาะสมขึ้นอยู่กับเครื่องจะกระทำหลังจากสร้างรหัสเป้าหมายและเมื่อรหัสถูกเปลี่ยนตามสถาปัตยกรรมเครื่องเป้าหมาย เกี่ยวข้องกับการลงทะเบียน CPU และอาจมีการอ้างอิงหน่วยความจำแบบสัมบูรณ์มากกว่าการอ้างอิงแบบสัมพัทธ์ เครื่องมือเพิ่มประสิทธิภาพที่ขึ้นอยู่กับเครื่องพยายามใช้ประโยชน์สูงสุดจากลำดับชั้นของหน่วยความจำ

บล็อกพื้นฐาน

โดยทั่วไปซอร์สโค้ดจะมีคำสั่งจำนวนหนึ่งซึ่งจะดำเนินการตามลำดับเสมอและถือเป็นบล็อคพื้นฐานของโค้ด บล็อกพื้นฐานเหล่านี้ไม่มีคำสั่งกระโดดใด ๆ ในหมู่พวกเขากล่าวคือเมื่อดำเนินการคำสั่งแรกคำสั่งทั้งหมดในบล็อกพื้นฐานเดียวกันจะดำเนินการตามลำดับการปรากฏโดยไม่สูญเสียการควบคุมการไหลของโปรแกรม

โปรแกรมสามารถมีโครงสร้างต่างๆเป็นบล็อกพื้นฐานเช่น IF-THEN-ELSE คำสั่งเงื่อนไข SWITCH-CASE และลูปเช่น DO-WHILE, FOR และ REPEAT-UNTIL เป็นต้น

การระบุบล็อกพื้นฐาน

เราอาจใช้อัลกอริทึมต่อไปนี้เพื่อค้นหาบล็อกพื้นฐานในโปรแกรม:

  • ค้นหาคำสั่งส่วนหัวของบล็อกพื้นฐานทั้งหมดจากจุดเริ่มต้นของบล็อกพื้นฐาน:

    • คำสั่งแรกของโปรแกรม
    • คำสั่งที่เป็นเป้าหมายของสาขาใด ๆ (เงื่อนไข / ไม่มีเงื่อนไข)
    • งบที่เป็นไปตามคำสั่งสาขาใด ๆ
  • คำสั่งส่วนหัวและข้อความต่อไปนี้เป็นบล็อกพื้นฐาน

  • บล็อกพื้นฐานไม่มีข้อความส่วนหัวของบล็อกพื้นฐานอื่น ๆ

บล็อกพื้นฐานเป็นแนวคิดที่สำคัญจากทั้งการสร้างโค้ดและมุมมองการเพิ่มประสิทธิภาพ

บล็อกพื้นฐานมีบทบาทสำคัญในการระบุตัวแปรซึ่งถูกใช้มากกว่าหนึ่งครั้งในบล็อกพื้นฐานเดียว หากมีการใช้ตัวแปรใด ๆ มากกว่าหนึ่งครั้งหน่วยความจำรีจิสเตอร์ที่จัดสรรให้กับตัวแปรนั้นไม่จำเป็นต้องว่างเปล่าเว้นแต่บล็อกจะเสร็จสิ้นการดำเนินการ

ควบคุม Flow Graph

บล็อกพื้นฐานในโปรแกรมสามารถแสดงโดยใช้โฟลว์กราฟควบคุม กราฟโฟลว์การควบคุมแสดงให้เห็นว่าการควบคุมโปรแกรมถูกส่งผ่านไปยังบล็อกต่างๆอย่างไร เป็นเครื่องมือที่มีประโยชน์ที่ช่วยในการเพิ่มประสิทธิภาพโดยช่วยค้นหาลูปที่ไม่ต้องการในโปรแกรม

การเพิ่มประสิทธิภาพลูป

โปรแกรมส่วนใหญ่ทำงานเป็นลูปในระบบ จำเป็นต้องปรับลูปให้เหมาะสมที่สุดเพื่อประหยัดรอบ CPU และหน่วยความจำ ลูปสามารถปรับให้เหมาะสมได้โดยใช้เทคนิคต่อไปนี้:

  • Invariant code: ส่วนของรหัสที่อยู่ในลูปและคำนวณค่าเดียวกันในการวนซ้ำแต่ละครั้งเรียกว่ารหัสที่ไม่แปรผันของการวนซ้ำ รหัสนี้สามารถย้ายออกจากลูปได้โดยบันทึกเพื่อคำนวณเพียงครั้งเดียวแทนที่จะใช้การวนซ้ำแต่ละครั้ง

  • Induction analysis : ตัวแปรเรียกว่าตัวแปรเหนี่ยวนำหากค่าของมันถูกเปลี่ยนแปลงภายในลูปด้วยค่าที่ไม่แปรผันของลูป

  • Strength reduction: มีนิพจน์ที่ใช้รอบ CPU เวลาและหน่วยความจำมากขึ้น นิพจน์เหล่านี้ควรถูกแทนที่ด้วยนิพจน์ที่ถูกกว่าโดยไม่กระทบต่อผลลัพธ์ของนิพจน์ ตัวอย่างเช่นการคูณ (x * 2) มีราคาแพงในแง่ของรอบ CPU มากกว่า (x << 1) และให้ผลลัพธ์เดียวกัน

การกำจัดรหัสตาย

Dead code คือหนึ่งหรือมากกว่าหนึ่งรหัสคำสั่งซึ่ง ได้แก่ :

  • ไม่ว่าจะไม่ถูกประหารชีวิตหรือไม่สามารถเข้าถึงได้
  • หรือหากดำเนินการเอาต์พุตจะไม่ถูกใช้

ดังนั้นโค้ดที่ตายแล้วจึงไม่มีบทบาทในการทำงานของโปรแกรมใด ๆ ดังนั้นจึงสามารถกำจัดได้

รหัสตายบางส่วน

มีคำสั่งรหัสบางส่วนที่มีการใช้ค่าที่คำนวณได้ในบางสถานการณ์เท่านั้นกล่าวคือบางครั้งมีการใช้ค่าและบางครั้งก็ไม่ใช้ รหัสดังกล่าวเรียกว่ารหัสตายบางส่วน

โฟลว์การควบคุมข้างต้นแสดงให้เห็นกลุ่มของโปรแกรมที่ใช้ตัวแปร 'a' เพื่อกำหนดผลลัพธ์ของนิพจน์ 'x * y' สมมติว่าไม่มีการใช้ค่าที่กำหนดให้กับ 'a' ในลูปทันทีที่ตัวควบคุมออกจากลูป 'a' จะถูกกำหนดค่าของตัวแปร 'z' ซึ่งจะใช้ในโปรแกรมในภายหลัง เราสรุปได้ที่นี่ว่ารหัสการมอบหมายของ 'a' ไม่เคยใช้ที่ใดก็ได้ดังนั้นจึงมีสิทธิ์ถูกตัดออก

ในทำนองเดียวกันภาพด้านบนแสดงให้เห็นว่าคำสั่งเงื่อนไขเป็นเท็จเสมอซึ่งหมายความว่าโค้ดที่เขียนด้วยตัวพิมพ์จริงจะไม่ถูกเรียกใช้งานดังนั้นจึงสามารถลบออกได้

ความซ้ำซ้อนบางส่วน

นิพจน์ซ้ำซ้อนถูกคำนวณมากกว่าหนึ่งครั้งในพา ธ คู่ขนานโดยไม่มีการเปลี่ยนแปลงใด ๆ ในตัวถูกดำเนินการในขณะที่นิพจน์บางส่วนซ้ำซ้อนถูกคำนวณมากกว่าหนึ่งครั้งในพา ธ โดยไม่มีการเปลี่ยนแปลงตัวถูกดำเนินการใด ๆ ตัวอย่างเช่น,

[นิพจน์ซ้ำซ้อน]

[นิพจน์ซ้ำซ้อนบางส่วน]

รหัสที่ไม่แปรเปลี่ยนวนซ้ำมีความซ้ำซ้อนบางส่วนและสามารถกำจัดได้โดยใช้เทคนิคการเคลื่อนที่ของรหัส

อีกตัวอย่างหนึ่งของโค้ดที่ซ้ำซ้อนบางส่วนสามารถ:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

เราถือว่าค่าของตัวถูกดำเนินการ (y และ z) จะไม่เปลี่ยนแปลงจากการกำหนดตัวแปร a เป็นตัวแปร c. ที่นี่ถ้าคำสั่งเงื่อนไขเป็นจริง y OP z จะถูกคำนวณสองครั้งหรือครั้งเดียว สามารถใช้การเคลื่อนที่ของโค้ดเพื่อกำจัดความซ้ำซ้อนดังที่แสดงด้านล่าง:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

ที่นี่ไม่ว่าเงื่อนไขจะเป็นจริงหรือเท็จ y OP z ควรคำนวณเพียงครั้งเดียว