1 module d.ir.instruction; 2 3 import source.context; 4 import source.location; 5 import source.name; 6 7 import d.ir.expression; 8 import d.ir.symbol; 9 10 struct Body { 11 private: 12 BasicBlock[] basicBlocks; 13 14 public: 15 ref inout(BasicBlock) opIndex(BasicBlockRef i) inout in { 16 assert(i, "null block ref"); 17 assert(i.index <= basicBlocks.length, "Out of bounds block ref"); 18 } do { 19 return basicBlocks.ptr[i.index - 1]; 20 } 21 22 bool opCast(T : bool)() const { 23 return basicBlocks.length > 0; 24 } 25 26 @property 27 auto length() const { 28 return basicBlocks.length; 29 } 30 31 // XXX: Required due to conversion rules. 32 BasicBlockRef newBasicBlock(Name name) { 33 BasicBlockRef landingpad; 34 return newBasicBlock(name, landingpad); 35 } 36 37 BasicBlockRef newBasicBlock(Name name, BasicBlockRef landingpad) { 38 auto i = cast(uint) basicBlocks.length; 39 auto bbref = BasicBlockRef(i); 40 // XXX: We can't happend because it is non copyable (DMD bug, IMO). 41 // basicBlocks ~= BasicBlock(bbref); 42 basicBlocks.length += 1; 43 basicBlocks[i] = BasicBlock(name, landingpad); 44 return bbref; 45 } 46 47 void dump(const Context c) const { 48 foreach (ref b; basicBlocks) { 49 dump(c, b); 50 } 51 } 52 53 void dump(const Context c, const ref BasicBlock b) const { 54 import std.stdio; 55 writeln(); 56 dumpBasicBlockName(c, b); 57 write(':'); 58 59 if (b.landingpad) { 60 import std.stdio; 61 write("\t\t\t\tunwind to "); 62 dumpBasicBlockName(c, this[b.landingpad]); 63 } 64 65 writeln(); 66 67 foreach (ref i; b.instructions) { 68 dump(c, b, i); 69 } 70 71 final switch (b.terminator) with (Terminator) { 72 case None: 73 writeln("unterminated..."); 74 break; 75 76 case Branch: 77 write("\tbranch "); 78 if (b.value is null) { 79 dumpBasicBlockName(c, this[b.successors[0]]); 80 } else { 81 write(b.value.toString(c), ", "); 82 dumpBasicBlockName(c, this[b.successors[0]]); 83 write(", "); 84 dumpBasicBlockName(c, this[b.successors[1]]); 85 } 86 87 writeln(); 88 break; 89 90 case Switch: 91 writeln("\tswitch ", b.value.toString(c)); 92 write("\t\tdefault: "); 93 dumpBasicBlockName(c, this[b.switchTable.defaultBlock]); 94 foreach (ce; b.switchTable.cases) { 95 write("\n\t\tcase ", ce.value, ": "); 96 dumpBasicBlockName(c, this[ce.block]); 97 } 98 99 writeln(); 100 break; 101 102 case Return: 103 writeln("\treturn ", b.value ? b.value.toString(c) : "void"); 104 break; 105 106 case Throw: 107 if (b.value) { 108 writeln("\tthrow ", b.value.toString(c)); 109 } else if (b.catchTable) { 110 write("\tcatch"); 111 foreach (ca; b.catchTable.catches) { 112 write("\n\t\t", ca.type.name.toString(c), ": "); 113 dumpBasicBlockName(c, this[ca.block]); 114 } 115 116 writeln(); 117 } else { 118 writeln("\trethrow"); 119 } 120 121 break; 122 123 case Halt: 124 writeln("\thalt ", b.value ? b.value.toString(c) : ""); 125 break; 126 } 127 } 128 129 void dumpBasicBlockName(const Context c, const ref BasicBlock b) const { 130 size_t index = (cast(size_t) &b - cast(size_t) basicBlocks.ptr) 131 / BasicBlock.sizeof; 132 133 import std.stdio; 134 write(b.name.toString(c), index); 135 } 136 137 void dump(const Context c, const ref BasicBlock b, 138 const ref Instruction i) const { 139 import std.stdio; 140 final switch (i.op) with (OpCode) { 141 case Alloca: 142 writeln("\t", i.var.toString(c)); 143 break; 144 145 case Destroy: 146 writeln("\tdestroy\t", i.var.name.toString(c)); 147 break; 148 149 case Evaluate: 150 writeln("\t", i.expr.toString(c)); 151 break; 152 153 case Declare: 154 writeln("\t", i.sym.toString(c)); 155 break; 156 } 157 } 158 } 159 160 auto range(const Body fbody) { 161 import std.algorithm, std.range; 162 return iota(0, cast(uint) fbody.basicBlocks.length) 163 .map!(i => BasicBlockRef(i)); 164 } 165 166 struct BasicBlockRef { 167 private: 168 uint index; 169 170 this(uint index) { 171 this.index = index + 1; 172 } 173 174 public: 175 bool opCast(T : bool)() const { 176 return index != 0; 177 } 178 179 BasicBlockRef opAssign(typeof(null)) { 180 index = 0; 181 return this; 182 } 183 } 184 185 auto range(inout Body fbody, BasicBlockRef b) { 186 return fbody[b].instructions; 187 } 188 189 enum Terminator { 190 None, 191 Branch, 192 Switch, 193 Return, 194 Throw, 195 Halt, 196 } 197 198 struct BasicBlock { 199 private: 200 Instruction[] instructions; 201 202 import source.name; 203 Name _name; 204 205 Terminator _terminator; 206 union { 207 public BasicBlockRef[2] successors; 208 public SwitchTable* switchTable; 209 public CatchTable* catchTable; 210 } 211 212 // We need to win a uint in there so that this is 4 pointers sized. 213 // We probably won't need more than 4G instructions, so we can win 214 // int he instruction array length. 215 BasicBlockRef _landingpad; 216 217 // XXX: Let's say I'm not happy with that layout. 218 public Location location; 219 public Expression value; 220 221 this(Name name, BasicBlockRef landingpad) { 222 _name = name; 223 _landingpad = landingpad; 224 } 225 226 @disable 227 this(this); 228 229 void add(Instruction i) in { 230 assert(!terminate, "block does terminate already"); 231 } do { 232 instructions ~= i; 233 } 234 235 public: 236 @property 237 Name name() const { 238 return _name; 239 } 240 241 @property 242 Terminator terminator() const { 243 return _terminator; 244 } 245 246 @property 247 bool terminate() const { 248 return terminator != Terminator.None; 249 } 250 251 @property 252 bool empty() const { 253 return !terminate && instructions.length == 0; 254 } 255 256 @property 257 BasicBlockRef landingpad() const { 258 return _landingpad; 259 } 260 261 @property 262 BasicBlockRef landingpad(BasicBlockRef landingpad) { 263 return _landingpad = landingpad; 264 } 265 266 void alloca(Location location, Variable v) { 267 add(Instruction(location, v)); 268 } 269 270 void destroy(Location location, Variable v) { 271 add(Instruction.destroy(location, v)); 272 } 273 274 void eval(Location location, Expression e) { 275 add(Instruction(location, e)); 276 } 277 278 void declare(Location location, Symbol s) { 279 add(Instruction(location, s)); 280 } 281 282 void branch(Location location, BasicBlockRef dst) { 283 _terminator = Terminator.Branch; 284 successors[0] = dst; 285 } 286 287 void branch(Location location, Expression cond, BasicBlockRef ifTrue, 288 BasicBlockRef ifFalse) { 289 _terminator = Terminator.Branch; 290 291 // XXX: ALARM! ALARM! 292 value = cond; 293 successors[0] = ifTrue; 294 successors[1] = ifFalse; 295 } 296 297 void doSwitch(Location location, Expression e, SwitchTable* switchTable) { 298 _terminator = Terminator.Switch; 299 this.location = location; 300 this.value = e; 301 this.switchTable = switchTable; 302 } 303 304 void ret(Location location, Expression e = null) { 305 _terminator = Terminator.Return; 306 this.location = location; 307 value = e; 308 } 309 310 void doThrow(Location location, Expression e = null) { 311 _terminator = Terminator.Throw; 312 this.location = location; 313 value = e; 314 } 315 316 void doCatch(Location location, CatchTable* catchTable) { 317 _terminator = Terminator.Throw; 318 this.location = location; 319 this.catchTable = catchTable; 320 } 321 322 void halt(Location location, Expression msg = null) { 323 _terminator = Terminator.Halt; 324 this.location = location; 325 value = msg; 326 } 327 } 328 329 enum OpCode { 330 Alloca, 331 Destroy, 332 Evaluate, 333 334 // FIXME: This is unecessary, but will makes things easier for now. 335 Declare, 336 } 337 338 struct Instruction { 339 Location location; 340 341 OpCode op; 342 343 union { 344 Expression expr; 345 Variable var; 346 Symbol sym; 347 } 348 349 private: 350 this(Location location, Expression e) { 351 this.location = location; 352 op = OpCode.Evaluate; 353 expr = e; 354 } 355 356 this(Location location, Variable v) in { 357 assert(v.step == Step.Processed, "Variable is not processed"); 358 } do { 359 this.location = location; 360 op = OpCode.Alloca; 361 var = v; 362 } 363 364 static destroy(Location location, Variable v) { 365 auto i = Instruction(location, v); 366 i.op = OpCode.Destroy; 367 return i; 368 } 369 370 this(Location location, Symbol s) in { 371 assert(s.step == Step.Processed, "Symbol is not processed"); 372 assert(!cast(Variable) s, "Use alloca for variables"); 373 } do { 374 this.location = location; 375 op = OpCode.Declare; 376 sym = s; 377 } 378 } 379 380 struct SwitchTable { 381 BasicBlockRef defaultBlock; 382 uint entryCount; 383 384 @property 385 inout(CaseEntry)[] cases() inout { 386 return (cast(inout(CaseEntry)*) &(&this)[1])[0 .. entryCount]; 387 } 388 } 389 390 struct CaseEntry { 391 BasicBlockRef block; 392 uint value; 393 } 394 395 struct CatchTable { 396 size_t catchCount; 397 BasicBlockRef catchAll; 398 399 @property 400 inout(CatchPad)[] catches() inout { 401 return (cast(inout(CatchPad)*) &(&this)[1])[0 .. catchCount]; 402 } 403 } 404 405 struct CatchPad { 406 Class type; 407 BasicBlockRef block; 408 }