1 /***** 2 * coder.h 3 * Andy Hammerlindl 2004/11/06 4 * 5 * Handles encoding of syntax into programs. It's methods are called by 6 * abstract syntax objects during translation to construct the virtual machine 7 * code. 8 *****/ 9 10 #ifndef CODER_H 11 #define CODER_H 12 13 #include "errormsg.h" 14 #include "entry.h" 15 #include "types.h" 16 #include "record.h" 17 #include "frame.h" 18 #include "program.h" 19 #include "util.h" 20 #include "modifier.h" 21 #include "inst.h" 22 23 namespace trans { 24 25 using sym::symbol; 26 using types::ty; 27 using types::function; 28 using types::record; 29 30 using vm::bltin; 31 using vm::inst; 32 using vm::item; 33 34 #ifdef DEBUG_BLTIN 35 void assertBltinLookup(inst::opcode op, item it); 36 #endif 37 38 // Labels used by the coder class to denote where in the code a jump 39 // instruction should go to. Label can be used before their exact location is 40 // known. 41 // Declared outside of the coder class, so that it can be declared in exp.h. 42 struct label_t : public gc { 43 vm::program::label location; 44 vm::program::label firstUse; 45 46 // Most labels are used only once, and so we optimize for that case. We do, 47 // however, have to handle labels which are used multiple times (such as 48 // break locations in a loop), and so a useVector is allocated to store 49 // these if necessary. 50 typedef mem::vector<vm::program::label> useVector; 51 useVector *moreUses; 52 53 // Only the constructor is defined. Everything else is handles by methods 54 // of the coder class. label_tlabel_t55 label_t() : location(), firstUse(), moreUses(0) {} 56 }; 57 typedef label_t *label; 58 59 class coder { 60 // The frame of the function we are currently encoding. This keeps 61 // track of local variables, and parameters with respect to the stack. 62 frame *level; 63 64 // The frame of the enclosing record that the "this" expression yields. ie. 65 // the highest frame that is a record, not a function. 66 frame *recordLevel; 67 68 // The type of the enclosing record. Also needed for the "this" expression. 69 record *recordType; 70 71 // Are we translating a codelet? 72 bool isCodelet; 73 74 // The lambda being constructed. In some cases, this lambda is needed 75 // before full translation of the function, so it is stored, 76 // incomplete, here. 77 vm::lambda *l; 78 79 // The type of the function being translated. 80 const function *funtype; 81 82 // The enclosing environment. Null if this is a file-level module. 83 coder *parent; 84 85 // The mode of encoding, either static or dynamic. sord is used as an 86 // acronym for Static OR Dynamic. 87 // Once something is static, no amount of dynamic modifiers can change 88 // that, so once a stack is EXPLICIT_STATIC, additional modifiers will 89 // be pushed on as EXPLICIT_STATIC. 90 modifier sord; 91 std::stack<modifier> sord_stack; 92 93 // What permissions will be given to a new access. 94 // TODO: Ensure private fields don't show up calling lookup for a 95 // record. 96 permission perm; 97 98 // The function code as its being written. Code points to next place in 99 // array to write. 100 vm::program *program; 101 102 // Some loops allocate nested frames, in case variables in an 103 // iteration escape in a closure. This stack keeps track of where the 104 // pushframe instructions are, so the size of the frame can be encoded. 105 std::stack<vm::program::label> pushframeLabels; 106 107 // Loops need to store labels to where break and continue statements 108 // should pass control. Since loops can be nested, this needs to 109 // be stored as a stack. We also store which of the loops are being encoded 110 // with an additional frame for variables. This is needed to know if the 111 // break and continue statements need to pop the frame. 112 struct loopdata_t : gc { 113 label continueLabel; 114 label breakLabel; 115 bool pushedFrame; 116 loopdata_tloopdata_t117 loopdata_t(label c, label b) 118 : continueLabel(c), breakLabel(b), pushedFrame(false) {} 119 }; 120 mem::stack<loopdata_t> loopdata; 121 122 // Current File Position 123 position curPos; 124 125 public: 126 // Define a new function coder. If reframe is true, this gives the function 127 // its own frame, which is the usual (sensible) thing to do. It is set to 128 // false for a line-at-a-time codelet, where variables should be allocated in 129 // the lower frame. 130 coder(position pos, 131 string name, function *t, coder *parent, 132 modifier sord = DEFAULT_DYNAMIC, 133 bool reframe=true); 134 135 // Start encoding the body of the record. The function being encoded 136 // is the record's initializer. 137 coder(position pos, 138 record *t, coder *parent, modifier sord = DEFAULT_DYNAMIC); 139 140 coder(position pos, 141 string name, modifier sord = DEFAULT_DYNAMIC); 142 143 coder(const coder&); 144 145 /* Add a static or dynamic modifier. */ pushModifier(modifier s)146 void pushModifier(modifier s) 147 { 148 /* Default setting should only be used in the constructor. */ 149 assert(s != DEFAULT_STATIC && s != DEFAULT_DYNAMIC); 150 151 /* Non-default static overrules. */ 152 if (sord != EXPLICIT_STATIC) 153 sord = s; 154 155 sord_stack.push(sord); 156 } 157 158 /* Tests if encoding mode is currently static. */ isStatic()159 bool isStatic() 160 { 161 switch(sord) { 162 case DEFAULT_STATIC: 163 case EXPLICIT_STATIC: 164 return true; 165 case DEFAULT_DYNAMIC: 166 case EXPLICIT_DYNAMIC: 167 return false; 168 default: 169 assert(False); 170 return false; 171 } 172 } 173 174 175 /* Remove a modifier. */ popModifier()176 void popModifier() 177 { 178 assert(!sord_stack.empty()); 179 sord_stack.pop(); 180 181 assert(!sord_stack.empty()); 182 sord = sord_stack.top(); 183 } 184 185 /* Set/get/clear permissions. */ setPermission(permission p)186 void setPermission(permission p) 187 { 188 perm = p; 189 } getPermission()190 permission getPermission() 191 { 192 return perm; 193 } clearPermission()194 void clearPermission() 195 { 196 perm = DEFAULT_PERM; 197 } 198 199 200 // Says what the return type of the function is. getReturnType()201 ty *getReturnType() { 202 return funtype->result; 203 } 204 205 bool isRecord(); 206 207 // Creates a new coder to handle the translation of a new function. 208 coder newFunction(position pos, 209 string name, function *t, modifier sord=DEFAULT_DYNAMIC); 210 211 // Creates a new record type. 212 record *newRecord(symbol id); 213 214 // Create a coder for the initializer of the record. 215 coder newRecordInit(position pos, record *r, modifier sord=DEFAULT_DYNAMIC); 216 217 // Create a coder for translating a small piece of code. Used for 218 // line-at-a-time mode. 219 coder newCodelet(position pos); 220 getFrame()221 frame *getFrame() 222 { 223 if (isStatic() && !isTopLevel()) { 224 assert(parent->getFrame()); 225 return parent->getFrame(); 226 } 227 else 228 return level; 229 } 230 231 // Tests if the function or record with the given frame is currently under 232 // translation (either by this coder or an ancestor). inTranslation(frame * f)233 bool inTranslation(frame *f) { 234 frame *level=this->level; 235 while (level) { 236 if (f==level) 237 return true; 238 level=level->getParent(); 239 } 240 return parent && parent->inTranslation(f); 241 } 242 243 // Allocates space in the function or record frame for a new local variable. allocLocal()244 access *allocLocal() 245 { 246 return getFrame()->allocLocal(); 247 } 248 249 // Get the access in the frame for a specified formal parameter. accessFormal(Int index)250 access *accessFormal(Int index) 251 { 252 // NOTE: This hasn't been extended to handle frames for loops, but is 253 // currently only called when starting to translate a function, where there 254 // can be no loops. 255 return level->accessFormal(index); 256 } 257 258 // Checks if we are at the top level, which is true for a file-level module or 259 // a codelet. isTopLevel()260 bool isTopLevel() { 261 return parent==0 || isCodelet; 262 } 263 264 // The encode functions add instructions and operands on to the code array. 265 private: encode(inst i)266 void encode(inst i) 267 { 268 i.pos = curPos; 269 // Static code is put into the enclosing coder, unless we are translating a 270 // codelet. 271 if (isStatic() && !isTopLevel()) { 272 assert(parent); 273 parent->encode(i); 274 } 275 else { 276 program->encode(i); 277 } 278 } 279 280 // Encode a jump to a not yet known location. 281 vm::program::label encodeEmptyJump(inst::opcode op); 282 283 public: encode(inst::opcode op)284 void encode(inst::opcode op) 285 { 286 inst i; i.op = op; i.pos = nullPos; 287 encode(i); 288 } encode(inst::opcode op,item it)289 void encode(inst::opcode op, item it) 290 { 291 #ifdef DEBUG_BLTIN 292 assertBltinLookup(op, it); 293 #endif 294 inst i; i.op = op; i.pos = nullPos; i.ref = it; 295 encode(i); 296 } 297 298 // Encodes a pop instruction, or merges the pop into the previous 299 // instruction (ex. varsave+pop becomes varpop). 300 void encodePop(); 301 302 // Puts the requested frame on the stack. If the frame is not that of 303 // this coder or its ancestors, false is returned. 304 bool encode(frame *f); 305 306 // Puts the frame corresponding to the expression "this" on the stack. encodeThis()307 bool encodeThis() 308 { 309 assert(recordLevel); 310 return encode(recordLevel); 311 } 312 313 // An access that encodes the frame corresponding to "this". thisLocation()314 access *thisLocation() 315 { 316 assert(recordLevel); 317 return new frameAccess(recordLevel); 318 } 319 320 // Returns the type of the enclosing record. thisType()321 record *thisType() 322 { 323 return recordType; 324 } 325 326 // Puts the 'dest' frame on the stack, assuming the frame 'top' is on 327 // top of the stack. If 'dest' is not an ancestor frame of 'top', 328 // false is returned. 329 bool encode(frame *dest, frame *top); 330 331 332 // Assigns a handle to the current point in the list of bytecode 333 // instructions and returns that handle. 334 label defNewLabel(); 335 336 // Sets the handle given by label to the current point in the list of 337 // instructions. 338 label defLabel(label label); 339 340 // Encodes the address pointed to by the handle label into the 341 // sequence of instructions. This is useful for a jump instruction to 342 // jump to where a label was defined. 343 void useLabel(inst::opcode op, label label); 344 345 // If an address has to be used for a jump instruction before it is 346 // actually encoded, a handle can be given to it by this function. 347 // When that handle's label is later defined, the proper address will 348 // be inserted into the code where the handle was used. 349 label fwdLabel(); 350 pushLoop(label c,label b)351 void pushLoop(label c, label b) { 352 loopdata.push(loopdata_t(c,b)); 353 } popLoop()354 void popLoop() { 355 loopdata.pop(); 356 } loopPushesFrame()357 void loopPushesFrame() 358 { 359 assert(!loopdata.empty()); 360 loopdata_t& d = loopdata.top(); 361 d.pushedFrame = true; 362 } encodeBreak()363 bool encodeBreak() { 364 if (loopdata.empty()) 365 return false; 366 else { 367 loopdata_t& d = loopdata.top(); 368 if (d.pushedFrame) 369 encode(inst::popframe); 370 useLabel(inst::jmp,d.breakLabel); 371 return true; 372 } 373 } encodeContinue()374 bool encodeContinue() { 375 if (loopdata.empty()) 376 return false; 377 else { 378 loopdata_t& d = loopdata.top(); 379 if (d.pushedFrame) 380 encode(inst::popframe); 381 useLabel(inst::jmp,d.continueLabel); 382 return true; 383 } 384 } 385 386 // Returns true if a pushclosure has been encoded since the definition of 387 // the label. 388 bool usesClosureSinceLabel(label l); 389 390 // Turn a no-op into a jump to bypass incorrect code. 391 void encodePatch(label from, label to); 392 393 public: encodePushFrame()394 void encodePushFrame() { 395 pushframeLabels.push(program->end()); 396 encode(inst::pushframe, (Int)0); 397 398 level = new frame("encodePushFrame", level, 0); 399 } 400 encodePopFrame()401 void encodePopFrame() { 402 pushframeLabels.top()->ref = level->size(); 403 pushframeLabels.pop(); 404 405 encode(inst::popframe); 406 407 level = level->getParent(); 408 } 409 410 // Adds an entry into the position list, linking the given point in the 411 // source code to the current position in the virtual machine code. This is 412 // used to print positions at runtime. 413 void markPos(position pos); 414 415 // When translation of the function is finished, this ties up loose ends 416 // and returns the lambda. 417 vm::lambda *close(); 418 419 // Finishes translating the initializer of a record. 420 void closeRecord(); 421 422 private: // Non-copyable 423 void operator=(const coder&); 424 }; 425 426 } // namespace trans 427 428 #endif 429