diff options
Diffstat (limited to 'chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen')
4 files changed, 640 insertions, 0 deletions
diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/FlagSpillTestSupport.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/FlagSpillTestSupport.java new file mode 100644 index 00000000..00d86c63 --- /dev/null +++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/FlagSpillTestSupport.java @@ -0,0 +1,145 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.isa.X86; +import com.seaofnodes.isa.eval.EvalArm64; +import com.seaofnodes.simple.TestC; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.arm.arm; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import static org.junit.Assert.*; + +// Force overlapping flags, then force every GPR unavailable across the gap. +public class FlagSpillTestSupport { + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + Op(RegMask def,RegMask use,RegMask kill,Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _type=TypeInteger.BOT; + } + @Override public String op() { return "flagsProbe"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @Override public RegMask killmap() { return _kill; } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + + public static void run() throws Exception { + StringBuilder asm = new StringBuilder(".text\n"); + for( boolean isArm : new boolean[]{false,true} ) + for( boolean stack : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + code._callingConv="SystemV"; + code._mach=isArm ? new arm(code) : new x86_64_v2(code); + RegionNode block = new RegionNode(null,code._start,code._start); + code._cfg.add(block); + int flagsReg=isArm ? 64 : 32, firstStack=flagsReg+1; + RegMask flags = new RegMask(flagsReg); + Op def = new Op(flags,null,null,block); + RegMask killMask = stack ? (isArm ? new RegMask(0x7fffffffL,1L) : new RegMask(0x1ffffffefL)) : flags; + Op kill = new Op(null,null,killMask,block); + new Op(null,flags,null,block,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); + + int splits=0, slots=0; + for( Node n : block._outputs ) if( n instanceof SplitNode split ) { + int dst=alloc.regnum(n), src=alloc.regnum(n.in(1)); + assertTrue(split.outregmap().test(dst)); + assertTrue(split.regmap(1).test(src)); + for( int fp=isArm ? 32 : 16; fp<flagsReg; fp++ ) { + assertFalse("FP output allowed",split.outregmap().test(fp)); + assertFalse("FP input allowed",split.regmap(1).test(fp)); + } + if( dst>=firstStack || src>=firstStack ) slots++; + splits++; + } + assertTrue(splits>=2); + assertEquals(stack,slots!=0); + + code._regAlloc=alloc; + FunNode frame = new FunNode(null,null,"flags",(Node)null); + Encoding save = new Encoding(code), restore = new Encoding(code); + save._fun=restore._fun=frame; + Encoding enc = save; + for( Node n : block._outputs ) { + if( n==kill ) enc=restore; + if( n instanceof SplitNode split ) split.encoding(enc); + } + if( isArm ) { + for( int bits=0; bits<16; bits++ ) { + EvalArm64 cpu = new EvalArm64(new byte[1024],512); + System.arraycopy(save._bits.buf(),0,cpu._buf,0,save._bits.size()); + System.arraycopy(restore._bits.buf(),0,cpu._buf,save._bits.size(),restore._bits.size()); + cpu.N=(bits&8)!=0; cpu.Z=(bits&4)!=0; cpu.C=(bits&2)!=0; cpu.V=(bits&1)!=0; + assertEquals(0,cpu.step(save._bits.size()/4)); + cpu.N=cpu.Z=cpu.C=cpu.V=false; + if( stack ) for( int r=0; r<31; r++ ) cpu.regs[r]=0; + assertEquals(0,cpu.step(restore._bits.size()/4)); + assertEquals((bits&8)!=0,cpu.N); assertEquals((bits&4)!=0,cpu.Z); + assertEquals((bits&2)!=0,cpu.C); assertEquals((bits&1)!=0,cpu.V); + assertEquals(512,cpu.regs[31]); + } + } else { + Encoding body = new Encoding(code); + int[] preserved={3,5,6,7,12,13,14,15}; + for( int r : preserved ) pushPop(body,r,false); + X86.imm(body,0x81,5,4,16); // Reserve spill storage. + X86.flags(body,TestC.OS.startsWith("Windows") ? 1 : 7,true); + bytes(body,save); + if( stack ) { + for( int r=0; r<16; r++ ) if( r!=4 ) X86.constant(body,r,0); + } else X86.reg(body,0x39,0,0); // CMP rax,rax clobbers only flags. + bytes(body,restore); + X86.flags(body,0,false); // Return the restored flags. + X86.imm(body,0x81,0,4,16); + for( int i=preserved.length-1; i>=0; i-- ) pushPop(body,preserved[i],true); + X86.ret(body); + String name=stack ? "flags_stack" : "flags_reg"; + asm.append(".globl ").append(name).append('\n').append(name).append(":\n.byte "); + for( int i=0; i<body._bits.size(); i++ ) { + if( i!=0 ) asm.append(','); + asm.append(body._bits.buf()[i]&255); + } + asm.append('\n'); + } + } + Path dir=Files.createTempDirectory(Path.of("build/objs"),"flag_spills_"); + Files.writeString(dir.resolve("flags.s"),asm); + Files.writeString(dir.resolve("flags.c"),""" + typedef unsigned long long u64; + u64 __attribute__((CALL_CONV)) flags_reg(u64); + u64 __attribute__((CALL_CONV)) flags_stack(u64); + int main(void) { + const int positions[]={0,2,4,6,7,11}; + for(int bits=0; bits<64; bits++) { + u64 flags=0x202; + for(int i=0;i<6;i++) if(bits&(1<<i)) flags|=1ULL<<positions[i]; + if((flags_reg(flags)&0x8d5)!=(flags&0x8d5)) return 1; + if((flags_stack(flags)&0x8d5)!=(flags&0x8d5)) return 2; + } + return 0; + } + """); + String exe=dir.resolve(TestC.OS.startsWith("Windows") ? "flags.exe" : "flags").toString(); + exec("gcc","-DCALL_CONV="+(TestC.OS.startsWith("Windows") ? "ms_abi" : "sysv_abi"), + "-o",exe,dir.resolve("flags.c").toString(),dir.resolve("flags.s").toString()); + exec(exe); + } + + private static void exec(String... command) throws Exception { + Process process = new ProcessBuilder(command).redirectErrorStream(true).start(); + String output = new String(process.getInputStream().readAllBytes(),java.nio.charset.StandardCharsets.UTF_8); + assertEquals(String.join(" ",command)+"\n"+output,0,process.waitFor()); + } + + private static void bytes(Encoding dst,Encoding src) { + for( int i=0; i<src._bits.size(); i++ ) dst.add1(src._bits.buf()[i]&255); + } + private static void pushPop(Encoding enc,int reg,boolean pop) { + if( reg>=8 ) enc.add1(0x41); + enc.add1((pop ? 0x58 : 0x50)+(reg&7)); + } +} diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java new file mode 100644 index 00000000..b9b49c9f --- /dev/null +++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; +public class PrintRegTestSupport { + public static void check() throws Exception { + var code = new CodeGen("return 0;").parse(); + var alloc = new RegAlloc(code); + var n = new ConstantNode(TypeInteger.ZERO); + var a = new LRG((short)1); + var b = new LRG((short)2); + var c = new LRG((short)3); + a._reg = -1; + c._leader = b; + b._leader = a; + var field = RegAlloc.class.getDeclaredField("_lrgs"); + field.setAccessible(true); + var map = (java.util.Map<Node,LRG>)field.get(alloc); + map.put(n,c); + assertEquals("V1",alloc.reg(n)); + assertEquals(-1,alloc.regnum(n)); + assertSame(c,map.get(n)); + assertSame(b,c._leader); + assertSame(a,b._leader); + } +} diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..0304c6a1 --- /dev/null +++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,346 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; + +// Small scheduled machine graphs isolate register constraints from peepholes. +public class RegAllocTestSupport { + private static final RegMask A = new RegMask(0), B = new RegMask(1); + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + final boolean _clone; + Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT; + } + @Override public String op() { return "testOp"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @Override public RegMask killmap() { return _kill; } + @Override public boolean isClone() { return _clone; } + @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + private static SplitNode testSplit(CodeGen code, MachNode def) { + LRG lrg = new LRG((short)0); + lrg._machDef = def; + return code._mach.split("test",(byte)0,lrg); + } + private static CodeGen graph() { + CodeGen code = new CodeGen(""); + code._mach = new x86_64_v2(code); + code._cfg.add(code._start); + return code; + } + + public static void uncoloredFixedNeighbor() throws Exception { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + LRG lrg = alloc.newLRG(def); + LRG neighbor = new LRG((short)99); + neighbor._mask = A; + lrg.addNeighbor(neighbor); // Uncolored, but its only possible color is A. + var bias = IFG.class.getDeclaredMethod("biasColorNeighbors",RegAlloc.class,Node.class,RegMask.class); + bias.setAccessible(true); + assertEquals((short)1,bias.invoke(null,alloc,def,new RegMaskRW(3L,0L))); + } + + public static void masks() { + for( int reg : new int[]{0,63,64,65,127} ) { + RegMask mask = new RegMask(reg); + assertEquals(reg,mask.firstReg()); + assertEquals(1,mask.size()); + } + assertEquals(-1,new RegMask(0L).firstReg()); + assertFalse(new RegMask(0L).size1()); + RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1); + assertEquals(64,boundary.nextReg((short)63)); + assertEquals(127,boundary.nextReg((short)64)); + assertEquals(-1,boundary.nextReg((short)127)); + } + + public static void union() { + CodeGen code = graph(); + Op use = new Op(null,B,null,false,code._start); + LRG a = new LRG((short)1), b = new LRG((short)2); + a._mask = new RegMask(3L); + b._mask = new RegMask(6L); + b.machUse(use,(short)2,true); + LRG both = a.union(b); + assertNotNull(both._mask); + assertEquals(1,both._mask.firstReg()); + assertEquals(1,both._mask.size()); + assertSame(use,both._machUse); + assertEquals(2,both._uidx); + } + + public static void killWithoutResult() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,A,false,code._start); // Clobbers A, produces no value. + new Op(null,A,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + } + + public static void nullUseMask() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,null,false,code._start,def); // Scheduling dependency only. + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertTrue(IFG.build(0,alloc)); + } + + public static void cloneRegisterClass() { + for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) { + CodeGen code = graph(); + Op def = new Op(A,null,null,true,code._start); + Op use = new Op(null,required,null,false,code._start,def); + Op use2 = new Op(null,required,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses. + assertEquals(0,alloc.regnum(def)); + assertTrue(required.test(alloc.regnum(use.in(1)))); + assertTrue(required.test(alloc.regnum(use2.in(1)))); + assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void commutativePhi() { + CodeGen code = graph(); + Op a = new Op(A,null,null,false,code._start); + Op b = new Op(A,null,null,false,code._start); + Op add = new Op(A,A,null,false,code._start,a,b) { + @Override public boolean commutes() { return true; } + }; + RegionNode region = new RegionNode(null,code._start,code._start); + new PhiNode("sum",TypeInteger.BOT,region,add,a); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,new RegAlloc(code))); + } + + private static class CallOp extends CallNode implements MachNode { + CallOp(Node ctrl, Node def) { super(null,ctrl,null,def,def); } + @Override public RegMask regmap(int i) { return i==2 ? A : i==3 ? B : null; } + @Override public RegMask outregmap() { return null; } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + + public static void popularUses() { + for( int calls=0; calls<=2; calls++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + RegionNode block = new RegionNode(null,code._start,code._start); + Op def = new Op(new RegMask(7L),null,null,false,block); + LRG lrg = alloc.newLRG(def); + lrg._machDef = def; + lrg._mask = new RegMask(0L); + Op ab = new Op(null,new RegMask(3L),null,false,block,def); + Op bc = new Op(null,new RegMask(6L),null,false,block,def); + Op a = new Op(null,A,null,false,block,def,def); + Op b = new Op(null,B,null,false,block,def); + Op dep = new Op(null,null,null,false,block,def); + CallOp call = calls>0 ? new CallOp(block,def) : null; + if( calls==2 ) new CallOp(block,def); + boolean split = alloc.splitEmptyMaskByUse((byte)0,lrg); + assertEquals(calls<2,split); + if( !split ) { assertSame(def,a.in(1)); assertSame(def,b.in(1)); continue; } + // Two shared copies, even with overlapping masks and repeated inputs. + assertTrue(a.in(1) instanceof SplitNode); + assertTrue(b.in(1) instanceof SplitNode); + assertNotSame(a.in(1),b.in(1)); + assertSame(a.in(1),a.in(2)); + assertSame(b.in(1),ab.in(1)); + assertSame(b.in(1),bc.in(1)); + assertSame(def,dep.in(1)); // A scheduling dependency has no register. + assertEquals(3,def.nOuts()); // Two copies and the dependency. + if( call!=null ) { + assertSame(a.in(1),call.in(2)); + assertSame(b.in(1),call.in(3)); + } + } + } + + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. + public static class CheckedCodeGen extends CodeGen { + public CheckedCodeGen(String src) { super(src); } + public CheckedCodeGen(String src, TypeInteger arg) { super(src,arg); } + @Override public CodeGen regAlloc() { + super.regAlloc(); + checkRegisters(this); + return this; + } + } + + public static void topPhi() { + // Either arm can be the synthetic exit. Both predecessors share a + // block here so making TOP live would conflict with the real value. + for( int slot=1; slot<=2; slot++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + Node top = new ConstantNode(com.seaofnodes.simple.type.Type.TOP); + RegionNode region = new RegionNode(null,code._start,code._start); + PhiNode phi = new PhiNode("value",TypeInteger.BOT,region,slot==1 ? top : def,slot==2 ? top : def); + phi._type = TypeInteger.BOT; + new Op(null,A,null,false,region,phi); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,alloc)); + assertNull(alloc.lrg(top)); + assertSame(alloc.lrg(def),alloc.lrg(phi)); + assertTrue(IFG.build(0,alloc)); + alloc.insertBefore(phi,slot,"test",(byte)0,alloc.lrg(phi)); + assertSame(top,phi.in(slot)); + } + } + + public static void checkRegisters(CodeGen code) { + assertTrue(code._regAlloc.verifyFunctionLocalEdges()); + for( CFGNode bb : code._cfg ) + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach ) { + if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n))); + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i)))); + if( mach.twoAddress()!=0 ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress()))); + } + if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP ) + assertNull(code._regAlloc.lrg(n.in(i))); + else + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + } + } + + public static void copyClobber() throws Exception { + for( boolean killed : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode hi = testSplit(code,def); + hi.setDef(0,code._start); hi.setDef(1,def); + alloc.newLRG(hi)._reg=1; + new Op(null,null,killed ? A : null,false,code._start); + SplitNode lo = testSplit(code,hi); + lo.setDef(0,code._start); lo.setDef(1,hi); + alloc.newLRG(lo)._reg=0; + Op use = new Op(null,A,null,false,code._start,lo); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame(killed ? lo : def,use.in(1)); + } + CodeGen pre = graph(); + RegAlloc uncolored = new RegAlloc(pre); + Op def0 = new Op(A,null,null,false,pre._start); + uncolored.newLRG(def0)._mask=A; + Op fixed = new Op(A,null,null,false,pre._start); + uncolored.newLRG(fixed)._mask=A; + SplitNode copy = testSplit(pre,def0); + copy.setDef(0,pre._start); copy.setDef(1,def0); + assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); + } + + public static void coldLoopSelfConflict() { + for( boolean phiConflict : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op init = new Op(A,null,null,false,code._start); + LoopNode loop = new LoopNode(null,code._start); + PhiNode phi = new PhiNode("loop",TypeInteger.BOT,loop,init,null); + Op back = new Op(A,A,null,false,loop,phi); + phi.setDef(2,back); + Op use = new Op(null,A,null,false,loop,phi); + loop.setDef(2,loop); + LRG lrg = alloc.newLRG(phi); + lrg._mask = A; + alloc.union(lrg,init); alloc.union(lrg,back); + lrg.selfConflict(back); + if( phiConflict ) lrg.selfConflict(phi); + assertTrue(alloc.splitSelfConflict((byte)0,lrg)); + assertSame(phi,use.in(1)); // First try leaves the hot definition alone. + assertSame(back,phi.in(2)); + if( phiConflict ) assertTrue(phi.in(1) instanceof SplitNode); + // Even if the first attempt made no graph change, retry must split. + assertTrue(alloc.splitSelfConflict((byte)1,lrg)); + assertTrue(phi.in(2) instanceof SplitNode); + if( phiConflict ) assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void copyForward() throws Exception { + // Forwarding, fixed operand, two-address tie, intervening clobber, + // another user, and a scheduling-only edge. + for( int kind=0; kind<6; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode copy = testSplit(code,def); + copy.setDef(0,code._start); copy.setDef(1,def); + alloc.newLRG(copy)._reg=1; + if( kind==3 ) new Op(null,null,A,false,code._start); + int twoAddress = kind==2 ? 1 : 0; + RegMask mask = kind==1 ? B : kind==5 ? null : new RegMask(3L); + Op use = new Op(null,mask,null,false,code._start,copy) { + @Override public int twoAddress() { return twoAddress; } + }; + if( kind==4 ) new Op(null,B,null,false,code._start,copy); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame("copy case "+kind,kind==0 ? def : copy,use.in(1)); + assertEquals(kind==0 ? 0 : 1,alloc._spills); + } + } + + public static void coalescing() { + // Merge, incompatible masks, interference, capacity, and adjacency remapping. + for( int kind=0; kind<5; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + SplitNode copy = testSplit(code,def); + copy.setDef(0,code._start); copy.setDef(1,def); + Op use = new Op(null,new RegMask(3L),null,false,code._start,copy); + LRG from = alloc.newLRG(def), to = alloc.newLRG(copy); + from._mask = kind==1 ? A : new RegMask(3L); + to._mask = kind==1 ? B : new RegMask(3L); + from.machDef(def,false); from.machUse(copy,(short)1,false); + to.machDef(copy,false); to.machUse(use,(short)1,false); + LRG left = new LRG((short)100), right = new LRG((short)101); + if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); } + if( kind>=3 ) { + from.addNeighbor(left); left.addNeighbor(from); + if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); } + else { to.addNeighbor(left); left.addNeighbor(to); } + } + int fcnt=from.nadj(), tcnt=to.nadj(); + assertTrue(Coalesce.coalesce(0,alloc)); + if( kind==0 || kind==4 ) { + assertSame(def,use.in(1)); + assertSame(alloc.lrg(def),alloc.lrg(copy)); + assertSame(use,alloc.lrg(def)._machUse); + assertEquals(1,alloc.lrg(def)._uidx); + if( kind==4 ) { + assertEquals(1,left.nadj()); + assertSame(alloc.lrg(def),left._adj.at(0)); + assertSame(left,alloc.lrg(def)._adj.at(0)); + } + } else { + assertSame(copy,use.in(1)); + assertNotSame(alloc.lrg(def),alloc.lrg(copy)); + assertEquals(fcnt,from.nadj()); + assertEquals(tcnt,to.nadj()); + } + } + } + +} diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java new file mode 100644 index 00000000..0914d916 --- /dev/null +++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java @@ -0,0 +1,123 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.MulIX86; +import org.junit.Test; +import static org.junit.Assert.*; + +public class X86EncodingTest { + + @Test + public void testLogicalNotRegisters() { + CodeGen code = new CodeGen("return !arg;") + .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV"); + var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null); + assertNotNull("Must exercise logical not", not); + int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}}; + // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping + // registers, low-byte registers requiring REX, and extended registers. + String[] expected = { + "4885c00f94c00fb6c0", "4885c90f94c10fb6c9", + "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9", + "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9", + "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff" + }; + for (int i = 0; i < registers.length; i++) { + int dst = registers[i][0], src = registers[i][1]; + var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src); + not.encoding(enc); + assertArrayEquals("Logical not dst=" + dst + ", src=" + src, + java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray()); + } + } + + @Test + public void testLogicalNotExecution() throws java.io.IOException { + var dir = java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"), + "val logicalNot = { int x -> return !x; };"); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """ + #include <limits.h> + extern long long logicalNot(long long); + int main(void) { + long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32}; + for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++) + if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1; + return 0; + } + """); + com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1); + } + + @Test + public void testMultiplyImmediateRegisters() { + // Destination, source, expected REX and ModRM. Cross the register-8 + // boundary in both directions, with low/low and high/high controls. + int[][] cases = {{1, 9, 0x49, 0xC9}, {9, 1, 0x4C, 0xC9}, + {1, 2, 0x48, 0xCA}, {9, 10, 0x4D, 0xCA}}; + for (int immediate : new int[]{11, -11, 123456789, -123456789}) { + CodeGen code = new CodeGen("return arg * " + immediate + ";") + .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV"); + var mul = code._stop.walk(n -> n instanceof MulIX86 ? n : null); + assertNotNull("Must exercise immediate multiply", mul); + for (int[] regs : cases) { + var enc = new FixedRegisterEncoding( + code, mul, regs[0], mul.in(1), regs[1]); + ((MulIX86)mul).encoding(enc); + boolean small = immediate == 11 || immediate == -11; + assertEquals("REX for dst=" + regs[0] + ", src=" + regs[1], regs[2], enc.read1(0)); + assertEquals(small ? 0x6B : 0x69, enc.read1(1)); + assertEquals(regs[3], enc.read1(2)); + assertEquals(small ? 4 : 7, enc._bits.size()); + assertEquals(immediate, small ? (byte)enc.read1(3) : enc.read4(3)); + } + } + } + @Test + public void testMemoryCompare64Immediate32() { + for (int immediate : new int[]{123456789, -123456789}) { + String src = "int[] !a = new int[2]; a[0] = arg; return a[arg & 1] == " + immediate + ";"; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding, "x86_64_v2", "SystemV"); + var cmp = code._stop.walk(n -> n instanceof CmpMemX86 ? n : null); + assertNotNull("Must exercise a memory comparison", cmp); + var enc = code._encoding; + int start = enc._opStart[cmp._nid]; + + // REX.W, 81 /7, SIB with scale 8, disp8, and a sign-extended imm32. + assertEquals(0x48, enc.read1(start) & 0xF8); + assertEquals(0x81, enc.read1(start + 1)); + assertEquals(0x7C, enc.read1(start + 2)); + assertEquals(0xC0, enc.read1(start + 3) & 0xC0); + assertEquals(8, enc.read1(start + 4)); + assertEquals(immediate, enc.read4(start + 5)); + assertEquals("CMP r/m64 uses four immediate bytes", 9, enc._opLen[cmp._nid]); + + // SETE must immediately follow the CPU's nine-byte CMP instruction. + assertEquals(0x0F, enc.read1(start + 9)); + assertEquals(0x94, enc.read1(start + 10)); + } + } + + /** Exercise instruction encoders with explicit registers, independent of allocator choices. */ + private static class FixedRegisterEncoding extends Encoding { + private final Node _dst, _src; + private final short _dstReg, _srcReg; + + FixedRegisterEncoding(CodeGen code, Node dst, int dstReg, Node src, int srcReg) { + super(code); + _dst = dst; + _src = src; + _dstReg = (short)dstReg; + _srcReg = (short)srcReg; + } + + @Override public short reg(Node n) { + if (n == _dst) return _dstReg; + if (n == _src) return _srcReg; + throw new AssertionError("Unexpected register lookup"); + } + } +} |