LLVM 20.0.0git
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
13using namespace llvm;
14
15bool 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.pop_back_val();
43 bool Done = isBlockDone(ActiveMBB);
44 MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
45 for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
46 unsigned SuccNumber = Succ->getNumber();
47 assert(SuccNumber < MBBInfos.size() &&
48 "Unexpected basic block number.");
49 if (!isBlockDone(Succ)) {
50 if (Primary)
51 MBBInfos[SuccNumber].IncomingProcessed++;
52 if (Done)
53 MBBInfos[SuccNumber].IncomingCompleted++;
54 if (isBlockDone(Succ))
55 Workqueue.push_back(Succ);
56 }
57 }
58 Primary = false;
59 }
60 }
61
62 // We need to go through again and finalize any blocks that are not done yet.
63 // This is possible if blocks have dead predecessors, so we didn't visit them
64 // above.
65 for (MachineBasicBlock *MBB : RPOT) {
66 if (!isBlockDone(MBB))
67 MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
68 // Don't update successors here. We'll get to them anyway through this
69 // loop.
70 }
71
72 MBBInfos.clear();
73
74 return MBBTraversalOrder;
75}
MachineBasicBlock & MBB
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
TraversalOrder traverse(MachineFunction &MF)
unsigned pred_size() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator_range< succ_iterator > successors()
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:717
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Done
Definition: Threading.h:61