Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(216)

Side by Side Diff: pkg/compiler/lib/src/dart_backend/logical_rewriter.dart

Issue 693183006: Revert "Move dart2js from sdk/lib/_internal/compiler to pkg/compiler" (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
(Empty)
1 // Copyright (c) 2014, 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 logical_rewriter;
6
7 import '../constants/values.dart' as values;
8 import 'tree_ir_nodes.dart';
9
10 /// Rewrites logical expressions to be more compact in the Tree IR.
11 ///
12 /// In this class an expression is said to occur in "boolean context" if
13 /// its result is immediately applied to boolean conversion.
14 ///
15 /// IF STATEMENTS:
16 ///
17 /// We apply the following two rules to [If] statements (see [visitIf]).
18 ///
19 /// if (E) {} else S ==> if (!E) S else {} (else can be omitted)
20 /// if (!E) S1 else S2 ==> if (E) S2 else S1 (unless previous rule applied)
21 ///
22 /// NEGATION:
23 ///
24 /// De Morgan's Laws are used to rewrite negations of logical operators so
25 /// negations are closer to the root:
26 ///
27 /// !x && !y --> !(x || y)
28 ///
29 /// This is to enable other rewrites, such as branch swapping in an if. In some
30 /// contexts, the rule is reversed because we do not expect to apply a rewrite
31 /// rule to the result. For example:
32 ///
33 /// z = !(x || y) ==> z = !x && !y;
34 ///
35 /// CONDITIONALS:
36 ///
37 /// Conditionals with boolean constant operands occur frequently in the input.
38 /// They can often the re-written to logical operators, for instance:
39 ///
40 /// if (x ? y : false) S1 else S2
41 /// ==>
42 /// if (x && y) S1 else S2
43 ///
44 /// Conditionals are tricky to rewrite when they occur out of boolean context.
45 /// Here we must apply more conservative rules, such as:
46 ///
47 /// x ? true : false ==> !!x
48 ///
49 /// If an operand is known to be a boolean, we can introduce a logical operator:
50 ///
51 /// x ? y : false ==> x && y (if y is known to be a boolean)
52 ///
53 /// The following sequence of rewrites demonstrates the merit of these rules:
54 ///
55 /// x ? (y ? true : false) : false
56 /// x ? !!y : false (double negation introduced by [toBoolean])
57 /// x && !!y (!!y validated by [isBooleanValued])
58 /// x && y (double negation removed by [putInBooleanContext])
59 ///
60 class LogicalRewriter extends Visitor<Statement, Expression> {
61
62 /// Statement to be executed next by natural fallthrough. Although fallthrough
63 /// is not introduced in this phase, we need to reason about fallthrough when
64 /// evaluating the benefit of swapping the branches of an [If].
65 Statement fallthrough;
66
67 void rewrite(FunctionDefinition definition) {
68 if (definition.isAbstract) return;
69
70 definition.body = visitStatement(definition.body);
71 }
72
73 Statement visitLabeledStatement(LabeledStatement node) {
74 Statement savedFallthrough = fallthrough;
75 fallthrough = node.next;
76 node.body = visitStatement(node.body);
77 fallthrough = savedFallthrough;
78 node.next = visitStatement(node.next);
79 return node;
80 }
81
82 Statement visitAssign(Assign node) {
83 node.definition = visitExpression(node.definition);
84 node.next = visitStatement(node.next);
85 return node;
86 }
87
88 Statement visitReturn(Return node) {
89 node.value = visitExpression(node.value);
90 return node;
91 }
92
93 Statement visitBreak(Break node) {
94 return node;
95 }
96
97 Statement visitContinue(Continue node) {
98 return node;
99 }
100
101 bool isFallthroughBreak(Statement node) {
102 return node is Break && node.target.binding.next == fallthrough;
103 }
104
105 Statement visitIf(If node) {
106 // If one of the branches is empty (i.e. just a fallthrough), then that
107 // branch should preferrably be the 'else' so we won't have to print it.
108 // In other words, we wish to perform this rewrite:
109 // if (E) {} else {S}
110 // ==>
111 // if (!E) {S}
112 // In the tree language, empty statements do not exist yet, so we must check
113 // if one branch contains a break that can be eliminated by fallthrough.
114
115 // Swap branches if then is a fallthrough break.
116 if (isFallthroughBreak(node.thenStatement)) {
117 node.condition = new Not(node.condition);
118 Statement tmp = node.thenStatement;
119 node.thenStatement = node.elseStatement;
120 node.elseStatement = tmp;
121 }
122
123 // Can the else part be eliminated?
124 // (Either due to the above swap or if the break was already there).
125 bool emptyElse = isFallthroughBreak(node.elseStatement);
126
127 node.condition = makeCondition(node.condition, true, liftNots: !emptyElse);
128 node.thenStatement = visitStatement(node.thenStatement);
129 node.elseStatement = visitStatement(node.elseStatement);
130
131 // If neither branch is empty, eliminate a negation in the condition
132 // if (!E) S1 else S2
133 // ==>
134 // if (E) S2 else S1
135 if (!emptyElse && node.condition is Not) {
136 node.condition = (node.condition as Not).operand;
137 Statement tmp = node.thenStatement;
138 node.thenStatement = node.elseStatement;
139 node.elseStatement = tmp;
140 }
141
142 return node;
143 }
144
145 Statement visitWhileTrue(WhileTrue node) {
146 node.body = visitStatement(node.body);
147 return node;
148 }
149
150 Statement visitWhileCondition(WhileCondition node) {
151 node.condition = makeCondition(node.condition, true, liftNots: false);
152 node.body = visitStatement(node.body);
153 node.next = visitStatement(node.next);
154 return node;
155 }
156
157 Statement visitExpressionStatement(ExpressionStatement node) {
158 node.expression = visitExpression(node.expression);
159 node.next = visitStatement(node.next);
160 return node;
161 }
162
163
164 Expression visitVariable(Variable node) {
165 return node;
166 }
167
168 Expression visitInvokeStatic(InvokeStatic node) {
169 _rewriteList(node.arguments);
170 return node;
171 }
172
173 Expression visitInvokeMethod(InvokeMethod node) {
174 node.receiver = visitExpression(node.receiver);
175 _rewriteList(node.arguments);
176 return node;
177 }
178
179 Expression visitInvokeSuperMethod(InvokeSuperMethod node) {
180 _rewriteList(node.arguments);
181 return node;
182 }
183
184 Expression visitInvokeConstructor(InvokeConstructor node) {
185 _rewriteList(node.arguments);
186 return node;
187 }
188
189 Expression visitConcatenateStrings(ConcatenateStrings node) {
190 _rewriteList(node.arguments);
191 return node;
192 }
193
194 Expression visitLiteralList(LiteralList node) {
195 _rewriteList(node.values);
196 return node;
197 }
198
199 Expression visitLiteralMap(LiteralMap node) {
200 node.entries.forEach((LiteralMapEntry entry) {
201 entry.key = visitExpression(entry.key);
202 entry.value = visitExpression(entry.value);
203 });
204 return node;
205 }
206
207 Expression visitTypeOperator(TypeOperator node) {
208 node.receiver = visitExpression(node.receiver);
209 return node;
210 }
211
212 Expression visitConstant(Constant node) {
213 return node;
214 }
215
216 Expression visitThis(This node) {
217 return node;
218 }
219
220 Expression visitReifyTypeVar(ReifyTypeVar node) {
221 return node;
222 }
223
224 Expression visitFunctionExpression(FunctionExpression node) {
225 new LogicalRewriter().rewrite(node.definition);
226 return node;
227 }
228
229 Statement visitFunctionDeclaration(FunctionDeclaration node) {
230 new LogicalRewriter().rewrite(node.definition);
231 node.next = visitStatement(node.next);
232 return node;
233 }
234
235 Expression visitNot(Not node) {
236 return toBoolean(makeCondition(node.operand, false, liftNots: false));
237 }
238
239 Expression visitConditional(Conditional node) {
240 // node.condition will be visited after the then and else parts, because its
241 // polarity depends on what rewrite we use.
242 node.thenExpression = visitExpression(node.thenExpression);
243 node.elseExpression = visitExpression(node.elseExpression);
244
245 // In the following, we must take care not to eliminate or introduce a
246 // boolean conversion.
247
248 // x ? true : false --> !!x
249 if (isTrue(node.thenExpression) && isFalse(node.elseExpression)) {
250 return toBoolean(makeCondition(node.condition, true, liftNots: false));
251 }
252 // x ? false : true --> !x
253 if (isFalse(node.thenExpression) && isTrue(node.elseExpression)) {
254 return toBoolean(makeCondition(node.condition, false, liftNots: false));
255 }
256
257 // x ? y : false ==> x && y (if y is known to be a boolean)
258 if (isBooleanValued(node.thenExpression) && isFalse(node.elseExpression)) {
259 return new LogicalOperator.and(
260 makeCondition(node.condition, true, liftNots:false),
261 putInBooleanContext(node.thenExpression));
262 }
263 // x ? y : true ==> !x || y (if y is known to be a boolean)
264 if (isBooleanValued(node.thenExpression) && isTrue(node.elseExpression)) {
265 return new LogicalOperator.or(
266 makeCondition(node.condition, false, liftNots: false),
267 putInBooleanContext(node.thenExpression));
268 }
269 // x ? true : y ==> x || y (if y if known to be boolean)
270 if (isBooleanValued(node.elseExpression) && isTrue(node.thenExpression)) {
271 return new LogicalOperator.or(
272 makeCondition(node.condition, true, liftNots: false),
273 putInBooleanContext(node.elseExpression));
274 }
275 // x ? false : y ==> !x && y (if y is known to be a boolean)
276 if (isBooleanValued(node.elseExpression) && isFalse(node.thenExpression)) {
277 return new LogicalOperator.and(
278 makeCondition(node.condition, false, liftNots: false),
279 putInBooleanContext(node.elseExpression));
280 }
281
282 node.condition = makeCondition(node.condition, true);
283
284 // !x ? y : z ==> x ? z : y
285 if (node.condition is Not) {
286 node.condition = (node.condition as Not).operand;
287 Expression tmp = node.thenExpression;
288 node.thenExpression = node.elseExpression;
289 node.elseExpression = tmp;
290 }
291
292 return node;
293 }
294
295 Expression visitLogicalOperator(LogicalOperator node) {
296 node.left = makeCondition(node.left, true);
297 node.right = makeCondition(node.right, true);
298 return node;
299 }
300
301 /// True if the given expression is known to evaluate to a boolean.
302 /// This will not recursively traverse [Conditional] expressions, but if
303 /// applied to the result of [visitExpression] conditionals will have been
304 /// rewritten anyway.
305 bool isBooleanValued(Expression e) {
306 return isTrue(e) || isFalse(e) || e is Not || e is LogicalOperator;
307 }
308
309 /// Rewrite an expression that was originally processed in a non-boolean
310 /// context.
311 Expression putInBooleanContext(Expression e) {
312 if (e is Not && e.operand is Not) {
313 return (e.operand as Not).operand;
314 } else {
315 return e;
316 }
317 }
318
319 /// Forces a boolean conversion of the given expression.
320 Expression toBoolean(Expression e) {
321 if (isBooleanValued(e))
322 return e;
323 else
324 return new Not(new Not(e));
325 }
326
327 /// Creates an equivalent boolean expression. The expression must occur in a
328 /// context where its result is immediately subject to boolean conversion.
329 /// If [polarity] if false, the negated condition will be created instead.
330 /// If [liftNots] is true (default) then Not expressions will be lifted toward
331 /// the root the condition so they can be eliminated by the caller.
332 Expression makeCondition(Expression e, bool polarity, {bool liftNots:true}) {
333 if (e is Not) {
334 // !!E ==> E
335 return makeCondition(e.operand, !polarity, liftNots: liftNots);
336 }
337 if (e is LogicalOperator) {
338 // If polarity=false, then apply the rewrite !(x && y) ==> !x || !y
339 e.left = makeCondition(e.left, polarity);
340 e.right = makeCondition(e.right, polarity);
341 if (!polarity) {
342 e.isAnd = !e.isAnd;
343 }
344 // !x && !y ==> !(x || y) (only if lifting nots)
345 if (e.left is Not && e.right is Not && liftNots) {
346 e.left = (e.left as Not).operand;
347 e.right = (e.right as Not).operand;
348 e.isAnd = !e.isAnd;
349 return new Not(e);
350 }
351 return e;
352 }
353 if (e is Conditional) {
354 // Handle polarity by: !(x ? y : z) ==> x ? !y : !z
355 // Rewrite individual branches now. The condition will be rewritten
356 // when we know what polarity to use (depends on which rewrite is used).
357 e.thenExpression = makeCondition(e.thenExpression, polarity);
358 e.elseExpression = makeCondition(e.elseExpression, polarity);
359
360 // x ? true : false ==> x
361 if (isTrue(e.thenExpression) && isFalse(e.elseExpression)) {
362 return makeCondition(e.condition, true, liftNots: liftNots);
363 }
364 // x ? false : true ==> !x
365 if (isFalse(e.thenExpression) && isTrue(e.elseExpression)) {
366 return makeCondition(e.condition, false, liftNots: liftNots);
367 }
368 // x ? true : y ==> x || y
369 if (isTrue(e.thenExpression)) {
370 return makeOr(makeCondition(e.condition, true),
371 e.elseExpression,
372 liftNots: liftNots);
373 }
374 // x ? false : y ==> !x && y
375 if (isFalse(e.thenExpression)) {
376 return makeAnd(makeCondition(e.condition, false),
377 e.elseExpression,
378 liftNots: liftNots);
379 }
380 // x ? y : true ==> !x || y
381 if (isTrue(e.elseExpression)) {
382 return makeOr(makeCondition(e.condition, false),
383 e.thenExpression,
384 liftNots: liftNots);
385 }
386 // x ? y : false ==> x && y
387 if (isFalse(e.elseExpression)) {
388 return makeAnd(makeCondition(e.condition, true),
389 e.thenExpression,
390 liftNots: liftNots);
391 }
392
393 e.condition = makeCondition(e.condition, true);
394
395 // !x ? y : z ==> x ? z : y
396 if (e.condition is Not) {
397 e.condition = (e.condition as Not).operand;
398 Expression tmp = e.thenExpression;
399 e.thenExpression = e.elseExpression;
400 e.elseExpression = tmp;
401 }
402 // x ? !y : !z ==> !(x ? y : z) (only if lifting nots)
403 if (e.thenExpression is Not && e.elseExpression is Not && liftNots) {
404 e.thenExpression = (e.thenExpression as Not).operand;
405 e.elseExpression = (e.elseExpression as Not).operand;
406 return new Not(e);
407 }
408 return e;
409 }
410 if (e is Constant && e.value.isBool) {
411 // !true ==> false
412 if (!polarity) {
413 values.BoolConstantValue value = e.value;
414 return new Constant.primitive(value.negate());
415 }
416 return e;
417 }
418 e = visitExpression(e);
419 return polarity ? e : new Not(e);
420 }
421
422 bool isTrue(Expression e) {
423 return e is Constant && e.value.isTrue;
424 }
425
426 bool isFalse(Expression e) {
427 return e is Constant && e.value.isFalse;
428 }
429
430 Expression makeAnd(Expression e1, Expression e2, {bool liftNots: true}) {
431 if (e1 is Not && e2 is Not && liftNots) {
432 return new Not(new LogicalOperator.or(e1.operand, e2.operand));
433 } else {
434 return new LogicalOperator.and(e1, e2);
435 }
436 }
437
438 Expression makeOr(Expression e1, Expression e2, {bool liftNots: true}) {
439 if (e1 is Not && e2 is Not && liftNots) {
440 return new Not(new LogicalOperator.and(e1.operand, e2.operand));
441 } else {
442 return new LogicalOperator.or(e1, e2);
443 }
444 }
445
446 /// Destructively updates each entry of [l] with the result of visiting it.
447 void _rewriteList(List<Expression> l) {
448 for (int i = 0; i < l.length; i++) {
449 l[i] = visitExpression(l[i]);
450 }
451 }
452 }
453
OLDNEW
« no previous file with comments | « pkg/compiler/lib/src/dart_backend/dart_backend.dart ('k') | pkg/compiler/lib/src/dart_backend/loop_rewriter.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698