LLVM  10.0.0svn
LoopTraversal.cpp
Go to the documentation of this file.
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 
12 
13 using namespace llvm;
14 
15 bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
16  unsigned MBBNumber = MBB->getNumber();
17  assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
18  return MBBInfos[MBBNumber].PrimaryCompleted &&
19  MBBInfos[MBBNumber].IncomingCompleted ==
20  MBBInfos[MBBNumber].PrimaryIncoming &&
21  MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size();
22 }
23 
25  // Initialize the MMBInfos
26  MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo());
27 
28  MachineBasicBlock *Entry = &*MF.begin();
31  SmallVector<TraversedMBBInfo, 4> MBBTraversalOrder;
32  for (MachineBasicBlock *MBB : RPOT) {
33  // N.B: IncomingProcessed and IncomingCompleted were already updated while
34  // processing this block's predecessors.
35  unsigned MBBNumber = MBB->getNumber();
36  assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
37  MBBInfos[MBBNumber].PrimaryCompleted = true;
38  MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed;
39  bool Primary = true;
40  Workqueue.push_back(MBB);
41  while (!Workqueue.empty()) {
42  MachineBasicBlock *ActiveMBB = &*Workqueue.back();
43  Workqueue.pop_back();
44  bool Done = isBlockDone(ActiveMBB);
45  MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
46  for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
47  unsigned SuccNumber = Succ->getNumber();
48  assert(SuccNumber < MBBInfos.size() &&
49  "Unexpected basic block number.");
50  if (!isBlockDone(Succ)) {
51  if (Primary)
52  MBBInfos[SuccNumber].IncomingProcessed++;
53  if (Done)
54  MBBInfos[SuccNumber].IncomingCompleted++;
55  if (isBlockDone(Succ))
56  Workqueue.push_back(Succ);
57  }
58  }
59  Primary = false;
60  }
61  }
62 
63  // We need to go through again and finalize any blocks that are not done yet.
64  // This is possible if blocks have dead predecessors, so we didn't visit them
65  // above.
66  for (MachineBasicBlock *MBB : RPOT) {
67  if (!isBlockDone(MBB))
68  MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
69  // Don't update successors here. We'll get to them anyway through this
70  // loop.
71  }
72 
73  MBBInfos.clear();
74 
75  return MBBTraversalOrder;
76 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
iterator_range< succ_iterator > successors()
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:412
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
size_t size() const
Definition: SmallVector.h:52
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
unsigned pred_size() const
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
TraversalOrder traverse(MachineFunction &MF)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())