IceOperand.cpp revision 2e8bfbb9e2a5be0271d771f197d629e6f7d3568e
1//===- subzero/src/IceOperand.cpp - High-level operand implementation -----===// 2// 3// The Subzero Code Generator 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the Operand class and its target-independent 11// subclasses, primarily for the methods of the Variable class. 12// 13//===----------------------------------------------------------------------===// 14 15#include "IceCfg.h" 16#include "IceInst.h" 17#include "IceOperand.h" 18#include "IceTargetLowering.h" // dumping stack/frame pointer register 19 20namespace Ice { 21 22bool operator<(const RelocatableTuple &A, const RelocatableTuple &B) { 23 if (A.Offset != B.Offset) 24 return A.Offset < B.Offset; 25 if (A.SuppressMangling != B.SuppressMangling) 26 return A.SuppressMangling < B.SuppressMangling; 27 return A.Name < B.Name; 28} 29 30bool operator<(const RegWeight &A, const RegWeight &B) { 31 return A.getWeight() < B.getWeight(); 32} 33bool operator<=(const RegWeight &A, const RegWeight &B) { return !(B < A); } 34bool operator==(const RegWeight &A, const RegWeight &B) { 35 return !(B < A) && !(A < B); 36} 37 38void LiveRange::addSegment(InstNumberT Start, InstNumberT End) { 39#ifdef USE_SET 40 RangeElementType Element(Start, End); 41 RangeType::iterator Next = Range.lower_bound(Element); 42 assert(Next == Range.upper_bound(Element)); // Element not already present 43 44 // Beginning of code that merges contiguous segments. TODO: change 45 // "if(true)" to "if(false)" to see if this extra optimization code 46 // gives any performance gain, or is just destabilizing. 47 if (true) { 48 RangeType::iterator FirstDelete = Next; 49 RangeType::iterator Prev = Next; 50 bool hasPrev = (Next != Range.begin()); 51 bool hasNext = (Next != Range.end()); 52 if (hasPrev) 53 --Prev; 54 // See if Element and Next should be joined. 55 if (hasNext && End == Next->first) { 56 Element.second = Next->second; 57 ++Next; 58 } 59 // See if Prev and Element should be joined. 60 if (hasPrev && Prev->second == Start) { 61 Element.first = Prev->first; 62 FirstDelete = Prev; 63 } 64 Range.erase(FirstDelete, Next); 65 } 66 // End of code that merges contiguous segments. 67 68 Range.insert(Next, Element); 69#else 70 if (Range.empty()) { 71 Range.push_back(RangeElementType(Start, End)); 72 return; 73 } 74 // Special case for faking in-arg liveness. 75 if (End < Range.front().first) { 76 assert(Start < 0); 77 Range.push_front(RangeElementType(Start, End)); 78 return; 79 } 80 InstNumberT CurrentEnd = Range.back().second; 81 assert(Start >= CurrentEnd); 82 // Check for merge opportunity. 83 if (Start == CurrentEnd) { 84 Range.back().second = End; 85 return; 86 } 87 Range.push_back(RangeElementType(Start, End)); 88#endif 89} 90 91// Returns true if this live range ends before Other's live range 92// starts. This means that the highest instruction number in this 93// live range is less than or equal to the lowest instruction number 94// of the Other live range. 95bool LiveRange::endsBefore(const LiveRange &Other) const { 96 // Neither range should be empty, but let's be graceful. 97 if (Range.empty() || Other.Range.empty()) 98 return true; 99 InstNumberT MyEnd = (*Range.rbegin()).second; 100 InstNumberT OtherStart = (*Other.Range.begin()).first; 101 return MyEnd <= OtherStart; 102} 103 104// Returns true if there is any overlap between the two live ranges. 105bool LiveRange::overlaps(const LiveRange &Other) const { 106 // Do a two-finger walk through the two sorted lists of segments. 107 RangeType::const_iterator I1 = Range.begin(), I2 = Other.Range.begin(); 108 RangeType::const_iterator E1 = Range.end(), E2 = Other.Range.end(); 109 while (I1 != E1 && I2 != E2) { 110 if (I1->second <= I2->first) { 111 ++I1; 112 continue; 113 } 114 if (I2->second <= I1->first) { 115 ++I2; 116 continue; 117 } 118 return true; 119 } 120 return false; 121} 122 123bool LiveRange::overlaps(InstNumberT OtherBegin) const { 124 LiveRange Temp; 125 Temp.addSegment(OtherBegin, OtherBegin + 1); 126 return overlaps(Temp); 127} 128 129// Returns true if the live range contains the given instruction 130// number. This is only used for validating the live range 131// calculation. 132bool LiveRange::containsValue(InstNumberT Value) const { 133 for (RangeType::const_iterator I = Range.begin(), E = Range.end(); I != E; 134 ++I) { 135 if (I->first <= Value && Value <= I->second) 136 return true; 137 } 138 return false; 139} 140 141void Variable::setUse(const Inst *Inst, const CfgNode *Node) { 142 if (DefNode == NULL) 143 return; 144 if (llvm::isa<InstPhi>(Inst) || Node != DefNode) 145 DefNode = NULL; 146} 147 148void Variable::setDefinition(Inst *Inst, const CfgNode *Node) { 149 if (DefInst && !DefInst->isDeleted() && DefInst != Inst) { 150 // Detect when a variable is being defined multiple times, 151 // particularly for Phi instruction lowering. If this happens, we 152 // need to lock DefInst to NULL. 153 DefInst = NULL; 154 DefNode = NULL; 155 return; 156 } 157 if (DefNode == NULL) 158 return; 159 DefInst = Inst; 160 if (Node != DefNode) 161 DefNode = NULL; 162} 163 164void Variable::replaceDefinition(Inst *Inst, const CfgNode *Node) { 165 DefInst = NULL; 166 setDefinition(Inst, Node); 167} 168 169void Variable::setIsArg(Cfg *Func, bool IsArg) { 170 if (IsArg) { 171 IsArgument = true; 172 if (DefNode == NULL) 173 return; 174 CfgNode *Entry = Func->getEntryNode(); 175 if (DefNode == Entry) 176 return; 177 DefNode = NULL; 178 } else { 179 IsArgument = false; 180 } 181} 182 183IceString Variable::getName() const { 184 if (!Name.empty()) 185 return Name; 186 char buf[30]; 187 snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex()); 188 return buf; 189} 190 191Variable Variable::asType(Type Ty) { 192 Variable V(Ty, DefNode, Number, Name); 193 V.RegNum = RegNum; 194 V.StackOffset = StackOffset; 195 return V; 196} 197 198// ======================== dump routines ======================== // 199 200void Variable::emit(const Cfg *Func) const { 201 Func->getTarget()->emitVariable(this, Func); 202} 203 204void Variable::dump(const Cfg *Func, Ostream &Str) const { 205 if (Func == NULL) { 206 Str << "%" << getName(); 207 return; 208 } 209 const CfgNode *CurrentNode = Func->getCurrentNode(); 210 (void)CurrentNode; // used only in assert() 211 assert(CurrentNode == NULL || DefNode == NULL || DefNode == CurrentNode); 212 if (Func->getContext()->isVerbose(IceV_RegOrigins) || 213 (!hasReg() && !Func->getTarget()->hasComputedFrame())) 214 Str << "%" << getName(); 215 if (hasReg()) { 216 if (Func->getContext()->isVerbose(IceV_RegOrigins)) 217 Str << ":"; 218 Str << Func->getTarget()->getRegName(RegNum, getType()); 219 } else if (Func->getTarget()->hasComputedFrame()) { 220 if (Func->getContext()->isVerbose(IceV_RegOrigins)) 221 Str << ":"; 222 Str << "[" << Func->getTarget()->getRegName( 223 Func->getTarget()->getFrameOrStackReg(), IceType_i32); 224 int32_t Offset = getStackOffset(); 225 if (Offset) { 226 if (Offset > 0) 227 Str << "+"; 228 Str << Offset; 229 } 230 Str << "]"; 231 } 232} 233 234void ConstantRelocatable::emit(GlobalContext *Ctx) const { 235 Ostream &Str = Ctx->getStrEmit(); 236 if (SuppressMangling) 237 Str << Name; 238 else 239 Str << Ctx->mangleName(Name); 240 if (Offset) { 241 if (Offset > 0) 242 Str << "+"; 243 Str << Offset; 244 } 245} 246 247void ConstantRelocatable::dump(const Cfg *, Ostream &Str) const { 248 Str << "@" << Name; 249 if (Offset) 250 Str << "+" << Offset; 251} 252 253void LiveRange::dump(Ostream &Str) const { 254 Str << "(weight=" << Weight << ") "; 255 for (RangeType::const_iterator I = Range.begin(), E = Range.end(); I != E; 256 ++I) { 257 if (I != Range.begin()) 258 Str << ", "; 259 Str << "[" << (*I).first << ":" << (*I).second << ")"; 260 } 261} 262 263Ostream &operator<<(Ostream &Str, const LiveRange &L) { 264 L.dump(Str); 265 return Str; 266} 267 268Ostream &operator<<(Ostream &Str, const RegWeight &W) { 269 if (W.getWeight() == RegWeight::Inf) 270 Str << "Inf"; 271 else 272 Str << W.getWeight(); 273 return Str; 274} 275 276} // end of namespace Ice 277