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