# HG changeset patch # User Christian Haeubl # Date 1368023519 -7200 # Node ID 9529ab567367a4341421df558a380f8a5ba58db9 # Parent 8cee5c95b774ffbe9cb0250f0c46c659b472fd1a Drafted version of an inlining policy that uses the callee graph size as its metric. diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/Assumptions.java --- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/Assumptions.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/Assumptions.java Wed May 08 16:31:59 2013 +0200 @@ -362,4 +362,9 @@ count++; } + public void record(Assumptions assumptions) { + for (int i = 0; i < assumptions.count; i++) { + record(assumptions.list[i]); + } + } } diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ResolvedJavaMethod.java --- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ResolvedJavaMethod.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ResolvedJavaMethod.java Wed May 08 16:31:59 2013 +0200 @@ -57,13 +57,6 @@ int getCompiledCodeSize(); /** - * Returns an estimate how complex it is to compile this method. - * - * @return A value >= 0, where higher means more complex. - */ - int getCompilationComplexity(); - - /** * Returns the {@link ResolvedJavaType} object representing the class or interface that declares * this method. */ diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/Bytecodes.java --- a/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/Bytecodes.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/Bytecodes.java Wed May 08 16:31:59 2013 +0200 @@ -357,218 +357,212 @@ */ private static final int[] lengthArray = new int[256]; - /** - * An array that maps from a bytecode value to the estimated complexity of the bytecode in terms - * of generated machine code. - */ - private static final int[] compilationComplexityArray = new int[256]; - // Checkstyle: stop // @formatter:off static { - def(NOP , "nop" , "b" , 0); - def(ACONST_NULL , "aconst_null" , "b" , 0); - def(ICONST_M1 , "iconst_m1" , "b" , 0); - def(ICONST_0 , "iconst_0" , "b" , 0); - def(ICONST_1 , "iconst_1" , "b" , 0); - def(ICONST_2 , "iconst_2" , "b" , 0); - def(ICONST_3 , "iconst_3" , "b" , 0); - def(ICONST_4 , "iconst_4" , "b" , 0); - def(ICONST_5 , "iconst_5" , "b" , 0); - def(LCONST_0 , "lconst_0" , "b" , 0); - def(LCONST_1 , "lconst_1" , "b" , 0); - def(FCONST_0 , "fconst_0" , "b" , 0); - def(FCONST_1 , "fconst_1" , "b" , 0); - def(FCONST_2 , "fconst_2" , "b" , 0); - def(DCONST_0 , "dconst_0" , "b" , 0); - def(DCONST_1 , "dconst_1" , "b" , 0); - def(BIPUSH , "bipush" , "bc" , 0); - def(SIPUSH , "sipush" , "bcc" , 0); - def(LDC , "ldc" , "bi" , 0, TRAP); - def(LDC_W , "ldc_w" , "bii" , 0, TRAP); - def(LDC2_W , "ldc2_w" , "bii" , 0, TRAP); - def(ILOAD , "iload" , "bi" , 0, LOAD); - def(LLOAD , "lload" , "bi" , 0, LOAD); - def(FLOAD , "fload" , "bi" , 0, LOAD); - def(DLOAD , "dload" , "bi" , 0, LOAD); - def(ALOAD , "aload" , "bi" , 0, LOAD); - def(ILOAD_0 , "iload_0" , "b" , 0, LOAD); - def(ILOAD_1 , "iload_1" , "b" , 0, LOAD); - def(ILOAD_2 , "iload_2" , "b" , 0, LOAD); - def(ILOAD_3 , "iload_3" , "b" , 0, LOAD); - def(LLOAD_0 , "lload_0" , "b" , 0, LOAD); - def(LLOAD_1 , "lload_1" , "b" , 0, LOAD); - def(LLOAD_2 , "lload_2" , "b" , 0, LOAD); - def(LLOAD_3 , "lload_3" , "b" , 0, LOAD); - def(FLOAD_0 , "fload_0" , "b" , 0, LOAD); - def(FLOAD_1 , "fload_1" , "b" , 0, LOAD); - def(FLOAD_2 , "fload_2" , "b" , 0, LOAD); - def(FLOAD_3 , "fload_3" , "b" , 0, LOAD); - def(DLOAD_0 , "dload_0" , "b" , 0, LOAD); - def(DLOAD_1 , "dload_1" , "b" , 0, LOAD); - def(DLOAD_2 , "dload_2" , "b" , 0, LOAD); - def(DLOAD_3 , "dload_3" , "b" , 0, LOAD); - def(ALOAD_0 , "aload_0" , "b" , 0, LOAD); - def(ALOAD_1 , "aload_1" , "b" , 0, LOAD); - def(ALOAD_2 , "aload_2" , "b" , 0, LOAD); - def(ALOAD_3 , "aload_3" , "b" , 0, LOAD); - def(IALOAD , "iaload" , "b" , 0, TRAP); - def(LALOAD , "laload" , "b" , 0, TRAP); - def(FALOAD , "faload" , "b" , 0, TRAP); - def(DALOAD , "daload" , "b" , 0, TRAP); - def(AALOAD , "aaload" , "b" , 0, TRAP); - def(BALOAD , "baload" , "b" , 0, TRAP); - def(CALOAD , "caload" , "b" , 0, TRAP); - def(SALOAD , "saload" , "b" , 0, TRAP); - def(ISTORE , "istore" , "bi" , 0, STORE); - def(LSTORE , "lstore" , "bi" , 0, STORE); - def(FSTORE , "fstore" , "bi" , 0, STORE); - def(DSTORE , "dstore" , "bi" , 0, STORE); - def(ASTORE , "astore" , "bi" , 0, STORE); - def(ISTORE_0 , "istore_0" , "b" , 0, STORE); - def(ISTORE_1 , "istore_1" , "b" , 0, STORE); - def(ISTORE_2 , "istore_2" , "b" , 0, STORE); - def(ISTORE_3 , "istore_3" , "b" , 0, STORE); - def(LSTORE_0 , "lstore_0" , "b" , 0, STORE); - def(LSTORE_1 , "lstore_1" , "b" , 0, STORE); - def(LSTORE_2 , "lstore_2" , "b" , 0, STORE); - def(LSTORE_3 , "lstore_3" , "b" , 0, STORE); - def(FSTORE_0 , "fstore_0" , "b" , 0, STORE); - def(FSTORE_1 , "fstore_1" , "b" , 0, STORE); - def(FSTORE_2 , "fstore_2" , "b" , 0, STORE); - def(FSTORE_3 , "fstore_3" , "b" , 0, STORE); - def(DSTORE_0 , "dstore_0" , "b" , 0, STORE); - def(DSTORE_1 , "dstore_1" , "b" , 0, STORE); - def(DSTORE_2 , "dstore_2" , "b" , 0, STORE); - def(DSTORE_3 , "dstore_3" , "b" , 0, STORE); - def(ASTORE_0 , "astore_0" , "b" , 0, STORE); - def(ASTORE_1 , "astore_1" , "b" , 0, STORE); - def(ASTORE_2 , "astore_2" , "b" , 0, STORE); - def(ASTORE_3 , "astore_3" , "b" , 0, STORE); - def(IASTORE , "iastore" , "b" , 3, TRAP); - def(LASTORE , "lastore" , "b" , 3, TRAP); - def(FASTORE , "fastore" , "b" , 3, TRAP); - def(DASTORE , "dastore" , "b" , 3, TRAP); - def(AASTORE , "aastore" , "b" , 4, TRAP); - def(BASTORE , "bastore" , "b" , 3, TRAP); - def(CASTORE , "castore" , "b" , 3, TRAP); - def(SASTORE , "sastore" , "b" , 3, TRAP); - def(POP , "pop" , "b" , 0); - def(POP2 , "pop2" , "b" , 0); - def(DUP , "dup" , "b" , 0); - def(DUP_X1 , "dup_x1" , "b" , 0); - def(DUP_X2 , "dup_x2" , "b" , 0); - def(DUP2 , "dup2" , "b" , 0); - def(DUP2_X1 , "dup2_x1" , "b" , 0); - def(DUP2_X2 , "dup2_x2" , "b" , 0); - def(SWAP , "swap" , "b" , 0); - def(IADD , "iadd" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(LADD , "ladd" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(FADD , "fadd" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(DADD , "dadd" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(ISUB , "isub" , "b" , 1); - def(LSUB , "lsub" , "b" , 1); - def(FSUB , "fsub" , "b" , 1); - def(DSUB , "dsub" , "b" , 1); - def(IMUL , "imul" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(LMUL , "lmul" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(FMUL , "fmul" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(DMUL , "dmul" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(IDIV , "idiv" , "b" , 1, TRAP); - def(LDIV , "ldiv" , "b" , 1, TRAP); - def(FDIV , "fdiv" , "b" , 1); - def(DDIV , "ddiv" , "b" , 1); - def(IREM , "irem" , "b" , 1, TRAP); - def(LREM , "lrem" , "b" , 1, TRAP); - def(FREM , "frem" , "b" , 1); - def(DREM , "drem" , "b" , 1); - def(INEG , "ineg" , "b" , 1); - def(LNEG , "lneg" , "b" , 1); - def(FNEG , "fneg" , "b" , 1); - def(DNEG , "dneg" , "b" , 1); - def(ISHL , "ishl" , "b" , 1); - def(LSHL , "lshl" , "b" , 1); - def(ISHR , "ishr" , "b" , 1); - def(LSHR , "lshr" , "b" , 1); - def(IUSHR , "iushr" , "b" , 1); - def(LUSHR , "lushr" , "b" , 1); - def(IAND , "iand" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(LAND , "land" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(IOR , "ior" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(LOR , "lor" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(IXOR , "ixor" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(LXOR , "lxor" , "b" , 1, COMMUTATIVE | ASSOCIATIVE); - def(IINC , "iinc" , "bic" , 1, LOAD | STORE); - def(I2L , "i2l" , "b" , 1); - def(I2F , "i2f" , "b" , 1); - def(I2D , "i2d" , "b" , 1); - def(L2I , "l2i" , "b" , 1); - def(L2F , "l2f" , "b" , 1); - def(L2D , "l2d" , "b" , 1); - def(F2I , "f2i" , "b" , 1); - def(F2L , "f2l" , "b" , 1); - def(F2D , "f2d" , "b" , 1); - def(D2I , "d2i" , "b" , 1); - def(D2L , "d2l" , "b" , 1); - def(D2F , "d2f" , "b" , 1); - def(I2B , "i2b" , "b" , 1); - def(I2C , "i2c" , "b" , 1); - def(I2S , "i2s" , "b" , 1); - def(LCMP , "lcmp" , "b" , 1); - def(FCMPL , "fcmpl" , "b" , 1); - def(FCMPG , "fcmpg" , "b" , 1); - def(DCMPL , "dcmpl" , "b" , 1); - def(DCMPG , "dcmpg" , "b" , 1); - def(IFEQ , "ifeq" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IFNE , "ifne" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IFLT , "iflt" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IFGE , "ifge" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IFGT , "ifgt" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IFLE , "ifle" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IF_ICMPEQ , "if_icmpeq" , "boo" , 2, COMMUTATIVE | FALL_THROUGH | BRANCH); - def(IF_ICMPNE , "if_icmpne" , "boo" , 2, COMMUTATIVE | FALL_THROUGH | BRANCH); - def(IF_ICMPLT , "if_icmplt" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IF_ICMPGE , "if_icmpge" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IF_ICMPGT , "if_icmpgt" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IF_ICMPLE , "if_icmple" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IF_ACMPEQ , "if_acmpeq" , "boo" , 2, COMMUTATIVE | FALL_THROUGH | BRANCH); - def(IF_ACMPNE , "if_acmpne" , "boo" , 2, COMMUTATIVE | FALL_THROUGH | BRANCH); - def(GOTO , "goto" , "boo" , 1, STOP | BRANCH); - def(JSR , "jsr" , "boo" , 0, STOP | BRANCH); - def(RET , "ret" , "bi" , 0, STOP); - def(TABLESWITCH , "tableswitch" , "" , 4, STOP); - def(LOOKUPSWITCH , "lookupswitch" , "" , 4, STOP); - def(IRETURN , "ireturn" , "b" , 1, TRAP | STOP); - def(LRETURN , "lreturn" , "b" , 1, TRAP | STOP); - def(FRETURN , "freturn" , "b" , 1, TRAP | STOP); - def(DRETURN , "dreturn" , "b" , 1, TRAP | STOP); - def(ARETURN , "areturn" , "b" , 1, TRAP | STOP); - def(RETURN , "return" , "b" , 1, TRAP | STOP); - def(GETSTATIC , "getstatic" , "bjj" , 2, TRAP | FIELD_READ); - def(PUTSTATIC , "putstatic" , "bjj" , 2, TRAP | FIELD_WRITE); - def(GETFIELD , "getfield" , "bjj" , 2, TRAP | FIELD_READ); - def(PUTFIELD , "putfield" , "bjj" , 2, TRAP | FIELD_WRITE); - def(INVOKEVIRTUAL , "invokevirtual" , "bjj" , 7, TRAP | INVOKE); - def(INVOKESPECIAL , "invokespecial" , "bjj" , 5, TRAP | INVOKE); - def(INVOKESTATIC , "invokestatic" , "bjj" , 5, TRAP | INVOKE); - def(INVOKEINTERFACE , "invokeinterface" , "bjja_", 7, TRAP | INVOKE); - def(INVOKEDYNAMIC , "invokedynamic" , "bjjjj", 7, TRAP | INVOKE); - def(NEW , "new" , "bii" , 6, TRAP); - def(NEWARRAY , "newarray" , "bc" , 6, TRAP); - def(ANEWARRAY , "anewarray" , "bii" , 6, TRAP); - def(ARRAYLENGTH , "arraylength" , "b" , 2, TRAP); - def(ATHROW , "athrow" , "b" , 5, TRAP | STOP); - def(CHECKCAST , "checkcast" , "bii" , 3, TRAP); - def(INSTANCEOF , "instanceof" , "bii" , 4, TRAP); - def(MONITORENTER , "monitorenter" , "b" , 5, TRAP); - def(MONITOREXIT , "monitorexit" , "b" , 5, TRAP); - def(WIDE , "wide" , "" , 0); - def(MULTIANEWARRAY , "multianewarray" , "biic" , 6, TRAP); - def(IFNULL , "ifnull" , "boo" , 2, FALL_THROUGH | BRANCH); - def(IFNONNULL , "ifnonnull" , "boo" , 2, FALL_THROUGH | BRANCH); - def(GOTO_W , "goto_w" , "boooo", 1, STOP | BRANCH); - def(JSR_W , "jsr_w" , "boooo", 0, STOP | BRANCH); - def(BREAKPOINT , "breakpoint" , "b" , 0, TRAP); + def(NOP , "nop" , "b" ); + def(ACONST_NULL , "aconst_null" , "b" ); + def(ICONST_M1 , "iconst_m1" , "b" ); + def(ICONST_0 , "iconst_0" , "b" ); + def(ICONST_1 , "iconst_1" , "b" ); + def(ICONST_2 , "iconst_2" , "b" ); + def(ICONST_3 , "iconst_3" , "b" ); + def(ICONST_4 , "iconst_4" , "b" ); + def(ICONST_5 , "iconst_5" , "b" ); + def(LCONST_0 , "lconst_0" , "b" ); + def(LCONST_1 , "lconst_1" , "b" ); + def(FCONST_0 , "fconst_0" , "b" ); + def(FCONST_1 , "fconst_1" , "b" ); + def(FCONST_2 , "fconst_2" , "b" ); + def(DCONST_0 , "dconst_0" , "b" ); + def(DCONST_1 , "dconst_1" , "b" ); + def(BIPUSH , "bipush" , "bc" ); + def(SIPUSH , "sipush" , "bcc" ); + def(LDC , "ldc" , "bi" , TRAP); + def(LDC_W , "ldc_w" , "bii" , TRAP); + def(LDC2_W , "ldc2_w" , "bii" , TRAP); + def(ILOAD , "iload" , "bi" , LOAD); + def(LLOAD , "lload" , "bi" , LOAD); + def(FLOAD , "fload" , "bi" , LOAD); + def(DLOAD , "dload" , "bi" , LOAD); + def(ALOAD , "aload" , "bi" , LOAD); + def(ILOAD_0 , "iload_0" , "b" , LOAD); + def(ILOAD_1 , "iload_1" , "b" , LOAD); + def(ILOAD_2 , "iload_2" , "b" , LOAD); + def(ILOAD_3 , "iload_3" , "b" , LOAD); + def(LLOAD_0 , "lload_0" , "b" , LOAD); + def(LLOAD_1 , "lload_1" , "b" , LOAD); + def(LLOAD_2 , "lload_2" , "b" , LOAD); + def(LLOAD_3 , "lload_3" , "b" , LOAD); + def(FLOAD_0 , "fload_0" , "b" , LOAD); + def(FLOAD_1 , "fload_1" , "b" , LOAD); + def(FLOAD_2 , "fload_2" , "b" , LOAD); + def(FLOAD_3 , "fload_3" , "b" , LOAD); + def(DLOAD_0 , "dload_0" , "b" , LOAD); + def(DLOAD_1 , "dload_1" , "b" , LOAD); + def(DLOAD_2 , "dload_2" , "b" , LOAD); + def(DLOAD_3 , "dload_3" , "b" , LOAD); + def(ALOAD_0 , "aload_0" , "b" , LOAD); + def(ALOAD_1 , "aload_1" , "b" , LOAD); + def(ALOAD_2 , "aload_2" , "b" , LOAD); + def(ALOAD_3 , "aload_3" , "b" , LOAD); + def(IALOAD , "iaload" , "b" , TRAP); + def(LALOAD , "laload" , "b" , TRAP); + def(FALOAD , "faload" , "b" , TRAP); + def(DALOAD , "daload" , "b" , TRAP); + def(AALOAD , "aaload" , "b" , TRAP); + def(BALOAD , "baload" , "b" , TRAP); + def(CALOAD , "caload" , "b" , TRAP); + def(SALOAD , "saload" , "b" , TRAP); + def(ISTORE , "istore" , "bi" , STORE); + def(LSTORE , "lstore" , "bi" , STORE); + def(FSTORE , "fstore" , "bi" , STORE); + def(DSTORE , "dstore" , "bi" , STORE); + def(ASTORE , "astore" , "bi" , STORE); + def(ISTORE_0 , "istore_0" , "b" , STORE); + def(ISTORE_1 , "istore_1" , "b" , STORE); + def(ISTORE_2 , "istore_2" , "b" , STORE); + def(ISTORE_3 , "istore_3" , "b" , STORE); + def(LSTORE_0 , "lstore_0" , "b" , STORE); + def(LSTORE_1 , "lstore_1" , "b" , STORE); + def(LSTORE_2 , "lstore_2" , "b" , STORE); + def(LSTORE_3 , "lstore_3" , "b" , STORE); + def(FSTORE_0 , "fstore_0" , "b" , STORE); + def(FSTORE_1 , "fstore_1" , "b" , STORE); + def(FSTORE_2 , "fstore_2" , "b" , STORE); + def(FSTORE_3 , "fstore_3" , "b" , STORE); + def(DSTORE_0 , "dstore_0" , "b" , STORE); + def(DSTORE_1 , "dstore_1" , "b" , STORE); + def(DSTORE_2 , "dstore_2" , "b" , STORE); + def(DSTORE_3 , "dstore_3" , "b" , STORE); + def(ASTORE_0 , "astore_0" , "b" , STORE); + def(ASTORE_1 , "astore_1" , "b" , STORE); + def(ASTORE_2 , "astore_2" , "b" , STORE); + def(ASTORE_3 , "astore_3" , "b" , STORE); + def(IASTORE , "iastore" , "b" , TRAP); + def(LASTORE , "lastore" , "b" , TRAP); + def(FASTORE , "fastore" , "b" , TRAP); + def(DASTORE , "dastore" , "b" , TRAP); + def(AASTORE , "aastore" , "b" , TRAP); + def(BASTORE , "bastore" , "b" , TRAP); + def(CASTORE , "castore" , "b" , TRAP); + def(SASTORE , "sastore" , "b" , TRAP); + def(POP , "pop" , "b" ); + def(POP2 , "pop2" , "b" ); + def(DUP , "dup" , "b" ); + def(DUP_X1 , "dup_x1" , "b" ); + def(DUP_X2 , "dup_x2" , "b" ); + def(DUP2 , "dup2" , "b" ); + def(DUP2_X1 , "dup2_x1" , "b" ); + def(DUP2_X2 , "dup2_x2" , "b" ); + def(SWAP , "swap" , "b" ); + def(IADD , "iadd" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(LADD , "ladd" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(FADD , "fadd" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(DADD , "dadd" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(ISUB , "isub" , "b" ); + def(LSUB , "lsub" , "b" ); + def(FSUB , "fsub" , "b" ); + def(DSUB , "dsub" , "b" ); + def(IMUL , "imul" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(LMUL , "lmul" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(FMUL , "fmul" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(DMUL , "dmul" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(IDIV , "idiv" , "b" , TRAP); + def(LDIV , "ldiv" , "b" , TRAP); + def(FDIV , "fdiv" , "b" ); + def(DDIV , "ddiv" , "b" ); + def(IREM , "irem" , "b" , TRAP); + def(LREM , "lrem" , "b" , TRAP); + def(FREM , "frem" , "b" ); + def(DREM , "drem" , "b" ); + def(INEG , "ineg" , "b" ); + def(LNEG , "lneg" , "b" ); + def(FNEG , "fneg" , "b" ); + def(DNEG , "dneg" , "b" ); + def(ISHL , "ishl" , "b" ); + def(LSHL , "lshl" , "b" ); + def(ISHR , "ishr" , "b" ); + def(LSHR , "lshr" , "b" ); + def(IUSHR , "iushr" , "b" ); + def(LUSHR , "lushr" , "b" ); + def(IAND , "iand" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(LAND , "land" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(IOR , "ior" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(LOR , "lor" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(IXOR , "ixor" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(LXOR , "lxor" , "b" , COMMUTATIVE | ASSOCIATIVE); + def(IINC , "iinc" , "bic" , LOAD | STORE); + def(I2L , "i2l" , "b" ); + def(I2F , "i2f" , "b" ); + def(I2D , "i2d" , "b" ); + def(L2I , "l2i" , "b" ); + def(L2F , "l2f" , "b" ); + def(L2D , "l2d" , "b" ); + def(F2I , "f2i" , "b" ); + def(F2L , "f2l" , "b" ); + def(F2D , "f2d" , "b" ); + def(D2I , "d2i" , "b" ); + def(D2L , "d2l" , "b" ); + def(D2F , "d2f" , "b" ); + def(I2B , "i2b" , "b" ); + def(I2C , "i2c" , "b" ); + def(I2S , "i2s" , "b" ); + def(LCMP , "lcmp" , "b" ); + def(FCMPL , "fcmpl" , "b" ); + def(FCMPG , "fcmpg" , "b" ); + def(DCMPL , "dcmpl" , "b" ); + def(DCMPG , "dcmpg" , "b" ); + def(IFEQ , "ifeq" , "boo" , FALL_THROUGH | BRANCH); + def(IFNE , "ifne" , "boo" , FALL_THROUGH | BRANCH); + def(IFLT , "iflt" , "boo" , FALL_THROUGH | BRANCH); + def(IFGE , "ifge" , "boo" , FALL_THROUGH | BRANCH); + def(IFGT , "ifgt" , "boo" , FALL_THROUGH | BRANCH); + def(IFLE , "ifle" , "boo" , FALL_THROUGH | BRANCH); + def(IF_ICMPEQ , "if_icmpeq" , "boo" , COMMUTATIVE | FALL_THROUGH | BRANCH); + def(IF_ICMPNE , "if_icmpne" , "boo" , COMMUTATIVE | FALL_THROUGH | BRANCH); + def(IF_ICMPLT , "if_icmplt" , "boo" , FALL_THROUGH | BRANCH); + def(IF_ICMPGE , "if_icmpge" , "boo" , FALL_THROUGH | BRANCH); + def(IF_ICMPGT , "if_icmpgt" , "boo" , FALL_THROUGH | BRANCH); + def(IF_ICMPLE , "if_icmple" , "boo" , FALL_THROUGH | BRANCH); + def(IF_ACMPEQ , "if_acmpeq" , "boo" , COMMUTATIVE | FALL_THROUGH | BRANCH); + def(IF_ACMPNE , "if_acmpne" , "boo" , COMMUTATIVE | FALL_THROUGH | BRANCH); + def(GOTO , "goto" , "boo" , STOP | BRANCH); + def(JSR , "jsr" , "boo" , STOP | BRANCH); + def(RET , "ret" , "bi" , STOP); + def(TABLESWITCH , "tableswitch" , "" , STOP); + def(LOOKUPSWITCH , "lookupswitch" , "" , STOP); + def(IRETURN , "ireturn" , "b" , TRAP | STOP); + def(LRETURN , "lreturn" , "b" , TRAP | STOP); + def(FRETURN , "freturn" , "b" , TRAP | STOP); + def(DRETURN , "dreturn" , "b" , TRAP | STOP); + def(ARETURN , "areturn" , "b" , TRAP | STOP); + def(RETURN , "return" , "b" , TRAP | STOP); + def(GETSTATIC , "getstatic" , "bjj" , TRAP | FIELD_READ); + def(PUTSTATIC , "putstatic" , "bjj" , TRAP | FIELD_WRITE); + def(GETFIELD , "getfield" , "bjj" , TRAP | FIELD_READ); + def(PUTFIELD , "putfield" , "bjj" , TRAP | FIELD_WRITE); + def(INVOKEVIRTUAL , "invokevirtual" , "bjj" , TRAP | INVOKE); + def(INVOKESPECIAL , "invokespecial" , "bjj" , TRAP | INVOKE); + def(INVOKESTATIC , "invokestatic" , "bjj" , TRAP | INVOKE); + def(INVOKEINTERFACE , "invokeinterface" , "bjja_", TRAP | INVOKE); + def(INVOKEDYNAMIC , "invokedynamic" , "bjjjj", TRAP | INVOKE); + def(NEW , "new" , "bii" , TRAP); + def(NEWARRAY , "newarray" , "bc" , TRAP); + def(ANEWARRAY , "anewarray" , "bii" , TRAP); + def(ARRAYLENGTH , "arraylength" , "b" , TRAP); + def(ATHROW , "athrow" , "b" , TRAP | STOP); + def(CHECKCAST , "checkcast" , "bii" , TRAP); + def(INSTANCEOF , "instanceof" , "bii" , TRAP); + def(MONITORENTER , "monitorenter" , "b" , TRAP); + def(MONITOREXIT , "monitorexit" , "b" , TRAP); + def(WIDE , "wide" , "" ); + def(MULTIANEWARRAY , "multianewarray" , "biic" , TRAP); + def(IFNULL , "ifnull" , "boo" , FALL_THROUGH | BRANCH); + def(IFNONNULL , "ifnonnull" , "boo" , FALL_THROUGH | BRANCH); + def(GOTO_W , "goto_w" , "boooo", STOP | BRANCH); + def(JSR_W , "jsr_w" , "boooo", STOP | BRANCH); + def(BREAKPOINT , "breakpoint" , "b" , TRAP); } // @formatter:on // Checkstyle: resume @@ -596,16 +590,6 @@ } /** - * Gets the compilation complexity for a given opcode. - * - * @param opcode an opcode - * @return a value >= 0 - */ - public static int compilationComplexity(int opcode) { - return compilationComplexityArray[opcode & 0xff]; - } - - /** * Gets the lower-case mnemonic for a given opcode. * * @param opcode an opcode @@ -809,8 +793,8 @@ * @param name instruction name (should be lower case) * @param format encodes the length of the instruction */ - private static void def(int opcode, String name, String format, int compilationComplexity) { - def(opcode, name, format, compilationComplexity, 0); + private static void def(int opcode, String name, String format) { + def(opcode, name, format, 0); } /** @@ -820,12 +804,11 @@ * @param format encodes the length of the instruction * @param flags the set of {@link Flags} associated with the instruction */ - private static void def(int opcode, String name, String format, int compilationComplexity, int flags) { + private static void def(int opcode, String name, String format, int flags) { assert nameArray[opcode] == null : "opcode " + opcode + " is already bound to name " + nameArray[opcode]; nameArray[opcode] = name; int instructionLength = format.length(); lengthArray[opcode] = instructionLength; - compilationComplexityArray[opcode] = compilationComplexity; Bytecodes.flagsArray[opcode] = flags; assert !isConditionalBranch(opcode) || isBranch(opcode) : "a conditional branch must also be a branch"; diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Wed May 08 16:31:59 2013 +0200 @@ -42,6 +42,7 @@ import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.common.InliningPhase.CompiledMethodInfo; import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.phases.tiers.*; @@ -137,15 +138,21 @@ plan.runPhases(PhasePosition.HIGH_LEVEL, graph); + CompiledMethodInfo info = InliningPhase.compiledMethodInfo(graph.method()); + analyzeInvokes(graph, info); + Suites.DEFAULT.getHighTier().apply(graph, highTierContext); + info.setHighLevelNodes(graph.getNodeCount()); MidTierContext midTierContext = new MidTierContext(runtime, assumptions, replacements, target); Suites.DEFAULT.getMidTier().apply(graph, midTierContext); + info.setMidLevelNodes(graph.getNodeCount()); plan.runPhases(PhasePosition.LOW_LEVEL, graph); LowTierContext lowTierContext = new LowTierContext(runtime, assumptions, replacements, target); Suites.DEFAULT.getLowTier().apply(graph, lowTierContext); + info.setLowLevelNodes(graph.getNodeCount()); final SchedulePhase schedule = new SchedulePhase(); schedule.apply(graph); @@ -173,6 +180,21 @@ } + private static void analyzeInvokes(final StructuredGraph graph, CompiledMethodInfo info) { + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + double summedUpProbabilityOfRemainingInvokes = 0; + double maxProbabilityOfRemainingInvokes = 0; + int invokes = 0; + for (Invoke invoke : graph.getInvokes()) { + summedUpProbabilityOfRemainingInvokes += nodeProbabilities.get(invoke.asNode()); + maxProbabilityOfRemainingInvokes = Math.max(maxProbabilityOfRemainingInvokes, nodeProbabilities.get(invoke.asNode())); + invokes++; + } + info.setSummedUpProbabilityOfRemainingInvokes(summedUpProbabilityOfRemainingInvokes); + info.setMaxProbabilityOfRemainingInvokes(maxProbabilityOfRemainingInvokes); + info.setNumberOfRemainingInvokes(invokes); + } + public static LIRGenerator emitLIR(Backend backend, final TargetDescription target, final LIR lir, StructuredGraph graph, final ResolvedJavaMethod method) { final FrameMap frameMap = backend.newFrameMap(); final LIRGenerator lirGen = backend.newLIRGenerator(graph, frameMap, method, lir); @@ -214,6 +236,7 @@ TargetMethodAssembler tasm = backend.newAssembler(lirGen, compilationResult); backend.emitCode(tasm, method, lirGen); CompilationResult result = tasm.finishTargetMethod(method, false); + InliningPhase.compiledMethodInfo(method).setCompiledCodeSize(result.getTargetCodeSize()); if (!assumptions.isEmpty()) { result.setAssumptions(assumptions); } diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java Wed May 08 16:31:59 2013 +0200 @@ -23,7 +23,6 @@ package com.oracle.graal.hotspot; import static com.oracle.graal.nodes.StructuredGraph.*; -import static com.oracle.graal.phases.common.InliningUtil.*; import java.lang.reflect.Modifier; import java.util.concurrent.*; @@ -38,6 +37,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.common.*; public final class CompilationTask implements Runnable, Comparable { @@ -156,7 +156,7 @@ // Compiling method substitution - must clone the graph graph = graph.copy(); } - InlinedBytecodes.add(method.getCodeSize()); + InliningUtil.InlinedBytecodes.add(method.getCodeSize()); return GraalCompiler.compileMethod(graalRuntime.getRuntime(), replacements, graalRuntime.getBackend(), graalRuntime.getTarget(), method, graph, graalRuntime.getCache(), plan, optimisticOpts, method.getSpeculationLog()); } diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java Wed May 08 16:31:59 2013 +0200 @@ -27,7 +27,6 @@ import static com.oracle.graal.hotspot.CompilationTask.*; import static com.oracle.graal.hotspot.HotSpotGraalRuntime.*; import static com.oracle.graal.java.GraphBuilderPhase.*; -import static com.oracle.graal.phases.common.InliningUtil.*; import java.io.*; import java.lang.reflect.*; @@ -49,6 +48,7 @@ import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; +import com.oracle.graal.phases.common.*; import com.oracle.graal.printer.*; import com.oracle.graal.replacements.*; @@ -319,7 +319,7 @@ CompilationStatistics.clear(phase); if (graalRuntime.getConfig().ciTime) { parsedBytecodesPerSecond = MetricRateInPhase.snapshot(phase, parsedBytecodesPerSecond, BytecodesParsed, CompilationTime, TimeUnit.SECONDS); - inlinedBytecodesPerSecond = MetricRateInPhase.snapshot(phase, inlinedBytecodesPerSecond, InlinedBytecodes, CompilationTime, TimeUnit.SECONDS); + inlinedBytecodesPerSecond = MetricRateInPhase.snapshot(phase, inlinedBytecodesPerSecond, InliningUtil.InlinedBytecodes, CompilationTime, TimeUnit.SECONDS); } } diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotResolvedJavaMethod.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotResolvedJavaMethod.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotResolvedJavaMethod.java Wed May 08 16:31:59 2013 +0200 @@ -23,7 +23,7 @@ package com.oracle.graal.hotspot.meta; import static com.oracle.graal.api.meta.MetaUtil.*; -import static com.oracle.graal.graph.FieldIntrospection.*; +import static com.oracle.graal.graph.UnsafeAccess.*; import static com.oracle.graal.hotspot.HotSpotGraalRuntime.*; import java.lang.annotation.*; @@ -34,7 +34,6 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.api.meta.ProfilingInfo.TriState; -import com.oracle.graal.bytecode.*; import com.oracle.graal.hotspot.*; import com.oracle.graal.hotspot.debug.*; import com.oracle.graal.phases.*; @@ -59,7 +58,6 @@ private Map compilerStorage; private HotSpotMethodData methodData; private byte[] code; - private int compilationComplexity; private CompilationTask currentTask; private SpeculationLog speculationLog; @@ -199,22 +197,6 @@ } @Override - public int getCompilationComplexity() { - if (compilationComplexity <= 0 && getCodeSize() > 0) { - BytecodeStream s = new BytecodeStream(getCode()); - int result = 0; - int currentBC; - while ((currentBC = s.currentBC()) != Bytecodes.END) { - result += Bytecodes.compilationComplexity(currentBC); - s.next(); - } - assert result > 0; - compilationComplexity = result; - } - return compilationComplexity; - } - - @Override public ProfilingInfo getProfilingInfo() { ProfilingInfo info; diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InlineableElement.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InlineableElement.java Wed May 08 16:31:59 2013 +0200 @@ -0,0 +1,30 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes; + +public interface InlineableElement { + + int getNodeCount(); + + Iterable getInvokes(); +} diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Wed May 08 16:31:59 2013 +0200 @@ -83,7 +83,9 @@ @Override public Map getDebugProperties(Map map) { Map debugProperties = super.getDebugProperties(map); - debugProperties.put("targetMethod", callTarget.targetName()); + if (callTarget != null) { + debugProperties.put("targetMethod", callTarget.targetName()); + } return debugProperties; } diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Wed May 08 16:31:59 2013 +0200 @@ -35,7 +35,7 @@ * A graph that contains at least one distinguished node : the {@link #start() start} node. This * node is the start of the control flow of the graph. */ -public class StructuredGraph extends Graph { +public class StructuredGraph extends Graph implements InlineableElement { public static final int INVOCATION_ENTRY_BCI = -1; public static final long INVALID_GRAPH_ID = -1; diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Wed May 08 16:31:59 2013 +0200 @@ -22,7 +22,6 @@ */ package com.oracle.graal.phases.common; -import java.lang.reflect.*; import java.util.*; import java.util.concurrent.*; @@ -31,38 +30,30 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; import com.oracle.graal.phases.common.InliningUtil.InlineInfo; -import com.oracle.graal.phases.common.InliningUtil.InliningCallback; import com.oracle.graal.phases.common.InliningUtil.InliningPolicy; import com.oracle.graal.phases.graph.*; -public class InliningPhase extends Phase implements InliningCallback { +public class InliningPhase extends Phase { - /* - * - Detect method which only call another method with some parameters set to constants: void - * foo(a) -> void foo(a, b) -> void foo(a, b, c) ... These should not be taken into account when - * determining inlining depth. - honor the result of overrideInliningDecision(0, caller, - * invoke.bci, method, true); - */ + private static final HashMap compiledMethodInfo = new HashMap<>(); private final PhasePlan plan; - private final MetaAccessProvider runtime; - private final Assumptions assumptions; + private final Assumptions compilationAssumptions; private final Replacements replacements; private final GraphCache cache; private final InliningPolicy inliningPolicy; private final OptimisticOptimizations optimisticOpts; - private CustomCanonicalizer customCanonicalizer; + private final InliningData data; + private CustomCanonicalizer customCanonicalizer; private int inliningCount; - private int maxMethodPerInlining = Integer.MAX_VALUE; // Metrics @@ -73,18 +64,33 @@ public InliningPhase(MetaAccessProvider runtime, Map hints, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) { - this(runtime, replacements, assumptions, cache, plan, createInliningPolicy(runtime, replacements, assumptions, optimisticOpts, hints), optimisticOpts); + this(runtime, replacements, assumptions, cache, plan, optimisticOpts, hints); + } + + public InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) { + this(runtime, replacements, assumptions, cache, plan, optimisticOpts, null); } - public InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, InliningPolicy inliningPolicy, - OptimisticOptimizations optimisticOpts) { + private InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts, + Map hints) { this.runtime = runtime; this.replacements = replacements; - this.assumptions = assumptions; + this.compilationAssumptions = assumptions; this.cache = cache; this.plan = plan; - this.inliningPolicy = inliningPolicy; + this.inliningPolicy = new GreedyInliningPolicy(replacements, hints); this.optimisticOpts = optimisticOpts; + + this.data = new InliningData(); + } + + public static synchronized CompiledMethodInfo compiledMethodInfo(ResolvedJavaMethod m) { + CompiledMethodInfo info = compiledMethodInfo.get(m); + if (info == null) { + info = new CompiledMethodInfo(); + compiledMethodInfo.put(m, info); + } + return info; } public void setCustomCanonicalizer(CustomCanonicalizer customCanonicalizer) { @@ -99,261 +105,422 @@ return inliningCount; } + static class InliningData { + + private static final GraphInfo DummyGraphInfo = new GraphInfo(null, new Stack(), 1.0, 1.0); + + private final ArrayDeque graphQueue; + private final ArrayDeque invocationQueue; + + private int maxGraphs = 1; + + public InliningData() { + this.graphQueue = new ArrayDeque<>(); + this.invocationQueue = new ArrayDeque<>(); + } + + public void pushGraph(StructuredGraph graph, double probability, double relevance) { + assert !contains(graph); + NodeBitMap visitedFixedNodes = graph.createNodeBitMap(); + Stack invokes = new InliningIterator(graph.start(), visitedFixedNodes).apply(); + assert invokes.size() == count(graph.getInvokes()); + graphQueue.push(new GraphInfo(graph, invokes, probability, relevance)); + assert graphQueue.size() <= maxGraphs; + } + + public void pushGraphDummy() { + graphQueue.push(DummyGraphInfo); + } + + public boolean hasUnprocessedGraphs() { + return !graphQueue.isEmpty(); + } + + public GraphInfo currentGraph() { + return graphQueue.peek(); + } + + public void popGraph() { + graphQueue.pop(); + assert graphQueue.size() <= maxGraphs; + } + + public MethodInvocation currentInvocation() { + return invocationQueue.peek(); + } + + public MethodInvocation pushInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) { + MethodInvocation methodInvocation = new MethodInvocation(info, new Assumptions(assumptions.useOptimisticAssumptions()), probability, relevance); + invocationQueue.push(methodInvocation); + maxGraphs += info.numberOfMethods(); + assert graphQueue.size() <= maxGraphs; + return methodInvocation; + } + + public void popInvocation() { + maxGraphs -= invocationQueue.peek().callee.numberOfMethods(); + assert graphQueue.size() <= maxGraphs; + invocationQueue.pop(); + } + + public int countRecursiveInlining(ResolvedJavaMethod method) { + int count = 0; + for (GraphInfo graphInfo : graphQueue) { + if (method.equals(graphInfo.graph().method())) { + count++; + } + } + return count; + } + + @Override + public String toString() { + StringBuilder result = new StringBuilder("Invocations: "); + + for (MethodInvocation invocation : invocationQueue) { + result.append(invocation.callee().numberOfMethods()); + result.append("x "); + result.append(invocation.callee().invoke()); + result.append("; "); + } + + result.append("\nGraphs: "); + for (GraphInfo graph : graphQueue) { + result.append(graph.graph()); + result.append("; "); + } + + return result.toString(); + } + + private boolean contains(StructuredGraph graph) { + for (GraphInfo info : graphQueue) { + if (info.graph() == graph) { + return true; + } + } + return false; + } + + private static int count(Iterable invokes) { + int count = 0; + Iterator iterator = invokes.iterator(); + while (iterator.hasNext()) { + iterator.next(); + count++; + } + return count; + } + + public int inliningDepth() { + return invocationQueue.size(); + } + } + + private static class MethodInvocation { + + private final InlineInfo callee; + private final Assumptions assumptions; + private final double probability; + private final double relevance; + + private int processedGraphs; + + public MethodInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) { + this.callee = info; + this.assumptions = assumptions; + this.probability = probability; + this.relevance = relevance; + } + + public void incrementProcessedGraphs() { + processedGraphs++; + } + + public boolean processedAllGraphs() { + assert processedGraphs <= callee.numberOfMethods(); + return processedGraphs == callee.numberOfMethods(); + } + + public InlineInfo callee() { + return callee; + } + + public Assumptions assumptions() { + return assumptions; + } + + public double probability() { + return probability; + } + + public double relevance() { + return relevance; + } + } + @Override protected void run(final StructuredGraph graph) { - NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); - NodesToDoubles nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); - inliningPolicy.initialize(graph); - - while (inliningPolicy.continueInlining(graph)) { - final InlineInfo candidate = inliningPolicy.next(); - - if (candidate != null) { - boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate, nodeProbabilities, nodeRelevance); - isWorthInlining &= candidate.numberOfMethods() <= maxMethodPerInlining; + data.pushGraph(graph, 1.0, 1.0); - metricInliningConsidered.increment(); - if (isWorthInlining) { - int mark = graph.getMark(); - try { - List invokeUsages = candidate.invoke().asNode().usages().snapshot(); - candidate.inline(graph, runtime, replacements, this, assumptions); - Debug.dump(graph, "after %s", candidate); - Iterable newNodes = graph.getNewNodes(mark); - inliningPolicy.scanInvokes(newNodes); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase.Instance(runtime, assumptions, invokeUsages, mark, customCanonicalizer).apply(graph); - } - - nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); - nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); - - inliningCount++; - metricInliningPerformed.increment(); - } catch (BailoutException bailout) { - throw bailout; - } catch (AssertionError e) { - throw new GraalInternalError(e).addContext(candidate.toString()); - } catch (RuntimeException e) { - throw new GraalInternalError(e).addContext(candidate.toString()); - } catch (GraalInternalError e) { - throw e.addContext(candidate.toString()); + while (data.hasUnprocessedGraphs()) { + GraphInfo graphInfo = data.currentGraph(); + if (graphInfo.hasRemainingInvokes() && inliningPolicy.continueInlining(data)) { + processNextInvoke(graphInfo); + } else { + data.popGraph(); + MethodInvocation currentInvoke = data.currentInvocation(); + if (currentInvoke != null) { + assert currentInvoke.callee().invoke().asNode().isAlive(); + currentInvoke.incrementProcessedGraphs(); + if (currentInvoke.processedAllGraphs()) { + data.popInvocation(); + MethodInvocation parentInvoke = data.currentInvocation(); + tryToInline(data.currentGraph(), currentInvoke, parentInvoke); } - } else if (optimisticOpts.devirtualizeInvokes()) { - candidate.tryToDevirtualizeInvoke(graph, runtime, assumptions); } } } } - @Override - public StructuredGraph buildGraph(final ResolvedJavaMethod method) { - metricInliningRuns.increment(); + private void processNextInvoke(GraphInfo graphInfo) { + // process the next invoke and enqueue all its graphs for processing + Invoke invoke = graphInfo.popInvoke(); + MethodInvocation callerInvocation = data.currentInvocation(); + Assumptions parentAssumptions = callerInvocation == null ? compilationAssumptions : callerInvocation.assumptions(); + InlineInfo info = InliningUtil.getInlineInfo(data, invoke, maxMethodPerInlining, replacements, parentAssumptions, optimisticOpts); + + if (info != null) { + double callerProbability = graphInfo.getInvokeProbability(invoke); + double callerRelevance = graphInfo.getInvokeRelevance(invoke); + MethodInvocation calleeInvocation = data.pushInvocation(info, parentAssumptions, callerProbability, callerRelevance); + + for (int i = 0; i < info.numberOfMethods(); i++) { + InlineableElement elem = getInlineableElement(info.methodAt(i), info.invoke(), calleeInvocation.assumptions()); + info.setInlinableElement(i, elem); + if (elem instanceof StructuredGraph) { + data.pushGraph((StructuredGraph) elem, callerProbability * info.probabilityAt(i), callerRelevance * info.relevanceAt(i)); + } else { + data.pushGraphDummy(); + } + } + } + } + + private void tryToInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvoke) { + InlineInfo callee = calleeInfo.callee(); + Assumptions callerAssumptions = parentInvoke == null ? compilationAssumptions : parentInvoke.assumptions(); + + if (inliningPolicy.isWorthInlining(callee, calleeInfo.probability(), calleeInfo.relevance())) { + doInline(callerGraphInfo, calleeInfo, callerAssumptions); + } else if (optimisticOpts.devirtualizeInvokes()) { + callee.tryToDevirtualizeInvoke(runtime, callerAssumptions); + } + metricInliningConsidered.increment(); + } + + private void doInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, Assumptions callerAssumptions) { + StructuredGraph callerGraph = callerGraphInfo.graph(); + int mark = callerGraph.getMark(); + InlineInfo callee = calleeInfo.callee(); + try { + List invokeUsages = callee.invoke().asNode().usages().snapshot(); + callee.inline(runtime, callerAssumptions); + callerAssumptions.record(calleeInfo.assumptions()); + metricInliningRuns.increment(); + Debug.dump(callerGraph, "after %s", callee); + + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase.Instance(runtime, callerAssumptions, invokeUsages, mark, customCanonicalizer).apply(callerGraph); + +// if (callerGraph.getNewNodes(mark).contains(Invoke.class)) { +// // TODO (chaeubl): invoke nodes might be created during canonicalization, which +// // is bad for the CF ordering of the invokes but we still have to handle it properly... +// } + } + + callerGraphInfo.computeProbabilities(); + + inliningCount++; + metricInliningPerformed.increment(); + } catch (BailoutException bailout) { + throw bailout; + } catch (AssertionError | RuntimeException e) { + throw new GraalInternalError(e).addContext(callee.toString()); + } catch (GraalInternalError e) { + throw e.addContext(callee.toString()); + } + } + + private InlineableElement getInlineableElement(final ResolvedJavaMethod method, Invoke invoke, Assumptions assumptions) { + Class macroNodeClass = InliningUtil.getMacroNodeClass(replacements, method); + if (macroNodeClass != null) { + return new InliningUtil.InlineableMacroNode(macroNodeClass); + } else { + return buildGraph(method, invoke, assumptions); + } + } + + private StructuredGraph buildGraph(final ResolvedJavaMethod method, final Invoke invoke, final Assumptions assumptions) { + final StructuredGraph newGraph; + final boolean parseBytecodes; + + // TODO (chaeubl): copying the graph is only necessary if it is modified + StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(replacements, method); + if (intrinsicGraph != null) { + newGraph = intrinsicGraph.copy(); + parseBytecodes = false; + } else { + StructuredGraph cachedGraph = getCachedGraph(method); + if (cachedGraph != null) { + newGraph = cachedGraph.copy(); + parseBytecodes = false; + } else { + newGraph = new StructuredGraph(method); + parseBytecodes = true; + } + } + + return Debug.scope("InlineGraph", newGraph, new Callable() { + + @Override + public StructuredGraph call() throws Exception { + if (parseBytecodes) { + parseBytecodes(newGraph, assumptions); + } + + if (GraalOptions.PropagateArgumentsDuringInlining) { + // TODO (chaeubl): if args are not more concrete, inlining will not change the + // size of the graph + NodeInputList args = invoke.callTarget().arguments(); + for (LocalNode localNode : newGraph.getNodes(LocalNode.class).snapshot()) { + ValueNode arg = args.get(localNode.index()); + if (arg.isConstant()) { + Constant constant = arg.asConstant(); + newGraph.replaceFloating(localNode, ConstantNode.forConstant(constant, runtime, newGraph)); + } else { + localNode.setStamp(localNode.stamp().join(arg.stamp())); + } + } + + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); + } + } + + return newGraph; + } + }); + } + + private StructuredGraph getCachedGraph(ResolvedJavaMethod method) { if (GraalOptions.CacheGraphs && cache != null) { StructuredGraph cachedGraph = cache.get(method); if (cachedGraph != null) { return cachedGraph; } } - final StructuredGraph newGraph = new StructuredGraph(method); - return Debug.scope("InlineGraph", newGraph, new Callable() { + return null; + } - @Override - public StructuredGraph call() throws Exception { - if (plan != null) { - plan.runPhases(PhasePosition.AFTER_PARSING, newGraph); - } - assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; + private StructuredGraph parseBytecodes(StructuredGraph newGraph, Assumptions assumptions) { + if (plan != null) { + plan.runPhases(PhasePosition.AFTER_PARSING, newGraph); + } + assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; - new DeadCodeEliminationPhase().apply(newGraph); + new DeadCodeEliminationPhase().apply(newGraph); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); - } - if (GraalOptions.CullFrameStates) { - new CullFrameStatesPhase().apply(newGraph); - } - if (GraalOptions.CacheGraphs && cache != null) { - cache.put(newGraph); - } - return newGraph; - } - }); + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); + } + + if (GraalOptions.CullFrameStates) { + new CullFrameStatesPhase().apply(newGraph); + } + if (GraalOptions.CacheGraphs && cache != null) { + cache.put(newGraph.copy()); + } + return newGraph; } - private interface InliningDecision { + private static class GraphInfo { + + private final StructuredGraph graph; + private final Stack remainingInvokes; + private final double probability; + private final double relevance; + private NodesToDoubles nodeProbabilities; + private NodesToDoubles nodeRelevance; + + public GraphInfo(StructuredGraph graph, Stack invokes, double probability, double relevance) { + this.graph = graph; + this.remainingInvokes = invokes; + this.probability = probability; + this.relevance = relevance; + + if (graph != null) { + computeProbabilities(); + } + } - boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance); + public boolean hasRemainingInvokes() { + return !remainingInvokes.isEmpty(); + } + + public StructuredGraph graph() { + return graph; + } + + public Invoke popInvoke() { + return remainingInvokes.pop(); + } + + public void computeProbabilities() { + nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); + } + + public double getInvokeProbability(Invoke invoke) { + return probability * nodeProbabilities.get(invoke.asNode()); + } + + public double getInvokeRelevance(Invoke invoke) { + return Math.min(relevance, 1.0) * nodeRelevance.get(invoke.asNode()); + } } - private static class GreedySizeBasedInliningDecision implements InliningDecision { + private abstract static class AbstractInliningPolicy implements InliningPolicy { - private final MetaAccessProvider runtime; - private final Replacements replacements; - private final Map hints; + protected final Replacements replacements; + protected final Map hints; - public GreedySizeBasedInliningDecision(MetaAccessProvider runtime, Replacements replacements, Map hints) { - this.runtime = runtime; + public AbstractInliningPolicy(Replacements replacements, Map hints) { this.replacements = replacements; this.hints = hints; } - @Override - public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { - /* - * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> - * will be compiled anyways and it is likely that we are the only caller... might be - * useful to inline those methods but increases bootstrap time (maybe those methods are - * also getting queued in the compilation queue concurrently) - */ - - if (GraalOptions.AlwaysInlineIntrinsics) { - if (onlyIntrinsics(replacements, info)) { - return InliningUtil.logInlinedMethod(info, "intrinsic"); - } - } else { - if (onlyForcedIntrinsics(replacements, info)) { - return InliningUtil.logInlinedMethod(info, "intrinsic"); - } - } - - double bonus = 1; - if (hints != null && hints.containsKey(info.invoke())) { - bonus = hints.get(info.invoke()); - } - - int bytecodeSize = (int) (bytecodeCodeSize(info) / bonus); - int complexity = (int) (compilationComplexity(info) / bonus); - int compiledCodeSize = (int) (compiledCodeSize(info) / bonus); - double relevance = nodeRelevance.get(info.invoke().asNode()); - /* - * as long as the compiled code size is small enough (or the method was not yet - * compiled), we can do a pretty general inlining that suits most situations - */ - if (compiledCodeSize < GraalOptions.SmallCompiledCodeSize) { - if (isTrivialInlining(bytecodeSize, complexity, compiledCodeSize)) { - return InliningUtil.logInlinedMethod(info, "trivial (bytecodes=%d, complexity=%d, codeSize=%d)", bytecodeSize, complexity, compiledCodeSize); - } - - if (canInlineRelevanceBased(relevance, bytecodeSize, complexity, compiledCodeSize)) { - return InliningUtil.logInlinedMethod(info, "relevance-based (relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d)", relevance, bytecodeSize, complexity, compiledCodeSize); - } - } - - /* - * the normal inlining did not fit this invoke, so check if we have any reason why we - * should still do the inlining - */ - double probability = nodeProbabilities.get(info.invoke().asNode()); - int transferredValues = numberOfTransferredValues(info); - int invokeUsages = countInvokeUsages(info); - int moreSpecificArguments = countMoreSpecificArgumentInfo(info); - int level = info.level(); - - // TODO (chaeubl): compute metric that is used to check if this method should be inlined - - return InliningUtil.logNotInlinedMethod(info, - "(relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d, probability=%f, transferredValues=%d, invokeUsages=%d, moreSpecificArguments=%d, level=%d, bonus=%f)", relevance, - bytecodeSize, complexity, compiledCodeSize, probability, transferredValues, invokeUsages, moreSpecificArguments, level, bonus); - } - - private static boolean isTrivialInlining(int bytecodeSize, int complexity, int compiledCodeSize) { - return bytecodeSize < GraalOptions.TrivialBytecodeSize || complexity < GraalOptions.TrivialComplexity || compiledCodeSize > 0 && compiledCodeSize < GraalOptions.TrivialCompiledCodeSize; - } - - private static boolean canInlineRelevanceBased(double relevance, int bytecodeSize, int complexity, int compiledCodeSize) { - return bytecodeSize < computeMaximumSize(relevance, GraalOptions.NormalBytecodeSize) || complexity < computeMaximumSize(relevance, GraalOptions.NormalComplexity) || compiledCodeSize > 0 && - compiledCodeSize < computeMaximumSize(relevance, GraalOptions.NormalCompiledCodeSize); - } - - private static double computeMaximumSize(double relevance, int configuredMaximum) { + protected double computeMaximumSize(double relevance, int configuredMaximum) { double inlineRatio = Math.min(GraalOptions.RelevanceCapForInlining, relevance); return configuredMaximum * inlineRatio; } - private static int numberOfTransferredValues(InlineInfo info) { - MethodCallTargetNode methodCallTargetNode = ((MethodCallTargetNode) info.invoke().callTarget()); - Signature signature = methodCallTargetNode.targetMethod().getSignature(); - int transferredValues = signature.getParameterCount(!Modifier.isStatic(methodCallTargetNode.targetMethod().getModifiers())); - if (signature.getReturnKind() != Kind.Void) { - transferredValues++; + protected double getInliningBonus(InlineInfo info) { + if (hints != null && hints.containsKey(info.invoke())) { + return hints.get(info.invoke()); } - return transferredValues; - } - - private static int countInvokeUsages(InlineInfo info) { - // inlining calls with lots of usages simplifies the caller - int usages = 0; - for (Node n : info.invoke().asNode().usages()) { - if (!(n instanceof FrameState)) { - usages++; - } - } - return usages; + return 1; } - private int countMoreSpecificArgumentInfo(InlineInfo info) { - /* - * inlining invokes where the caller has very specific information about the passed - * argument simplifies the callee - */ - int moreSpecificArgumentInfo = 0; - MethodCallTargetNode methodCallTarget = (MethodCallTargetNode) info.invoke().callTarget(); - boolean isStatic = methodCallTarget.isStatic(); - int signatureOffset = isStatic ? 0 : 1; - NodeInputList arguments = methodCallTarget.arguments(); - ResolvedJavaMethod targetMethod = methodCallTarget.targetMethod(); - ResolvedJavaType methodHolderClass = targetMethod.getDeclaringClass(); - Signature signature = targetMethod.getSignature(); - - for (int i = 0; i < arguments.size(); i++) { - Node n = arguments.get(i); - if (n instanceof ConstantNode) { - moreSpecificArgumentInfo++; - } else if (n instanceof ValueNode && !((ValueNode) n).kind().isPrimitive()) { - ResolvedJavaType actualType = ((ValueNode) n).stamp().javaType(runtime); - JavaType declaredType; - if (i == 0 && !isStatic) { - declaredType = methodHolderClass; - } else { - declaredType = signature.getParameterType(i - signatureOffset, methodHolderClass); - } - - if (declaredType instanceof ResolvedJavaType && !actualType.equals(declaredType) && ((ResolvedJavaType) declaredType).isAssignableFrom(actualType)) { - moreSpecificArgumentInfo++; - } - } - + protected boolean isIntrinsic(InlineInfo info) { + if (GraalOptions.AlwaysInlineIntrinsics) { + return onlyIntrinsics(info); + } else { + return onlyForcedIntrinsics(info); } - - return moreSpecificArgumentInfo; } - private static int bytecodeCodeSize(InlineInfo info) { - int result = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - result += info.methodAt(i).getCodeSize(); - } - return result; - } - - private static int compilationComplexity(InlineInfo info) { - int result = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - result += info.methodAt(i).getCompilationComplexity(); - } - return result; - } - - private static int compiledCodeSize(InlineInfo info) { - int result = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - result += info.methodAt(i).getCompiledCodeSize(); - } - return result; - } - - private static boolean onlyIntrinsics(Replacements replacements, InlineInfo info) { + private boolean onlyIntrinsics(InlineInfo info) { for (int i = 0; i < info.numberOfMethods(); i++) { if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) { return false; @@ -362,7 +529,7 @@ return true; } - private static boolean onlyForcedIntrinsics(Replacements replacements, InlineInfo info) { + private boolean onlyForcedIntrinsics(InlineInfo info) { for (int i = 0; i < info.numberOfMethods(); i++) { if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) { return false; @@ -375,82 +542,137 @@ } } - private static class CFInliningPolicy implements InliningPolicy { + private static class GreedyInliningPolicy extends AbstractInliningPolicy { - private final InliningDecision inliningDecision; - private final Assumptions assumptions; - private final Replacements replacements; - private final OptimisticOptimizations optimisticOpts; - private final Deque sortedInvokes; - private NodeBitMap visitedFixedNodes; - private FixedNode invokePredecessor; - - public CFInliningPolicy(InliningDecision inliningPolicy, Replacements replacements, Assumptions assumptions, OptimisticOptimizations optimisticOpts) { - this.inliningDecision = inliningPolicy; - this.replacements = replacements; - this.assumptions = assumptions; - this.optimisticOpts = optimisticOpts; - this.sortedInvokes = new ArrayDeque<>(); + public GreedyInliningPolicy(Replacements replacements, Map hints) { + super(replacements, hints); } - public boolean continueInlining(StructuredGraph graph) { - if (graph.getNodeCount() >= GraalOptions.MaximumDesiredSize) { + public boolean continueInlining(InliningData data) { + if (data.currentGraph().graph().getNodeCount() >= GraalOptions.MaximumDesiredSize) { InliningUtil.logInliningDecision("inlining is cut off by MaximumDesiredSize"); metricInliningStoppedByMaxDesiredSize.increment(); return false; } - return !sortedInvokes.isEmpty(); - } + MethodInvocation currentInvocation = data.currentInvocation(); + if (currentInvocation == null) { + return true; + } + + InlineInfo info = currentInvocation.callee(); + double inliningBonus = getInliningBonus(info); + + int hirSize = previousHIRSize(info); + if (hirSize > GraalOptions.SmallCompiledGraphSize * inliningBonus) { + return InliningUtil.logNotInlinedMethod(info, "too large HIR graph: %s", hirSize); + } - public InlineInfo next() { - Invoke invoke = sortedInvokes.pop(); - InlineInfo info = InliningUtil.getInlineInfo(invoke, replacements, assumptions, optimisticOpts); - if (info != null) { - invokePredecessor = (FixedNode) info.invoke().predecessor(); - assert invokePredecessor.isAlive(); + int nodes = determineNodeCount(info); + if (nodes < GraalOptions.TrivialHighLevelGraphSize * inliningBonus) { + return InliningUtil.logInlinedMethod(info, "trivial (nodes=%d)", nodes); } - return info; + + double maximumNodes = computeMaximumSize(currentInvocation.relevance(), (int) (GraalOptions.NormalHighLevelGraphSize * inliningBonus)); + if (nodes < maximumNodes) { + return InliningUtil.logInlinedMethod(info, "relevance-based (relevance=%f, nodes=%d)", currentInvocation.relevance(), nodes); + } + + // TODO (chaeubl): compute metric that is used to check if this method should be + // inlined + + return InliningUtil.logNotInlinedMethod(info, "(relevance=%f, probability=%f, bonus=%f)", currentInvocation.relevance(), currentInvocation.probability(), inliningBonus); } @Override - public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { - return inliningDecision.isWorthInlining(info, nodeProbabilities, nodeRelevance); - } + public boolean isWorthInlining(InlineInfo info, double probability, double relevance) { + if (isIntrinsic(info)) { + return InliningUtil.logInlinedMethod(info, "intrinsic"); + } + + double inliningBonus = getInliningBonus(info); + + int hirSize = previousHIRSize(info); + if (hirSize > GraalOptions.SmallCompiledGraphSize * inliningBonus) { + return InliningUtil.logNotInlinedMethod(info, "too large HIR graph: %s", hirSize); + } + + /* + * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> + * will be compiled anyways and it is likely that we are the only caller... might be + * useful to inline those methods but increases bootstrap time (maybe those methods are + * also getting queued in the compilation queue concurrently) + */ + + // TODO (chaeubl): we could do a shortcut here, i.e. if it resulted in something simple + // before avoid building the graphs - public void initialize(StructuredGraph graph) { - visitedFixedNodes = graph.createNodeBitMap(true); - scanGraphForInvokes(graph.start()); - } + // @formatter:off + // trivial + // few nodes + // linear and no invokes + // leaf + // no invokes + // normal + // many nodes + // no frequently executed invokes + // complex + // many nodes + // frequently executed invokes + // @formatter:on - public void scanInvokes(Iterable newNodes) { - assert invokePredecessor.isAlive(); - int invokes = scanGraphForInvokes(invokePredecessor); - assert invokes == countInvokes(newNodes); + int nodes = determineNodeCount(info); + if (nodes < GraalOptions.TrivialHighLevelGraphSize * inliningBonus) { + return InliningUtil.logInlinedMethod(info, "trivial (nodes=%d)", nodes); + } + + double invokes = determineInvokeProbability(info); + if (GraalOptions.LimitInlinedInvokes > 0 && invokes > GraalOptions.LimitInlinedInvokes * inliningBonus) { + return InliningUtil.logNotInlinedMethod(info, "invoke probability is too high (%f)", invokes); + } + + double maximumNodes = computeMaximumSize(relevance, (int) (GraalOptions.NormalHighLevelGraphSize * inliningBonus)); + if (nodes < maximumNodes) { + return InliningUtil.logInlinedMethod(info, "relevance-based (relevance=%f, nodes=%d)", relevance, nodes); + } + + // TODO (chaeubl): compute metric that is used to check if this method should be inlined + + return InliningUtil.logNotInlinedMethod(info, "(relevance=%f, probability=%f, bonus=%f)", relevance, probability, inliningBonus); } - private int scanGraphForInvokes(FixedNode start) { - ArrayList invokes = new InliningIterator(start, visitedFixedNodes).apply(); - - // insert the newly found invokes in their correct control-flow order - for (int i = invokes.size() - 1; i >= 0; i--) { - Invoke invoke = invokes.get(i); - assert !sortedInvokes.contains(invoke); - sortedInvokes.addFirst(invoke); - + private static int previousHIRSize(InlineInfo info) { + int size = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + size += compiledMethodInfo(info.methodAt(i)).getHighLevelNodes(); } - - return invokes.size(); + return size; } - private static int countInvokes(Iterable nodes) { - int count = 0; - for (Node n : nodes) { - if (n instanceof Invoke) { - count++; + private static int determineNodeCount(InlineInfo info) { + int nodes = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + InlineableElement elem = info.inlineableElementAt(i); + if (elem != null) { + nodes += elem.getNodeCount(); } } - return count; + return nodes; + } + + private static double determineInvokeProbability(InlineInfo info) { + double invokeProbability = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + InlineableElement callee = info.inlineableElementAt(i); + Iterable invokes = callee.getInvokes(); + if (invokes.iterator().hasNext()) { + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure((StructuredGraph) callee).apply(); + for (Invoke invoke : invokes) { + invokeProbability += nodeProbabilities.get(invoke.asNode()); + } + } + } + return invokeProbability; } } @@ -467,8 +689,8 @@ assert start.isAlive(); } - public ArrayList apply() { - ArrayList invokes = new ArrayList<>(); + public Stack apply() { + Stack invokes = new Stack<>(); FixedNode current; forcedQueue(start); @@ -477,7 +699,7 @@ if (current instanceof Invoke) { if (current != start) { - invokes.add((Invoke) current); + invokes.push((Invoke) current); } queueSuccessors(current); } else if (current instanceof LoopBeginNode) { @@ -547,8 +769,79 @@ } } - private static InliningPolicy createInliningPolicy(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, OptimisticOptimizations optimisticOpts, Map hints) { - InliningDecision inliningDecision = new GreedySizeBasedInliningDecision(runtime, replacements, hints); - return new CFInliningPolicy(inliningDecision, replacements, assumptions, optimisticOpts); + public static class CompiledMethodInfo { + + private int highLevelNodes; + private int midLevelNodes; + private int lowLevelNodes; + private int compiledCodeSize; + private double summedUpProbabilityOfRemainingInvokes; + private double maxProbabilityOfRemainingInvokes; + private int numberOfRemainingInvokes; + + public CompiledMethodInfo() { + } + + public int getHighLevelNodes() { + return highLevelNodes; + } + + public int getMidLevelNodes() { + return midLevelNodes; + } + + public int getLowLevelNodes() { + return lowLevelNodes; + } + + public int getCompiledCodeSize() { + return compiledCodeSize; + } + + public double getMaxProbabilityOfRemainingInvokes() { + return maxProbabilityOfRemainingInvokes; + } + + public double getSummedUpProbabilityOfRemainingInvokes() { + return summedUpProbabilityOfRemainingInvokes; + } + + public int getNumberOfRemainingInvokes() { + return numberOfRemainingInvokes; + } + + public void setHighLevelNodes(int highLevelNodes) { + this.highLevelNodes = highLevelNodes; + } + + public void setMidLevelNodes(int midLevelNodes) { + this.midLevelNodes = midLevelNodes; + } + + public void setLowLevelNodes(int lowLevelNodes) { + this.lowLevelNodes = lowLevelNodes; + } + + public void setMaxProbabilityOfRemainingInvokes(double maxProbabilityOfRemainingInvokes) { + this.maxProbabilityOfRemainingInvokes = maxProbabilityOfRemainingInvokes; + } + + public void setSummedUpProbabilityOfRemainingInvokes(double summedUpProbabilityOfRemainingInvokes) { + this.summedUpProbabilityOfRemainingInvokes = summedUpProbabilityOfRemainingInvokes; + } + + public void setCompiledCodeSize(int compiledCodeSize) { + this.compiledCodeSize = compiledCodeSize; + } + + public void setNumberOfRemainingInvokes(int numberOfRemainingInvokes) { + this.numberOfRemainingInvokes = numberOfRemainingInvokes; + } + + @Override + public String toString() { + return String.format("High: %d, Mid: %d, Low: %d, Compiled: %d, #Invokes: %d, SumOfInvokes: %f, MaxOfInvokes: %f", highLevelNodes, midLevelNodes, lowLevelNodes, compiledCodeSize, + numberOfRemainingInvokes, summedUpProbabilityOfRemainingInvokes, maxProbabilityOfRemainingInvokes); + } } } diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Wed May 08 16:31:59 2013 +0200 @@ -42,12 +42,12 @@ import com.oracle.graal.nodes.type.*; import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.common.InliningPhase.InliningData; public class InliningUtil { private static final DebugMetric metricInliningTailDuplication = Debug.metric("InliningTailDuplication"); private static final String inliningDecisionsScopeString = "InliningDecisions"; - /** * Meters the size (in bytecodes) of all methods processed during compilation (i.e., top level * and all inlined methods), irrespective of how many bytecodes in each method are actually @@ -55,22 +55,34 @@ */ public static final DebugMetric InlinedBytecodes = Debug.metric("InlinedBytecodes"); - public interface InliningCallback { - - StructuredGraph buildGraph(final ResolvedJavaMethod method); - } - public interface InliningPolicy { - void initialize(StructuredGraph graph); + boolean continueInlining(InliningData data); + + boolean isWorthInlining(InlineInfo info, double probability, double relevance); + } - boolean continueInlining(StructuredGraph graph); + public static class InlineableMacroNode implements InlineableElement { + + private final Class macroNodeClass; + + public InlineableMacroNode(Class macroNodeClass) { + this.macroNodeClass = macroNodeClass; + } - InlineInfo next(); + @Override + public int getNodeCount() { + return 1; + } - void scanInvokes(Iterable newNodes); + @Override + public Iterable getInvokes() { + return Collections.emptyList(); + } - boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance); + public Class getMacroNodeClass() { + return macroNodeClass; + } } /** @@ -211,25 +223,36 @@ */ public interface InlineInfo { + StructuredGraph graph(); + Invoke invoke(); - int level(); - + /** + * Returns the number of invoked methods. + */ int numberOfMethods(); ResolvedJavaMethod methodAt(int index); + InlineableElement inlineableElementAt(int index); + + double probabilityAt(int index); + + double relevanceAt(int index); + + void setInlinableElement(int index, InlineableElement inlineableElement); + /** * Performs the inlining described by this object and returns the node that represents the * return value of the inlined method (or null for void methods and methods that have no * non-exceptional exit). **/ - void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions); + void inline(MetaAccessProvider runtime, Assumptions assumptions); /** * Try to make the call static bindable to avoid interface and virtual method calls. */ - void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions); + void tryToDevirtualizeInvoke(MetaAccessProvider runtime, Assumptions assumptions); } public abstract static class AbstractInlineInfo implements InlineInfo { @@ -241,29 +264,40 @@ } @Override + public StructuredGraph graph() { + return (StructuredGraph) invoke.asNode().graph(); + } + + @Override public Invoke invoke() { return invoke; } - @Override - public int level() { - return computeInliningLevel(invoke); - } + protected static void inline(Invoke invoke, ResolvedJavaMethod concrete, InlineableElement inlineable, Assumptions assumptions, boolean receiverNullCheck) { + StructuredGraph graph = (StructuredGraph) invoke.asNode().graph(); + if (inlineable instanceof StructuredGraph) { + StructuredGraph calleeGraph = (StructuredGraph) inlineable; + InliningUtil.inline(invoke, calleeGraph, receiverNullCheck); - protected static void inline(Invoke invoke, ResolvedJavaMethod concrete, InliningCallback callback, Replacements replacements, Assumptions assumptions, boolean receiverNullCheck) { - Class macroNodeClass = getMacroNodeClass(replacements, concrete); - StructuredGraph graph = (StructuredGraph) invoke.asNode().graph(); - if (macroNodeClass != null) { + graph.getLeafGraphIds().add(calleeGraph.graphId()); + // we might at some point cache already-inlined graphs, so add recursively: + graph.getLeafGraphIds().addAll(calleeGraph.getLeafGraphIds()); + } else { + assert inlineable instanceof InlineableMacroNode; + + Class macroNodeClass = ((InlineableMacroNode) inlineable).getMacroNodeClass(); if (((MethodCallTargetNode) invoke.callTarget()).targetMethod() != concrete) { assert ((MethodCallTargetNode) invoke.callTarget()).invokeKind() != InvokeKind.Static; InliningUtil.replaceInvokeCallTarget(invoke, graph, InvokeKind.Special, concrete); } + FixedWithNextNode macroNode; try { macroNode = macroNodeClass.getConstructor(Invoke.class).newInstance(invoke); } catch (ReflectiveOperationException | IllegalArgumentException | SecurityException e) { throw new GraalInternalError(e).addContext(invoke.asNode()).addContext("macroSubstitution", macroNodeClass); } + CallTargetNode callTarget = invoke.callTarget(); if (invoke instanceof InvokeNode) { graph.replaceFixedWithFixed((InvokeNode) invoke, graph.add(macroNode)); @@ -273,30 +307,10 @@ graph.replaceSplitWithFixed(invokeWithException, graph.add(macroNode), invokeWithException.next()); } GraphUtil.killWithUnusedFloatingInputs(callTarget); - } else { - StructuredGraph calleeGraph = getIntrinsicGraph(replacements, concrete); - if (calleeGraph == null) { - calleeGraph = getGraph(concrete, callback); - } - InlinedBytecodes.add(concrete.getCodeSize()); - assumptions.recordMethodContents(concrete); - InliningUtil.inline(invoke, calleeGraph, receiverNullCheck); + } - graph.getLeafGraphIds().add(calleeGraph.graphId()); - // we might at some point cache already-inlined graphs, so add recursively: - graph.getLeafGraphIds().addAll(calleeGraph.getLeafGraphIds()); - } - } - - protected static StructuredGraph getGraph(final ResolvedJavaMethod concrete, final InliningCallback callback) { - return Debug.scope("GetInliningGraph", concrete, new Callable() { - - @Override - public StructuredGraph call() throws Exception { - assert !Modifier.isNative(concrete.getModifiers()); - return callback.buildGraph(concrete); - } - }); + InlinedBytecodes.add(concrete.getCodeSize()); + assumptions.recordMethodContents(concrete); } } @@ -312,7 +326,8 @@ */ private static class ExactInlineInfo extends AbstractInlineInfo { - public final ResolvedJavaMethod concrete; + protected final ResolvedJavaMethod concrete; + private InlineableElement inlineableElement; public ExactInlineInfo(Invoke invoke, ResolvedJavaMethod concrete) { super(invoke); @@ -320,12 +335,12 @@ } @Override - public void inline(StructuredGraph compilerGraph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) { - inline(invoke, concrete, callback, replacements, assumptions, true); + public void inline(MetaAccessProvider runtime, Assumptions assumptions) { + inline(invoke, concrete, inlineableElement, assumptions, true); } @Override - public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) { + public void tryToDevirtualizeInvoke(MetaAccessProvider runtime, Assumptions assumptions) { // nothing todo, can already be bound statically } @@ -341,9 +356,33 @@ } @Override + public double probabilityAt(int index) { + assert index == 0; + return 1.0; + } + + @Override + public double relevanceAt(int index) { + assert index == 0; + return 1.0; + } + + @Override public String toString() { return "exact " + MetaUtil.format("%H.%n(%p):%r", concrete); } + + @Override + public InlineableElement inlineableElementAt(int index) { + assert index == 0; + return inlineableElement; + } + + @Override + public void setInlinableElement(int index, InlineableElement inlineableElement) { + assert index == 0; + this.inlineableElement = inlineableElement; + } } /** @@ -353,8 +392,9 @@ */ private static class TypeGuardInlineInfo extends AbstractInlineInfo { - public final ResolvedJavaMethod concrete; - public final ResolvedJavaType type; + private final ResolvedJavaMethod concrete; + private final ResolvedJavaType type; + private InlineableElement inlineableElement; public TypeGuardInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, ResolvedJavaType type) { super(invoke); @@ -374,15 +414,39 @@ } @Override - public void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) { - createGuard(graph, runtime); - inline(invoke, concrete, callback, replacements, assumptions, false); + public InlineableElement inlineableElementAt(int index) { + assert index == 0; + return inlineableElement; + } + + @Override + public double probabilityAt(int index) { + assert index == 0; + return 1.0; } @Override - public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) { - createGuard(graph, runtime); - replaceInvokeCallTarget(invoke, graph, InvokeKind.Special, concrete); + public double relevanceAt(int index) { + assert index == 0; + return 1.0; + } + + @Override + public void setInlinableElement(int index, InlineableElement inlineableElement) { + assert index == 0; + this.inlineableElement = inlineableElement; + } + + @Override + public void inline(MetaAccessProvider runtime, Assumptions assumptions) { + createGuard(graph(), runtime); + inline(invoke, concrete, inlineableElement, assumptions, false); + } + + @Override + public void tryToDevirtualizeInvoke(MetaAccessProvider runtime, Assumptions assumptions) { + createGuard(graph(), runtime); + replaceInvokeCallTarget(invoke, graph(), InvokeKind.Special, concrete); } private void createGuard(StructuredGraph graph, MetaAccessProvider runtime) { @@ -416,10 +480,13 @@ */ private static class MultiTypeGuardInlineInfo extends AbstractInlineInfo { - public final List concretes; - public final ArrayList ptypes; - public final int[] typesToConcretes; - public final double notRecordedTypeProbability; + private final List concretes; + private final double[] methodProbabilities; + private final double maximumMethodProbability; + private final ArrayList ptypes; + private final int[] typesToConcretes; + private final double notRecordedTypeProbability; + private final InlineableElement[] inlineableElements; public MultiTypeGuardInlineInfo(Invoke invoke, ArrayList concretes, ArrayList ptypes, int[] typesToConcretes, double notRecordedTypeProbability) { super(invoke); @@ -430,6 +497,28 @@ this.ptypes = ptypes; this.typesToConcretes = typesToConcretes; this.notRecordedTypeProbability = notRecordedTypeProbability; + this.inlineableElements = new InlineableElement[concretes.size()]; + this.methodProbabilities = computeMethodProbabilities(); + this.maximumMethodProbability = maximumMethodProbability(); + assert maximumMethodProbability > 0; + } + + private double[] computeMethodProbabilities() { + double[] result = new double[concretes.size()]; + for (int i = 0; i < typesToConcretes.length; i++) { + int concrete = typesToConcretes[i]; + double probability = ptypes.get(i).getProbability(); + result[concrete] += probability; + } + return result; + } + + private double maximumMethodProbability() { + double max = 0; + for (int i = 0; i < methodProbabilities.length; i++) { + max = Math.max(max, methodProbabilities[i]); + } + return max; } @Override @@ -444,13 +533,35 @@ } @Override - public void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) { + public InlineableElement inlineableElementAt(int index) { + assert index >= 0 && index < concretes.size(); + return inlineableElements[index]; + } + + @Override + public double probabilityAt(int index) { + return methodProbabilities[index]; + } + + @Override + public double relevanceAt(int index) { + return probabilityAt(index) / maximumMethodProbability; + } + + @Override + public void setInlinableElement(int index, InlineableElement inlineableElement) { + assert index >= 0 && index < concretes.size(); + inlineableElements[index] = inlineableElement; + } + + @Override + public void inline(MetaAccessProvider runtime, Assumptions assumptions) { // receiver null check must be the first node InliningUtil.receiverNullCheck(invoke); if (hasSingleMethod()) { - inlineSingleMethod(graph, callback, replacements, assumptions); + inlineSingleMethod(graph(), assumptions); } else { - inlineMultipleMethods(graph, callback, replacements, assumptions); + inlineMultipleMethods(graph(), assumptions); } } @@ -462,7 +573,7 @@ return notRecordedTypeProbability > 0; } - private void inlineMultipleMethods(StructuredGraph graph, InliningCallback callback, Replacements replacements, Assumptions assumptions) { + private void inlineMultipleMethods(StructuredGraph graph, Assumptions assumptions) { int numberOfMethods = concretes.size(); FixedNode continuation = invoke.next(); @@ -538,7 +649,7 @@ PiNode anchoredReceiver = createAnchoredReceiver(graph, node, commonType, receiver, exact); invokeForInlining.callTarget().replaceFirstInput(receiver, anchoredReceiver); - inline(invokeForInlining, concretes.get(i), callback, replacements, assumptions, false); + inline(invokeForInlining, methodAt(i), inlineableElementAt(i), assumptions, false); replacementNodes.add(anchoredReceiver); } @@ -602,8 +713,8 @@ return result; } - private void inlineSingleMethod(StructuredGraph graph, InliningCallback callback, Replacements replacements, Assumptions assumptions) { - assert concretes.size() == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0; + private void inlineSingleMethod(StructuredGraph graph, Assumptions assumptions) { + assert concretes.size() == 1 && inlineableElements.length == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0; BeginNode calleeEntryNode = graph.add(new BeginNode()); @@ -613,8 +724,7 @@ calleeEntryNode.setNext(invoke.asNode()); - ResolvedJavaMethod concrete = concretes.get(0); - inline(invoke, concrete, callback, replacements, assumptions, false); + inline(invoke, methodAt(0), inlineableElementAt(0), assumptions, false); } private void createDispatchOnTypeBeforeInvoke(StructuredGraph graph, BeginNode[] successors, boolean invokeIsOnlySuccessor) { @@ -693,11 +803,11 @@ } @Override - public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) { + public void tryToDevirtualizeInvoke(MetaAccessProvider runtime, Assumptions assumptions) { if (hasSingleMethod()) { - tryToDevirtualizeSingleMethod(graph); + tryToDevirtualizeSingleMethod(graph()); } else { - tryToDevirtualizeMultipleMethods(graph); + tryToDevirtualizeMultipleMethods(graph()); } } @@ -777,15 +887,15 @@ } @Override - public void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) { + public void inline(MetaAccessProvider runtime, Assumptions assumptions) { assumptions.record(takenAssumption); - super.inline(graph, runtime, replacements, callback, assumptions); + super.inline(runtime, assumptions); } @Override - public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) { + public void tryToDevirtualizeInvoke(MetaAccessProvider runtime, Assumptions assumptions) { assumptions.record(takenAssumption); - replaceInvokeCallTarget(invoke, graph, InvokeKind.Special, concrete); + replaceInvokeCallTarget(invoke, graph(), InvokeKind.Special, concrete); } @Override @@ -800,7 +910,7 @@ * @param invoke the invoke that should be inlined * @return an instance of InlineInfo, or null if no inlining is possible at the given invoke */ - public static InlineInfo getInlineInfo(Invoke invoke, Replacements replacements, Assumptions assumptions, OptimisticOptimizations optimisticOpts) { + public static InlineInfo getInlineInfo(InliningData data, Invoke invoke, int maxNumberOfMethods, Replacements replacements, Assumptions assumptions, OptimisticOptimizations optimisticOpts) { if (!checkInvokeConditions(invoke)) { return null; } @@ -809,7 +919,7 @@ ResolvedJavaMethod targetMethod = callTarget.targetMethod(); if (callTarget.invokeKind() == InvokeKind.Special || targetMethod.canBeStaticallyBound()) { - return getExactInlineInfo(replacements, invoke, optimisticOpts, targetMethod); + return getExactInlineInfo(data, invoke, replacements, optimisticOpts, targetMethod); } assert callTarget.invokeKind() == InvokeKind.Virtual || callTarget.invokeKind() == InvokeKind.Interface; @@ -824,50 +934,51 @@ holder = receiverType; if (receiverStamp.isExactType()) { assert targetMethod.getDeclaringClass().isAssignableFrom(holder) : holder + " subtype of " + targetMethod.getDeclaringClass() + " for " + targetMethod; - return getExactInlineInfo(replacements, invoke, optimisticOpts, holder.resolveMethod(targetMethod)); + return getExactInlineInfo(data, invoke, replacements, optimisticOpts, holder.resolveMethod(targetMethod)); } } } if (holder.isArray()) { // arrays can be treated as Objects - return getExactInlineInfo(replacements, invoke, optimisticOpts, holder.resolveMethod(targetMethod)); + return getExactInlineInfo(data, invoke, replacements, optimisticOpts, holder.resolveMethod(targetMethod)); } if (assumptions.useOptimisticAssumptions()) { ResolvedJavaType uniqueSubtype = holder.findUniqueConcreteSubtype(); if (uniqueSubtype != null) { - return getAssumptionInlineInfo(replacements, invoke, optimisticOpts, uniqueSubtype.resolveMethod(targetMethod), new Assumptions.ConcreteSubtype(holder, uniqueSubtype)); + return getAssumptionInlineInfo(data, invoke, replacements, optimisticOpts, uniqueSubtype.resolveMethod(targetMethod), new Assumptions.ConcreteSubtype(holder, uniqueSubtype)); } ResolvedJavaMethod concrete = holder.findUniqueConcreteMethod(targetMethod); if (concrete != null) { - return getAssumptionInlineInfo(replacements, invoke, optimisticOpts, concrete, new Assumptions.ConcreteMethod(targetMethod, holder, concrete)); + return getAssumptionInlineInfo(data, invoke, replacements, optimisticOpts, concrete, new Assumptions.ConcreteMethod(targetMethod, holder, concrete)); } } // type check based inlining - return getTypeCheckedInlineInfo(replacements, invoke, caller, holder, targetMethod, optimisticOpts); + return getTypeCheckedInlineInfo(data, invoke, maxNumberOfMethods, replacements, caller, holder, targetMethod, optimisticOpts); } - private static InlineInfo getAssumptionInlineInfo(Replacements replacements, Invoke invoke, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod concrete, Assumption takenAssumption) { + private static InlineInfo getAssumptionInlineInfo(InliningData data, Invoke invoke, Replacements replacements, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod concrete, + Assumption takenAssumption) { assert !Modifier.isAbstract(concrete.getModifiers()); - if (!checkTargetConditions(replacements, invoke, concrete, optimisticOpts)) { + if (!checkTargetConditions(data, replacements, invoke, concrete, optimisticOpts)) { return null; } return new AssumptionInlineInfo(invoke, concrete, takenAssumption); } - private static InlineInfo getExactInlineInfo(Replacements replacements, Invoke invoke, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod targetMethod) { + private static InlineInfo getExactInlineInfo(InliningData data, Invoke invoke, Replacements replacements, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod targetMethod) { assert !Modifier.isAbstract(targetMethod.getModifiers()); - if (!checkTargetConditions(replacements, invoke, targetMethod, optimisticOpts)) { + if (!checkTargetConditions(data, replacements, invoke, targetMethod, optimisticOpts)) { return null; } return new ExactInlineInfo(invoke, targetMethod); } - private static InlineInfo getTypeCheckedInlineInfo(Replacements replacements, Invoke invoke, ResolvedJavaMethod caller, ResolvedJavaType holder, ResolvedJavaMethod targetMethod, - OptimisticOptimizations optimisticOpts) { + private static InlineInfo getTypeCheckedInlineInfo(InliningData data, Invoke invoke, int maxNumberOfMethods, Replacements replacements, ResolvedJavaMethod caller, ResolvedJavaType holder, + ResolvedJavaMethod targetMethod, OptimisticOptimizations optimisticOpts) { ProfilingInfo profilingInfo = caller.getProfilingInfo(); JavaTypeProfile typeProfile = profilingInfo.getTypeProfile(invoke.bci()); if (typeProfile == null) { @@ -888,7 +999,7 @@ ResolvedJavaType type = ptypes.get(0).getType(); ResolvedJavaMethod concrete = type.resolveMethod(targetMethod); - if (!checkTargetConditions(replacements, invoke, concrete, optimisticOpts)) { + if (!checkTargetConditions(data, replacements, invoke, concrete, optimisticOpts)) { return null; } return new TypeGuardInlineInfo(invoke, concrete, type); @@ -919,8 +1030,12 @@ typesToConcretes[i] = index; } + if (concreteMethods.size() > maxNumberOfMethods) { + return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "polymorphic call with more than %d target methods", maxNumberOfMethods); + } + for (ResolvedJavaMethod concrete : concreteMethods) { - if (!checkTargetConditions(replacements, invoke, concrete, optimisticOpts)) { + if (!checkTargetConditions(data, replacements, invoke, concrete, optimisticOpts)) { return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined"); } } @@ -971,7 +1086,7 @@ } } - private static boolean checkTargetConditions(Replacements replacements, Invoke invoke, ResolvedJavaMethod method, OptimisticOptimizations optimisticOpts) { + private static boolean checkTargetConditions(InliningData data, Replacements replacements, Invoke invoke, ResolvedJavaMethod method, OptimisticOptimizations optimisticOpts) { if (method == null) { return logNotInlinedMethodAndReturnFalse(invoke, method, "the method is not resolved"); } else if (Modifier.isNative(method.getModifiers()) && (!GraalOptions.Intrinsify || !InliningUtil.canIntrinsify(replacements, method))) { @@ -982,7 +1097,7 @@ return logNotInlinedMethodAndReturnFalse(invoke, method, "the method's class is not initialized"); } else if (!method.canBeInlined()) { return logNotInlinedMethodAndReturnFalse(invoke, method, "it is marked non-inlinable"); - } else if (computeRecursiveInliningLevel(invoke.stateAfter(), method) > GraalOptions.MaximumRecursiveInlining) { + } else if (data.countRecursiveInlining(method) > GraalOptions.MaximumRecursiveInlining) { return logNotInlinedMethodAndReturnFalse(invoke, method, "it exceeds the maximum recursive inlining depth"); } else if (new OptimisticOptimizations(method).lessOptimisticThan(optimisticOpts)) { return logNotInlinedMethodAndReturnFalse(invoke, method, "the callee uses less optimistic optimizations than caller"); @@ -1001,20 +1116,6 @@ return count; } - private static int computeRecursiveInliningLevel(FrameState state, ResolvedJavaMethod method) { - assert state != null; - - int count = 0; - FrameState curState = state; - while (curState != null) { - if (curState.method() == method) { - count++; - } - curState = curState.outerFrameState(); - } - return count; - } - static MonitorExitNode findPrecedingMonitorExit(UnwindNode unwind) { Node pred = unwind.predecessor(); while (pred != null) { diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Wed May 08 16:31:59 2013 +0200 @@ -51,16 +51,11 @@ public static float RelevanceCapForInlining = 1f; public static boolean IterativeInlining = ____; - public static int TrivialBytecodeSize = 10; - public static int NormalBytecodeSize = 150; - public static int MaximumBytecodeSize = 500; - public static int TrivialComplexity = 10; - public static int NormalComplexity = 60; - public static int MaximumComplexity = 400; - public static int TrivialCompiledCodeSize = 150; - public static int NormalCompiledCodeSize = 750; - public static int MaximumCompiledCodeSize = 4000; - public static int SmallCompiledCodeSize = 1000; + public static int TrivialHighLevelGraphSize = 20; + public static int NormalHighLevelGraphSize = 100; + public static int SmallCompiledGraphSize = 150; + public static double LimitInlinedInvokes = 10.0; + public static boolean PropagateArgumentsDuringInlining = true; // escape analysis settings public static boolean PartialEscapeAnalysis = true; diff -r 8cee5c95b774 -r 9529ab567367 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java Wed May 08 16:31:59 2013 +0200 @@ -24,7 +24,6 @@ import java.util.*; -import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.util.*; @@ -65,9 +64,7 @@ public NodesToDoubles apply() { new PropagateProbability(graph.start()).apply(); - Debug.dump(graph, "After PropagateProbability"); computeLoopFactors(); - Debug.dump(graph, "After computeLoopFactors"); new PropagateLoopFrequency(graph.start()).apply(); return nodeProbabilities; }