LLVM API Documentation
00001 //===- LowerPacked.cpp - Implementation of LowerPacked Transform ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by Brad Jones and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements lowering Packed datatypes into more primitive 00011 // Packed datatypes, and finally to scalar operations. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Transforms/Scalar.h" 00016 #include "llvm/Argument.h" 00017 #include "llvm/Constants.h" 00018 #include "llvm/DerivedTypes.h" 00019 #include "llvm/Function.h" 00020 #include "llvm/Instructions.h" 00021 #include "llvm/Pass.h" 00022 #include "llvm/Support/InstVisitor.h" 00023 #include "llvm/ADT/StringExtras.h" 00024 #include <algorithm> 00025 #include <map> 00026 #include <iostream> 00027 #include <functional> 00028 00029 using namespace llvm; 00030 00031 namespace { 00032 00033 /// This pass converts packed operators to an 00034 /// equivalent operations on smaller packed data, to possibly 00035 /// scalar operations. Currently it supports lowering 00036 /// to scalar operations. 00037 /// 00038 /// @brief Transforms packed instructions to simpler instructions. 00039 /// 00040 class LowerPacked : public FunctionPass, public InstVisitor<LowerPacked> { 00041 public: 00042 /// @brief Lowers packed operations to scalar operations. 00043 /// @param F The fuction to process 00044 virtual bool runOnFunction(Function &F); 00045 00046 /// @brief Lowers packed load instructions. 00047 /// @param LI the load instruction to convert 00048 void visitLoadInst(LoadInst& LI); 00049 00050 /// @brief Lowers packed store instructions. 00051 /// @param SI the store instruction to convert 00052 void visitStoreInst(StoreInst& SI); 00053 00054 /// @brief Lowers packed binary operations. 00055 /// @param BO the binary operator to convert 00056 void visitBinaryOperator(BinaryOperator& BO); 00057 00058 /// @brief Lowers packed select instructions. 00059 /// @param SELI the select operator to convert 00060 void visitSelectInst(SelectInst& SELI); 00061 00062 /// @brief Lowers packed extractelement instructions. 00063 /// @param EI the extractelement operator to convert 00064 void visitExtractElementInst(ExtractElementInst& EE); 00065 00066 /// @brief Lowers packed insertelement instructions. 00067 /// @param EI the insertelement operator to convert 00068 void visitInsertElementInst(InsertElementInst& IE); 00069 00070 /// This function asserts if the instruction is a PackedType but 00071 /// is handled by another function. 00072 /// 00073 /// @brief Asserts if PackedType instruction is not handled elsewhere. 00074 /// @param I the unhandled instruction 00075 void visitInstruction(Instruction &I) 00076 { 00077 if(isa<PackedType>(I.getType())) { 00078 std::cerr << "Unhandled Instruction with Packed ReturnType: " << 00079 I << '\n'; 00080 } 00081 } 00082 private: 00083 /// @brief Retrieves lowered values for a packed value. 00084 /// @param val the packed value 00085 /// @return the lowered values 00086 std::vector<Value*>& getValues(Value* val); 00087 00088 /// @brief Sets lowered values for a packed value. 00089 /// @param val the packed value 00090 /// @param values the corresponding lowered values 00091 void setValues(Value* val,const std::vector<Value*>& values); 00092 00093 // Data Members 00094 /// @brief whether we changed the function or not 00095 bool Changed; 00096 00097 /// @brief a map from old packed values to new smaller packed values 00098 std::map<Value*,std::vector<Value*> > packedToScalarMap; 00099 00100 /// Instructions in the source program to get rid of 00101 /// after we do a pass (the old packed instructions) 00102 std::vector<Instruction*> instrsToRemove; 00103 }; 00104 00105 RegisterOpt<LowerPacked> 00106 X("lower-packed", 00107 "lowers packed operations to operations on smaller packed datatypes"); 00108 00109 } // end namespace 00110 00111 FunctionPass *llvm::createLowerPackedPass() { return new LowerPacked(); } 00112 00113 00114 // This function sets lowered values for a corresponding 00115 // packed value. Note, in the case of a forward reference 00116 // getValues(Value*) will have already been called for 00117 // the packed parameter. This function will then replace 00118 // all references in the in the function of the "dummy" 00119 // value the previous getValues(Value*) call 00120 // returned with actual references. 00121 void LowerPacked::setValues(Value* value,const std::vector<Value*>& values) 00122 { 00123 std::map<Value*,std::vector<Value*> >::iterator it = 00124 packedToScalarMap.lower_bound(value); 00125 if (it == packedToScalarMap.end() || it->first != value) { 00126 // there was not a forward reference to this element 00127 packedToScalarMap.insert(it,std::make_pair(value,values)); 00128 } 00129 else { 00130 // replace forward declarations with actual definitions 00131 assert(it->second.size() == values.size() && 00132 "Error forward refences and actual definition differ in size"); 00133 for (unsigned i = 0, e = values.size(); i != e; ++i) { 00134 // replace and get rid of old forward references 00135 it->second[i]->replaceAllUsesWith(values[i]); 00136 delete it->second[i]; 00137 it->second[i] = values[i]; 00138 } 00139 } 00140 } 00141 00142 // This function will examine the packed value parameter 00143 // and if it is a packed constant or a forward reference 00144 // properly create the lowered values needed. Otherwise 00145 // it will simply retreive values from a 00146 // setValues(Value*,const std::vector<Value*>&) 00147 // call. Failing both of these cases, it will abort 00148 // the program. 00149 std::vector<Value*>& LowerPacked::getValues(Value* value) 00150 { 00151 assert(isa<PackedType>(value->getType()) && 00152 "Value must be PackedType"); 00153 00154 // reject further processing if this one has 00155 // already been handled 00156 std::map<Value*,std::vector<Value*> >::iterator it = 00157 packedToScalarMap.lower_bound(value); 00158 if (it != packedToScalarMap.end() && it->first == value) { 00159 return it->second; 00160 } 00161 00162 if (ConstantPacked* CP = dyn_cast<ConstantPacked>(value)) { 00163 // non-zero constant case 00164 std::vector<Value*> results; 00165 results.reserve(CP->getNumOperands()); 00166 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) { 00167 results.push_back(CP->getOperand(i)); 00168 } 00169 return packedToScalarMap.insert(it, 00170 std::make_pair(value,results))->second; 00171 } 00172 else if (ConstantAggregateZero* CAZ = 00173 dyn_cast<ConstantAggregateZero>(value)) { 00174 // zero constant 00175 const PackedType* PKT = cast<PackedType>(CAZ->getType()); 00176 std::vector<Value*> results; 00177 results.reserve(PKT->getNumElements()); 00178 00179 Constant* C = Constant::getNullValue(PKT->getElementType()); 00180 for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) { 00181 results.push_back(C); 00182 } 00183 return packedToScalarMap.insert(it, 00184 std::make_pair(value,results))->second; 00185 } 00186 else if (isa<Instruction>(value)) { 00187 // foward reference 00188 const PackedType* PKT = cast<PackedType>(value->getType()); 00189 std::vector<Value*> results; 00190 results.reserve(PKT->getNumElements()); 00191 00192 for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) { 00193 results.push_back(new Argument(PKT->getElementType())); 00194 } 00195 return packedToScalarMap.insert(it, 00196 std::make_pair(value,results))->second; 00197 } 00198 else { 00199 // we don't know what it is, and we are trying to retrieve 00200 // a value for it 00201 assert(false && "Unhandled PackedType value"); 00202 abort(); 00203 } 00204 } 00205 00206 void LowerPacked::visitLoadInst(LoadInst& LI) 00207 { 00208 // Make sure what we are dealing with is a packed type 00209 if (const PackedType* PKT = dyn_cast<PackedType>(LI.getType())) { 00210 // Initialization, Idx is needed for getelementptr needed later 00211 std::vector<Value*> Idx(2); 00212 Idx[0] = ConstantUInt::get(Type::UIntTy,0); 00213 00214 ArrayType* AT = ArrayType::get(PKT->getContainedType(0), 00215 PKT->getNumElements()); 00216 PointerType* APT = PointerType::get(AT); 00217 00218 // Cast the packed type to an array 00219 Value* array = new CastInst(LI.getPointerOperand(), 00220 APT, 00221 LI.getName() + ".a", 00222 &LI); 00223 00224 // Convert this load into num elements number of loads 00225 std::vector<Value*> values; 00226 values.reserve(PKT->getNumElements()); 00227 00228 for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) { 00229 // Calculate the second index we will need 00230 Idx[1] = ConstantUInt::get(Type::UIntTy,i); 00231 00232 // Get the pointer 00233 Value* val = new GetElementPtrInst(array, 00234 Idx, 00235 LI.getName() + 00236 ".ge." + utostr(i), 00237 &LI); 00238 00239 // generate the new load and save the result in packedToScalar map 00240 values.push_back(new LoadInst(val, 00241 LI.getName()+"."+utostr(i), 00242 LI.isVolatile(), 00243 &LI)); 00244 } 00245 00246 setValues(&LI,values); 00247 Changed = true; 00248 instrsToRemove.push_back(&LI); 00249 } 00250 } 00251 00252 void LowerPacked::visitBinaryOperator(BinaryOperator& BO) 00253 { 00254 // Make sure both operands are PackedTypes 00255 if (isa<PackedType>(BO.getOperand(0)->getType())) { 00256 std::vector<Value*>& op0Vals = getValues(BO.getOperand(0)); 00257 std::vector<Value*>& op1Vals = getValues(BO.getOperand(1)); 00258 std::vector<Value*> result; 00259 assert((op0Vals.size() == op1Vals.size()) && 00260 "The two packed operand to scalar maps must be equal in size."); 00261 00262 result.reserve(op0Vals.size()); 00263 00264 // generate the new binary op and save the result 00265 for (unsigned i = 0; i != op0Vals.size(); ++i) { 00266 result.push_back(BinaryOperator::create(BO.getOpcode(), 00267 op0Vals[i], 00268 op1Vals[i], 00269 BO.getName() + 00270 "." + utostr(i), 00271 &BO)); 00272 } 00273 00274 setValues(&BO,result); 00275 Changed = true; 00276 instrsToRemove.push_back(&BO); 00277 } 00278 } 00279 00280 void LowerPacked::visitStoreInst(StoreInst& SI) 00281 { 00282 if (const PackedType* PKT = 00283 dyn_cast<PackedType>(SI.getOperand(0)->getType())) { 00284 // We will need this for getelementptr 00285 std::vector<Value*> Idx(2); 00286 Idx[0] = ConstantUInt::get(Type::UIntTy,0); 00287 00288 ArrayType* AT = ArrayType::get(PKT->getContainedType(0), 00289 PKT->getNumElements()); 00290 PointerType* APT = PointerType::get(AT); 00291 00292 // cast the packed to an array type 00293 Value* array = new CastInst(SI.getPointerOperand(), 00294 APT, 00295 "store.ge.a.", 00296 &SI); 00297 std::vector<Value*>& values = getValues(SI.getOperand(0)); 00298 00299 assert((values.size() == PKT->getNumElements()) && 00300 "Scalar must have the same number of elements as Packed Type"); 00301 00302 for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) { 00303 // Generate the indices for getelementptr 00304 Idx[1] = ConstantUInt::get(Type::UIntTy,i); 00305 Value* val = new GetElementPtrInst(array, 00306 Idx, 00307 "store.ge." + 00308 utostr(i) + ".", 00309 &SI); 00310 new StoreInst(values[i], val, SI.isVolatile(),&SI); 00311 } 00312 00313 Changed = true; 00314 instrsToRemove.push_back(&SI); 00315 } 00316 } 00317 00318 void LowerPacked::visitSelectInst(SelectInst& SELI) 00319 { 00320 // Make sure both operands are PackedTypes 00321 if (isa<PackedType>(SELI.getType())) { 00322 std::vector<Value*>& op0Vals = getValues(SELI.getTrueValue()); 00323 std::vector<Value*>& op1Vals = getValues(SELI.getFalseValue()); 00324 std::vector<Value*> result; 00325 00326 assert((op0Vals.size() == op1Vals.size()) && 00327 "The two packed operand to scalar maps must be equal in size."); 00328 00329 for (unsigned i = 0; i != op0Vals.size(); ++i) { 00330 result.push_back(new SelectInst(SELI.getCondition(), 00331 op0Vals[i], 00332 op1Vals[i], 00333 SELI.getName()+ "." + utostr(i), 00334 &SELI)); 00335 } 00336 00337 setValues(&SELI,result); 00338 Changed = true; 00339 instrsToRemove.push_back(&SELI); 00340 } 00341 } 00342 00343 void LowerPacked::visitExtractElementInst(ExtractElementInst& EI) 00344 { 00345 std::vector<Value*>& op0Vals = getValues(EI.getOperand(0)); 00346 const PackedType *PTy = cast<PackedType>(EI.getOperand(0)->getType()); 00347 Value *op1 = EI.getOperand(1); 00348 00349 if (ConstantUInt *C = dyn_cast<ConstantUInt>(op1)) { 00350 EI.replaceAllUsesWith(op0Vals[C->getValue()]); 00351 } else { 00352 AllocaInst *alloca = 00353 new AllocaInst(PTy->getElementType(), 00354 ConstantUInt::get(Type::UIntTy, PTy->getNumElements()), 00355 EI.getName() + ".alloca", 00356 EI.getParent()->getParent()->getEntryBlock().begin()); 00357 for (unsigned i = 0; i < PTy->getNumElements(); ++i) { 00358 GetElementPtrInst *GEP = 00359 new GetElementPtrInst(alloca, ConstantUInt::get(Type::UIntTy, i), 00360 "store.ge", &EI); 00361 new StoreInst(op0Vals[i], GEP, &EI); 00362 } 00363 GetElementPtrInst *GEP = 00364 new GetElementPtrInst(alloca, op1, EI.getName() + ".ge", &EI); 00365 LoadInst *load = new LoadInst(GEP, EI.getName() + ".load", &EI); 00366 EI.replaceAllUsesWith(load); 00367 } 00368 00369 Changed = true; 00370 instrsToRemove.push_back(&EI); 00371 } 00372 00373 void LowerPacked::visitInsertElementInst(InsertElementInst& IE) 00374 { 00375 std::vector<Value*>& Vals = getValues(IE.getOperand(0)); 00376 Value *Elt = IE.getOperand(1); 00377 Value *Idx = IE.getOperand(2); 00378 std::vector<Value*> result; 00379 result.reserve(Vals.size()); 00380 00381 if (ConstantUInt *C = dyn_cast<ConstantUInt>(Idx)) { 00382 unsigned idxVal = C->getValue(); 00383 for (unsigned i = 0; i != Vals.size(); ++i) { 00384 result.push_back(i == idxVal ? Elt : Vals[i]); 00385 } 00386 } else { 00387 for (unsigned i = 0; i != Vals.size(); ++i) { 00388 SetCondInst *setcc = 00389 new SetCondInst(Instruction::SetEQ, Idx, 00390 ConstantUInt::get(Type::UIntTy, i), 00391 "setcc", &IE); 00392 SelectInst *select = 00393 new SelectInst(setcc, Elt, Vals[i], "select", &IE); 00394 result.push_back(select); 00395 } 00396 } 00397 00398 setValues(&IE, result); 00399 Changed = true; 00400 instrsToRemove.push_back(&IE); 00401 } 00402 00403 bool LowerPacked::runOnFunction(Function& F) 00404 { 00405 // initialize 00406 Changed = false; 00407 00408 // Does three passes: 00409 // Pass 1) Converts Packed Operations to 00410 // new Packed Operations on smaller 00411 // datatypes 00412 visit(F); 00413 00414 // Pass 2) Drop all references 00415 std::for_each(instrsToRemove.begin(), 00416 instrsToRemove.end(), 00417 std::mem_fun(&Instruction::dropAllReferences)); 00418 00419 // Pass 3) Delete the Instructions to remove aka packed instructions 00420 for (std::vector<Instruction*>::iterator i = instrsToRemove.begin(), 00421 e = instrsToRemove.end(); 00422 i != e; ++i) { 00423 (*i)->getParent()->getInstList().erase(*i); 00424 } 00425 00426 // clean-up 00427 packedToScalarMap.clear(); 00428 instrsToRemove.clear(); 00429 00430 return Changed; 00431 } 00432