[JSC] AI should not propagate AbstractValue relying on constant folding phase
[WebKit-https.git] / JSTests / microbenchmarks / richards-try-catch.js
1 // Copyright 2006-2008 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 //     * Redistributions of source code must retain the above copyright
7 //       notice, this list of conditions and the following disclaimer.
8 //     * Redistributions in binary form must reproduce the above
9 //       copyright notice, this list of conditions and the following
10 //       disclaimer in the documentation and/or other materials provided
11 //       with the distribution.
12 //     * Neither the name of Google Inc. nor the names of its
13 //       contributors may be used to endorse or promote products derived
14 //       from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28
29 // This is a JavaScript implementation of the Richards
30 // benchmark from:
31 //
32 //    http://www.cl.cam.ac.uk/~mr10/Bench.html
33 //
34 // The benchmark was originally implemented in BCPL by
35 // Martin Richards.
36
37
38 let __exceptionCounter = 0;
39 function randomException() {
40     __exceptionCounter++;
41     if (__exceptionCounter % 5000 === 0) {
42         throw new Error("rando");
43     }
44 }
45 noInline(randomException);
46
47 /**
48  * The Richards benchmark simulates the task dispatcher of an
49  * operating system.
50  **/
51 function runRichards() {
52     try {
53         var scheduler = new Scheduler();
54         scheduler.addIdleTask(ID_IDLE, 0, null, COUNT);
55
56         var queue = new Packet(null, ID_WORKER, KIND_WORK);
57         queue = new Packet(queue,  ID_WORKER, KIND_WORK);
58         scheduler.addWorkerTask(ID_WORKER, 1000, queue);
59
60         queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE);
61         queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
62         queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
63         scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue);
64
65         queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE);
66         queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
67         queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
68         scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue);
69
70         scheduler.addDeviceTask(ID_DEVICE_A, 4000, null);
71
72         scheduler.addDeviceTask(ID_DEVICE_B, 5000, null);
73
74         scheduler.schedule();
75
76         if (scheduler.queueCount != EXPECTED_QUEUE_COUNT ||
77                 scheduler.holdCount != EXPECTED_HOLD_COUNT) {
78             var msg =
79                 "Error during execution: queueCount = " + scheduler.queueCount +
80                 ", holdCount = " + scheduler.holdCount + ".";
81             throw new Error(msg);
82         }
83
84         randomException();
85     } catch(e) { }
86 }
87
88 var COUNT = 1000;
89
90 /**
91  * These two constants specify how many times a packet is queued and
92  * how many times a task is put on hold in a correct run of richards.
93  * They don't have any meaning a such but are characteristic of a
94  * correct run so if the actual queue or hold count is different from
95  * the expected there must be a bug in the implementation.
96  **/
97 var EXPECTED_QUEUE_COUNT = 2322;
98 var EXPECTED_HOLD_COUNT = 928;
99
100
101 /**
102  * A scheduler can be used to schedule a set of tasks based on their relative
103  * priorities.  Scheduling is done by maintaining a list of task control blocks
104  * which holds tasks and the data queue they are processing.
105  * @constructor
106  */
107 function Scheduler() {
108     try {
109         this.queueCount = 0;
110         this.holdCount = 0;
111         this.blocks = new Array(NUMBER_OF_IDS);
112         this.list = null;
113         this.currentTcb = null;
114         this.currentId = null;
115
116         randomException();
117     } catch(e) { }
118 }
119
120 var ID_IDLE       = 0;
121 var ID_WORKER     = 1;
122 var ID_HANDLER_A  = 2;
123 var ID_HANDLER_B  = 3;
124 var ID_DEVICE_A   = 4;
125 var ID_DEVICE_B   = 5;
126 var NUMBER_OF_IDS = 6;
127
128 var KIND_DEVICE   = 0;
129 var KIND_WORK     = 1;
130
131 /**
132  * Add an idle task to this scheduler.
133  * @param {int} id the identity of the task
134  * @param {int} priority the task's priority
135  * @param {Packet} queue the queue of work to be processed by the task
136  * @param {int} count the number of times to schedule the task
137  */
138 Scheduler.prototype.addIdleTask = function (id, priority, queue, count) {
139     try {
140         this.addRunningTask(id, priority, queue, new IdleTask(this, 1, count));
141         randomException();
142     } catch(e) { }
143 };
144
145 /**
146  * Add a work task to this scheduler.
147  * @param {int} id the identity of the task
148  * @param {int} priority the task's priority
149  * @param {Packet} queue the queue of work to be processed by the task
150  */
151 Scheduler.prototype.addWorkerTask = function (id, priority, queue) {
152     try {
153         this.addTask(id, priority, queue, new WorkerTask(this, ID_HANDLER_A, 0));
154         randomException();
155     } catch(e) { }
156 };
157
158 /**
159  * Add a handler task to this scheduler.
160  * @param {int} id the identity of the task
161  * @param {int} priority the task's priority
162  * @param {Packet} queue the queue of work to be processed by the task
163  */
164 Scheduler.prototype.addHandlerTask = function (id, priority, queue) {
165     try {
166         this.addTask(id, priority, queue, new HandlerTask(this));
167         randomException();
168     } catch(e) { }
169 };
170
171 /**
172  * Add a handler task to this scheduler.
173  * @param {int} id the identity of the task
174  * @param {int} priority the task's priority
175  * @param {Packet} queue the queue of work to be processed by the task
176  */
177 Scheduler.prototype.addDeviceTask = function (id, priority, queue) {
178     try {
179         this.addTask(id, priority, queue, new DeviceTask(this))
180         randomException();
181     } catch(e) { }
182 };
183
184 /**
185  * Add the specified task and mark it as running.
186  * @param {int} id the identity of the task
187  * @param {int} priority the task's priority
188  * @param {Packet} queue the queue of work to be processed by the task
189  * @param {Task} task the task to add
190  */
191 Scheduler.prototype.addRunningTask = function (id, priority, queue, task) {
192     try {
193         this.addTask(id, priority, queue, task);
194         this.currentTcb.setRunning();
195         randomException();
196     } catch(e) { }
197 };
198
199 /**
200  * Add the specified task to this scheduler.
201  * @param {int} id the identity of the task
202  * @param {int} priority the task's priority
203  * @param {Packet} queue the queue of work to be processed by the task
204  * @param {Task} task the task to add
205  */
206 Scheduler.prototype.addTask = function (id, priority, queue, task) {
207     try {
208         this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task);
209         this.list = this.currentTcb;
210         this.blocks[id] = this.currentTcb;
211         randomException();
212     } catch(e) { }
213 };
214
215 /**
216  * Execute the tasks managed by this scheduler.
217  */
218 Scheduler.prototype.schedule = function () {
219     this.currentTcb = this.list;
220     while (this.currentTcb != null) {
221         try {
222             if (this.currentTcb.isHeldOrSuspended()) {
223                 this.currentTcb = this.currentTcb.link;
224             } else {
225                 this.currentId = this.currentTcb.id;
226                 this.currentTcb = this.currentTcb.run();
227             }
228             randomException();
229         } catch(e) { }
230     }
231 };
232
233 /**
234  * Release a task that is currently blocked and return the next block to run.
235  * @param {int} id the id of the task to suspend
236  */
237 Scheduler.prototype.release = function (id) {
238     try {
239         var tcb = this.blocks[id];
240         if (tcb == null) return tcb;
241         tcb.markAsNotHeld();
242         randomException();
243     } catch(e) { }
244     try {
245         if (tcb.priority > this.currentTcb.priority) {
246             return tcb;
247         } else {
248             return this.currentTcb;
249         }
250     } catch(e) { }
251 };
252
253 /**
254  * Block the currently executing task and return the next task control block
255  * to run.  The blocked task will not be made runnable until it is explicitly
256  * released, even if new work is added to it.
257  */
258 Scheduler.prototype.holdCurrent = function () {
259     try {
260         this.holdCount++;
261         this.currentTcb.markAsHeld();
262         randomException();
263     } catch(e) { }
264     return this.currentTcb.link;
265 };
266
267 /**
268  * Suspend the currently executing task and return the next task control block
269  * to run.  If new work is added to the suspended task it will be made runnable.
270  */
271 Scheduler.prototype.suspendCurrent = function () {
272     try {
273         this.currentTcb.markAsSuspended();
274         randomException();
275     } catch(e) { }
276     try {
277         return this.currentTcb;
278     } catch(e) { }
279 };
280
281 /**
282  * Add the specified packet to the end of the worklist used by the task
283  * associated with the packet and make the task runnable if it is currently
284  * suspended.
285  * @param {Packet} packet the packet to add
286  */
287 Scheduler.prototype.queue = function (packet) {
288     try {
289         var t = this.blocks[packet.id];
290         if (t == null) return t;
291         this.queueCount++;
292         packet.link = null;
293         randomException();
294     } catch(e) { }
295     packet.id = this.currentId;
296     return t.checkPriorityAdd(this.currentTcb, packet);
297 };
298
299 /**
300  * A task control block manages a task and the queue of work packages associated
301  * with it.
302  * @param {TaskControlBlock} link the preceding block in the linked block list
303  * @param {int} id the id of this block
304  * @param {int} priority the priority of this block
305  * @param {Packet} queue the queue of packages to be processed by the task
306  * @param {Task} task the task
307  * @constructor
308  */
309 function TaskControlBlock(link, id, priority, queue, task) {
310     try {
311         this.link = link;
312         this.id = id;
313         this.priority = priority;
314         this.queue = queue;
315         this.task = task;
316         randomException();
317     } catch(e) { }
318     try {
319         if (queue == null) {
320             this.state = STATE_SUSPENDED;
321         } else {
322             this.state = STATE_SUSPENDED_RUNNABLE;
323         }
324         randomException();
325     } catch(e) { }
326 }
327
328 /**
329  * The task is running and is currently scheduled.
330  */
331 var STATE_RUNNING = 0;
332
333 /**
334  * The task has packets left to process.
335  */
336 var STATE_RUNNABLE = 1;
337
338 /**
339  * The task is not currently running.  The task is not blocked as such and may
340  * be started by the scheduler.
341  */
342 var STATE_SUSPENDED = 2;
343
344 /**
345  * The task is blocked and cannot be run until it is explicitly released.
346  */
347 var STATE_HELD = 4;
348
349 var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE;
350 var STATE_NOT_HELD = ~STATE_HELD;
351
352 TaskControlBlock.prototype.setRunning = function () {
353     try {
354         this.state = STATE_RUNNING;
355         randomException();
356     } catch(e){}
357 };
358
359 TaskControlBlock.prototype.markAsNotHeld = function () {
360     try {
361         this.state = this.state & STATE_NOT_HELD;
362         randomException();
363     } catch(e) { }
364 };
365
366 TaskControlBlock.prototype.markAsHeld = function () {
367     try {
368         this.state = this.state | STATE_HELD;
369         randomException();
370     } catch(e) { }
371 };
372
373 TaskControlBlock.prototype.isHeldOrSuspended = function () {
374     try {
375         randomException();
376         return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
377     } catch(e) { 
378         return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
379     }
380 };
381
382 TaskControlBlock.prototype.markAsSuspended = function () {
383     try {
384         randomException();
385         this.state = this.state | STATE_SUSPENDED;
386     } catch(e) { 
387         this.state = this.state | STATE_SUSPENDED;
388     }
389 };
390
391 TaskControlBlock.prototype.markAsRunnable = function () {
392     try {
393         randomException();
394         this.state = this.state | STATE_RUNNABLE;
395     } catch(e) {
396         this.state = this.state | STATE_RUNNABLE;
397     }
398 };
399
400 /**
401  * Runs this task, if it is ready to be run, and returns the next task to run.
402  */
403 TaskControlBlock.prototype.run = function () {
404     var packet;
405     try {
406         if (this.state == STATE_SUSPENDED_RUNNABLE) {
407             packet = this.queue;
408             this.queue = packet.link;
409             if (this.queue == null) {
410                 this.state = STATE_RUNNING;
411             } else {
412                 this.state = STATE_RUNNABLE;
413             }
414         } else {
415             packet = null;
416         }
417         randomException();
418     } catch(e) { }
419     return this.task.run(packet);
420 };
421
422 /**
423  * Adds a packet to the worklist of this block's task, marks this as runnable if
424  * necessary, and returns the next runnable object to run (the one
425  * with the highest priority).
426  */
427 TaskControlBlock.prototype.checkPriorityAdd = function (task, packet) {
428     try {
429         if (this.queue == null) {
430             this.queue = packet;
431             this.markAsRunnable();
432             if (this.priority > task.priority) return this;
433         } else {
434             this.queue = packet.addTo(this.queue);
435         }
436
437         randomException();
438         return task;
439     } catch(e) { 
440         return task;
441     }
442 };
443
444 TaskControlBlock.prototype.toString = function () {
445     try {
446         randomException();
447         return "tcb { " + this.task + "@" + this.state + " }";
448     } catch(e) {
449         return "tcb { " + this.task + "@" + this.state + " }";
450     }
451 };
452
453 /**
454  * An idle task doesn't do any work itself but cycles control between the two
455  * device tasks.
456  * @param {Scheduler} scheduler the scheduler that manages this task
457  * @param {int} v1 a seed value that controls how the device tasks are scheduled
458  * @param {int} count the number of times this task should be scheduled
459  * @constructor
460  */
461 function IdleTask(scheduler, v1, count) {
462     try {
463         this.scheduler = scheduler;
464         this.v1 = v1;
465         randomException();
466         this.count = count;
467     } catch(e) {
468         this.count = count;
469     }
470 }
471
472 IdleTask.prototype.run = function (packet) {
473     try {
474         this.count--;
475         if (this.count == 0) return this.scheduler.holdCurrent();
476         randomException();
477     } catch(e) { }
478
479     try {
480         if ((this.v1 & 1) == 0) {
481             this.v1 = this.v1 >> 1;
482             return this.scheduler.release(ID_DEVICE_A);
483         } else {
484             this.v1 = (this.v1 >> 1) ^ 0xD008;
485             return this.scheduler.release(ID_DEVICE_B);
486         }
487     } catch(e) { }
488 };
489
490 IdleTask.prototype.toString = function () {
491     try {
492         randomException();
493         return "IdleTask"
494     } catch(e) {
495         return "IdleTask"
496     }
497 };
498
499 /**
500  * A task that suspends itself after each time it has been run to simulate
501  * waiting for data from an external device.
502  * @param {Scheduler} scheduler the scheduler that manages this task
503  * @constructor
504  */
505 function DeviceTask(scheduler) {
506     try {
507         this.scheduler = scheduler;
508         this.v1 = null;
509         randomException();
510     } catch(e) { }
511 }
512
513 DeviceTask.prototype.run = function (packet) {
514     if (packet == null) {
515         try {
516             if (this.v1 == null) return this.scheduler.suspendCurrent();
517             var v = this.v1;
518             this.v1 = null;
519             randomException();
520         } catch(e) { }
521         return this.scheduler.queue(v);
522     } else {
523         try {
524             this.v1 = packet;
525             randomException();
526         } catch(e) { }
527         return this.scheduler.holdCurrent();
528     }
529 };
530
531 DeviceTask.prototype.toString = function () {
532     try {
533         randomException();
534         return "DeviceTask";
535     } catch(e) { }
536 };
537
538 /**
539  * A task that manipulates work packets.
540  * @param {Scheduler} scheduler the scheduler that manages this task
541  * @param {int} v1 a seed used to specify how work packets are manipulated
542  * @param {int} v2 another seed used to specify how work packets are manipulated
543  * @constructor
544  */
545 function WorkerTask(scheduler, v1, v2) {
546     try {
547         this.scheduler = scheduler;
548         this.v1 = v1;
549         this.v2 = v2;
550         randomException();
551     } catch(e) { }
552 }
553
554 WorkerTask.prototype.run = function (packet) {
555     if (packet == null) {
556         return this.scheduler.suspendCurrent();
557     } else {
558         try {
559             if (this.v1 == ID_HANDLER_A) {
560                 this.v1 = ID_HANDLER_B;
561             } else {
562                 this.v1 = ID_HANDLER_A;
563             }
564             packet.id = this.v1;
565             packet.a1 = 0;
566             randomException();
567         } catch(e) { }
568         for (var i = 0; i < DATA_SIZE; i++) {
569             try {
570                 this.v2++;
571                 if (this.v2 > 26) this.v2 = 1;
572                 packet.a2[i] = this.v2;
573                 randomException();
574             } catch(e) { }
575         }
576         return this.scheduler.queue(packet);
577     }
578 };
579
580 WorkerTask.prototype.toString = function () {
581     try {
582         return "WorkerTask";
583     } catch(e) { }
584 };
585
586 /**
587  * A task that manipulates work packets and then suspends itself.
588  * @param {Scheduler} scheduler the scheduler that manages this task
589  * @constructor
590  */
591 function HandlerTask(scheduler) {
592     try {
593         this.scheduler = scheduler;
594         this.v1 = null;
595         this.v2 = null;
596         randomException();
597     } catch(e) { }
598 }
599
600 HandlerTask.prototype.run = function (packet) {
601     try {
602         if (packet != null) {
603             if (packet.kind == KIND_WORK) {
604                 this.v1 = packet.addTo(this.v1);
605             } else {
606                 this.v2 = packet.addTo(this.v2);
607             }
608         }
609         randomException();
610     } catch(e) { }
611
612     try {
613         if (this.v1 != null) {
614             var count = this.v1.a1;
615             var v;
616             if (count < DATA_SIZE) {
617                 if (this.v2 != null) {
618                     v = this.v2;
619                     this.v2 = this.v2.link;
620                     v.a1 = this.v1.a2[count];
621                     this.v1.a1 = count + 1;
622                     return this.scheduler.queue(v);
623                 }
624             } else {
625                 v = this.v1;
626                 this.v1 = this.v1.link;
627                 return this.scheduler.queue(v);
628             }
629         }
630         randomException();
631     } catch(e) { }
632     return this.scheduler.suspendCurrent();
633 };
634
635 HandlerTask.prototype.toString = function () {
636     try {
637         return "HandlerTask";
638     } catch(e) { }
639 };
640
641 /* --- *
642  * P a c k e t
643  * --- */
644
645 var DATA_SIZE = 4;
646
647 /**
648  * A simple package of data that is manipulated by the tasks.  The exact layout
649  * of the payload data carried by a packet is not importaint, and neither is the
650  * nature of the work performed on packets by the tasks.
651  *
652  * Besides carrying data, packets form linked lists and are hence used both as
653  * data and worklists.
654  * @param {Packet} link the tail of the linked list of packets
655  * @param {int} id an ID for this packet
656  * @param {int} kind the type of this packet
657  * @constructor
658  */
659 function Packet(link, id, kind) {
660     try {
661         this.link = link;
662         this.id = id;
663         this.kind = kind;
664         this.a1 = 0;
665         this.a2 = new Array(DATA_SIZE);
666         randomException();
667     } catch(e) { }
668 }
669
670 /**
671  * Add this packet to the end of a worklist, and return the worklist.
672  * @param {Packet} queue the worklist to add this packet to
673  */
674 Packet.prototype.addTo = function (queue) {
675     this.link = null;
676     if (queue == null) return this;
677     var peek, next = queue;
678     while ((peek = next.link) != null) {
679         try {
680             next = peek;
681             randomException();
682         } catch(e) { }
683     }
684     next.link = this;
685     return queue;
686 };
687
688 Packet.prototype.toString = function () {
689     try {
690         return "Packet";
691     } catch(e) { }
692 };
693
694 for (let i = 0; i < 350; ++i)
695   runRichards();