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