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