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

วิธีง่ายๆ ในการวิเคราะห์การไหลของข้อมูลในโปรแกรม คือ การตั้งสมการการไหลของข้อมูลสำหรับแต่ละโหนดในกราฟการไหลของการควบคุม และแก้สมการเหล่านั้นโดยการคำนวณเอาต์พุตจากอินพุตซ้ำๆ ที่แต่ละโหนด จนกว่าระบบทั้งหมดจะเสถียร กล่าวคือ ถึงจุด คงที่ ประสิทธิภาพและความแม่นยำของกระบวนการนี้ได้รับอิทธิพลอย่างมากจากการออกแบบกรอบการไหลของข้อมูล รวมถึงทิศทางการวิเคราะห์ (ไปข้างหน้าหรือย้อนกลับ) ขอบเขตของค่า และการดำเนินการเชื่อมต่อที่ใช้ในการรวมข้อมูลจากเส้นทางการควบคุมหลายเส้นทางแนวทางทั่วไปนี้ หรือที่รู้จักกันในชื่อวิธีของ Kildallได้รับการพัฒนาโดยGary Kildallในขณะที่สอนอยู่ที่Naval Postgraduate School ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]}

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

สำหรับแต่ละบล็อก b:

${\displaystyle out_{b}=trans_{b}(in_{b})}$

${\displaystyle in_{b}=join_{p\in pred_{b}}(out_{p})}$

ในส่วนนี้คือฟังก์ชันถ่ายโอนของบล็อกมันทำงานกับสถานะเริ่มต้นโดยให้ผลลัพธ์เป็นสถานะสิ้นสุดการดำเนินการรวมจะรวมสถานะสิ้นสุดของตัวก่อนหน้าของ เข้าด้วยกันโดยให้ผลลัพธ์เป็นสถานะเริ่มต้นของ ${\displaystyle trans_{b}}$${\displaystyle b}$${\displaystyle in_{b}}$${\displaystyle out_{b}}$${\displaystyle join}$${\displaystyle p\in pred_{b}}$${\displaystyle b}$${\displaystyle b}$

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

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

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

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

อัลกอริทึมพื้นฐานสำหรับการแก้สมการการไหลของข้อมูลคืออัลกอริทึมแบบวนซ้ำแบบรอบโรบิน :

สำหรับi ← 1 ถึงN

เริ่มต้นโหนด i

ในขณะที่ ( ชุดข้อมูลยังคงเปลี่ยนแปลงอยู่ )

สำหรับi ← 1 ถึงN

คำนวณชุดใหม่ที่โหนด i

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

โดเมนค่าควรเป็นลำดับบางส่วนที่มีความสูงจำกัด (กล่าวคือ ไม่มีสายโซ่ที่เพิ่มขึ้นอย่างไม่มีที่สิ้นสุด< < ...) การรวมกันของฟังก์ชันถ่ายโอนและการดำเนินการเชื่อมต่อควรเป็นแบบโมโนโทนิกเมื่อเทียบกับลำดับบางส่วนนี้ ความเป็นโมโนโทนิกทำให้มั่นใจได้ว่าในแต่ละรอบการทำซ้ำ ค่าจะคงที่หรือเพิ่มขึ้น ในขณะที่ความสูงที่จำกัดทำให้มั่นใจได้ว่าค่าจะไม่เพิ่มขึ้นอย่างไม่มีที่สิ้นสุด ดังนั้นในที่สุดเราจะไปถึงสถานการณ์ที่ T(x) = x สำหรับทุก x ซึ่งเป็นจุดตรึง ${\displaystyle x_{1}}$${\displaystyle x_{2}}$

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

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

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

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

• ลำดับแบบสุ่ม - ลำดับการวนซ้ำนี้ไม่คำนึงว่าสมการการไหลของข้อมูลแก้ปัญหาการไหลของข้อมูลไปข้างหน้าหรือย้อนกลับ ดังนั้นประสิทธิภาพจึงค่อนข้างต่ำเมื่อเทียบกับลำดับการวนซ้ำแบบเฉพาะเจาะจง
• ลำดับหลัง (Postorder) - นี่คือลำดับการวนซ้ำทั่วไปสำหรับปัญหาการไหลของข้อมูลย้อนกลับ ในการวนซ้ำแบบลำดับหลังโหนดจะถูกเยี่ยมชมหลังจากที่โหนดถัดไปทั้งหมดได้รับการเยี่ยมชมแล้ว โดยทั่วไปการวนซ้ำแบบลำดับหลังจะถูกนำไปใช้กับกลยุทธ์การค้นหาเชิงลึก (Deep-first )
• ลำดับ การวนซ้ำแบบย้อนกลับ (Reverse postorder ) - นี่คือลำดับการวนซ้ำทั่วไปสำหรับปัญหาการไหลของข้อมูลไปข้างหน้า ในการวนซ้ำแบบย้อนกลับนี้โหนดจะถูกเยี่ยมชมก่อนโหนดถัดไปใดๆ ยกเว้นในกรณีที่โหนดถัดไปนั้นเข้าถึงได้ด้วยขอบย้อนกลับ (โปรดทราบว่า ลำดับการวนซ้ำแบบย้อนกลับไม่เหมือนกับ ลำดับก่อนหน้า (Preorder ))

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

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

การ วิเคราะห์ คำจำกัดความที่เข้าถึงได้จะคำนวณชุดคำจำกัดความที่อาจเข้าถึงจุดโปรแกรมแต่ละจุดได้ สำหรับแต่ละจุดของโปรแกรม

 ถ้า b == 4 แล้ว  a = 5;  อื่น  a = 3;  จบเงื่อนไข  ถ้า a < 4 แล้ว  ... 

นิยามที่ครอบคลุมของตัวแปรaในบรรทัดที่ 7 คือชุดของการกำหนดค่าa = 5ในบรรทัดที่ 2 และa = 3บรรทัดที่ 4

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

สถานะเริ่มต้น (in-state) ของบล็อก คือ เซตของตัวแปรที่ยังใช้งานได้ ณ จุดเริ่มต้นของบล็อกนั้น โดยในขั้นต้นจะประกอบด้วยตัวแปรทั้งหมดที่ใช้งานได้ (บรรจุอยู่) ในบล็อก ก่อนที่จะมีการใช้ฟังก์ชันถ่ายโอน (transfer function) และคำนวณค่าจริงของตัวแปรเหล่านั้น ฟังก์ชันถ่ายโอนของคำสั่งจะถูกใช้โดยการลบตัวแปรที่เขียนไว้ในบล็อกนั้นออกจากเซตของตัวแปรที่ยังใช้งานได้ สถานะสิ้นสุด (out-state) ของบล็อก คือ เซตของตัวแปรที่ยังใช้งานได้ ณ จุดสิ้นสุดของบล็อก ซึ่งคำนวณได้จากการรวมกันของสถานะเริ่มต้นของบล็อกถัดไป

รหัสเริ่มต้น:

b1: a = 3; b = 5; d = 4; x = 100; ถ้า a > b แล้ว b2: c = a + b; d = 2; b3: endif c = 4; ส่งคืนค่า b * d + c; 

การวิเคราะห์ย้อนกลับ:

// ใน: {} b1: a = 3; b = 5; d = 4; x = 100; // x จะไม่ถูกนำไปใช้ในภายหลัง ดังนั้นจึงไม่ได้อยู่ในเซตเอาต์พุต {a,b,d} ถ้า a > b แล้ว // ผลลัพธ์: {a,b,d} // การรวมกันของตัวสืบทอด (ขาเข้า) ทั้งหมดของ b1 => b2: {a,b} และ b3: {b,d} // ใน: {a,b} b2: c = a + b; d = 2; // ผลลัพธ์: {b,d} // ใน: {b,d} b3: endif c = 4; ส่งคืนค่า b * d + c; // ออก:{} 

สถานะขาเข้าของ b3 ประกอบด้วยbและd เท่านั้น เนื่องจากcได้ถูกเขียนลงไปแล้ว สถานะขาออกของ b1 คือการรวมกันของสถานะขาเข้าของ b2 และ b3 นิยามของcใน b2 สามารถลบออกได้ เนื่องจากcไม่ได้มีชีวิตอยู่ทันทีหลังจากคำสั่งนั้น

การแก้สมการการไหลของข้อมูลเริ่มต้นด้วยการกำหนดค่าเริ่มต้นให้กับสถานะขาเข้าและสถานะขาออกทั้งหมดให้เป็นเซตว่าง รายการงานจะถูกเริ่มต้นโดยการแทรกจุดออก (b3) ลงในรายการงาน (ซึ่งเป็นลักษณะทั่วไปของการไหลย้อนกลับ) สถานะขาเข้าที่คำนวณได้จะแตกต่างจากสถานะก่อนหน้า ดังนั้นจึงมีการแทรกสถานะก่อนหน้า b1 และ b2 เข้าไป และกระบวนการจะดำเนินต่อไป ความคืบหน้าจะสรุปไว้ในตารางด้านล่าง

โปรดสังเกตว่า b1 ถูกป้อนในรายการก่อน b2 ซึ่งทำให้ต้องประมวลผล b1 สองครั้ง (b1 ถูกป้อนซ้ำในฐานะตัวก่อนหน้าของ b2) การแทรก b2 ก่อน b1 จะช่วยให้การดำเนินการเสร็จสิ้นเร็วกว่า

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

คอมไพเลอร์สมัยใหม่หลายตัวใช้รูปแบบการกำหนดค่าเดี่ยวแบบคงที่เป็นวิธีการวิเคราะห์การพึ่งพาตัวแปร^{[ 10 ]}

ในปี พ.ศ. 2545 Markus Mohnen ได้อธิบายวิธีการวิเคราะห์การไหลของข้อมูลแบบใหม่ที่ไม่จำเป็นต้องสร้างกราฟการไหลของข้อมูลอย่างชัดเจน^{[ 11 ]}แต่ใช้การตีความเชิงนามธรรมของโปรแกรมและเก็บชุดตัวนับโปรแกรมที่ใช้งานอยู่ ในแต่ละสาขาเงื่อนไข เป้าหมายทั้งสองจะถูกเพิ่มเข้าไปในชุดที่ใช้งานอยู่ แต่ละเส้นทางจะถูกติดตามเป็นจำนวนคำสั่งมากที่สุดเท่าที่จะเป็นไปได้ (จนกว่าจะสิ้นสุดโปรแกรมหรือจนกว่าจะวนซ้ำโดยไม่มีการเปลี่ยนแปลง) จากนั้นจะถูกลบออกจากชุดและดึงตัวนับโปรแกรมถัดไป

การผสมผสานระหว่างการวิเคราะห์การไหลของการควบคุม และการวิเคราะห์การไหลของข้อมูลได้รับ การพิสูจน์แล้วว่ามีประโยชน์และเสริมกันในการระบุพื้นที่รหัสต้นฉบับที่สอดคล้องกันซึ่งดำเนินการฟังก์ชันการทำงานของระบบ (เช่นคุณสมบัติข้อกำหนดหรือกรณีการใช้งาน ) ^{[ 12 ]}

มีปัญหาการไหลของข้อมูลเฉพาะประเภทต่างๆ ที่มีวิธีแก้ปัญหาที่มีประสิทธิภาพหรือเป็นแบบทั่วไป

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

ยกตัวอย่างเช่น ในการวิเคราะห์ตัวแปรแบบเรียลไทม์ การดำเนินการเชื่อมต่อ (join) คือการรวม (union) ชุดตัวแปรที่ถูกเขียนลงในบล็อกเรียกว่าkill set ในขณะที่ชุดตัวแปรที่ถูกอ่านโดยไม่ต้องเขียนลงไปก่อนเรียกว่า gen set สมการการไหลของข้อมูลจึงเป็นดังนี้

${\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}$

${\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}$

ในทางตรรกศาสตร์ สามารถอ่านได้ดังนี้

out( b ) = 0 สำหรับs ใน succ( b ) out( b ) = out( b ) หรือ in( s ) in( b ) = (out( b ) and not kill( b )) or gen( b ) 

ปัญหาการไหลของข้อมูลที่มีชุดค่าการไหลของข้อมูลที่สามารถแสดงเป็นเวกเตอร์บิตเรียกว่าปัญหาเวกเตอร์บิตปัญหาgen-killหรือปัญหาที่แยกได้ในระดับท้องถิ่น [ ^{13 ] ปัญหา}ดังกล่าวมีวิธีแก้ปัญหาแบบพหุนามทั่วไป^{[ 14 ]}

นอกเหนือจากปัญหาการเข้าถึงคำจำกัดความและตัวแปรที่มีชีวิตที่กล่าวถึงข้างต้นแล้ว ปัญหาต่อไปนี้เป็นตัวอย่างของปัญหาเวกเตอร์บิต: ^{[ 14 ]}

• นิพจน์ที่มีให้เลือก
• การแสดงออกที่ยุ่งมาก
• ห่วงโซ่การกำหนดการใช้งาน

ปัญหา Interprocedural, finite, distributive, subsetหรือ ปัญหา IFDSเป็นปัญหาอีกประเภทหนึ่งที่มีวิธีแก้ปัญหาแบบพหุนามทั่วไป^{[ 13 ] [ 15 ]}วิธีแก้ปัญหาเหล่านี้ให้การวิเคราะห์การไหลของข้อมูลที่ไวต่อบริบทและไวต่อการไหล

มีการนำการวิเคราะห์การไหลของข้อมูลตาม IFDS มาใช้หลายแบบสำหรับภาษาโปรแกรมยอดนิยม เช่น ในเฟรมเวิร์ก Soot ^{[ 16 ]}และ WALA ^{[ 17 ]}สำหรับการวิเคราะห์ Java

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

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

• การ วิเคราะห์ ที่คำนึงถึงลำดับของคำสั่งในโปรแกรมจะพิจารณาตามลำดับของคำสั่งเหล่านั้น ตัวอย่างเช่น การวิเคราะห์นามแฝงของตัวชี้ที่ไม่คำนึงถึงลำดับของคำสั่งอาจสรุปได้ว่า "ตัวแปรxและyอาจอ้างอิงถึงตำแหน่งเดียวกัน" ในขณะที่การวิเคราะห์ที่คำนึงถึงลำดับของคำสั่งอาจสรุปได้ว่า "หลังจากคำสั่งที่ 20 ตัวแปรxและyอาจอ้างอิงถึงตำแหน่งเดียวกัน"
• การ วิเคราะห์ ที่คำนึงถึงเส้นทางจะคำนวณข้อมูลการวิเคราะห์ที่แตกต่างกันไปขึ้นอยู่กับเงื่อนไขในคำสั่งแยกสาขาแบบมีเงื่อนไข ตัวอย่างเช่น หากสาขาหนึ่งมีเงื่อนไขx>0แล้วใน เส้นทาง ที่ข้ามไปการวิเคราะห์จะถือว่าx<=0และในเป้าหมายของสาขา การวิเคราะห์จะถือว่า เป็นx>0จริง
• การ วิเคราะห์ ที่คำนึงถึงบริบทคือ การวิเคราะห์ ระหว่างกระบวนการที่พิจารณาบริบทการเรียกใช้เมื่อวิเคราะห์เป้าหมายของการเรียกใช้ฟังก์ชัน โดยเฉพาะอย่างยิ่ง การใช้ข้อมูลบริบทจะช่วยให้สามารถย้อนกลับไปยังตำแหน่งการเรียกใช้ดั้งเดิมได้ ในขณะที่หากไม่มีข้อมูลดังกล่าว ข้อมูลการวิเคราะห์จะต้องถูกส่งต่อไปยังตำแหน่งการเรียกใช้ที่เป็นไปได้ทั้งหมด ซึ่งอาจทำให้สูญเสียความแม่นยำได้

• การเข้าถึงคำจำกัดความ
• การวิเคราะห์ความมีชีวิตชีวา
• การวิเคราะห์การมอบหมายที่แน่นอน
• การแสดงออกที่มีอยู่
• การแพร่กระจายอย่างต่อเนื่อง

• การตีความเชิงนามธรรม
• การวิเคราะห์การไหลของควบคุม
• เอ็กซ์แอลที86

• คูเปอร์, คีธ ดี. ; ทอร์ซอน, ลินดา (2003) [2002-01-01]. วิศวกรรมคอมไพเลอร์ . มอร์แกน คอฟแมนน์ . ISBN 978-1-55860-698-2.
• Muchnick, Steven Stanley (1997). การออกแบบและการใช้งานคอมไพเลอร์ขั้นสูง . สำนักพิมพ์ Morgan Kaufmann . ISBN 978-1-55860-320-2.
• เฮชต์, แมทธิว เอส. (3 พฤษภาคม 1977). การวิเคราะห์การไหลของโปรแกรมคอมพิวเตอร์ . ชุดภาษาโปรแกรม. เล่มที่ 5. เอลเซเวียร์ นอร์ท-ฮอลแลนด์ อิงค์. ISBN 978-0-44400210-5.
• Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). การวิเคราะห์การไหลของข้อมูล: ทฤษฎีและการปฏิบัติ . สำนักพิมพ์ CRC ( Taylor and Francis Group ).
• นีลสัน, เฟลมมิง; นีลสัน, ฮันเน รีส ; แฮงกิน, คริส (2005). หลักการวิเคราะห์โปรแกรม . สปริงเกอร์ ไซเอนซ์+บิสซิเนส มีเดีย .