OLD | NEW |
1 //===- ExpandStructRegs.cpp - Expand out variables with struct type--------===// | 1 //===- ExpandStructRegs.cpp - Expand out variables with struct type--------===// |
2 // | 2 // |
3 // The LLVM Compiler Infrastructure | 3 // The LLVM Compiler Infrastructure |
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 pass expands out some uses of LLVM variables | 10 // This pass expands out some uses of LLVM variables |
11 // (a.k.a. registers) of struct type. It replaces loads and stores of | 11 // (a.k.a. registers) of struct type. It replaces loads and stores of |
12 // structs with separate loads and stores of the structs' fields. The | 12 // structs with separate loads and stores of the structs' fields. The |
13 // motivation is to omit struct types from PNaCl's stable ABI. | 13 // motivation is to omit struct types from PNaCl's stable ABI. |
14 // | 14 // |
15 // ExpandStructRegs does not yet handle all possible uses of struct | 15 // ExpandStructRegs does not yet handle all possible uses of struct |
16 // values. It is intended to handle the uses that Clang and the SROA | 16 // values. It is intended to handle the uses that Clang and the SROA |
17 // pass generate. Clang generates struct loads and stores, along with | 17 // pass generate. Clang generates struct loads and stores, along with |
18 // extractvalue instructions, in its implementation of C++ method | 18 // extractvalue instructions, in its implementation of C++ method |
19 // pointers, and the SROA pass sometimes converts this code to using | 19 // pointers, and the SROA pass sometimes converts this code to using |
20 // insertvalue instructions too. | 20 // insertvalue instructions too. |
21 // | 21 // |
22 // ExpandStructRegs does not handle: | 22 // ExpandStructRegs does not handle: |
23 // | 23 // |
24 // * Nested struct types. | |
25 // * Array types. | 24 // * Array types. |
26 // * Function types containing arguments or return values of struct | 25 // * Function types containing arguments or return values of struct |
27 // type without the "byval" or "sret" attributes. Since by-value | 26 // type without the "byval" or "sret" attributes. Since by-value |
28 // struct-passing generally uses "byval"/"sret", this does not | 27 // struct-passing generally uses "byval"/"sret", this does not |
29 // matter. | 28 // matter. |
30 // | 29 // |
31 // Other limitations: | 30 // Other limitations: |
32 // | 31 // |
33 // * ExpandStructRegs does not attempt to use memcpy() where that | 32 // * ExpandStructRegs does not attempt to use memcpy() where that |
34 // might be more appropriate than copying fields individually. | 33 // might be more appropriate than copying fields individually. |
35 // * ExpandStructRegs does not preserve the contents of padding | 34 // * ExpandStructRegs does not preserve the contents of padding |
36 // between fields when copying structs. However, the contents of | 35 // between fields when copying structs. However, the contents of |
37 // padding fields are not defined anyway. | 36 // padding fields are not defined anyway. |
38 // | 37 // |
39 //===----------------------------------------------------------------------===// | 38 //===----------------------------------------------------------------------===// |
40 | 39 |
41 #include "llvm/ADT/SmallVector.h" | 40 #include "llvm/ADT/SmallVector.h" |
42 #include "llvm/IR/Constants.h" | 41 #include "llvm/IR/Constants.h" |
43 #include "llvm/IR/Function.h" | 42 #include "llvm/IR/Function.h" |
44 #include "llvm/IR/Instructions.h" | 43 #include "llvm/IR/Instructions.h" |
45 #include "llvm/Pass.h" | 44 #include "llvm/Pass.h" |
46 #include "llvm/Support/raw_ostream.h" | 45 #include "llvm/Support/raw_ostream.h" |
47 #include "llvm/Transforms/NaCl.h" | 46 #include "llvm/Transforms/NaCl.h" |
48 | 47 |
49 using namespace llvm; | 48 using namespace llvm; |
50 | 49 |
51 namespace { | 50 namespace { |
52 struct ExpandStructRegs : public FunctionPass { | 51 struct ExpandStructRegs : public FunctionPass { |
53 static char ID; // Pass identification, replacement for typeid | 52 static char ID; // Pass identification, replacement for typeid |
54 ExpandStructRegs() : FunctionPass(ID) { | 53 ExpandStructRegs() : FunctionPass(ID) { |
55 initializeExpandStructRegsPass(*PassRegistry::getPassRegistry()); | 54 initializeExpandStructRegsPass(*PassRegistry::getPassRegistry()); |
56 } | 55 } |
57 | 56 |
58 virtual bool runOnFunction(Function &F); | 57 virtual bool runOnFunction(Function &F); |
59 }; | 58 }; |
60 } | 59 } |
61 | 60 |
62 char ExpandStructRegs::ID = 0; | 61 char ExpandStructRegs::ID = 0; |
63 INITIALIZE_PASS(ExpandStructRegs, "expand-struct-regs", | 62 INITIALIZE_PASS(ExpandStructRegs, "expand-struct-regs", |
64 "Expand out variables with struct types", false, false) | 63 "Expand out variables with struct types", false, false) |
65 | 64 |
66 static void SplitUpPHINode(PHINode *Phi) { | 65 static bool DoAnotherPass(Type *Ty) { return isa<StructType>(Ty); } |
| 66 static bool DoAnotherPass(Value *V) { return DoAnotherPass(V->getType()); } |
| 67 |
| 68 static bool SplitUpPHINode(PHINode *Phi) { |
67 StructType *STy = cast<StructType>(Phi->getType()); | 69 StructType *STy = cast<StructType>(Phi->getType()); |
68 | 70 |
69 Value *NewStruct = UndefValue::get(STy); | 71 Value *NewStruct = UndefValue::get(STy); |
70 Instruction *NewStructInsertPt = Phi->getParent()->getFirstInsertionPt(); | 72 Instruction *NewStructInsertPt = Phi->getParent()->getFirstInsertionPt(); |
71 | 73 |
| 74 bool NeedsAnotherPass = false; |
| 75 |
72 // Create a separate PHINode for each struct field. | 76 // Create a separate PHINode for each struct field. |
73 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { | 77 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { |
74 SmallVector<unsigned, 1> EVIndexes; | 78 SmallVector<unsigned, 1> EVIndexes; |
75 EVIndexes.push_back(Index); | 79 EVIndexes.push_back(Index); |
76 | 80 |
77 PHINode *NewPhi = PHINode::Create( | 81 Type *ElemTy = STy->getElementType(Index); |
78 STy->getElementType(Index), Phi->getNumIncomingValues(), | 82 NeedsAnotherPass = NeedsAnotherPass || DoAnotherPass(ElemTy); |
79 Phi->getName() + ".index", Phi); | 83 |
| 84 PHINode *NewPhi = PHINode::Create(ElemTy, Phi->getNumIncomingValues(), |
| 85 Phi->getName() + ".index", Phi); |
80 CopyDebug(NewPhi, Phi); | 86 CopyDebug(NewPhi, Phi); |
81 for (unsigned PhiIndex = 0; PhiIndex < Phi->getNumIncomingValues(); | 87 for (unsigned PhiIndex = 0; PhiIndex < Phi->getNumIncomingValues(); |
82 ++PhiIndex) { | 88 ++PhiIndex) { |
83 BasicBlock *IncomingBB = Phi->getIncomingBlock(PhiIndex); | 89 BasicBlock *IncomingBB = Phi->getIncomingBlock(PhiIndex); |
84 Value *EV = CopyDebug( | 90 Value *EV = CopyDebug( |
85 ExtractValueInst::Create( | 91 ExtractValueInst::Create(Phi->getIncomingValue(PhiIndex), EVIndexes, |
86 Phi->getIncomingValue(PhiIndex), EVIndexes, | 92 Phi->getName() + ".extract", |
87 Phi->getName() + ".extract", IncomingBB->getTerminator()), Phi); | 93 IncomingBB->getTerminator()), |
| 94 Phi); |
88 NewPhi->addIncoming(EV, IncomingBB); | 95 NewPhi->addIncoming(EV, IncomingBB); |
89 } | 96 } |
90 | 97 |
91 // Reconstruct the original struct value. | 98 // Reconstruct the original struct value. |
92 NewStruct = CopyDebug( | 99 NewStruct = CopyDebug(InsertValueInst::Create(NewStruct, NewPhi, EVIndexes, |
93 InsertValueInst::Create(NewStruct, NewPhi, EVIndexes, | 100 Phi->getName() + ".insert", |
94 Phi->getName() + ".insert", NewStructInsertPt), | 101 NewStructInsertPt), |
95 Phi); | 102 Phi); |
96 } | 103 } |
97 Phi->replaceAllUsesWith(NewStruct); | 104 Phi->replaceAllUsesWith(NewStruct); |
98 Phi->eraseFromParent(); | 105 Phi->eraseFromParent(); |
| 106 |
| 107 return NeedsAnotherPass; |
99 } | 108 } |
100 | 109 |
101 static void SplitUpSelect(SelectInst *Select) { | 110 static bool SplitUpSelect(SelectInst *Select) { |
102 StructType *STy = cast<StructType>(Select->getType()); | 111 StructType *STy = cast<StructType>(Select->getType()); |
103 Value *NewStruct = UndefValue::get(STy); | 112 Value *NewStruct = UndefValue::get(STy); |
104 | 113 |
| 114 bool NeedsAnotherPass = false; |
105 // Create a separate SelectInst for each struct field. | 115 // Create a separate SelectInst for each struct field. |
106 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { | 116 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { |
107 SmallVector<unsigned, 1> EVIndexes; | 117 SmallVector<unsigned, 1> EVIndexes; |
108 EVIndexes.push_back(Index); | 118 EVIndexes.push_back(Index); |
109 | 119 |
110 Value *TrueVal = CopyDebug( | 120 Value *TrueVal = CopyDebug( |
111 ExtractValueInst::Create(Select->getTrueValue(), EVIndexes, | 121 ExtractValueInst::Create(Select->getTrueValue(), EVIndexes, |
112 Select->getName() + ".extract", Select), | 122 Select->getName() + ".extract", Select), |
113 Select); | 123 Select); |
114 Value *FalseVal = CopyDebug( | 124 Value *FalseVal = CopyDebug( |
115 ExtractValueInst::Create(Select->getFalseValue(), EVIndexes, | 125 ExtractValueInst::Create(Select->getFalseValue(), EVIndexes, |
116 Select->getName() + ".extract", Select), | 126 Select->getName() + ".extract", Select), |
117 Select); | 127 Select); |
118 Value *NewSelect = CopyDebug( | 128 Value *NewSelect = |
119 SelectInst::Create(Select->getCondition(), TrueVal, FalseVal, | 129 CopyDebug(SelectInst::Create(Select->getCondition(), TrueVal, FalseVal, |
120 Select->getName() + ".index", Select), Select); | 130 Select->getName() + ".index", Select), |
| 131 Select); |
| 132 |
| 133 NeedsAnotherPass = NeedsAnotherPass || DoAnotherPass(NewSelect); |
121 | 134 |
122 // Reconstruct the original struct value. | 135 // Reconstruct the original struct value. |
123 NewStruct = CopyDebug( | 136 NewStruct = CopyDebug( |
124 InsertValueInst::Create(NewStruct, NewSelect, EVIndexes, | 137 InsertValueInst::Create(NewStruct, NewSelect, EVIndexes, |
125 Select->getName() + ".insert", Select), | 138 Select->getName() + ".insert", Select), |
126 Select); | 139 Select); |
127 } | 140 } |
128 Select->replaceAllUsesWith(NewStruct); | 141 Select->replaceAllUsesWith(NewStruct); |
129 Select->eraseFromParent(); | 142 Select->eraseFromParent(); |
| 143 |
| 144 return NeedsAnotherPass; |
130 } | 145 } |
131 | 146 |
132 template <class InstType> | 147 template <class InstType> |
133 static void ProcessLoadOrStoreAttrs(InstType *Dest, InstType *Src) { | 148 static void ProcessLoadOrStoreAttrs(InstType *Dest, InstType *Src) { |
134 CopyDebug(Dest, Src); | 149 CopyDebug(Dest, Src); |
135 Dest->setVolatile(Src->isVolatile()); | 150 Dest->setVolatile(Src->isVolatile()); |
136 if (Src->isAtomic()) { | 151 if (Src->isAtomic()) { |
137 errs() << "Use: " << *Src << "\n"; | 152 errs() << "Use: " << *Src << "\n"; |
138 report_fatal_error("Atomic struct loads/stores not supported"); | 153 report_fatal_error("Atomic struct loads/stores not supported"); |
139 } | 154 } |
140 // Make a pessimistic assumption about alignment. Preserving | 155 // Make a pessimistic assumption about alignment. Preserving |
141 // alignment information here is tricky and is not really desirable | 156 // alignment information here is tricky and is not really desirable |
142 // for PNaCl because mistakes here could lead to non-portable | 157 // for PNaCl because mistakes here could lead to non-portable |
143 // behaviour. | 158 // behaviour. |
144 Dest->setAlignment(1); | 159 Dest->setAlignment(1); |
145 } | 160 } |
146 | 161 |
147 static void SplitUpStore(StoreInst *Store) { | 162 static bool SplitUpStore(StoreInst *Store) { |
148 StructType *STy = cast<StructType>(Store->getValueOperand()->getType()); | 163 StructType *STy = cast<StructType>(Store->getValueOperand()->getType()); |
| 164 |
| 165 bool NeedsAnotherPass = false; |
149 // Create a separate store instruction for each struct field. | 166 // Create a separate store instruction for each struct field. |
150 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { | 167 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { |
151 SmallVector<Value *, 2> Indexes; | 168 SmallVector<Value *, 2> Indexes; |
152 Indexes.push_back(ConstantInt::get(Store->getContext(), APInt(32, 0))); | 169 Indexes.push_back(ConstantInt::get(Store->getContext(), APInt(32, 0))); |
153 Indexes.push_back(ConstantInt::get(Store->getContext(), APInt(32, Index))); | 170 Indexes.push_back(ConstantInt::get(Store->getContext(), APInt(32, Index))); |
154 Value *GEP = CopyDebug(GetElementPtrInst::Create( | 171 Value *GEP = |
155 Store->getPointerOperand(), Indexes, | 172 CopyDebug(GetElementPtrInst::Create( |
156 Store->getPointerOperand()->getName() + ".index", | 173 Store->getPointerOperand(), Indexes, |
157 Store), Store); | 174 Store->getPointerOperand()->getName() + ".index", Store), |
| 175 Store); |
| 176 NeedsAnotherPass = |
| 177 NeedsAnotherPass || DoAnotherPass(GEP->getType()->getContainedType(0)); |
| 178 |
158 SmallVector<unsigned, 1> EVIndexes; | 179 SmallVector<unsigned, 1> EVIndexes; |
159 EVIndexes.push_back(Index); | 180 EVIndexes.push_back(Index); |
160 Value *Field = ExtractValueInst::Create(Store->getValueOperand(), | 181 Value *Field = ExtractValueInst::Create(Store->getValueOperand(), EVIndexes, |
161 EVIndexes, "", Store); | 182 "", Store); |
162 StoreInst *NewStore = new StoreInst(Field, GEP, Store); | 183 StoreInst *NewStore = new StoreInst(Field, GEP, Store); |
163 ProcessLoadOrStoreAttrs(NewStore, Store); | 184 ProcessLoadOrStoreAttrs(NewStore, Store); |
164 } | 185 } |
165 Store->eraseFromParent(); | 186 Store->eraseFromParent(); |
166 } | 187 |
167 | 188 return NeedsAnotherPass; |
168 static void SplitUpLoad(LoadInst *Load) { | 189 } |
| 190 |
| 191 static bool SplitUpLoad(LoadInst *Load) { |
169 StructType *STy = cast<StructType>(Load->getType()); | 192 StructType *STy = cast<StructType>(Load->getType()); |
170 Value *NewStruct = UndefValue::get(STy); | 193 Value *NewStruct = UndefValue::get(STy); |
171 | 194 |
| 195 bool NeedsAnotherPass = false; |
172 // Create a separate load instruction for each struct field. | 196 // Create a separate load instruction for each struct field. |
173 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { | 197 for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) { |
174 SmallVector<Value *, 2> Indexes; | 198 SmallVector<Value *, 2> Indexes; |
175 Indexes.push_back(ConstantInt::get(Load->getContext(), APInt(32, 0))); | 199 Indexes.push_back(ConstantInt::get(Load->getContext(), APInt(32, 0))); |
176 Indexes.push_back(ConstantInt::get(Load->getContext(), APInt(32, Index))); | 200 Indexes.push_back(ConstantInt::get(Load->getContext(), APInt(32, Index))); |
177 Value *GEP = CopyDebug( | 201 Value *GEP = |
178 GetElementPtrInst::Create(Load->getPointerOperand(), Indexes, | 202 CopyDebug(GetElementPtrInst::Create(Load->getPointerOperand(), Indexes, |
179 Load->getName() + ".index", Load), Load); | 203 Load->getName() + ".index", Load), |
| 204 Load); |
180 LoadInst *NewLoad = new LoadInst(GEP, Load->getName() + ".field", Load); | 205 LoadInst *NewLoad = new LoadInst(GEP, Load->getName() + ".field", Load); |
| 206 |
| 207 NeedsAnotherPass = NeedsAnotherPass || DoAnotherPass(NewLoad); |
181 ProcessLoadOrStoreAttrs(NewLoad, Load); | 208 ProcessLoadOrStoreAttrs(NewLoad, Load); |
182 | 209 |
183 // Reconstruct the struct value. | 210 // Reconstruct the struct value. |
184 SmallVector<unsigned, 1> EVIndexes; | 211 SmallVector<unsigned, 1> EVIndexes; |
185 EVIndexes.push_back(Index); | 212 EVIndexes.push_back(Index); |
186 NewStruct = CopyDebug( | 213 NewStruct = |
187 InsertValueInst::Create(NewStruct, NewLoad, EVIndexes, | 214 CopyDebug(InsertValueInst::Create(NewStruct, NewLoad, EVIndexes, |
188 Load->getName() + ".insert", Load), Load); | 215 Load->getName() + ".insert", Load), |
| 216 Load); |
189 } | 217 } |
190 Load->replaceAllUsesWith(NewStruct); | 218 Load->replaceAllUsesWith(NewStruct); |
191 Load->eraseFromParent(); | 219 Load->eraseFromParent(); |
192 } | 220 |
193 | 221 return NeedsAnotherPass; |
194 static bool ExpandExtractValue(ExtractValueInst *EV) { | 222 } |
| 223 |
| 224 static bool ExpandExtractValue(ExtractValueInst *EV, |
| 225 SmallVectorImpl<Instruction *> *ToErase) { |
195 // Search for the insertvalue instruction that inserts the struct field | 226 // Search for the insertvalue instruction that inserts the struct field |
196 // referenced by this extractvalue instruction, excluding CmpXchg which | 227 // referenced by this extractvalue instruction, excluding CmpXchg which |
197 // returns a struct and is handled by RewriteAtomics. | 228 // returns a struct and is handled by RewriteAtomics. |
198 Value *StructVal = EV->getAggregateOperand(); | 229 Value *StructVal = EV->getAggregateOperand(); |
199 Value *ResultField; | 230 Value *ResultField = nullptr; |
| 231 |
| 232 // The current depth of the search. It's impossible to backtrack in our search |
| 233 // tree (all prior (not in the CFG sense) extractvalues will already be |
| 234 // expanded), so this variable is never reset to zero. |
| 235 size_t EVIndex = 0; |
| 236 |
200 if (isa<AtomicCmpXchgInst>(StructVal)) | 237 if (isa<AtomicCmpXchgInst>(StructVal)) |
201 return false; | 238 return false; |
| 239 |
202 for (;;) { | 240 for (;;) { |
203 if (InsertValueInst *IV = dyn_cast<InsertValueInst>(StructVal)) { | 241 if (InsertValueInst *IV = dyn_cast<InsertValueInst>(StructVal)) { |
204 if (EV->getNumIndices() != 1 || IV->getNumIndices() != 1) { | 242 |
205 errs() << "Value: " << *EV << "\n"; | 243 size_t IVIndex = 0; |
206 errs() << "Value: " << *IV << "\n"; | 244 for (; EVIndex < EV->getIndices().size() && |
207 report_fatal_error("ExpandStructRegs does not handle nested structs"); | 245 IVIndex < IV->getIndices().size(); |
208 } | 246 ++IVIndex, ++EVIndex) { |
209 if (EV->getIndices()[0] == IV->getIndices()[0]) { | 247 |
210 ResultField = IV->getInsertedValueOperand(); | 248 const bool Equal = |
| 249 (EV->getIndices()[EVIndex] == IV->getIndices()[IVIndex]); |
| 250 |
| 251 if (IVIndex + 1 == IV->getIndices().size() && Equal) { |
| 252 if (EVIndex + 1 == EV->getIndices().size()) { |
| 253 // Exact match. We break out of all loops and ResultField will |
| 254 // replace EV. |
| 255 ResultField = IV->getInsertedValueOperand(); |
| 256 } else { |
| 257 // We've found a match, but haven't reached the end of EV's indexes. |
| 258 // We continue looping through the outermost loop, and search for |
| 259 // indices on the next level down (ie we increment EVIndex). |
| 260 // This branch is common when encountering nested insertvalues; for |
| 261 // example: |
| 262 // ```llvm |
| 263 // %1 = insertvalue { i32 } undef, i32 1, 0 |
| 264 // %2 = insertvalue { { i32 } } %1, { i32 } %1, 0 |
| 265 // %3 = extractvalue { { i32 } } %2, 0, 0 |
| 266 // ``` |
| 267 StructVal = IV->getInsertedValueOperand(); |
| 268 ++EVIndex; |
| 269 } |
| 270 break; |
| 271 } else if (!Equal) { |
| 272 // No match. Try the next struct value in the chain. |
| 273 // For example: |
| 274 // ```llvm |
| 275 // %1 = insertvalue { i32, i32, i32 } undef, i32 5, 0 |
| 276 // %2 = insertvalue { i32, i32, i32 } %1, i32 10, 1 |
| 277 // %3 = insertvalue { i32, i32, i32 } %2, i32 15, 2 |
| 278 // %4 = extractvalue { i32, i32, i32 } %3, 0 |
| 279 // ``` |
| 280 // In this case, to expand %4, this branch will hit insertvalues %3 |
| 281 // and %2 before |
| 282 // it finds the solution, %1. |
| 283 StructVal = IV->getAggregateOperand(); |
| 284 break; |
| 285 } |
| 286 |
| 287 // One last case worth mentioning: |
| 288 // ```llvm |
| 289 // %aa = alloca { i32 } |
| 290 // %a = insertvalue { i32 } undef, i32 1, 0 |
| 291 // %b = insertvalue { { i32 } } undef, { i32 } %a, 0 |
| 292 // %c = extractvalue { { i32 } } %b, 0 |
| 293 // store { i32 } %c, { i32 }* %aa |
| 294 // ``` |
| 295 // In the case of %c, the condition of our inner loop will be false, and |
| 296 // we will fall into (EVIndex == EV->getIndices().size()) |
| 297 // Note that in this case, SplitStore will have inserted an extra |
| 298 // extractvalue and GEP: |
| 299 // ```llvm |
| 300 // %aa = alloca { i32 } |
| 301 // %a = insertvalue { i32 } undef, i32 1, 0 |
| 302 // %b = insertvalue { { i32 } } undef, { i32 } %a, 0 |
| 303 // %c.extractval = extractvalue { i32 } %a, 0 |
| 304 // %aa.index = getelementptr { i32 }* %aa, i32 0, i32 0 |
| 305 // store i32 %c, i32* %aa.index |
| 306 // ``` |
| 307 } |
| 308 if (ResultField) { |
| 309 // \O/ We're done with this ExtractValueInst! |
211 break; | 310 break; |
212 } | 311 } else if (EVIndex == EV->getIndices().size()) { |
213 // No match. Try the next struct value in the chain. | 312 // We've found an insertvalue that inserts at one or more levels deeper |
214 StructVal = IV->getAggregateOperand(); | 313 // than this extractvalue. For example (borrowed from the tests), where |
| 314 // %h is EV && %e is IV: |
| 315 // ```llvm |
| 316 // %e = insertvalue { { { i32, i64 } }, i64 } undef, { i32, i64 } %b, 0,
0 |
| 317 // %h = extractvalue { { { i32, i64 } }, i64 } %e, 0 |
| 318 // ; later on.. |
| 319 // %1 = extractvalue { { i32, i64 } } %h, 0 |
| 320 // ``` |
| 321 // This expands to: |
| 322 // ```llvm |
| 323 // %e = insertvalue { { { i32, i64 } }, i64 } undef, { i32, i64 } %b, 0,
0 |
| 324 // %1 = insertvalue { { i32, i64 } } undef, { i32, i64 } %b, 0 |
| 325 // %h = extractvalue { { { i32, i64 } }, i64 } %e, 0 |
| 326 // %2 = extractvalue { { i32, i64 } } %h, 0 |
| 327 // ``` |
| 328 // Then, outside the outer loop, %h is deleted: |
| 329 // ```llvm |
| 330 // %e = insertvalue { { { i32, i64 } }, i64 } undef, { i32, i64 } %b, 0,
0 |
| 331 // %1 = insertvalue { { i32, i64 } } undef, { i32, i64 } %b, 0 |
| 332 // %2 = extractvalue { { i32, i64 } } %1, 0 |
| 333 // ``` |
| 334 // %2 will be expanded at a later point. |
| 335 // This branch used the second index in %e to create %1 (because %2 && |
| 336 // %e's first indices where equal). |
| 337 // |
| 338 // Additionally, it's impossible to not change StructVal && not hit this |
| 339 // branch (but the reverse is not true!). |
| 340 |
| 341 SmallVector<unsigned, 4> Indices(IV->getIndices().begin() + IVIndex, |
| 342 IV->getIndices().end()); |
| 343 |
| 344 InsertValueInst *Insert = InsertValueInst::Create( |
| 345 UndefValue::get(EV->getType()), IV->getInsertedValueOperand(), |
| 346 Indices, "", EV); |
| 347 ToErase->push_back(Insert); |
| 348 ResultField = CopyDebug(Insert, EV); |
| 349 break; |
| 350 } |
| 351 |
| 352 // At this point, StructVal must be changed. |
215 } else if (Constant *C = dyn_cast<Constant>(StructVal)) { | 353 } else if (Constant *C = dyn_cast<Constant>(StructVal)) { |
216 ResultField = ConstantExpr::getExtractValue(C, EV->getIndices()); | 354 SmallVector<unsigned, 4> Indices(EV->getIndices().begin() + EVIndex, |
| 355 EV->getIndices().end()); |
| 356 ResultField = ConstantExpr::getExtractValue(C, Indices); |
| 357 break; |
| 358 } else if (isa<LoadInst>(StructVal)) { |
| 359 ResultField = StructVal; |
217 break; | 360 break; |
218 } else { | 361 } else { |
219 errs() << "Value: " << *StructVal << "\n"; | 362 errs() << "Value: " << *StructVal << "\n"; |
220 report_fatal_error("Unrecognized struct value"); | 363 report_fatal_error("Unrecognized struct value"); |
221 } | 364 } |
222 } | 365 } |
| 366 |
| 367 assert(ResultField); // Failsafe. |
223 EV->replaceAllUsesWith(ResultField); | 368 EV->replaceAllUsesWith(ResultField); |
224 EV->eraseFromParent(); | 369 EV->eraseFromParent(); |
225 return true; | 370 return true; |
226 } | 371 } |
227 | 372 |
228 bool ExpandStructRegs::runOnFunction(Function &Func) { | 373 static bool ExpandExtractValues(Function &Func) { |
229 bool Changed = false; | 374 bool Changed = false; |
230 | 375 |
231 // Split up aggregate loads, stores and phi nodes into operations on | 376 SmallVector<Instruction *, 10> ToErase; |
232 // scalar types. This inserts extractvalue and insertvalue | |
233 // instructions which we will expand out later. | |
234 for (Function::iterator BB = Func.begin(), E = Func.end(); | |
235 BB != E; ++BB) { | |
236 for (BasicBlock::iterator Iter = BB->begin(), E = BB->end(); | |
237 Iter != E; ) { | |
238 Instruction *Inst = Iter++; | |
239 if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) { | |
240 if (Store->getValueOperand()->getType()->isStructTy()) { | |
241 SplitUpStore(Store); | |
242 Changed = true; | |
243 } | |
244 } else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) { | |
245 if (Load->getType()->isStructTy()) { | |
246 SplitUpLoad(Load); | |
247 Changed = true; | |
248 } | |
249 } else if (PHINode *Phi = dyn_cast<PHINode>(Inst)) { | |
250 if (Phi->getType()->isStructTy()) { | |
251 SplitUpPHINode(Phi); | |
252 Changed = true; | |
253 } | |
254 } else if (SelectInst *Select = dyn_cast<SelectInst>(Inst)) { | |
255 if (Select->getType()->isStructTy()) { | |
256 SplitUpSelect(Select); | |
257 Changed = true; | |
258 } | |
259 } | |
260 } | |
261 } | |
262 | |
263 // Expand out all the extractvalue instructions. Also collect up | 377 // Expand out all the extractvalue instructions. Also collect up |
264 // the insertvalue instructions for later deletion so that we do not | 378 // the insertvalue instructions for later deletion so that we do not |
265 // need to make extra passes across the whole function. | 379 // need to make extra passes across the whole function. |
266 SmallVector<Instruction *, 10> ToErase; | 380 |
267 for (Function::iterator BB = Func.begin(), E = Func.end(); | 381 for (auto &BB : Func) { |
268 BB != E; ++BB) { | 382 for (BasicBlock::iterator Iter = BB.begin(), E = BB.end(); Iter != E;) { |
269 for (BasicBlock::iterator Iter = BB->begin(), E = BB->end(); | |
270 Iter != E; ) { | |
271 Instruction *Inst = Iter++; | 383 Instruction *Inst = Iter++; |
272 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Inst)) { | 384 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Inst)) { |
273 Changed |= ExpandExtractValue(EV); | 385 Changed |= ExpandExtractValue(EV, &ToErase); |
274 } else if (isa<InsertValueInst>(Inst)) { | 386 } else if (isa<InsertValueInst>(Inst)) { |
275 ToErase.push_back(Inst); | 387 ToErase.push_back(Inst); |
276 Changed = true; | 388 Changed = true; |
277 } | 389 } |
278 } | 390 } |
279 } | 391 } |
| 392 |
280 // Delete the insertvalue instructions. These can reference each | 393 // Delete the insertvalue instructions. These can reference each |
281 // other, so we must do dropAllReferences() before doing | 394 // other, so we must do dropAllReferences() before doing |
282 // eraseFromParent(), otherwise we will try to erase instructions | 395 // eraseFromParent(), otherwise we will try to erase instructions |
283 // that are still referenced. | 396 // that are still referenced. |
284 for (SmallVectorImpl<Instruction *>::iterator I = ToErase.begin(), | 397 for (Instruction *I : ToErase) { |
285 E = ToErase.end(); | 398 I->dropAllReferences(); |
286 I != E; ++I) { | 399 } |
287 (*I)->dropAllReferences(); | 400 |
288 } | 401 for (Instruction *I : ToErase) { |
289 for (SmallVectorImpl<Instruction *>::iterator I = ToErase.begin(), | 402 I->eraseFromParent(); |
290 E = ToErase.end(); | 403 } |
291 I != E; ++I) { | 404 |
292 (*I)->eraseFromParent(); | |
293 } | |
294 return Changed; | 405 return Changed; |
295 } | 406 } |
296 | 407 |
| 408 bool ExpandStructRegs::runOnFunction(Function &Func) { |
| 409 bool Changed = false; |
| 410 bool NeedsAnotherPass; |
| 411 |
| 412 do { |
| 413 NeedsAnotherPass = false; |
| 414 // Split up aggregate loads, stores and phi nodes into operations on |
| 415 // scalar types. This inserts extractvalue and insertvalue |
| 416 // instructions which we will expand out later. |
| 417 for (Function::iterator BB = Func.begin(), E = Func.end(); BB != E; ++BB) { |
| 418 for (BasicBlock::iterator Iter = BB->begin(), E = BB->end(); Iter != E;) { |
| 419 Instruction *Inst = Iter++; |
| 420 if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) { |
| 421 if (Store->getValueOperand()->getType()->isStructTy()) { |
| 422 NeedsAnotherPass |= SplitUpStore(Store); |
| 423 Changed = true; |
| 424 } |
| 425 } else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) { |
| 426 if (Load->getType()->isStructTy()) { |
| 427 NeedsAnotherPass |= SplitUpLoad(Load); |
| 428 Changed = true; |
| 429 } |
| 430 } else if (PHINode *Phi = dyn_cast<PHINode>(Inst)) { |
| 431 if (Phi->getType()->isStructTy()) { |
| 432 NeedsAnotherPass |= SplitUpPHINode(Phi); |
| 433 Changed = true; |
| 434 } |
| 435 } else if (SelectInst *Select = dyn_cast<SelectInst>(Inst)) { |
| 436 if (Select->getType()->isStructTy()) { |
| 437 NeedsAnotherPass |= SplitUpSelect(Select); |
| 438 Changed = true; |
| 439 } |
| 440 } |
| 441 } |
| 442 } |
| 443 } while (NeedsAnotherPass); |
| 444 |
| 445 Changed |= ExpandExtractValues(Func); |
| 446 |
| 447 return Changed; |
| 448 } |
| 449 |
297 FunctionPass *llvm::createExpandStructRegsPass() { | 450 FunctionPass *llvm::createExpandStructRegsPass() { |
298 return new ExpandStructRegs(); | 451 return new ExpandStructRegs(); |
299 } | 452 } |
OLD | NEW |