| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library cps_ir.cps_fragment; | |
| 6 | |
| 7 import '../constants/values.dart'; | |
| 8 import '../elements/elements.dart'; | |
| 9 import '../io/source_information.dart'; | |
| 10 import '../types/types.dart' show TypeMask; | |
| 11 import '../universe/selector.dart' show Selector; | |
| 12 import 'cps_ir_nodes.dart'; | |
| 13 | |
| 14 /// Builds a CPS fragment that can be plugged into another CPS term. | |
| 15 /// | |
| 16 /// A CPS fragment contains a CPS term, possibly with a "hole" in it denoting | |
| 17 /// where to insert new IR nodes. We say a fragment is "open" if it has such | |
| 18 /// a hole. Otherwise, the fragment is "closed" and cannot be extended further. | |
| 19 /// | |
| 20 /// This class is designed for building non-trivial CPS terms in a readable and | |
| 21 /// non-error prone manner. It is not designed to manipulate existing IR nodes, | |
| 22 /// nor is it intended to shield the user from every complexity in the IR. | |
| 23 /// | |
| 24 /// EXAMPLES: | |
| 25 /// | |
| 26 /// Call `cont` with `obj.field + 1` as argument: | |
| 27 /// | |
| 28 /// CpsFragment cps = new CpsFragment(); | |
| 29 /// var fieldValue = cps.letPrim(new GetField(obj, field)); | |
| 30 /// var plusOne = cps.applyBuiltin(BuiltinOperator.NumAdd, | |
| 31 /// [fieldValue, cps.makeOne()]); | |
| 32 /// cps.invokeContinuation(cont, [plusOne]); | |
| 33 /// | |
| 34 /// If `condition` is true then invoke `cont1`, else `cont2`. | |
| 35 /// | |
| 36 /// cps.ifTruthy(condition).invokeContinuation(cont1, []); | |
| 37 /// cps.invokeContinuation(cont2, []); | |
| 38 /// | |
| 39 /// If `condition` is true then invoke `cont` with a bound primitive: | |
| 40 /// | |
| 41 /// CpsFragment branch = cps.ifTruthy(condition); | |
| 42 /// branch.invokeContinuation(cont, [branch.letPrim(arg)]); | |
| 43 /// | |
| 44 /// Loop and call a method until it returns false: | |
| 45 /// | |
| 46 /// Continuation loop = cps.beginLoop(); | |
| 47 /// var result = cps.invokeMethod(receiver, selector, ...); | |
| 48 /// cps.ifFalsy(result).invokeContinuation(exit, []); | |
| 49 /// cps.continueLoop(loop); | |
| 50 /// | |
| 51 class CpsFragment { | |
| 52 /// The root of the IR built using this fragment. | |
| 53 Expression root; | |
| 54 | |
| 55 /// Node whose body is the hole in this CPS fragment. May be null. | |
| 56 InteriorNode context; | |
| 57 | |
| 58 /// Source information to attach to every IR node created in the fragment. | |
| 59 SourceInformation sourceInformation; | |
| 60 | |
| 61 CpsFragment([this.sourceInformation, this.context]); | |
| 62 | |
| 63 bool get isOpen => root == null || context != null; | |
| 64 bool get isClosed => !isOpen; | |
| 65 bool get isEmpty => root == null; | |
| 66 | |
| 67 /// Asserts that the fragment is non-empty and closed and returns the IR that | |
| 68 /// was built. | |
| 69 Expression get result { | |
| 70 assert(!isEmpty); | |
| 71 assert(isClosed); | |
| 72 return root; | |
| 73 } | |
| 74 | |
| 75 /// Put the given expression into the fragment's hole. | |
| 76 /// | |
| 77 /// Afterwards the fragment is closed and cannot be extended until a new | |
| 78 /// [context] is set. | |
| 79 void put(Expression node) { | |
| 80 assert(root == null || context != null); // We must put the node somewhere. | |
| 81 if (root == null) { | |
| 82 root = node; | |
| 83 } | |
| 84 if (context != null) { | |
| 85 context.body = node; | |
| 86 node.parent = context; | |
| 87 } | |
| 88 context = null; | |
| 89 } | |
| 90 | |
| 91 /// Bind a primitive. Returns the same primitive for convenience. | |
| 92 Primitive letPrim(Primitive prim) { | |
| 93 assert(prim != null); | |
| 94 LetPrim let = new LetPrim(prim); | |
| 95 put(let); | |
| 96 context = let; | |
| 97 return prim; | |
| 98 } | |
| 99 | |
| 100 /// Bind a constant value. | |
| 101 Primitive makeConstant(ConstantValue constant) { | |
| 102 return letPrim(new Constant(constant)); | |
| 103 } | |
| 104 | |
| 105 Primitive makeZero() => makeConstant(new IntConstantValue(0)); | |
| 106 Primitive makeOne() => makeConstant(new IntConstantValue(1)); | |
| 107 Primitive makeMinusOne() => makeConstant(new IntConstantValue(-1)); | |
| 108 Primitive makeNull() => makeConstant(new NullConstantValue()); | |
| 109 Primitive makeTrue() => makeConstant(new TrueConstantValue()); | |
| 110 Primitive makeFalse() => makeConstant(new FalseConstantValue()); | |
| 111 | |
| 112 /// Invoke a built-in operator. | |
| 113 Primitive applyBuiltin(BuiltinOperator op, List<Primitive> args) { | |
| 114 return letPrim(new ApplyBuiltinOperator(op, args, sourceInformation)); | |
| 115 } | |
| 116 | |
| 117 Primitive refine(Primitive value, TypeMask type) { | |
| 118 return letPrim(new Refinement(value, type)); | |
| 119 } | |
| 120 | |
| 121 Primitive invokeBuiltin( | |
| 122 BuiltinMethod method, Primitive receiver, List<Primitive> arguments, | |
| 123 {bool receiverIsNotNull: false}) { | |
| 124 ApplyBuiltinMethod apply = | |
| 125 new ApplyBuiltinMethod(method, receiver, arguments, sourceInformation); | |
| 126 return letPrim(apply); | |
| 127 } | |
| 128 | |
| 129 /// Inserts an invocation and returns a primitive holding the returned value. | |
| 130 Primitive invokeMethod(Primitive receiver, Selector selector, TypeMask mask, | |
| 131 List<Primitive> arguments, | |
| 132 {Primitive interceptor, CallingConvention callingConvention}) { | |
| 133 InvokeMethod invoke = new InvokeMethod(receiver, selector, mask, arguments, | |
| 134 sourceInformation: sourceInformation, | |
| 135 callingConvention: callingConvention, | |
| 136 interceptor: interceptor); | |
| 137 return letPrim(invoke); | |
| 138 } | |
| 139 | |
| 140 /// Inserts an invocation and returns a primitive holding the returned value. | |
| 141 Primitive invokeStatic(FunctionElement target, List<Primitive> arguments) { | |
| 142 return letPrim(new InvokeStatic(target, new Selector.fromElement(target), | |
| 143 arguments, sourceInformation)); | |
| 144 } | |
| 145 | |
| 146 /// Inserts an invocation to a static function that throws an error. | |
| 147 /// | |
| 148 /// This closes the fragment; no more nodes may be added. | |
| 149 void invokeStaticThrower(FunctionElement target, List<Primitive> arguments) { | |
| 150 invokeStatic(target, arguments); | |
| 151 put(new Unreachable()); | |
| 152 } | |
| 153 | |
| 154 /// Invoke a non-recursive continuation. | |
| 155 /// | |
| 156 /// This closes the fragment; no more nodes may be inserted. | |
| 157 void invokeContinuation(Continuation cont, [List<Primitive> arguments]) { | |
| 158 if (arguments == null) arguments = <Primitive>[]; | |
| 159 put(new InvokeContinuation(cont, arguments)); | |
| 160 } | |
| 161 | |
| 162 /// Build a loop with the given loop variables and initial values. | |
| 163 /// Call [continueLoop] with the returned continuation to iterate the loop. | |
| 164 /// | |
| 165 /// The loop body becomes the new hole. | |
| 166 Continuation beginLoop( | |
| 167 [List<Parameter> loopVars, List<Primitive> initialValues]) { | |
| 168 if (initialValues == null) { | |
| 169 assert(loopVars == null); | |
| 170 loopVars = <Parameter>[]; | |
| 171 initialValues = <Primitive>[]; | |
| 172 } | |
| 173 Continuation cont = new Continuation(loopVars); | |
| 174 put(new LetCont(cont, new InvokeContinuation(cont, initialValues))); | |
| 175 context = cont; | |
| 176 return cont; | |
| 177 } | |
| 178 | |
| 179 /// Continue a loop started by [beginLoop]. | |
| 180 /// | |
| 181 /// This closes the fragment; no more nodes may be inserted. | |
| 182 void continueLoop(Continuation cont, [List<Primitive> updatedLoopVariables]) { | |
| 183 put(new InvokeContinuation(cont, updatedLoopVariables, isRecursive: true)); | |
| 184 } | |
| 185 | |
| 186 /// Branch on [condition]. | |
| 187 /// | |
| 188 /// Returns a new fragment for the 'then' branch, or the 'else' branch | |
| 189 /// if [negate] is true. | |
| 190 /// | |
| 191 /// The other branch becomes the new hole. | |
| 192 CpsFragment branch(Primitive condition, | |
| 193 {bool negate: false, bool strict: false}) { | |
| 194 Continuation trueCont = new Continuation(<Parameter>[]); | |
| 195 Continuation falseCont = new Continuation(<Parameter>[]); | |
| 196 put(new LetCont.two( | |
| 197 trueCont, | |
| 198 falseCont, | |
| 199 new Branch(condition, trueCont, falseCont, sourceInformation, | |
| 200 strict: strict))); | |
| 201 if (negate) { | |
| 202 context = trueCont; | |
| 203 return new CpsFragment(sourceInformation, falseCont); | |
| 204 } else { | |
| 205 context = falseCont; | |
| 206 return new CpsFragment(sourceInformation, trueCont); | |
| 207 } | |
| 208 } | |
| 209 | |
| 210 /// Branch on [condition]. | |
| 211 /// | |
| 212 /// Returns a new fragment for the 'then' branch. | |
| 213 /// | |
| 214 /// The 'else' branch becomes the new hole. | |
| 215 CpsFragment ifTruthy(Primitive condition) => branch(condition); | |
| 216 | |
| 217 /// Branch on [condition]. | |
| 218 /// | |
| 219 /// Returns a new fragment for the 'else' branch. | |
| 220 /// | |
| 221 /// The 'then' branch becomes the new hole. | |
| 222 CpsFragment ifFalsy(Primitive condition) => branch(condition, negate: true); | |
| 223 | |
| 224 /// Create a new empty continuation and bind it here. | |
| 225 /// | |
| 226 /// Convenient for making a join point where multiple branches | |
| 227 /// meet later. | |
| 228 /// | |
| 229 /// The LetCont body becomes the new hole. | |
| 230 /// | |
| 231 /// Example use: | |
| 232 /// | |
| 233 /// Continuation fail = cps.letCont(); | |
| 234 /// | |
| 235 /// // Fail if something | |
| 236 /// cps.ifTrue(<condition>) | |
| 237 /// ..invokeMethod(<method>) | |
| 238 /// ..invokeContinuation(fail); | |
| 239 /// | |
| 240 /// // Fail if something else | |
| 241 /// cps.ifTrue(<anotherCondition>) | |
| 242 /// ..invokeMethod(<anotherMethod>) | |
| 243 /// ..invokeContinuation(fail); | |
| 244 /// | |
| 245 /// // Build the fail branch | |
| 246 /// cps.insideContinuation(fail) | |
| 247 /// ..invokeStaticThrower(...); | |
| 248 /// | |
| 249 /// // Go to the happy branch | |
| 250 /// cps.invokeContinuation(cont..) | |
| 251 /// | |
| 252 Continuation letCont([List<Parameter> parameters]) { | |
| 253 if (parameters == null) parameters = <Parameter>[]; | |
| 254 Continuation cont = new Continuation(parameters); | |
| 255 bindContinuation(cont); | |
| 256 return cont; | |
| 257 } | |
| 258 | |
| 259 /// Binds an existing continuation at this position. | |
| 260 /// | |
| 261 /// The LetCont body becomes the new hole. | |
| 262 void bindContinuation(Continuation cont) { | |
| 263 LetCont let = new LetCont(cont, null); | |
| 264 put(let); | |
| 265 context = let; | |
| 266 } | |
| 267 | |
| 268 /// Inlines [target] at the current position, substituting the provided | |
| 269 /// arguments. | |
| 270 /// | |
| 271 /// Returns a primitive containing the function's return value. | |
| 272 /// | |
| 273 /// The new hole is the point after [target] has returned. The fragment | |
| 274 /// remains open, even if [target] never returns. | |
| 275 /// | |
| 276 /// The [target] function is destroyed and should not be reused. | |
| 277 Primitive inlineFunction( | |
| 278 FunctionDefinition target, Primitive receiver, List<Primitive> arguments, | |
| 279 {Entity hint, Primitive interceptor}) { | |
| 280 if (interceptor != null) { | |
| 281 target.interceptorParameter.replaceUsesWith(interceptor); | |
| 282 } | |
| 283 if (receiver != null) { | |
| 284 target.receiverParameter.replaceUsesWith(receiver); | |
| 285 } | |
| 286 for (int i = 0; i < arguments.length; ++i) { | |
| 287 target.parameters[i].replaceUsesWith(arguments[i]); | |
| 288 } | |
| 289 Continuation returnCont = target.returnContinuation; | |
| 290 bindContinuation(returnCont); | |
| 291 put(target.body); | |
| 292 Parameter returnValue = returnCont.parameters.single; | |
| 293 returnValue.hint = hint; | |
| 294 context = returnCont; | |
| 295 return returnValue; | |
| 296 } | |
| 297 | |
| 298 /// Returns a fragment whose context is the body of the given continuation. | |
| 299 /// | |
| 300 /// Does not change the state of this CPS fragment. | |
| 301 /// | |
| 302 /// Useful for building the body of a continuation created using [letCont]. | |
| 303 CpsFragment insideContinuation(Continuation cont) { | |
| 304 return new CpsFragment(sourceInformation, cont); | |
| 305 } | |
| 306 | |
| 307 /// Puts the given fragment into this one. | |
| 308 /// | |
| 309 /// If [other] was an open fragment, its hole becomes the new hole | |
| 310 /// in this fragment. | |
| 311 /// | |
| 312 /// [other] is reset to an empty fragment after this. | |
| 313 void append(CpsFragment other) { | |
| 314 if (other.root == null) return; | |
| 315 put(other.root); | |
| 316 context = other.context; | |
| 317 other.context = null; | |
| 318 other.root = null; | |
| 319 } | |
| 320 | |
| 321 /// Reads the value of the given mutable variable. | |
| 322 Primitive getMutable(MutableVariable variable) { | |
| 323 return letPrim(new GetMutable(variable)); | |
| 324 } | |
| 325 | |
| 326 /// Sets the value of the given mutable variable. | |
| 327 void setMutable(MutableVariable variable, Primitive value) { | |
| 328 letPrim(new SetMutable(variable, value)); | |
| 329 } | |
| 330 | |
| 331 /// Declare a new mutable variable. | |
| 332 void letMutable(MutableVariable variable, Primitive initialValue) { | |
| 333 LetMutable let = new LetMutable(variable, initialValue); | |
| 334 put(let); | |
| 335 context = let; | |
| 336 } | |
| 337 | |
| 338 void insertBelow(InteriorNode node) { | |
| 339 assert(isOpen); | |
| 340 if (isEmpty) return; | |
| 341 Expression child = node.body; | |
| 342 node.body = root; | |
| 343 root.parent = node; | |
| 344 context.body = child; | |
| 345 child.parent = context; | |
| 346 root = context = null; | |
| 347 } | |
| 348 | |
| 349 void insertAbove(InteriorExpression node) { | |
| 350 insertBelow(node.parent); | |
| 351 } | |
| 352 } | |
| 353 | |
| 354 /// Removes [node], unlinking all its references and replaces it with [newNode]. | |
| 355 void destroyAndReplace(Expression node, Expression newNode) { | |
| 356 InteriorNode parent = node.parent; | |
| 357 RemovalVisitor.remove(node); | |
| 358 parent.body = newNode; | |
| 359 newNode.parent = parent; | |
| 360 } | |
| 361 | |
| 362 /// Removes all [Refinement] uses of a given primitive that has no effective | |
| 363 /// uses. | |
| 364 void destroyRefinementsOfDeadPrimitive(Primitive prim) { | |
| 365 while (prim.firstRef != null) { | |
| 366 Refinement refine = prim.firstRef.parent; | |
| 367 destroyRefinementsOfDeadPrimitive(refine); | |
| 368 LetPrim letPrim = refine.parent; | |
| 369 InteriorNode parent = letPrim.parent; | |
| 370 parent.body = letPrim.body; | |
| 371 letPrim.body.parent = parent; | |
| 372 prim.firstRef.unlink(); | |
| 373 } | |
| 374 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
