LLVM API Documentation
00001 //===- CodeExtractor.cpp - Pull code region into a new function -----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the interface to tear out a code region, such as an 00011 // individual loop or a parallel section, into a new function, replacing it with 00012 // a call to the new function. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "llvm/Transforms/Utils/FunctionUtils.h" 00017 #include "llvm/Constants.h" 00018 #include "llvm/DerivedTypes.h" 00019 #include "llvm/Instructions.h" 00020 #include "llvm/Intrinsics.h" 00021 #include "llvm/Module.h" 00022 #include "llvm/Pass.h" 00023 #include "llvm/Analysis/Dominators.h" 00024 #include "llvm/Analysis/LoopInfo.h" 00025 #include "llvm/Analysis/Verifier.h" 00026 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00027 #include "llvm/Support/CommandLine.h" 00028 #include "llvm/Support/Debug.h" 00029 #include "llvm/ADT/StringExtras.h" 00030 #include <algorithm> 00031 #include <set> 00032 using namespace llvm; 00033 00034 // Provide a command-line option to aggregate function arguments into a struct 00035 // for functions produced by the code extrator. This is useful when converting 00036 // extracted functions to pthread-based code, as only one argument (void*) can 00037 // be passed in to pthread_create(). 00038 static cl::opt<bool> 00039 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 00040 cl::desc("Aggregate arguments to code-extracted functions")); 00041 00042 namespace { 00043 class CodeExtractor { 00044 typedef std::vector<Value*> Values; 00045 std::set<BasicBlock*> BlocksToExtract; 00046 DominatorSet *DS; 00047 bool AggregateArgs; 00048 unsigned NumExitBlocks; 00049 const Type *RetTy; 00050 public: 00051 CodeExtractor(DominatorSet *ds = 0, bool AggArgs = false) 00052 : DS(ds), AggregateArgs(AggArgs||AggregateArgsOpt), NumExitBlocks(~0U) {} 00053 00054 Function *ExtractCodeRegion(const std::vector<BasicBlock*> &code); 00055 00056 bool isEligible(const std::vector<BasicBlock*> &code); 00057 00058 private: 00059 /// definedInRegion - Return true if the specified value is defined in the 00060 /// extracted region. 00061 bool definedInRegion(Value *V) const { 00062 if (Instruction *I = dyn_cast<Instruction>(V)) 00063 if (BlocksToExtract.count(I->getParent())) 00064 return true; 00065 return false; 00066 } 00067 00068 /// definedInCaller - Return true if the specified value is defined in the 00069 /// function being code extracted, but not in the region being extracted. 00070 /// These values must be passed in as live-ins to the function. 00071 bool definedInCaller(Value *V) const { 00072 if (isa<Argument>(V)) return true; 00073 if (Instruction *I = dyn_cast<Instruction>(V)) 00074 if (!BlocksToExtract.count(I->getParent())) 00075 return true; 00076 return false; 00077 } 00078 00079 void severSplitPHINodes(BasicBlock *&Header); 00080 void splitReturnBlocks(); 00081 void findInputsOutputs(Values &inputs, Values &outputs); 00082 00083 Function *constructFunction(const Values &inputs, 00084 const Values &outputs, 00085 BasicBlock *header, 00086 BasicBlock *newRootNode, BasicBlock *newHeader, 00087 Function *oldFunction, Module *M); 00088 00089 void moveCodeToFunction(Function *newFunction); 00090 00091 void emitCallAndSwitchStatement(Function *newFunction, 00092 BasicBlock *newHeader, 00093 Values &inputs, 00094 Values &outputs); 00095 00096 }; 00097 } 00098 00099 /// severSplitPHINodes - If a PHI node has multiple inputs from outside of the 00100 /// region, we need to split the entry block of the region so that the PHI node 00101 /// is easier to deal with. 00102 void CodeExtractor::severSplitPHINodes(BasicBlock *&Header) { 00103 bool HasPredsFromRegion = false; 00104 unsigned NumPredsOutsideRegion = 0; 00105 00106 if (Header != &Header->getParent()->front()) { 00107 PHINode *PN = dyn_cast<PHINode>(Header->begin()); 00108 if (!PN) return; // No PHI nodes. 00109 00110 // If the header node contains any PHI nodes, check to see if there is more 00111 // than one entry from outside the region. If so, we need to sever the 00112 // header block into two. 00113 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00114 if (BlocksToExtract.count(PN->getIncomingBlock(i))) 00115 HasPredsFromRegion = true; 00116 else 00117 ++NumPredsOutsideRegion; 00118 00119 // If there is one (or fewer) predecessor from outside the region, we don't 00120 // need to do anything special. 00121 if (NumPredsOutsideRegion <= 1) return; 00122 } 00123 00124 // Otherwise, we need to split the header block into two pieces: one 00125 // containing PHI nodes merging values from outside of the region, and a 00126 // second that contains all of the code for the block and merges back any 00127 // incoming values from inside of the region. 00128 BasicBlock::iterator AfterPHIs = Header->begin(); 00129 while (isa<PHINode>(AfterPHIs)) ++AfterPHIs; 00130 BasicBlock *NewBB = Header->splitBasicBlock(AfterPHIs, 00131 Header->getName()+".ce"); 00132 00133 // We only want to code extract the second block now, and it becomes the new 00134 // header of the region. 00135 BasicBlock *OldPred = Header; 00136 BlocksToExtract.erase(OldPred); 00137 BlocksToExtract.insert(NewBB); 00138 Header = NewBB; 00139 00140 // Okay, update dominator sets. The blocks that dominate the new one are the 00141 // blocks that dominate TIBB plus the new block itself. 00142 if (DS) { 00143 DominatorSet::DomSetType DomSet = DS->getDominators(OldPred); 00144 DomSet.insert(NewBB); // A block always dominates itself. 00145 DS->addBasicBlock(NewBB, DomSet); 00146 00147 // Additionally, NewBB dominates all blocks in the function that are 00148 // dominated by OldPred. 00149 Function *F = Header->getParent(); 00150 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00151 if (DS->properlyDominates(OldPred, I)) 00152 DS->addDominator(I, NewBB); 00153 } 00154 00155 // Okay, now we need to adjust the PHI nodes and any branches from within the 00156 // region to go to the new header block instead of the old header block. 00157 if (HasPredsFromRegion) { 00158 PHINode *PN = cast<PHINode>(OldPred->begin()); 00159 // Loop over all of the predecessors of OldPred that are in the region, 00160 // changing them to branch to NewBB instead. 00161 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00162 if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 00163 TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator(); 00164 TI->replaceUsesOfWith(OldPred, NewBB); 00165 } 00166 00167 // Okay, everthing within the region is now branching to the right block, we 00168 // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 00169 for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 00170 PHINode *PN = cast<PHINode>(AfterPHIs); 00171 // Create a new PHI node in the new region, which has an incoming value 00172 // from OldPred of PN. 00173 PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".ce", 00174 NewBB->begin()); 00175 NewPN->addIncoming(PN, OldPred); 00176 00177 // Loop over all of the incoming value in PN, moving them to NewPN if they 00178 // are from the extracted region. 00179 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 00180 if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 00181 NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 00182 PN->removeIncomingValue(i); 00183 --i; 00184 } 00185 } 00186 } 00187 } 00188 } 00189 00190 void CodeExtractor::splitReturnBlocks() { 00191 for (std::set<BasicBlock*>::iterator I = BlocksToExtract.begin(), 00192 E = BlocksToExtract.end(); I != E; ++I) 00193 if (ReturnInst *RI = dyn_cast<ReturnInst>((*I)->getTerminator())) 00194 (*I)->splitBasicBlock(RI, (*I)->getName()+".ret"); 00195 } 00196 00197 // findInputsOutputs - Find inputs to, outputs from the code region. 00198 // 00199 void CodeExtractor::findInputsOutputs(Values &inputs, Values &outputs) { 00200 std::set<BasicBlock*> ExitBlocks; 00201 for (std::set<BasicBlock*>::const_iterator ci = BlocksToExtract.begin(), 00202 ce = BlocksToExtract.end(); ci != ce; ++ci) { 00203 BasicBlock *BB = *ci; 00204 00205 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 00206 // If a used value is defined outside the region, it's an input. If an 00207 // instruction is used outside the region, it's an output. 00208 for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) 00209 if (definedInCaller(*O)) 00210 inputs.push_back(*O); 00211 00212 // Consider uses of this instruction (outputs). 00213 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00214 UI != E; ++UI) 00215 if (!definedInRegion(*UI)) { 00216 outputs.push_back(I); 00217 break; 00218 } 00219 } // for: insts 00220 00221 // Keep track of the exit blocks from the region. 00222 TerminatorInst *TI = BB->getTerminator(); 00223 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 00224 if (!BlocksToExtract.count(TI->getSuccessor(i))) 00225 ExitBlocks.insert(TI->getSuccessor(i)); 00226 } // for: basic blocks 00227 00228 NumExitBlocks = ExitBlocks.size(); 00229 00230 // Eliminate duplicates. 00231 std::sort(inputs.begin(), inputs.end()); 00232 inputs.erase(std::unique(inputs.begin(), inputs.end()), inputs.end()); 00233 std::sort(outputs.begin(), outputs.end()); 00234 outputs.erase(std::unique(outputs.begin(), outputs.end()), outputs.end()); 00235 } 00236 00237 /// constructFunction - make a function based on inputs and outputs, as follows: 00238 /// f(in0, ..., inN, out0, ..., outN) 00239 /// 00240 Function *CodeExtractor::constructFunction(const Values &inputs, 00241 const Values &outputs, 00242 BasicBlock *header, 00243 BasicBlock *newRootNode, 00244 BasicBlock *newHeader, 00245 Function *oldFunction, 00246 Module *M) { 00247 DEBUG(std::cerr << "inputs: " << inputs.size() << "\n"); 00248 DEBUG(std::cerr << "outputs: " << outputs.size() << "\n"); 00249 00250 // This function returns unsigned, outputs will go back by reference. 00251 switch (NumExitBlocks) { 00252 case 0: 00253 case 1: RetTy = Type::VoidTy; break; 00254 case 2: RetTy = Type::BoolTy; break; 00255 default: RetTy = Type::UShortTy; break; 00256 } 00257 00258 std::vector<const Type*> paramTy; 00259 00260 // Add the types of the input values to the function's argument list 00261 for (Values::const_iterator i = inputs.begin(), 00262 e = inputs.end(); i != e; ++i) { 00263 const Value *value = *i; 00264 DEBUG(std::cerr << "value used in func: " << *value << "\n"); 00265 paramTy.push_back(value->getType()); 00266 } 00267 00268 // Add the types of the output values to the function's argument list. 00269 for (Values::const_iterator I = outputs.begin(), E = outputs.end(); 00270 I != E; ++I) { 00271 DEBUG(std::cerr << "instr used in func: " << **I << "\n"); 00272 if (AggregateArgs) 00273 paramTy.push_back((*I)->getType()); 00274 else 00275 paramTy.push_back(PointerType::get((*I)->getType())); 00276 } 00277 00278 DEBUG(std::cerr << "Function type: " << *RetTy << " f("); 00279 DEBUG(for (std::vector<const Type*>::iterator i = paramTy.begin(), 00280 e = paramTy.end(); i != e; ++i) std::cerr << **i << ", "); 00281 DEBUG(std::cerr << ")\n"); 00282 00283 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 00284 PointerType *StructPtr = PointerType::get(StructType::get(paramTy)); 00285 paramTy.clear(); 00286 paramTy.push_back(StructPtr); 00287 } 00288 const FunctionType *funcType = FunctionType::get(RetTy, paramTy, false); 00289 00290 // Create the new function 00291 Function *newFunction = new Function(funcType, 00292 GlobalValue::InternalLinkage, 00293 oldFunction->getName() + "_" + 00294 header->getName(), M); 00295 newFunction->getBasicBlockList().push_back(newRootNode); 00296 00297 // Create an iterator to name all of the arguments we inserted. 00298 Function::aiterator AI = newFunction->abegin(); 00299 00300 // Rewrite all users of the inputs in the extracted region to use the 00301 // arguments (or appropriate addressing into struct) instead. 00302 for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 00303 Value *RewriteVal; 00304 if (AggregateArgs) { 00305 std::vector<Value*> Indices; 00306 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00307 Indices.push_back(ConstantUInt::get(Type::UIntTy, i)); 00308 std::string GEPname = "gep_" + inputs[i]->getName(); 00309 TerminatorInst *TI = newFunction->begin()->getTerminator(); 00310 GetElementPtrInst *GEP = new GetElementPtrInst(AI, Indices, GEPname, TI); 00311 RewriteVal = new LoadInst(GEP, "load" + GEPname, TI); 00312 } else 00313 RewriteVal = AI++; 00314 00315 std::vector<User*> Users(inputs[i]->use_begin(), inputs[i]->use_end()); 00316 for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); 00317 use != useE; ++use) 00318 if (Instruction* inst = dyn_cast<Instruction>(*use)) 00319 if (BlocksToExtract.count(inst->getParent())) 00320 inst->replaceUsesOfWith(inputs[i], RewriteVal); 00321 } 00322 00323 // Set names for input and output arguments. 00324 if (!AggregateArgs) { 00325 AI = newFunction->abegin(); 00326 for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 00327 AI->setName(inputs[i]->getName()); 00328 for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 00329 AI->setName(outputs[i]->getName()+".out"); 00330 } 00331 00332 // Rewrite branches to basic blocks outside of the loop to new dummy blocks 00333 // within the new function. This must be done before we lose track of which 00334 // blocks were originally in the code region. 00335 std::vector<User*> Users(header->use_begin(), header->use_end()); 00336 for (unsigned i = 0, e = Users.size(); i != e; ++i) 00337 // The BasicBlock which contains the branch is not in the region 00338 // modify the branch target to a new block 00339 if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i])) 00340 if (!BlocksToExtract.count(TI->getParent()) && 00341 TI->getParent()->getParent() == oldFunction) 00342 TI->replaceUsesOfWith(header, newHeader); 00343 00344 return newFunction; 00345 } 00346 00347 /// emitCallAndSwitchStatement - This method sets up the caller side by adding 00348 /// the call instruction, splitting any PHI nodes in the header block as 00349 /// necessary. 00350 void CodeExtractor:: 00351 emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, 00352 Values &inputs, Values &outputs) { 00353 // Emit a call to the new function, passing in: *pointer to struct (if 00354 // aggregating parameters), or plan inputs and allocated memory for outputs 00355 std::vector<Value*> params, StructValues, ReloadOutputs; 00356 00357 // Add inputs as params, or to be filled into the struct 00358 for (Values::iterator i = inputs.begin(), e = inputs.end(); i != e; ++i) 00359 if (AggregateArgs) 00360 StructValues.push_back(*i); 00361 else 00362 params.push_back(*i); 00363 00364 // Create allocas for the outputs 00365 for (Values::iterator i = outputs.begin(), e = outputs.end(); i != e; ++i) { 00366 if (AggregateArgs) { 00367 StructValues.push_back(*i); 00368 } else { 00369 AllocaInst *alloca = 00370 new AllocaInst((*i)->getType(), 0, (*i)->getName()+".loc", 00371 codeReplacer->getParent()->begin()->begin()); 00372 ReloadOutputs.push_back(alloca); 00373 params.push_back(alloca); 00374 } 00375 } 00376 00377 AllocaInst *Struct = 0; 00378 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 00379 std::vector<const Type*> ArgTypes; 00380 for (Values::iterator v = StructValues.begin(), 00381 ve = StructValues.end(); v != ve; ++v) 00382 ArgTypes.push_back((*v)->getType()); 00383 00384 // Allocate a struct at the beginning of this function 00385 Type *StructArgTy = StructType::get(ArgTypes); 00386 Struct = 00387 new AllocaInst(StructArgTy, 0, "structArg", 00388 codeReplacer->getParent()->begin()->begin()); 00389 params.push_back(Struct); 00390 00391 for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 00392 std::vector<Value*> Indices; 00393 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00394 Indices.push_back(ConstantUInt::get(Type::UIntTy, i)); 00395 GetElementPtrInst *GEP = 00396 new GetElementPtrInst(Struct, Indices, 00397 "gep_" + StructValues[i]->getName()); 00398 codeReplacer->getInstList().push_back(GEP); 00399 StoreInst *SI = new StoreInst(StructValues[i], GEP); 00400 codeReplacer->getInstList().push_back(SI); 00401 } 00402 } 00403 00404 // Emit the call to the function 00405 CallInst *call = new CallInst(newFunction, params, 00406 NumExitBlocks > 1 ? "targetBlock" : ""); 00407 codeReplacer->getInstList().push_back(call); 00408 00409 Function::aiterator OutputArgBegin = newFunction->abegin(); 00410 unsigned FirstOut = inputs.size(); 00411 if (!AggregateArgs) 00412 std::advance(OutputArgBegin, inputs.size()); 00413 00414 // Reload the outputs passed in by reference 00415 for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 00416 Value *Output = 0; 00417 if (AggregateArgs) { 00418 std::vector<Value*> Indices; 00419 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00420 Indices.push_back(ConstantUInt::get(Type::UIntTy, FirstOut + i)); 00421 GetElementPtrInst *GEP 00422 = new GetElementPtrInst(Struct, Indices, 00423 "gep_reload_" + outputs[i]->getName()); 00424 codeReplacer->getInstList().push_back(GEP); 00425 Output = GEP; 00426 } else { 00427 Output = ReloadOutputs[i]; 00428 } 00429 LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload"); 00430 codeReplacer->getInstList().push_back(load); 00431 std::vector<User*> Users(outputs[i]->use_begin(), outputs[i]->use_end()); 00432 for (unsigned u = 0, e = Users.size(); u != e; ++u) { 00433 Instruction *inst = cast<Instruction>(Users[u]); 00434 if (!BlocksToExtract.count(inst->getParent())) 00435 inst->replaceUsesOfWith(outputs[i], load); 00436 } 00437 } 00438 00439 // Now we can emit a switch statement using the call as a value. 00440 SwitchInst *TheSwitch = 00441 new SwitchInst(ConstantUInt::getNullValue(Type::UShortTy), 00442 codeReplacer, codeReplacer); 00443 00444 // Since there may be multiple exits from the original region, make the new 00445 // function return an unsigned, switch on that number. This loop iterates 00446 // over all of the blocks in the extracted region, updating any terminator 00447 // instructions in the to-be-extracted region that branch to blocks that are 00448 // not in the region to be extracted. 00449 std::map<BasicBlock*, BasicBlock*> ExitBlockMap; 00450 00451 unsigned switchVal = 0; 00452 for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 00453 e = BlocksToExtract.end(); i != e; ++i) { 00454 TerminatorInst *TI = (*i)->getTerminator(); 00455 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 00456 if (!BlocksToExtract.count(TI->getSuccessor(i))) { 00457 BasicBlock *OldTarget = TI->getSuccessor(i); 00458 // add a new basic block which returns the appropriate value 00459 BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 00460 if (!NewTarget) { 00461 // If we don't already have an exit stub for this non-extracted 00462 // destination, create one now! 00463 NewTarget = new BasicBlock(OldTarget->getName() + ".exitStub", 00464 newFunction); 00465 unsigned SuccNum = switchVal++; 00466 00467 Value *brVal = 0; 00468 switch (NumExitBlocks) { 00469 case 0: 00470 case 1: break; // No value needed. 00471 case 2: // Conditional branch, return a bool 00472 brVal = SuccNum ? ConstantBool::False : ConstantBool::True; 00473 break; 00474 default: 00475 brVal = ConstantUInt::get(Type::UShortTy, SuccNum); 00476 break; 00477 } 00478 00479 ReturnInst *NTRet = new ReturnInst(brVal, NewTarget); 00480 00481 // Update the switch instruction. 00482 TheSwitch->addCase(ConstantUInt::get(Type::UShortTy, SuccNum), 00483 OldTarget); 00484 00485 // Restore values just before we exit 00486 Function::aiterator OAI = OutputArgBegin; 00487 for (unsigned out = 0, e = outputs.size(); out != e; ++out) { 00488 // For an invoke, the normal destination is the only one that is 00489 // dominated by the result of the invocation 00490 BasicBlock *DefBlock = cast<Instruction>(outputs[out])->getParent(); 00491 00492 bool DominatesDef = true; 00493 00494 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(outputs[out])) { 00495 DefBlock = Invoke->getNormalDest(); 00496 00497 // Make sure we are looking at the original successor block, not 00498 // at a newly inserted exit block, which won't be in the dominator 00499 // info. 00500 for (std::map<BasicBlock*, BasicBlock*>::iterator I = 00501 ExitBlockMap.begin(), E = ExitBlockMap.end(); I != E; ++I) 00502 if (DefBlock == I->second) { 00503 DefBlock = I->first; 00504 break; 00505 } 00506 00507 // In the extract block case, if the block we are extracting ends 00508 // with an invoke instruction, make sure that we don't emit a 00509 // store of the invoke value for the unwind block. 00510 if (!DS && DefBlock != OldTarget) 00511 DominatesDef = false; 00512 } 00513 00514 if (DS) 00515 DominatesDef = DS->dominates(DefBlock, OldTarget); 00516 00517 if (DominatesDef) { 00518 if (AggregateArgs) { 00519 std::vector<Value*> Indices; 00520 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00521 Indices.push_back(ConstantUInt::get(Type::UIntTy,FirstOut+out)); 00522 GetElementPtrInst *GEP = 00523 new GetElementPtrInst(OAI, Indices, 00524 "gep_" + outputs[out]->getName(), 00525 NTRet); 00526 new StoreInst(outputs[out], GEP, NTRet); 00527 } else { 00528 new StoreInst(outputs[out], OAI, NTRet); 00529 } 00530 } 00531 // Advance output iterator even if we don't emit a store 00532 if (!AggregateArgs) ++OAI; 00533 } 00534 } 00535 00536 // rewrite the original branch instruction with this new target 00537 TI->setSuccessor(i, NewTarget); 00538 } 00539 } 00540 00541 // Now that we've done the deed, simplify the switch instruction. 00542 const Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 00543 switch (NumExitBlocks) { 00544 case 0: 00545 // There are no successors (the block containing the switch itself), which 00546 // means that previously this was the last part of the function, and hence 00547 // this should be rewritten as a `ret' 00548 00549 // Check if the function should return a value 00550 if (OldFnRetTy == Type::VoidTy) { 00551 new ReturnInst(0, TheSwitch); // Return void 00552 } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 00553 // return what we have 00554 new ReturnInst(TheSwitch->getCondition(), TheSwitch); 00555 } else { 00556 // Otherwise we must have code extracted an unwind or something, just 00557 // return whatever we want. 00558 new ReturnInst(Constant::getNullValue(OldFnRetTy), TheSwitch); 00559 } 00560 00561 TheSwitch->getParent()->getInstList().erase(TheSwitch); 00562 break; 00563 case 1: 00564 // Only a single destination, change the switch into an unconditional 00565 // branch. 00566 new BranchInst(TheSwitch->getSuccessor(1), TheSwitch); 00567 TheSwitch->getParent()->getInstList().erase(TheSwitch); 00568 break; 00569 case 2: 00570 new BranchInst(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 00571 call, TheSwitch); 00572 TheSwitch->getParent()->getInstList().erase(TheSwitch); 00573 break; 00574 default: 00575 // Otherwise, make the default destination of the switch instruction be one 00576 // of the other successors. 00577 TheSwitch->setOperand(0, call); 00578 TheSwitch->setSuccessor(0, TheSwitch->getSuccessor(NumExitBlocks)); 00579 TheSwitch->removeCase(NumExitBlocks); // Remove redundant case 00580 break; 00581 } 00582 } 00583 00584 void CodeExtractor::moveCodeToFunction(Function *newFunction) { 00585 Function *oldFunc = (*BlocksToExtract.begin())->getParent(); 00586 Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 00587 Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 00588 00589 for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 00590 e = BlocksToExtract.end(); i != e; ++i) { 00591 // Delete the basic block from the old function, and the list of blocks 00592 oldBlocks.remove(*i); 00593 00594 // Insert this basic block into the new function 00595 newBlocks.push_back(*i); 00596 } 00597 } 00598 00599 /// ExtractRegion - Removes a loop from a function, replaces it with a call to 00600 /// new function. Returns pointer to the new function. 00601 /// 00602 /// algorithm: 00603 /// 00604 /// find inputs and outputs for the region 00605 /// 00606 /// for inputs: add to function as args, map input instr* to arg# 00607 /// for outputs: add allocas for scalars, 00608 /// add to func as args, map output instr* to arg# 00609 /// 00610 /// rewrite func to use argument #s instead of instr* 00611 /// 00612 /// for each scalar output in the function: at every exit, store intermediate 00613 /// computed result back into memory. 00614 /// 00615 Function *CodeExtractor:: 00616 ExtractCodeRegion(const std::vector<BasicBlock*> &code) { 00617 if (!isEligible(code)) 00618 return 0; 00619 00620 // 1) Find inputs, outputs 00621 // 2) Construct new function 00622 // * Add allocas for defs, pass as args by reference 00623 // * Pass in uses as args 00624 // 3) Move code region, add call instr to func 00625 // 00626 BlocksToExtract.insert(code.begin(), code.end()); 00627 00628 Values inputs, outputs; 00629 00630 // Assumption: this is a single-entry code region, and the header is the first 00631 // block in the region. 00632 BasicBlock *header = code[0]; 00633 00634 for (unsigned i = 1, e = code.size(); i != e; ++i) 00635 for (pred_iterator PI = pred_begin(code[i]), E = pred_end(code[i]); 00636 PI != E; ++PI) 00637 assert(BlocksToExtract.count(*PI) && 00638 "No blocks in this region may have entries from outside the region" 00639 " except for the first block!"); 00640 00641 // If we have to split PHI nodes or the entry block, do so now. 00642 severSplitPHINodes(header); 00643 00644 // If we have any return instructions in the region, split those blocks so 00645 // that the return is not in the region. 00646 splitReturnBlocks(); 00647 00648 Function *oldFunction = header->getParent(); 00649 00650 // This takes place of the original loop 00651 BasicBlock *codeReplacer = new BasicBlock("codeRepl", oldFunction, header); 00652 00653 // The new function needs a root node because other nodes can branch to the 00654 // head of the region, but the entry node of a function cannot have preds. 00655 BasicBlock *newFuncRoot = new BasicBlock("newFuncRoot"); 00656 newFuncRoot->getInstList().push_back(new BranchInst(header)); 00657 00658 // Find inputs to, outputs from the code region. 00659 findInputsOutputs(inputs, outputs); 00660 00661 // Construct new function based on inputs/outputs & add allocas for all defs. 00662 Function *newFunction = constructFunction(inputs, outputs, header, 00663 newFuncRoot, 00664 codeReplacer, oldFunction, 00665 oldFunction->getParent()); 00666 00667 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 00668 00669 moveCodeToFunction(newFunction); 00670 00671 // Loop over all of the PHI nodes in the header block, and change any 00672 // references to the old incoming edge to be the new incoming edge. 00673 for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 00674 PHINode *PN = cast<PHINode>(I); 00675 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00676 if (!BlocksToExtract.count(PN->getIncomingBlock(i))) 00677 PN->setIncomingBlock(i, newFuncRoot); 00678 } 00679 00680 // Look at all successors of the codeReplacer block. If any of these blocks 00681 // had PHI nodes in them, we need to update the "from" block to be the code 00682 // replacer, not the original block in the extracted region. 00683 std::vector<BasicBlock*> Succs(succ_begin(codeReplacer), 00684 succ_end(codeReplacer)); 00685 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 00686 for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) { 00687 PHINode *PN = cast<PHINode>(I); 00688 std::set<BasicBlock*> ProcessedPreds; 00689 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00690 if (BlocksToExtract.count(PN->getIncomingBlock(i))) 00691 if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second) 00692 PN->setIncomingBlock(i, codeReplacer); 00693 else { 00694 // There were multiple entries in the PHI for this block, now there 00695 // is only one, so remove the duplicated entries. 00696 PN->removeIncomingValue(i, false); 00697 --i; --e; 00698 } 00699 } 00700 00701 //std::cerr << "NEW FUNCTION: " << *newFunction; 00702 // verifyFunction(*newFunction); 00703 00704 // std::cerr << "OLD FUNCTION: " << *oldFunction; 00705 // verifyFunction(*oldFunction); 00706 00707 DEBUG(if (verifyFunction(*newFunction)) abort()); 00708 return newFunction; 00709 } 00710 00711 bool CodeExtractor::isEligible(const std::vector<BasicBlock*> &code) { 00712 // Deny code region if it contains allocas or vastarts. 00713 for (std::vector<BasicBlock*>::const_iterator BB = code.begin(), e=code.end(); 00714 BB != e; ++BB) 00715 for (BasicBlock::const_iterator I = (*BB)->begin(), Ie = (*BB)->end(); 00716 I != Ie; ++I) 00717 if (isa<AllocaInst>(*I)) 00718 return false; 00719 else if (const CallInst *CI = dyn_cast<CallInst>(I)) 00720 if (const Function *F = CI->getCalledFunction()) 00721 if (F->getIntrinsicID() == Intrinsic::vastart) 00722 return false; 00723 return true; 00724 } 00725 00726 00727 /// ExtractCodeRegion - slurp a sequence of basic blocks into a brand new 00728 /// function 00729 /// 00730 Function* llvm::ExtractCodeRegion(DominatorSet &DS, 00731 const std::vector<BasicBlock*> &code, 00732 bool AggregateArgs) { 00733 return CodeExtractor(&DS, AggregateArgs).ExtractCodeRegion(code); 00734 } 00735 00736 /// ExtractBasicBlock - slurp a natural loop into a brand new function 00737 /// 00738 Function* llvm::ExtractLoop(DominatorSet &DS, Loop *L, bool AggregateArgs) { 00739 return CodeExtractor(&DS, AggregateArgs).ExtractCodeRegion(L->getBlocks()); 00740 } 00741 00742 /// ExtractBasicBlock - slurp a basic block into a brand new function 00743 /// 00744 Function* llvm::ExtractBasicBlock(BasicBlock *BB, bool AggregateArgs) { 00745 std::vector<BasicBlock*> Blocks; 00746 Blocks.push_back(BB); 00747 return CodeExtractor(0, AggregateArgs).ExtractCodeRegion(Blocks); 00748 }