newtype OptLevel = OptLevel ()
    deriving (Show,Typeable,Eq,Hashable,Binary,NFData)
type instance RuleResult OptLevel = String

rules = do
    addOracle $ (OptLevel _) -> return $
        if <whatever you use to decide> then "-O0" else "-O2"

    "foo.o" %> _ -> do
        level <- askOracle $ OptLevel ()
        cmd "gcc" level ...