diff options
author | Alon Zakai <alonzakai@gmail.com> | 2013-06-11 09:46:33 -0700 |
---|---|---|
committer | Alon Zakai <alonzakai@gmail.com> | 2013-06-11 09:46:33 -0700 |
commit | 0ad87244178badf26cd5c8e0ed88116e87026472 (patch) | |
tree | db19d53d4548391d316fec33954ed7d5d3cfb68b /src | |
parent | a1eb425371aa310e074b06d80d56adf71d6f5383 (diff) | |
parent | 886e3158cf5d95a2c2721e5eb9a1c3ac4461f805 (diff) |
Merge branch 'incoming'
Diffstat (limited to 'src')
-rw-r--r-- | src/analyzer.js | 12 | ||||
-rw-r--r-- | src/headless.js | 14 | ||||
-rw-r--r-- | src/library.js | 45 | ||||
-rw-r--r-- | src/library_sdl.js | 116 | ||||
-rw-r--r-- | src/modules.js | 1 | ||||
-rw-r--r-- | src/parseTools.js | 2 | ||||
-rw-r--r-- | src/relooper/Relooper.cpp | 95 | ||||
-rw-r--r-- | src/relooper/Relooper.h | 1 | ||||
-rw-r--r-- | src/relooper/test.cpp | 27 | ||||
-rw-r--r-- | src/relooper/test.txt | 17 | ||||
-rw-r--r-- | src/relooper/test3.txt | 4 | ||||
-rw-r--r-- | src/relooper/test_inf.txt | 648 | ||||
-rw-r--r-- | src/settings.js | 3 | ||||
-rw-r--r-- | src/shell.js | 4 |
14 files changed, 591 insertions, 398 deletions
diff --git a/src/analyzer.js b/src/analyzer.js index 2cc46ab6..de9a7940 100644 --- a/src/analyzer.js +++ b/src/analyzer.js @@ -20,7 +20,7 @@ var BRANCH_INVOKE = set('branch', 'invoke'); var LABEL_ENDERS = set('branch', 'return', 'switch'); var SIDE_EFFECT_CAUSERS = set('call', 'invoke', 'atomic'); var UNUNFOLDABLE = set('value', 'structvalue', 'type', 'phiparam'); -var I64_DOUBLE_FLIP = { i64: 'double', double: 'i64' }; +var SHADOW_FLIP = { i64: 'double', double: 'i64' }; //, i32: 'float', float: 'i32' }; // Analyzer @@ -124,13 +124,13 @@ function analyzer(data, sidePass) { var lines = label.lines; for (var i = 0; i < lines.length; i++) { var line = lines[i]; - if (line.intertype == 'bitcast' && line.type in I64_DOUBLE_FLIP) { + if (line.intertype == 'bitcast' && line.type in SHADOW_FLIP) { has = true; } } }); if (!has) return; - // there are i64<-->double bitcasts, create shadows for everything + // there are integer<->floating-point bitcasts, create shadows for everything var shadowed = {}; func.labels.forEach(function(label) { var lines = label.lines; @@ -138,11 +138,11 @@ function analyzer(data, sidePass) { while (i < lines.length) { var lines = label.lines; var line = lines[i]; - if (line.intertype == 'load' && line.type in I64_DOUBLE_FLIP) { + if (line.intertype == 'load' && line.type in SHADOW_FLIP) { if (line.pointer.intertype != 'value') { i++; continue } // TODO shadowed[line.assignTo] = 1; var shadow = line.assignTo + '$$SHADOW'; - var flip = I64_DOUBLE_FLIP[line.type]; + var flip = SHADOW_FLIP[line.type]; lines.splice(i + 1, 0, { // if necessary this element will be legalized in the next phase tokens: null, indent: 2, @@ -171,7 +171,7 @@ function analyzer(data, sidePass) { var lines = label.lines; for (var i = 0; i < lines.length; i++) { var line = lines[i]; - if (line.intertype == 'bitcast' && line.type in I64_DOUBLE_FLIP && line.ident in shadowed) { + if (line.intertype == 'bitcast' && line.type in SHADOW_FLIP && line.ident in shadowed) { var shadow = line.ident + '$$SHADOW'; line.params[0].ident = shadow; line.params[0].type = line.type; diff --git a/src/headless.js b/src/headless.js index d81fb5a3..097a42f7 100644 --- a/src/headless.js +++ b/src/headless.js @@ -4,6 +4,20 @@ // TODO: sync from bananabread headless.js var window = { + eventListeners: {}, + addEventListener: function(id, func) { + var listeners = this.eventListeners[id]; + if (!listeners) { + listeners = this.eventListeners[id] = []; + } + listeners.push(func); + }, + callEventListeners: function(id) { + var listeners = this.eventListeners[id]; + if (listeners) { + listeners.forEach(function(listener) { listener() }); + } + }, location: { toString: function() { return '%s'; diff --git a/src/library.js b/src/library.js index ab27ed35..f958a436 100644 --- a/src/library.js +++ b/src/library.js @@ -2621,7 +2621,7 @@ LibraryManager.library = { var curr = 0; var buffer = []; // Read characters according to the format. floats are trickier, they may be in an unfloat state in the middle, then be a valid float later - if (type == 'f' || type == 'e' || type == 'g' || + if (type == 'f' || type == 'e' || type == 'g' || type == 'F' || type == 'E' || type == 'G') { var last = 0; next = get(); @@ -3965,8 +3965,8 @@ LibraryManager.library = { {{{ makeGetValue('str+1', 0, 'i8') }}} == {{{ charCode('X') }}}) { str += 2; } - } - } + } + } if (!finalBase) finalBase = 10; // Get digits. @@ -4020,7 +4020,7 @@ LibraryManager.library = { var isNegative = false; // Skip space. while (_isspace({{{ makeGetValue('str', 0, 'i8') }}})) str++; - + // Check for a plus/minus sign. if ({{{ makeGetValue('str', 0, 'i8') }}} == {{{ charCode('-') }}}) { str++; @@ -4049,8 +4049,8 @@ LibraryManager.library = { {{{ makeGetValue('str+1', 0, 'i8') }}} == {{{ charCode('X') }}}) { str += 2; } - } - } + } + } if (!finalBase) finalBase = 10; start = str; @@ -5732,7 +5732,8 @@ LibraryManager.library = { llround: 'round', llroundf: 'round', rint: function(x) { - return (x > 0) ? -Math.round(-x) : Math.round(x); + if (Math.abs(x % 1) !== 0.5) return Math.round(x); + return x + x % 2 + ((x < 0) ? 1 : -1); }, rintf: 'rint', lrint: 'rint', @@ -6353,7 +6354,8 @@ LibraryManager.library = { // Note that we need to emulate functions that use setjmp, and also to create // a new label we can return to. Emulation make such functions slower, this // can be alleviated by making a new function containing just the setjmp - // related functionality so the slowdown is more limited. + // related functionality so the slowdown is more limited - you may need + // to prevent inlining to keep this isolated, try __attribute__((noinline)) // ========================================================================== saveSetjmp__asm: true, @@ -6373,11 +6375,11 @@ LibraryManager.library = { setjmpId = (setjmpId+1)|0; {{{ makeSetValueAsm('env', '0', 'setjmpId', 'i32') }}}; while ((i|0) < {{{ 2*MAX_SETJMPS }}}) { - if ({{{ makeGetValueAsm('table', 'i*4', 'i32') }}} == 0) { - {{{ makeSetValueAsm('table', 'i*4', 'setjmpId', 'i32') }}}; - {{{ makeSetValueAsm('table', 'i*4+4', 'label', 'i32') }}}; + if ({{{ makeGetValueAsm('table', '(i<<2)', 'i32') }}} == 0) { + {{{ makeSetValueAsm('table', '(i<<2)', 'setjmpId', 'i32') }}}; + {{{ makeSetValueAsm('table', '(i<<2)+4', 'label', 'i32') }}}; // prepare next slot - {{{ makeSetValueAsm('table', 'i*4+8', '0', 'i32') }}}; + {{{ makeSetValueAsm('table', '(i<<2)+8', '0', 'i32') }}}; return 0; } i = (i+2)|0; @@ -6394,10 +6396,10 @@ LibraryManager.library = { table = table|0; var i = 0, curr = 0; while ((i|0) < {{{ MAX_SETJMPS }}}) { - curr = {{{ makeGetValueAsm('table', 'i*4', 'i32') }}}; + curr = {{{ makeGetValueAsm('table', '(i<<2)', 'i32') }}}; if ((curr|0) == 0) break; if ((curr|0) == (id|0)) { - return {{{ makeGetValueAsm('table', 'i*4+4', 'i32') }}}; + return {{{ makeGetValueAsm('table', '(i<<2)+4', 'i32') }}}; } i = (i+2)|0; } @@ -7330,6 +7332,7 @@ LibraryManager.library = { */ socket__deps: ['$Sockets'], socket: function(family, type, protocol) { + var INCOMING_QUEUE_LENGTH = 64; var fd = FS.createFileHandle({ addr: null, port: null, @@ -7337,7 +7340,7 @@ LibraryManager.library = { header: new Uint16Array(2), bound: false, socket: true - }; + }); assert(fd < 64); // select() assumes socket fd values are in 0..63 var stream = type == {{{ cDefine('SOCK_STREAM') }}}; if (protocol) { @@ -7423,8 +7426,6 @@ LibraryManager.library = { Sockets.peer = peer; } - var INCOMING_QUEUE_LENGTH = 64; - function CircularBuffer(max_length) { var buffer = new Array(++ max_length); var head = 0; @@ -7668,8 +7669,8 @@ LibraryManager.library = { nfds = Math.min(64, nfds); // fd sets have 64 bits for (var fd = 0; fd < nfds; fd++) { - var mask = 1 << (fd % 32), int = fd < 32 ? srcLow : srcHigh; - if (int & mask) { + var mask = 1 << (fd % 32), int_ = fd < 32 ? srcLow : srcHigh; + if (int_ & mask) { // index is in the set, check if it is ready for read var info = FS.streams[fd]; if (info && can(info)) { @@ -7700,7 +7701,7 @@ LibraryManager.library = { if (protocol) { assert(stream == (protocol == {{{ cDefine('IPPROTO_TCP') }}})); // if SOCK_STREAM, must be tcp } - var fd = FS.createFileHandle({ + var fd = FS.createFileHandle({ connected: false, stream: stream, socket: true @@ -8057,8 +8058,8 @@ LibraryManager.library = { nfds = Math.min(64, nfds); // fd sets have 64 bits for (var fd = 0; fd < nfds; fd++) { - var mask = 1 << (fd % 32), int = fd < 32 ? srcLow : srcHigh; - if (int & mask) { + var mask = 1 << (fd % 32), int_ = fd < 32 ? srcLow : srcHigh; + if (int_ & mask) { // index is in the set, check if it is ready for read var info = FS.streams[fd]; if (info && can(info)) { diff --git a/src/library_sdl.js b/src/library_sdl.js index 4f871f9d..a131f424 100644 --- a/src/library_sdl.js +++ b/src/library_sdl.js @@ -47,6 +47,7 @@ var LibrarySDL = { startTime: null, buttonState: 0, + modState: 0, DOMButtons: [0, 0, 0], DOMEventToSDLEvent: {}, @@ -373,7 +374,8 @@ var LibrarySDL = { if (event['movementX'] == 0 && event['movementY'] == 0) { // ignore a mousemove event if it doesn't contain any movement info // (without pointer lock, we infer movement from pageX/pageY, so this check is unnecessary) - return false; + event.preventDefault(); + return; } } // fall through @@ -396,15 +398,20 @@ var LibrarySDL = { } else if (event.type == 'mousedown') { SDL.DOMButtons[event.button] = 1; } else if (event.type == 'mouseup') { - if (!SDL.DOMButtons[event.button]) return false; // ignore extra ups, can happen if we leave the canvas while pressing down, then return, - // since we add a mouseup in that case + // ignore extra ups, can happen if we leave the canvas while pressing down, then return, + // since we add a mouseup in that case + if (!SDL.DOMButtons[event.button]) { + event.preventDefault(); + return; + } + SDL.DOMButtons[event.button] = 0; } if (event.type == 'keypress' && !SDL.textInput) { break; } - + SDL.events.push(event); break; case 'mouseout': @@ -438,7 +445,7 @@ var LibrarySDL = { // Force-run a main event loop, since otherwise this event will never be caught! Browser.mainLoop.runner(); } - return true; + return; case 'resize': SDL.events.push(event); break; @@ -447,7 +454,11 @@ var LibrarySDL = { Module.printErr('SDL event queue full, dropping events'); SDL.events = SDL.events.slice(0, 10000); } - return false; + // manually triggered resize event doesn't have a preventDefault member + if (event.preventDefault) { + event.preventDefault(); + } + return; }, makeCEvent: function(event, ptr) { @@ -473,15 +484,6 @@ var LibrarySDL = { } else { scan = SDL.scanCodes[key] || key; } - {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.type', 'SDL.DOMEventToSDLEvent[event.type]', 'i32') }}} - //{{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.which', '1', 'i32') }}} - {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.state', 'down ? 1 : 0', 'i8') }}} - {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.repeat', '0', 'i8') }}} // TODO - - {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.scancode', 'scan', 'i32') }}} - {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.sym', 'key', 'i32') }}} - {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.mod', '0', 'i32') }}} - {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.unicode', 'key', 'i32') }}} var code = SDL.keyCodes[event.keyCode] || event.keyCode; {{{ makeSetValue('SDL.keyboardState', 'code', 'down', 'i8') }}}; @@ -491,6 +493,19 @@ var LibrarySDL = { delete SDL.keyboardMap[code]; } + // TODO: lmeta, rmeta, numlock, capslock, KMOD_MODE, KMOD_RESERVED + SDL.modState = ({{{ makeGetValue('SDL.keyboardState', '1248', 'i8') }}} ? 0x0040 | 0x0080 : 0) | // KMOD_LCTRL & KMOD_RCTRL + ({{{ makeGetValue('SDL.keyboardState', '1249', 'i8') }}} ? 0x0001 | 0x0002 : 0) | // KMOD_LSHIFT & KMOD_RSHIFT + ({{{ makeGetValue('SDL.keyboardState', '1250', 'i8') }}} ? 0x0100 | 0x0200 : 0); // KMOD_LALT & KMOD_RALT + + {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.type', 'SDL.DOMEventToSDLEvent[event.type]', 'i32') }}} + {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.state', 'down ? 1 : 0', 'i8') }}} + {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.repeat', '0', 'i8') }}} // TODO + {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.scancode', 'scan', 'i32') }}} + {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.sym', 'key', 'i32') }}} + {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.mod', 'SDL.modState', 'i32') }}} + {{{ makeSetValue('ptr', 'SDL.structs.KeyboardEvent.keysym + SDL.structs.keysym.unicode', 'key', 'i32') }}} + break; } case 'keypress': { @@ -614,13 +629,13 @@ var LibrarySDL = { SDL.startTime = Date.now(); // capture all key events. we just keep down and up, but also capture press to prevent default actions if (!Module['doNotCaptureKeyboard']) { - document.onkeydown = SDL.receiveEvent; - document.onkeyup = SDL.receiveEvent; - document.onkeypress = SDL.receiveEvent; - document.onblur = SDL.receiveEvent; + document.addEventListener("keydown", SDL.receiveEvent); + document.addEventListener("keyup", SDL.receiveEvent); + document.addEventListener("keypress", SDL.receiveEvent); + document.addEventListener("blur", SDL.receiveEvent); document.addEventListener("visibilitychange", SDL.receiveEvent); } - window.onunload = SDL.receiveEvent; + window.addEventListener("unload", SDL.receiveEvent); SDL.keyboardState = _malloc(0x10000); // Our SDL needs 512, but 64K is safe for older SDLs _memset(SDL.keyboardState, 0, 0x10000); // Initialize this structure carefully for closure @@ -868,7 +883,7 @@ var LibrarySDL = { }, SDL_Delay: function(delay) { - throw 'SDL_Delay called! Potential infinite loop, quitting. ' + new Error().stack; + abort('SDL_Delay called! Potential infinite loop, quitting.'); }, SDL_WM_SetCaption: function(title, icon) { @@ -888,12 +903,16 @@ var LibrarySDL = { SDL_GetKeyState: function() { return _SDL_GetKeyboardState(); }, + + SDL_GetKeyName: function(key) { + if (!SDL.keyName) { + SDL.keyName = allocate(intArrayFromString('unknown key'), 'i8', ALLOC_NORMAL); + } + return SDL.keyName; + }, SDL_GetModState: function() { - // TODO: numlock, capslock, etc. - return (SDL.keyboardState[16] ? 0x0001 | 0x0002 : 0) | // KMOD_LSHIFT & KMOD_RSHIFT - (SDL.keyboardState[17] ? 0x0040 | 0x0080 : 0) | // KMOD_LCTRL & KMOD_RCTRL - (SDL.keyboardState[18] ? 0x0100 | 0x0200 : 0); // KMOD_LALT & KMOD_RALT + return SDL.modState; }, SDL_GetMouseState: function(x, y) { @@ -936,7 +955,10 @@ var LibrarySDL = { }, SDL_GetError: function() { - return allocate(intArrayFromString("unknown SDL-emscripten error"), 'i8'); + if (!SDL.errorMessage) { + SDL.errorMessage = allocate(intArrayFromString("unknown SDL-emscripten error"), 'i8', ALLOC_NORMAL); + } + return SDL.errorMessage; }, SDL_CreateRGBSurface: function(flags, width, height, depth, rmask, gmask, bmask, amask) { @@ -1100,6 +1122,20 @@ var LibrarySDL = { return (a&0xff)+((b&0xff)<<8)+((g&0xff)<<16)+((r&0xff)<<24) }, + SDL_GetAppState: function() { + var state = 0; + + if (Browser.pointerLock) { + state |= 0x01; // SDL_APPMOUSEFOCUS + } + if (document.hasFocus()) { + state |= 0x02; // SDL_APPINPUTFOCUS + } + state |= 0x04; // SDL_APPACTIVE + + return state; + }, + SDL_WM_GrabInput: function() {}, SDL_WM_ToggleFullScreen: function(surf) { @@ -1160,9 +1196,6 @@ var LibrarySDL = { SDL_OpenAudio: function(desired, obtained) { SDL.allocateChannels(32); - // FIXME: Assumes 16-bit audio - assert(obtained === 0, 'Cannot return obtained SDL audio params'); - SDL.audio = { freq: {{{ makeGetValue('desired', 'SDL.structs.AudioSpec.freq', 'i32', 0, 1) }}}, format: {{{ makeGetValue('desired', 'SDL.structs.AudioSpec.format', 'i16', 0, 1) }}}, @@ -1174,6 +1207,16 @@ var LibrarySDL = { timer: null }; + if (obtained) { + {{{ makeSetValue('obtained', 'SDL.structs.AudioSpec.freq', 'SDL.audio.freq', 'i32') }}}; // no good way for us to know if the browser can really handle this + {{{ makeSetValue('obtained', 'SDL.structs.AudioSpec.format', 33040, 'i16') }}}; // float, signed, 16-bit + {{{ makeSetValue('obtained', 'SDL.structs.AudioSpec.channels', 'SDL.audio.channels', 'i8') }}}; + {{{ makeSetValue('obtained', 'SDL.structs.AudioSpec.silence', makeGetValue('desired', 'SDL.structs.AudioSpec.silence', 'i8', 0, 1), 'i8') }}}; // unclear if browsers can provide this + {{{ makeSetValue('obtained', 'SDL.structs.AudioSpec.samples', 'SDL.audio.samples', 'i16') }}}; + {{{ makeSetValue('obtained', 'SDL.structs.AudioSpec.callback', 'SDL.audio.callback', '*') }}}; + {{{ makeSetValue('obtained', 'SDL.structs.AudioSpec.userdata', 'SDL.audio.userdata', '*') }}}; + } + var totalSamples = SDL.audio.samples*SDL.audio.channels; SDL.audio.bufferSize = totalSamples*2; // hardcoded 16-bit audio SDL.audio.buffer = _malloc(SDL.audio.bufferSize); @@ -1745,6 +1788,10 @@ var LibrarySDL = { return -1; }, + SDL_SetGammaRamp: function (redTable, greenTable, blueTable) { + return -1; + }, + // Misc SDL_InitSubSystem: function(flags) { return 0 }, @@ -1782,7 +1829,7 @@ var LibrarySDL = { SDL_FreeRW: function() { throw 'SDL_FreeRW: TODO' }, SDL_CondBroadcast: function() { throw 'SDL_CondBroadcast: TODO' }, SDL_CondWaitTimeout: function() { throw 'SDL_CondWaitTimeout: TODO' }, - SDL_WM_ToggleFullScreen: function() { throw 'SDL_WM_ToggleFullScreen: TODO' }, + SDL_WM_IconifyWindow: function() { throw 'SDL_WM_IconifyWindow TODO' }, Mix_SetPostMix: function() { throw 'Mix_SetPostMix: TODO' }, Mix_QuerySpec: function() { throw 'Mix_QuerySpec: TODO' }, @@ -1792,6 +1839,15 @@ var LibrarySDL = { Mix_Linked_Version: function() { throw 'Mix_Linked_Version: TODO' }, SDL_CreateRGBSurfaceFrom: function() { throw 'SDL_CreateRGBSurfaceFrom: TODO' }, SDL_SaveBMP_RW: function() { throw 'SDL_SaveBMP_RW: TODO' }, + + SDL_HasRDTSC: function() { return 0; }, + SDL_HasMMX: function() { return 0; }, + SDL_HasMMXExt: function() { return 0; }, + SDL_Has3DNow: function() { return 0; }, + SDL_Has3DNowExt: function() { return 0; }, + SDL_HasSSE: function() { return 0; }, + SDL_HasSSE2: function() { return 0; }, + SDL_HasAltiVec: function() { return 0; } }; autoAddDeps(LibrarySDL, '$SDL'); diff --git a/src/modules.js b/src/modules.js index e4093078..b13ab3c5 100644 --- a/src/modules.js +++ b/src/modules.js @@ -341,6 +341,7 @@ var Functions = { call += (j > 1 ? ',' : '') + asmCoercion('a' + j, t[j] != 'i' ? 'float' : 'i32'); } call += ')'; + if (curr == '_setjmp') printErr('WARNING: setjmp used via a function pointer. If this is for libc setjmp (not something of your own with the same name), it will break things'); tables.pre += 'function ' + curr + '__wrapper(' + args + ') { ' + arg_coercions + ' ; ' + retPre + call + retPost + ' }\n'; wrapped[curr] = 1; } diff --git a/src/parseTools.js b/src/parseTools.js index 3949491e..687faaa8 100644 --- a/src/parseTools.js +++ b/src/parseTools.js @@ -2204,7 +2204,7 @@ function processMathop(item) { case 'sub': return handleOverflow(getFastValue(idents[0], '-', idents[1], item.type), bits); case 'sdiv': case 'udiv': return makeRounding(getFastValue(idents[0], '/', idents[1], item.type), bits, op[0] === 's'); case 'mul': return getFastValue(idents[0], '*', idents[1], item.type); // overflow handling is already done in getFastValue for '*' - case 'urem': case 'srem': return getFastValue(idents[0], '%', idents[1], item.type); + case 'urem': case 'srem': return makeRounding(getFastValue(idents[0], '%', idents[1], item.type), bits, op[0] === 's'); case 'or': { if (bits > 32) { assert(bits === 64, 'Too many bits for or: ' + bits); diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index 8c72b0a6..8a6e18b8 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -70,7 +70,7 @@ int Indenter::CurrIndent = 0; // Branch -Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(false) { +Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(true) { Condition = ConditionInit ? strdup(ConditionInit) : NULL; Code = CodeInit ? strdup(CodeInit) : NULL; } @@ -522,14 +522,60 @@ void Relooper::Calculate(Block *Entry) { } } +#if 0 + // We can avoid multiple next entries by hoisting them into the loop. + if (NextEntries.size() > 1) { + BlockBlockSetMap IndependentGroups; + FindIndependentGroups(NextEntries, IndependentGroups, &InnerBlocks); + + while (IndependentGroups.size() > 0 && NextEntries.size() > 1) { + Block *Min = NULL; + int MinSize = 0; + for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) { + Block *Entry = iter->first; + BlockSet &Blocks = iter->second; + if (!Min || Blocks.size() < MinSize) { // TODO: code size, not # of blocks + Min = Entry; + MinSize = Blocks.size(); + } + } + // check how many new entries this would cause + BlockSet &Hoisted = IndependentGroups[Min]; + bool abort = false; + for (BlockSet::iterator iter = Hoisted.begin(); iter != Hoisted.end() && !abort; iter++) { + Block *Curr = *iter; + for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + Block *Target = iter->first; + if (Hoisted.find(Target) == Hoisted.end() && NextEntries.find(Target) == NextEntries.end()) { + // abort this hoisting + abort = true; + break; + } + } + } + if (abort) { + IndependentGroups.erase(Min); + continue; + } + // hoist this entry + PrintDebug("hoisting %d into loop\n", Min->Id); + NextEntries.erase(Min); + for (BlockSet::iterator iter = Hoisted.begin(); iter != Hoisted.end(); iter++) { + Block *Curr = *iter; + InnerBlocks.insert(Curr); + Blocks.erase(Curr); + } + IndependentGroups.erase(Min); + } + } +#endif + PrintDebug("creating loop block:\n"); DebugDump(InnerBlocks, " inner blocks:"); DebugDump(Entries, " inner entries:"); DebugDump(Blocks, " outer blocks:"); DebugDump(NextEntries, " outer entries:"); - // TODO: Optionally hoist additional blocks into the loop - LoopShape *Loop = new LoopShape(); Notice(Loop); @@ -551,7 +597,8 @@ void Relooper::Calculate(Block *Entry) { // For each entry, find the independent group reachable by it. The independent group is // the entry itself, plus all the blocks it can reach that cannot be directly reached by another entry. Note that we // ignore directly reaching the entry itself by another entry. - void FindIndependentGroups(BlockSet &Blocks, BlockSet &Entries, BlockBlockSetMap& IndependentGroups) { + // @param Ignore - previous blocks that are irrelevant + void FindIndependentGroups(BlockSet &Entries, BlockBlockSetMap& IndependentGroups, BlockSet *Ignore=NULL) { typedef std::map<Block*, Block*> BlockBlockMap; struct HelperClass { @@ -639,6 +686,7 @@ void Relooper::Calculate(Block *Entry) { Block *Child = *iter; for (BlockSet::iterator iter = Child->BranchesIn.begin(); iter != Child->BranchesIn.end(); iter++) { Block *Parent = *iter; + if (Ignore && Ignore->find(Parent) != Ignore->end()) continue; if (Helper.Ownership[Parent] != Helper.Ownership[Child]) { ToInvalidate.push_back(Child); } @@ -756,7 +804,7 @@ void Relooper::Calculate(Block *Entry) { // independent blocks from an entry/ies. It is important to remove through // multiples as opposed to looping since the former is more performant. BlockBlockSetMap IndependentGroups; - FindIndependentGroups(Blocks, *Entries, IndependentGroups); + FindIndependentGroups(*Entries, IndependentGroups); PrintDebug("Independent groups: %d\n", IndependentGroups.size()); @@ -903,10 +951,28 @@ void Relooper::Calculate(Block *Entry) { }); } + void FindNaturals(Shape *Root, Shape *Otherwise=NULL) { + if (Root->Next) { + Root->Natural = Root->Next; + FindNaturals(Root->Next, Otherwise); + } else { + Root->Natural = Otherwise; + } + + SHAPE_SWITCH(Root, { + }, { + for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { + FindNaturals(iter->second, Root->Natural); + } + }, { + FindNaturals(Loop->Inner, Loop->Inner); + }); + } + // Remove unneeded breaks and continues. // A flow operation is trivially unneeded if the shape we naturally get to by normal code // execution is the same as the flow forces us to. - void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL) { + void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL, LoopShape *LastLoop=NULL) { BlockSet NaturalBlocks; FollowNaturalFlow(Natural, NaturalBlocks); Shape *Next = Root; @@ -928,16 +994,22 @@ void Relooper::Calculate(Block *Entry) { if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { Multiple->NeedLoop--; } + } else if (Details->Type == Branch::Break && LastLoop && LastLoop->Natural == Details->Ancestor->Natural) { + // it is important to simplify breaks, as simpler breaks enable other optimizations + Details->Labeled = false; + if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { + Multiple->NeedLoop--; + } } } } }, { for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { - RemoveUnneededFlows(iter->second, Multiple->Next); + RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->NeedLoop ? NULL : LastLoop); } Next = Multiple->Next; }, { - RemoveUnneededFlows(Loop->Inner, Loop->Inner); + RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop); Next = Loop->Next; }); } @@ -968,7 +1040,7 @@ void Relooper::Calculate(Block *Entry) { Branch *Details = iter->second; if (Details->Type != Branch::Direct) { assert(LoopStack.size() > 0); - if (Details->Ancestor != LoopStack.top()) { + if (Details->Ancestor != LoopStack.top() && Details->Labeled) { LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor); Labeled->Labeled = true; Details->Labeled = true; @@ -1006,6 +1078,7 @@ void Relooper::Calculate(Block *Entry) { } void Process(Shape *Root) { + FindNaturals(Root); RemoveUnneededFlows(Root); FindLabeledLoops(Root); } @@ -1053,6 +1126,10 @@ void Debugging::Dump(BlockSet &Blocks, const char *prefix) { void Debugging::Dump(Shape *S, const char *prefix) { if (prefix) printf("%s ", prefix); + if (!S) { + printf(" (null)\n"); + return; + } printf(" %d ", S->Id); SHAPE_SWITCH(S, { printf("<< Simple with block %d\n", Simple->Inner->Id); diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h index 34b6db08..fe56a133 100644 --- a/src/relooper/Relooper.h +++ b/src/relooper/Relooper.h @@ -101,6 +101,7 @@ class LoopShape; struct Shape { int Id; // A unique identifier. Used to identify loops, labels are Lx where x is the Id. Shape *Next; // The shape that will appear in the code right after this one + Shape *Natural; // The shape that control flow gets to naturally (if there is Next, then this is Next) enum ShapeType { Simple, diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp index 7da990b5..b2d500d7 100644 --- a/src/relooper/test.cpp +++ b/src/relooper/test.cpp @@ -231,5 +231,32 @@ int main() { puts(buffer); } + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- conditional loop --\n\n"); + + Block *b_a = new Block("// block A\n"); + Block *b_b = new Block("// block B\n"); + Block *b_c = new Block("// block C\n"); + + b_a->AddBranchTo(b_b, "shouldLoop()"); + b_a->AddBranchTo(b_c, NULL); + + b_b->AddBranchTo(b_b, "moarLoop()"); + b_b->AddBranchTo(b_c, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + } } diff --git a/src/relooper/test.txt b/src/relooper/test.txt index d657c6af..b3535592 100644 --- a/src/relooper/test.txt +++ b/src/relooper/test.txt @@ -136,3 +136,20 @@ while(1) { // block F } + + +-- conditional loop -- + + + +// block A +if (shouldLoop()) { + while(1) { + // block B + if (!(moarLoop())) { + break; + } + } +} +// block C + diff --git a/src/relooper/test3.txt b/src/relooper/test3.txt index 696542ef..6049ee48 100644 --- a/src/relooper/test3.txt +++ b/src/relooper/test3.txt @@ -9,7 +9,7 @@ do { } } while(0); LBB3 -L5: do { +do { if (LBB3 -> LBB4) { LBB4 if (!(LBB4 -> LBB5)) { @@ -18,7 +18,7 @@ L5: do { while(1) { LBB5 if (LBB5 -> LBB6) { - break L5; + break; } } } diff --git a/src/relooper/test_inf.txt b/src/relooper/test_inf.txt index 379d2083..1dff59bb 100644 --- a/src/relooper/test_inf.txt +++ b/src/relooper/test_inf.txt @@ -5,35 +5,33 @@ if (uint(i4) >= uint(i5)) { code 1 } code 3 -L5: do { - if (!(i2 == 0)) { - code 4 - while(1) { - code 5 - if (uint(i6) >= uint(i7)) { - code 7 - } else { - code 6 - } - code 8 - if (uint(i6) >= uint(i7)) { - code 10 - } else { - code 9 - } - code 11 - if (uint(i5) >= uint(i6)) { - code 13 - } else { - code 12 - } - code 14 - if (!(i2 != 0)) { - break L5; - } +if (!(i2 == 0)) { + code 4 + while(1) { + code 5 + if (uint(i6) >= uint(i7)) { + code 7 + } else { + code 6 + } + code 8 + if (uint(i6) >= uint(i7)) { + code 10 + } else { |