From 86bc0909613e19e284b40fce9f9914e3a115bbe8 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 14 Feb 2023 16:14:51 +0100 Subject: [PATCH] Fix possible sanopt compile-time hog While working on bitmap operations I figured sanopt.cc uses a sbitmap worklist, iterating using bitmap_first_set_bit on it. That's quadratic since bitmap_first_set_bit for sbitmap is O(n). The fix is to use regular bitmaps for the worklist and the bitmap feeding it and to avoid a useless copy. * sanopt.cc (sanitize_asan_mark_unpoison): Use bitmap for with_poison and alias worklist to it. (sanitize_asan_mark_poison): Likewise. --- gcc/sanopt.cc | 17 ++++++----------- 1 file changed, 6 insertions(+), 11 deletions(-) diff --git a/gcc/sanopt.cc b/gcc/sanopt.cc index aed2285..b356a21 100644 --- a/gcc/sanopt.cc +++ b/gcc/sanopt.cc @@ -987,15 +987,11 @@ static void sanitize_asan_mark_unpoison (void) { /* 1) Find all BBs that contain an ASAN_MARK poison call. */ - auto_sbitmap with_poison (last_basic_block_for_fn (cfun) + 1); - bitmap_clear (with_poison); + auto_bitmap with_poison; basic_block bb; FOR_EACH_BB_FN (bb, cfun) { - if (bitmap_bit_p (with_poison, bb->index)) - continue; - gimple_stmt_iterator gsi; for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) { @@ -1010,8 +1006,8 @@ sanitize_asan_mark_unpoison (void) auto_sbitmap poisoned (last_basic_block_for_fn (cfun) + 1); bitmap_clear (poisoned); - auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1); - bitmap_copy (worklist, with_poison); + /* We now treat with_poison as worklist. */ + bitmap worklist = with_poison; /* 2) Propagate the information to all reachable blocks. */ while (!bitmap_empty_p (worklist)) @@ -1088,8 +1084,7 @@ static void sanitize_asan_mark_poison (void) { /* 1) Find all BBs that possibly contain an ASAN_CHECK. */ - auto_sbitmap with_check (last_basic_block_for_fn (cfun) + 1); - bitmap_clear (with_check); + auto_bitmap with_check; basic_block bb; FOR_EACH_BB_FN (bb, cfun) @@ -1108,8 +1103,8 @@ sanitize_asan_mark_poison (void) auto_sbitmap can_reach_check (last_basic_block_for_fn (cfun) + 1); bitmap_clear (can_reach_check); - auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1); - bitmap_copy (worklist, with_check); + /* We now treat with_check as worklist. */ + bitmap worklist = with_check; /* 2) Propagate the information to all definitions blocks. */ while (!bitmap_empty_p (worklist)) -- 2.7.4