LLVM  14.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 
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.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 }
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallVector< TraversedMBBInfo, 4 >
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:753
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:328
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:808
LoopTraversal.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1056
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::LoopTraversal::traverse
TraversalOrder traverse(MachineFunction &MF)
Definition: LoopTraversal.cpp:24
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::SmallVectorImpl::assign
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:669
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
PostOrderIterator.h
MachineFunction.h
llvm::LoopTraversal::TraversedMBBInfo
Definition: LoopTraversal.h:87