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

นี่คือการใช้คำในภาษาพูดที่พบได้บ่อยที่สุด ในอีกความหมายหนึ่งการวิเคราะห์ตัวชี้ (pointer analysis)อาจเป็นชื่อเรียกโดยรวมของการวิเคราะห์จุดไปยัง (points-to analysis)ซึ่งนิยามไว้ข้างต้น และการวิเคราะห์นามแฝง (alias analysis ) การวิเคราะห์จุดไปยังและการวิเคราะห์นามแฝงมีความเกี่ยวข้องกันอย่างใกล้ชิด แต่ไม่ใช่ปัญหาที่เทียบเท่ากันเสมอไป

พิจารณาโปรแกรมภาษา C ต่อไปนี้:

int * id ( int * p ) { return p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); int * v = id ( & y ); }

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

(โดยที่X::Yแทนการจัดสรรสแต็กที่เก็บตัวแปรโลคอลYในฟังก์ชันX)

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

การวิเคราะห์ตัวชี้ที่แม่นยำอย่างสมบูรณ์สามารถแสดงให้เห็นว่าไม่สามารถตัดสินได้เนื่องจาก เป็นการวิเคราะห์แบบคงที่ ^{[ 1 ]}วิธีการส่วนใหญ่มีความถูกต้องแต่มีประสิทธิภาพและความแม่นยำที่แตกต่างกันอย่างมาก การตัดสินใจด้านการออกแบบหลายอย่างส่งผลกระทบต่อทั้งความแม่นยำและประสิทธิภาพของการวิเคราะห์ บ่อยครั้ง (แต่ไม่เสมอไป) ความแม่นยำที่ต่ำกว่าจะให้ประสิทธิภาพที่สูงกว่า ตัวเลือกเหล่านี้ได้แก่: ^{[ 2 ] [ 3 ]}

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

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

อัลกอริทึมของ Steensgaardและอัลกอริทึมของ Andersen เป็นอัลกอริทึมทั่วไปที่ไม่คำนึงถึงบริบทและไม่คำนึงถึงการไหลสำหรับการ วิเคราะห์ ตัวชี้ มักใช้ในคอมไพเลอร์ และมีการใช้งานในSVF ^{[ 5 ]} และLLVM

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

อัลกอริทึมที่ไม่ไวต่อการไหลจำนวนมากได้รับการกำหนดไว้ในDatalogรวมถึงอัลกอริทึมในเฟรมเวิร์กการวิเคราะห์ Soot สำหรับ Java ^{[ 7 ]}

อัลกอริทึมที่คำนึงถึงบริบทและกระแสการไหลจะบรรลุความแม่นยำที่สูงขึ้น โดยทั่วไปแล้วต้องแลกมาด้วยประสิทธิภาพที่ลดลงบ้าง โดยการวิเคราะห์แต่ละขั้นตอนหลายครั้ง ครั้งละหนึ่งบริบท^{[ 8 ]}การวิเคราะห์ส่วนใหญ่ใช้วิธี "สตริงบริบท" โดยที่บริบทประกอบด้วยรายการของรายการ (ตัวเลือกทั่วไปของรายการบริบท ได้แก่ ตำแหน่งการเรียก ตำแหน่งการจัดสรร และประเภท) ^{[ 9 ]}เพื่อให้แน่ใจว่าการสิ้นสุด (และโดยทั่วไปคือความสามารถในการปรับขนาด) การวิเคราะห์ดังกล่าวโดยทั่วไปจะใช้ วิธีการจำกัด kโดยที่บริบทมีขนาดสูงสุดคงที่ และองค์ประกอบที่เพิ่มเข้ามาล่าสุดน้อยที่สุดจะถูกลบออกตามความจำเป็น^{[ 10 ]}รูปแบบทั่วไปสามแบบของการวิเคราะห์ที่คำนึงถึงบริบทและไม่คำนึงถึงกระแสการไหล ได้แก่: ^{[ 11 ]}

• ความไวของจุดเรียก
• ความไวต่อวัตถุ
• ความไวต่อประเภท

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

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

int * id ( int * p ) { return p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); // main.3 int * v = id ( & y ); // main.4 }

สำหรับโปรแกรมนี้ การวิเคราะห์ที่ไม่คำนึงถึงบริบทจะสรุปได้ (อย่างถูกต้องแต่ไม่แม่นยำ) ว่าpสามารถชี้ไปยังการจัดสรรที่ถือxหรือการจัดสรรที่ถือy ได้ ดังนั้นuและvอาจเป็นชื่อเดียวกัน และทั้งคู่สามารถชี้ไปยังการจัดสรรใดก็ได้:

การวิเคราะห์ที่คำนึงถึงไซต์การเรียกจะวิเคราะห์idสองครั้ง ครั้งหนึ่งสำหรับmain.3และอีกครั้งสำหรับmain.4และข้อเท็จจริงที่ชี้ไปยังpจะถูกจำกัดโดยไซต์การเรียก ทำให้การวิเคราะห์สามารถสรุปได้ว่า เมื่อส่งคืนค่าหลักuสามารถชี้ไปยังการจัดสรรที่ถือx เท่านั้น และvสามารถชี้ไปยังการจัดสรรที่ถือyเท่านั้น

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

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

• Zyrianov, Vlas; Newman, Christian D.; Guarnera, Drew T.; Collard, Michael L.; Maletic, Jonathan I. (2019). "srcPtr: กรอบงานสำหรับการนำวิธีการวิเคราะห์ตัวชี้แบบคงที่ไปใช้" (PDF) . ICPC '19: รายงานการประชุมวิชาการนานาชาติ IEEE ครั้งที่ 27 ว่าด้วยความเข้าใจโปรแกรม . มอนทรีออล ประเทศแคนาดา: IEEE.
• Smaragdakis, Yannis; Balatsouras, George (2015). "การวิเคราะห์พอยน์เตอร์" (PDF) . พื้นฐานและแนวโน้มในภาษาโปรแกรม . 2 (1): 1– 69. doi : 10.1561/2500000014 . S2CID  207179267 . สืบค้นเมื่อ30 พฤษภาคม 2019 .
• Li, Yue; Tan/, Tian; Møller, Anders; Smaragdakis, Yannis (18 พฤษภาคม 2020). "แนวทางที่มีหลักการสำหรับความไวต่อบริบทแบบเลือกสรรสำหรับการวิเคราะห์ตัวชี้" . ACM Transactions on Programming Languages ​​and Systems . 42 (2): 10:1–10:40. doi : 10.1145/3381915 . ISSN  0164-0925 . S2CID  214812357 .
• Michael Hind (2001). "การวิเคราะห์ตัวชี้: เรายังแก้ปัญหานี้ไม่ได้หรือ?" (PDF) . PASTE '01: รายงานการประชุมเชิงปฏิบัติการ ACM SIGPLAN-SIGSOFT ปี 2001 ว่าด้วยการวิเคราะห์โปรแกรมสำหรับเครื่องมือและวิศวกรรมซอฟต์แวร์ . ACM. หน้า  54– 61. ISBN 1-58113-413-4.
• Steensgaard, Bjarne (1996). "การวิเคราะห์จุดในเวลาเกือบเชิงเส้น" (PDF) . POPL '96: รายงานการประชุมสัมมนา ACM SIGPLAN-SIGACT ครั้งที่ 23 ว่าด้วยหลักการของภาษาโปรแกรม . นิวยอร์ก, นิวยอร์ก, สหรัฐอเมริกา: ACM. หน้า  32–41 . doi : 10.1145/237721.237727 . ISBN 0-89791-769-3.
• Andersen, Lars Ole (1994). การวิเคราะห์โปรแกรมและการปรับแต่งเฉพาะสำหรับภาษาการเขียนโปรแกรม C (PDF) (วิทยานิพนธ์ปริญญาเอก)