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