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

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: lib/Transforms/NaCl/ExpandI64.cpp

Issue 1692803002: Remove Emscripten support (Closed) Base URL: https://chromium.googlesource.com/a/native_client/pnacl-llvm.git@master
Patch Set: Created 4 years, 10 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 | « lib/Transforms/NaCl/CMakeLists.txt ('k') | lib/Transforms/NaCl/ExpandInsertExtractElement.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 //===- ExpandI64.cpp - Expand i64 and wider integer types -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===------------------------------------------------------------------===//
9 //
10 // This pass expands and lowers all operations on integers i64 and wider
11 // into 32-bit operations that can be handled by JS in a natural way.
12 //
13 // 64-bit variables become pairs of 2 32-bit variables, for the low and
14 // high 32 bit chunks. This happens for both registers and function
15 // arguments. Function return values become a return of the low 32 bits
16 // and a store of the high 32-bits in tempRet0, a global helper variable.
17 // Larger values become more chunks of 32 bits. Currently we require that
18 // types be a multiple of 32 bits.
19 //
20 // Many operations then become simple pairs of operations, for example
21 // bitwise AND becomes and AND of each 32-bit chunk. More complex operations
22 // like addition are lowered into calls into library support code in
23 // Emscripten (i64Add for example).
24 //
25 //===------------------------------------------------------------------===//
26
27 #include "llvm/ADT/PostOrderIterator.h"
28 #include "llvm/ADT/SmallString.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/StringExtras.h"
31 #include "llvm/Analysis/ConstantFolding.h"
32 #include "llvm/Analysis/InstructionSimplify.h"
33 #include "llvm/IR/CFG.h"
34 #include "llvm/IR/DataLayout.h"
35 #include "llvm/IR/Function.h"
36 #include "llvm/IR/IRBuilder.h"
37 #include "llvm/IR/Instructions.h"
38 #include "llvm/IR/IntrinsicInst.h"
39 #include "llvm/IR/Module.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Analysis/TargetLibraryInfo.h"
42 #include "llvm/Transforms/NaCl.h"
43 #include "llvm/Transforms/Utils/Local.h"
44 #include <map>
45 #include <vector>
46
47 #include "llvm/Support/raw_ostream.h"
48
49 #ifdef NDEBUG
50 #undef assert
51 #define assert(x) { if (!(x)) report_fatal_error(#x); }
52 #endif
53
54 using namespace llvm;
55
56 namespace {
57
58 struct PhiBlockChange {
59 BasicBlock *DD, *SwitchBB, *NewBB;
60 };
61
62 typedef SmallVector<Value*, 2> ChunksVec;
63 typedef std::map<Value*, ChunksVec> SplitsMap;
64
65 typedef SmallVector<PHINode *, 8> PHIVec;
66 typedef SmallVector<Instruction *, 8> DeadVec;
67
68 // This is a ModulePass because the pass recreates functions in
69 // order to expand i64 arguments to pairs of i32s.
70 class ExpandI64 : public ModulePass {
71 bool Changed;
72 const DataLayout *DL;
73 Module *TheModule;
74
75 SplitsMap Splits; // old illegal value to new insts
76 PHIVec Phis;
77 std::vector<PhiBlockChange> PhiBlockChanges;
78
79 // If the function has an illegal return or argument, create a legal version
80 void ensureLegalFunc(Function *F);
81
82 // If a function is illegal, remove it
83 void removeIllegalFunc(Function *F);
84
85 // splits an illegal instruction into 32-bit chunks. We do
86 // not yet have the values yet, as they depend on other
87 // splits, so store the parts in Splits, for FinalizeInst.
88 bool splitInst(Instruction *I);
89
90 // For an illegal value, returns the split out chunks
91 // representing the low and high parts, that splitInst
92 // generated.
93 // The value can also be a constant, in which case we just
94 // split it, or a function argument, in which case we
95 // map to the proper legalized new arguments
96 //
97 // @param AllowUnreachable It is possible for phi nodes
98 // to refer to unreachable blocks,
99 // which our traversal never
100 // reaches; this flag lets us
101 // ignore those - otherwise,
102 // not finding chunks is fatal
103 ChunksVec getChunks(Value *V, bool AllowUnreachable=false);
104
105 Function *Add, *Sub, *Mul, *SDiv, *UDiv, *SRem, *URem, *LShr, *AShr, *Shl, * GetHigh, *SetHigh, *FtoILow, *FtoIHigh, *DtoILow, *DtoIHigh, *SItoF, *UItoF, *SI toD, *UItoD, *BItoD, *BDtoILow, *BDtoIHigh;
106
107 void ensureFuncs();
108 unsigned getNumChunks(Type *T);
109
110 public:
111 static char ID;
112 ExpandI64() : ModulePass(ID) {
113 initializeExpandI64Pass(*PassRegistry::getPassRegistry());
114
115 Add = Sub = Mul = SDiv = UDiv = SRem = URem = LShr = AShr = Shl = GetHigh = SetHigh = NULL;
116 }
117
118 virtual bool runOnModule(Module &M);
119 };
120 }
121
122 char ExpandI64::ID = 0;
123 INITIALIZE_PASS(ExpandI64, "expand-illegal-ints",
124 "Expand and lower illegal >i32 operations into 32-bit chunks",
125 false, false)
126
127 // Utilities
128
129 static Instruction *CopyDebug(Instruction *NewInst, Instruction *Original) {
130 NewInst->setDebugLoc(Original->getDebugLoc());
131 return NewInst;
132 }
133
134 static bool isIllegal(Type *T) {
135 return T->isIntegerTy() && T->getIntegerBitWidth() > 32;
136 }
137
138 static FunctionType *getLegalizedFunctionType(FunctionType *FT) {
139 SmallVector<Type*, 0> ArgTypes; // XXX
140 int Num = FT->getNumParams();
141 for (int i = 0; i < Num; i++) {
142 Type *T = FT->getParamType(i);
143 if (!isIllegal(T)) {
144 ArgTypes.push_back(T);
145 } else {
146 Type *i32 = Type::getInt32Ty(FT->getContext());
147 ArgTypes.push_back(i32);
148 ArgTypes.push_back(i32);
149 }
150 }
151 Type *RT = FT->getReturnType();
152 Type *NewRT;
153 if (!isIllegal(RT)) {
154 NewRT = RT;
155 } else {
156 NewRT = Type::getInt32Ty(FT->getContext());
157 }
158 return FunctionType::get(NewRT, ArgTypes, false);
159 }
160
161 // Implementation of ExpandI64
162
163 static bool okToRemainIllegal(Function *F) {
164 StringRef Name = F->getName();
165 if (Name == "llvm.dbg.value") return true;
166
167 // XXX EMSCRIPTEN: These take an i64 immediate argument; since they're not
168 // real instructions, we don't need to legalize them.
169 if (Name == "llvm.lifetime.start") return true;
170 if (Name == "llvm.lifetime.end") return true;
171 if (Name == "llvm.invariant.start") return true;
172 if (Name == "llvm.invariant.end") return true;
173
174 return false;
175 }
176
177 unsigned ExpandI64::getNumChunks(Type *T) {
178 unsigned Num = DL->getTypeSizeInBits(T);
179 return (Num + 31) / 32;
180 }
181
182 static bool isLegalFunctionType(FunctionType *FT) {
183 if (isIllegal(FT->getReturnType())) {
184 return false;
185 }
186
187 int Num = FT->getNumParams();
188 for (int i = 0; i < Num; i++) {
189 if (isIllegal(FT->getParamType(i))) {
190 return false;
191 }
192 }
193
194 return true;
195 }
196
197 static bool isLegalInstruction(const Instruction *I) {
198 if (isIllegal(I->getType())) {
199 return false;
200 }
201
202 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
203 if (isIllegal(I->getOperand(i)->getType())) {
204 return false;
205 }
206 }
207
208 return true;
209 }
210
211 // We can't use RecreateFunction because we need to handle
212 // function and argument attributes specially.
213 static Function *RecreateFunctionLegalized(Function *F, FunctionType *NewType) {
214 Function *NewFunc = Function::Create(NewType, F->getLinkage());
215
216 AttributeSet Attrs = F->getAttributes();
217 AttributeSet FnAttrs = Attrs.getFnAttributes();
218
219 // Legalizing the return value is done by storing part of the value into
220 // static storage. Subsequent analysis will see this as a memory access,
221 // so we can no longer claim to be readonly or readnone.
222 if (isIllegal(F->getReturnType())) {
223 FnAttrs = FnAttrs.removeAttribute(F->getContext(),
224 AttributeSet::FunctionIndex,
225 Attribute::ReadOnly);
226 FnAttrs = FnAttrs.removeAttribute(F->getContext(),
227 AttributeSet::FunctionIndex,
228 Attribute::ReadNone);
229 }
230
231 NewFunc->addAttributes(AttributeSet::FunctionIndex, FnAttrs);
232 NewFunc->addAttributes(AttributeSet::ReturnIndex, Attrs.getRetAttributes());
233 Function::arg_iterator AI = F->arg_begin();
234
235 // We need to recreate the attribute set, with the right indexes
236 AttributeSet NewAttrs;
237 unsigned NumArgs = F->arg_size();
238 for (unsigned i = 1, j = 1; i < NumArgs+1; i++, j++, AI++) {
239 if (isIllegal(AI->getType())) {
240 j++;
241 continue;
242 }
243 if (!Attrs.hasAttributes(i)) continue;
244 AttributeSet ParamAttrs = Attrs.getParamAttributes(i);
245 AttrBuilder AB;
246 unsigned NumSlots = ParamAttrs.getNumSlots();
247 for (unsigned k = 0; k < NumSlots; k++) {
248 for (AttributeSet::iterator I = ParamAttrs.begin(k), E = ParamAttrs.end(k) ; I != E; I++) {
249 AB.addAttribute(*I);
250 }
251 }
252 NewFunc->addAttributes(j, AttributeSet::get(F->getContext(), j, AB));
253 }
254
255 F->getParent()->getFunctionList().insert(F, NewFunc);
256 NewFunc->takeName(F);
257 NewFunc->getBasicBlockList().splice(NewFunc->begin(),
258 F->getBasicBlockList());
259 F->replaceAllUsesWith(
260 ConstantExpr::getBitCast(NewFunc,
261 F->getFunctionType()->getPointerTo()));
262 return NewFunc;
263 }
264
265 void ExpandI64::ensureLegalFunc(Function *F) {
266 if (okToRemainIllegal(F)) return;
267
268 FunctionType *FT = F->getFunctionType();
269 if (isLegalFunctionType(FT)) return;
270
271 Changed = true;
272 Function *NF = RecreateFunctionLegalized(F, getLegalizedFunctionType(FT));
273 std::string Name = NF->getName();
274 if (strncmp(Name.c_str(), "llvm.", 5) == 0) {
275 // this is an intrinsic, and we are changing its signature, which will annoy LLVM, so rename
276 const size_t len = Name.size();
277 SmallString<256> NewName;
278 NewName.resize(len);
279 for (unsigned i = 0; i < len; i++) {
280 NewName[i] = Name[i] != '.' ? Name[i] : '_';
281 }
282 NF->setName(Twine(NewName));
283 }
284
285 // Move and update arguments
286 for (Function::arg_iterator Arg = F->arg_begin(), E = F->arg_end(), NewArg = N F->arg_begin();
287 Arg != E; ++Arg) {
288 if (Arg->getType() == NewArg->getType()) {
289 NewArg->takeName(Arg);
290 Arg->replaceAllUsesWith(NewArg);
291 NewArg++;
292 } else {
293 // This was legalized
294 ChunksVec &Chunks = Splits[&*Arg];
295 int Num = getNumChunks(Arg->getType());
296 assert(Num == 2);
297 for (int i = 0; i < Num; i++) {
298 Chunks.push_back(&*NewArg);
299 if (NewArg->hasName()) Chunks[i]->setName(NewArg->getName() + "$" + utos tr(i));
300 NewArg++;
301 }
302 }
303 }
304 }
305
306 void ExpandI64::removeIllegalFunc(Function *F) {
307 if (okToRemainIllegal(F)) return;
308
309 FunctionType *FT = F->getFunctionType();
310 if (!isLegalFunctionType(FT)) {
311 F->eraseFromParent();
312 }
313 }
314
315 bool ExpandI64::splitInst(Instruction *I) {
316 Type *i32 = Type::getInt32Ty(I->getContext());
317 Type *i32P = i32->getPointerTo();
318 Type *i64 = Type::getInt64Ty(I->getContext());
319 Value *Zero = Constant::getNullValue(i32);
320
321 ChunksVec &Chunks = Splits[I];
322
323 switch (I->getOpcode()) {
324 case Instruction::GetElementPtr: {
325 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
326 SmallVector<Value*, 2> NewOps;
327 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i) {
328 Value *Op = I->getOperand(i);
329 if (isIllegal(Op->getType())) {
330 // Truncate the operand down to one chunk.
331 NewOps.push_back(getChunks(Op)[0]);
332 } else {
333 NewOps.push_back(Op);
334 }
335 }
336 Value *NewGEP = CopyDebug(GetElementPtrInst::Create(GEP->getPointerOperand ()->getType(), GEP->getPointerOperand(), NewOps, "", GEP), GEP);
337 Chunks.push_back(NewGEP);
338 I->replaceAllUsesWith(NewGEP);
339 break;
340 }
341 case Instruction::SExt: {
342 ChunksVec InputChunks;
343 Value *Op = I->getOperand(0);
344 if (isIllegal(Op->getType())) {
345 InputChunks = getChunks(Op);
346 } else {
347 InputChunks.push_back(Op);
348 }
349
350 for (unsigned i = 0, e = InputChunks.size(); i != e; ++i) {
351 Value *Input = InputChunks[i];
352
353 Type *T = Input->getType();
354 Value *Chunk;
355 if (T->getIntegerBitWidth() < 32) {
356 Chunk = CopyDebug(new SExtInst(Input, i32, "", I), I);
357 } else {
358 assert(T->getIntegerBitWidth() == 32);
359 Chunk = Input;
360 }
361 Chunks.push_back(Chunk);
362 }
363
364 Instruction *Check = CopyDebug(new ICmpInst(I, ICmpInst::ICMP_SLT, Chunks. back(), Zero), I);
365 int Num = getNumChunks(I->getType());
366 for (int i = Chunks.size(); i < Num; i++) {
367 Instruction *High = CopyDebug(new SExtInst(Check, i32, "", I), I);
368 Chunks.push_back(High);
369 }
370 break;
371 }
372 case Instruction::PtrToInt:
373 case Instruction::ZExt: {
374 Value *Op = I->getOperand(0);
375 ChunksVec InputChunks;
376 if (I->getOpcode() == Instruction::PtrToInt) {
377 InputChunks.push_back(CopyDebug(new PtrToIntInst(Op, i32, "", I), I));
378 } else if (isIllegal(Op->getType())) {
379 InputChunks = getChunks(Op);
380 } else {
381 InputChunks.push_back(Op);
382 }
383
384 for (unsigned i = 0, e = InputChunks.size(); i != e; ++i) {
385 Value *Input = InputChunks[i];
386 Type *T = Input->getType();
387
388 Value *Chunk;
389 if (T->getIntegerBitWidth() < 32) {
390 Chunk = CopyDebug(new ZExtInst(Input, i32, "", I), I);
391 } else {
392 assert(T->getIntegerBitWidth() == 32);
393 Chunk = Input;
394 }
395 Chunks.push_back(Chunk);
396 }
397
398 int Num = getNumChunks(I->getType());
399 for (int i = Chunks.size(); i < Num; i++) {
400 Chunks.push_back(Zero);
401 }
402 break;
403 }
404 case Instruction::IntToPtr:
405 case Instruction::Trunc: {
406 unsigned Num = getNumChunks(I->getType());
407 unsigned NumBits = DL->getTypeSizeInBits(I->getType());
408 ChunksVec InputChunks = getChunks(I->getOperand(0));
409 for (unsigned i = 0; i < Num; i++) {
410 Value *Input = InputChunks[i];
411
412 Value *Chunk;
413 if (NumBits < 32) {
414 Chunk = CopyDebug(new TruncInst(Input, IntegerType::get(I->getContext( ), NumBits), "", I), I);
415 NumBits = 0;
416 } else {
417 Chunk = Input;
418 NumBits -= 32;
419 }
420 if (I->getOpcode() == Instruction::IntToPtr) {
421 assert(i == 0);
422 Chunk = CopyDebug(new IntToPtrInst(Chunk, I->getType(), "", I), I);
423 }
424 Chunks.push_back(Chunk);
425 }
426 if (!isIllegal(I->getType())) {
427 assert(Chunks.size() == 1);
428 I->replaceAllUsesWith(Chunks[0]);
429 }
430 break;
431 }
432 case Instruction::Load: {
433 LoadInst *LI = cast<LoadInst>(I);
434 Instruction *AI = CopyDebug(new PtrToIntInst(LI->getPointerOperand(), i32, "", I), I);
435 int Num = getNumChunks(I->getType());
436 for (int i = 0; i < Num; i++) {
437 Instruction *Add = i == 0 ? AI : CopyDebug(BinaryOperator::Create(Instru ction::Add, AI, ConstantInt::get(i32, 4*i), "", I), I);
438 Instruction *Ptr = CopyDebug(new IntToPtrInst(Add, i32P, "", I), I);
439 LoadInst *Chunk = new LoadInst(Ptr, "", I); CopyDebug(Chunk, I);
440 Chunk->setAlignment(MinAlign(LI->getAlignment() == 0 ?
441 DL->getABITypeAlignment(LI->getType()) :
442 LI->getAlignment(),
443 4*i));
444 Chunk->setVolatile(LI->isVolatile());
445 Chunk->setOrdering(LI->getOrdering());
446 Chunk->setSynchScope(LI->getSynchScope());
447 Chunks.push_back(Chunk);
448 }
449 break;
450 }
451 case Instruction::Store: {
452 StoreInst *SI = cast<StoreInst>(I);
453 Instruction *AI = CopyDebug(new PtrToIntInst(SI->getPointerOperand(), i32, "", I), I);
454 ChunksVec InputChunks = getChunks(SI->getValueOperand());
455 int Num = InputChunks.size();
456 for (int i = 0; i < Num; i++) {
457 Instruction *Add = i == 0 ? AI : CopyDebug(BinaryOperator::Create(Instru ction::Add, AI, ConstantInt::get(i32, 4*i), "", I), I);
458 Instruction *Ptr = CopyDebug(new IntToPtrInst(Add, i32P, "", I), I);
459 StoreInst *Chunk = new StoreInst(InputChunks[i], Ptr, I);
460 Chunk->setAlignment(MinAlign(SI->getAlignment() == 0 ?
461 DL->getABITypeAlignment(SI->getValueOpe rand()->getType()) :
462 SI->getAlignment(),
463 4*i));
464 Chunk->setVolatile(SI->isVolatile());
465 Chunk->setOrdering(SI->getOrdering());
466 Chunk->setSynchScope(SI->getSynchScope());
467 CopyDebug(Chunk, I);
468 }
469 break;
470 }
471 case Instruction::Ret: {
472 assert(I->getOperand(0)->getType() == i64);
473 ChunksVec InputChunks = getChunks(I->getOperand(0));
474 ensureFuncs();
475 SmallVector<Value *, 1> Args;
476 Args.push_back(InputChunks[1]);
477 CopyDebug(CallInst::Create(SetHigh, Args, "", I), I);
478 CopyDebug(ReturnInst::Create(I->getContext(), InputChunks[0], I), I);
479 break;
480 }
481 case Instruction::Add:
482 case Instruction::Sub:
483 case Instruction::Mul:
484 case Instruction::SDiv:
485 case Instruction::UDiv:
486 case Instruction::SRem:
487 case Instruction::URem:
488 case Instruction::LShr:
489 case Instruction::AShr:
490 case Instruction::Shl: {
491 ChunksVec LeftChunks = getChunks(I->getOperand(0));
492 ChunksVec RightChunks = getChunks(I->getOperand(1));
493 unsigned Num = getNumChunks(I->getType());
494 if (Num == 2) {
495 ensureFuncs();
496 Value *Low = NULL, *High = NULL;
497 Function *F = NULL;
498 switch (I->getOpcode()) {
499 case Instruction::Add: F = Add; break;
500 case Instruction::Sub: F = Sub; break;
501 case Instruction::Mul: F = Mul; break;
502 case Instruction::SDiv: F = SDiv; break;
503 case Instruction::UDiv: F = UDiv; break;
504 case Instruction::SRem: F = SRem; break;
505 case Instruction::URem: F = URem; break;
506 case Instruction::AShr: F = AShr; break;
507 case Instruction::LShr: {
508 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
509 unsigned Shifts = CI->getZExtValue();
510 if (Shifts == 32) {
511 Low = LeftChunks[1];
512 High = Zero;
513 break;
514 }
515 }
516 F = LShr;
517 break;
518 }
519 case Instruction::Shl: {
520 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
521 const APInt &Shifts = CI->getValue();
522 if (Shifts == 32) {
523 Low = Zero;
524 High = LeftChunks[0];
525 break;
526 }
527 }
528 F = Shl;
529 break;
530 }
531 default: assert(0);
532 }
533 if (F) {
534 // use a library call, no special optimization was found
535 SmallVector<Value *, 4> Args;
536 Args.push_back(LeftChunks[0]);
537 Args.push_back(LeftChunks[1]);
538 Args.push_back(RightChunks[0]);
539 Args.push_back(RightChunks[1]);
540 Low = CopyDebug(CallInst::Create(F, Args, "", I), I);
541 High = CopyDebug(CallInst::Create(GetHigh, "", I), I);
542 }
543 Chunks.push_back(Low);
544 Chunks.push_back(High);
545 } else {
546 // more than 64 bits. handle simple shifts for lshr and shl
547 assert(I->getOpcode() == Instruction::LShr || I->getOpcode() == Instruct ion::AShr || I->getOpcode() == Instruction::Shl);
548 ConstantInt *CI = cast<ConstantInt>(I->getOperand(1));
549 unsigned Shifts = CI->getZExtValue();
550 unsigned Fraction = Shifts % 32;
551 Constant *Frac = ConstantInt::get(i32, Fraction);
552 Constant *Comp = ConstantInt::get(i32, 32 - Fraction);
553 Instruction::BinaryOps Opcode, Reverse;
554 unsigned ShiftChunks, Dir;
555 Value *TopFiller = Zero;
556 if (I->getOpcode() == Instruction::Shl) {
557 Opcode = Instruction::Shl;
558 Reverse = Instruction::LShr;
559 ShiftChunks = -(Shifts/32);
560 Dir = -1;
561 } else {
562 Opcode = Instruction::LShr;
563 Reverse = Instruction::Shl;
564 ShiftChunks = Shifts/32;
565 Dir = 1;
566 if (I->getOpcode() == Instruction::AShr) {
567 Value *Cond = CopyDebug(new ICmpInst(I, ICmpInst::ICMP_SLT, LeftChun ks[LeftChunks.size()-1], Zero), I);
568 TopFiller = CopyDebug(SelectInst::Create(Cond, ConstantInt::get(i32, -1), Zero, "", I), I);
569 }
570 }
571 for (unsigned i = 0; i < Num; i++) {
572 Value *L;
573 if (i + ShiftChunks < LeftChunks.size()) {
574 L = LeftChunks[i + ShiftChunks];
575 } else {
576 L = Zero;
577 }
578
579 Value *H;
580 if (i + ShiftChunks + Dir < LeftChunks.size()) {
581 H = LeftChunks[i + ShiftChunks + Dir];
582 } else {
583 H = TopFiller;
584 }
585
586 // shifted the fractional amount
587 if (Frac != Zero && L != Zero) {
588 if (Fraction == 32) {
589 L = Zero;
590 } else {
591 L = CopyDebug(BinaryOperator::Create(Opcode, L, Frac, "", I), I);
592 }
593 }
594 // shifted the complement-fractional amount to the other side
595 if (Comp != Zero && H != Zero) {
596 if (Fraction == 0) {
597 H = TopFiller;
598 } else {
599 H = CopyDebug(BinaryOperator::Create(Reverse, H, Comp, "", I), I);
600 }
601 }
602
603 // Or the parts together. Since we may have zero, try to fold it away.
604 if (Value *V = SimplifyBinOp(Instruction::Or, L, H, *DL)) {
605 Chunks.push_back(V);
606 } else {
607 Chunks.push_back(CopyDebug(BinaryOperator::Create(Instruction::Or, L , H, "", I), I));
608 }
609 }
610 }
611 break;
612 }
613 case Instruction::ICmp: {
614 ICmpInst *CE = cast<ICmpInst>(I);
615 ICmpInst::Predicate Pred = CE->getPredicate();
616 ChunksVec LeftChunks = getChunks(I->getOperand(0));
617 ChunksVec RightChunks = getChunks(I->getOperand(1));
618 switch (Pred) {
619 case ICmpInst::ICMP_EQ:
620 case ICmpInst::ICMP_NE: {
621 ICmpInst::Predicate PartPred; // the predicate to use on each of the p arts
622 llvm::Instruction::BinaryOps CombineOp; // the predicate to use to com bine the subcomparisons
623 int Num = LeftChunks.size();
624 if (Pred == ICmpInst::ICMP_EQ) {
625 PartPred = ICmpInst::ICMP_EQ;
626 CombineOp = Instruction::And;
627 } else {
628 PartPred = ICmpInst::ICMP_NE;
629 CombineOp = Instruction::Or;
630 }
631 // first combine 0 and 1. then combine that with 2, etc.
632 Value *Combined = NULL;
633 for (int i = 0; i < Num; i++) {
634 Value *Cmp = CopyDebug(new ICmpInst(I, PartPred, LeftChunks[i], Righ tChunks[i]), I);
635 Combined = !Combined ? Cmp : CopyDebug(BinaryOperator::Create(Combin eOp, Combined, Cmp, "", I), I);
636 }
637 I->replaceAllUsesWith(Combined);
638 break;
639 }
640 case ICmpInst::ICMP_ULT:
641 case ICmpInst::ICMP_SLT:
642 case ICmpInst::ICMP_UGT:
643 case ICmpInst::ICMP_SGT:
644 case ICmpInst::ICMP_ULE:
645 case ICmpInst::ICMP_SLE:
646 case ICmpInst::ICMP_UGE:
647 case ICmpInst::ICMP_SGE: {
648 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
649 if (CI->getZExtValue() == 0 && Pred == ICmpInst::ICMP_SLT) {
650 // strict < 0 is easy to do, even on non-i64, just the sign bit ma tters
651 Instruction *NewInst = new ICmpInst(I, ICmpInst::ICMP_SLT, LeftChu nks[LeftChunks.size()-1], Zero);
652 CopyDebug(NewInst, I);
653 I->replaceAllUsesWith(NewInst);
654 return true;
655 }
656 }
657 Type *T = I->getOperand(0)->getType();
658 assert(T->isIntegerTy() && T->getIntegerBitWidth() % 32 == 0);
659 int NumChunks = getNumChunks(T);
660 assert(NumChunks >= 2);
661 ICmpInst::Predicate StrictPred = Pred;
662 ICmpInst::Predicate UnsignedPred = Pred;
663 switch (Pred) {
664 case ICmpInst::ICMP_ULE: StrictPred = ICmpInst::ICMP_ULT; break;
665 case ICmpInst::ICMP_UGE: StrictPred = ICmpInst::ICMP_UGT; break;
666 case ICmpInst::ICMP_SLE: StrictPred = ICmpInst::ICMP_SLT; UnsignedPr ed = ICmpInst::ICMP_ULE; break;
667 case ICmpInst::ICMP_SGE: StrictPred = ICmpInst::ICMP_SGT; UnsignedPr ed = ICmpInst::ICMP_UGE; break;
668 case ICmpInst::ICMP_SLT: UnsignedPr ed = ICmpInst::ICMP_ULT; break;
669 case ICmpInst::ICMP_SGT: UnsignedPr ed = ICmpInst::ICMP_UGT; break;
670 case ICmpInst::ICMP_ULT: break;
671 case ICmpInst::ICMP_UGT: break;
672 default: assert(0);
673 }
674 // general pattern is
675 // a,b,c < A,B,C => c < C || (c == C && b < B) || (c == C && b = = B && a < A)
676 Instruction *Final = CopyDebug(new ICmpInst(I, StrictPred, LeftChunks[ NumChunks-1], RightChunks[NumChunks-1]), I);
677 for (int i = NumChunks-2; i >= 0; i--) {
678 Instruction *Curr = CopyDebug(new ICmpInst(I, UnsignedPred, LeftChun ks[i], RightChunks[i]), I);
679 for (int j = NumChunks-1; j > i; j--) {
680 Instruction *Temp = CopyDebug(new ICmpInst(I, ICmpInst::ICMP_EQ, L eftChunks[j], RightChunks[j]), I);
681 Curr = CopyDebug(BinaryOperator::Create(Instruction::And, Temp, Cu rr, "", I), I);
682 }
683 Final = CopyDebug(BinaryOperator::Create(Instruction::Or, Final, Cur r, "", I), I);
684 }
685 I->replaceAllUsesWith(Final);
686 break;
687 }
688 default: assert(0);
689 }
690 break;
691 }
692 case Instruction::Select: {
693 SelectInst *SI = cast<SelectInst>(I);
694 Value *Cond = SI->getCondition();
695 ChunksVec TrueChunks = getChunks(SI->getTrueValue());
696 ChunksVec FalseChunks = getChunks(SI->getFalseValue());
697 unsigned Num = getNumChunks(I->getType());
698 for (unsigned i = 0; i < Num; i++) {
699 Instruction *Part = CopyDebug(SelectInst::Create(Cond, TrueChunks[i], Fa lseChunks[i], "", I), I);
700 Chunks.push_back(Part);
701 }
702 break;
703 }
704 case Instruction::PHI: {
705 PHINode *Parent = cast<PHINode>(I);
706 int Num = getNumChunks(I->getType());
707 int PhiNum = Parent->getNumIncomingValues();
708 for (int i = 0; i < Num; i++) {
709 Instruction *P = CopyDebug(PHINode::Create(i32, PhiNum, "", I), I);
710 Chunks.push_back(P);
711 }
712 // PHI node operands may not be translated yet; we'll handle them at the e nd.
713 Phis.push_back(Parent);
714 break;
715 }
716 case Instruction::And:
717 case Instruction::Or:
718 case Instruction::Xor: {
719 BinaryOperator *BO = cast<BinaryOperator>(I);
720 ChunksVec LeftChunks = getChunks(BO->getOperand(0));
721 ChunksVec RightChunks = getChunks(BO->getOperand(1));
722 int Num = getNumChunks(BO->getType());
723 for (int i = 0; i < Num; i++) {
724 // If there's a constant operand, it's likely enough that one of the
725 // chunks will be a trivial operation, so it's worth calling
726 // SimplifyBinOp here.
727 if (Value *V = SimplifyBinOp(BO->getOpcode(), LeftChunks[i], RightChunks [i], *DL)) {
728 Chunks.push_back(V);
729 } else {
730 Chunks.push_back(CopyDebug(BinaryOperator::Create(BO->getOpcode(), Lef tChunks[i], RightChunks[i], "", BO), BO));
731 }
732 }
733 break;
734 }
735 case Instruction::Call: {
736 CallInst *CI = cast<CallInst>(I);
737 Function *F = CI->getCalledFunction();
738 if (F) {
739 assert(okToRemainIllegal(F));
740 return false;
741 }
742 Value *CV = CI->getCalledValue();
743 FunctionType *OFT = NULL;
744 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(CV)) {
745 assert(CE);
746 assert(CE->getOpcode() == Instruction::BitCast);
747 OFT = cast<FunctionType>(cast<PointerType>(CE->getType())->getElementTyp e());
748 Constant *C = CE->getOperand(0);
749 CV = ConstantExpr::getBitCast(C, getLegalizedFunctionType(OFT)->getPoint erTo());
750 } else {
751 // this is a function pointer call
752 OFT = cast<FunctionType>(cast<PointerType>(CV->getType())->getElementTyp e());
753 // we need to add a bitcast
754 CV = new BitCastInst(CV, getLegalizedFunctionType(OFT)->getPointerTo(), "", I);
755 }
756 // create a call with space for legal args
757 SmallVector<Value *, 0> Args; // XXX
758 int Num = OFT->getNumParams();
759 for (int i = 0; i < Num; i++) {
760 Type *T = OFT->getParamType(i);
761 if (!isIllegal(T)) {
762 Args.push_back(CI->getArgOperand(i));
763 } else {
764 assert(T == i64);
765 ChunksVec ArgChunks = getChunks(CI->getArgOperand(i));
766 Args.push_back(ArgChunks[0]);
767 Args.push_back(ArgChunks[1]);
768 }
769 }
770 Instruction *L = CopyDebug(CallInst::Create(CV, Args, "", I), I);
771 Instruction *H = NULL;
772 // legalize return value as well, if necessary
773 if (isIllegal(I->getType())) {
774 assert(I->getType() == i64);
775 ensureFuncs();
776 H = CopyDebug(CallInst::Create(GetHigh, "", I), I);
777 Chunks.push_back(L);
778 Chunks.push_back(H);
779 } else {
780 I->replaceAllUsesWith(L);
781 }
782 break;
783 }
784 case Instruction::FPToUI:
785 case Instruction::FPToSI: {
786 assert(I->getType() == i64);
787 ensureFuncs();
788 SmallVector<Value *, 1> Args;
789 Value *Input = I->getOperand(0);
790 Args.push_back(Input);
791 Instruction *L, *H;
792 if (Input->getType()->isFloatTy()) {
793 L = CopyDebug(CallInst::Create(FtoILow, Args, "", I), I);
794 H = CopyDebug(CallInst::Create(FtoIHigh, Args, "", I), I);
795 } else {
796 L = CopyDebug(CallInst::Create(DtoILow, Args, "", I), I);
797 H = CopyDebug(CallInst::Create(DtoIHigh, Args, "", I), I);
798 }
799 Chunks.push_back(L);
800 Chunks.push_back(H);
801 break;
802 }
803 case Instruction::BitCast: {
804 if (I->getType() == Type::getDoubleTy(TheModule->getContext())) {
805 // fall through to itofp
806 } else if (I->getOperand(0)->getType() == Type::getDoubleTy(TheModule->get Context())) {
807 // double to i64
808 assert(I->getType() == i64);
809 ensureFuncs();
810 SmallVector<Value *, 1> Args;
811 Args.push_back(I->getOperand(0));
812 Instruction *L = CopyDebug(CallInst::Create(BDtoILow, Args, "", I), I);
813 Instruction *H = CopyDebug(CallInst::Create(BDtoIHigh, Args, "", I), I);
814 Chunks.push_back(L);
815 Chunks.push_back(H);
816 break;
817 } else if (isa<VectorType>(I->getOperand(0)->getType()) && !isa<VectorType >(I->getType())) {
818 unsigned NumElts = getNumChunks(I->getType());
819 VectorType *IVTy = VectorType::get(i32, NumElts);
820 Instruction *B = CopyDebug(new BitCastInst(I->getOperand(0), IVTy, "", I), I);
821 for (unsigned i = 0; i < NumElts; ++i) {
822 Constant *Idx = ConstantInt::get(i32, i);
823 Instruction *Ext = CopyDebug(ExtractElementInst::Create(B, Idx, "" , I), I);
824 Chunks.push_back(Ext);
825 }
826 break;
827 } else {
828 // no-op bitcast
829 assert(I->getType() == I->getOperand(0)->getType());
830 Chunks = getChunks(I->getOperand(0));
831 break;
832 }
833 }
834 case Instruction::SIToFP:
835 case Instruction::UIToFP: {
836 assert(I->getOperand(0)->getType() == i64);
837 ensureFuncs();
838 ChunksVec InputChunks = getChunks(I->getOperand(0));
839 Function *F;
840 switch (I->getOpcode()) {
841 case Instruction::SIToFP: F = I->getType() == Type::getDoubleTy(TheModul e->getContext()) ? SItoD : SItoF; break;
842 case Instruction::UIToFP: F = I->getType() == Type::getDoubleTy(TheModul e->getContext()) ? UItoD : UItoF; break;
843 case Instruction::BitCast: {
844 assert(I->getType() == Type::getDoubleTy(TheModule->getContext()));
845 F = BItoD;
846 break;
847 }
848 default: assert(0);
849 }
850 Instruction *D = CopyDebug(CallInst::Create(F, InputChunks, "", I), I);
851 I->replaceAllUsesWith(D);
852 break;
853 }
854 case Instruction::Switch: {
855 assert(I->getOperand(0)->getType() == i64);
856 ChunksVec InputChunks = getChunks(I->getOperand(0));
857
858 // do a switch on the lower 32 bits, into a different basic block for each target, then do a branch in each of those on the high 32 bits
859 SwitchInst* SI = cast<SwitchInst>(I);
860 BasicBlock *DD = SI->getDefaultDest();
861 BasicBlock *SwitchBB = I->getParent();
862 Function *F = SwitchBB->getParent();
863
864 unsigned NumItems = SI->getNumCases();
865 SwitchInst *LowSI = SwitchInst::Create(InputChunks[0], DD, NumItems, I); / / same default destination: if lower bits do not match, go straight to default
866 CopyDebug(LowSI, I);
867
868 typedef std::pair<uint32_t, BasicBlock*> Pair;
869 typedef std::vector<Pair> Vec; // vector of pairs of high 32 bits, basic b lock
870 typedef std::map<uint32_t, Vec> Map; // maps low 32 bits to their Vec info
871 Map Groups; // (as two 64-bit values in the switc h may share their lower bits)
872
873 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
874 BasicBlock *BB = i.getCaseSuccessor();
875 uint64_t Bits = i.getCaseValue()->getZExtValue();
876 uint32_t LowBits = (uint32_t)Bits;
877 uint32_t HighBits = (uint32_t)(Bits >> 32);
878 Vec& V = Groups[LowBits];
879 V.push_back(Pair(HighBits, BB));
880 }
881
882 unsigned Counter = 0;
883 BasicBlock *InsertPoint = SwitchBB;
884
885 for (Map::iterator GI = Groups.begin(); GI != Groups.end(); GI++) {
886 uint32_t LowBits = GI->first;
887 Vec &V = GI->second;
888
889 BasicBlock *NewBB = BasicBlock::Create(F->getContext(), "switch64_" + ut ostr(Counter++), F);
890 NewBB->moveAfter(InsertPoint);
891 InsertPoint = NewBB;
892 LowSI->addCase(cast<ConstantInt>(ConstantInt::get(i32, LowBits)), NewBB) ;
893
894 /*if (V.size() == 1) {
895 // just one option, create a branch
896 Instruction *CheckHigh = CopyDebug(new ICmpInst(*NewBB, ICmpInst::ICMP _EQ, InputChunks[1], ConstantInt::get(i32, V[0]->first)), I);
897 Split.ToFix.push_back(CheckHigh);
898 CopyDebug(BranchInst::Create(V[0]->second, DD, CheckHigh, NewBB), I);
899 } else {*/
900
901 // multiple options, create a switch - we could also optimize and make a n icmp/branch if just one, as in commented code above
902 SwitchInst *HighSI = SwitchInst::Create(InputChunks[1], DD, V.size(), Ne wBB); // same default destination: if lower bits do not match, go straight to de fault
903 for (unsigned i = 0; i < V.size(); i++) {
904 BasicBlock *BB = V[i].second;
905 HighSI->addCase(cast<ConstantInt>(ConstantInt::get(i32, V[i].first)), BB);
906 // fix phis, we used to go SwitchBB->BB, but now go SwitchBB->NewBB->B B, so we look like we arrived from NewBB. Replace the phi from the
907 // now unneeded SwitchBB to the new BB
908 // We cannot do this here right now, as phis we encounter may be in th e middle of processing (empty), so we queue these.
909 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
910 PHINode *Phi = dyn_cast<PHINode>(I);
911 if (!Phi) break;
912 PhiBlockChange Change;
913 Change.DD = BB;
914 Change.SwitchBB = SwitchBB;
915 Change.NewBB = NewBB;
916 PhiBlockChanges.push_back(Change);
917 break; // we saw a phi on this BB, and pushed a Change
918 }
919 }
920
921 // We used to go SwitchBB->DD, but now go SwitchBB->NewBB->DD, fix that like with BB above. However here we do not replace,
922 // as the switch BB is still possible to arrive from - we can arrive at the default if either the lower bits were wrong (we
923 // arrive from the switchBB) or from the NewBB if the high bits were wro ng.
924 PhiBlockChange Change;
925 Change.DD = DD;
926 Change.SwitchBB = SwitchBB;
927 Change.NewBB = NewBB;
928 PhiBlockChanges.push_back(Change);
929 }
930 break;
931 }
932 default: {
933 I->dump();
934 assert(0 && "some i64 thing we can't legalize yet");
935 }
936 }
937
938 return true;
939 }
940
941 ChunksVec ExpandI64::getChunks(Value *V, bool AllowUnreachable) {
942 assert(isIllegal(V->getType()));
943
944 unsigned Num = getNumChunks(V->getType());
945 Type *i32 = Type::getInt32Ty(V->getContext());
946
947 if (isa<UndefValue>(V))
948 return ChunksVec(Num, UndefValue::get(i32));
949
950 if (Constant *C = dyn_cast<Constant>(V)) {
951 ChunksVec Chunks;
952 for (unsigned i = 0; i < Num; i++) {
953 Constant *Count = ConstantInt::get(C->getType(), i * 32);
954 Constant *NewC = ConstantExpr::getTrunc(ConstantExpr::getLShr(C, Count), i 32);
955 TargetLibraryInfo *TLI = 0; // TODO
956 if (ConstantExpr *NewCE = dyn_cast<ConstantExpr>(NewC)) {
957 if (Constant *FoldedC = ConstantFoldConstantExpression(NewCE, *DL, TLI)) {
958 NewC = FoldedC;
959 }
960 }
961
962 Chunks.push_back(NewC);
963 }
964 return Chunks;
965 }
966
967 if (Splits.find(V) == Splits.end()) {
968 if (AllowUnreachable)
969 return ChunksVec(Num, UndefValue::get(i32));
970 errs() << *V << "\n";
971 report_fatal_error("could not find chunks for illegal value");
972 }
973 assert(Splits[V].size() == Num);
974 return Splits[V];
975 }
976
977 void ExpandI64::ensureFuncs() {
978 if (Add != NULL) return;
979
980 Type *i32 = Type::getInt32Ty(TheModule->getContext());
981
982 SmallVector<Type*, 4> FourArgTypes;
983 FourArgTypes.push_back(i32);
984 FourArgTypes.push_back(i32);
985 FourArgTypes.push_back(i32);
986 FourArgTypes.push_back(i32);
987 FunctionType *FourFunc = FunctionType::get(i32, FourArgTypes, false);
988
989 Add = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
990 "i64Add", TheModule);
991 Sub = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
992 "i64Subtract", TheModule);
993 Mul = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
994 "__muldi3", TheModule);
995 SDiv = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
996 "__divdi3", TheModule);
997 UDiv = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
998 "__udivdi3", TheModule);
999 SRem = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
1000 "__remdi3", TheModule);
1001 URem = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
1002 "__uremdi3", TheModule);
1003 LShr = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
1004 "bitshift64Lshr", TheModule);
1005 AShr = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
1006 "bitshift64Ashr", TheModule);
1007 Shl = Function::Create(FourFunc, GlobalValue::ExternalLinkage,
1008 "bitshift64Shl", TheModule);
1009
1010 if (!(GetHigh = TheModule->getFunction("getHigh32"))) {
1011 SmallVector<Type*, 0> GetHighArgTypes;
1012 FunctionType *GetHighFunc = FunctionType::get(i32, GetHighArgTypes, false);
1013 GetHigh = Function::Create(GetHighFunc, GlobalValue::ExternalLinkage,
1014 "getHigh32", TheModule);
1015 }
1016
1017 Type *V = Type::getVoidTy(TheModule->getContext());
1018
1019 SmallVector<Type*, 1> SetHighArgTypes;
1020 SetHighArgTypes.push_back(i32);
1021 FunctionType *SetHighFunc = FunctionType::get(V, SetHighArgTypes, false);
1022 SetHigh = Function::Create(SetHighFunc, GlobalValue::ExternalLinkage,
1023 "setHigh32", TheModule);
1024
1025 Type *Double = Type::getDoubleTy(TheModule->getContext());
1026 Type *Float = Type::getFloatTy(TheModule->getContext());
1027
1028 SmallVector<Type*, 1> FtoITypes;
1029 FtoITypes.push_back(Float);
1030 FunctionType *FtoIFunc = FunctionType::get(i32, FtoITypes, false);
1031
1032 SmallVector<Type*, 1> DtoITypes;
1033 DtoITypes.push_back(Double);
1034 FunctionType *DtoIFunc = FunctionType::get(i32, DtoITypes, false);
1035
1036 FtoILow = Function::Create(FtoIFunc, GlobalValue::ExternalLinkage,
1037 "FtoILow", TheModule);
1038 FtoIHigh = Function::Create(FtoIFunc, GlobalValue::ExternalLinkage,
1039 "FtoIHigh", TheModule);
1040 DtoILow = Function::Create(DtoIFunc, GlobalValue::ExternalLinkage,
1041 "DtoILow", TheModule);
1042 DtoIHigh = Function::Create(DtoIFunc, GlobalValue::ExternalLinkage,
1043 "DtoIHigh", TheModule);
1044 BDtoILow = Function::Create(DtoIFunc, GlobalValue::ExternalLinkage,
1045 "BDtoILow", TheModule);
1046 BDtoIHigh = Function::Create(DtoIFunc, GlobalValue::ExternalLinkage,
1047 "BDtoIHigh", TheModule);
1048
1049 SmallVector<Type*, 2> ItoTypes;
1050 ItoTypes.push_back(i32);
1051 ItoTypes.push_back(i32);
1052
1053 FunctionType *ItoFFunc = FunctionType::get(Float, ItoTypes, false);
1054 SItoF = Function::Create(ItoFFunc, GlobalValue::ExternalLinkage,
1055 "SItoF", TheModule);
1056 UItoF = Function::Create(ItoFFunc, GlobalValue::ExternalLinkage,
1057 "UItoF", TheModule);
1058
1059 FunctionType *ItoDFunc = FunctionType::get(Double, ItoTypes, false);
1060 SItoD = Function::Create(ItoDFunc, GlobalValue::ExternalLinkage,
1061 "SItoD", TheModule);
1062 UItoD = Function::Create(ItoDFunc, GlobalValue::ExternalLinkage,
1063 "UItoD", TheModule);
1064
1065 BItoD = Function::Create(ItoDFunc, GlobalValue::ExternalLinkage,
1066 "BItoD", TheModule);
1067 }
1068
1069 bool ExpandI64::runOnModule(Module &M) {
1070 TheModule = &M;
1071 DL = &M.getDataLayout();
1072 Splits.clear();
1073 Changed = false;
1074
1075 // pre pass - legalize functions
1076 for (Module::iterator Iter = M.begin(), E = M.end(); Iter != E; ) {
1077 Function *Func = Iter++;
1078 ensureLegalFunc(Func);
1079 }
1080
1081 // first pass - split
1082 DeadVec Dead;
1083 for (Module::iterator Iter = M.begin(), E = M.end(); Iter != E; ++Iter) {
1084 Function *Func = Iter;
1085 if (Func->isDeclaration()) {
1086 continue;
1087 }
1088
1089 // Walk the body of the function. We use reverse postorder so that we visit
1090 // all operands of an instruction before the instruction itself. The
1091 // exception to this is PHI nodes, which we put on a list and handle below.
1092 ReversePostOrderTraversal<Function*> RPOT(Func);
1093 for (ReversePostOrderTraversal<Function*>::rpo_iterator RI = RPOT.begin(),
1094 RE = RPOT.end(); RI != RE; ++RI) {
1095 BasicBlock *BB = *RI;
1096 for (BasicBlock::iterator Iter = BB->begin(), E = BB->end();
1097 Iter != E; ) {
1098 Instruction *I = Iter++;
1099 if (!isLegalInstruction(I)) {
1100 if (splitInst(I)) {
1101 Changed = true;
1102 Dead.push_back(I);
1103 }
1104 }
1105 }
1106 }
1107
1108 // Fix up PHI node operands.
1109 while (!Phis.empty()) {
1110 PHINode *PN = Phis.pop_back_val();
1111 ChunksVec OutputChunks = getChunks(PN);
1112 for (unsigned j = 0, je = PN->getNumIncomingValues(); j != je; ++j) {
1113 Value *Op = PN->getIncomingValue(j);
1114 ChunksVec InputChunks = getChunks(Op, true);
1115 for (unsigned k = 0, ke = OutputChunks.size(); k != ke; ++k) {
1116 PHINode *NewPN = cast<PHINode>(OutputChunks[k]);
1117 NewPN->addIncoming(InputChunks[k], PN->getIncomingBlock(j));
1118 }
1119 }
1120 PN->dropAllReferences();
1121 }
1122
1123 // Delete instructions which were replaced. We do this after the full walk
1124 // of the instructions so that all uses are replaced first.
1125 while (!Dead.empty()) {
1126 Instruction *D = Dead.pop_back_val();
1127 D->eraseFromParent();
1128 }
1129
1130 // Apply basic block changes to phis, now that phis are all processed (and i llegal phis erased)
1131 for (unsigned i = 0; i < PhiBlockChanges.size(); i++) {
1132 PhiBlockChange &Change = PhiBlockChanges[i];
1133 for (BasicBlock::iterator I = Change.DD->begin(); I != Change.DD->end(); + +I) {
1134 PHINode *Phi = dyn_cast<PHINode>(I);
1135 if (!Phi) break;
1136 int Index = Phi->getBasicBlockIndex(Change.SwitchBB);
1137 assert(Index >= 0);
1138 Phi->addIncoming(Phi->getIncomingValue(Index), Change.NewBB);
1139 }
1140 }
1141 PhiBlockChanges.clear();
1142
1143 // We only visited blocks found by a DFS walk from the entry, so we haven't
1144 // visited any unreachable blocks, and they may still contain illegal
1145 // instructions at this point. Being unreachable, they can simply be deleted .
1146 removeUnreachableBlocks(*Func);
1147 }
1148
1149 // post pass - clean up illegal functions that were legalized. We do this
1150 // after the full walk of the functions so that all uses are replaced first.
1151 for (Module::iterator Iter = M.begin(), E = M.end(); Iter != E; ) {
1152 Function *Func = Iter++;
1153 removeIllegalFunc(Func);
1154 }
1155
1156 return Changed;
1157 }
1158
1159 ModulePass *llvm::createExpandI64Pass() {
1160 return new ExpandI64();
1161 }
OLDNEW
« no previous file with comments | « lib/Transforms/NaCl/CMakeLists.txt ('k') | lib/Transforms/NaCl/ExpandInsertExtractElement.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698