CGO’25 เปิดตัวนวัตกรรมใหม่: เทคโนโลยี e-graph แบบถาวรบนพื้นฐาน MLIR แก้ไขปัญหาการเรียงลำดับขั้นตอนคอมไพเลอร์อย่างสมบูรณ์

คำสำคัญ: ความอิ่มตัวของสมการ, e-graph, คอมไพเลอร์, MLIR, การคงอยู่ถาวร, การเพิ่มประสิทธิภาพ

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

คอมไพเลอร์สมัยใหม่มักประกอบด้วยชุดการเพิ่มประสิทธิภาพ (pass) ที่เป็นอิสระต่อกัน แต่ละ pass จะดำเนินการแปลงเฉพาะบนตัวแทนกลาง (IR) เช่น การพับค่าคงที่ การกำจัดโค้ดที่ตายแล้ว การดึงนิพจน์ที่ไม่แปรเปลี่ยนในลูปออกมา เป็นต้น การออกแบบแบบโมดูลาร์นี้แม้จะบำรุงรักษาและขยายได้ง่าย แต่ก็นำมาซึ่งปัญหาคลาสสิก—ปัญหาลำดับขั้น (phase‑ordering problem) Pass การเพิ่มประสิทธิภาพหนึ่งอาจทำลายโอกาสการใช้งานของอีก Pass หนึ่ง และผู้เขียนคอมไพเลอร์ต้องตัดสินใจลำดับของ Pass ด้วยตนเอง ซึ่งมักอาศัยประสบการณ์หรือการวิเคราะห์เชิงฮิวริสติก ไม่สามารถรับประกันผลลัพธ์ที่ดีที่สุดได้

ความอิ่มตัวของสมการ (equality saturation) ให้แนวคิดใหม่ มันไม่ใช่การแทนที่นิพจน์แบบ “ทำลาย” อีกต่อไป แต่เก็บนิพจน์สมมูลทั้งหมดไว้ในโครงสร้างข้อมูลที่เรียกว่า e‑graph และใช้กฎการเขียนใหม่อย่างต่อเนื่องเพื่อเพิ่มนิพจน์ใหม่เข้าไป

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

ความอิ่มตัวของสมการประสบความสำเร็จในความท้าทายด้านการเพิ่มประสิทธิภาพมากมาย เช่น การเพิ่มความแม่นยำจุดลอยตัว (Herbie) การสังเคราะห์ระดับสูง (SEER) การเลือกคำสั่ง (Cranelift) เป็นต้น อย่างไรก็ตาม วิธีการบูรณาการที่มีอยู่ในปัจจุบันมีข้อจำกัดที่ชัดเจน:

• ไม่ว่าจะแปลโปรแกรมไปยังไลบรารีความอิ่มตัวของสมการภายนอก เช่น egg, egglog แล้วแปลกลับหลังจากเพิ่มประสิทธิภาพ ซึ่งทำให้เกิดค่าใช้จ่ายในการแปลและการสูญเสียข้อมูลสมมูล
• หรือสร้างการใช้งาน e‑graph เฉพาะสำหรับแอปพลิเคชันเฉพาะ ซึ่งนำกลับมาใช้ใหม่ได้ยาก

งานที่นำเสนอในบทความนี้เผยแพร่ใน CGO 2025 เสนอวิธีแก้ปัญหาที่รุนแรงและสง่างาม: ฝัง e‑graph โดยตรงลงใน IR ของคอมไพเลอร์ ทำให้เป็นส่วนหนึ่งของคอมไพเลอร์ และเก็บรักษาข้อมูลสมมูลไว้อย่างถาวรตลอดกระบวนการคอมไพล์

ผู้เขียนออกแบบ dialect ใหม่ชื่อ eqsat ขึ้นบนเฟรมเวิร์ก MLIR และการใช้งาน Python ของมันคือ xDSL และปรับปรุงโครงสร้างพื้นฐานการจับคู่รูปแบบของ MLIR เพื่อให้นักพัฒนาสามารถเขียนกฎการเขียนใหม่ด้วยวิธีเดียวกันทุกประการ ซึ่งสามารถใช้ได้ทั้งสำหรับการเขียนใหม่แบบทำลายดั้งเดิม และสำหรับความอิ่มตัวของสมการ โดยการสร้างฟังก์ชันหลักของ Herbie ขึ้นใหม่ ผู้เขียนได้พิสูจน์ความยืดหยุ่นและศักยภาพของวิธีนี้

1. พื้นฐานความอิ่มตัวของสมการ: e-graph และ e-matching

ก่อนเข้าสู่รายละเอียดทางเทคนิค เรามาทบทวนแนวคิดหลักของ e‑graph

e‑graph ประกอบด้วย e‑class หลายคลาส แต่ละ e‑class ประกอบด้วย e‑node หลายโหนด ซึ่ง e‑node เหล่านี้มีความหมายเทียบเท่ากัน e‑node คล้ายกับโหนดในต้นไม้ไวยากรณ์เชิงนามธรรม แต่โหนดย่อยของมันชี้ไปที่ e‑class แทนที่จะเป็นโหนดเฉพาะ

ตัวอย่างเช่น นิพจน์ a * 2 สามารถแสดงเป็น e‑class (เขียนแทนด้วย C1) ที่มี e‑node การคูณหนึ่งตัว โหนดย่อยซ้ายชี้ไปที่ e‑class ของตัวแปร a และโหนดย่อยขวาชี้ไปที่ e‑class ของค่าคงที่ 2 เมื่อใช้กฎการเขียนใหม่ x*2 → x<<1 จะไม่ลบโหนดการคูณเดิม แต่จะเพิ่ม e‑node การเลื่อนบิตซ้ายใหม่เข้าไปใน C1 จึงเก็บทั้งสองรูปแบบไว้ใน e‑class เดียวกัน

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

2. ข้อบกพร่องของวิธีการที่มีอยู่: ข้อจำกัดของไลบรารีภายนอกและการใช้งานเฉพาะ

รูปที่ 1 แสดงการเปรียบเทียบสามวิธีบูรณาการในปัจจุบันอย่างชัดเจน:

รูปที่ 1 | งานวิจัยที่มีอยู่ทำงานเฉพาะระดับนามธรรมเดียวเท่านั้น ไม่ว่าจะเป็น (b) ประสานงานกับไลบรารีความอิ่มตัวของสมการภายนอก หรือ (c) รองรับ e-graph แบบเนทีฟสำหรับสถานการณ์การใช้งานเฉพาะ ในทางตรงกันข้าม วิธีการความอิ่มตัวของสมการแบบถาวรของเรา (d) สามารถนำตรรกะการแปลงคอมไพเลอร์ที่มีอยู่กลับมาใช้ใหม่ และสามารถเก็บรักษาข้อมูลสมมูลที่ได้มาทั่วระดับนามธรรมต่างๆ ได้ โดยรวมแล้ว จะเห็นได้ว่าการใช้งานความอิ่มตัวของสมการในคอมไพเลอร์ทั้งสามประเภทนี้ โซลูชันแบบดั้งเดิมต้องพึ่งพาไลบรารีภายนอกหรือปรับให้เข้ากับสถานการณ์เฉพาะเท่านั้น ซึ่งต่างก็มีปัญหาของระดับนามธรรมเดียวและข้อมูลสมมูลสูญหายได้ง่าย ในขณะที่โซลูชันแบบถาวรของบทความนี้ฝัง e-graph ลงใน IR ของคอมไพเลอร์ ทำให้สามารถเก็บรักษาสมมูลข้ามระดับได้ และยังสามารถนำกระบวนการแปลงที่มีอยู่ของคอมไพเลอร์กลับมาใช้ใหม่ได้โดยตรง ซึ่งเป็นการก้าวข้ามขีดจำกัดการใช้งานของโซลูชันแบบดั้งเดิมโดยพื้นฐาน

• รูปที่ 1a : กระบวนการคอมไพเลอร์แบบดั้งเดิม ลำดับของ pass การเพิ่มประสิทธิภาพคงที่
• รูปที่ 1b : เรียกใช้ไลบรารีความอิ่มตัวของสมการภายนอก โปรแกรมถูกแปลไปยัง IR ของไลบรารี หลังจากอิ่มตัวแล้วจึงแปลกลับเป็น IR ของคอมไพเลอร์ ข้อเสีย: ค่าใช้จ่ายในการแปลสูง และเมื่อดึงออกมา รูปแบบสมมูลอื่นๆ ทั้งหมดจะสูญหายทันที pass ต่อๆ ไปไม่สามารถใช้ข้อมูลนี้ได้อีก
• รูปที่ 1c : การปรับแต่งลึก เช่น acyclic e‑graph ของ Cranelift มันใช้ e‑graph แทน IR โดยตรง แต่เพื่อความเร็วในการคอมไพล์จึงเสียสละความเป็นทั่วไป เช่น ไม่รองรับลูป และไม่สามารถทำงานร่วมกับโครงสร้างพื้นฐานคอมไพเลอร์อื่นๆ (เช่น pass การวิเคราะห์ที่มีอยู่) ได้

วิธีการที่เสนอในบทความนี้ (รูปที่ 1d) คือ การใช้งาน e‑graph ภายในคอมไพเลอร์ในฐานะพลเมืองชั้นหนึ่ง ทำให้สามารถทำงานตลอดกระบวนการคอมไพล์ และนำการวิเคราะห์ การแปลง และกลไกการจับคู่รูปแบบที่มีอยู่กลับมาใช้ใหม่

3. นวัตกรรมหลัก: การฝัง e-graph ลงใน IR ของคอมไพเลอร์

3.1 พื้นฐาน MLIR: ตัวแทนกลาง SSA ที่ขยายได้

การใช้งานในบทความนี้ใช้พื้นฐานจากเฟรมเวิร์ก MLIR (Multi-Level Intermediate Representation) MLIR ใช้ความสามารถในการขยายโดยผู้ใช้เป็นแกนหลักการออกแบบ จัดการการดำเนินการในระดับนามธรรมต่างๆ ผ่าน dialect และใช้รูปแบบ SSA (Static Single Assignment) เพื่อลดความซับซ้อนของการวิเคราะห์และการแปลง

แต่ละการดำเนินการสามารถมี region ได้ และ region ประกอบด้วยบล็อกพื้นฐาน รองรับ graph region เพื่ออนุญาตให้นิยามลูปได้ ดังแสดงในรูปที่ 2 โครงสร้างที่ยืดหยุ่นนี้ให้พื้นฐานในอุดมคติสำหรับการฝัง e-graph ภายในคอมไพเลอร์

รูปที่ 2 | โครงสร้างแบบโมดูลาร์ของ MLIR โดยใช้ SSA เป็นพื้นฐาน ผสมผสานการออกแบบ dialect, การดำเนินการ, แอตทริบิวต์ เป็นต้น ซึ่งสนับสนุนความสามารถในการขยายแกนกลาง ทำให้การฝัง e-graph เป็นไปได้

จากพื้นฐานการใช้งาน Python ของ MLIR คือ xDSL เราได้แนะนำ dialect ใหม่—eqsat ซึ่งแสดง e-graph อย่างสมบูรณ์ใน IR แบบ SSA ผ่านการดำเนินการหลักสี่อย่าง

3.2 การออกแบบ eqsat dialect

ผู้เขียนแนะนำ dialect ใหม่ใน MLIR—eqsat ซึ่งประกอบด้วยการดำเนินการหลักสี่อย่าง เพียงพอที่จะแสดง e‑graph อย่างสมบูรณ์ใน IR แบบ SSA:

• eqsat.eclass : รับค่า (ซึ่งเป็นผลลัพธ์ของ e‑node) หนึ่งค่าขึ้นไป สร้างค่า SSA ที่แทน e‑class นั้น แต่ละโอเปอแรนด์ของมันสอดคล้องกับ e‑node หนึ่งตัว
• eqsat.const_eclass : รูปแบบแปรผันที่ออกแบบมาเฉพาะสำหรับค่าคงที่ มันถือแอตทริบิวต์ค่าคงที่โดยตรง และสามารถกระตุ้นกลไกการพับค่าคงที่ของ MLIR ได้
• eqsat.egraph : การดำเนินการ graph region ซึ่งภายในประกอบด้วยการดำเนินการ eclass ทั้งหมดที่เกี่ยวข้องกับ e‑graph นั้น graph region อนุญาตให้นิยามแบบวนซ้ำได้ ซึ่งสำคัญสำหรับการแสดงลูปที่ถูกนำเข้ามาโดยการเขียนใหม่ (เช่น a + 0 → a)
• eqsat.yield : เป็นตัวจบ (terminator) ของ egraph ซึ่งเปิดเผยผลลัพธ์ e‑class ที่ระบุให้กับภายนอก

กระบวนการแปลงฟังก์ชันทั่วไปเป็น e‑graph นั้นตรงไปตรงมา: pass ของคอมไพเลอร์จะสำรวจฟังก์ชัน ห่อหุ้มผลลัพธ์ของแต่ละการดำเนินการด้วย eqsat.eclass และแทนที่การอ้างอิงทั้งหมดไปยังค่าเดิมด้วยการอ้างอิงไปยังผลลัพธ์ e‑class ที่สอดคล้องกัน Listing 3 แสดงการแปลงนี้

Listing 3 | โดยการแทรกการดำเนินการเช่น eqsat.eclass แปลง IR ทั่วไปเป็นการแสดง e‑graph ด้านขวาคือการแสดงภาพ e‑graph ที่เทียบเท่า กรอบเส้นประแทน e‑class

เมื่อใช้การเขียนใหม่ x*2 → x<<1 การดำเนินการเลื่อนบิตซ้ายใหม่และค่าคงที่ของมันถูกสร้างขึ้น แต่การดำเนินการคูณเดิมไม่ถูกลบออก แต่เพิ่มผลลัพธ์ของมันเป็นสมาชิกของ e‑class เดียวกัน (Listing 4) นี่คือแก่นแท้ของความอิ่มตัวของสมการ—เก็บรักษารูปแบบสมมูลทั้งหมดไว้

Listing 4 | หลังจากใช้การเขียนใหม่ eqsat.eclass ตอนนี้ประกอบด้วยสมาชิกสองตัว: การคูณและการเลื่อนบิตซ้าย ทำให้ e‑class ขยายตัว

3.3 จากเขียนใหม่แบบดั้งเดิมสู่ e-matching: การปรับปรุง PDL

MLIR มีเฟรมเวิร์กการเขียนใหม่แบบประกาศที่ทรงพลังคือ PDL (Pattern Definition Language) นักพัฒนาสามารถเขียนรูปแบบด้วย PDL จากนั้นคอมไพล์เป็นตัวจับคู่ที่มีประสิทธิภาพ (dialect pdl_interp)

โดยดั้งเดิมแล้ว ตัวจับคู่ PDL เป็นแบบทำลาย—รูปแบบที่จับคู่ได้จะถูกแทนที่ ผู้เขียนเก็บไวยากรณ์ของ PDL ไว้ แต่สร้างอินเทอร์พรีเตอร์ของ pdl_interp ขึ้นใหม่ เพื่อให้สามารถรับรู้ถึงชั้นทางอ้อมของ eqsat.eclass และรองรับการย้อนกลับ (backtracking)

รูปที่ 3 | ความแตกต่างหลักระหว่างการเขียนใหม่ MLIR แบบดั้งเดิมกับการเชื่อมโยงการดำเนินการใน eqsat ในเฟรมเวิร์กแบบดั้งเดิม ผลลัพธ์ของการดำเนินการสอดคล้องหนึ่งต่อหนึ่งกับแหล่งที่มาของคำจำกัดความ ในขณะที่ eqsat เนื่องจากแนะนำ e-class ค่าหนึ่งค่าสอดคล้องกับการดำเนินการสมมูลหลายอย่าง ซึ่งทำลายความสัมพันธ์ผกผันของการดำเนินการเดิม

ความท้าทายสำคัญอยู่ที่การดำเนินการเช่น pdl_interp.get_defining_op และ pdl_interp.get_result
* ใน IR ทั่วไป พวกมันเป็นการดำเนินการผกผันซึ่งกันและกัน
* แต่ใน e‑graph ค่าหนึ่งค่าอาจถูกนิยามโดย e‑node หลายตัว get_defining_op จำเป็นต้องคืนค่าการดำเนินการนิยามที่เป็นไปได้ทั้งหมด

อินเทอร์พรีเตอร์จัดการโดยการรักษาจุดย้อนกลับ: เมื่อเส้นทางหนึ่งล้มเหลว จะย้อนกลับไปยังจุดเลือกล่าสุดและลอง e‑node ถัดไปใน e‑class

นอกจากนี้ pdl_interp.create_operation ไม่สร้างการดำเนินการใหม่โดยสุ่มสี่สุ่มห้าอีกต่อไป แต่ตรวจสอบก่อนว่ามีการดำเนินการเดียวกันอยู่แล้วหรือไม่ (hashconsing) เพื่อหลีกเลี่ยงการซ้ำซ้อน pdl_interp.replace ไม่ลบการดำเนินการเดิมอีกต่อไป แต่เพิ่มค่าที่แทนที่เข้าไปใน e‑class ที่สอดคล้องกัน

3.4 การเพิ่มประสิทธิภาพ e-matching: หลีกเลี่ยงการระเบิดแบบเอ็กซ์โพเนนเชียล

การรวมรูปแบบ PDL หลายรูปแบบเป็นตัวจับคู่เดียวอย่างง่ายๆ และใช้สำหรับ e‑matching โดยตรงจะนำไปสู่หายนะด้านประสิทธิภาพ สาเหตุคือกลยุทธ์การลดระดับจาก PDL ไปเป็น pdl_interp เริ่มต้นให้ความสำคัญกับการตรวจสอบโครงสร้างก่อน แล้วจึงตรวจสอบความหมาย

ตัวอย่างเช่น สำหรับรูปแบบ f(a, g(a)) ตัวจับคู่จะรับโอเปอแรนด์สองตัวของการดำเนินการ

⚠️ หมายเหตุ: เนื้อหาได้รับการแปลโดย AI และตรวจสอบโดยมนุษย์ หากมีข้อผิดพลาดโปรดแจ้ง

☕ สนับสนุนค่ากาแฟทีมงาน

หากคุณชอบบทความนี้ สามารถสนับสนุนเราได้ผ่าน PromptPay

SCAN TO PAY WITH ANY BANK