1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit-test/tests/v8-v5/check-richards.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,536 @@
1.4 +// Copyright 2006-2008 the V8 project authors. All rights reserved.
1.5 +// Redistribution and use in source and binary forms, with or without
1.6 +// modification, are permitted provided that the following conditions are
1.7 +// met:
1.8 +//
1.9 +// * Redistributions of source code must retain the above copyright
1.10 +// notice, this list of conditions and the following disclaimer.
1.11 +// * Redistributions in binary form must reproduce the above
1.12 +// copyright notice, this list of conditions and the following
1.13 +// disclaimer in the documentation and/or other materials provided
1.14 +// with the distribution.
1.15 +// * Neither the name of Google Inc. nor the names of its
1.16 +// contributors may be used to endorse or promote products derived
1.17 +// from this software without specific prior written permission.
1.18 +//
1.19 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.20 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.21 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.22 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.23 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.24 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.25 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.26 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.27 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.28 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.29 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.30 +
1.31 +
1.32 +// This is a JavaScript implementation of the Richards
1.33 +// benchmark from:
1.34 +//
1.35 +// http://www.cl.cam.ac.uk/~mr10/Bench.html
1.36 +//
1.37 +// The benchmark was originally implemented in BCPL by
1.38 +// Martin Richards.
1.39 +
1.40 +
1.41 +//var Richards = new BenchmarkSuite('Richards', 34886, [
1.42 +// new Benchmark("Richards", runRichards)
1.43 +//]);
1.44 +
1.45 +
1.46 +/**
1.47 + * The Richards benchmark simulates the task dispatcher of an
1.48 + * operating system.
1.49 + **/
1.50 +function runRichards() {
1.51 + var scheduler = new Scheduler();
1.52 + scheduler.addIdleTask(ID_IDLE, 0, null, COUNT);
1.53 +
1.54 + var queue = new Packet(null, ID_WORKER, KIND_WORK);
1.55 + queue = new Packet(queue, ID_WORKER, KIND_WORK);
1.56 + scheduler.addWorkerTask(ID_WORKER, 1000, queue);
1.57 +
1.58 + queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE);
1.59 + queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE);
1.60 + queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE);
1.61 + scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue);
1.62 +
1.63 + queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE);
1.64 + queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE);
1.65 + queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE);
1.66 + scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue);
1.67 +
1.68 + scheduler.addDeviceTask(ID_DEVICE_A, 4000, null);
1.69 +
1.70 + scheduler.addDeviceTask(ID_DEVICE_B, 5000, null);
1.71 +
1.72 + scheduler.schedule();
1.73 +
1.74 + assertEq(scheduler.queueCount, EXPECTED_QUEUE_COUNT);
1.75 + assertEq(scheduler.holdCount, EXPECTED_HOLD_COUNT);
1.76 +}
1.77 +
1.78 +var COUNT = 1000;
1.79 +
1.80 +/**
1.81 + * These two constants specify how many times a packet is queued and
1.82 + * how many times a task is put on hold in a correct run of richards.
1.83 + * They don't have any meaning a such but are characteristic of a
1.84 + * correct run so if the actual queue or hold count is different from
1.85 + * the expected there must be a bug in the implementation.
1.86 + **/
1.87 +var EXPECTED_QUEUE_COUNT = 2322;
1.88 +var EXPECTED_HOLD_COUNT = 928;
1.89 +
1.90 +
1.91 +/**
1.92 + * A scheduler can be used to schedule a set of tasks based on their relative
1.93 + * priorities. Scheduling is done by maintaining a list of task control blocks
1.94 + * which holds tasks and the data queue they are processing.
1.95 + * @constructor
1.96 + */
1.97 +function Scheduler() {
1.98 + this.queueCount = 0;
1.99 + this.holdCount = 0;
1.100 + this.blocks = new Array(NUMBER_OF_IDS);
1.101 + this.list = null;
1.102 + this.currentTcb = null;
1.103 + this.currentId = null;
1.104 +}
1.105 +
1.106 +var ID_IDLE = 0;
1.107 +var ID_WORKER = 1;
1.108 +var ID_HANDLER_A = 2;
1.109 +var ID_HANDLER_B = 3;
1.110 +var ID_DEVICE_A = 4;
1.111 +var ID_DEVICE_B = 5;
1.112 +var NUMBER_OF_IDS = 6;
1.113 +
1.114 +var KIND_DEVICE = 0;
1.115 +var KIND_WORK = 1;
1.116 +
1.117 +/**
1.118 + * Add an idle task to this scheduler.
1.119 + * @param {int} id the identity of the task
1.120 + * @param {int} priority the task's priority
1.121 + * @param {Packet} queue the queue of work to be processed by the task
1.122 + * @param {int} count the number of times to schedule the task
1.123 + */
1.124 +Scheduler.prototype.addIdleTask = function (id, priority, queue, count) {
1.125 + this.addRunningTask(id, priority, queue, new IdleTask(this, 1, count));
1.126 +};
1.127 +
1.128 +/**
1.129 + * Add a work task to this scheduler.
1.130 + * @param {int} id the identity of the task
1.131 + * @param {int} priority the task's priority
1.132 + * @param {Packet} queue the queue of work to be processed by the task
1.133 + */
1.134 +Scheduler.prototype.addWorkerTask = function (id, priority, queue) {
1.135 + this.addTask(id, priority, queue, new WorkerTask(this, ID_HANDLER_A, 0));
1.136 +};
1.137 +
1.138 +/**
1.139 + * Add a handler task to this scheduler.
1.140 + * @param {int} id the identity of the task
1.141 + * @param {int} priority the task's priority
1.142 + * @param {Packet} queue the queue of work to be processed by the task
1.143 + */
1.144 +Scheduler.prototype.addHandlerTask = function (id, priority, queue) {
1.145 + this.addTask(id, priority, queue, new HandlerTask(this));
1.146 +};
1.147 +
1.148 +/**
1.149 + * Add a handler task to this scheduler.
1.150 + * @param {int} id the identity of the task
1.151 + * @param {int} priority the task's priority
1.152 + * @param {Packet} queue the queue of work to be processed by the task
1.153 + */
1.154 +Scheduler.prototype.addDeviceTask = function (id, priority, queue) {
1.155 + this.addTask(id, priority, queue, new DeviceTask(this))
1.156 +};
1.157 +
1.158 +/**
1.159 + * Add the specified task and mark it as running.
1.160 + * @param {int} id the identity of the task
1.161 + * @param {int} priority the task's priority
1.162 + * @param {Packet} queue the queue of work to be processed by the task
1.163 + * @param {Task} task the task to add
1.164 + */
1.165 +Scheduler.prototype.addRunningTask = function (id, priority, queue, task) {
1.166 + this.addTask(id, priority, queue, task);
1.167 + this.currentTcb.setRunning();
1.168 +};
1.169 +
1.170 +/**
1.171 + * Add the specified task to this scheduler.
1.172 + * @param {int} id the identity of the task
1.173 + * @param {int} priority the task's priority
1.174 + * @param {Packet} queue the queue of work to be processed by the task
1.175 + * @param {Task} task the task to add
1.176 + */
1.177 +Scheduler.prototype.addTask = function (id, priority, queue, task) {
1.178 + this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task);
1.179 + this.list = this.currentTcb;
1.180 + this.blocks[id] = this.currentTcb;
1.181 +};
1.182 +
1.183 +/**
1.184 + * Execute the tasks managed by this scheduler.
1.185 + */
1.186 +Scheduler.prototype.schedule = function () {
1.187 + this.currentTcb = this.list;
1.188 + while (this.currentTcb != null) {
1.189 + if (this.currentTcb.isHeldOrSuspended()) {
1.190 + this.currentTcb = this.currentTcb.link;
1.191 + } else {
1.192 + this.currentId = this.currentTcb.id;
1.193 + this.currentTcb = this.currentTcb.run();
1.194 + }
1.195 + }
1.196 +};
1.197 +
1.198 +/**
1.199 + * Release a task that is currently blocked and return the next block to run.
1.200 + * @param {int} id the id of the task to suspend
1.201 + */
1.202 +Scheduler.prototype.release = function (id) {
1.203 + var tcb = this.blocks[id];
1.204 + if (tcb == null) return tcb;
1.205 + tcb.markAsNotHeld();
1.206 + if (tcb.priority > this.currentTcb.priority) {
1.207 + return tcb;
1.208 + } else {
1.209 + return this.currentTcb;
1.210 + }
1.211 +};
1.212 +
1.213 +/**
1.214 + * Block the currently executing task and return the next task control block
1.215 + * to run. The blocked task will not be made runnable until it is explicitly
1.216 + * released, even if new work is added to it.
1.217 + */
1.218 +Scheduler.prototype.holdCurrent = function () {
1.219 + this.holdCount++;
1.220 + this.currentTcb.markAsHeld();
1.221 + return this.currentTcb.link;
1.222 +};
1.223 +
1.224 +/**
1.225 + * Suspend the currently executing task and return the next task control block
1.226 + * to run. If new work is added to the suspended task it will be made runnable.
1.227 + */
1.228 +Scheduler.prototype.suspendCurrent = function () {
1.229 + this.currentTcb.markAsSuspended();
1.230 + return this.currentTcb;
1.231 +};
1.232 +
1.233 +/**
1.234 + * Add the specified packet to the end of the worklist used by the task
1.235 + * associated with the packet and make the task runnable if it is currently
1.236 + * suspended.
1.237 + * @param {Packet} packet the packet to add
1.238 + */
1.239 +Scheduler.prototype.queue = function (packet) {
1.240 + var t = this.blocks[packet.id];
1.241 + if (t == null) return t;
1.242 + this.queueCount++;
1.243 + packet.link = null;
1.244 + packet.id = this.currentId;
1.245 + return t.checkPriorityAdd(this.currentTcb, packet);
1.246 +};
1.247 +
1.248 +/**
1.249 + * A task control block manages a task and the queue of work packages associated
1.250 + * with it.
1.251 + * @param {TaskControlBlock} link the preceding block in the linked block list
1.252 + * @param {int} id the id of this block
1.253 + * @param {int} priority the priority of this block
1.254 + * @param {Packet} queue the queue of packages to be processed by the task
1.255 + * @param {Task} task the task
1.256 + * @constructor
1.257 + */
1.258 +function TaskControlBlock(link, id, priority, queue, task) {
1.259 + this.link = link;
1.260 + this.id = id;
1.261 + this.priority = priority;
1.262 + this.queue = queue;
1.263 + this.task = task;
1.264 + if (queue == null) {
1.265 + this.state = STATE_SUSPENDED;
1.266 + } else {
1.267 + this.state = STATE_SUSPENDED_RUNNABLE;
1.268 + }
1.269 +}
1.270 +
1.271 +/**
1.272 + * The task is running and is currently scheduled.
1.273 + */
1.274 +var STATE_RUNNING = 0;
1.275 +
1.276 +/**
1.277 + * The task has packets left to process.
1.278 + */
1.279 +var STATE_RUNNABLE = 1;
1.280 +
1.281 +/**
1.282 + * The task is not currently running. The task is not blocked as such and may
1.283 +* be started by the scheduler.
1.284 + */
1.285 +var STATE_SUSPENDED = 2;
1.286 +
1.287 +/**
1.288 + * The task is blocked and cannot be run until it is explicitly released.
1.289 + */
1.290 +var STATE_HELD = 4;
1.291 +
1.292 +var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE;
1.293 +var STATE_NOT_HELD = ~STATE_HELD;
1.294 +
1.295 +TaskControlBlock.prototype.setRunning = function () {
1.296 + this.state = STATE_RUNNING;
1.297 +};
1.298 +
1.299 +TaskControlBlock.prototype.markAsNotHeld = function () {
1.300 + this.state = this.state & STATE_NOT_HELD;
1.301 +};
1.302 +
1.303 +TaskControlBlock.prototype.markAsHeld = function () {
1.304 + this.state = this.state | STATE_HELD;
1.305 +};
1.306 +
1.307 +TaskControlBlock.prototype.isHeldOrSuspended = function () {
1.308 + return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
1.309 +};
1.310 +
1.311 +TaskControlBlock.prototype.markAsSuspended = function () {
1.312 + this.state = this.state | STATE_SUSPENDED;
1.313 +};
1.314 +
1.315 +TaskControlBlock.prototype.markAsRunnable = function () {
1.316 + this.state = this.state | STATE_RUNNABLE;
1.317 +};
1.318 +
1.319 +/**
1.320 + * Runs this task, if it is ready to be run, and returns the next task to run.
1.321 + */
1.322 +TaskControlBlock.prototype.run = function () {
1.323 + var packet;
1.324 + if (this.state == STATE_SUSPENDED_RUNNABLE) {
1.325 + packet = this.queue;
1.326 + this.queue = packet.link;
1.327 + if (this.queue == null) {
1.328 + this.state = STATE_RUNNING;
1.329 + } else {
1.330 + this.state = STATE_RUNNABLE;
1.331 + }
1.332 + } else {
1.333 + packet = null;
1.334 + }
1.335 + return this.task.run(packet);
1.336 +};
1.337 +
1.338 +/**
1.339 + * Adds a packet to the worklist of this block's task, marks this as runnable if
1.340 + * necessary, and returns the next runnable object to run (the one
1.341 + * with the highest priority).
1.342 + */
1.343 +TaskControlBlock.prototype.checkPriorityAdd = function (task, packet) {
1.344 + if (this.queue == null) {
1.345 + this.queue = packet;
1.346 + this.markAsRunnable();
1.347 + if (this.priority > task.priority) return this;
1.348 + } else {
1.349 + this.queue = packet.addTo(this.queue);
1.350 + }
1.351 + return task;
1.352 +};
1.353 +
1.354 +TaskControlBlock.prototype.toString = function () {
1.355 + return "tcb { " + this.task + "@" + this.state + " }";
1.356 +};
1.357 +
1.358 +/**
1.359 + * An idle task doesn't do any work itself but cycles control between the two
1.360 + * device tasks.
1.361 + * @param {Scheduler} scheduler the scheduler that manages this task
1.362 + * @param {int} v1 a seed value that controls how the device tasks are scheduled
1.363 + * @param {int} count the number of times this task should be scheduled
1.364 + * @constructor
1.365 + */
1.366 +function IdleTask(scheduler, v1, count) {
1.367 + this.scheduler = scheduler;
1.368 + this.v1 = v1;
1.369 + this.count = count;
1.370 +}
1.371 +
1.372 +IdleTask.prototype.run = function (packet) {
1.373 + this.count--;
1.374 + if (this.count == 0) return this.scheduler.holdCurrent();
1.375 + if ((this.v1 & 1) == 0) {
1.376 + this.v1 = this.v1 >> 1;
1.377 + return this.scheduler.release(ID_DEVICE_A);
1.378 + } else {
1.379 + this.v1 = (this.v1 >> 1) ^ 0xD008;
1.380 + return this.scheduler.release(ID_DEVICE_B);
1.381 + }
1.382 +};
1.383 +
1.384 +IdleTask.prototype.toString = function () {
1.385 + return "IdleTask"
1.386 +};
1.387 +
1.388 +/**
1.389 + * A task that suspends itself after each time it has been run to simulate
1.390 + * waiting for data from an external device.
1.391 + * @param {Scheduler} scheduler the scheduler that manages this task
1.392 + * @constructor
1.393 + */
1.394 +function DeviceTask(scheduler) {
1.395 + this.scheduler = scheduler;
1.396 + this.v1 = null;
1.397 +}
1.398 +
1.399 +DeviceTask.prototype.run = function (packet) {
1.400 + if (packet == null) {
1.401 + if (this.v1 == null) return this.scheduler.suspendCurrent();
1.402 + var v = this.v1;
1.403 + this.v1 = null;
1.404 + return this.scheduler.queue(v);
1.405 + } else {
1.406 + this.v1 = packet;
1.407 + return this.scheduler.holdCurrent();
1.408 + }
1.409 +};
1.410 +
1.411 +DeviceTask.prototype.toString = function () {
1.412 + return "DeviceTask";
1.413 +};
1.414 +
1.415 +/**
1.416 + * A task that manipulates work packets.
1.417 + * @param {Scheduler} scheduler the scheduler that manages this task
1.418 + * @param {int} v1 a seed used to specify how work packets are manipulated
1.419 + * @param {int} v2 another seed used to specify how work packets are manipulated
1.420 + * @constructor
1.421 + */
1.422 +function WorkerTask(scheduler, v1, v2) {
1.423 + this.scheduler = scheduler;
1.424 + this.v1 = v1;
1.425 + this.v2 = v2;
1.426 +}
1.427 +
1.428 +WorkerTask.prototype.run = function (packet) {
1.429 + if (packet == null) {
1.430 + return this.scheduler.suspendCurrent();
1.431 + } else {
1.432 + if (this.v1 == ID_HANDLER_A) {
1.433 + this.v1 = ID_HANDLER_B;
1.434 + } else {
1.435 + this.v1 = ID_HANDLER_A;
1.436 + }
1.437 + packet.id = this.v1;
1.438 + packet.a1 = 0;
1.439 + for (var i = 0; i < DATA_SIZE; i++) {
1.440 + this.v2++;
1.441 + if (this.v2 > 26) this.v2 = 1;
1.442 + packet.a2[i] = this.v2;
1.443 + }
1.444 + return this.scheduler.queue(packet);
1.445 + }
1.446 +};
1.447 +
1.448 +WorkerTask.prototype.toString = function () {
1.449 + return "WorkerTask";
1.450 +};
1.451 +
1.452 +/**
1.453 + * A task that manipulates work packets and then suspends itself.
1.454 + * @param {Scheduler} scheduler the scheduler that manages this task
1.455 + * @constructor
1.456 + */
1.457 +function HandlerTask(scheduler) {
1.458 + this.scheduler = scheduler;
1.459 + this.v1 = null;
1.460 + this.v2 = null;
1.461 +}
1.462 +
1.463 +HandlerTask.prototype.run = function (packet) {
1.464 + if (packet != null) {
1.465 + if (packet.kind == KIND_WORK) {
1.466 + this.v1 = packet.addTo(this.v1);
1.467 + } else {
1.468 + this.v2 = packet.addTo(this.v2);
1.469 + }
1.470 + }
1.471 + if (this.v1 != null) {
1.472 + var count = this.v1.a1;
1.473 + var v;
1.474 + if (count < DATA_SIZE) {
1.475 + if (this.v2 != null) {
1.476 + v = this.v2;
1.477 + this.v2 = this.v2.link;
1.478 + v.a1 = this.v1.a2[count];
1.479 + this.v1.a1 = count + 1;
1.480 + return this.scheduler.queue(v);
1.481 + }
1.482 + } else {
1.483 + v = this.v1;
1.484 + this.v1 = this.v1.link;
1.485 + return this.scheduler.queue(v);
1.486 + }
1.487 + }
1.488 + return this.scheduler.suspendCurrent();
1.489 +};
1.490 +
1.491 +HandlerTask.prototype.toString = function () {
1.492 + return "HandlerTask";
1.493 +};
1.494 +
1.495 +/* --- *
1.496 + * P a c k e t
1.497 + * --- */
1.498 +
1.499 +var DATA_SIZE = 4;
1.500 +
1.501 +/**
1.502 + * A simple package of data that is manipulated by the tasks. The exact layout
1.503 + * of the payload data carried by a packet is not importaint, and neither is the
1.504 + * nature of the work performed on packets by the tasks.
1.505 + *
1.506 + * Besides carrying data, packets form linked lists and are hence used both as
1.507 + * data and worklists.
1.508 + * @param {Packet} link the tail of the linked list of packets
1.509 + * @param {int} id an ID for this packet
1.510 + * @param {int} kind the type of this packet
1.511 + * @constructor
1.512 + */
1.513 +function Packet(link, id, kind) {
1.514 + this.link = link;
1.515 + this.id = id;
1.516 + this.kind = kind;
1.517 + this.a1 = 0;
1.518 + this.a2 = new Array(DATA_SIZE);
1.519 +}
1.520 +
1.521 +/**
1.522 + * Add this packet to the end of a worklist, and return the worklist.
1.523 + * @param {Packet} queue the worklist to add this packet to
1.524 + */
1.525 +Packet.prototype.addTo = function (queue) {
1.526 + this.link = null;
1.527 + if (queue == null) return this;
1.528 + var peek, next = queue;
1.529 + while ((peek = next.link) != null)
1.530 + next = peek;
1.531 + next.link = this;
1.532 + return queue;
1.533 +};
1.534 +
1.535 +Packet.prototype.toString = function () {
1.536 + return "Packet";
1.537 +};
1.538 +
1.539 +runRichards();
