Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(442)

Side by Side Diff: src/IceLiveness.cpp

Issue 652633002: Subzero: Improve performance of liveness analysis and live range construction. (Closed) Base URL: https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Patch Set: Remove TODO Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/IceLiveness.h ('k') | src/IceOperand.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 //===- subzero/src/IceLiveness.cpp - Liveness analysis implementation -----===// 1 //===- subzero/src/IceLiveness.cpp - Liveness analysis implementation -----===//
2 // 2 //
3 // The Subzero Code Generator 3 // The Subzero Code Generator
4 // 4 //
5 // This file is distributed under the University of Illinois Open Source 5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details. 6 // License. See LICENSE.TXT for details.
7 // 7 //
8 //===----------------------------------------------------------------------===// 8 //===----------------------------------------------------------------------===//
9 // 9 //
10 // This file provides some of the support for the Liveness class. In 10 // This file provides some of the support for the Liveness class. In
(...skipping 14 matching lines...) Expand all
25 #include "IceInst.h" 25 #include "IceInst.h"
26 #include "IceLiveness.h" 26 #include "IceLiveness.h"
27 #include "IceOperand.h" 27 #include "IceOperand.h"
28 28
29 namespace Ice { 29 namespace Ice {
30 30
31 void Liveness::init() { 31 void Liveness::init() {
32 // Initialize most of the container sizes. 32 // Initialize most of the container sizes.
33 SizeT NumVars = Func->getVariables().size(); 33 SizeT NumVars = Func->getVariables().size();
34 SizeT NumNodes = Func->getNumNodes(); 34 SizeT NumNodes = Func->getNumNodes();
35 VariablesMetadata *VMetadata = Func->getVMetadata();
35 Nodes.resize(NumNodes); 36 Nodes.resize(NumNodes);
36 VarToLiveMap.resize(NumVars); 37 VarToLiveMap.resize(NumVars);
37 if (Mode == Liveness_Intervals) 38 if (Mode == Liveness_Intervals)
38 LiveRanges.resize(NumVars); 39 LiveRanges.resize(NumVars);
39 40
40 // Count the number of globals, and the number of locals for each 41 // Count the number of globals, and the number of locals for each
41 // block. 42 // block.
42 for (SizeT i = 0; i < NumVars; ++i) { 43 for (SizeT i = 0; i < NumVars; ++i) {
43 Variable *Var = Func->getVariables()[i]; 44 Variable *Var = Func->getVariables()[i];
44 if (Func->getVMetadata()->isMultiBlock(Var)) { 45 if (VMetadata->isMultiBlock(Var)) {
45 ++NumGlobals; 46 ++NumGlobals;
46 } else { 47 } else {
47 SizeT Index = Func->getVMetadata()->getLocalUseNode(Var)->getIndex(); 48 SizeT Index = VMetadata->getLocalUseNode(Var)->getIndex();
48 ++Nodes[Index].NumLocals; 49 ++Nodes[Index].NumLocals;
49 } 50 }
50 } 51 }
51 52
52 // Resize each LivenessNode::LiveToVarMap, and the global 53 // Resize each LivenessNode::LiveToVarMap, and the global
53 // LiveToVarMap. Reset the counts to 0. 54 // LiveToVarMap. Reset the counts to 0.
54 for (SizeT i = 0; i < NumNodes; ++i) { 55 for (SizeT i = 0; i < NumNodes; ++i) {
55 Nodes[i].LiveToVarMap.assign(Nodes[i].NumLocals, NULL); 56 Nodes[i].LiveToVarMap.assign(Nodes[i].NumLocals, NULL);
56 Nodes[i].NumLocals = 0; 57 Nodes[i].NumLocals = 0;
57 } 58 }
58 LiveToVarMap.assign(NumGlobals, NULL); 59 LiveToVarMap.assign(NumGlobals, NULL);
59 60
60 // Sort each variable into the appropriate LiveToVarMap. Also set 61 // Sort each variable into the appropriate LiveToVarMap. Also set
61 // VarToLiveMap. 62 // VarToLiveMap.
62 SizeT TmpNumGlobals = 0; 63 SizeT TmpNumGlobals = 0;
63 for (SizeT i = 0; i < NumVars; ++i) { 64 for (SizeT i = 0; i < NumVars; ++i) {
64 Variable *Var = Func->getVariables()[i]; 65 Variable *Var = Func->getVariables()[i];
65 SizeT VarIndex = Var->getIndex(); 66 SizeT VarIndex = Var->getIndex();
66 SizeT LiveIndex; 67 SizeT LiveIndex;
67 if (Func->getVMetadata()->isMultiBlock(Var)) { 68 if (VMetadata->isMultiBlock(Var)) {
68 LiveIndex = TmpNumGlobals++; 69 LiveIndex = TmpNumGlobals++;
69 LiveToVarMap[LiveIndex] = Var; 70 LiveToVarMap[LiveIndex] = Var;
70 } else { 71 } else {
71 SizeT NodeIndex = Func->getVMetadata()->getLocalUseNode(Var)->getIndex(); 72 SizeT NodeIndex = VMetadata->getLocalUseNode(Var)->getIndex();
72 LiveIndex = Nodes[NodeIndex].NumLocals++; 73 LiveIndex = Nodes[NodeIndex].NumLocals++;
73 Nodes[NodeIndex].LiveToVarMap[LiveIndex] = Var; 74 Nodes[NodeIndex].LiveToVarMap[LiveIndex] = Var;
74 LiveIndex += NumGlobals; 75 LiveIndex += NumGlobals;
75 } 76 }
76 VarToLiveMap[VarIndex] = LiveIndex; 77 VarToLiveMap[VarIndex] = LiveIndex;
77 } 78 }
78 assert(NumGlobals == TmpNumGlobals); 79 assert(NumGlobals == TmpNumGlobals);
79 80
80 // Process each node. 81 // Process each node.
81 const NodeList &LNodes = Func->getNodes(); 82 const NodeList &LNodes = Func->getNodes();
82 SizeT NumLNodes = LNodes.size(); 83 SizeT NumLNodes = LNodes.size();
83 for (SizeT i = 0; i < NumLNodes; ++i) { 84 for (SizeT i = 0; i < NumLNodes; ++i) {
84 LivenessNode &Node = Nodes[LNodes[i]->getIndex()]; 85 LivenessNode &Node = Nodes[LNodes[i]->getIndex()];
85 // NumLocals, LiveToVarMap already initialized 86 // NumLocals, LiveToVarMap already initialized
86 Node.LiveIn.resize(NumGlobals); 87 Node.LiveIn.resize(NumGlobals);
87 Node.LiveOut.resize(NumGlobals); 88 Node.LiveOut.resize(NumGlobals);
88 // LiveBegin and LiveEnd are reinitialized before each pass over 89 // LiveBegin and LiveEnd are reinitialized before each pass over
89 // the block. 90 // the block.
90 } 91 }
91 } 92 }
92 93
93 Variable *Liveness::getVariable(SizeT LiveIndex, const CfgNode *Node) const { 94 Variable *Liveness::getVariable(SizeT LiveIndex, const CfgNode *Node) const {
94 if (LiveIndex < NumGlobals) 95 if (LiveIndex < NumGlobals)
95 return LiveToVarMap[LiveIndex]; 96 return LiveToVarMap[LiveIndex];
96 SizeT NodeIndex = Node->getIndex(); 97 SizeT NodeIndex = Node->getIndex();
97 return Nodes[NodeIndex].LiveToVarMap[LiveIndex - NumGlobals]; 98 return Nodes[NodeIndex].LiveToVarMap[LiveIndex - NumGlobals];
98 } 99 }
99 100
100 SizeT Liveness::getLiveIndex(const Variable *Var) const {
101 return VarToLiveMap[Var->getIndex()];
102 }
103
104 void Liveness::addLiveRange(Variable *Var, InstNumberT Start, InstNumberT End, 101 void Liveness::addLiveRange(Variable *Var, InstNumberT Start, InstNumberT End,
105 uint32_t WeightDelta) { 102 uint32_t WeightDelta) {
106 LiveRange &LiveRange = LiveRanges[Var->getIndex()]; 103 LiveRange &LiveRange = LiveRanges[Var->getIndex()];
107 assert(WeightDelta != RegWeight::Inf); 104 assert(WeightDelta != RegWeight::Inf);
108 LiveRange.addSegment(Start, End); 105 LiveRange.addSegment(Start, End);
109 LiveRange.addWeight(WeightDelta); 106 LiveRange.addWeight(WeightDelta);
110 } 107 }
111 108
112 LiveRange &Liveness::getLiveRange(Variable *Var) { 109 LiveRange &Liveness::getLiveRange(Variable *Var) {
113 return LiveRanges[Var->getIndex()]; 110 return LiveRanges[Var->getIndex()];
114 } 111 }
115 112
116 } // end of namespace Ice 113 } // end of namespace Ice
OLDNEW
« no previous file with comments | « src/IceLiveness.h ('k') | src/IceOperand.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698