/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LoopTraversal.cpp
Line | Count | Source |
1 | | //===- LoopTraversal.cpp - Optimal basic block traversal order --*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | |
9 | | #include "llvm/CodeGen/LoopTraversal.h" |
10 | | #include "llvm/ADT/PostOrderIterator.h" |
11 | | #include "llvm/CodeGen/MachineFunction.h" |
12 | | |
13 | | using namespace llvm; |
14 | | |
15 | 4.43M | bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) { |
16 | 4.43M | unsigned MBBNumber = MBB->getNumber(); |
17 | 4.43M | assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number."); |
18 | 4.43M | return MBBInfos[MBBNumber].PrimaryCompleted && |
19 | 4.43M | MBBInfos[MBBNumber].IncomingCompleted == |
20 | 2.42M | MBBInfos[MBBNumber].PrimaryIncoming && |
21 | 4.43M | MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size()2.10M ; |
22 | 4.43M | } |
23 | | |
24 | 288k | LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) { |
25 | 288k | // Initialize the MMBInfos |
26 | 288k | MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo()); |
27 | 288k | |
28 | 288k | MachineBasicBlock *Entry = &*MF.begin(); |
29 | 288k | ReversePostOrderTraversal<MachineBasicBlock *> RPOT(Entry); |
30 | 288k | SmallVector<MachineBasicBlock *, 4> Workqueue; |
31 | 288k | SmallVector<TraversedMBBInfo, 4> MBBTraversalOrder; |
32 | 936k | for (MachineBasicBlock *MBB : RPOT) { |
33 | 936k | // N.B: IncomingProcessed and IncomingCompleted were already updated while |
34 | 936k | // processing this block's predecessors. |
35 | 936k | unsigned MBBNumber = MBB->getNumber(); |
36 | 936k | assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number."); |
37 | 936k | MBBInfos[MBBNumber].PrimaryCompleted = true; |
38 | 936k | MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed; |
39 | 936k | bool Primary = true; |
40 | 936k | Workqueue.push_back(MBB); |
41 | 2.00M | while (!Workqueue.empty()) { |
42 | 1.06M | MachineBasicBlock *ActiveMBB = &*Workqueue.back(); |
43 | 1.06M | Workqueue.pop_back(); |
44 | 1.06M | bool Done = isBlockDone(ActiveMBB); |
45 | 1.06M | MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done)); |
46 | 1.23M | for (MachineBasicBlock *Succ : ActiveMBB->successors()) { |
47 | 1.23M | unsigned SuccNumber = Succ->getNumber(); |
48 | 1.23M | assert(SuccNumber < MBBInfos.size() && |
49 | 1.23M | "Unexpected basic block number."); |
50 | 1.23M | if (!isBlockDone(Succ)) { |
51 | 1.19M | if (Primary) |
52 | 1.00M | MBBInfos[SuccNumber].IncomingProcessed++; |
53 | 1.19M | if (Done) |
54 | 968k | MBBInfos[SuccNumber].IncomingCompleted++; |
55 | 1.19M | if (isBlockDone(Succ)) |
56 | 131k | Workqueue.push_back(Succ); |
57 | 1.19M | } |
58 | 1.23M | } |
59 | 1.06M | Primary = false; |
60 | 1.06M | } |
61 | 936k | } |
62 | 288k | |
63 | 288k | // We need to go through again and finalize any blocks that are not done yet. |
64 | 288k | // This is possible if blocks have dead predecessors, so we didn't visit them |
65 | 288k | // above. |
66 | 936k | for (MachineBasicBlock *MBB : RPOT) { |
67 | 936k | if (!isBlockDone(MBB)) |
68 | 2 | MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true)); |
69 | 936k | // Don't update successors here. We'll get to them anyway through this |
70 | 936k | // loop. |
71 | 936k | } |
72 | 288k | |
73 | 288k | MBBInfos.clear(); |
74 | 288k | |
75 | 288k | return MBBTraversalOrder; |
76 | 288k | } |