computePostOrder computes the postorder of depth first search tree (DFST) of the live blocks of the CFG. The backpropagation algorithm converges faster if the CFG blocks are traversed in postorder, compared to the random order (Check [Kam, Ullman 76']).
(blocks []*cfg.Block)
| 874 | // The backpropagation algorithm converges faster if the CFG blocks are traversed in postorder, compared to the random |
| 875 | // order (Check [Kam, Ullman 76']). |
| 876 | func computePostOrder(blocks []*cfg.Block) []int { |
| 877 | numBlocks := len(blocks) |
| 878 | visited := make([]bool, numBlocks) |
| 879 | postOrder := make([]int, 0, numBlocks) |
| 880 | var visit func(curBlock int) |
| 881 | visit = func(curBlock int) { |
| 882 | visited[curBlock] = true |
| 883 | for _, suc := range blocks[curBlock].Succs { |
| 884 | sucIdx := int(suc.Index) |
| 885 | if !visited[sucIdx] { |
| 886 | visit(sucIdx) |
| 887 | } |
| 888 | } |
| 889 | postOrder = append(postOrder, curBlock) |
| 890 | } |
| 891 | |
| 892 | // Start traversal from entry block (index 0): https://pkg.go.dev/golang.org/x/tools/go/cfg#CFG |
| 893 | visit(0) |
| 894 | |
| 895 | return postOrder |
| 896 | } |
| 897 | |
| 898 | // BackpropAcrossFunc is the main driver of the backpropagation, it takes a function declaration |
| 899 | // with accompanying CFG, and back-propagates a tree of assertions across it to generate, at entry |
no outgoing calls
no test coverage detected