LLVM  14.0.0git
EdgeBundles.cpp
Go to the documentation of this file.
1 //===-------- EdgeBundles.cpp - Bundles of CFG edges ----------------------===//
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 // This file provides the implementation of the EdgeBundles analysis.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/Twine.h"
17 #include "llvm/CodeGen/Passes.h"
18 #include "llvm/InitializePasses.h"
22 
23 using namespace llvm;
24 
25 static cl::opt<bool>
26 ViewEdgeBundles("view-edge-bundles", cl::Hidden,
27  cl::desc("Pop up a window to show edge bundle graphs"));
28 
29 char EdgeBundles::ID = 0;
30 
31 INITIALIZE_PASS(EdgeBundles, "edge-bundles", "Bundle Machine CFG Edges",
32  /* cfg = */true, /* is_analysis = */ true)
33 
35 
36 void EdgeBundles::getAnalysisUsage(AnalysisUsage &AU) const {
37  AU.setPreservesAll();
39 }
40 
41 bool EdgeBundles::runOnMachineFunction(MachineFunction &mf) {
42  MF = &mf;
43  EC.clear();
44  EC.grow(2 * MF->getNumBlockIDs());
45 
46  for (const auto &MBB : *MF) {
47  unsigned OutE = 2 * MBB.getNumber() + 1;
48  // Join the outgoing bundle with the ingoing bundles of all successors.
49  for (const MachineBasicBlock *Succ : MBB.successors())
50  EC.join(OutE, 2 * Succ->getNumber());
51  }
52  EC.compress();
53  if (ViewEdgeBundles)
54  view();
55 
56  // Compute the reverse mapping.
57  Blocks.clear();
58  Blocks.resize(getNumBundles());
59 
60  for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) {
61  unsigned b0 = getBundle(i, false);
62  unsigned b1 = getBundle(i, true);
63  Blocks[b0].push_back(i);
64  if (b1 != b0)
65  Blocks[b1].push_back(i);
66  }
67 
68  return false;
69 }
70 
71 namespace llvm {
72 
73 /// Specialize WriteGraph, the standard implementation won't work.
74 template<>
75 raw_ostream &WriteGraph<>(raw_ostream &O, const EdgeBundles &G,
76  bool ShortNames,
77  const Twine &Title) {
78  const MachineFunction *MF = G.getMachineFunction();
79 
80  O << "digraph {\n";
81  for (const auto &MBB : *MF) {
82  unsigned BB = MBB.getNumber();
83  O << "\t\"" << printMBBReference(MBB) << "\" [ shape=box ]\n"
84  << '\t' << G.getBundle(BB, false) << " -> \"" << printMBBReference(MBB)
85  << "\"\n"
86  << "\t\"" << printMBBReference(MBB) << "\" -> " << G.getBundle(BB, true)
87  << '\n';
88  for (const MachineBasicBlock *Succ : MBB.successors())
89  O << "\t\"" << printMBBReference(MBB) << "\" -> \""
90  << printMBBReference(*Succ) << "\" [ color=lightgray ]\n";
91  }
92  O << "}\n";
93  return O;
94 }
95 
96 } // end namespace llvm
97 
98 /// view - Visualize the annotated bipartite CFG with Graphviz.
99 void EdgeBundles::view() const {
100  ViewGraph(*this, "EdgeBundles");
101 }
i
i
Definition: README.txt:29
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
MachineBasicBlock.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:757
llvm::ViewGraph
void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, then cleanup.
Definition: GraphWriter.h:375
llvm::IntEqClasses::join
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
Definition: IntEqClasses.cpp:32
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
llvm::EdgeBundles
Definition: EdgeBundles.h:24
llvm::EdgeBundlesID
char & EdgeBundlesID
EdgeBundles analysis - Bundle machine CFG edges.
CommandLine.h
llvm::EdgeBundles::view
void view() const
view - Visualize the annotated bipartite CFG with Graphviz.
Definition: EdgeBundles.cpp:99
Twine.h
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::EdgeBundles::getNumBundles
unsigned getNumBundles() const
getNumBundles - Return the total number of bundles in the CFG.
Definition: EdgeBundles.h:44
EdgeBundles.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
Passes.h
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::cl::opt< bool >
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
llvm::IntEqClasses::clear
void clear()
clear - Clear all classes so that grow() will assign a unique class to every integer.
Definition: IntEqClasses.h:50
llvm::IntEqClasses::compress
void compress()
compress - Compress equivalence classes by numbering them 0 .
Definition: IntEqClasses.cpp:60
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
ViewEdgeBundles
static cl::opt< bool > ViewEdgeBundles("view-edge-bundles", cl::Hidden, cl::desc("Pop up a window to show edge bundle graphs"))
b1
int b1
Definition: README.txt:84
llvm::MachineFunction
Definition: MachineFunction.h:234
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
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
GraphWriter.h
llvm::IntEqClasses::grow
void grow(unsigned N)
grow - Increase capacity to hold 0 .
Definition: IntEqClasses.cpp:25
llvm::EdgeBundles::ID
static char ID
Definition: EdgeBundles.h:36
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
b0
int b0
llvm::cl::desc
Definition: CommandLine.h:412
raw_ostream.h
MachineFunction.h
InitializePasses.h
llvm::EdgeBundles::getBundle
unsigned getBundle(unsigned N, bool Out) const
getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N
Definition: EdgeBundles.h:41
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37