aboutsummaryrefslogtreecommitdiffgithub
diff options
context:
space:
mode:
authorAustin Adams <git@austinjadams.com>2019-02-05 23:00:58 -0500
committerAustin Adams <git@austinjadams.com>2019-02-05 23:00:58 -0500
commita1cf7626f6971c1f80a8511608ee5c701de2ccb4 (patch)
treef851e61dacff0fe311d0418ec8ffb6f857fdc891
parent699bb01c1d7036bae89423cc4d5b24552cec6fbe (diff)
downloadnovice-a1cf7626f6971c1f80a8511608ee5c701de2ccb4.tar.gz
novice-a1cf7626f6971c1f80a8511608ee5c701de2ccb4.tar.xz
Try to optimize symbol lookups in debuggerHEADmaster
-rw-r--r--novice/assembler/opspec/opspec.ts4
-rw-r--r--novice/cli.test.ts27
-rw-r--r--novice/cli.ts4
-rw-r--r--novice/simulator/cli-debugger.test.ts4
-rw-r--r--novice/simulator/cli-debugger.ts4
-rw-r--r--novice/simulator/debugger.test.ts2
-rw-r--r--novice/simulator/debugger.ts103
-rw-r--r--novice/simulator/loaders/complx.test.ts27
-rw-r--r--novice/simulator/loaders/complx.ts15
-rw-r--r--novice/simulator/loaders/loader.ts5
-rw-r--r--novice/simulator/simulator.ts3
-rw-r--r--novice/simulator/symbols.ts11
12 files changed, 132 insertions, 77 deletions
diff --git a/novice/assembler/opspec/opspec.ts b/novice/assembler/opspec/opspec.ts
index d1f3923..8b9945b 100644
--- a/novice/assembler/opspec/opspec.ts
+++ b/novice/assembler/opspec/opspec.ts
@@ -1,8 +1,8 @@
-import { Isa } from '../../isa';
+import { Isa, SymbTable } from '../../isa';
interface AsmContext {
isa: Isa;
- symbtable: {[s: string]: number};
+ symbtable: SymbTable;
}
interface OpOperandSpec {
diff --git a/novice/cli.test.ts b/novice/cli.test.ts
index 1955af8..abe7241 100644
--- a/novice/cli.test.ts
+++ b/novice/cli.test.ts
@@ -495,25 +495,20 @@ describe('cli', () => {
describe('dbg subcommand', () => {
let mockDbg: CliDebugger;
- // @ts-ignore
- let mockDbgSymbTable: SymbTable;
beforeAll(() => {
// @ts-ignore
mockDbg = {
loadSections: jest.fn(),
+ setSymbols: jest.fn(),
run: jest.fn(),
- getSymbTable: jest.fn(),
close: jest.fn(),
};
});
beforeEach(() => {
- mockDbgSymbTable = {bob: 0xbeef};
// @ts-ignore
CliDebugger.mockImplementation(() => mockDbg);
- // @ts-ignore
- mockDbg.getSymbTable.mockReturnValue(mockDbgSymbTable);
});
afterEach(() => {
@@ -522,9 +517,9 @@ describe('cli', () => {
// @ts-ignore
mockDbg.loadSections.mockReset();
// @ts-ignore
- mockDbg.run.mockReset();
+ mockDbg.setSymbols.mockReset();
// @ts-ignore
- mockDbg.getSymbTable.mockReset();
+ mockDbg.run.mockReset();
// @ts-ignore
mockDbg.close.mockReset();
});
@@ -553,15 +548,11 @@ describe('cli', () => {
// @ts-ignore
expect(CliDebugger.mock.calls).toEqual([[mockSimConfig.isa, stdin, stdout]]);
// @ts-ignore
- expect(mockDbg.getSymbTable.mock.calls).toEqual([[]]);
+ expect(mockDbg.setSymbols.mock.calls).toEqual([[mockSymbTable]]);
// @ts-ignore
expect(mockDbg.run.mock.calls).toEqual([[]]);
// @ts-ignore
expect(mockDbg.close.mock.calls).toEqual([[]]);
- expect(mockDbgSymbTable).toEqual({
- bob: 0xbeef,
- nice: 0x69,
- });
});
});
@@ -579,7 +570,7 @@ describe('cli', () => {
// @ts-ignore
expect(mockSimConfig.loader.load.mock.calls).toEqual([[mockSimConfig.isa, mockFp, mockDbg]]);
// @ts-ignore
- expect(mockSimConfig.loader.loadSymb.mock.calls).toEqual([[mockFp, mockDbgSymbTable]]);
+ expect(mockSimConfig.loader.loadSymb.mock.calls).toEqual([[mockFp, mockDbg]]);
// @ts-ignore
expect(getConfig.mock.calls).toEqual([]);
// @ts-ignore
@@ -589,8 +580,6 @@ describe('cli', () => {
// @ts-ignore
expect(CliDebugger.mock.calls).toEqual([[mockSimConfig.isa, stdin, stdout]]);
// @ts-ignore
- expect(mockDbg.getSymbTable.mock.calls).toEqual([[]]);
- // @ts-ignore
expect(mockDbg.run.mock.calls).toEqual([[]]);
// @ts-ignore
expect(mockDbg.close.mock.calls).toEqual([[]]);
@@ -633,8 +622,6 @@ describe('cli', () => {
// @ts-ignore
expect(CliDebugger.mock.calls).toEqual([[mockSimConfig.isa, stdin, stdout]]);
// @ts-ignore
- expect(mockDbg.getSymbTable.mock.calls).toEqual([]);
- // @ts-ignore
expect(mockDbg.run.mock.calls).toEqual([[]]);
// @ts-ignore
expect(mockDbg.close.mock.calls).toEqual([[]]);
@@ -686,7 +673,7 @@ describe('cli', () => {
// @ts-ignore
expect(mockSimConfig.loader.load.mock.calls).toEqual([[mockSimConfig.isa, mockFp, mockDbg]]);
// @ts-ignore
- expect(mockSimConfig.loader.loadSymb.mock.calls).toEqual([[mockFp, mockDbgSymbTable]]);
+ expect(mockSimConfig.loader.loadSymb.mock.calls).toEqual([[mockFp, mockDbg]]);
// @ts-ignore
expect(getConfig.mock.calls).toEqual([]);
// @ts-ignore
@@ -696,8 +683,6 @@ describe('cli', () => {
// @ts-ignore
expect(CliDebugger.mock.calls).toEqual([[mockSimConfig.isa, stdin, stdout]]);
// @ts-ignore
- expect(mockDbg.getSymbTable.mock.calls).toEqual([[]]);
- // @ts-ignore
expect(mockDbg.run.mock.calls).toEqual([[]]);
// @ts-ignore
expect(mockDbg.close.mock.calls).toEqual([[]]);
diff --git a/novice/cli.ts b/novice/cli.ts
index 1cad194..f1ada7a 100644
--- a/novice/cli.ts
+++ b/novice/cli.ts
@@ -207,7 +207,7 @@ async function dbg(configName: string, path: string, stdin: Readable,
if (symbFp) {
await Promise.all([
loadPromise,
- cfg.loader.loadSymb(symbFp, debug.getSymbTable()),
+ cfg.loader.loadSymb(symbFp, debug),
]);
} else {
await loadPromise;
@@ -217,7 +217,7 @@ async function dbg(configName: string, path: string, stdin: Readable,
const assembler = new Assembler(asmCfg);
const [symbtable, sections] = await assembler.assemble(fp);
debug.loadSections(sections);
- Object.assign(debug.getSymbTable(), symbtable);
+ debug.setSymbols(symbtable);
}
await debug.run();
diff --git a/novice/simulator/cli-debugger.test.ts b/novice/simulator/cli-debugger.test.ts
index e4a24f7..3c4db48 100644
--- a/novice/simulator/cli-debugger.test.ts
+++ b/novice/simulator/cli-debugger.test.ts
@@ -210,8 +210,8 @@ describe('cli debugger', () => {
dbg.store(0x3003, 0x1264); // add r1, r1, 4
dbg.store(0x3004, 0xf025); // halt
- Object.assign(dbg.getSymbTable(), {
- tim_brown: 0x3002
+ dbg.setSymbols({
+ tim_brown: 0x3002,
});
runCmd('b tim_brown');
diff --git a/novice/simulator/cli-debugger.ts b/novice/simulator/cli-debugger.ts
index 6a8e8d5..b40d517 100644
--- a/novice/simulator/cli-debugger.ts
+++ b/novice/simulator/cli-debugger.ts
@@ -178,10 +178,10 @@ class CliDebugger extends Debugger {
/\d+/.test(operand) ? 10 : -1;
let addr: number;
if (base === -1) {
- if (!(operand in this.symbTable)) {
+ if (!this.hasSymbol(operand)) {
throw new Error(`unknown label \`${operand}'`);
}
- addr = this.symbTable[operand];
+ addr = this.getSymbolAddr(operand);
} else {
addr = parseInt(operand, base);
}
diff --git a/novice/simulator/debugger.test.ts b/novice/simulator/debugger.test.ts
index c37b9ed..230807d 100644
--- a/novice/simulator/debugger.test.ts
+++ b/novice/simulator/debugger.test.ts
@@ -75,7 +75,7 @@ describe('debugger', () => {
dbg.store(0x3008, 0x0021); // bang .fill '!'
dbg.store(0x3009, 0xd000); // .fill 0xd000
- Object.assign(dbg.getSymbTable(), {
+ dbg.setSymbols({
loop: 0x3003,
// Don't include this so the branch has to have an integer
// operand in the disassembly
diff --git a/novice/simulator/debugger.ts b/novice/simulator/debugger.ts
index f53e0e4..28b6a4f 100644
--- a/novice/simulator/debugger.ts
+++ b/novice/simulator/debugger.ts
@@ -2,15 +2,18 @@ import { Fields, getRegAliases, InstructionSpec, IO, Isa,
SymbTable } from '../isa';
import { maskTo, maxUnsignedVal, sextTo } from '../util';
import { Simulator } from './simulator';
+import { Symbols } from './symbols';
type RegAliasLut = {[prefix: string]: (string|null)[]};
+type InvSymbTable = {[addr: number]: string[]};
-class Debugger extends Simulator {
+class Debugger extends Simulator implements Symbols {
protected nextBreakpoint: number;
// Map of address -> breakpoint number
protected breakpoints: {[addr: number]: number};
protected interrupt: boolean;
protected symbTable: SymbTable;
+ protected invSymbTable: InvSymbTable;
protected regAliasLut: RegAliasLut;
public constructor(isa: Isa, io: IO, maxExec: number) {
@@ -20,36 +23,12 @@ class Debugger extends Simulator {
this.breakpoints = {};
this.interrupt = false;
this.symbTable = {};
+ this.invSymbTable = {};
this.regAliasLut = this.genRegAliasLut(isa);
}
- private genRegAliasLut(isa: Isa): RegAliasLut {
- const lut: RegAliasLut = {};
-
- for (const reg of isa.regs) {
- if (reg.kind === 'reg-range') {
- lut[reg.prefix] = new Array(reg.count).fill(null);
-
- if (reg.aliases) {
- for (const alias in reg.aliases) {
- const regno = reg.aliases[alias];
- const current = lut[reg.prefix][regno];
- // Make sure we behave deterministically: If we
- // have a collision, choose the
- // lexicographically smaller alias
- if (!current || current > alias) {
- lut[reg.prefix][regno] = alias;
- }
- }
- }
- }
- }
-
- return lut;
- }
-
public getSymbTable(): SymbTable {
- return this.symbTable;
+ return Object.assign({}, this.symbTable);
}
// continue
@@ -179,10 +158,80 @@ class Debugger extends Simulator {
return result;
}
+ public hasSymbol(symb: string): boolean {
+ return symb in this.symbTable;
+ }
+
+ public setSymbol(symb: string, addr: number): void {
+ if (this.hasSymbol(symb)) {
+ const oldAddr = this.symbTable[symb];
+ // update inverted
+ const symbols = this.invSymbTable[oldAddr];
+ symbols.splice(symbols.indexOf(symb), 1);
+ }
+
+ this.symbTable[symb] = addr;
+
+ if (!(addr in this.invSymbTable)) {
+ this.invSymbTable[addr] = [];
+ }
+
+ this.invSymbTable[addr].push(symb);
+ // Determinism!
+ this.invSymbTable[addr].sort();
+ }
+
+ public setSymbols(symbtable: SymbTable): void {
+ for (const symb in symbtable) {
+ this.setSymbol(symb, symbtable[symb]);
+ }
+ }
+
+ public getSymbolAddr(symb: string): number {
+ if (!(symb in this.symbTable)) {
+ throw new Error(`no such symbol \`${symb}'`);
+ }
+
+ return this.symbTable[symb];
+ }
+
+ public getAddrSymbols(addr: number): string[] {
+ if (!(addr in this.invSymbTable)) {
+ return [];
+ }
+
+ return this.invSymbTable[addr];
+ }
+
protected lookupRegAlias(prefix: string, regno: number): string|null {
return this.regAliasLut[prefix][regno];
}
+ private genRegAliasLut(isa: Isa): RegAliasLut {
+ const lut: RegAliasLut = {};
+
+ for (const reg of isa.regs) {
+ if (reg.kind === 'reg-range') {
+ lut[reg.prefix] = new Array(reg.count).fill(null);
+
+ if (reg.aliases) {
+ for (const alias in reg.aliases) {
+ const regno = reg.aliases[alias];
+ const current = lut[reg.prefix][regno];
+ // Make sure we behave deterministically: If we
+ // have a collision, choose the
+ // lexicographically smaller alias
+ if (!current || current > alias) {
+ lut[reg.prefix][regno] = alias;
+ }
+ }
+ }
+ }
+ }
+
+ return lut;
+ }
+
private labelsForAddr(pc: number): string[] {
// TODO: replace with something less grossly inefficient
const results: string[] = [];
diff --git a/novice/simulator/loaders/complx.test.ts b/novice/simulator/loaders/complx.test.ts
index a2969f1..7045584 100644
--- a/novice/simulator/loaders/complx.test.ts
+++ b/novice/simulator/loaders/complx.test.ts
@@ -3,6 +3,7 @@ import { Loader } from './loader';
import { ComplxObjectFileLoader } from './complx';
import { Readable } from 'stream';
import { Memory } from '../mem';
+import { Symbols } from '../symbols';
interface Mem extends Memory {
data: {[n: number]: number};
@@ -182,12 +183,18 @@ describe('complx loader', () => {
describe('loadSymb()', () => {
let symbTable: SymbTable;
+ let symbs: Symbols;
beforeEach(() => {
fp = new Readable({
objectMode: true,
});
symbTable = {};
+ // @ts-ignore
+ symbs = {
+ hasSymbol: (symb: string) => symb in symbTable,
+ setSymbol: (symb: string, addr: number) => { symbTable[symb] = addr; },
+ };
});
it('loads basic table', () => {
@@ -199,7 +206,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return loader.loadSymb(fp, symbTable).then(() => {
+ return loader.loadSymb(fp, symbs).then(() => {
expect(symbTable).toEqual({
daisyy: 0x69,
marley: 0x420,
@@ -216,7 +223,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return loader.loadSymb(fp, symbTable).then(() => {
+ return loader.loadSymb(fp, symbs).then(() => {
expect(symbTable).toEqual({
bob1: 0x69,
bob2: 0x69,
@@ -227,7 +234,7 @@ describe('complx loader', () => {
it('handles empty table', () => {
fp.push(null);
- return loader.loadSymb(fp, symbTable).then(() => {
+ return loader.loadSymb(fp, symbs).then(() => {
expect(symbTable).toEqual({});
});
});
@@ -239,7 +246,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return loader.loadSymb(fp, symbTable).then(() => {
+ return loader.loadSymb(fp, symbs).then(() => {
expect(symbTable).toEqual({
savage: 0x21,
bob: 0x420,
@@ -253,7 +260,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return expect(loader.loadSymb(fp, symbTable)).rejects.toThrow(/exceeds.*on line 1$/);
+ return expect(loader.loadSymb(fp, symbs)).rejects.toThrow(/exceeds.*on line 1$/);
});
it('errors on overlong line', () => {
@@ -263,7 +270,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return expect(loader.loadSymb(fp, symbTable)).rejects.toThrow(/exceeds.*on line 2$/);
+ return expect(loader.loadSymb(fp, symbs)).rejects.toThrow(/exceeds.*on line 2$/);
});
it('errors on nonempty line without tab', () => {
@@ -274,7 +281,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return expect(loader.loadSymb(fp, symbTable)).rejects.toThrow(/tabs.*on line 2$/);
+ return expect(loader.loadSymb(fp, symbs)).rejects.toThrow(/tabs.*on line 2$/);
});
it('errors on negative address', () => {
@@ -283,7 +290,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return expect(loader.loadSymb(fp, symbTable)).rejects.toThrow(/negative.*on line 1$/);
+ return expect(loader.loadSymb(fp, symbs)).rejects.toThrow(/negative.*on line 1$/);
});
it('errors on non-hex address', () => {
@@ -292,7 +299,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return expect(loader.loadSymb(fp, symbTable)).rejects.toThrow(/`x4'.*on line 1$/);
+ return expect(loader.loadSymb(fp, symbs)).rejects.toThrow(/`x4'.*on line 1$/);
});
it('errors duplicate symbol', () => {
@@ -302,7 +309,7 @@ describe('complx loader', () => {
].forEach(s => fp.push(Buffer.from(s)));
fp.push(null);
- return expect(loader.loadSymb(fp, symbTable)).rejects.toThrow(/`gaming'.*on line 2$/);
+ return expect(loader.loadSymb(fp, symbs)).rejects.toThrow(/`gaming'.*on line 2$/);
});
});
});
diff --git a/novice/simulator/loaders/complx.ts b/novice/simulator/loaders/complx.ts
index 51a33a9..fe84e56 100644
--- a/novice/simulator/loaders/complx.ts
+++ b/novice/simulator/loaders/complx.ts
@@ -1,7 +1,8 @@
import { Buffer } from 'buffer';
import { Readable } from 'stream';
-import { Isa, SymbTable } from '../../isa';
+import { Isa } from '../../isa';
import { Memory } from '../mem';
+import { Symbols } from '../symbols';
import { Loader } from './loader';
type State = 'addr'|'len'|'words';
@@ -97,7 +98,7 @@ class ComplxObjectFileLoader implements Loader {
return 'sym';
}
- public async loadSymb(fp: Readable, symbtable: SymbTable): Promise<void> {
+ public async loadSymb(fp: Readable, symbols: Symbols): Promise<void> {
// If you have any lines this long, I'm praying for your entire
// family
const buf = Buffer.alloc(1024);
@@ -131,7 +132,7 @@ class ComplxObjectFileLoader implements Loader {
try {
this.parseLine(buf.slice(0, totalLen).toString(),
- lines, symbtable);
+ lines, symbols);
} catch (e) {
err = e;
return;
@@ -165,12 +166,12 @@ class ComplxObjectFileLoader implements Loader {
}
if (size > 0) {
- this.parseLine(buf.slice(0, size).toString(), lines, symbtable);
+ this.parseLine(buf.slice(0, size).toString(), lines, symbols);
size = 0;
}
}
- private parseLine(line: string, lines: number, symbtable: SymbTable) {
+ private parseLine(line: string, lines: number, symbols: Symbols) {
line = line.trim();
// Ignore empty lines
@@ -196,11 +197,11 @@ class ComplxObjectFileLoader implements Loader {
throw new Error(`invalid address \`${hexAddr}' on line ${lines}`);
}
- if (sym in symbtable) {
+ if (symbols.hasSymbol(sym)) {
throw new Error(`duplicate symbol \`${sym}' on line ${lines}`);
}
- symbtable[sym] = addr;
+ symbols.setSymbol(sym, addr);
}
}
diff --git a/novice/simulator/loaders/loader.ts b/novice/simulator/loaders/loader.ts
index 1b070e3..d6ca931 100644
--- a/novice/simulator/loaders/loader.ts
+++ b/novice/simulator/loaders/loader.ts
@@ -1,12 +1,13 @@
import { Readable } from 'stream';
-import { Isa, SymbTable } from '../../isa';
+import { Isa } from '../../isa';
import { Memory } from '../mem';
+import { Symbols } from '../symbols';
interface Loader {
load(isa: Isa, fp: Readable, mem: Memory): Promise<void>;
fileExt(): string;
symbFileExt(): string;
- loadSymb(fp: Readable, symbtable: SymbTable): Promise<void>;
+ loadSymb(fp: Readable, symbols: Symbols): Promise<void>;
}
export { Loader };
diff --git a/novice/simulator/simulator.ts b/novice/simulator/simulator.ts
index 6da9687..4800e4b 100644
--- a/novice/simulator/simulator.ts
+++ b/novice/simulator/simulator.ts
@@ -1,6 +1,7 @@
import { Fields, InstructionSpec, IO, Isa, MachineCodeSection, MachineStateLogEntry,
MachineStateUpdate, Reg, RegIdentifier } from '../isa';
import { forceUnsigned, maskTo, sextTo } from '../util';
+import { Memory } from './mem';
class InstrLut {
private isa: Isa;
@@ -81,7 +82,7 @@ class InstrLut {
}
}
-class Simulator {
+class Simulator implements Memory {
protected pc: number;
protected mem: {[addr: number]: number};
protected regs: {
diff --git a/novice/simulator/symbols.ts b/novice/simulator/symbols.ts
new file mode 100644
index 0000000..997f374
--- /dev/null
+++ b/novice/simulator/symbols.ts
@@ -0,0 +1,11 @@
+import { SymbTable } from '../isa';
+
+interface Symbols {
+ hasSymbol(symb: string): boolean;
+ setSymbol(symb: string, addr: number): void;
+ setSymbols(symbtable: SymbTable): void;
+ getSymbolAddr(symb: string): number;
+ getAddrSymbols(addr: number): string[];
+}
+
+export { Symbols };