Tôi đang cố hiểu chính xác khái niệm về đồ thị phụ thuộc kiểm soát. Giả sử tôi có đồ thị luồng điều khiển sau đây (theo ký hiệu DOT):Biểu đồ phụ thuộc có thể có vòng lặp không?
graph g {
1 -> 2;
2 -> 3;
3 -> 2;
2 -> 4;
1 -> 4
}
Nó có một nút độc đáo nhập cảnh (1) và lần thoát nút duy nhất (4), và một vòng 2 -> 3 -> 2.
Câu hỏi của tôi là: biểu đồ phụ thuộc điều khiển cho CFG này có chứa cạnh vòng lặp từ 2 đến chính nó không?
Allen & "Các trình biên dịch tối ưu hóa cho các kiến trúc hiện đại" của Kennedy có một thuật toán tạo ra một vòng lặp như vậy. Tuy nhiên, thuật toán "Compiler design & implementation" của Muchnick cho sự phụ thuộc kiểm soát không tạo ra một cạnh như vậy. Bên cạnh đó, tôi không thể tìm thấy bất kỳ ví dụ nào trong tài liệu mà CDG được vẽ với cạnh vòng lặp như vậy. Tôi có xu hướng tin rằng không có cạnh như vậy, nhưng theo định nghĩa chính thức của sự phụ thuộc kiểm soát và theo Allen & thuật toán của Kennedy, nó nên!
Nếu bạn có thể vui lòng chỉ cho tôi một ví dụ trong đó có một vòng lặp trong CDG (tốt nhất là trong một bài đánh giá ngang hàng, hoặc một số ghi chú bài giảng của giáo sư, vv), hoặc nếu bạn có thể tranh luận tại sao Allen & nên không chính xác, tôi rất vui được biết.
Tiện ích của biểu đồ phụ thuộc như vậy là xác định cách đặt hàng các hoạt động, đúng không? Theo nghĩa đó, nó không phải là hữu ích để biết rằng một yếu tố phụ thuộc vào chính nó. Bạn có thể vẽ các vòng nếu bạn thích, nhưng điều thực sự quan trọng là tất cả các cạnh khác. – mitchus
Vâng, tôi nghĩ rằng tôi đang mong đợi một số "định nghĩa kinh điển" có thể được sử dụng như một oracle để kiểm tra nhiều triển khai, nhưng đúng là cả hai phiên bản đều tương đương với tất cả các mục đích thực tế ... cảm ơn! – anol
@mitchus Bạn nên chuyển nhận xét của mình thành câu trả lời để câu trả lời có thể được chấp nhận làm câu trả lời. –