From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14479 invoked by alias); 2 Jan 2005 23:15:19 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 14412 invoked by alias); 2 Jan 2005 23:15:12 -0000 Date: Sun, 02 Jan 2005 23:15:00 -0000 Message-ID: <20050102231512.14409.qmail@sourceware.org> From: "sebastian dot pop at cri dot ensmp dot fr" To: gcc-bugs@gcc.gnu.org In-Reply-To: <20050102074446.19224.aj@gcc.gnu.org> References: <20050102074446.19224.aj@gcc.gnu.org> Reply-To: gcc-bugzilla@gcc.gnu.org Subject: [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? X-Bugzilla-Reason: CC X-SW-Source: 2005-01/txt/msg00154.txt.bz2 List-Id: ------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr 2005-01-02 23:15 ------- Subject: Re: [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? rakdver at gcc dot gnu dot org wrote: > > ------- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-02 18:55 ------- > Caused by an exponential time complexity of instantiate_parameters. > I am working on a patch. > The following patch solves the exponential time complexity. Sorry for the inconvenient. Sebastian *************** instantiate_parameters_1 (struct loop *l *** 1946,1960 **** result again. Avoid the cyclic instantiation in mixers. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), allow_superloop_chrecs); if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); --- 2005,2026 ---- result again. Avoid the cyclic instantiation in mixers. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! if (res != chrec_dont_know) ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1963,1970 **** --- 2029,2042 ---- case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1973,1980 **** --- 2045,2058 ---- case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1983,1990 **** --- 2061,2074 ---- case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 2018,2027 **** --- 2102,2120 ---- case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), allow_superloop_chrecs); + if (op2 == chrec_dont_know) + return chrec_dont_know; + if (op0 == chrec_dont_know || op1 == chrec_dont_know || op2 == chrec_dont_know) *************** instantiate_parameters_1 (struct loop *l *** 2038,2047 **** case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); ! if (op0 == chrec_dont_know ! || op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) --- 2131,2142 ---- case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); ! if (op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224