Mercurial > hg > CbC > CbC_llvm

annotate lib/Target/Hexagon/RDFDeadCode.cpp @ 100:7d135dc70f03 LLVM 3.9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.9
author Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
date Tue, 26 Jan 2016 22:53:40 +0900
parents
children 803732b1fca8
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
100
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 //===--- RDFDeadCode.cpp --------------------------------------------------===//
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 //
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 // The LLVM Compiler Infrastructure
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 //
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 // This file is distributed under the University of Illinois Open Source
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 // License. See LICENSE.TXT for details.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 //
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 //===----------------------------------------------------------------------===//
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 //
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 // RDF-based generic dead code elimination.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 #include "RDFGraph.h"
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 #include "RDFLiveness.h"
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 #include "RDFDeadCode.h"
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 #include "llvm/ADT/SetVector.h"
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 #include "llvm/CodeGen/MachineBasicBlock.h"
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 #include "llvm/CodeGen/MachineFunction.h"
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 #include <queue>
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 using namespace llvm;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 using namespace rdf;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 // This drastically improves execution time in "collect" over using
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 // SetVector as a work queue, and popping the first element from it.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 template<typename T> struct DeadCodeElimination::SetQueue {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 SetQueue() : Set(), Queue() {}
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 bool empty() const {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 return Queue.empty();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 T pop_front() {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 T V = Queue.front();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 Queue.pop();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 Set.erase(V);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 return V;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 void push_back(T V) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 if (Set.count(V))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 return;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 Queue.push(V);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 Set.insert(V);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 private:
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 DenseSet<T> Set;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 std::queue<T> Queue;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 };
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 // Check if the given instruction has observable side-effects, i.e. if
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 // it should be considered "live". It is safe for this function to be
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 // overly conservative (i.e. return "true" for all instructions), but it
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 // is not safe to return "false" for an instruction that should not be
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 // considered removable.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 return true;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 return true;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 if (MI->isPHI())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 return false;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 for (auto &Op : MI->operands())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 if (Op.isReg() && MRI.isReserved(Op.getReg()))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 return true;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 return false;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 SetQueue<NodeId> &WorkQ) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 return;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 return;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 if (!LiveNodes.count(RA.Id))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 WorkQ.push_back(RA.Id);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 SetQueue<NodeId> &WorkQ) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 if (!LiveNodes.count(UA.Id))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 WorkQ.push_back(UA.Id);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 LiveNodes.insert(TA.Id);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 SetQueue<NodeId> &WorkQ) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 if (!LiveNodes.count(DA.Id))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 WorkQ.push_back(DA.Id);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 // Traverse the DFG and collect the set dead RefNodes and the set of
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 // dead instructions. Return "true" if any of these sets is non-empty,
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 // "false" otherwise.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 bool DeadCodeElimination::collect() {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 // This function works by first finding all live nodes. The dead nodes
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 // are then the complement of the set of live nodes.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 //
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 // Assume that all nodes are dead. Identify instructions which must be
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 // considered live, i.e. instructions with observable side-effects, such
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 // as calls and stores. All arguments of such instructions are considered
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 // live. For each live def, all operands used in the corresponding
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 // instruction are considered live. For each live use, all its reaching
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 // defs are considered live.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 LiveNodes.clear();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 SetQueue<NodeId> WorkQ;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 scanInstr(IA, WorkQ);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
120
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 while (!WorkQ.empty()) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 NodeId N = WorkQ.pop_front();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 LiveNodes.insert(N);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 auto RA = DFG.addr<RefNode*>(N);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 if (DFG.IsDef(RA))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 processDef(RA, WorkQ);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 else
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 processUse(RA, WorkQ);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 if (trace()) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 dbgs() << "Live nodes:\n";
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 for (NodeId N : LiveNodes) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 auto RA = DFG.addr<RefNode*>(N);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 if (LiveNodes.count(DA.Id))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 return false;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 return true;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 };
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 if (!LiveNodes.count(RA.Id))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 DeadNodes.insert(RA.Id);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 if (DFG.IsCode<NodeAttrs::Stmt>(IA))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 if (isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 continue;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 if (IsDead(IA)) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 DeadInstrs.insert(IA.Id);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
156 if (trace())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
161
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 return !DeadNodes.empty();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
164
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 // Erase the nodes given in the Nodes set from DFG. In addition to removing
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 // them from the DFG, if a node corresponds to a statement, the corresponding
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 // machine instruction is erased from the function.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 if (Nodes.empty())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 return false;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
171
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 // are included directly, for each InstrNode in Nodes, include the set
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 // of all RefNodes from it.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 NodeList DRNs, DINs;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 for (auto I : Nodes) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 auto BA = DFG.addr<NodeBase*>(I);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 uint16_t Type = BA.Addr->getType();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 if (Type == NodeAttrs::Ref) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 DRNs.push_back(DFG.addr<RefNode*>(I));
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 continue;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
183
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 // If it's a code node, add all ref nodes from it.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
185 uint16_t Kind = BA.Addr->getKind();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 DRNs.push_back(N);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 DINs.push_back(DFG.addr<InstrNode*>(I));
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 } else {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 llvm_unreachable("Unexpected code node");
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
192 return false;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
195
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
196 // Sort the list so that use nodes are removed first. This makes the
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
197 // "unlink" functions a bit faster.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
199 uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
200 if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def)
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 return true;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 return false;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 return A.Id < B.Id;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 };
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 std::sort(DRNs.begin(), DRNs.end(), UsesFirst);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
207
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 if (trace())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 dbgs() << "Removing dead ref nodes:\n";
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 for (NodeAddr<RefNode*> RA : DRNs) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 if (trace())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n';
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 if (DFG.IsUse(RA))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
214 DFG.unlinkUse(RA, true);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
215 else if (DFG.IsDef(RA))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 DFG.unlinkDef(RA, true);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
218
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
219 // Now, remove all dead instruction nodes.
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 for (NodeAddr<InstrNode*> IA : DINs) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 BA.Addr->removeMember(IA, DFG);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
223 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
224 continue;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
225
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
226 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 if (trace())
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 dbgs() << "erasing: " << *MI;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 MI->eraseFromParent();
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
230 }
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
231 return true;
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 }