LLVM จากมุมมองของ Go

การพัฒนาคอมไพเลอร์เป็นงานที่ยากมาก แต่โชคดีที่การพัฒนาโครงการเช่น LLVM การแก้ปัญหานี้ง่ายขึ้นอย่างมากซึ่งช่วยให้แม้แต่โปรแกรมเมอร์เพียงคนเดียวสามารถสร้างภาษาใหม่ที่มีประสิทธิภาพใกล้เคียงกับ C การทำงานกับ LLVM นั้นซับซ้อนเนื่องจากความจริงที่ว่าสิ่งนี้ ระบบแสดงด้วยโค้ดจำนวนมหาศาล พร้อมด้วยเอกสารประกอบเพียงเล็กน้อย เพื่อพยายามแก้ไขข้อบกพร่องนี้ ผู้เขียนเนื้อหาซึ่งเรากำลังเผยแพร่ในวันนี้ จะแสดงตัวอย่างโค้ดที่เขียนใน Go และแสดงให้เห็นว่ามีการแปลอย่างไรเป็นครั้งแรก ไป สสสจากนั้นใน LLVM IR โดยใช้คอมไพเลอร์ จิ๋วGO. รหัส Go SSA และ LLVM IR ได้รับการแก้ไขเล็กน้อยเพื่อลบสิ่งที่ไม่เกี่ยวข้องกับคำอธิบายที่ให้ไว้ที่นี่ เพื่อให้คำอธิบายเข้าใจได้ง่ายขึ้น

ตัวอย่างแรก

ฟังก์ชันแรกที่ฉันจะดูที่นี่คือกลไกง่ายๆ ในการบวกตัวเลข:

func myAdd(a, b int) int{
    return a + b
}

ฟังก์ชันนี้เรียบง่ายมาก และบางที ไม่มีอะไรจะง่ายไปกว่านี้แล้ว แปลเป็นโค้ด Go SSA ต่อไปนี้:

func myAdd(a int, b int) int:
entry:
    t0 = a + b                                                    int
    return t0

ด้วยมุมมองนี้ คำแนะนำชนิดข้อมูลจะถูกวางไว้ทางด้านขวาและสามารถละเว้นได้ในกรณีส่วนใหญ่

ตัวอย่างเล็กๆ น้อยๆ นี้ช่วยให้คุณเห็นแก่นแท้ของแง่มุมหนึ่งของ SSA แล้ว กล่าวคือ เมื่อแปลงโค้ดเป็นรูปแบบ SSA แต่ละนิพจน์จะถูกแบ่งออกเป็นส่วนพื้นฐานที่สุดที่ประกอบด้วย ในกรณีของเราคือคำสั่ง return a + bอันที่จริงแล้ว แสดงถึงการดำเนินการสองรายการ: บวกตัวเลขสองตัวและส่งกลับผลลัพธ์

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

รหัส Go SSA แปลงเป็น LLVM IR ได้อย่างง่ายดาย:

define i64 @myAdd(i64 %a, i64 %b) {
entry:
  %0 = add i64 %a, %b
  ret i64 %0
}

สิ่งที่สังเกตได้ก็คือ แม้ว่าจะใช้โครงสร้างทางวากยสัมพันธ์ที่แตกต่างกันที่นี่ แต่โครงสร้างของฟังก์ชันโดยพื้นฐานแล้วไม่มีการเปลี่ยนแปลง รหัส LLVM IR นั้นแข็งแกร่งกว่าโค้ด Go SSA เล็กน้อย ซึ่งคล้ายกับ C ในการประกาศฟังก์ชัน อันดับแรกจะมีคำอธิบายของประเภทข้อมูลที่ส่งคืน ประเภทอาร์กิวเมนต์จะถูกระบุก่อนชื่ออาร์กิวเมนต์ นอกจากนี้ เพื่อให้การแยกวิเคราะห์ IR ง่ายขึ้น ชื่อของเอนทิตีส่วนกลางจะขึ้นต้นด้วยสัญลักษณ์ @และหน้าชื่อท้องถิ่นจะมีสัญลักษณ์ % (ฟังก์ชันก็ถือเป็นเอนทิตีส่วนกลางด้วย)

สิ่งหนึ่งที่ควรทราบเกี่ยวกับโค้ดนี้คือการตัดสินใจแสดงประเภทของ Go intซึ่งสามารถแสดงเป็นค่า 32 บิตหรือ 64 บิต ขึ้นอยู่กับคอมไพลเลอร์และเป้าหมายของการคอมไพล์ ซึ่งเป็นที่ยอมรับเมื่อ LLVM สร้างโค้ด IR นี่เป็นหนึ่งในหลายเหตุผลที่รหัส LLVM IR ไม่ใช่แพลตฟอร์มที่เป็นอิสระอย่างที่หลายๆ คนคิด โค้ดดังกล่าวซึ่งสร้างขึ้นสำหรับแพลตฟอร์มเดียว ไม่สามารถนำไปใช้และคอมไพล์สำหรับแพลตฟอร์มอื่นได้ง่ายๆ (เว้นแต่คุณจะเหมาะสมสำหรับการแก้ปัญหานี้ ด้วยความห่วงใย).

อีกจุดที่น่าสนใจที่น่าสังเกตก็คือประเภท i64 ไม่ใช่จำนวนเต็มที่มีเครื่องหมาย แต่เป็นกลางในแง่ของการแสดงเครื่องหมายของตัวเลข ขึ้นอยู่กับคำแนะนำ ซึ่งสามารถแสดงทั้งหมายเลขที่ลงนามและไม่ได้ลงนาม ในกรณีของการเป็นตัวแทนของการดำเนินการบวก สิ่งนี้ไม่สำคัญ ดังนั้นจึงไม่มีความแตกต่างในการทำงานกับหมายเลขที่ลงนามหรือไม่ได้ลงนาม ที่นี่ฉันต้องการทราบว่าในภาษา C การล้นตัวแปรจำนวนเต็มที่ลงนามนำไปสู่พฤติกรรมที่ไม่ได้กำหนด ดังนั้นส่วนหน้าของ Clang จึงเพิ่มแฟล็กให้กับการดำเนินการ nsw (ไม่มีการห่อแบบลงนาม) ซึ่งบอก LLVM ว่าสามารถสรุปได้ว่าการเพิ่มจะไม่ล้น

นี่อาจมีความสำคัญสำหรับการเพิ่มประสิทธิภาพบางอย่าง เช่น เพิ่มค่าสองค่า i16 บนแพลตฟอร์ม 32 บิต (พร้อมรีจิสเตอร์ 32 บิต) จำเป็นต้องมีการดำเนินการขยายเครื่องหมายเพื่อให้คงอยู่ในช่วง i16. ด้วยเหตุนี้ การดำเนินการจำนวนเต็มตามขนาดรีจิสเตอร์ของเครื่องจึงมักจะมีประสิทธิภาพมากกว่า

จะเกิดอะไรขึ้นต่อไปกับรหัส IR นี้ ยังไม่เป็นที่สนใจของเราในตอนนี้ โค้ดได้รับการปรับให้เหมาะสม (แต่ในกรณีของตัวอย่างง่ายๆ เช่นของเรา ไม่มีการปรับให้เหมาะสม) จากนั้นจึงแปลงเป็นรหัสเครื่อง

ตัวอย่างที่สอง

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

func sum(numbers []int) int {
    n := 0
    for i := 0; i < len(numbers); i++ {
        n += numbers[i]
    }
    return n
}

รหัสนี้แปลงเป็นรหัส Go SSA ต่อไปนี้:

func sum(numbers []int) int:
entry:
    jump for.loop
for.loop:
    t0 = phi [entry: 0:int, for.body: t6] #n                       int
    t1 = phi [entry: 0:int, for.body: t7] #i                       int
    t2 = len(numbers)                                              int
    t3 = t1 < t2                                                  bool
    if t3 goto for.body else for.done
for.body:
    t4 = &numbers[t1]                                             *int
    t5 = *t4                                                       int
    t6 = t0 + t5                                                   int
    t7 = t1 + 1:int                                                int
    jump for.loop
for.done:
    return t0

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

ในความเป็นจริงที่นี่คุณสามารถใส่ใจกับความจริงที่ว่าโปรแกรมไม่ได้แบ่งออกเป็นบล็อกโดยใช้เครื่องหมายปีกกา (เช่นเดียวกับในตระกูลภาษา C) มันถูกแบ่งตามป้ายกำกับ ชวนให้นึกถึงภาษาแอสเซมบลี และนำเสนอในรูปแบบของบล็อกพื้นฐาน ใน SSA บล็อกพื้นฐานถูกกำหนดให้เป็นลำดับโค้ดที่ต่อเนื่องกันโดยเริ่มจากป้ายกำกับและลงท้ายด้วยคำแนะนำในการบล็อกขั้นพื้นฐาน เช่น - return и jump.

รายละเอียดที่น่าสนใจอีกประการหนึ่งของโค้ดนี้แสดงโดยคำสั่ง phi. คำแนะนำค่อนข้างผิดปกติและอาจใช้เวลาพอสมควรในการทำความเข้าใจ จำไว้ SSA ย่อมาจาก Static Single Assignment นี่คือการแสดงระดับกลางของโค้ดที่ใช้โดยคอมไพเลอร์ ซึ่งแต่ละตัวแปรจะได้รับการกำหนดค่าเพียงครั้งเดียว เหมาะอย่างยิ่งสำหรับการแสดงฟังก์ชันง่ายๆ เช่นฟังก์ชันของเรา myAddแสดงไว้ข้างต้น แต่ไม่เหมาะสำหรับฟังก์ชันที่ซับซ้อนมากขึ้น เช่น ฟังก์ชันที่กล่าวถึงในส่วนนี้ sum. โดยเฉพาะอย่างยิ่ง ตัวแปรจะเปลี่ยนแปลงระหว่างการดำเนินการของลูป i и n.

SSA ข้ามข้อจำกัดในการกำหนดค่าตัวแปรเมื่อใช้สิ่งที่เรียกว่าคำสั่ง phi (ชื่อของมันนำมาจากอักษรกรีก) ความจริงก็คือในการสร้างการแสดงโค้ด SSA สำหรับภาษาเช่น C คุณต้องใช้เทคนิคบางอย่าง ผลลัพธ์ของการเรียกคำสั่งนี้คือค่าปัจจุบันของตัวแปร (i หรือ n) และใช้รายการบล็อกพื้นฐานเป็นพารามิเตอร์ ตัวอย่างเช่น พิจารณาคำสั่งนี้:

t0 = phi [entry: 0:int, for.body: t6] #n

ความหมายมีดังนี้: ถ้าบล็อกพื้นฐานก่อนหน้านี้เป็นบล็อก entry (อินพุต) จากนั้น t0 เป็นค่าคงที่ 0และถ้าเป็นบล็อกพื้นฐานก่อนหน้านี้ for.bodyจากนั้นคุณจะต้องรับค่านั้น t6 จากบล็อกนี้ ทั้งหมดนี้อาจดูค่อนข้างลึกลับ แต่กลไกนี้คือสิ่งที่ทำให้ SSA ทำงานได้ จากมุมมองของมนุษย์ ทั้งหมดนี้ทำให้โค้ดเข้าใจยาก แต่การที่แต่ละค่าได้รับการกำหนดเพียงครั้งเดียวทำให้การปรับให้เหมาะสมหลายอย่างง่ายขึ้นมาก

โปรดทราบว่าหากคุณเขียนคอมไพเลอร์ของคุณเอง คุณจะไม่ต้องจัดการกับเรื่องประเภทนี้อีกต่อไป แม้แต่เสียงดังกราวก็ไม่ได้สร้างคำแนะนำทั้งหมดนี้ phiก็ใช้กลไก alloca (คล้ายกับการทำงานกับตัวแปรท้องถิ่นทั่วไป) จากนั้นเมื่อรันการเพิ่มประสิทธิภาพ LLVM ที่เรียกว่า mem2reg, คำแนะนำ alloca แปลงเป็นรูปแบบ SSA อย่างไรก็ตาม TinyGo รับอินพุตจาก Go SSA ซึ่งแปลงเป็นรูปแบบ SSA ได้อย่างสะดวกแล้ว

นวัตกรรมอีกประการหนึ่งของส่วนของรหัสระดับกลางที่อยู่ระหว่างการพิจารณาคือการเข้าถึงองค์ประกอบชิ้นด้วยดัชนีจะแสดงในรูปแบบของการดำเนินการคำนวณที่อยู่และการดำเนินการในการยกเลิกการอ้างอิงตัวชี้ผลลัพธ์ ที่นี่คุณสามารถดูการเพิ่มค่าคงที่ลงในรหัส IR ได้โดยตรง (เช่น - 1:int). ในตัวอย่างที่มีฟังก์ชัน myAdd สิ่งนี้ไม่ได้ใช้ ตอนนี้เราไม่มีฟีเจอร์เหล่านั้นแล้ว ลองมาดูกันว่าโค้ดนี้จะเป็นอย่างไรเมื่อแปลงเป็นรูปแบบ LLVM IR:

define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
  br label %for.loop

for.loop:                                         ; preds = %for.body, %entry
  %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
  %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
  %2 = icmp slt i64 %1, %len
  br i1 %2, label %for.body, label %for.done

for.body:                                         ; preds = %for.loop
  %3 = getelementptr i64, i64* %ptr, i64 %1
  %4 = load i64, i64* %3
  %5 = add i64 %0, %4
  %6 = add i64 %1, 1
  br label %for.loop

for.done:                                         ; preds = %for.loop
  ret i64 %0
}

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

ขั้นแรก คุณจะเห็นลายเซ็นฟังก์ชันที่แตกต่างไปจากเดิมอย่างสิ้นเชิงที่นี่ LLVM ไม่รองรับสไลซ์ และด้วยเหตุนี้ คอมไพเลอร์ TinyGo ที่สร้างโค้ดระดับกลางนี้จึงแบ่งคำอธิบายของโครงสร้างข้อมูลออกเป็นส่วนต่างๆ เพื่อเป็นการปรับให้เหมาะสม มันสามารถแสดงถึงองค์ประกอบสามชิ้น (ptr, len и cap) เป็นโครงสร้าง (struct) แต่การแสดงเป็นเอนทิตีที่แยกจากกันสามรายการทำให้สามารถเพิ่มประสิทธิภาพบางอย่างได้ คอมไพเลอร์อื่นๆ อาจเป็นตัวแทนของสไลซ์ด้วยวิธีอื่น ขึ้นอยู่กับรูปแบบการเรียกฟังก์ชันของแพลตฟอร์มเป้าหมาย

คุณสมบัติที่น่าสนใจอีกอย่างของโค้ดนี้คือการใช้คำสั่ง getelementptr (มักเรียกสั้นว่า GEP)

คำสั่งนี้ทำงานร่วมกับพอยน์เตอร์และใช้เพื่อรับพอยน์เตอร์ไปยังองค์ประกอบสไลซ์ ตัวอย่างเช่น ลองเปรียบเทียบกับโค้ดต่อไปนี้ที่เขียนด้วยภาษา C:

int* sliceptr(int *ptr, int index) {
    return &ptr[index];
}

หรือเทียบเท่ากับสิ่งนี้:

int* sliceptr(int *ptr, int index) {
    return ptr + index;
}

สิ่งที่สำคัญที่สุดที่นี่คือคำแนะนำ getelementptr ไม่ดำเนินการลดการอ้างอิง มันแค่คำนวณพอยน์เตอร์ใหม่ตามอันที่มีอยู่ สามารถใช้เป็นคำแนะนำได้ mul и add ในระดับฮาร์ดแวร์ คุณสามารถอ่านเพิ่มเติมเกี่ยวกับคำแนะนำของ GEP ที่นี่.

คุณสมบัติที่น่าสนใจอีกประการหนึ่งของโค้ดระดับกลางนี้คือการใช้คำสั่ง icmp. นี่เป็นคำสั่งวัตถุประสงค์ทั่วไปที่ใช้ในการเปรียบเทียบจำนวนเต็ม ผลลัพธ์ของคำสั่งนี้จะเป็นค่าประเภทเสมอ i1 — ค่าตรรกะ ในกรณีนี้ จะมีการเปรียบเทียบโดยใช้คำสำคัญ slt (ลงนามน้อยกว่า) เนื่องจากเรากำลังเปรียบเทียบตัวเลขสองตัวที่ก่อนหน้านี้แสดงตามประเภท int. หากเราเปรียบเทียบจำนวนเต็มสองตัวที่ไม่ได้ลงนาม เราจะใช้ icmpและคีย์เวิร์ดที่ใช้ในการเปรียบเทียบจะเป็น ult. ในการเปรียบเทียบจำนวนจุดลอยตัว จะใช้คำสั่งอื่น fcmpซึ่งทำงานในลักษณะเดียวกัน

ผลของการ

ฉันเชื่อว่าในเอกสารนี้ ฉันได้กล่าวถึงคุณลักษณะที่สำคัญที่สุดของ LLVM IR แล้ว แน่นอนว่ายังมีอะไรอีกมากมายที่นี่ โดยเฉพาะอย่างยิ่ง การแสดงโค้ดระดับกลางอาจมีคำอธิบายประกอบจำนวนมากที่อนุญาตให้ส่งผ่านการปรับให้เหมาะสมโดยคำนึงถึงคุณลักษณะบางอย่างของโค้ดที่คอมไพเลอร์รู้จักซึ่งไม่สามารถแสดงใน IR ได้ ตัวอย่างเช่น นี่คือธง inbounds คำแนะนำ GEP หรือแฟล็ก nsw и nuwซึ่งสามารถเพิ่มลงในคำแนะนำได้ add. เช่นเดียวกับคำหลัก privateระบุให้เครื่องมือเพิ่มประสิทธิภาพทราบว่าฟังก์ชันที่ทำเครื่องหมายไว้จะไม่ถูกอ้างอิงจากภายนอกหน่วยการคอมไพล์ปัจจุบัน สิ่งนี้ทำให้สามารถเพิ่มประสิทธิภาพระหว่างโพรซีเดอร์ที่น่าสนใจได้มากมาย เช่น การกำจัดข้อโต้แย้งที่ไม่ได้ใช้

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

เรียนผู้อ่าน! คุณใช้ LLVM หรือไม่?

ที่มา: will.com