Suy luận chương trình con

Question

Có giấy nào mô tả bất kỳ thuật toán/kỹ thuật nào để suy ra các chương trình con từ một chương trình đã biên dịch không? Nói cách khác: có một thuật toán để tìm các khối mã xuất hiện nhiều lần trong chương trình không? Những khối này có thể có các hướng dẫn sắp xếp lại (không có thay đổi hành vi chương trình), dĩ nhiên là có nhiều khả năng tìm thấy kết quả phù hợp hơn.

Quá trình này có thể được xem là đối diện của nội tuyến chương trình con được thực hiện bởi trình biên dịch để tránh các cuộc gọi, nhưng tăng kích thước nhị phân.

Dường như với tôi rằng đây là một vấn đề lý thuyết rất khó.

Answer 1

Vâng, đó là một vấn đề thú vị. Mọi người đã thực sự làm việc về điều này. Một tìm kiếm nhanh chóng trả về hai:

• Keith D. Cooper, Nathaniel McIntosh: Enhanced Code Compression for Embedded RISC Processors, PLDI 1999.

• Christopher W. Fraser, Eugene W. Myers, Alan L. Wendt: Analyzing and Compressing Assembly Code, SIGPLAN Thông báo, tháng 6 năm 1984.

Nhưng có thể còn nhiều hơn thế nữa. Bạn có thể sử dụng Google Scholar để tìm thêm các giấy tờ gần đây có tham khảo những tài liệu cũ.

Answer 2

Điều bạn đang tìm kiếm được gọi là "trình phát hiện nhân bản". Bạn có thể làm điều này trên mã nguồn hoặc mã đối tượng. Ý tưởng chính là quyết định những điểm biến đổi nào bạn muốn chấp nhận.

Bạn có thể read about our CloneDR máy phát hiện nhân bản, tìm mã trùng lặp bằng cách so sánh các cây cú pháp của tệp nguồn, tìm các kết quả khớp chính xác và gần thiếu. Nó thực hiện trên nhiều tệp thay vì chỉ trong một tệp nguồn. Đây là loại như phát hiện "subexpression phổ biến", nhưng nó hoạt động trên các tờ khai cũng như mã thực thi. Khi đối sánh không chính xác, nó có thể xác định tham số cho "chương trình con" (trừu tượng).

Xem bài viết của tôi trên Clone Detection Using Abstract Syntax trees để biết mô tả thuật toán.

CloneDR thực hiện điều này cho nhiều ngôn ngữ, sử dụng language-precise front end parsers.

Trang web mô tả cách CloneDR hoạt động và so sánh CloneDR với một số công cụ phát hiện bản sao khác.

CloneDR không xử lý "sắp xếp lại hướng dẫn". Các phương pháp có khả năng mở rộng ít hơn tìm thấy các bản sao bằng cách so sánh các PDG có thể làm điều này. Những thứ này khá gần với việc so sánh các biểu đồ lưu lượng dữ liệu, điều này có thể tốt cho việc tìm kiếm các mã lệnh lệnh máy.

Answer 3

Có thể đây là câm .. nhưng xem xét "khác biệt". Về cơ bản nó có phiên bản giới hạn này.